題號題目知識點質量

1504A	Déjà Vu	思維題
1504B	Flip the Bits	貪心
1504C	Balance the Bits	構造題
1504D	3-Coloring	思維題，構造題
1504E	Travelling Salesman Problem	思維題	好題啊
1504F	Flip the Cards	貪心，思維題	現在還沒搞明白，不錯的思維題

A~D題解代碼如下
E

文章目錄

• • A
  • • 題意：
    • 題解：
    • 代碼：
  • B
  • • 題意：
    • 題解：
    • 代碼：
  • C
  • 題目：
  • 題解：
  • 代碼：
  • D
  • 題目：
  • 題解：
  • 代碼：

A

題意：

給你一個字符串，在某一個位置添加一個a，問能不能不構成回文串，并輸出任意答案

題解：

從開頭開始找，只要不是a，對應的另一端的位置直接插入a即可

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int main() {int t;cin>>t;while(t--){string a;cin>>a;bool f=0;for(int i=0;i<a.length();i++){if(a[i]!='a'){f=1;break;}}if(f==0){cout<<"NO"<<endl;}else {cout<<"YES"<<endl;for(int i=0;i<a.length();i++){if(a[i]!='a'){a.insert(a.length()-i, "a");//cout<<"a="<<a<<endl;break;}}cout<<a<<endl;}} }

B

題意：

從第一位開始，任意長度選一個區間，區間內0，1翻轉，問a串能不能變成b串

題解：

過了太久記不清了。。。
奧對，不同的相鄰區間內0和1一樣多，且之前的相同的相鄰區間內0和1數量一樣多，
我們將區間分為a和b一樣的區間和a和b不一樣的區間，每到一個新區間，前一個區間內的01必須一樣多，這樣翻轉才不會亂
應該是這樣
比如：
0111010000
0100101100
區間1 ~ 2一樣，區間3 ~ 8不一樣
這兩個區間內，各自的01數量必須一樣多
區間9 ~ 10因為在區間3 ~ 8之后，所以不用考慮

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=3e5+8; int x[maxn]; int sum[maxn]; int main() {int t;cin>>t;while(t--){int n;cin>>n;string a,b;cin>>a>>b;if(a==b){cout<<"YES"<<endl;continue;}//for(int i=0;i<n;i++)sum[i]+=(a[i]=='1');int last=-1;bool f=0;int x1=0,x0=0;int y1=0,y0=0;bool xx=0;for(int i=0;i<=n;i++){if(a[i]==b[i]){if(a[i]=='1')y1++;else y0++;if(x0!=x1){f=1;break;}x0=0;x1=0;}else if(a[i]!=b[i]){if(a[i]=='1')x1++;else x0++;if(y1!=y0){f=1;break;}y1=0;y0=0;}}if(f==1||(x1!=x0))cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0; }

C

題目：

給你一個01串，構造兩個由括號組成的字符串，1表示該位置的兩個字符串一樣，0表示不一樣

題解：

首先兩端必然是1，不然有朝內朝外
我記得前一半1第一個字符串是"("，后一半1第一個字符串是“）”
對于0，根據奇偶性輸出左右括號
第二個字符串對于1和第一個一樣，對于0直接反過來就行
具體構造思路。。太久忘了。。

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e5+9; int b[maxn]; int main() {int t;cin>>t;while(t--){int n;cin>>n;string a;cin>>a;//int len=a.length();if(a[0]=='0'||a[n-1]=='0'){cout<<"NO"<<endl;continue;}int len=0;for(int i=0;i<n;i++){if(a[i]=='0')len++;}if(len%2==1){cout<<"NO"<<endl;continue;}int len2=n-len;len2/=2;cout<<"YES"<<endl;int ww=0;for(int i=0;i<n;i++){if(a[i]=='1'){ww++;if(ww<=len2){b[i]=0;}else b[i]=1;}}int x=0;for(int i=0;i<n;i++){if(a[i]=='1'&&b[i]==0)cout<<"(";else if(a[i]=='1'&&b[i]==1)cout<<")";else if(a[i]=='0'){x++;if(x%2==1)//奇數個{cout<<")";} else {cout<<"(";}}}cout<<endl;x=0;for(int i=0;i<n;i++){if(a[i]=='1'&&b[i]==0)cout<<"(";else if(a[i]=='1'&&b[i]==1)cout<<")";else if(a[i]=='0'){x++;if(x%2==1)//奇數個{cout<<"(";} else {cout<<")";}}}cout<<endl;}return 0; }

D

交互題

題目：

每次從1 ~ 3給你一個數，如果給了x就不能選x，再另外兩個數里選個數填進n * n的格子里，要求相鄰的格子不能有一樣的數，問怎么構造

題解：

想象一下網格的顏色就像一個黑白方格的棋盤。然后鮑勃的策略是，只要他有能力，就把1號記號放在白色方塊上，把2號記號放在黑色方塊上。如果他不能，這意味著一種顏色的所有方塊都被填滿，他可以開始放置標記3，而不會產生無效的顏色。更具體地說，這是他的策略：
如果Alice選擇1：
如果一個黑色正方形是空的，在那里放一個2。
否則，將3放在白色單元格上。
如果Alice選擇2：
如果一個白色正方形是空的，在那里放一個1。
否則，將3放在黑色單元格上。
如果Alice選擇3：
如果一個白色正方形是空的，在那里放一個1。
否則，將2放在黑色單元格上。
總結：
1放白，2放黑，3穿插在其中

代碼：

#include <bits/stdc++.h> #define BLACK 0 #define WHITE 1 using namespace std;int main() {ios::sync_with_stdio(false); // cin.tie(0);int n;cin >> n;vector<pair<int, int>> ve[2];// color the cells like a checkerboard// ve[COLOR] = {list of unfilled cells of that color}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {ve[(i + j) % 2].push_back({i, j});//(i + j) % 2==1就是白 }}for(int t = 1; t <= n * n; t++) {int a, b, i, j, col;cin >> a;// choose an available checkerboard color and a token color for itif(a == 1) {if(!ve[BLACK].empty()) {col = BLACK;b = 2;}else {col = WHITE;b = 3;}}else if(a == 2) {if(!ve[WHITE].empty()) {col = WHITE;b = 1;}else {col = BLACK;b = 3;}}else { // a == 3if(!ve[WHITE].empty()) {col = WHITE;b = 1;}else {col = BLACK;b = 2;}}tie(i, j) = ve[col].back();ve[col].pop_back();cout << b << ' ' << i << ' ' << j << endl;} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Codeforces Round #712 (Div. 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。