【题解】Codeforces Round #619 (Div. 2)

缺乏、安全感 2023-07-05 11:43 65阅读 0赞

比赛链接:https://codeforces.com/contest/1301

#

  • A. Three Strings(思维)
  • B. Motarack’s Birthday(思维)
  • C. Ayoub’s function(思维)
  • D. Time to Run(构造)

A. Three Strings(思维)

原题链接:https://codeforces.com/contest/1301/problem/A

  • 题意: 给三个相同长度 n 字符串 a,b,c,c 每个字符必须和 a 或者 b 的相应下标字符交换,问经过 n 次变换后 a 是否可以和 b 相同。
  • 思路: a 的字符与 c 的相同或者 b 的字符与 c 的相同既符合交换。如果三个字符都相同也是一样的,交换后还是 a 和 b 还是相同。

Code:

  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. int main(){
  5. int t; cin>>t;
  6. while(t--){
  7. string a,b,c; cin>>a>>b>>c;
  8. ll len=a.length();
  9. int flag=1;
  10. for(int i=0;i<len;i++){
  11. if(a[i]==c[i] || b[i]==c[i])
  12. continue;
  13. else{
  14. flag=0;
  15. break;
  16. }
  17. }
  18. if(flag) cout<<"YES"<<endl;
  19. else cout<<"NO"<<endl;
  20. }
  21. return 0;
  22. }

B. Motarack’s Birthday(思维)

原题链接:https://codeforces.com/contest/1301/problem/B

  • 题意: 给一个长度为 n 的数组,-1 代表没有数,你需把空位补上相同的 k ,使得数组相邻元素中的最大的差值的绝对值最小。
  • 思路: 先找出旁边有空位的数的最大值和最小值,然后取中间值作为 k,将空位全部补上,遍历一遍数组,输出最大的差值的绝对值。

Code:

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #define inf 0x3f3f3f3f
  5. using namespace std;
  6. typedef long long ll;
  7. const int N=1e5+10;
  8. int a[N];
  9. int main(){
  10. int t; cin>>t;
  11. while(t--){
  12. memset(a,0,sizeof(a));
  13. int n; cin>>n;
  14. int maxn=0,minn=inf,flag=0;
  15. for(int i=1;i<=n;i++){
  16. cin>>a[i];
  17. if(a[i]!=-1) flag=1;
  18. }
  19. for(int i=1;i<=n;i++){
  20. if(a[i]!=-1 && (a[i-1]==-1 || a[i+1]==-1)){
  21. maxn=max(maxn,a[i]);
  22. minn=min(minn,a[i]);
  23. }
  24. }
  25. if(!flag){
  26. cout<<0<<' '<<0<<endl;
  27. continue;
  28. }
  29. int mid=(maxn+minn)/2;
  30. for(int i=1;i<=n;i++){
  31. if(a[i]==-1)
  32. a[i]=mid;
  33. }
  34. int ans=0;
  35. for(int i=2;i<=n;i++)
  36. ans=max(ans,(int)abs(a[i]-a[i-1]));
  37. cout<<ans<<' '<<mid<<endl;
  38. }
  39. return 0;
  40. }

C. Ayoub’s function(思维)

原题链接:https://codeforces.com/contest/1301/problem/C

  • 题意: 给长度 n ,m 个 1,构造出一个含 1 子串数量最大的字符串,求最多的含 1 子串数量。
  • 思路:
  1. 用子串总数量减掉不含 1 子串数量即为含 1 子串数量。一个字符串子串数量为 n*(1+n) / 2。
  2. m 个 1 把 n-m 个 0 分割成 m+1 部分,要使得含 1 子串数量最多,就得将 0 平均分给这 m+1 部分。a = (n-m) / (m+1)就是平均每份 0 的数量,剩下的 b = (n-m)%(m+1) 就在 m+1 份放个 1 。没放 1 的部分就有 m+1-b 份。
  3. 放 1 部分不含 0 的子串数量有 b*(a+2)*(a+1)/2 ,不放 1 部分不含 0 的子串数量有 c(1+a)a/2。

Code:

  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. int main(){
  5. int t; cin>>t;
  6. while(t--){
  7. ll n,m; cin>>n>>m;
  8. ll a = (n-m)/(m+1);
  9. ll b = (n-m)%(m+1);
  10. ll c = m+1-b;
  11. cout<<(1+n)*n/2-b*(a+2)*(a+1)/2-c*(1+a)*a/2<<endl;
  12. }
  13. return 0;
  14. }

D. Time to Run(构造)

原题链接:https://codeforces.com/contest/1301/problem/D

  • 题意: 给一个 n*m 的图,路线在图中已标出,问能否在图中走 k 步,路线不能重复,点可以重复。如果不能走,输出“NO”,否则输出 “YES” ,总步骤,每个步骤不能超出 4 个步数,并且总步骤数不能超过 3000 次。
  • 思路: 走法如图所示
    在这里插入图片描述
  1. 当没走到第 m 列时,每一列都要进行 n-1 次 “D”,n-1 次 “RLU”,1 次 “R”。
  2. 当走到第 m 列时,要进行 n-1 次 “D”,n-1 次 “U”,m-1 次 “L”。

Code:

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. struct node{
  5. int cnt;
  6. string str;
  7. node(int sum,string s){
  8. cnt=sum;
  9. str=s;
  10. }
  11. };
  12. vector<node> a;
  13. void push(node x){
  14. if(x.cnt!=0)
  15. a.push_back(x);
  16. }
  17. int main(){
  18. int n,m,k; cin>>n>>m>>k;
  19. if(4*n*m-2*n-2*m<k)
  20. cout<<"NO"<<endl;
  21. else{
  22. cout<<"YES"<<endl;
  23. int cow=1;
  24. while(k){
  25. if(cow!=m){
  26. if(k>=(n-1)){
  27. push({ n-1,"D"});
  28. k-=(n-1);
  29. }
  30. else{
  31. push({ k,"D"});
  32. k=0;
  33. }
  34. if(k==0) break;
  35. if(k>=3*(n-1)){
  36. push({ n-1,"RLU"});
  37. k-=3*(n-1);
  38. }
  39. else{
  40. push({ k/3,"RLU"});
  41. if(k%3==1) push({ 1,"R"});
  42. else if(k%3==2) push({ 1,"RL"});
  43. k=0;
  44. }
  45. if(k==0) break;
  46. if(k>=1){
  47. push({ 1,"R"});
  48. k--;
  49. }
  50. }
  51. else{
  52. if(k>=n-1){
  53. push({ n-1,"D"});
  54. k-=(n-1);
  55. }
  56. else{
  57. push({ k,"D"});
  58. k=0;
  59. }
  60. if(!k) break;
  61. if(k>=n-1){
  62. push({ n-1,"U"});
  63. k-=(n-1);
  64. }
  65. else{
  66. push({ k,"U"});
  67. k=0;
  68. }
  69. if(!k) break;
  70. if(k>=m-1){
  71. push({ m-1,"L"});
  72. k-=(m-1);
  73. }
  74. else{
  75. push({ k,"L"});
  76. k=0;
  77. }
  78. }
  79. cow++;
  80. }
  81. cout<<a.size()<<endl;
  82. for(int i=0;i<a.size();i++)
  83. cout<<a[i].cnt<<' '<<a[i].str<<endl;
  84. }
  85. return 0;
  86. }

发表评论

表情:
评论列表 (有 0 条评论,65人围观)

还没有评论,来说两句吧...

相关阅读