2017 Multi-University Training 1 解题报告
Add More Zero
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2245 Accepted Submission(s): 1053
Problem Description
There is a youngster known for amateur propositions concerning several mathematical hard problems.
Nowadays, he is preparing a thought-provoking problem on a specific type of supercomputer which has ability to support calculations of integers between 0
and (2m−1)
(inclusive).
As a young man born with ten fingers, he loves the powers of 10
so much, which results in his eccentricity that he always ranges integers he would like to use from 1
to 10k
(inclusive).
For the sake of processing, all integers he would use possibly in this interesting problem ought to be as computable as this supercomputer could.
Given the positive integer m
, your task is to determine maximum possible integer k
that is suitable for the specific supercomputer.
Input
The input contains multiple test cases. Each test case in one line contains only one positive integer m
, satisfying 1≤m≤ 105 .
Output
For each test case, output "Case #x
: y
" in one line (without quotes), where x
indicates the case number starting from 1
and y
denotes the answer of corresponding case.
Sample Input
64
Sample Output
Case #1: 0
Case #2: 19
该题求 2m -1 在10进制下的位数-1,我们注意到 k=log102m-1 ,因为 2m-1 != 10k1 且 2m!=10k2($ k_1 k_2 $都为任意正整数),所以 k=log102m-1 ,把m提出来,于是k=mlog102,这样O(1)即可算出答案。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
int main()
{
int m;
int t = ;
while(cin >> m) { cout << "Case #" << t ++ << ": " << (int)(m*0.30102999566)<< "\n";
}
return ;
}
Balala Power!
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 4809 Accepted Submission(s): 387
Problem Description
Talented Mr.Tang has n
strings consisting of only lower case characters. He wants to charge them with Balala Power (he could change each character ranged from a to z into each number ranged from 0 to 25, but each two different characters should not be changed into the same number) so that he could calculate the sum of these strings as integers in base 26
hilariously.
Mr.Tang wants you to maximize the summation. Notice that no string in this problem could have leading zeros except for string "0". It is guaranteed that at least one character does not appear at the beginning of any string.
The summation may be quite large, so you should output it in modulo 109+7
.
Input
The input contains multiple test cases.
For each test case, the first line contains one positive integers n
, the number of strings. (1≤n≤100000)
Each of the next n
lines contains a string si
consisting of only lower case letters. (1≤|si|≤100000,∑|si|≤106)
Output
For each test case, output "Case #x
: y
" in one line (without quotes), where x
indicates the case number starting from 1
and y
denotes the answer of corresponding case.
Sample Input
a
2
aa
bb
3
a
ba
abc
Sample Output
Case #1: 25
Case #2: 1323
Case #3: 18221
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define mod 1000000007
#define LL long long
using namespace std;
char ss[];
int n,m,k,l,t,minc,len;
int charc[][];
bool firsted[];
int inf[];
bool comp(int a,int b)
{
for(int i=m;i>=;i--)
if(charc[a-'a'][i]!=charc[b-'a'][i])
return charc[a-'a'][i]>charc[b-'a'][i];
return ;
}
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int T,kase=;
LL ans,mul;
while(scanf("%d",&n)!=EOF)
{
m=;
clr(firsted);
clr(charc);
printf("Case #%d: ",++kase);
for(int i=;i<=n;i++)
{
scanf("%s",ss);
len=strlen(ss);
if(len>) firsted[ss[]]=;
reverse(ss,ss+len);
for(int j=;j<len;j++)
charc[ss[j]-'a'][j]++;
m=max(m,len);
}
for(int i='a';i<='z';i++)
{
// cout<<i<<":";
for(int j=;j<m;j++)
{
if(charc[i-'a'][j]>)
{
charc[i-'a'][j+]+=charc[i-'a'][j]/;
charc[i-'a'][j]%=;
}
// cout<<" "<<charc[i-'a'][j];
}
while(charc[i-'a'][m]>)
{
charc[i-'a'][m+]+=charc[i-'a'][m]/;
charc[i-'a'][m]%=;
m++;
// cout<<" "<<charc[i-'a'][m];
}
if(charc[i-'a'][m]>)
m++;
// cout<<endl;
}
clr(inf);
ans=;
for(int i=;i<=;i++)
{
for(int j='a';j<='z';j++)
if((i== && firsted[j]==) || (i!= && inf[j-'a']==))
{
minc=j;
break;
}
for(int j='a';j<='z';j++)
if((i== && firsted[j]==) || (i!= && inf[j-'a']==))
if(!comp(j,minc))
minc=j;
mul=;
for(int j=;j<=m;j++)
{
ans=(ans+(LL)charc[minc-'a'][j]*mul*(LL)i)%mod;
mul=(mul*)%mod;
}
inf[minc-'a']=;
// cout<<ans<<" "<<maxc<<endl;
}
printf("%lld\n",ans);
}
return ;
}
Colorful Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 392 Accepted Submission(s): 68
Problem Description
There is a tree with n
nodes, each of which has a type of color represented by an integer, where the color of node i
is ci
.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has n(n−1)2
paths in total.
Input
The input contains multiple test cases.
For each test case, the first line contains one positive integers n
, indicating the number of node. (2≤n≤200000)
Next line contains n
integers where the i
-th integer represents ci
, the color of node i
. (1≤ci≤n)
Each of the next n−1
lines contains two positive integers x,y
(1≤x,y≤n,x≠y)
, meaning an edge between node x
and node y
.
It is guaranteed that these edges form a tree.
Output
For each test case, output "Case #x
: y
" in one line (without quotes), where x
indicates the case number starting from 1
and y
denotes the answer of corresponding case.
Sample Input
1 2 1
1 2
2 3
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6
Sample Output
Case #1: 6
Case #2: 29
该题应该按照颜色来求解,而不是点和路径来求解。每种颜色对答案的贡献为所有经过该颜色的点的路径数,也就是所有的路径数减去没有经过该颜色的点的路径数。那么求解量转化成该颜色的点的路径数之后,对于每个颜色我们接下来则是找树上没有经过该颜色的块,统计块内的点的数量,这些点都是互相可达且不经过该颜色,那么块内不经过该颜色的路径数就是块中点数ki*(ki-1)/2。那么很浅显的一个思路就是对于每个颜色都用dfs求解出不经过颜色的块然后用总的路径数减去每个块内的路径数,即为每个颜色的贡献。可是这个时间复杂度会很高,那能不能在一次dfs内解决呢?我们可以发觉在对每个颜色的点的dfs中,我们只有dfs到该颜色的点才有操作,去计算块内点的数量。那么一遍dfs的话,对于每个点它对应的颜色都应该有相应的操作,这样思路就显而易见了。我们在一次dfs中可以统计对于每个点子树中节点的数量,然后我们对于每个颜色都设置一个栈来存储该颜色的点的编号。当到dfs到某个点时,我们将该点的编号入相应颜色的栈继续向下dfs。然后回到该点的时候将该颜色在该点之后入栈的点全部都pop出来,然后该颜色的块的点的数量即为该点子树的点的数量减去pop出来的点的子树的数量,计算下路径数加入答案中作为没有经过该颜色的点的路径数的贡献。最后拿每个颜色的所有路径数的和,减去这个没有经过每个颜色的点的路径数的总和即为答案。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define LL long long
using namespace std;
int head[],cnt,ncnt,dif,col[];
LL ans;
int n,m,k,t,s,l;
struct edg
{
int next,to;
}edge[];
void addedge(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
return ;
}
int some[];
stack<int> sta[];
void dfs(int u,int pred)
{
some[u]=;
sta[col[u]].push(u);
for(int i=head[u];i!=-;i=edge[i].next)
{
if(edge[i].to!=pred)
{
dfs(edge[i].to,u);
some[u]+=some[edge[i].to];
dif=some[edge[i].to];
while(sta[col[u]].top()!=u)
{
dif-=some[sta[col[u]].top()];
sta[col[u]].pop();
}
ans+=(LL)dif*(dif-)/;
}
}
return ;
}
int main()
{
int kase=,u,v,diff,p;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
while(!sta[i].empty())
sta[i].pop();
printf("Case #%d: ",++kase);
clr_1(head);
cnt=ncnt=;
for(int i=;i<=n;i++)
scanf("%d",&col[i]);
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
ans=;
clr(some);
dfs(,);
for(int i=;i<=n;i++)
{
diff=n;
while(!sta[i].empty())
{
p=sta[i].top();
diff-=some[p];
sta[i].pop();
}
ans+=(LL)diff*(LL)(diff-)/;
}
ans=(LL)n*n*(n-)/-ans;
printf("%lld\n",ans);
}
return ;
}
KazaQ's Socks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2375 Accepted Submission(s): 1074
At the beginning, he has n
pairs of socks numbered from 1
to n
in his closets.
Every morning, he puts on a pair of socks which has the smallest number in the closets.
Every evening, he puts this pair of socks in the basket. If there are n−1
pairs of socks in the basket now, lazy KazaQ has to wash them. These socks will be put in the closets again in tomorrow evening.
KazaQ would like to know which pair of socks he should wear on the k
-th day.
)
For each case, there is a line contains two numbers n,k
(2≤n≤109,1≤k≤1018)
.
: y
" in one line (without quotes), where xindicates the case number starting from 1
and y
denotes the answer of corresponding case.
3 6
4 9
Case #2: 1
Case #3: 2
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define LL long long
using namespace std;
int main()
{
LL n,k,kase=,t,l,ans;
while(scanf("%lld%lld",&n,&k)!=EOF)
{
printf("Case #%lld: ",++kase);
if(k<=n)
printf("%lld\n",k);
else
{
k-=n;
t=k/(n-);
l=k%(n-);
if(l!=)
printf("%lld\n",l);
else if(t&)
printf("%lld\n",n-);
else
printf("%lld\n",n);
}
}
return ;
}
Function
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1464 Accepted Submission(s): 688
from 0
to n−1
and a permutation b
from 0
to m−1
.
Define that the domain of function f
is the set of integers from 0
to n−1
, and the range of it is the set of integers from 0
to m−1
.
Please calculate the quantity of different functions f
satisfying that f(i)=bf(ai)
for each i
from 0
to n−1
.
Two functions are different if and only if there exists at least one integer from 0
to n−1
mapped into different integers in these two functions.
The answer may be too large, so please output it in modulo 109+7
.
For each case:
The first line contains two numbers n,
m
. (1≤n≤100000,1≤m≤100000)
The second line contains n
numbers, ranged from 0
to n−1
, the i
-th number of which represents ai−1
.
The third line contains m
numbers, ranged from 0
to m−1
, the i
-th number of which represents bi−1
.
It is guaranteed that ∑n≤106,
∑m≤106
.
: y
" in one line (without quotes), where xindicates the case number starting from 1
and y
denotes the answer of corresponding case.
1 0 2
0 1
3 4
2 0 1
0 2 3 1
Case #2: 4
这题列下题目中给的式子将$ a_i $代入就能发现,这些式子构成了一些不相交且包含 1~n所有数的循环。于是我们对于a 中的每个循环,查找b中循环节为其循环节因数的循环的数量乘上该循环长度,将其求和,即为a中该循环可对应的f的映射数。那么a中每个循环的f的映射数相乘,即为对应的不同的映射数。
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define mod 1000000007
#define LL long long
using namespace std;
int a[];
int b[];
int knot[],inf[];
/*int prime[100010],infp[100010];
int ncnt;
void primer(int n)
{
ncnt=0;
clr(infp);
infp[1]=infp[2]=1;
for(int i=2;i<=n;i++)
{
if(!inf[i])
{
prime[++ncnt]=i;
}
for(int j=1;j<=ncnt;j++)
{
if(i*prime[j]>n) break;
infp[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
return ;
}*/
LL deal(LL l)
{
LL ans=;
for(int i=;i<=sqrt(l);i++)
{
if(l%i==)
{
ans=(ans+(LL)knot[l/i]*(LL)(l/i))%mod;
if(l/i!=i) ans=(ans+(LL)knot[i]*(LL)i)%mod;
}
}
return ans;
}
int main()
{
int kase=;
int n,m,sized,minsize,k,l;
LL t,ans;
// init();
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("Case #%d: ",++kase);
for(int i=;i<n;i++)
scanf("%d",&a[i]);
for(int i=;i<m;i++)
scanf("%d",&b[i]);
clr(inf);
clr(knot);
sized=m;
minsize=;
t=;
while(sized)
{
if(inf[minsize]!=)
minsize++;
l=;
k=minsize;
while(inf[k]==)
{
inf[k]=;
sized--;
k=b[k];
l++;
// cout<<k<<endl;
}
knot[l]++;
// cout<<endl;
}
ans=;
clr(inf);
sized=n;
minsize=;
while(sized)
{
while(inf[minsize]!=)
minsize++;
k=minsize;
l=;
while(inf[k]==)
{
inf[k]=;
sized--;
k=a[k];
l++;
}
ans=(ans*deal((LL)l))%mod;
}
printf("%lld\n",ans%mod);
}
return ;
}
最新文章
- CSS入门常见的问题
- 在Visual Studio 2012中使用VMSDK开发领域特定语言(一)
- MySQL中进行模糊搜索的一些问题
- 组合数问题hdu5894
- LightOj 1236 - Pairs Forming LCM (分解素因子,LCM )
- 为该目录以及子目录添加index.html
- linux下find查找命令用法
- iOS 中KVC、KVO、NSNotification、delegate 总结及区别-b
- SQL重复记录查询的几种方法
- Android 应用加固(乐固)操作说明
- Grains 与 Pillars
- jQuery对象与DOM对象互相转换
- List 接口中ArrayList Vector LinkedList 比较
- go 练习
- Tomcat环境变量,端口号,编码格式,项目路径,默认页的配置
- 【Linux】Ubuntu配置服务自启动 sysv-rc-conf
- 测试word发表博客
- TCP客户端【TcpClient】
- stdlib.h
- C#控制台应用程序之选课系统
热门文章
- 线程,JSP,Servlet面试题
- Linux 入门记录:八、Linux 文件系统
- Sql Server 2014/2012/2008/2005 数据库还原出现 3154错误的解决办法
- $scope作用及模块化解决全局问题
- HDU 5118 GRE Words Once More!
- win7下安装 LINUX虚拟机
- 在Redis集群中使用pipeline批量插入
- 0,null,undefined,[],{},&#39;&#39;,false之间的关系
- 一、python基础相关知识体系
- Set Matrix Zeroes——常数空间内完成