Codeforces Round #601 (Div. 1)
A
容易发现最小的差肯定是 (1)，即有一些块包含 (x) 个，一些块有 (x+1) 个。关键在于保证连通。只要按照“蛇形”拓展即可：一行一行走，第一行从左往右，第二行从右往左，第三行...
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 105;
int n, m, k, p[100], vis[N][N]; char a[N][N], b[N][N];
signed main() {
int T; read (T); int m = 0;
for (int i = '0'; i <= '9'; ++i) p[++m] = i;
for (int i = 'a'; i <= 'z'; ++i) p[++m] = i;
for (int i = 'A'; i <= 'Z'; ++i) p[++m] = i;
while (T--) {
read (n), read (m), read (k);
for (int i = 1; i <= n; ++i) scanf ("%s", a[i] + 1);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cnt += a[i][j] == 'R', vis[i][j] = 0;
int num = cnt / k, s = cnt - k * num;
int x = 1, y = 1, now = 0, f = 1, id = 1;
while (id <= s) {
// printf ("%d %d %d
", x, y, id);
now += a[x][y] == 'R', b[x][y] = p[id], vis[x][y] = 1;
if (y + f <= m && y + f >= 1) y += f;
else ++x, f = -f; if (x > n) break;
if (now == num + 1) now = 0, ++id;
}
while (id <= k) {
// printf ("%d %d %d
", x, y, id);
now += a[x][y] == 'R', b[x][y] = p[id], vis[x][y] = 1;
if (y + f <= m && y + f >= 1) y += f;
else ++x, f = -f; if (x > n) break;
if (now == num) now = 0, ++id;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) if (!vis[i][j]) b[i][j] = p[id - 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) putchar (b[i][j]); putchar ('
');
}
}
return 0;
}
B
对于 easy version，枚举约数 (p)，由于每个位置不超过 (1)，一定是连续 (p) 个 (1) 拼在一起。然后就成了“数轴上有一些村庄，建车站使距离和最短”的问题
对于 hard，首先可以发现 (p) 只需考虑质数，否则不会更优。为了简化问题，设 (b_i=sumlimits_{j=1}^{i}a_i)。把 (i) 移到 (i+1) 就是 (b_i) 减 (1)，移到 (i-1) 就是 (b_{i-1}) 加 (1)。其实就是可以任选一个 (iin[1,n-1]) 加一减一。(res=sum min(b_i\%p,p-b_i\%p))
质因数没几个（(leq12)），所以很快
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 1e6 + 5;
int n, a[N], s[N], p[N], in[N];
signed main() {
read (n);
for (int i = 1; i <= n; ++i) read (a[i]);
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
if (s[n] == 1) return puts ("-1"), 0;
int res = 5e18, sum = s[n];
for (int i = 2; i * i <= s[n]; ++i) {
if (!in[i]) {
if (sum % i == 0) {
while (sum % i == 0) sum /= i; int tmp = 0;
for (int j = 1; j <= n; ++j) tmp += min (s[j] % i, i - s[j] % i);
res = min (res, tmp);
}
for (int j = i; j * j <= s[n]; j += i) in[j] = 1;
}
}
if (sum > 1) {
int tmp = 0;
for (int j = 1; j <= n; ++j) tmp += min (s[j] % sum, sum - s[j] % sum);
res = min (res, tmp);
}
return printf ("%lld
", res), 0;
}
C
先通过 (1,2) 两点确定的直线把点分成 (A,B) 两部分，这一步可以通过 (n-2) 次 (2) 类询问 ((1,2,x)) 完成
然后对于每个点进行 (1) 类查询 ((1,2,x))，由此可以得出每个点到直线 (1,2) 的距离。记最远点为 (u)，再通过 (2) 类询问 ((1,u,x)) 可以把 (A) 中的点再次分为 (A_1,A_2) 两部分 ((B) 同)
然后对于 (A_1,A_2) 点的顺序分别按照点到线的距离降序、升序排列。需要注意的是最远点可能有两个
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1024;
int n, h[N]; vector<int> a, b, res;
void flush () { putchar ('
'); fflush (stdout); }
vector<pair<int, int> > l, r;
#define fi first
#define se second
#define pb push_back
signed main() {
cin >> n;
for (int i = 3, x; i <= n; ++i) {
printf ("2 1 2 %lld", i);
flush (); cin >> x;
x == -1 ? a.pb (i) : b.pb (i);
}
int u = 0, d = 0, v = 0;
for (int i : a) {
printf ("1 1 2 %lld", i);
flush (); int x; cin >> x; h[i] = x;
if (x > d) d = x, u = i, v = 0;
else if (x == d) v = i;
}
for (int i : a) {
if (i == u || i == v) continue;
printf ("2 1 %lld %lld", u, i);
flush (); int x; cin >> x;
if (x == 1) r.pb ({h[i], i});
else l.pb ({h[i], i});
}
res.pb (1);
sort (l.begin(), l.end());
for (auto i : l) res.pb (i.se);
if (!v && u) res.pb (u);
if (u && v) {
printf ("2 1 %lld %lld", u, v);
flush (); int x; cin >> x;
if (x < 0) swap (u, v);
res.pb (u), res.pb (v);
}
sort (r.begin(), r.end());
reverse (r.begin(), r.end());
for (auto i : r) res.pb (i.se);
res.pb (2);
////////////////////////////
u = 0, d = 0, v = 0; l.clear(), r.clear();
for (int i : b) {
printf ("1 1 2 %lld", i);
flush (); int x; cin >> x; h[i] = x;
if (x > d) d = x, u = i, v = 0;
else if (x == d) v = i;
}
for (int i : b) {
if (i == u || i == v) continue;
printf ("2 1 %lld %lld", u, i);
flush (); int x; cin >> x;
if (x == 1) l.pb ({h[i], i});
else r.pb ({h[i], i});
}
sort (r.begin(), r.end());
for (auto i : r) res.pb (i.se);
if (!v && u) res.pb (u);
if (u && v){
printf ("2 1 %lld %lld", u, v);
flush (); int x; cin >> x;
if (x < 0) swap (u, v);
res.pb (u), res.pb (v);
}
sort (l.begin(), l.end());
reverse (l.begin(), l.end());
for (auto i : l) res.pb (i.se);
printf ("0 ");
for (int i : res) printf ("%lld ", i);
}
D
操作 (x)，此时以 (x) 为根，(y) 被修改的概率和 (y) 在 (x) 的哪个儿子的子树中有关，只要 (r) 不选在这棵子树中 (y) 就被修改。容易发现朴素算法的复杂度是操作节点的度数之和
1、对于度数分类处理，(gesqrt{n}) 的打标记，查询的时候再算，(leqsqrt{n}) 的直接暴力修改，根据实现方式不同可以做到 (O(nsqrt{n})——O(nsqrt{n}log{n}))
2、轻重链剖分，对于 (x) 的重儿子的子树和外子树暴力修改，轻儿子不管，查询的时候跳重链累计答案（两条重链相接处）。每次暴力修改 (2) 个区间，(O(log{n}))。每次查询的时候重链最多 (log n) 条，概率 (O(1)) 计算，复杂度也为 (O(log n))。总复杂度 (O(nlog n))
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 150010, M = N << 1, mod = 998244353;
int qpow (int x, int y) {
int t = 1;
while (y) {
if (y & 1) t = t * x % mod;
x = x * x % mod, y >>= 1;
}
return t;
}
int n, q, cnt, inv, h[N], to[M], nxt[M];
void add (int u, int v) {
to[++cnt] = v, nxt[cnt] = h[u], h[u] = cnt;
}
#define up(x, y) ((x += y) >= mod && (x -= mod))
struct tree {
int c[N];
void add (int x, int v) {
for (++x; x <= n + 1; x += (x & -x)) up (c[x], v);
}
int ask (int x) {
int s = 0; for (++x; x; x -= (x & -x)) up (s, c[x]); return s;
}
void update (int l, int r, int v) { add (l, v), add (r + 1, mod - v); }
} t;
struct solve {
int cnt, d[N], son[N], sz[N], dfn[N], fa[N], tp[N], ed[N], num[N];
void dfs (int u) {
sz[u] = 1;
for (int i = h[u], v; i; i = nxt[i]) {
if ((v = to[i]) == fa[u]) continue;
fa[v] = u, d[v] = d[u] + 1, dfs (v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs (int u, int topp) {
tp[u] = topp, dfn[u] = ++cnt;
if (son[u]) dfs (son[u], topp);
for (int i = h[u], v; i; i = nxt[i])
if (!dfn[v = to[i]]) dfs (v, v); ed[u] = cnt;
}
void prework () { dfs (1); dfs (1, 1); }
void modify (int x, int c) {
int l = 1, r = dfn[x] - 1, k = c * inv % mod * sz[x] % mod;
if (l <= r) t.update (l, r, k);
l = ed[x] + 1, r = n;
if (l <= r) t.update (l, r, k);
if (son[x]) {
int y = son[x];
l = dfn[y], r = ed[y], k = c * inv % mod * (n - sz[y]) % mod;
if (l <= r) t.update (l, r, k);
}
up (num[x], c);
}
int ask (int x) {
int res = num[x]; up (res, t.ask (dfn[x]));
while (x) {
int a = tp[x], b = fa[tp[x]]; x = b;
(res += num[b] * inv % mod * (n - sz[a])) %= mod;
}
return res;
}
} qwq;
signed main() {
read (n), read (q); inv = qpow (n, mod - 2);
for (int i = 1, u, v; i < n; ++i)
read (u), read (v), add (u, v), add (v, u);
qwq.prework (); int o, x, c;
for (int i = 1; i <= q; ++i) {
read (o), read (x);
if (o == 1) read (c), qwq.modify (x, c);
else printf ("%lld
", qwq.ask (x));
}
return 0;
}
E
如果没有限制，(res=prod s_i)，(s_i) 为 (i) 节点的度数。
一个限制意味着什么？提取出 (path(x,a_x)) 这条链，有三种限制
1、(x) 的第一条删除的边固定。
2、(a_x) 的最后一条删除边固定。
3、链上的边删除有依赖关系（可传递）。即删除完一条边后，和公共点相连的边中必须立刻删除链上的下一条。
注意到有依赖关系的边都有一个公共点。
把和某个点相邻的边提出来，把这些边看成节点，每个依赖关系连一条有向边，构成一张“新图”（下面提到“新链”是“新图”中的链，“链”指原图的链）
可以找到一些无解的情况：
1、某个 (x) 在 (a) 中出现不止一次
2、和某条边有直接依赖关系的边不止一条或依赖关系成环（In other words，“新图”中有节点出度或入度 (ge 2) 或 "新图"中有环）
3、某个点的第一条边和最后一条边固定且在同一条“新链”上，但还有其他“新链”存在
4、如果链 (path(x,a_x)) 的长度之和 (ge 2n-1)，一定无解，因为每删除一条边 (i) 节点和数字 (i) 的距离之和 (+2)。所以可以暴力判断无解而保证复杂度。
如果有解，答案就是 (prod c_i!)，(c_i) 为“新链”数量。
语文水平太低，说的很模糊，但又懒得画图，不如↓
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 5e5 + 5, mod = 1e9 + 7;
int n; vector<int> g[N];
#define int long long
void fail () { puts ("0"); exit (0); }
int sum, d[N], fa[N], nxt[N], pre[N], vis[N];
void dfs (int u, int la) {
d[u] = d[la] + 1, fa[u] = la;
for (int v : g[u]) if (v != la) dfs (v, u);
}
vector<int> vx, vy;
#define pb push_back
void lca (int x, int y) {
vx.clear(), vy.clear(); vx.pb (n + 1), vy.pb (n + 2);
while (d[x] > d[y]) ++sum, vx.pb (x), x = fa[x];
while (d[x] < d[y]) ++sum, vy.pb (y), y = fa[y];
while (x != y) sum += 2, vx.pb (x), vy.pb (y), x = fa[x], y = fa[y];
vx.pb (x);
}
struct e { int x, y; } ; vector<e> a[N];
void work (int x, int y) {
lca (x, y); if (sum > 2 * n - 2) fail ();
vx.insert (vx.end(), vy.rbegin(), vy.rend()); int sx = (int)vx.size();
for (int i = 1; i + 1 < sx; ++i) a[vx[i]].pb ({vx[i - 1], vx[i + 1]});
}
signed main() {
read (n);
for (int i = 1, u, v; i < n; ++i)
read (u), read (v), g[u].pb (v), g[v].pb (u);
for (int i = 1; i <= n; ++i)
g[i].pb (n + 1), g[i].pb (n + 2);
if (n == 1) return puts ("1"), 0;
dfs (1, 1); int res = 1;
for (int i = 1, x; i <= n; ++i) { read (x); if (x) work (i, x); }
for (int i = 1; i <= n; ++i) {
for (e p : a[i]) {
int x = p.x, y = p.y;
if (nxt[x] && nxt[x] != y) fail ();
if (pre[y] && pre[y] != x) fail ();
nxt[x] = y, pre[y] = x;
}
for (int x : g[i]) if (!vis[x]) {
vis[x] = 1; int now = nxt[x];
while (now) {
if (now == x) fail ();
if (vis[now]) break; vis[now] = 1, now = nxt[now];
}
}
if (nxt[n + 1]) {
int now = n + 1, c = 1;
while (now) {
if (now == n + 2) break; ++c, now = nxt[now];
}
if (now == n + 2 && c < g[i].size()) fail ();
}
int num = 0;
for (int x : g[i]) num += (x <= n && !pre[x]);
if (pre[n + 2]) --num;
for (int j = 1; j <= num; ++j) res = res * j % mod;
for (int x : g[i]) nxt[x] = pre[x] = vis[x] = 0;
}
printf ("%lld
", res);
}