Codeforces Round 748 div.3 A-G

A. Elections

题意：有三个数ABC，问他们分别需要加多少才能成为三个数中最大的

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    int mx = max(a, max(b, c));
    int mx2 = a+b+c - mx - min(a, min(b, c));
 
    if(a == mx && mx2 != mx) cout << "0 ";
    else cout << mx+1-a << ' ';
    if(b == mx && mx2 != mx) cout << "0 ";
    else cout << mx+1-b << ' ';
 
    if(c == mx && mx2 != mx) cout << "0\n";
    else cout << mx+1-c << '\n';
 
}

B. Make it Divisible by 25

题意：给定一个数字，问至少从中删除几位数，可以使他能被25整除

只要最后两位是00,25,50,75即可，那么从低位到高位找，分别找这几种第一次出现的位置，取最小即可

int a[maxn], ans;

void getnum(int a1, int a2){
    for(int i=1;i<20;i++){
        if(a[i] == a2){
            for(int j=i+1;j<20;j++){
                if(a[j] == a1){
                    ans = min(ans, j - 2);
                    return;
                }
            }
        }
    }
}

void solve(){
    ll n;
    cin >> n;
    ans = 1e9;
    for(int i=1;i<=20;i++){
        a[i] = n%10;
        n /= 10;
    }
    getnum(0, 0);
    getnum(5, 0);
    getnum(2, 5);
    getnum(7, 5);

    cout << ans << '\n';
}

C. Save More Mice

题意：X轴上有若干个老鼠，每个老鼠的位置都是整数，$(n,0)$ 处有一个洞，$(0,0)$ 中有一只猫，每回合可以选择一只老鼠向右移动一格，抵达洞即安全，每回合猫也向右移动一格，吃掉该格上的老鼠。问最多可以让多少老鼠存活

因为老鼠和猫的移动速度相同，任何一只老鼠都不可能和猫拉开距离，所以每次都选择离洞最近的老鼠让它进洞，答案一定最大。模拟即可。

void solve(){
    ll n, k;
    cin >> n >> k;
    for(int i=1;i<=k;i++){
        cin >> a[i];
    }
    sort(a+1, a+k+1);
    ll ans = 0, p = 0;
    for(int i=k;i>=1;i--){
        if(p >= a[i]) break;
        p += n - a[i];
        ans++;
    }
    cout << ans << '\n';
}

D1. All are Same

题意：给一个序列，要找一个最大的 $k$，使得所有数都可以减去若干个 $k$ 后变成相同的数字

找到最小的数 $mi$，然后计算每个数和 $mi$ 的差的 $gcd$ 和即可

int st[maxn];
struct Edge{
    int t, nt, tp;
}e[maxn << 1];
int head[maxn], ecnt = 0;

inline void add(int x, int y, int tp){
    e[++ecnt].t = y;
    e[ecnt].tp = tp;
    e[ecnt].nt = head[x];
    head[x] = ecnt;
}

int num[2];
bool dfs(int p){
    for(int i=head[p];i;i=e[i].nt){
        int v = e[i].t;
        if(st[v] == -1){
            st[v] = st[p] ^ e[i].tp;
            num[st[v]]++;
            if(!dfs(v)) return false;
        }else{
            if(st[v] != (st[p] ^ e[i].tp)) return false;
        }
    }
    return true;
}

void solve(){
    int n, m;
    cin >> n >> m;

    ecnt = 0;
    for(int i=1;i<=n;i++){
        head[i] = 0;
        st[i] = -1;
    }

    for(int i=1;i<=m;i++){
        int x, y; string s;
        cin >> x >> y >> s;
        int tp = (s[0] == 'i');
        add(x, y, tp);
        add(y, x, tp);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(st[i] == -1){
            st[i] = 1;
            num[1] = 1;
            num[0] = 0;
            if(!dfs(i)){
                cout << "-1\n";
                return;
            }
            ans += max(num[0], num[1]);
        }
    }
    cout << ans << '\n';
}

D2. Half of Same

题意：和D1一样，区别在于只需要有一半数减去若干个 $k$ 后变成相同的数字

$n\le40, -10^6\le a_i \le 10^6$

先考虑，如果有一个 $k$，我们怎么判断它是否合法：

可以让每个数都减 $k$ 减到第一次小于 $mi$ 为止，然后数一下有多少数是相同的

这个Judge过程是 $O(n)$ 的

那么有多少个 $k$ 需要judge呢？

可以从1到2e6全部枚举一遍，$O(2e6\times n)$ 看似可行，然而被卡常了

想到这个 $k$ 一定是某两个数的差的约数，又因为 $n$ 很小，可以非常暴力地枚举任意两个数，再枚举它们差的约数，总复杂度 $O(n^2\sqrt{2\times10^6}\times n)$

int a[50];
int mia, mxa;
int num[5000009];
int n;
 
bool judge(int k){
    bool re = false;
    for(int i=1;i<=n;i++){
        int t = a[i] - (a[i]-mia+k-1)/k*k;
        num[t]++;
        if(num[t] >= n/2) re = true;
    }
    for(int i=1;i<=n;i++){
        int t = a[i] - (a[i]-mia+k-1)/k*k;
        num[t]--;
    }
    return re;
}
 
void solve(){
    cin >> n;
    mia = 2e8, mxa = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i] += 4000000;
        mia = min(mia, a[i]);
        mxa = max(mxa, a[i]);
    }
 
    sort(a+1, a+n+1);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(a[j] != a[i]){
                i = j - 1;
                break;
            }
            if(j - i + 1 >= n/2){
                cout << "-1\n";
                return;
            }
        }
    }
 
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int d = abs(a[j] - a[i]);
            for(int k=1;k<=sqrt(d);k++){
                if(d % k != 0) continue;
                if(judge(k)) ans = max(ans, k);
                if(judge(d/k)) ans = max(ans, d/k);
            }
        }
    }
    cout << ans << '\n';
}

E. Gardener and Tree

题意：有一棵树，每次操作可以删除所有的叶子节点（度数为1的节点），问几次操作后树为空

很明显拓扑删一遍即可，队友说也可以换根dp，改天了解一下（

vector<int> vp[maxn];
int du[maxn];
 
void solve(){
    int n, k;
    cin >> n >> k;
    for(int i=1;i<=n;i++) vp[i].clear(), du[i] = 0;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        vp[x].push_back(y);
        vp[y].push_back(x);
        du[x]++;
        du[y]++;
    }
    if(n == 1){
        cout << "0\n";
        return;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(du[i] == 1){
            q.push(i);
        }
    }
    for(int i=1;i<=k;i++){
        vector<int> tmp;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            du[u]--;
            n--;
            for(auto &j:vp[u]){
                if(du[j] > 0){
                    du[j]--;
                    if(du[j] == 1) tmp.push_back(j);
                }
            }
        }
        for(auto &x:tmp) q.push(x);
    }
    cout << n << '\n';
}

F. Red-Black Number

题意：红黑数 给一个可能含前导0的数字，要求对将每一位染色成红或者黑，在满足红色数字拼起来后可以被 $A$ 整除，黑色数字拼起来可以被 $B$ 整除的条件下，涂红和涂黑的数量差最小，输出涂色方案。

乍一看有点不好下手，一看数据范围 $n\le40,A,B\le40$，考虑暴力dp

设 $dp[i][r][m_1][m_2]$ 表示前 $i$ 位中，涂了 $r$ 个红色，红色部分模 $A$ 结果为 $m_1$，黑色部分模 $B$ 结果为 $m_2$ 时，选择的红色位置（状态压缩，保存方案）

这样设置状态的原因在于，在后方添加一个新数位时（比如涂成红色），$m_1$ 可以转移到 $(m_1\times10+a[i+1])\mod A$，转移很方便，模结果为0即为合法答案

想到了状态后，转移不难写

 int n, mda, mdb;
string a;
ll dp[50][50][50][50];//pos, rednum, redres, blkres = respos
 
void solve(){
    cin >> n >> mda >> mdb;
    cin >> a; a = "s" + a;
 
    memset(dp, -1, sizeof(dp));
    dp[0][0][0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int r = 0; r <= i; r++){
            for(int rs = 0; rs < mda; rs++){
                for(int rb = 0; rb < mdb; rb++){
                    ll t = dp[i][r][rs][rb];
                    if(t >= 0){
                        dp[i+1][r][rs][(rb * 10 + a[i+1] - '0')%mdb] = t;
                        dp[i+1][r+1][(rs * 10 + a[i+1] - '0')%mda][rb] = t | (1ll << i);
                    }
                }
            }
        }
    }
    int ans = 1e9;
    ll redp;
    for(int r = n-1; r >= 1; r--){
        if(dp[n][r][0][0] >= 0){
            if(ans > abs(2 * r - n)){
                ans = abs(2 * r - n);
                redp = dp[n][r][0][0];
            }
        }
    }
    if(ans >= n) cout << "-1\n";
    else{
        for(int i=1;i<=n;i++){
            if(redp & (1ll << (i-1))) cout << "R";
            else cout << "B";
        }
        cout << '\n';
    }
}

G. Changing Brackets

题意：有一个括号序列，包含 ( ) [ ] 四种括号，可以免费将括号翻转，或花费1块把圆括号变方括号（或者反过来），有多个询问，每次询问 $[l,r]$ ，需要最少花费多少使这个区间的括号合法，保证 $[l,r]$ 长度为偶数

一道纯思维题，考虑怎么样的一个括号序列才合法：我们不断将序列中相邻的同类括号删掉，两边的拼在一起，不断这样删去，最后可能全删了（即这个括号序合法），或者剩下形如 ( [ ( [ 这样交替出现的括号，剩下的长度的一半就是最小的花费

一个很容易理解（但可能比较难想到）的性质：圆括号我们直接不管了，剩下的方括号要么全在奇数位，要么全在偶数位

而这个序列中被删掉的那些方括号，也一定是一奇一偶一起删的

所以区间 $[l,r]$ 的答案就是区间中 奇数位方括号数量 - 偶数位方括号数量 再取个绝对值。前缀和搞一下就好了

感觉很不错的一个题，思维略有难度，但正解很容易让人接受

int sum[maxn];
 
void solve(){
    string s;
    cin >> s;
    int n = s.size();
    s = "0" + s;
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1];
        if(s[i] == '[' || s[i] == ']'){
            if(i%2 == 1) sum[i]++;
            else sum[i]--;
        }
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++){
        int l, r;
        cin >> l >> r;
        cout << abs(sum[r] - sum[l-1]) << '\n';
    }
 
}