• 2022ICPC济南站

    K

    Stack Sort

    题意：给你一个长度为n的排列，设有m个栈，你需要将这n个数按出现顺序入栈，每次入栈操作从m个栈中选择一个栈从栈顶入栈。当所有元素入栈完成后，需要不断选择栈，将栈中元素弹空。需满足出栈顺序为1 2 3 ... n，问完成上述任务所需最少栈的个数为多少。

    思路：遍历数组，设当前元素为x，我们就看是否存在栈顶为x+1的栈，若存在则入该栈；否则新开一个栈将x入栈。

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N=1e6+10;
    6. const int inf=0x3f3f3f3f;
    7.  
    8. using namespace std;
    9. /*
    10. 1 4 2 5 3
    11. 1 34 2 5 
    12. 找x+1存在否 存在
    13. 			不存在 ++
    14. */
    15. int n;
    16. bool st[N];
    17. void solve()
    18. {
    19. 	cin>>n;
    20. 	for(int i=1;i<=n+1;i++) st[i]=0;
    21. 	int ans=0;
    22. 	for(int i=1;i<=n;i++)
    23. 	{
    24. 		int x;
    25. 		cin>>x;
    26. 		if(st[x+1])
    27. 		{
    28. 			st[x+1]=0;
    29. 			st[x]=1;
    30. 		}
    31. 		else
    32. 		{
    33. 			st[x]=1;
    34. 			ans++;
    35. 		}
    36. 	}
    37. 	cout<'\n';
    38. }
    39. signed main()
    40. {
    41. 	//freopen("input.txt","r",stdin);
    42. 	//freopen("output.txt","w",stdout);
    43. 	ios;
    44. 	int _t=1;
    45. 	cin>>_t;
    46. 	while(_t--) solve();
    47. 	system("pause");
    48. 	return 0;
    49. }

    M

    Best Carry Player

    题意：给定n个元素的数组a[]，起始sum=0，不断执行sum+=a[i]，问加法过程中的总进位次数为多少？

    思路：模拟

    1. #include 
    2. #define ios ios::sync_with_stdio(0), cin.tie(0)
    3. #define PII pair
    4. typedef long long ll;
    5. const int N = 1e5 + 10;
    6. const int inf = 0x3f3f3f3f;
    7.  
    8. using namespace std;
    9. int n;
    10. string a[N];
    11. void solve()
    12. {
    13. 	cin >> n;
    14. 	for (int i = 1; i <= n; i++)
    15. 	{
    16. 		string x;
    17. 		cin >> x;
    18. 		reverse(x.begin(), x.end());
    19. 		a[i] = x;
    20. 	}
    21. 	string ret = "000000000000000";
    22. 	int ans = 0;
    23. 	int del = 0;
    24. 	for (int i = 1; i <= n; i++)
    25. 	{
    26. 		for (int j = 0; j < 15; j++)
    27. 		{
    28. 			int c1 = int(ret[j] - '0');
    29. 			int c2 = 0;
    30. 			if(jsize()) c2=int(a[i][j] - '0');
    31. 			int t = c1 + c2 + del;
    32. 			ret[j] = char(t % 10 + '0');
    33. 			if (t >= 10)
    34. 			{
    35. 				ans++;
    36. 				del = 1;
    37. 			}
    38. 			else
    39. 				del = 0;
    40. 		}
    41. 	}
    42. 	cout << ans << '\n';
    43. }
    44. signed main()
    45. {
    46. 	// freopen("input.txt","r",stdin);
    47. 	// freopen("output.txt","w",stdout);
    48. 	ios;
    49. 	int _t = 1;
    50. 	cin >> _t;
    51. 	while (_t--)
    52. 		solve();
    53. 	system("pause");
    54. 	return 0;
    55. }

    E

    Identical Parity

    题意：一个序列的值定义为所有数字的和，给定n，k问是否存在长度为n的排列满足所有长度为k的子段的值奇偶性都相同。

    思路：当k=1时，若n=1 Yes；k=1, n不为1 No

    当k为偶数时，我们可以奇偶交替的放，Yes

    当k为奇数时，我们可以分成k组，每组的下标满足a, a+k, a+2k...a属于[1,k]，同一组我们放相同奇偶的数。我们发现这样的序列就满足条件。

    设n/k=b余c，我们将k/2个组，这些组的位置放偶数；其余k/2+1个组，这些组的位置上放奇数。那么还剩下c个数没放，判断剩下的数是否满足奇偶个数。

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. #define int long long
    5. typedef long long ll;
    6. const int N=1e6+10;
    7. const int inf=0x3f3f3f3f;
    8.  
    9. using namespace std;
    10. int n,k;
    11. void solve()
    12. {
    13. 	cin>>n>>k;
    14. 	if(k==1)
    15. 	{
    16. 		if(n==1) cout<<"Yes\n";
    17. 		else cout<<"No\n";
    18. 	}
    19. 	else if(k%2==0) cout<<"Yes\n";
    20. 	else
    21. 	{
    22. 		int tot_o=n/2,tot_j=(n+1)/2;//总的奇偶个数
    23. 		int k_o=k/2,k_j=k/2+1;//k组中有多少组奇数偶数
    24. 		int b=n/k,c=n%k;
    25. 		int r_o=tot_o-b*k_o,r_j=tot_j-b*k_j;//放完k组，还剩多少奇偶数没放
    26. 		if(r_o>=0&&r_j>=0&&r_o+r_j==c)
    27. 		{
    28. 			if(r_o<=k_o&&r_j<=k_j) cout<<"Yes\n";
    29. 			else cout<<"No\n";
    30. 		}
    31. 		else cout<<"No\n";
    32. 	}
    33. }
    34. signed main()
    35. {
    36. 	//freopen("input.txt","r",stdin);
    37. 	//freopen("output.txt","w",stdout);
    38. 	ios;
    39. 	int _t=1;
    40. 	cin>>_t;
    41. 	while(_t--) solve();
    42. 	system("pause");
    43. 	return 0;
    44. }

    A

    Tower

    题意：有n座不同高度的塔，第i座塔的高度为a[i]

    你可以将其中的m座塔移除，然后进行下面的操作：

    1.选择一座塔，将其高度 a[i]增加 1

    2.选择一座塔，将其高度 a[i]减少 1

    3.选择一座塔，将其高度 a[i]/=2，向下取整

    不允许操作后塔的高度为0。问将剩余n-m座塔的高度搞成相同所需最少的操作次数。

    思路：最后变成的相同高度一定是某个塔的高度不断/2的结果。所以我们可以通过枚举最后高度，来计算塔到这个高度的最小操作次数。

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. #define int long long
    5. typedef long long ll;
    6. const int N=1e6+10;
    7. const int inf=0x3f3f3f3f;
    8.  
    9. using namespace std;
    10. int n,m;
    11. int a[N];
    12. int get(int now,int x)
    13. {
    14. 	int ret=0;
    15. 	if(now
    16. 	else if(now==x) ret=0;
    17. 	else
    18. 	{
    19. 		while(now>x)
    20. 		{
    21. 			if(now>x&&now/2<=x)
    22. 			{
    23. 				ret+=min(now-x,1+x-now/2);
    24. 				break;
    25. 			}
    26. 			now/=2;
    27. 			ret++;
    28. 		}
    29. 	}
    30. 	return ret;
    31. }
    32. void solve()
    33. {
    34. 	cin>>n>>m;
    35. 	for(int i=1;i<=n;i++)
    36. 		cin>>a[i];
    37. 	set<int>s;
    38. 	for(int i=1;i<=n;i++)
    39. 	{
    40. 		int x=a[i];
    41. 		s.insert(x);
    42. 		while(x>=2)
    43. 		{
    44. 			x/=2;
    45. 			s.insert(x);
    46. 		}
    47. 	}
    48. 	int ans=1e18;
    49. 	for(auto x:s)
    50. 	{
    51. 		vector<int>v;
    52. 		for(int i=1;i<=n;i++)
    53. 		{
    54. 			int t=get(a[i],x);
    55. 			v.push_back(t);
    56. 		}
    57. 		sort(v.begin(),v.end());
    58. 		int tem=0;
    59. 		for(int i=0;i
    60. 			tem+=v[i];
    61. 		ans=min(ans,tem);
    62. 	}
    63. 	cout<'\n';
    64. }
    65. signed main()
    66. {
    67. 	//freopen("input.txt","r",stdin);
    68. 	//freopen("output.txt","w",stdout);
    69. 	ios;
    70. 	int _t=1;
    71. 	cin>>_t;
    72. 	while(_t--) solve();
    73. 	system("pause");
    74. 	return 0;
    75. }

    D

    Frozen Scoreboard

    题意：给你封榜前的情况和最终通过的题数和罚时，问最终的榜单

    思路：将封榜前的过题数和罚时减去，再对封榜后的题进行二进制枚举，判断合法

    1. #include 
    2. #define ios ios::sync_with_stdio(0),cin.tie(0)
    3. #define PII pair
    4. #define int long long
    5. typedef long long ll;
    6. const int N=1e6+10;
    7. const int inf=0x3f3f3f3f;
    8.  
    9. using namespace std;
    10. int n,m;
    11. int a[N],b[N];
    12. struct node{
    13. 	char op;
    14. 	int x,y;
    15. 	int num;
    16. }P[N];
    17. void solve()
    18. {
    19. 	cin>>n>>m;
    20. 	for(int i=1;i<=n;i++)
    21. 	{
    22. 		cin>>a[i]>>b[i];
    23. 		int nowt=0,nowcnt=0;
    24. 		vectoruk;
    25. 		for(int i=0;i
    26. 		{
    27. 			char op;
    28. 			cin>>op;
    29. 			if(op=='+')
    30. 			{
    31. 				int u,v;char _;
    32. 				cin>>u>>_>>v;
    33. 				nowcnt++;
    34. 				nowt+=(u-1)*20+v;
    35. 				P[i]={'+',u,v};
    36. 			}
    37. 			else if(op=='-') 
    38. 			{
    39. 				int u;
    40. 				cin>>u;
    41. 				P[i]={'-',u};
    42. 			}
    43. 			else if(op=='?')
    44. 			{
    45. 				int u,v;
    46. 				cin>>u>>v;
    47. 				P[i]={'?',u,v,i};
    48. 				uk.push_back({'?',u,v,i});
    49. 			}
    50. 			else P[i]={'.'};
    51. 		}
    52. 		if(nowcnt==a[i]&&nowt==b[i])
    53. 		{
    54. 			cout<<"Yes\n";
    55. 			for(int j=0;j
    56. 			{
    57. 				if(P[j].op=='+') printf("+ %d/%d\n",P[j].x,P[j].y);
    58. 				else if(P[j].op=='-') printf("- %d\n",P[j].x);
    59. 				else if(P[j].op=='?') printf("- %d\n",P[j].y);
    60. 				else printf(".\n");
    61. 			}
    62. 		}
    63. 		else if(nowcnt
    64. 		{
    65. 			int cnt=a[i]-nowcnt;
    66. 			int t=b[i]-nowt;
    67. 			bool f=0;
    68. 			for(int j=0;j<(1<size());j++)
    69. 			{
    70. 				int mi=0,ma=0;
    71. 				for(int k=0;ksize();k++)
    72. 				{
    73. 					if((j>>k)&1)
    74. 					{
    75. 						mi+=240+(uk[k].y-uk[k].x)*20;
    76. 						ma+=299+(uk[k].y-1)*20;
    77. 					}
    78. 				}
    79. 				if(t>=mi&&t<=ma)
    80. 				{
    81. 					map<int,node>ans;
    82. 					int remt=t-mi;
    83. 					int finish=0;
    84.  
    85. 					for(int k=0;ksize();k++)
    86. 					{
    87. 						if((j>>k)&1)
    88. 						{
    89. 							int num=uk[k].num;
    90. 							int cishu=min(remt/20,uk[k].x-1);//封榜后wa了多少次
    91. 							ans[num].x=(uk[k].y-uk[k].x+cishu+1);
    92. 							remt-=cishu*20;
    93. 							int r1=min(remt,59ll);
    94. 							remt-=r1;
    95. 							ans[num].y=240+r1;
    96. 							finish++;
    97. 						}
    98. 					}
    99. 					if(remt==0&&finish==cnt)
    100. 					{
    101. 						f=1;
    102. 						cout<<"Yes\n";
    103. 						for(int k=0;k
    104. 						{
    105. 							if(P[k].op=='+') printf("+ %d/%d\n",P[k].x,P[k].y);
    106. 							else if(P[k].op=='-') printf("- %d\n",P[k].x);
    107. 							else if(P[k].op=='?'&&ans[k].x) printf("+ %d/%d\n",ans[k].x,ans[k].y);
    108. 							else if(P[k].op=='?') printf("- %d\n",P[k].y);
    109. 							else printf(".\n");
    110. 						}
    111. 						break;
    112. 					}
    113. 				}
    114. 			}
    115. 			if(!f) cout<<"No\n";
    116. 		}
    117. 		else cout<<"No\n";
    118. 	}
    119. }
    120. signed main()
    121. {
    122. 	//freopen("input.txt","r",stdin);
    123. 	//freopen("output.txt","w",stdout);
    124. 	//ios;
    125. 	int _t=1;
    126. 	//cin>>_t;
    127. 	while(_t--) solve();
    128. 	system("pause");
    129. 	return 0;
    130. }

  • 相关阅读:
    蓝桥杯备赛第五篇（动态规划）
    数据结构 六 理解二叉搜索树的实现
    图像语义分割 pytorch复现DeepLab v1图像分割网络以及网络详解（骨干网络基于VGG16）
    云原生Kubernetes：K8S安全机制
    算法刷题小结---几数之和
    供求两端的对接将不再是依靠互联网时代的平台和中心来实现的
    算法基础——时间复杂度和空间复杂度
    机器学习-K近邻(KNN)算法详解
    面试系列之-如何选择外包与自研公司
    实用调试技巧，debug
  • 原文地址：https://blog.csdn.net/qq_62615329/article/details/134319454