devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024蓝桥杯省赛C++软件算法研究生组题解(含代码)+游记_蓝桥杯2024年答案c++

作者：不正经 | 2024-05-07 21:40:07

赞

踩

蓝桥杯2024年答案c++

A题

给你一个音游的游戏记录log.txt，判断玩家的最高连击数

题解

水题，但是要小心，miss的键需要重置k=0，超时但正确的键重置k=1

个人答案是9

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. char a[5],b[5];
  6. int main()
  7. {
  8. 	long long x,lasx=0;
  9. 	int mx=0,k=0;
  10. 	freopen("log.txt","r",stdin);
  11. 	while(~scanf("%s%s%lld",a,b,&x)){
  12. 		//printf("%c %c %lld\n",a[0],b[0],x);
  13. 		if(a[0]==b[0]){
  14. 			if(x-lasx>1000)
  15. 				k=1;
  16. 			else{
  17. 				k++;
  18. 				if(mx<k)
  19. 					mx=k;
  20. 			}
  21. 		}
  22. 		else
  23. 			k=0;
  24. 		lasx=x;
  25. 	}
  26. 	printf("%d",mx);
  27. }

B题

计算1~2024041331404202中有多少个数x满足x! - x*(x+1)/2能被100整除

题解

首先x=10时，x！就会被100整除，所以只需要后面x*(x+1)/2能被100整除即可

可以数论分类讨论，x*(x+1)的因子需要包含3个2和2个5，然后通过x和x+1的奇偶性来删除一些讨论的情况

但是我选择打表，发现x每1000构成一个循环，1~1000只有20个x满足条件

然后再暴力判断一下1~10是否有满足原条件的，发现只有1、3满足

所以最后答案就是1+1+2024041331404 * 20 + 4（24、175、199、200<=202）

40480826628086

（之前写的内容错了，发现自己考场上少算了一个3。。。）

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. int main()
  6. {
  7. 	long long i,j,tot=0;
  8. 	long long ans=0;
  9. 	for(i=1;i<=1000;i++){
  10. 		if((i*(i+1)/2)%100==0){
  11. 			printf("%lld\n",i);
  12. 			tot++;
  13. 		}
  14. 	}
  15. 	printf("%lld\n",tot);
  16. 	long long jc=1;
  17. 	for(i=1;i<=10;i++){
  18. 		jc*=i;
  19. 		if((jc-i*(i+1)/2)%100==0){
  20. 			printf("%lld\n",i);
  21. 			ans++;
  22. 		}
  23. 	}
  24. 	ans+=2024041331404202ll/1000*tot+4;
  25. 	printf("%lld\n",ans);
  26. }

C题

一个长度为n的数组a[i]

给出数字的封闭图形数的定义

12357没有封闭图形，0469有一个封闭图形，8有两个封闭图形

要求以封闭图形数为第一关键字，数字值为第二关键字给数组排序。

n<=10^5,a[i]<=10^9

题解

结构体排序基础题

每个数字先算出它的封闭图形数作为第一关键字，再把它本身的值作为第二关键字。

结构体排序即可。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 200005
  13. struct node{
  14. 	int x,sum;
  15. 	bool operator < (const node &t)const{
  16. 		return sum<t.sum||(sum==t.sum&&x<t.x);
  17. 	}
  18. }a[N];
  19. int f[15]={1,0,0,0,1,0,1,0,2,1};
  20. int calsum(int x)
  21. {
  22. 	if(x==0) return 1;
  23. 	int sum=0;
  24. 	while(x){
  25. 		sum+=f[x%10];
  26. 		x/=10;
  27. 	}
  28. 	return sum;
  29. }
  30. int main()
  31. {
  32. 	int n,i;
  33. 	n=gi();
  34. 	for(i=1;i<=n;i++){
  35. 		a[i].x=gi();
  36. 		a[i].sum=calsum(a[i].x);
  37. 	}
  38. 	sort(a+1,a+n+1);
  39. 	printf("%d",a[1].x);
  40. 	for(i=2;i<=n;i++)
  41. 		printf(" %d",a[i].x);
  42. }

D题

给出n个长度为m的环形字符串，设每两个字符串的边权为LCS（最长公共子串）

求连接这n个字符串的最大生成树的代价

n<=200,m<=50

题解

显然瓶颈在建图，后面随便上一个生成树算法都能过。

看题的时候呆住了，想了一下自己SA和SAM都不会，这下咋办

突然发现不需要高级的算法

先O(n^2)枚举所有字符串对

再O（logm）二分答案最长公共子串的长度

最后O(mlogm)哈希检查LCS是否存在

对每个字符串先预处理出各个长度下的哈希值，保存到map里面

总时间复杂度O(n^2*m*(logm)^2)，空间复杂度O(n*m^2)

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<map>
  5. using namespace std;
  6. #define N 205
  7. #define M 55
  8. const int mod = 1000000007;
  9. const int base = 31;
  10. char s[N][M*2];
  11. map<int,bool> mp[N][M];
  12. struct node{
  13. 	int u,v,cd;
  14. 	node(){}
  15. 	node(int _u,int _v,int _cd){
  16. 		u=_u;v=_v;cd=_cd;
  17. 	}
  18. 	bool operator < (const node &t)const{
  19. 		return cd>t.cd;
  20. 	}
  21. }e[N*N];
  22. int h[M][M];
  23. int ecnt;
  24. int fa[N];
  25. int find(int x){
  26. 	return x==fa[x]?x:fa[x]=find(fa[x]);
  27. }
  28. int main()
  29. {
  30. 	int n,m,i,j,k;
  31. 	scanf("%d%d",&n,&m);
  32. 	for(i=1;i<=n;i++){
  33. 		scanf("%s",s[i]+1);
  34. 		for(j=1;j<=m;j++)
  35. 			s[i][j+m]=s[i][j];
  36. 		for(j=1;j<=m;j++){
  37. 			int hh=0;
  38. 			for(k=j;k<j+m;k++){
  39. 				hh=(1ll*hh*base+s[i][k]-96)%mod;
  40. 				h[k-j+1][j]=hh;
  41. 				mp[i][k-j+1][hh]=1;
  42. 			}
  43. 		}
  44. 		for(j=1;j<i;j++){
  45. 			int l=1,r=m,ans=0,mid;
  46. 			while(l<=r){
  47. 				mid=(l+r)>>1;
  48. 				bool flg=0;
  49. 				for(k=1;k<=m;k++)
  50. 					if(mp[j][mid][h[mid][k]]==1){
  51. 						flg=1;
  52. 						break;
  53. 					}
  54. 				if(flg){
  55. 					l=mid+1;
  56. 					ans=mid;
  57. 				}
  58. 				else
  59. 					r=mid-1;
  60. 			}
  61. 			e[++ecnt]=node(i,j,ans);
  62. 		}
  63. 	}
  64. //	for(i=1;i<=ecnt;i++){
  65. //		printf("%d %d %d\n",e[i].u,e[i].v,e[i].cd);
  66. //	}
  67. 	sort(e+1,e+ecnt+1);
  68. 	for(i=1;i<=n;i++)fa[i]=i;
  69. 	int ans=0,ncnt=0;
  70. 	for(i=1;i<=ecnt;i++){
  71. 		int p=find(e[i].u);
  72. 		int q=find(e[i].v);
  73. 		if(p!=q){
  74. 			fa[p]=q;
  75. 			ans+=e[i].cd;
  76. 			ncnt++;
  77. 			if(ncnt==n-1)
  78. 				break;
  79. 		}
  80. 	}
  81. 	printf("%d",ans);
  82. }

E题

数轴上有n个点，第i个点在ai，从0开始，走一步将坐标-1 或者 +1，一共可以走m步，问最多可以经过多少个点，重复经过一个点只算做一次。

n<=10^5, ai<=10^6,m<=2*10^6

题解

简单贪心

显然不可能反复横跳找点，这样会浪费步数

所以要么向左走到头，然后向右走用完步数；要么反过来。（路径只会有一个拐点）

发现m实际上很小，甚至可以直接暴力前缀和，直接统计m范围内的点。

直接枚举向左、向右走到的位置（拐点），然后前缀和O(1)查询即可。

时间复杂度O(m)

O（nlogn）做法也差不多，把点正负分类之后，用lower_bound查询回到0后剩余步数可以覆盖多少点即可。

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 100005
  13. #define M 2000001
  14. int sum1[M+5],sum2[M+5];
  15. int main()
  16. {
  17. 	int n,i,m,x;
  18. 	n=gi();m=gi();
  19. 	for(i=1;i<=n;i++){
  20. 		x=gi();
  21. 		if(x>=0) sum1[x]++;
  22. 		else sum2[-x]++;
  23. 	}
  24. 	for(i=1;i<=M;i++)sum1[i]+=sum1[i-1];
  25. 	for(i=1;i<=M;i++)sum2[i]+=sum2[i-1];
  26. 	int ans=0;
  27. 	for(i=0;i<=M;i++){
  28. 		if(i*2>m) break;
  29. 		ans=max(ans,max(sum1[i]+sum2[m-i*2],sum2[i]+sum1[m-i*2]));
  30. 	}
  31. 	printf("%d",ans);
  32. }

F题

一个矩阵，每行有一个权值ri，每列有一个权值ci

一个点（x，y）能走到另一个点（z，y），当且仅当，rx<rz且不存在u使得rx<ru<rz

一个点（x，y）能走到另一个点（x，w），当且仅当，cy<cw且不存在v使得cy<cv<cw

现给出T个询问，每次询问从点(x,y)到点(z,w)的路径条数，答案mod 1e9 +7

n,m,T<=10^5，Ri<=10^8

题解

当时一看就不想做了，看了一下道题发现有50%的白送分，就稍微推了一下式子

首先，行列的顺序在这道题中不重要，所以直接进行一个离散化（排序+去重）

题目要求的答案就直接变成了一个网格图路径计数问题，显然组合数

然后预处理一下组合数，搞定了（虽然期间还把题目读错了一次，以为是从大到小走。。）

但是！！！还没完

这个题坑点就在于，有重复的ri和ci值，在路径中也会贡献方案数

而这一点在出题人精心构造的样例下被完美回避了，稍有不慎就是0分和满分的区别

我们按行来看一下，发现如果从（1，1）走到（4，4），实际上就是给答案乘上了当前2的这一行可以选择的方案数，同理列也一样。

但是如果我们从（1，1）走到（3，3），情况就不一样了，由于我们无法在相同ri和ci的地方进行跳跃，只能走严格大于的路，我们就需要提前决策好哪些点是不能走的。

所以此时的答案就不应该乘上当前阶段的行列重复数

最终答案就是

\binom{z-x}{z-x+y-w}( \prod_{i=x+1}^{z-1} Rcnt[i])( \prod_{i=y+1}^{w-1} Ccnt[i])

Rcnt[i]表示Ri值第i小的有多少行（也就是重复的ri的数量）

另外还有一些坑点，例如在ri相同时，还需要判断原始的行数是否相同，才能确定是否有答案。列同理。在ri和ci都相同时，就需要判断原始坐标是否一致。

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 100005
  13. #define M 300000
  14. const int mod = 1000000007;
  15. int a[N],b[N],ha[N],hb[N],acnt,bcnt;
  16. int fac[M+5],inv[M+5];
  17. int ksm(int x,int y)
  18. {
  19. 	int ans=1;
  20. 	while(y){
  21. 		if(y&1)ans=1ll*ans*x%mod;
  22. 		y>>=1;x=1ll*x*x%mod;
  23. 	}
  24. 	return ans;
  25. }
  26. void shai()
  27. {
  28. 	int i;
  29. 	fac[0]=inv[0]=1;
  30. 	for(i=1;i<=M;i++)
  31. 		fac[i]=1ll*fac[i-1]*i%mod;
  32. 	inv[M]=ksm(fac[M],mod-2);
  33. 	for(i=M-1;i>=1;i--)
  34. 		inv[i]=1ll*inv[i+1]*(i+1)%mod;
  35. }
  36. int C(int n,int m)
  37. {
  38. 	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
  39. }
  40. int cal(int x,int y,int z,int w)
  41. {
  42. 	return C(z-x+w-y,z-x);
  43. }
  44. int mula[N],mulb[N];
  45. int main()
  46. {
  47. 	int n,m,T,i,x,y,z,w;
  48. 	shai();
  49. 	n=gi();m=gi();T=gi();
  50. 	for(i=1;i<=n;i++)ha[i]=a[i]=gi();
  51. 	for(i=1;i<=m;i++)hb[i]=b[i]=gi();
  52. 	sort(ha+1,ha+n+1);
  53. 	sort(hb+1,hb+m+1);
  54. 	int acnt=unique(ha+1,ha+n+1)-ha-1;
  55. 	int bcnt=unique(hb+1,hb+m+1)-hb-1;
  56. 	for(i=1;i<=n;i++){
  57. 		int pos=lower_bound(ha+1,ha+acnt+1,a[i])-ha;
  58. 		mula[pos]++;
  59. 	}
  60. 	for(i=2;i<=acnt;i++)mula[i]=1ll*mula[i]*mula[i-1]%mod;
  61. 	for(i=1;i<=m;i++){
  62. 		int pos=lower_bound(hb+1,hb+bcnt+1,b[i])-hb;
  63. 		mulb[pos]++;
  64. 	}
  65. 	for(i=2;i<=bcnt;i++)mulb[i]=1ll*mulb[i]*mulb[i-1]%mod;
  66. 	while(T--){
  67. 		x=gi();y=gi();z=gi();w=gi();
  68. 		if(a[x]==a[z]&&b[y]==b[w]){
  69. 			if(x!=z||y!=w) printf("0\n");
  70. 			else printf("1\n");
  71. 		}
  72. 		else{
  73. 			if(a[x]==a[z]){
  74. 				if(x!=z) printf("0\n");
  75. 				else{
  76. 					y=lower_bound(hb+1,hb+bcnt+1,b[y])-hb;
  77. 					w=lower_bound(hb+1,hb+bcnt+1,b[w])-hb;
  78. 					if(y>w) printf("0\n");
  79. 					else printf("%d\n",1ll*mulb[w-1]*ksm(mulb[y],mod-2)%mod);
  80. 				}
  81. 			}
  82. 			else if(b[y]==b[w]){
  83. 				if(y!=w) printf("0\n");
  84. 				else{
  85. 					x=lower_bound(ha+1,ha+acnt+1,a[x])-ha;
  86. 					z=lower_bound(ha+1,ha+acnt+1,a[z])-ha;
  87. 					if(x>z) printf("0\n");
  88. 					else printf("%d\n",1ll*mula[z-1]*ksm(mula[x],mod-2)%mod);
  89. 				}
  90. 			}
  91. 			else{
  92. 				x=lower_bound(ha+1,ha+acnt+1,a[x])-ha;
  93. 				y=lower_bound(hb+1,hb+bcnt+1,b[y])-hb;
  94. 				z=lower_bound(ha+1,ha+acnt+1,a[z])-ha;
  95. 				w=lower_bound(hb+1,hb+bcnt+1,b[w])-hb;
  96. //				printf("%d %d %d %d\n",x,y,z,w);
  97. 				if(x>z||y>w) printf("0\n");
  98. 				else{
  99. 					int ans=cal(x,y,z,w);
  100. 					ans=1ll*ans*mula[z-1]%mod*ksm(mula[x],mod-2)%mod;
  101. 					ans=1ll*ans*mulb[w-1]%mod*ksm(mulb[y],mod-2)%mod;
  102. 					printf("%d\n",ans);
  103. 				}
  104. 			}
  105. 		}
  106. 	}
  107. }
  108. /*
  109. 4 4 2
  110. 4 2 3 1
  111. 2 1 2 1
  112. 4 4 1 1
  113. 2 2 2 4
  115. */

G题

给出一个n个点的树，每个点有权值ai，求树上不相邻两点的权值异或的最大值。

n<=10^5，ai<=2^31-1

题解

先写了个暴力，就去看最后一题了，最后才来想的正解

发现很简单

直接把所有点插入01Trie树里面

然后枚举1~n的所有点，在Trie树中删除其相邻点，利用贪心遍历01Trie树查询最大异或值

然后再恢复所有相邻点即可

每个点u会被删除d[u]次（u的度数），均摊下来就是边数次，O（n）级别

查询和插入修改都是O（logn）

总复杂度O(nlogn)

不过我比较fw，最后没有调出来，只交了一个暴力。

暴力代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 100005
  13. int a[N],fa[N];
  14. int main()
  15. {
  16. 	int n,i,j;
  17. 	n=gi();
  18. 	for(i=1;i<=n;i++)a[i]=gi();
  19. 	for(i=1;i<=n;i++)fa[i]=gi()+1;
  20. 	int ans=0;
  21. 	for(i=1;i<=n;i++)
  22. 		for(j=i+1;j<=n;j++)
  23. 			if(fa[i]!=j&&fa[j]!=i)
  24. 				ans=max(ans,a[i]^a[j]);
  25. 	printf("%d",ans);
  26. }

正解代码：（比赛结束后才调出来）

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 100005
  13. #define LOG 31
  14. int va[N],fa[N];
  15. int fir[N],to[2*N],nxt[2*N],cnt;
  16. void adde(int a,int b)
  17. {
  18. 	to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;
  19. 	to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;
  20. }
  21. struct node{
  22. 	int l,r,siz;
  23. }a[N*LOG];
  24. int T,tcnt;
  25. void insert(int &i,int x,int k,int dep)
  26. {
  27. 	if(!i){
  28. 		i=++tcnt;
  29. 		a[i].siz=0;
  30. 		a[i].l=a[i].r=0;
  31. 	}
  32. 	a[i].siz+=k;
  33. 	if(dep==0) return;
  34. 	if(x&(1<<dep)) insert(a[i].r,x,k,dep-1);
  35. 	else insert(a[i].l,x,k,dep-1);
  36. }
  37. int ans;
  38. void query(int i,int x,int val,int dep)
  39. {
  40. 	//printf("%d( ",val);
  41. 	if(a[i].siz==0) return;
  42. 	if(dep==0){
  43. 		//printf("x val:%d %d\n",x,val);
  44. 		ans=max(ans,x^val);
  45. 		return;
  46. 	}
  47. 	if(x&(1<<dep)){
  48. 		if(a[i].l&&a[a[i].l].siz)
  49. 			query(a[i].l,x,val,dep-1);
  50. 		else
  51. 			query(a[i].r,x,val^(1<<dep),dep-1);
  52. 	}
  53. 	else{
  54. 		if(a[i].r&&a[a[i].r].siz)
  55. 			query(a[i].r,x,val^(1<<dep),dep-1);
  56. 		else
  57. 			query(a[i].l,x,val,dep-1);
  58. 	}
  59. 	//printf(")");
  60. }
  61. int main()
  62. {
  63. 	int n,i,j;
  64. 	n=gi();
  65. 	for(i=1;i<=n;i++)va[i]=gi();
  66. 	for(i=1;i<=n;i++){
  67. 		fa[i]=gi()+1;
  68. 		if(fa[i])
  69. 			adde(i,fa[i]);
  70. 	}
  71. 	for(i=1;i<=n;i++)
  72. 		insert(T,va[i],1,30);
  73. 	ans=0;
  74. 	for(i=1;i<=n;i++){
  75. 		for(int v,p=fir[i];p;p=nxt[p])
  76. 			insert(T,va[to[p]],-1,30);
  77. 		query(T,va[i],0,30);
  78. 		for(int v,p=fir[i];p;p=nxt[p])
  79. 			insert(T,va[to[p]],1,30);
  80. 	}
  81. 	printf("%d",ans);
  82. }
  83. /*
  84. 5
  85. 7 4 2 5 4
  86. -1 0 0 2 2
  87. */

H题

给出一个n个点的树，根为root，每个点有权值ai。

求每个点u的子树中有多少个节点v，满足av<au且av不整除au

你只需要输出每个子树答案的和。

n<=10^5，ai为1~n的一个排列。

题解

当时一看，觉得这题是啥玩意啊

然后看了看性质，发现非常可做

首先，按照子树一个一个算肯定是不可能的，肯定需要一大堆高级数据结构

我们换个思路，既然它求整体的答案，我们可以把枚举子树改为枚举链

因为一个节点v给u做贡献，u必定会在v到root的路径上，而一个点v也只会对v到root路径上的点做贡献。

于是我们就从上到下dfs，维护一个树状数组，里面装当前点u到root的路径上点的权值，

这样就可以直接查询到这条路径上 有多少点权大于当前点权

那剩下一个不整除的条件应该怎么办

暴力扫描即可！！！

维护一个桶，来看路径上是否存在点权为x的点

然后对一个点a[u]，暴力枚举a[u]的所有倍数，有一个存在的点，就让答案减一掉即可。（倍数肯定比a[u]大，所以不会多减）

这样做的均摊时间复杂度O（n*ln(n)）

总的时间复杂度也是O（nlogn）（树状数组logn，暴力枚举均摊nlnn）

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. inline int gi()
  6. {
  7. 	char c;int num=0,flg=1;
  8. 	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
  9. 	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
  10. 	return num*flg;
  11. }
  12. #define N 100005
  13. int fir[N],to[2*N],nxt[2*N],cnt;
  14. void adde(int a,int b)
  15. {
  16. 	to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;
  17. 	to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;
  18. }
  19. int n;
  20. int a[N];
  21. int tong[N];
  22. int tra[N];
  23. int getsum(int x)
  24. {
  25. 	int ret=0;
  26. 	while(x){
  27. 		ret+=tra[x];
  28. 		x-=(x&-x);
  29. 	}
  30. 	return ret;
  31. }
  32. void update(int x,int k)
  33. {
  34. 	while(x<=n){
  35. 		tra[x]+=k;
  36. 		x+=(x&-x);
  37. 	}
  38. }
  39. long long ans;
  40. void dfs(int u,int f)
  41. {
  42. 	ans+=1ll*getsum(n-a[u]+1);
  43. 	for(int i=a[u];i<=n;i+=a[u])
  44. 		if(tong[i]) ans--;
  45. 	
  46. 	tong[a[u]]++;
  47. 	update(n-a[u]+1,1);
  48. 	for(int v,p=fir[u];p;p=nxt[p]){
  49. 		v=to[p];
  50. 		if(v!=f){
  51. 			dfs(v,u);
  52. 		}
  53. 	}
  54. 	update(n-a[u]+1,-1);
  55. 	tong[a[u]]--;
  56. }
  57. int main()
  58. {
  59. 	int rt,i,u,v;
  60. 	n=gi();rt=gi();
  61. 	for(i=1;i<=n;i++)
  62. 		a[i]=gi();
  63. 	for(i=1;i<n;i++){
  64. 		u=gi();v=gi();
  65. 		adde(u,v);
  66. 	}
  67. 	ans=0;
  68. 	dfs(rt,0);
  69. 	printf("%lld",ans);
  70. }

游记

Day0

忙碌的一天，上午早八上课，听不进去，开始看莫比乌斯反演，心想着，这次考研究生组是不是题会很难啊，估计有什么字符串网络流主席树平衡树CDQ分治之类的东西，反正全都看看。

课上就劈里啪啦的默写模板。

下午又是满课，看了点计数，晚上吃个饭，回来又是排练

回寝本来打算再复习一下，结果看了一晚上下象棋

好一个准备充足

Day1

早上8点醒，有点困。

然后开始比赛了。

先看了前两道填空，发现A题挺好做的，freopen一下，读个文件，小统计一下

然后B题打个表找了下规律，就过去30分钟了

10分钟写完C题结构体排序，开始看D题，开始后悔自己没有看SAM，毕竟n*m是10000，说大不大，说小不小，时限还给的一秒，九年编程，字符串题还是只会哈希。

大概过了20几分钟，发现直接二分求LCS就搞定了，呆

好久没写哈希了，又写了20几分钟，调完就10：27了

看E题，这个数轴游走取值勾起了我不好的回忆，想当年做了一道180多行的分类讨论贪心也是长这样。原题重测背了我好几个个小时才背下来。

结果发现只有一个拐点，是个简单贪心，10分钟过了，10：47。

看F题，开始还有点懵逼，然后发现就是一个离散化+网格路径计数，正兴高采烈地写完准备下一题的时候，发现有点不对劲，ri和ci会重复，瞬间就汗流浃背了（汗流浃背了吧~小老弟），但是又发现了一个很好的性质，可以直接把重复的贡献单独拿出来算，就结束了。一看时间11：20，人麻了。

看G题，先想到是01Trie树合并，感觉研究生组目前还没有题上强度，到G题应该开始加码了吧，然后一看，发现一共就只有8道题，瞬间就轻松了。但是我不想些01Trie树合并，50%的O(n^2)暴力它不香吗，那肯定香啊，十分钟暴力走人。

最后到了H题，看了5分钟，转换一下枚举方式之后，发现直接暴力可以均摊复杂度O（nln(n)），直接过了，有点难以置信，这居然能让我给做出来了？！但是时间已经不多了，还有个01Trie合并没写，就直接开写了，12：00过了样例，感觉没毛病。

回来写G题的01Trie树合并，各种细节处理、空间优化，写了半个小时，发现不对劲啊，有更简单的做法，直接一个01Trie树插入加删除不就搞定了，此时只剩下30分钟了，然后删了重新开写，写了15分钟就写完了，然后开始调，调到最后都没有调出来，有点难受。

有生之年能不能AK一次啊。

 

upd2024.5.6：省赛前几天出成绩了，终于拿了一次省一，还挺不错的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/551393
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号