code forces round 998 (div. 3)

Question link:Codeforces Round 998 (Div. 3)

Summary: Reconstruction, Cwa was issued twice, and E read a false question.

A. Fibonacciness

tag: sign in

Solution: Simply simulate it.

void solve(){
    int a[5];
    for (int i = 0; i < 5; i ++){
        if (i == 2){
            continue;
        }
        cin >> a[i];
    }
    a[2] = a[0] + a[1];
    int ans = 0;
    for (int i = 2;  i < 5; i ++){
        if (a[i] == a[i - 1] + a[i - 2])
            ans ++;
        else
            continue;
    }
    a[2] = a[3] - a[1];
    int ans2 = 0;
    for (int i = 2;  i < 5; i ++){
        if (a[i] == a[i - 1] + a[i - 2])
            ans2 ++;
        else
            continue;
    }
    cout << max(ans, ans2) << endl;
}

B. Farmer John's Card Game

tag: sign in

Solution: Obviously, it is necessary to play cards incrementally one by one in order. After sorting everyone's cards, simulate the order of playing cards to see if it can be satisfied.

void solve(){
     int n, m;
     cin >> n >> m;
     vector<pii> ans(n); //
     set<int> a[n];

     for (int i = 0; i < n; i ++){
         ans[i].se = i; // Each person’s position
         for (int j = 0; j < m; j ++){
             int x;
             cin >> x;
             a[i].insert(x);
         }
         ans[i].fi = *(a[i].begin()); // Everyone’s smallest card
     }

     sort((), ());
     int t = 0;
     for (int j = 0; j < m; j ++)
         for (int i = 0; i < n; i ++){
             if (*(a[ans[i].se].begin()) == t){
                 a[ans[i].se].erase(t);
                 t++;
             }
             else{
                 cout << -1 << endl;
                 return;
             }
         }

     for (int i = 0; i < n; i ++){
         cout << ans[i].se + 1 << " \n"[i + 1 == n];
     }
 }

C. Game of Mathletes

tag: thinking

Solution: The score is fixed. As long as two numbers can add up to K, then b can score.

void solve(){
     int n, k;
     cin >> n >> k;
     vector<int> a(n);

     multiset<int> st;
     for (int i = 0; i < n; i ++){
         cin >> a[i];
         (a[i]);
     }
     sort((), ());

     int ans = 0;
     for (int i = 0; i < n; i ++){
         if (() == 0 || a[i] >= k)
             break;
         int b = k - a[i];
         if ((a[i]) != () && (b) != ()){
             auto x = (a[i]);
             (x);
             if ((b) == ()){ // avoid RE when a == b
                 (a[i]);
                 continue;
             }
             auto y = (b);
             (y);
             ans++;
         }
     }

     cout << ans << endl;
 }

D. Subtract Min Sort

tag: thinking

Description: Given n numbers, any number of operations can be performed. Each operation requires\(a_i\)and\(a_{i + 1}\)Also subtract\(min(a_i, a_{i +1})\). Ask if it is possible to change the original sequence into a non-decreasing sequence.

Solution: Start the simulation from the first number. Obviously the first number cannot be larger than the second number. Otherwise, if we let them operate, the first number will become zero and the operation can continue backwards.

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }

    for (int i = 1; i < n; i ++){
        if (a[i - 1] > a[i]){
            cout << "NO\n";
            return;
        }
        a[i] -= a[i - 1];
    }

    cout << "YES\n";
}

E. Graph Composition

tag: merge and search

Description: Given two undirected graphs F and G, you can operate on F:

• Create an edge between u and v.
• Delete an edge between u and v.
• Find the minimum number of operations such that there is a path between u and v in F, if and only if there is a path between u and v in G.

Solution: Build two union-find sets f and g, merge the points in g, first enumerate the edges in F, if the two points do not belong to the same union-find set in g, delete them, otherwise in f Merge them. Then enumerate the edges in g. If the two points in the figure are in the same union search set, merge them in f and record the number of operations.

Competing: Treat the graph as a connected graph.

void solve(){
     int n, m1, m2;
     cin >> n >> m1 >> m2;
     set<pii> a1, a2;
     DSU f(n + 1), g(n + 1);
    
     for (int i = 0; i < m1; i ++){
         int x, y;
         cin >> x >> y;
         if(x>y)
             swap(x, y);
         ({x, y});
     }

     for (int i = 0; i < m2; i ++){
         int x, y;
         cin >> x >> y;
         ({x, y});
         (x, y);
     }

     int ans = 0;
     for (auto [x, y] : a1){
         if ((x) != (y)){ // Must be deleted
             ans++;
         }
         else{
             (x, y);
         }
     }

     for (auto [x, y] : a2){
         if ((x) == (y)){
             ans += (x, y);
         }
     }
     cout << ans << endl;
    
 }