# 2022 CCPC Henan Province Competition (A,E,F,G,H)

## 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:

• 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 = 1e-6, 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:

• 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 = 1e-6, 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 = 1e-6, 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 l-r 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 = 1e-6, 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 I-shaped water pipes, the outflow and inflow states are the same.
• For L-shaped 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 = 1e-6, 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
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;

}


## Post-match 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.

Post-match 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: