Location>code7788 >text

Niuke Weekly Round 77

Popularity：989 ℃/2025-01-20 20:26:29

Question link:Niuke Weekly Round 77

A. schedule

tag: sign in

B. Sudoku array

tag: sign in

Description: Given n numbers, the range of each number is1-9, asking whether it can be arranged so that each continuous subarray of length 9 contains1-9these 9 numbers.

Solution: The hand model found that every number must appear in the front and the same number of times, and finally some numbers will appear only once. Therefore, as long as the difference between the minimum number of times and the maximum number of times to judge the number is not greater than 1.

C. Xiaohong walks on the grid

tag：gcd

Solution: Up and down and left and right are independent, according to Pei Shu’s theoremax + by | gcd(a, b)。

void solve(){
    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;

    int t1 = gcd(a, b), t2 = gcd(c, d);
    
    if (y % t1 == 0 && x % t2 == 0){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
}

D. Hidden social networks

tag: union search + bit operation

Solution: Perform bitwise operations, use the account whose bit is 1 and search the set for merging.

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

    for (int i = 0; i < 63; i ++){
        int t = -1;
        for (int j = 1; j <= n; j ++){
            if (a[j] >> i & 1){
                if (t == -1)
                    t = j;
                else{
                    (t, j);
                }
            }
        }
    }

    int ans = 1;
    for (int i = 1; i <= n; i ++){
        ans = max(ans, (i));
    }

    cout << ans << endl;
}

E. 1or0

tag: line segment tree

F. Ji Shu

tag: thinking

Solution: Consider the answer to lca with u as the target, and num[i] records the number of target nodes contained in the subtree rooted at i.

  • Traversing the child nodes of u, the number of target nodes that have been traversed is x, then the contribution of the current node is x * num[i].
  • When it is the target node, x is 1.
void solve(){
     int n;
     cin >> n;
     vector g(n + 1, vector<int>());
     vector<int> flag(n + 1);

     for (int i = 1; i < n; i ++){
         int a, b;
         cin >> a >> b;
         g[a].pb(b);
         g[b].pb(a);
     }

     int ans = 0;
     int k;
     cin >> k;
     for (int i = 0; i < k; i ++){
         int x;
         cin >> x;
         flag[x] = true;
     }

     vector<int> num(n + 1); // Record how many target nodes there are under each subtree

     function<void(int, int)> dfs1 = [&](int u, int fa){
         if (flag[u])
             num[u]++;
         for (auto v : g[u]){
             if (v == fa)
                 continue;
             dfs1(v, u);
             num[u] += num[v];
         }

     };
     dfs1(1, 0);

     vector<int> cnt(n + 1);

     function<void(int, int)> dfs2 = [&](int u, int fa){
         int x = 0;
         if (flag[u]){
             cnt[u]++;
             x = 1;
         }
        
         for (auto v : g[u]){
             if (v == fa)
                 continue;
            
             cnt[u] += x * num[v] * 2;
             x += num[v];

             dfs2(v, u);
         }
        
     };
     dfs2(1, 0);
     
     for (int i = 1; i <= n; i ++){
         cout << cnt[i] << " ";
     }
 }
<Previous Next>