Multi-University Training Contest 1 BY BUAA

1001. Add More Zero

题意：给定m，找到最大的k满足[tex]10^k<2^m[/tex]。

题解：发现[tex]k<\log_{10}{2^m}[/tex]，由于[tex]10^k\neq 2^m[/tex]，所以变形得到[tex]k=\lfloor m*\log_{10}{2}\rfloor[/tex]。

#include<bits/stdc++.h>
using namespace std;
int x,_;
int main(){
	while(scanf("%d",&x)!=EOF)
		printf("Case #%d: %d\n",++_,(int)(x/log2(10.)));
}

1002. Balala Power

题意：给定n个小写字符串，让你将每个小写字母映射成0~25中的一个数字，任意两个小写字母映射字母不能相同。

要求给定的n个字符串表示成的26进制数的和最大。必须保证每个数不包含前缀0。

题解：首先我们可以统计出每种字符在各个字符串中出现的和，用一个26进制数表示。

之后我们找到一个出现和最小的，合法的字母赋值为0。最后我们将剩下的数从大到小排序后依次分配25~1即可。

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a[26][110000],S[26],*p,use[26],ans,i,j,n,f[26],m,t,q,pp,_;
char s[110000];
int comp(int x,int y){
	if(S[x]>S[y])return 1;
	if(S[x]<S[y])return 0;
	for(int i=S[x];i>=1;i--){
		if(a[x][i]>a[y][i])return 1;
		if(a[x][i]<a[y][i])return 0;
	}
	return 0;
}
int main(){
	while(scanf("%d",&n)!=EOF){
		ans=0;
		memset(use,0,sizeof(use));
		for(i=0;i<26;S[i]=0,i++)
			for(j=1;j<=S[i];j++)
				a[i][j]=0;
		memset(f,0,sizeof(f));
		for(i=1;i<=n;i++){
			scanf("%s",s+1);
			m=strlen(s+1);
			if(m>1)f[s[1]-'a']=1;
			for(j=1;j<=m;j++)
				a[s[j]-'a'][m-j+1]++,S[s[j]-'a']=max(S[s[j]-'a'],m-j+1);
		}
		for(i=0;i<26;i++){
			p=a[i];
			for(j=1;j<=S[i];j++){
				p[j+1]+=p[j]/26;
				p[j]%=26;
				if(p[S[i]+1])S[i]++;
			}
		}
		t=-1;
		for(i=0;i<26;i++)
		if(!f[i]){
			if(t<0){t=i;continue;}
			if(comp(t,i))t=i;
		}
		use[t]=1;
		for(i=25;i>0;i--){
			q=-1;
			for(j=0;j<26;j++)if(!use[j]){
				if(q<0){q=j;continue;}
				if(comp(j,q))q=j;
			}
			use[q]=1;
			for(j=pp=1;j<=S[q];j++,pp=1ll*pp*26%mod)
				ans=(ans+1ll*pp*a[q][j]*i)%mod;
		}
		printf("Case #%d: %d\n",++_,ans);
	}
}

1003. Colorful Tree

题意：有一棵n个节点的树，每个节点有颜色。一条路径的权值为路径上出现的颜色种类数。询问树上所有路径权值和。

题解：我们可以考虑对每种颜色分别计算贡献。

对于一条路径上的同色点，我们只考虑深度最小的点，深度相同则比较dfs序。

那么对于每一个节点，我们只要计算两条都在子树中和一条在子树中一条在外的情况，将两种情况加起来即可。

对每种颜色建立虚树进行遍历即可解决问题。

#include<bits/stdc++.h> 
#define N 400010
using namespace std;
vector<int> vec[N];
int n,i,x,y,m,j,a[N],p,fa[N],P[N],top,stark[N],V[N],fat[N],_;
int v[N],ne[N],head[N],dad[20][N],sz[N],l,dfn[N],cnt,deep[N],en[N];
long long sp[N],ans;
bool cmp(int x,int y){return dfn[x]<dfn[y];}
bool cmp1(int x,int y){return deep[x]<deep[y];}
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
void dfs(int x){
	int i;
	sz[x]=1;
	sp[x]=0;
	dfn[x]=++cnt;
	deep[x]=deep[dad[0][x]]+1;
	for(i=0;dad[i][x];i++)
		dad[i+1][x]=dad[i][dad[i][x]];
	for(i=head[x];i;i=ne[i])
	if(v[i]!=dad[0][x]){
		dad[0][v[i]]=x;
		dfs(v[i]);
		sz[x]+=sz[v[i]];
		sp[x]-=1ll*sz[v[i]]*(sz[v[i]]-1)/2;
	}
	sp[x]+=1ll*sz[x]*(sz[x]-1)/2;
	en[x]=cnt;
}
int get(int x,int y){
	for(int i=0;y>>i;i++)
		if(y>>i&1)x=dad[i][x];
	return x;
}
int main(){
	while(scanf("%d",&n)!=EOF){
		ans=0;
		for(i=1;i<=n;i++)vec[i].clear();
		memset(dad,0,sizeof(dad));
		memset(head,0,sizeof(head));
		l=cnt=0;
		for(i=1;i<=n;i++)
			scanf("%d",&x),vec[x].push_back(i);
		for(i=1;i<n;i++){
			scanf("%d%d",&x,&y);
			add(x,y);add(y,x);
		}
		dfs(1);
		en[0]=n+1;
		for(i=1;i<=n;i++)
		if(vec[i].size()){
			m=vec[i].size();
			for(j=0;j<m;j++)a[j]=vec[i][j];
			a[m++]=0;
			sort(a,a+m,cmp);
			for(j=0;j<m;j++)fa[j]=0;
			stark[top=1]=0;
			for(j=1;j<m;j++){
				for(;en[a[stark[top]]]<dfn[a[j]]&⊤top--);
				fa[j]=stark[top];
				stark[++top]=j;
			}
			for(j=1;j<m;j++)
				P[fat[a[j]]=get(a[j],deep[a[j]]-deep[a[fa[j]]]-1)]=sz[fat[a[j]]];
			sort(a,a+m,cmp1);
			for(j=1;j<m;j++){
				P[fat[a[j]]]-=sz[a[j]];
				ans+=sp[a[j]]+1ll*sz[a[j]]*P[fat[a[j]]];
			}
			for(j=1;j<m;j++)P[fat[a[j]]]=0,fat[a[j]]=0;
		}
		printf("Case #%d: %lld\n",++_,ans);
	}
}