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=pk,kNn=p^k, k\in\N^*pp 为素数, ans=pans=p
  2. ans=1ans=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

kk 这么小肯定是指数算法 然后 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