• “蔚来杯“2022牛客暑期多校训练营6

    J. Number Game

    给出A，B，C三个数，每次操作可以把B变为A-B，也可以将C变成B-C，给出x，问经过若干次操作之后能否使得C等于x。

    思路：首先有一个性质可以知道，这个x一定是两种操作交替进行得来的因为如果一个操作连续做两次，相当于没有操作。这样我们可以倒着推：

    在这里我们规定B'=A-B：

    C_{n}=B-C_{n-1}=x

    C_{n-1}=B-C_{n}=B-x

    C_{n-2}=B^{'}-C_{n-1}=B^{'}-B+x

    C_{n-3}=2\times B-B^{'}-x

    根据这些推导，可以知道此时满足条件：(C+x-B)%(B-B')==0，而因为第一步是先改变B的值还是先改变C的值不确定，所以另一种的满足条件即为：(C+x-B')%(B-B')==0。注意特判：当C==x时，不需要进行任何操作；如果A=2*B，即改变B的操作没有任何作用，此时只有B-C==x时才会满足条件。

    AC Code：

    1. #include 
    2.  
    3. int t,A,B,C,x;
    4.  
    5. int main(){
    6. 	std::ios::sync_with_stdio(false);
    7. 	std::cin.tie(0);
    8. 	std::cout.tie(0);
    9. 	std::cin>>t;
    10. 	while(t--){
    11. 		std::cin>>A>>B>>C>>x;
    12. 		int BB=A-B;
    13. 		if(C==x){
    14. 			std::cout<<"Yes"<<'\n';
    15. 			continue;
    16. 		}
    17. 		if(2*B==A&&B-C==x){
    18. 			std::cout<<"Yes"<<'\n';
    19. 			continue;
    20. 		}
    21. 		if(2*B==A){
    22. 			std::cout<<"No"<<'\n';
    23. 			continue;
    24. 		}
    25. 		if((C-x)%(BB-B)==0){
    26. 			std::cout<<"Yes"<<'\n';
    27. 			continue;
    28. 		}
    29. 		if((C+x-B)%(B-BB)==0||(C+x-BB)%(B-BB)==0){
    30. 			std::cout<<"Yes"<<'\n';
    31. 			continue;
    32. 		}
    33. 		std::cout<<"No"<<'\n';
    34. 	}
    35. 	return 0;
    36. }

    os：签到好难。。

    G. Icon Design

    给出数字n，输出等比例的图像。

    思路：（1）模拟，队友搞的，很强；（2）数据范围小于等于5，直接打表也很不错。

    AC Code：

    1. #include
    2.  
    3. int n;
    4.  
    5. void N(int n,int h){
    6. 	if(h==1||h==2*n+3){
    7. 		for(int i=1;i<=2*n+3;i++){
    8. 			if(i==1||i==2*n+3) std::cout<<"@";
    9. 			else std::cout<<".";
    10. 		}
    11. 	}
    12. 	else{
    13. 		for(int i=1;i<=2*n+3;i++){
    14. 			if(i==1||i==2*n+3||i==h) std::cout<<"@";
    15. 			else std::cout<<".";
    16. 		}
    17. 	}
    18. }
    19. void F(int n,int h){
    20. 	if(h==1||h==n+2){
    21. 		for(int i=1;i<=2*n+3;i++)
    22. 			std::cout<<"@";
    23. 	}
    24. 	else{
    25. 		std::cout<<"@";
    26. 		for(int i=1;i<=2*n+2;i++)
    27. 			std::cout<<".";
    28. 	}
    29. }
    30. void L(int n,int h){
    31. 	if(h==2*n+3){
    32. 		for(int i=1;i<=2*n+3;i++)
    33. 			std::cout<<"@";
    34. 	}
    35. 	else{
    36. 		std::cout<<"@";
    37. 		for(int i=1;i<=2*n+2;i++)
    38. 			std::cout<<".";
    39. 	}
    40. }
    41.  
    42. void S(int n,int h){
    43. 	if(h==1||h==2*n+3||h==n+2){
    44. 		for(int i=1;i<=2*n+3;i++)
    45. 			std::cout<<"@";
    46. 	}
    47. 	if(h>1&&h2){
    48. 		std::cout<<"@";
    49. 		for(int i=1;i<=2*n+2;i++)
    50. 			std::cout<<".";
    51. 	}
    52. 	if(h>n+2&&h<2*n+3){
    53. 		for(int i=1;i<=2*n+2;i++)
    54. 			std::cout<<".";
    55. 		std::cout<<"@";
    56. 	}
    57. }
    58.  
    59. int main(){
    60. 	std::ios::sync_with_stdio(false);
    61. 	std::cin.tie(0);
    62. 	std::cout.tie(0);
    63. 	std::cin>>n;
    64. 	for(int i=1;i<=13*n+19;i++)
    65. 		std::cout<<"*";
    66. 	std::cout<<'\n';
    67. 	for(int i=1;i<=n;i++)
    68. 		for(int j=1;j<=13*n+19;j++){
    69. 			if(j==1) std::cout<<"*";
    70. 			else if(j==13*n+19) std::cout<<"*"<<'\n';
    71. 			else std::cout<<".";
    72. 		}
    73. 	for(int i=1;i<=2*n+3;i++)
    74. 	{
    75. 		for(int j=1;j<=13*n+19;j++)
    76. 		{
    77. 			if(j==1) std::cout<<"*";
    78. 			else if(j==13*n+19) std::cout<<"*"<<'\n';
    79. 			else if(j==n+3)
    80. 			{
    81. 				N(n,i);
    82. 				for(int k=1;k<=n+1;k++)
    83. 					std::cout<<".";
    84. 				F(n,i);
    85. 				for(int k=1;k<=n+1;k++)
    86. 					std::cout<<".";
    87. 				L(n,i);
    88. 				for(int k=1;k<=n+1;k++)
    89. 					std::cout<<".";
    90. 				S(n,i);
    91. 				for(int k=1;k<=n+1;k++)
    92. 					std::cout<<".";
    93. 				j=13*n+18;
    94. 			}
    95. 			else std::cout<<".";
    96. 		}
    97. 	}
    98. 	for(int i=1;i<=n;i++)
    99. 		for(int j=1;j<=13*n+19;j++){
    100. 			if(j==1) std::cout<<"*";
    101. 			else if(j==13*n+19) std::cout<<"*"<<'\n';
    102. 			else std::cout<<".";
    103. 		}
    104. 	for(int i=1;i<=13*n+19;i++)
    105. 		std::cout<<"*";
    106. 	std::cout<<'\n';
    107. 	return 0;
    108. }

     B. Eezie and Pie

     给定一棵树，每个点给出一个权值d[i]，表示该位置向1走的这条路径中最多走d[i]步，问每个点可以由几个点到达。

    思路：每个点可以向上走d[i]步，说明这一段每个点的结果都要+1，很显然是个差分问题，将O(n)转化为O(1)修改，然后最后一步DFS统计答案即可，基本是个树上点差分的板子题。

    AC Code：

    1. #include 
    2.  
    3. #define int long long
    4. typedef long long ll;
    5. const int N=2e6+5;
    6. int n,cnt;
    7. int head[N],e[N<<1],next[N<<1],id[N],out[N];
    8. int deep[N],size[N],top[N],fa[N],son[N];
    9. int d[N],fat[N][30],f[N],w[N];
    10.  
    11. void add_edge(int u,int v){
    12. 	e[cnt]=v;
    13. 	next[cnt]=head[u];
    14. 	head[u]=cnt++;
    15. }
    16.  
    17. void DFS1(int u,int father){
    18. 	deep[u]=deep[father]+1;
    19. 	size[u]=1;
    20. 	fa[u]=father;
    21. 	for(int k=1;k<=25;k++){
    22. 		fat[u][k]=fat[fat[u][k-1]][k-1];
    23. 	}
    24. 	for(int i=head[u];~i;i=next[i]){
    25. 		int j=e[i];
    26. 		if(j==father) continue;
    27. 		fat[j][0]=u;
    28. 		DFS1(j,u);
    29. 		size[u]+=size[j];
    30. 		if(size[son[u]]
    31. 	}
    32. }
    33.  
    34. void DFS2(int u,int father){
    35. 	f[u]=w[u];
    36. 	for(int i=head[u];~i;i=next[i]){
    37. 		int j=e[i];
    38. 		if(j==father) continue;
    39. 		DFS2(j,u);
    40. 		f[u]+=f[j];
    41. 	}
    42. }
    43.  
    44. int LCA(int u,int depth){
    45. 	for(int k=25;k>=0;k--){
    46. 		if(deep[fat[u][k]]>=depth)
    47. 			u=fat[u][k];
    48. 	}
    49. 	return u;
    50. }
    51.  
    52. signed main(){
    53. 	std::ios::sync_with_stdio(false);
    54. 	std::cin.tie(0);
    55. 	std::cout.tie(0);
    56. 	std::cin>>n;
    57. 	memset(head,-1,sizeof(head));
    58. 	for(int i=1;i<=n-1;i++){
    59. 		int u,v;
    60. 		std::cin>>u>>v;
    61. 		add_edge(u,v);
    62. 		add_edge(v,u);
    63. 	}
    64. 	DFS1(1,0);
    65. 	std::vector<int>d(n+5,0);
    66. 	for(int i=1;i<=n;i++){
    67. 		std::cin>>d[i];
    68. 	}
    69. 	for(int i=1;i<=n;i++){
    70. 		int tar=deep[i]-d[i];
    71. 		tar=std::max((int)1,tar);
    72. 		int t=LCA(i,tar);
    73. 		w[fa[t]]--;
    74. 		w[i]++;
    75. 	}
    76. 	DFS2(1,0);
    77. 	for(int i=1;i<=n;i++){
    78. 		std::cout<" \n"[i==n];
    79. 	}
    80. 	return 0;
    81. }

    os：一开始队友写的暴力，很容易就T了一发，，不打这种比较正式难度的比赛不知道，一打发现原来签到的知识点都没学全呜呜呜

    Z-Game on Grid

    给出一个n*m的棋盘，由'.','a','b'组成，走到a算Alice赢，走到b算Bob赢，走到(n,m)平局，每次每个人可以向右或者向下走一格，Alice先手，问是否有先手必胜，平局或者必输的策略。

    思路：考虑DP。我也不知道为什么，感觉很怪。标解给的是记忆化搜索的做法。即倒着进行DP转移，我们在计算先手必胜时，设定A处值为1，B处为0，(n,m)处为0，根据到某一步是先手还是后手分类讨论，当到达(i,j)点且为先手操作时，只要(i+1,j)或者(i,.j+1)任意一个是先手必胜态则一定会胜；若当前为后手操作时，仅当(i,j+1)和(i+1,j)两点都为先手必胜态才会胜，即表示为符号：

    其他两种情况类似考虑，只是设置不同的初始值即可。

    题解写的很妙，它把状态表示成二进制，即题解中1,2,4分别表示001,010,100三种状态，这样类似状态压缩的方法可以学习。 

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. const int N=505;
    5. int t,n,m;
    6. char f[N][N][2];
    7. std::string s[N];
    8.  
    9. int DFS(int x,int y,int u){
    10. 	if(s[x][y]=='A') return 1;
    11. 	if(s[x][y]=='B') return 4;
    12. 	if(x==n-1&&y==m-1) return f[x][y][u]=2;
    13. 	char &q=f[x][y][u];
    14. 	if(q==-1){
    15. 		if(u==0){
    16. 			q=0;
    17. 			if(x+1DFS(x+1,y,u^1);
    18. 			if(y+1DFS(x,y+1,u^1);
    19. 		}
    20. 		else{
    21. 			q=7;
    22. 			if(x+1DFS(x+1,y,u^1);
    23. 			if(y+1DFS(x,y+1,u^1);
    24. 		}
    25. 	}
    26. 	return q;
    27. }
    28.  
    29. int main(){
    30. 	std::ios::sync_with_stdio(false);
    31. 	std::cin.tie(0);
    32. 	std::cout.tie(0);
    33. 	std::cin>>t;
    34. 	while(t--){
    35. 		std::cin>>n>>m;
    36. 		for(int i=0;i
    37. 			std::cin>>s[i];
    38. 		}
    39. 		memset(f,-1,sizeof(f));
    40. 		int ans=DFS(0,0,0);
    41. 		std::cout<<(ans&1?"yes":"no")<<' '<<(ans&2?"yes":"no")<<' '<<(ans&4?"yes":"no")<<'\n';
    42. 	}
    43. 	return 0;
    44. }

    补不动了，就这样吧

  • 相关阅读:
    C++程序入门（helloworld.cpp编写）
    layUI带搜索的选择框样式和官网显示不一致
    重新定义商业——以用户为中心的全新商业模式
    Android13适配-Google官方照片视频选择器
    1186: 奖学金（结构体专题)
    【Matlab】一、解常微分方程ODE
    【学习笔记38】JavaScript中的本地存储
    SpringBoot自动装配
    企业精准拓客必不可少的利器丨快鲸scrm系统
    面试阿里，倒在了第4轮后，才幡然醒悟——论系统学习的重要性
  • 原文地址：https://blog.csdn.net/m0_62289613/article/details/126656074