abc470

AtCoder Beginner Contest 470

异或运算 数学

A - Fizz

模拟

B - Monocolor

Problem Statement

There are \(N\) balls. Each ball is painted in one of \(N\) colors: color \(1\) through color \(N\). The color of the \(i\)-th ball \((1\le i\le N)\) is \(C_i\).

In one operation, you can change the color of any one ball to any of the \(N\) colors.

Find the minimum number of operations required to make all the balls the same color.

Constraints

• \(1\le N\le 100\)
• \(1\le C_i\le N\)
• All input values are integers.

Code

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+5,M=2e6+5,mod=998244353,inf=1LL<<60;
const long double pi=acos(-1);
int a[N];
void solve(){
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        int x;
        cin >> x;
        a[x]++;
    }
    int m = 0;
    for(int i = 1;i<=n;i++){ // 注意数据范围应该是从1到n
        m = max(m,a[i]);
    }
    cout << n-m;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout << fixed << setprecision(10);
    int T=1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

C - Inc, Dec, Xor

Problem Statement

There is a length-\(N\) integer sequence \(A=(A_1,A_2,\ldots,A_N)\). Initially, all elements of \(A\) are \(0\).

You will be given \(Q\) queries, which should be processed in order. There are two types of queries, each given in one of the following formats:

• 1 x: Increase the value of \(A_x\) by \(1\).
• 2: For each \(i=1,2,\ldots,N\), if \(A_i \geq 1\), decrease the value of \(A_i\) by \(1\).

Find the bitwise \(\mathrm{XOR}\) of \(A_1,A_2,\ldots,A_N\) immediately after processing each query.

What is bitwise \(\mathrm{XOR}\)?

The bitwise \(\mathrm{XOR}\) of non-negative integers \(A\) and \(B\), denoted \(A \oplus B\), is defined as follows:

• In the binary representation of \(A \oplus B\), the digit in the \(2^k\) (\(k \geq 0\)) place is \(1\) if exactly one of the digits in the \(2^k\) place of \(A\) and \(B\) in their binary representations is \(1\), and \(0\) otherwise.

For example, \(3 \oplus 5 = 6\) (in binary: \(011 \oplus 101 = 110\)).
More generally, the bitwise \(\mathrm{XOR}\) of \(k\) non-negative integers \(p_1, p_2, p_3, \dots, p_k\) is defined as \((\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)\), and it can be proved that this value does not depend on the order of \(p_1, p_2, p_3, \dots, p_k\).

Constraints

• \(1\le N\le 5\times 10^5\)
• \(1\le Q\le 5\times 10^5\)
• \(1\le x\le N\)
• All input values are integers.

Code

暴力模拟做法（不能AC，会超时）

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+5,M=2e6+5,mod=998244353,inf=1LL<<60;
const long double pi=acos(-1);
int a[M];  // 改之前AC2，其余RE，改之后AC9，TLE6
void solve(){
    int n,q;
    cin >> n >> q;
    int res = 0;
    for(int i =0;i<q;i++){
        int x;
        cin >> x;
        if(x==1){
            int hh;
            cin >> hh;
            res ^= a[hh];
            a[hh]++;
            res ^= a[hh];
            cout << res << endl;
        }else {
            for(int i = 1;i<=n;i++){
                if(a[i]>=1){
                    res ^= a[i];
                    a[i]--;
                    res ^= a[i];
                }
            }
            cout << res << endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout << fixed << setprecision(10);
    int T=1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

D - Inverse and Swap

Problem Statement

You are given a permutation \(P = (P_1, \dots, P_N)\) of \((1, \dots, N)\).

Process \(Q\) queries in order. There are two types of queries as follows:

• 1 x y: Swap the values of \(P_x\) and \(P_y\).
• 2: Construct the permutation \(P' = (P'_1, \dots, P'_N)\) of \((1, \dots, N)\) satisfying the following condition, and replace the values of \(P_1, \dots, P_N\) with \(P'_1, \dots, P'_N\), respectively. (One can prove that such \(P'\) uniquely exists.)
  • \(P_{P'_i} = i\) for every integer \(i\) satisfying \(1 \leq i \leq N\).

Output the values of \(P_1, \dots, P_N\) after processing all queries.

Constraints

• \(2 \leq N \leq 5 \times 10^5\)
• \(1 \leq Q \leq 5 \times 10^5\)
• \((P_1, \dots, P_N)\) is a permutation of \((1, \dots, N)\).
• \(1 \leq x < y \leq N\) for queries of type \(1\).
• All input values are integers.

Code

暴力模拟（会超时）

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll N=1e5+5,M=2e6+5,mod=998244353,inf=1LL<<60;
const long double pi=acos(-1);
// 优化前AC20超时16
void solve(){
    int n,q;
    cin >> n >> q;
    vector<int> p;
    vector<int> tt;
    p.push_back(0);
    for(int i = 0;i<n;i++){
        int x;
        cin >> x;
        p.push_back(x);
        tt.push_back(x);
    }
    for(int i = 0;i<q;i++){
        int x;
        cin >> x;
        if(x==1){
            int a,b;
            cin >> a >> b;
            int t = p[a];
            p[a] = p[b];
            p[b] = t;
        }else if(x==2){
            for(int j = 1;j<=n;j++){
                // int z = p[j];
                tt[p[j]] = j;
            }
            for(int j = 1;j<=n;j++){
                p[j] = tt[j];
            }
        }
    }
    for(int i = 1;i<=n;i++){
        cout << p[i] << " ";
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout << fixed << setprecision(10);
    int T=1;
    //cin >> T;
    while(T--) solve();
    return 0;
}