Codeforces Round #599 (Div. 1)

sto God Song orz

Being teached again

¶ A - Tile Painting

打表找规律

int clr[1000000], _n;

void dfs(int x){
    int n = _n;
    for(int i = 2; i <= n; ++i){
        if (n%i == 0){
            if (x-i >= 1 && !clr[x-i]){
                clr[x-i] = clr[x];
                dfs(x-i);
            }
            if (x+i <= n && !clr[x+i]){
                clr[x+i] = clr[x];
                dfs(x+i);
            }
        }
    }
}

int solve(int n){
    std::memset(clr, 0, sizeof(clr)); _n = n;
    int ret=0;
    for(int i = 1; i <= n; ++i){
        if (!clr[i]){
            clr[i] = ++ret;
            dfs(i);
        }
    }
    // rep(i,1,n) cerr << clr[i] << ' '; cerr <<endl;
    return ret;
}

1. $n=p^k, k\in\N^*$ ，$p$ 为素数， $ans=p$
2. $ans=1$

¶ B - 0-1 MST

pre[x] 是代表 pre[x]...x 的全被遍历到，并且 pre[x] 尽量小

然后 random_shuffle 就过了

我也不知道为什么

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;
 
const int N = 1e5+10;
 
int clr[N], pre[N];
std::vector<int> g[N];
  
void dfs(int u){
    // cerr << "node " << u << endl;
    std::vector<int> q;
    for(int i = 1; i < g[u].size(); ++i){
        int st = g[u][i-1] + 1, ed = g[u][i]-1;
        
        if(pre[ed] < st) continue;
        else if (pre[ed] == st) ed = st;
        rep(v, st, ed) pre[v] = pre[st];
        rep(v, st, ed)
            if (!clr[v]){
                clr[v] = 1;
                q.push_back(v);
            }
    }
    std::random_shuffle(q.begin(), q.end());
    for(auto x : q) dfs(x);
}
 
int main() {
// #ifdef LOCAL
    // freopen("in3.txt", "r", stdin);
// #endif
    std::ios::sync_with_stdio(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    rep(i, 0, n+1) pre[i] = i;
    rep(i, 1, m){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rep(i, 1, n){
        g[i].push_back(0), g[i].push_back(n+1);
        std::sort(g[i].begin(), g[i].end());
    }
    int ret = 0;
    rep(i, 1, n){
        if (!clr[i]){
            // cerr << "++ " << i << endl;
            clr[i] = 1; ++ret; dfs(i);
        }
    }
    cout << ret-1;
    return 0;
}

¶ C - Sum Balance

$k$ 这么小肯定是指数算法 然后 n 太大不会做

考虑一个数被拿出来一定会有另一个数被替换，而另一个数是确定的

把数看成节点，每个节点有一条或没有出边

于是就转换成了一个图论问题

当图上有环的时候，并且这些数属于不同的盒子时，这几个盒子就能一起选上

于是变成了一个内向基环树找环的问题，加上一个人人都会的状压

#include <bits/stdc++.h>
#define R(i, r) for (int i = 0; i < (r); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;
 
const int K = 15, N = 5010;
 
int n[K]; ll a[K][N], sig[K];
std::map<ll, pii> s;
pii g[K][N]; int clr[K][N];
int f[1<<K], from[1<<K];
pii plan[1<<K]; int origin[1<<K]; pii out[K];
 
void dfs(int state){
    if (origin[state]){
        int x = plan[state].first, y = plan[state].second;
        pii n;
        do {
            n = g[x][y];
            out[n.first] = {a[n.first][n.second], x};
            x = n.first, y = n.second;
        } while(x != plan[state].first);
    } else {
        dfs(from[state]);
        dfs(state^from[state]);
    }
}
 
int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(0); cout.tie(0);
    int k; cin >> k; ll avg = 0;
    R(i, k){
        cin >> n[i];
        R(j, n[i]){
            cin >> a[i][j];
            sig[i] += a[i][j];
            s[a[i][j]] = {i,j};
        }
        avg += sig[i];
    }
    if (avg % k != 0){ cout << "No"; return 0; }
    avg /= k;
    R(i, k) R(j, n[i]){
        ll x = avg - sig[i] + a[i][j];
        if (s.count(x)) g[i][j] = s[x];
        else g[i][j].first = -1;
    }
    int x, y, state, flag; pii np; int cnt = 0;
    R(i, k) R(j, n[i]){
        if (clr[i][j]) continue;
        x = i, y = j;
        clr[x][y] = ++cnt;
        while(g[x][y].first != -1){
            np = g[x][y]; x = np.first, y = np.second;
            if (clr[x][y] == cnt){
                state = 0, flag = 1;
                int ox = x, oy = y;
                do {
                    if (state&(1<<x)) { flag = 0; break; }
                    state |= (1<<x);
                    np = g[x][y];
                    x = np.first, y = np.second;
                } while(x != ox || y != oy);
                if (flag) f[state] = origin[state] = 1, plan[state] = {x, y};
                break;
            } else if (clr[x][y] != 0) break;
            clr[x][y] = cnt;
        }
    }
    f[0] = 1;
    for(int i = 1; i < (1<<k); ++i){
        for(int j = i; j && !f[i]; j = ((j-1)&i)){
            if (f[j] && f[i^j]){
                f[i] = 1;
                from[i] = j;
            }
        }
    }
    if(!f[(1<<k)-1]){ cout << "No"; return 0; }
    cout << "Yes\n";
    dfs((1<<k)-1);
    R(i, k){
        cout << out[i].first << ' ' << out[i].second+1 << endl;
    }
    return 0;
}

剩下的不会了 QAQ