better reading experience \color{red}{Better reading experience} better reading experience

A. Mocha is in small classes

Original title link

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 = 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

Original title link

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 = 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

Original title link

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

Original title link

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

Original title link

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
        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;

}

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:
  • 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.