better reading experience \color{red}{Better reading experience} better reading experience
A. Mocha is in small classes
Topic meaning:
 a number that differs from each other n n composed of n digits.
 output n n The smallest integer of n bits (without leading zeros) that satisfies the above conditions.
 output if it does not exist − 1 1 −1 .
Thought:
 Sign in question.
 When n <= 10, the smallest n n The sequence of n digits is [1, 0, 2, 3, 4, 5, 6, 7, 8 , 9].
 When n > 10 there is no number that satisfies the condition.
Code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e6, PI = acos(1); int a[] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9}; void solve(){ int n; cin >> n; if(n > 10) cout << 1 << endl; //There is no number greater than 10 that satisfies the condition else{ for(int i = 0 ; i < n; i ++) cout << a[i]; //Note the order of swapping 1s and 0s } return ; } int main(){ IOS; int _ = 1; // cin >> _; while(_ ){ solve(); } return 0; }
E. Serval's Haiku
Topic meaning:
 Given a length of n n string of n S S S .
 Find if there is a length of
17
17
A subsequence of 17 satisfies:
 S ′ 1 , S ′ 2 , S ′ 3 , S ′ 4 , S ′ 5 S′_1 , S′_2 , S′_3 , S′_4 , S′_5 S′1,S′2,S′3,S′4,S′5 are the same character;
 S ′ 6 , S ′ 7 , . . . , S ′ 11 , S ′ 12 S′_6 , S′_7 , . . . , S′_{11}, S′_{12} S′6,S′7,...,S′11,S′12 are the same character;
 S ′ 13 , S ′ 14 , S ′ 15 , S ′ 16 , S ′ 17 S′_{13}, S′_{14}, S′_{15}, S′_{16}, S′_{17} S′13,S′14,S′15,S′16,S′17 are the same character.
 Output the subsequence if it exists, or none if it does not exist.
Thought:
 Sign in question.
 brute force enumeration S i S_i Si, statistically satisfied S 1 ′ ∼ S 5 ′ S'_1 \sim S'_5 S1′∼S5′, if a satisfying subsequence can be found, mark the character and enter the next layer of loop;
 brute force enumeration S j S_j Sj, statistically satisfied S 6 ′ ∼ S 12 ′ S'_6 \sim S'_{12} S6′∼S12′, if a satisfying subsequence can be found, mark the character and enter the next layer of loop;
 brute force enumeration S k S_k Sk, statistically satisfied S 13 ′ ∼ S 17 ′ S'_{13} \sim S'_{17} S13′∼S17′, if you can find a satisfying subsequence, you can directly output the above marked.
 When n < 17 or no subsequence that satisfies the condition is found, output none.
 Since the subsequence of each segment is short, the worst case is 2 6 3 × 5 2 × 7 = 3 , 075 , 800 26^3 \times 5^2 \times 7 = 3,075,800 263×52×7=3,075,800, the actual situation will be much smaller than the time complexity, so it is completely O K OK OK .
Code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 200; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e6, PI = acos(1); void solve(){ int n; cin >> n; if(n < 17){ //Not long enough to find cout << "none" << endl; return ; } string s; cin >> s; int vis1[N] = {0}; //Count the same first 5 characters for(int i = 0; i < s.size(); i ++){ vis1[s[i]] ++; if(vis1[s[i]] == 5){ char op1 = s[i]; //mark the first 5 characters int vis2[N] = {0}; //Count the same middle 7 characters for(int j = i + 1; j < s.size(); j ++){ vis2[s[j]] ++; if(vis2[s[j]] == 7){ char op2 = s[j]; //Mark the middle 7 characters int vis3[N] = {0}; //Count the same last 5 characters for(int k = j + 1; k < s.size(); k ++){ vis3[s[k]] ++; if(vis3[s[k]] == 5){ //Find the last 5 characters and output directly for(int u = 0; u < 5; u ++) cout << op1; for(int u = 0; u < 7; u ++) cout << op2; for(int u = 0; u < 5; u ++) cout << s[k]; return ; } } } } } } //No sequence found that satisfies the condition cout << "none" << endl; return ; } int main(){ IOS; int _ = 1; // cin >> _; while(_ ){ solve(); } return 0; }
F. Sum of Sets
Topic meaning:
 for two finite sets of numbers
A
,
B
A,B
A,B, Definition
A
+
B
A+B
A+B is:
 A + B = { x + y ∣ x ∈ A , y ∈ B } A + B = \{x + y~~ x \in A, y \in B \} A+B={x+y ∣ x∈A,y∈B}
 remember finite sets A A The number of elements in A is ∣ A ∣ A ∣A∣.
 given n n n, to satisfy ∣ A + A ∣ = n A + A = n ∣A+A∣=n , and satisfy ∀ x ∈ A , 0 ≤ x ≤ 5 × 1 0 5 \forall x \in A, 0\le x \le 5\times10^5 The set of numbers ∀x∈A,0≤x≤5×105 A A A .
 if exists A A If A satisfies the above conditions, output the number of contained elements and output the contained elements (any solution is acceptable), output if it does not exist − 1 1 −1.
Thought:

Thought, law, structure.

Construct a simple set of numbers A = { 0 , 1 , 2 , ... , k } , ∣ A ∣ = k A = \{0,1,2,\dots,k\}, A = k A={0,1,2,…,k},∣A∣=k, then A + A = { 0 , 1 , 2 , ... , 2 k } , ∣ A + A ∣ = 2 k + 1 A + A = \{0,1,2,\dots,2k\},A+A = 2k + 1 A+A={0,1,2,...,2k},∣A+A∣=2k+1.

Through the above construction, it is obvious that when n n When n is an odd number, there must be a solution, we only need to construct a number set that satisfies the above rules.

Discuss next n n When n is even:
 ∣ A ∣ = 2 , ∣ A + A ∣ = 3 A = 2, A+A = 3 ∣A∣=2, ∣A+A∣=3, when n = 2 n = 2 No solution when n=2;
 ∣ A ∣ = 3 , 5 ≤ ∣ A + A ∣ ≤ 6 A =3,5\le A+A\le 6 ∣A∣=3,5≤∣A+A∣≤6, when n = 4 n = 4 No solution when n=4;
 In other cases, construct the set A = { 0 , 2 , 3 , ... , k } A = \{0,2,3,\dots,k\} A={0,2,3,…,k}, then A + A = { 0 , 2 , 3 , ... , 2 k } , ∣ A + A ∣ = 2 k A+A =\{0,2,3,\dots,2k\},A+A = 2k A+A={0,2,3,...,2k},∣A+A∣=2k.

In summary, according to the n n The parity of n can be constructed according to the above rules.
Code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, string> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e6, PI = acos(1); int n; void solve(){ cin >> n; if(n == 2  n == 4){ cout << 1 << endl; return ; } if(n % 2 != 0){ //Odd numbers construct 0, 1, 2, 3,...,(n  1) / 2 cout << (n  1) / 2 + 1 << endl; for(int i = 0; i <= (n  1) / 2; i ++) cout << i << ' '; } else{ //Even numbers construct 0, 2, 3,..., n / 2 cout << n / 2 << endl; cout << 0 << ' '; for(int i = 2; i <= n / 2; i ++) cout << i << ' '; } } int main(){ IOS; int _ = 1; while(_ ){ solve(); } return 0; }
G. Mocha is in big class
Topic meaning:
 given n n n 01 01 01 string and q q q operations, each operation will i i i strings of l − r l − r l−r bits are replaced with and j j j strings l − r l − r The result of ANDing the lr bits respectively.
 the first i i i operations have probability p i p_i pi succeeded.
 ask last n n In the strings obtained by the AND operation of n strings 1 1 1 number.
Thought:
 thinking question.
 Probability expects to be skinned, in fact, no need to deal with it.
 as long as it appears in a column 0 0 0, since the "AND" bit operation is performed, no matter how many times the operation is performed, it will not affect any one 01 01 01 series i i the value of the i bits, the result must be 0 0 0.
 So directly calculate the initial 01 01 01 String and operation after 1 1 The number of 1 is the answer.
Code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, string> PII; typedef pair<LL, LL> PLL; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e6, PI = acos(1); const int N = 1010; char a[N][4 * N]; int n, m; void solve(){ int res = 0; cin >> n >> m; for(int i = 0; i < n; i ++) cin >> a[i]; int q; cin >> q; while(q ){ for(int i = 0; i < 5; i ++){ int op; cin >> op; } } for(int i = 0; i < m; i ++){ int cnt = 1; for(int j = 0; j < n; j ++){ if(a[j][i] == '0') cnt = 0; //When there is a column of 0 } res += cnt; } cout << res << endl; } int main(){ IOS; int _ = 1; while(_ ){ solve(); } return 0; }
H. Swivel water pipe
Topic meaning:
 given 2 × m 2 \times m 2×m water pipe diagram, there are two types of water pipes, I and L, and both water pipes can be rotated.
 Ask if it is possible to rotate the water pipe so that the water flows from x x After column x flows in from y y y column flows out.
Thought:
 DFS search.
 The water outlet state of the water pipe is related to the entry state, so it is necessary to record the state when the previous grid flows into the next grid.
 The analysis status shows that:
 For Ishaped water pipes, the outflow and inflow states are the same.
 For Lshaped water pipes, when the inflow state is ↑ \uparrow ↑ or ↓ \downarrow ↓, there are two states when flowing out ← \leftarrow ← and → \rightarrow →; when the inflow state is ← \leftarrow ← or → \rightarrow → , there are two states when flowing out ↑ \uparrow ↑ and ↓ \downarrow ↓ .
 According to the above analysis, we can get the offset of the corresponding state, and the coordinate transfer can be achieved by adding the offset during the search.
Code:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 10; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e6, PI = acos(1); char mp[2][N]; bool vis[2][N]; int m, sl, el; bool flag = 0; void dfs(int l, int r, int st){ if(flag == 1) return ; //Return directly if the conditions are met if(l == 2 && r == el  1){ //Crossing the border is only legal if it reaches the exit flag = 1; //mark answer return ; } if(l < 0  l >= 2  r < 0  r >= m) return ; //Return directly out of bounds if(vis[l][r]) return ; //go back through the point vis[l][r] = 1; //mark walk if(l >= 0 && l < 2 && r >= 0 && r < m){ if(mp[l][r] == 'I'){ //Incoming state and outgoing state are the same if(st == 0) dfs(l + 1, r, 0); if(st == 1) dfs(l, r + 1, 1); if(st == 2) dfs(l  1, r, 2); if(st == 3) dfs(l, r  1, 3); } else{ if(st == 0  st == 2){ //the state of flowing in from below or above dfs(l, r + 1, 1); dfs(l, r  1, 3); } if(st == 1  st == 3){ //state of inflow from left or right dfs(l + 1, r, 0); dfs(l  1, r, 2); } } } vis[l][r] = 0; //Searched back to the recovery site return ; } bool solve(){ cin >> m >> sl >> el; for(int i = 0; i < 2; i ++) cin >> mp[i]; flag = 0; //Multiple instances, initialization for(int i = 0; i < 2; i ++){ for(int j = 0; j <= m; j ++) vis[i][j] = 0; } dfs(0, sl  1, 0); return flag; } int main(){ IOS; int _ = 1; cin >> _; while(_ ){ if(solve()) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
Postmatch review and summary
Participation for the first time C C P C CCPC CCPC, first post a record:
copper tail is 188 188 188, our team 191 191 191 Bushi (bushi) ah ah ah ah. . .
Schedule review
 The two junior teammates are still very powerful, and they are cut off when they come up. A A A question, won a beautiful AC.
 I did a rough calculation afterwards E E The time complexity of the E question, so the three loops were violently cut off, although because the vis array for counting the number of letters was too small, a WA was eaten in vain, laying a solid foundation for the team.
 then i found H H Question H is a search that seems to work? Since then, the team has lost one person. . .
 teammates F F F, get on the machine and print the meter, I tore the paper by hand H H H.
 teammates G G G , I finally found out that it was a fraud question expected by the Daosha pen cover. After writing the unexpected example at the speed of light, I rushed directly, and the small WA was over in a flash. It is a pity that it was not cut off at the beginning.
 Then zhgg started to help me tune my sand pen H H Question H, because I felt that the idea of BFS was completely fine, I stuck to the end, and finally got dizzy and confused with the coordinates. I rewrote it for half an hour and finally didn't figure it out, so I sent it directly (._.).
 The last desperate look at the list 200 + 200+ The team with 200+ rankings without the big star can get the Bronze Tail after a rough calculation~~ (I found that it was too naive after the game)~~, but the Vita lemon tea is really delicious, let’s escape.
Postmatch summary:
 The fundamental reason for ironing is that his ability is too weak.
 Its essence is my laziness. I was slack in thinking and lax in action when I should have achieved results. If the training volume is not up to the mark, I still try to get results.
 This competition also clearly felt the lack of experience. The two junior teammates were unusually calm and stable. In comparison, I, who had no competition experience, was in a hurry during the competition and dragged down the team.
 The last is the assignment and cooperation of the competition topics. We did not get along well with each other when the team participated in the competition. When my teammates were discussing, I went to solve the questions that I was not sure about, but I still didn’t solve them. I also missed the opportunity and time to discuss and look at other topics. .
PS:
 Future plans:
 additional training;
 additional training;
 Or TMD training.
 Take time out with your teammates to play a few more VP games and train your team to work together.
 Try your hardest, next time I C P C ICPC ICPC will win.