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

Codeforces Round 911 (Div. 2)补题

作者：算法构造者 | 2024-02-02 11:48:10

赞

踩

Codeforces Round 911 (Div. 2)补题

Cover in Water

题目大意：我们有一排房间，一些房间是空的，一些房间是阻塞的，现在需要将所有的空房间都填满水，我们能做的只有两个操作：1.往一个空房间内放入水；2.将一个房间中的水取出放入另一个房间。另外当一个房间的左右两个房间都有水的时候，这个房间会自己产生水，我们需要尽可能地减少操作1的执行次数，问最少需要多少次操作1.

思路：由于左右两个房间有水，中间那个房间会自然产生水，所以可以发现如果有3个连在一起的房间，那么我们只需要放入两份水，中间空一个空房间，那么这个空房间产生水，我们把它移到别的空房间，那么它又会产生新的水，即只要有大于等于三个房间连在一起，那么就可以无限产生水，否则就要一个一个房间放入。那么我们需要统计的只有两个值，一个是空房间的总数，一个是是否有大于等于3个的空房间连在一起。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char s[200];
  4. int main()
  5. {
  6. 	int t;
  7. 	scanf("%d",&t);
  8. 	while(t--)
  9. 	{
  10. 		int n;
  11. 		scanf("%d%s",&n,s);
  12. 		char c=s[0];
  13. 		int cnt,sum;
  14. 		int mx=0;
  15. 		if(c=='#') cnt=sum=0;
  16. 		else cnt=sum=1;
  17. 		for(int i=1;i<n;i++)
  18. 		{
  19. 			if(s[i]=='.') 
  20. 			{	
  21. 				sum++;
  22. 				if(s[i]==c) cnt++,mx=max(cnt,mx);
  23. 				else cnt=1,mx=max(cnt,mx);
  24. 			}
  25. 			else cnt=0;
  26. 			c=s[i];
  27. 		}
  28. 		if(mx>=3) printf("2\n");
  29. 		else printf("%d\n",sum);
  30. 	}
  31. }

Laura and Operations

题目大意：黑板上有若干个数，只有1，2，3三种，我们每次可以选择两个不同的数并擦除，然后添加一个不同于两者的数，问最后能否使黑板上所有的数都相同，如果有可能，那么会是哪些数。输入给出三个数各自的数量，输出只用输出0，1（0表示这个数最终不可能出现，1表示这个数最终有可能出现）

思路：首先，如果有两个数的个数相等，那么第三个数一定可以得到，否则，我们来仔细考虑一下，不管怎么样就算两个不相等，也要想办法使它们相等，该怎么使它们相等呢，一个方法是用目标数字和多的那个来生成少的那个，最后使两者相等，多的减少的和少的增加的是一样多的，那么就证明它们的差值是偶数；另外如果目标的数量太少没办法使两者相等怎么办，我们可以先将两个都减少，用来生成目标，然后再用目标和多的去生成少的，使多的和少的数目相等，那么条件也是它们的差值是偶数。至此问题解决，核心就是要另外两个相等，或者能变成相等的。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5. 	int t;
  6. 	scanf("%d",&t);
  7. 	while(t--)
  8. 	{
  9. 		int a,b,c;
  10. 		scanf("%d%d%d",&a,&b,&c);
  11. 		if(b==c||(b+c)%2==0) printf("1 ");
  12. 		else printf("0 ");
  13. 		if(a==c||(a+c)%2==0) printf("1 ");
  14. 		else printf("0 ");
  15. 		if(b==a||(b+a)%2==0) printf("1 ");
  16. 		else printf("0 ");
  17. 		printf("\n");
  18. 	}
  19. }

Anji's Binary Tree

题目大意：有一颗n节点的二叉树，1是根节点，我们对于每个节点输出它的左子节点和右子节点（0表示该节点为空），同时每个节点有一个字母，U表示返回父节点，R表示移动到右子节点，L表示移动到左子节点，如果该操作不合法则停止不动。我们想到任意一个叶子节点（没有子节点的点）去，可以修改任意一个节点处的操作，问最少修改多少次可以保证我们最终可以到达叶子节点。

思路：本来想的是记录所有的叶子节点，以及每个点的父节点的下标及到这个子节点需要进行的操作，我们遍历所有的叶子节点，并往回找知道访问到1，当父节点处的实际操作和到叶子节点的操作不同时，操作数自增，对于每个叶子节点求出需要的操作数，从中取最小值，理论上每个样例的时间复杂度是nlogn，不应该超时，但是很不幸，还是超时了。而且没办法优化，所以只能换思路。我们刚刚的思路是从后往前找，既然不成立，那么只能考虑遍历二叉树，用动态规划的思想来更新到每个节点的操作数，最后从所有叶子节点的操作数中找出最小值。实际上我感觉相比前一种方法，我们还多遍历了一些点，因为前一种方法不在路径上的点不会被遍历到，这种方法所有的点都会被遍历（这里分析有问题，前面的点会被反复访问），但是很奇怪，这个方法确实没有超时，并且AC了。不对，时间复杂度不能这么分析。

我重新分析了下，过程如下：
 

  1. for(int i=0;i<e.size();i++)
  2. {	
  3. 	int x=e[i];
  4. 	int op=0;
  5. 	while(x!=1)
  6. 	{
  7. 		if(s[v[x].first]!=v[x].second)  op++;
  8. 		x=v[x].first;
  9. 	}
  10. 	mi=min(mi,op);
  11. 	if(!mi) break;
  12. }

这个是第一种方法的查找部分，我们假设一下一共有m层，每层都是满的，即n=2^m-1，那么就有2^(m-1)个叶子节点，每个叶子节点需要执行m次while(),那么时间复杂度就是m*2^(m-1),log(n+1)*(n+1)/2,即相当于nlogn,但是对于第二种方法，dfs只会把所有节点遍历一遍，时间复杂度是n,所以实际上还是快一点，所以应该是这个logn被卡了。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char s[300010];
  4. int l[300010],r[300010];
  5. int dp[300010];
  6. void dfs(int x)
  7. {
  8. 	if((!l[x]&&!r[x])||!x) return; 
  9. 	dp[l[x]]=dp[r[x]]=dp[x];
  10. 	if(s[x]=='L') dp[r[x]]++;
  11. 	else if(s[x]=='R') dp[l[x]]++;
  12. 	else dp[l[x]]++,dp[r[x]]++;
  13. 	dfs(l[x]);
  14. 	dfs(r[x]);
  15. }
  16. int main()
  17. {
  18. 	int t;
  19. 	scanf("%d",&t);
  20. 	while(t--)
  21. 	{
  22. 		int n;
  23. 		scanf("%d",&n);
  24. 		scanf("%s",s+1);
  25. 		vector<pair<int,char>>v(n+10);
  26. 		vector<int>e;
  27. 		for(int i=1;i<=n;i++) l[i]=r[i]=dp[i]=0;
  28. 		for(int i=1;i<=n;i++)
  29. 		{
  30. 			int a,b;
  31. 			scanf("%d%d",&a,&b);
  32. 			l[i]=a,r[i]=b;
  33. 			if(!a&&!b) e.push_back(i);
  34. 		}
  35. 		dfs(1);
  36. 		int mi=n+10;
  37. 		for(int i=0;i<e.size();i++)
  38. 		{	
  39. 			int x=e[i];
  40. 			mi = min(mi,dp[x]);
  41. 		}
  42. 		printf("%d\n",mi);
  43. 	}
  44. }

ps:对于二叉树，遍历比访问路径的效率更高，修改可以用dp来累计和转移。

Small GCD

题目大意：有一个数组a[],我们定义运算f(x,y,z):将x,y,z排序使x<=y<=z,f(x,,y,z)=gcd(x,y),求\sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n}f(ai,aj,ak)

思路：我们可以发现一些数比如最小的两个，在它们同时与其他数组合的时候，f()的值始终是它们俩的最大公因数，所以我们想到排序，将循环从三维降成二维，那么总的时间复杂度就是t*n*n，看上去能卡着过去，但实际上gcd的时间复杂度也要考虑，gcd(x,y)的时间复杂度即O(log(min(x,y))),所以我们即使优化了，还是照样超时（如果n的范围是<=3e3就可以实现）。所以，我们就要想新的方法来优化。 

这题需要用到数论里的欧拉反演。本题欧拉反演部分的证明

核心的转化如下：
 

我感觉代码更直观，我就将链接中的公式推演全部转化成代码了，就从上一个思路的末尾开始讨论详细转化如下：

  1. for(int j=1;j<=n;j++)
  2. {
  3. 	for(int i=1;j<=j-1;j++)
  4. 	{
  5. 		ans += gcd(a[i],a[j])*(n-j);
  6. 	}
  7. }
  8.  
  9. //欧拉公式
  10. int sum=0;
  11. for(int i=1;i<=n;i++)
  12. {
  13. 	if(n%d==0) sum += phi(d);
  14. }
  15. =>sum==n;
  16.  
  17. |
  18. V
  19.  
  20. for(int j=1;j<=n;j++)
  21. {
  22. 	for(int i=1;j<=j-1;j++)
  23. 	{
  24. 		for(int d=1;d<=m;d++)
  25. 			if(gcd(a[i],a[j])%d==0) ans += phi(d)*(n-j);
  26. 	}
  27. }
  28.  
  29. for(int j=1;j<=n;j++)
  30. {
  31. 	for(int d=1;d<=m;d++)
  32. 	{	
  33. 		for(int i=1;j<=j-1;j++)
  34. 		{
  35. 			if(gcd(a[i],a[j])%d==0) ans += phi(d)*(n-j);
  36. 		}
  37. 	}
  38. }
  39.  
  40. for(int j=1;j<=n;j++)
  41. {
  42. 	for(int d=1;d<=m;d++)
  43. 	{	
  44. 		for(int i=1;j<=j-1;j++)
  45. 		//if(gcd(a[i],a[j])%d==0)这个条件成立的话，phi(d)*(n-j)会被加入ans一次，[]这个有0和1两种值，刚好用来替换if
  46. 		{
  47. 			 ans += [d|gcd(a[i],a[j])]*phi(d)*(n-j);
  48. 	    }
  49. 	}
  50. }
  51.  
  52. for(int j=1;j<=n;j++)
  53. {
  54. 	for(int d=1;d<=m;d++)
  55. 	{
  56. 		for(int i=1;j<=j-1;j++)
  57. 		{
  58. 			//d可以被两者的最大公因数整除，自然也可以被两者分别整除
  59. 			 ans += [d|a[i]]*[d|a[j]]*phi(d)*(n-j);
  60. 		}
  61. 	}
  62. }
  63.  
  64. for(int j=1;j<=n;j++)
  65. {	
  66. 	for(int d=1;d<=m;d++)
  67. 	{	
  68. 		if(a[j]%d==0)//将[d|a[j]]替换成if判断
  69. 		{
  70. 			for(int i=1;j<=j-1;j++)
  71. 			{
  72. 				ans += [d|a[i]]*phi(d)*(n-j);
  73. 			}
  74. 		}
  75. 	}
  76. }
  77.  
  78.  
  79. //令sum([d|ai])(1<=i<=j-1)=g(d)
  80.  
  81. for(int j=1;j<=n;j++)
  82. {	
  83. 	for(int d=1;d<=m;d++)
  84. 	{	
  85. 		if(a[j]%d==0) 
  86. 			ans += g(d)*phi(d)*(n-j); //g(d)相当于1-(j-1)中d的倍数的个数
  87. 	}
  88. }
  89.  
  90. //d是a[j]的因数，我们可以先将它预处理出来，得到v[a[j]]数组，那么就不用循环所有的数，只用循环v[a[i]]数组即可
  91. for(int j=1;j<=n;j++)
  92. {
  93. 	for(auto d:v[a[j]])
  94. 	{
  95. 		ans += g(d)*phi(d)*(n-j);
  96. 	}
  97. }
  98.  
  99.  
  100. //另外由于g(d)表示的是数组中的数在1~(j-1)范围内d的倍数的个数，那么我们直接在从小到大遍历的过程中统计一下即可
  101. for(int j=1;j<=n;j++)
  102. {
  103. 	for(auto d:v[a[j]])
  104. 	{
  105. 		ans += g(d)*phi(d)*(n-j);
  106. 		//a[j]是d的倍数，那么g[d]++；
  107. 		g[d]++;
  108. 	}
  109. }

现在需要计算phi(d),计算参考了线性筛计算欧拉函数，核心代码如下：

  1. 	phi[1]=1;
  2. 	for(int i=2;i<=N;i++) 
  3. 	{
  4. 		if(!st[i]) phi[i]=i-1,prime.push_back(i);
  5. 		for(auto j:prime)
  6. 		{
  7. 			if(i*j>N) break;
  8. 			st[i*j]=1;
  9. 			if(i%j)
  10. 			{
  11. 				phi[i*j]=phi[i]*(j-1);
  12. 			}
  13. 			else 
  14. 			{
  15. 				phi[i*j]=phi[i]*j;
  16. 				break;
  17. 			}
  18. 		}
  19. 	}

另外g(d)的计算也涉及到一些技巧，g(d)的含义是a[1]-a[j-1]之间d的倍数有多少个，挨个统计太麻烦，我们前面已经预处理了每个a[i]的因子，那么我们访问一个a[i]的时候，它所有因子的倍数多出现了一个，那么我们就将它所有因子d的g[d]++，那么g[d]同样能表示d的倍数的出现次数。至此所有细节都讨论清楚了。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=100010;
  4. int phi[N+10],g[N+10],a[N+10];
  5. vector<int>prime,v[N+10];
  6. int st[N+10];
  7. int main()
  8. {
  9. 	phi[1]=1;
  10. 	for(int i=2;i<=N;i++) 
  11. 	{
  12. 		if(!st[i]) phi[i]=i-1,prime.push_back(i);
  13. 		for(auto j:prime)
  14. 		{
  15. 			if(i*j>N) break;
  16. 			st[i*j]=1;
  17. 			if(i%j)
  18. 			{
  19. 				phi[i*j]=phi[i]*(j-1);
  20. 			}
  21. 			else 
  22. 			{
  23. 				phi[i*j]=phi[i]*j;
  24. 				break;
  25. 			}
  26. 		}
  27. 	}
  28. 	for(int i=1;i<=N;i++)
  29. 	{
  30. 		for(int j=i;j<=N;j+=i)
  31. 		{
  32. 			v[j].push_back(i);
  33. 		}
  34. 	}
  35. 	int t;
  36. 	scanf("%d",&t);
  37. 	while(t--)
  38. 	{
  39. 		int n;
  40. 		scanf("%d",&n);
  41. 		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  42. 		sort(a+1,a+1+n);
  43. 		memset(g,0,sizeof g);
  44. 		long long ans=0;
  45. 		for(int j=1;j<=n;j++)
  46. 		{
  47. 			for(auto d:v[a[j]])
  48. 				ans += 1ll*g[d]*phi[d]*(n-j),g[d]++;;
  49. 		}
  50. 		printf("%lld\n",ans);
  51. 	}
  52. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55186
推荐阅读
相关标签

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

  

闽ICP备14008679号