2023.11.16
Codeforces - 1408F - Two Different
(-3)
构造题，显然有一种想法可以在约 \(O(p2^p)\) 的复杂度内使一个长为 \(2^p\) 的数列变为全部相同。那么令 \(q = \lfloor \log_2n\rfloor\)，可以对 \([1,2^q],[n-2^q+1,n]\) 各做一次操作，刚好可过。
#include <bits/stdc++.h>
using namespace std;
int Q;
int p;
vector < pair < int , int > > R;
void Solve (int s, int wp){
for (int i = 1;i <= wp;++ i)
for (int j = s;j <= s + (1 << wp) - 1;j += (1 << i))
for (int k = j;k < j + (1 << (i - 1));++ k)
R.push_back (make_pair (k, k + (1 << (i - 1))));
}
int main (){
scanf ("%d", &Q);
p = (int) log2 (Q);
Solve (1, p);
if (Q - (1 << p) != 0)
Solve (Q - (1 << p) + 1, p);
printf ("%d\n", (int) R.size ());
for (int i = 0;i < (int) R.size ();++ i)
printf ("%d %d\n", R[i].first, R[i].second);
return 0;
}
2023.11.17
Luogu - P2664 - 树上游戏
(0)
好玩。随机跳到的（你怎么知道我最近在学点分治）。正解是点分治。但是可以 \(O(n)\) 做。因为是不同的颜色的计数，所以一个颜色对于一个点的贡献是（经过这种颜色 - 不经过这种颜色）的以这个点为起点的路径数。
然后会发现把相同颜色的点标出，可以把原树分为若干子树，子树到子树内的路径不含这种颜色，否则包含。然后对于不同颜色差分一下即可。
哈哈，但是没想好就开写，差分改了两次。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, c[100005], sz[100005], cs[100005], tw[100005], fa[100005];
int firs[100005], nex[200005], to[200005], tot;
int ton[100005], cr;
int vis[100005], ce[100005];
stack < int > st[100005];
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
void Init (int u, int father){
tw[father] = u;
fa[u] = st[c[u]].top ();
cs[u] = tw[fa[u]];
st[c[u]].push (u);
sz[u] = 1;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
Init (v, u);
sz[u] += sz[v];
}
st[c[u]].pop ();
if (cs[u] == 1 && u != 1)
vis[c[u]] -= sz[u], ce[1] -= sz[u];
else
ce[cs[u]] -= sz[u];
}
void Solve (int u, int father){
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
Solve (v, u);
}
if (u == 1)
return ;
if (cs[u] == 1)
ce[u] -= sz[1] + vis[c[u]];
else
ce[u] -= ce[cs[u]];
}
void push_down (int u, int father){
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
ce[v] += ce[u];
push_down (v, u);
}
}
signed main (){
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i){
scanf ("%lld", &c[i]);
if (ton[c[i]] == 0)
++ cr;
++ ton[c[i]];
}
for (int i = 1, u, v;i < n;++ i){
scanf ("%lld%lld", &u, &v);
Add (u, v);
Add (v, u);
}
for (int i = 0;i <= 1e5;++ i)
st[i].push (n + 1);
sz[n + 1] = n + 1;
c[n + 1] = 0;
Init (1, n + 1);
ce[1] += cr * sz[1];
for (int i = 2;i <= n;++ i)
ce[i] += sz[i];
Solve (1, n + 1);
push_down (1, n + 1);
for (int i = 1;i <= n;++ i)
printf ("%lld\n", n * cr - ce[i]);
return 0;
}
Luogu - P4819 - [中山市选] 杀人游戏
(-4)
很有意思的一道题，然而不难。
显然，若 \(x\) 认识 \(y\) ，则连边 \(x \to y\)。
如果通过询问确定了一个点，那么这个点可以到达的所有点都可以求得。
连通性相关，考虑缩点为 DAG。
这时我们有一些（缩完后的）点入度为 \(0\)，然而如果我们需要确定所有点的信息，这些点必须在没有安全保障（即在没有确认其信息时）被访问，假设一共 \(t\) 个这样的点，那么求得所有信息且保证安全的概率就是 \(1-\frac{t}{n}\)。
然而这题说了必然有一个人是杀手，即我们加入确定了 \(n-1\) 的点的信息，则剩下的一个点必然可知其信息，所以如果存在一个（缩完后的）入度为 \(0\) 的点自身大小为 \(1\)，且可以到达的点都可以被其他入度为 \(0\) 的点到达，则有更优的策略，使概率为 \(1-\frac{t-1}{n}\)。
#include <bits/stdc++.h>
using namespace std;
map < pair < int , int > , bool > ht;
const int N = 1e5 + 5, M = 3e5 + 5;
int n, m, cntc;
int firs[N], nex[M], to[M], tot;
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
int head[N], tur[M], fw[M], cnt;
int rd[N], f[N];
void Connect (int u, int v){
++ cnt;
tur[cnt] = head[u];
head[u] = cnt;
fw[cnt] = v;
}
int idx, dfn[N], low[N], sta[N], top;
bool ins[N];
int sz[N], cnt_scc, bel[N], df[N];
void Tarjan (int u){
if (dfn[u] > 0)
return ;
low[u] = dfn[u] = ++ idx;
ins[u] = true;
sta[++ top] = u;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (dfn[v] == 0){
Tarjan (v);
low[u] = min (low[u], low[v]);
} else
if (ins[v])
low[u] = min (low[u], dfn[v]);
}
if (low[u] == dfn[u]){
int v;
++ cnt_scc;
do {
v = sta[top --];
++ sz[cnt_scc];
bel[v] = cnt_scc;
ins[v] = false;
} while (u != v);
}
}
int main (){
scanf ("%d%d", &n, &m);
for (int i = 1, u, v;i <= m;++ i){
scanf ("%d%d", &u, &v);
Add (u, v);
}
for (int i = 1;i <= n;++ i)
Tarjan (i);
for (int u = 1;u <= n;++ u)
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (bel[u] != bel[v] && ht[make_pair (bel[u], bel[v])] != true){
Connect (bel[u], bel[v]);
ht[make_pair (bel[u], bel[v])] = true;
++ rd[bel[v]];
}
}
for (int i = 1;i <= cnt_scc;++ i)
if (rd[i] == 0)
++ f[i], ++ cntc;
for (int u = cnt_scc;u >= 1;-- u)
for (int e = head[u], v;e;e = tur[e]){
v = fw[e];
f[v] += f[u];
}
for (int u = 1;u <= cnt_scc;++ u)
if (rd[u] == 0 && sz[u] == 1){
bool tag = true;
for (int e = head[u], v;e;e = tur[e]){
v = fw[e];
tag = tag && f[v] > 1;
}
if (tag){
-- cntc;
break;
}
}
printf ("%0.6lf\n", 1.0 - 1.0 * cntc / n);
return 0;
}
Luogu - P6965 - [NEERC2016] Binary Code
(-3)
好玩。随便找点图论题做做还能找到这样好玩的题，幸运。
首先应该很容易想到在 trie 树上 Insert，连边跑 2-SAT。然后以为很简单直接开写，然后发现时间可能会假。
抱着 \(01\) 串 + 问号需要自己填 + NEERC 良心出题人 的期盼继续写，然后过了，最慢的点跑了 150ms。
正解应该在 trie 树上面做状态，再搞前缀优化。
但是发现有题解证明直接暴力建图是对的。嘿嘿。
题解这样证明：
先设字符总长为 \(L\)，由题目 \(O(n)=O(L)\)。
对于 trie 树上一个点，设深度为 \(d\)。所以这个点最多同时是 \(O(\min(\frac{L}{d}, d))\) 个不定串的可能答案。
-
因为当 \(d<\sqrt{L}\) 时不同位置的问号总共只有 \(O(d)\) 个，所以数量是 \(O(d)\)。
-
因为当 \(d\ge\sqrt{L}\) 时最多只有 \(O(\frac{L}{d})\) 个满足的串。
到这里也不能有力地说明什么，但题解到这里就完了。
所以我来补充一下。
设一个点被作为 \(\alpha\) 个不定串的可能答案，根据四点：
- \(O(\sum \alpha) = O(n)\)
- \(O(\alpha) = O(\min(\frac{L}{d}, d))\)
- \(O(\sum d\alpha ) = O(L)\)
- \(O(n)=O(L)\)
可以推得边的数量为 \(O(\sum\alpha^2)=O(L)\)。
可能还需要考虑点在同一链上的情况，然而因为随着长度的递增，后面的串对前面的串的遍历会极大地下降。因为是求和，所以能知道单点复杂度仍然维持在 \(O(\alpha^2)\)，只是增加了大概 \(2\) 倍左右的常数。
但上面的证明不严谨，还需要去重才能满足（题解也没提）。
而去重的性质是如果有超过 \(1\) 个相同的确定串或超过 \(2\) 个相同的不定串，则答案为 NO。
而我正好写了去重，也就直接过了。幸运。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table < string , int > ht;
int n, len[500005], pos[500005];
string s[500005];
char c[500005];
bool tag[2000005];
int firs[2000005], nex[2000005], to[2000005], tot;
void Add (int u, int v){
// printf ("%d %d\n", u, v);
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
int id (int i, int p){
return i + p * n;
}
int ny (int i){
if (i > n)
return i - n;
return i + n;
}
bool cmp (int i, int j){
return len[i] < len[j];
}
int cntt;
struct trie {
int to[2];
bool nt;
vector < int > nf;
trie (){
to[0] = to[1] = - 1;
nt = false;
}
} tr[1500005];
void Insert (int u, int i, int p, int vc){
if (! tag[vc] && tr[u].nt){
puts ("NO");
exit (0);
}
for (int t = 0;t < (int) tr[u].nf.size ();++ t){
if (tag[vc])
Add (tr[u].nf[t], ny (vc));
if (tag[tr[u].nf[t]])
Add (vc, ny (tr[u].nf[t]));
}
if (p == (int) s[i].size ()){
tr[u].nf.push_back (vc);
tr[u].nt = tr[u].nt || (! tag[vc]);
return ;
}
int fw = s[i][p] - '0';
if (tr[u].to[fw] == - 1)
tr[u].to[fw] = ++ cntt;
Insert (tr[u].to[fw], i, p + 1, vc);
}
int idx, dfn[1000005], low[1000005], sta[1000005], top;
int cnt_scc, bel[1000005];
bool ins[1000005];
void Tarjan (int u){
if (dfn[u] > 0)
return ;
++ idx;
dfn[u] = low[u] = idx;
sta[++ top] = u;
ins[u] = true;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (dfn[v] == 0){
Tarjan (v);
low[u] = min (low[u], low[v]);
} else
if (ins[v])
low[u] = min (low[u], dfn[v]);
}
if (dfn[u] == low[u]){
++ cnt_scc;
int v;
do {
v = sta[top --];
bel[v] = cnt_scc;
ins[v] = false;
} while (v != u);
}
}
int main (){
scanf ("%d", &n);
for (int i = 1;i <= n;++ i){
cin >> s[i];
for (int j = 0;j < (int) s[i].size ();++ j)
if (s[i][j] == '?')
tag[id (i, 0)] = tag[id (i, 1)] = true;
if (ht[s[i]] > (int) tag[i]){
puts ("NO");
return 0;
} else
++ ht[s[i]];
len[i] = (int) s[i].size ();
pos[i] = i;
}
sort (pos + 1, pos + n + 1, cmp);
for (int i = 1;i <= n;++ i){
if (tag[pos[i]]){
int pu = 0;
for (int j = 0;j < (int) s[pos[i]].size ();++ j)
if (s[pos[i]][j] == '?'){
pu = j;
break;
}
s[pos[i]][pu] = '0';
Insert (0, pos[i], 0, id (pos[i], 0));
s[pos[i]][pu] = '1';
Insert (0, pos[i], 0, id (pos[i], 1));
s[pos[i]][pu] = '?';
} else {
Insert (0, pos[i], 0, id (pos[i], 0));
Add (2 * n + 1, id (pos[i], 0));
}
}
for (int i = 1;i <= 2 * n;++ i)
if (tag[i])
Add (i, 2 * n + 1);
tag[2 * n + 1] = true;
for (int i = 1;i <= 2 * n + 1;++ i)
if (tag[i] || i <= n)
Tarjan (i);
for (int i = 1;i <= n;++ i)
if (tag[i] && bel[i] == bel[ny (i)]){
puts ("NO");
return 0;
} else
if (bel[i] > bel[ny (i)] && tag[i])
c[i] = '1';
else if (tag[i])
c[i] = '0';
puts ("YES");
for (int i = 1;i <= n;++ i){
for (int j = 0;j < (int) s[i].size ();++ j){
if (s[i][j] == '?')
printf ("%c", c[i]);
else
printf ("%c", s[i][j]);
}
puts ("");
}
return 0;
}
2023.11.20
Luogu - P1477 - [NOI2008] 假面舞会
(-5)
毕竟是图论娱乐题，还是简单且有趣的。
会发现一个连通块内一个点确定，则整个块确定。然而可能会出现一个人存在多个编号的的情况，这时根据差作 \(\gcd\)。
然而因为差作 \(\gcd\)，所以不需要因为编号的变化而重新更新一个点指向的节点。所以遍历图直接就是 \(O(n)\) 的。
注意最大的点数不一定是 \(n\)，而是每部分连通块极差之和与 \(n\) 的更小值。没注意到会挂 \(20\)~\(50\) 分。
#include <bits/stdc++.h>
using namespace std;
int n, m, K;
int tim[100005], lim;
int firs[100005], nex[2000005], to[2000005], w[2000005], tot;
int tmax, tmin;
bool vis[100005];
int gcd (int a, int b){
if (b == 0)
return a;
return gcd (b, a % b);
}
void Add (int u, int v, int p){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
w[tot] = p;
}
void Solve (int u){
vis[u] = true;
tmax = max (tmax, tim[u]);
tmin = min (tmin, tim[u]);
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (vis[v]){
if (tim[v] != tim[u] + w[e]){
if (K == 0)
K = abs (tim[u] + w[e] - tim[v]);
else
K = gcd (K, abs (tim[u] + w[e] - tim[v]));
}
} else {
tim[v] = tim[u] + w[e];
Solve (v);
}
}
}
int main (){
scanf ("%d%d", &n, &m);
for (int i = 1, u, v;i <= m;++ i){
scanf ("%d%d", &u, &v);
Add (u, v, 1);
Add (v, u, - 1);
}
for (int i = 1;i <= n;++ i)
if (! vis[i]){
tmax = tmin = 0;
Solve (i);
lim += tmax - tmin + 1;
}
int Ansmin = n + 1, Ansmax = 0;
int I = min (lim, n);
if (K > 0)
I = n;
for (int i = 3;i <= I;++ i)
if (K % i == 0){
Ansmin = min (Ansmin, i);
Ansmax = max (Ansmax, i);
}
if (Ansmax == 0)
puts ("-1 -1");
else
printf ("%d %d\n", Ansmax, Ansmin);
return 0;
}
2023.11.21
Codeforces - 36E - Two Paths
(-1)
欧拉路的优秀题。如果只处于一个连通块内相当于是只要满足恰好有 \(0,2,4\) 个奇数度数的点即可。四个奇数点时，可以把任意两个奇数点连一条虚边跑欧拉路，再断开即可。
两个连通块则必须各满足存在一条欧拉路；有大于两个连通块时不成立。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int firs[10005], nex[20005], to[20005], id[20005], tot, deg[10005];
int cur[10005], sta[10005], top;
int fa[10005], st[10005], ct, ld[10005];
bool ext[10005], vis[10005];
map < pair < int , int > , stack < int > > mp;
vector < int > Ans[2];
int find (int v){
if (fa[v] == v)
return v;
return fa[v] = find (fa[v]);
}
void Merge (int u, int v){
u = find (u);
v = find (v);
if (u != v)
fa[v] = u;
}
void Add (int u, int v, int i){
++ tot;
nex[tot] = firs[u];
cur[u] = firs[u] = tot;
to[tot] = v;
id[tot] = i;
}
void Hierholzer (int u){
int v;
for (int &e = cur[u];e;){
if (vis[id[e]])
e = nex[e];
else {
v = to[e];
vis[id[e]] = true;
e = nex[e];
Hierholzer (v);
}
}
sta[++ top] = u;
}
int main (){
freopen ("input.txt", "r", stdin);
freopen ("output.txt", "w", stdout);
n = 1e4;
scanf ("%d", &m);
for (int i = 1;i <= n;++ i)
fa[i] = i;
for (int i = 1, u, v;i <= m;++ i){
scanf ("%d%d", &u, &v);
if (u > v)
swap (u, v);
mp[make_pair (u, v)].push (i);
ext[u] = ext[v] = true;
++ deg[u];
++ deg[v];
Add (u, v, i);
Add (v, u, i);
Merge (u, v);
}
if (m < 2){
puts ("-1");
return 0;
}
int cnt = 0;
for (int i = 1;i <= n;++ i)
if (ext[i] && find (i) == i)
ld[++ cnt] = i;
if (cnt > 2){
puts ("-1");
return 0;
}
if (cnt == 1){
for (int i = 1;i <= n;++ i)
if (ext[i] && (deg[i] & 1))
st[++ ct] = i;
if (ct == 0){
for (int i = 1;i <= n;++ i)
if (ext[i]){
Hierholzer (i);
break;
}
printf ("%d\n", top - 2);
for (int i = top;i > 2;-- i){
printf ("%d\n", mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
printf ("1\n%d\n", mp[make_pair (min (sta[1], sta[2]), max (sta[1], sta[2]))].top ());
} else
if (ct == 2){
Hierholzer (st[1]);
printf ("%d\n", top - 2);
for (int i = top;i > 2;-- i){
printf ("%d\n", mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
printf ("1\n%d\n", mp[make_pair (min (sta[1], sta[2]), max (sta[1], sta[2]))].top ());
} else
if (ct == 4){
int a = st[1], b = st[2];
Add (a, b, n + 1);
Add (b, a, n + 1);
mp[make_pair (min (a, b), max (a, b))].push (n + 1);
Hierholzer (st[3]);
int tur = 0;
for (int i = top;i > 1;-- i){
if (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top () == n + 1)
++ tur;
else
Ans[tur].push_back (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
for (int i = 0;i < 2;++ i){
printf ("%d\n", Ans[i].size ());
for (int j = 0;j < (int) Ans[i].size ();++ j)
printf ("%d\n", Ans[i][j]);
}
} else
puts ("-1");
} else {
for (int i = 1;i <= n;++ i)
if (ext[i] && (deg[i] & 1) && find (i) == ld[1])
st[++ ct] = i;
if (ct == 0){
for (int i = 1;i <= n;++ i)
if (ext[i] && find (i) == ld[1]){
Hierholzer (i);
break;
}
for (int i = top;i > 1;-- i){
Ans[0].push_back (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
} else
if (ct == 2){
Hierholzer (st[1]);
for (int i = top;i > 1;-- i){
Ans[0].push_back (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
} else {
puts ("-1");
return 0;
}
top = 0;
ct = 0;
for (int i = 1;i <= n;++ i)
if (ext[i] && (deg[i] & 1) && find (i) == ld[2])
st[++ ct] = i;
if (ct == 0){
for (int i = 1;i <= n;++ i)
if (ext[i] && find (i) == ld[2]){
Hierholzer (i);
break;
}
for (int i = top;i > 1;-- i){
Ans[1].push_back (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
} else
if (ct == 2){
Hierholzer (st[1]);
for (int i = top;i > 1;-- i){
Ans[1].push_back (mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].top ());
mp[make_pair (min (sta[i], sta[i - 1]), max (sta[i], sta[i - 1]))].pop ();
}
} else {
puts ("-1");
return 0;
}
for (int i = 0;i < 2;++ i){
printf ("%d\n", Ans[i].size ());
for (int j = 0;j < (int) Ans[i].size ();++ j)
printf ("%d\n", Ans[i][j]);
}
}
return 0;
}
2023.11.23
Luogu - P9194 - [USACO23OPEN] Triples of Cows P
(0)
好题。
不给自己找理由，这题的思路确实是第一次见。考虑正常的点合并不再行得通，所以可以把边扩展一下。
如果原本有 \(e_i:(u,v)\)，则在扩展图中变为 \(e':(u,n+i),e'':(v,n+i)\)，我们把扩展的点称为白点，原本的点称为黑点。我们每次删去一个点时把它周围所有白点合并为一个。
这时新树 \(T'\) 以及任意删除后的树 \(T''\) 均满足黑白相间，原问题相当于求一条简单路径 \(a\to x\to b\to y\to c\)，使 \(a\) 是黑点。
不妨设 \(s_u\) 表示 \(u\) 的儿子个数。
那我们就分类讨论：
S1：
\(x=y\)，考虑按 \(x\) 点算贡献为 \(P_{s_x+1}^3\) 即 \(s_x(s_x+1)(s_x-1)\)。
S2：
\(x\ne y \land [x,y \text{为}b\text{儿子}]\) ,考虑按 \(b\) 点算贡献为：
\[\begin{aligned} & \sum_{x\in son_b}\sum_{y\in son_b \land x \ne y} s_xs_y \\ =&(\sum_{x\in son_b}s_x)^2-(\sum_{x\in son_b}s_x^2) \end{aligned} \]S3：
\(x\ne y \land [x\text{为 b 父亲，}y \text{为}b\text{儿子}]\) ,考虑按 \(x\) 点算贡献为：
\[\begin{aligned} & 2(s_x-1+1)\sum_{b\in son_x}\sum_{y\in son_b} s_y \\ =&2s_x\sum_{b\in son_x}\sum_{y\in son_b} s_y \end{aligned} \]然后求和化简就可以维护了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int firs[400005], nex[800005], to[800005], tot;
int bel[400005], fa[400005];
int s[400005], t[400005], ans;
int f_white (int x){
return s[x] * s[x] * s[x] - s[x] * s[x] - s[x] + 2ll * s[x] * t[x];
}
int f_black (int x){
return s[x] * s[x];
}
int f (int x){
if (x == 0)
return 0;
if (x > n)
return f_white (x);
else
return f_black (x);
}
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
int find (int v){
if (bel[v] == v)
return v;
return bel[v] = find (bel[v]);
}
void Merge (int u, int v){
u = find (u);
v = find (v);
if (u != v)
bel[v] = u;
}
void Init (int u, int father){
fa[u] = father;
bel[u] = u;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
Init (v, u);
if (u <= n)
s[u] += s[v];
else {
++ s[u];
t[u] += s[v];
}
}
ans += f (u);
}
signed main (){
scanf ("%lld", &n);
for (int i = 1, u, v;i < n;++ i){
scanf ("%lld%lld", &u, &v);
Add (u, n + i);
Add (n + i, u);
Add (v, n + i);
Add (n + i, v);
}
Init (n, 0);
for (int i = 1;i < n;++ i){
int u = find (fa[i]);
int ff = fa[u], faf = find (fa[ff]);
printf ("%lld\n", ans);
ans -= f (u) + f(i) + f (ff) + f (faf);
s[ff] -= s[u];
-- s[u];
t[u] -= s[i];
-- t[faf];
for (int e = firs[i], v;e;e = nex[e]){
v = to[e];
if (v == fa[i])
continue;
s[u] += s[v];
t[u] += t[v];
t[faf] += s[v];
Merge (u, v);
ans -= f (v);
}
s[ff] += s[u];
ans += f (u) + f (ff) + f (faf);
}
puts ("0");
return 0;
}
2023.12.03
难绷了，ruarua 地厌学，救命。
CF1086F Forest Fires
(0)
以前的比赛原题，今天找到原题，觉得当时自己太牛逼了，反观现在自己真的是越学越菜。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = - 1e18, mod = 998244353, inv2 = 499122177, inv6 = 166374059;
int n, t, pt[2505], cntm;
pair < int , int > ori[55];
int x[55], y[55];
int cnt, cntt;
pair < int , pair < int , int > > tt[205];
struct seq {
int l, r, s;
seq (int L = 0, int R = 0, int S = 0){
l = L;
r = R;
s = S;
}
} a[205];
map < int , int > dx, dy;
int Get_F (int q){
int Res = 0;
dx.clear ();
cnt = cntt = 0;
for (int i = 1;i <= n;++ i){
dx[x[i] - q] = 1;
dx[x[i] + q] = 1;
tt[++ cntt] = make_pair (y[i] - q, make_pair (i, 1));
tt[++ cntt] = make_pair (y[i] + q + 1, make_pair (i, - 1));
}
sort (tt + 1, tt + cntt + 1);
int pre = - inf;
for (map < int , int > :: iterator it = dx.begin ();it != dx.end ();++ it){
if (pre < it->first - 1 && pre != - inf)
a[++ cnt] = seq (pre + 1, it->first - 1, 0);
a[++ cnt] = seq (it->first, it->first, 0);
pre = it->first;
}
int idxt = 1, cos = 0;
pre = - inf;
for (;idxt <= cntt;){
int yy = tt[idxt].first;
(Res += (yy - pre) * cos % mod) %= mod;
while (idxt <= cntt && tt[idxt].first == yy){
int i = tt[idxt].second.first, e = tt[idxt].second.second;
int l = x[i] - q, r = x[i] + q;
for (int j = 1;j <= cnt;++ j)
if (l <= a[j].l && a[j].r <= r){
a[j].s += e;
if (a[j].s == 0)
cos -= a[j].r - a[j].l + 1;
else if (a[j].s == 1 && e == 1)
cos += a[j].r - a[j].l + 1;
}
++ idxt;
}
pre = yy;
}
return Res;
}
int Get_Sum (int x, int p){
if (p == 0)
return x;
if (p == 1)
return x * (x + 1) % mod * inv2 % mod;
if (p == 2)
return x * (x + 1) % mod * (2ll * x + 1) % mod * inv6 % mod;
return 0;
}
int Abs (int x){
if (x > 0)
return x;
else
return - x;
}
signed main (){
scanf ("%lld%lld", &n, &t);
for (int i = 1;i <= n;++ i)
scanf ("%lld%lld", &ori[i].first, &ori[i].second);
sort (ori + 1, ori + n + 1);
for (int i = 1;i <= n;++ i)
x[i] = ori[i].first, y[i] = ori[i].second;
for (int i = 1;i < n;++ i)
for (int j = i + 1;j <= n;++ j){
pt[++ cntm] = ((int) max (Abs (x[i] - x[j]), Abs (y[i] - y[j])) + 1) / 2;
if (pt[cntm] >= t)
-- cntm;
}
pt[++ cntm] = 0;
sort (pt + 1, pt + cntm + 1);
cntm = unique (pt + 1, pt + cntm + 1) - pt - 1;
pt[++ cntm] = t;
int Ans = t * Get_F (t) % mod;
for (int i = 1;i < cntm;++ i){
int tx = pt[i], px = pt[i + 1];
if (tx + 3 >= px)
for (int j = tx;j < px;++ j)
(Ans += mod - Get_F (j)) %= mod;
else {
int F1 = Get_F (tx), F2 = Get_F (tx + 1), F3 = Get_F (tx + 2);
int a = 0, b = 0, c = 0;
a = (F3 - F2) % mod - (F2 - F1) % mod + 2ll * mod;
a = (a % mod * inv2) % mod;
(F1 += mod - a * tx % mod * tx % mod) %= mod;
(F2 += mod - a * (tx + 1) % mod * (tx + 1) % mod) %= mod;
b = F2 - F1 + mod;
b %= mod;
(F1 += mod - b * tx % mod) %= mod;
c = F1;
Ans += mod - (Get_Sum (px - 1, 2) - Get_Sum (tx - 1, 2) + mod) % mod * a % mod;
Ans %= mod;
Ans += mod - (Get_Sum (px - 1, 1) - Get_Sum (tx - 1, 1) + mod) % mod * b % mod;
Ans %= mod;
Ans += mod - (Get_Sum (px - 1, 0) - Get_Sum (tx - 1, 0) + mod) % mod * c % mod;
Ans %= mod;
}
}
printf ("%lld\n", Ans);
return 0;
}
2023.12.04
VP 了场 Edu，名副其实出题人〇神玩多了。
CF1902F - Trees and XOR Queries Again
线性基板题。不知道这场在干什么，就没一道好题吗？
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
static char buf[1000000] ,*p1 = buf, *p2 = buf;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++
inline int read (){
register int x = 0;
register char c = getchar ();
while (c < '0' || c > '9') c = getchar ();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar ();
return x;
}
int n, a[200005], dep[200005];
int Q, x, y, k;
int firs[200005], nex[400005], to[400005], tot;
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
int fa[19][200005];
int log2_ (int u){
if (u == 0)
return - 1;
return 31 ^ __builtin_clz (u);
}
struct LB {
int a[20];
LB (){
for (int i = 19;i >= 0;-- i)
a[i] = 0;
}
inline void Join (const LB &oth){
for (int i = 19, u;i >= 0;-- i){
u = oth.a[i];
for (int j = i;j >= 0 && u;j = log2_ (u))
if (u >> j & 1){
if (a[j] != 0)
u ^= a[j];
else {
a[j] = u;
break;
}
}
}
}
inline void Add (int u){
for (int j = log2_ (u);j >= 0 && u;j = log2_ (u))
if (u >> j & 1){
if (a[j] != 0)
u ^= a[j];
else {
a[j] = u;
break;
}
}
}
inline bool Check (int u){
for (int i = log2_ (u);i >= 0 && u;i = log2_ (u))
if (u >> i & 1){
if (a[i] == 0)
return false;
else
u ^= a[i];
}
return true;
}
} lbf[19][200005], lbt;
inline void Init (int u, int father){
dep[u] = dep[father] + 1;
fa[0][u] = father;
lbf[0][u].Add (a[u]);
int lim = log2_ (dep[u]);
for (int i = 1;i <= lim;++ i){
fa[i][u] = fa[i - 1][fa[i - 1][u]];
lbf[i][u] = lbf[i - 1][u];
lbf[i][u].Join (lbf[i - 1][fa[i - 1][u]]);
}
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
Init (v, u);
}
}
inline void Solve (int u, int v){
lbt = LB ();
if (dep[u] < dep[v])
swap (u, v);
for (int i = log2_ (dep[u]);i >= 0;-- i)
if (dep[fa[i][u]] >= dep[v]){
lbt.Join (lbf[i][u]);
u = fa[i][u];
}
if (u == v){
lbt.Add (a[u]);
return ;
}
for (int i = log2_ (dep[u]);i >= 0;-- i)
if (fa[i][u] != fa[i][v]){
lbt.Join (lbf[i][u]);
lbt.Join (lbf[i][v]);
u = fa[i][u];
v = fa[i][v];
}
lbt.Add (a[u]);
lbt.Add (a[v]);
lbt.Add (a[fa[0][u]]);
}
int main (){
n = read ();
for (int i = 1;i <= n;++ i)
a[i] = read ();
for (int i = 1, u, v;i < n;++ i){
u = read ();
v = read ();
Add (u, v);
Add (v, u);
}
Init (1, 0);
Q = read ();
while (Q --){
x = read ();
y = read ();
k = read ();
Solve (x, y);
if (lbt.Check (k))
puts ("YES");
else
puts ("NO");
}
return 0;
}
/*
** I'm a crazy fan of MasterCactus.
*/
2023.12.06
CF1622F - Quadratic Set
喔趣，好题。综合了不同的思路（主要是证明思路），切掉了这个题。
首先答案大于等于 \(n-3\)。
\[\begin{aligned} &\sum_{i=1}^n i! = \sum_{i=1}^n i^{n-i+1} \\ &\Rightarrow \sum_{i=1}^{2k}i!=2^kk!(\prod_{i=1}^k (2i - 1)!)^2 \end{aligned} \]有构造法：
-
\(4|n\) 时，可以删去 \(\{\frac{n}{2}\}\)。
-
\(4|(n-2)\) 时，可以删去 \(\{2,\frac{n}{2}\}\)。
-
\(2|(n-1)\) 时，可以删去 \(\{2,\frac{n-1}{2}, n\}\)。
上述情况包含了所有非零自然数，故答案大于等于 \(n-3\)。
剩下的就是求具体方案，构造解并非最优解，所以去要另外想办法快速判断平方数。
于是可以 xor-hashing。很牛逼，给每个质因数随机赋值，再质因数分解 xor 去求每个数的 hash 值，再求阶乘，一扫障碍，甚至可以用一些 STL 和其他容器做到 \(O(n)\)，但是我太懒了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 mtrand (time (0));
const int N = 1e6 + 5;
int n;
int val[N], jc[N], s;
int cnt, prime[N];
bool not_prime[N], out_set[N];
map < int , int > mp;
void FIN (){
for (int i = 1;i <= n;++ i)
if (! out_set[i])
printf ("%lld ", i);
puts ("");
exit (0);
}
signed main (){
scanf ("%lld", &n);
not_prime[1] = true;
for (int i = 2;i <= n;++ i)
if (! not_prime[i]){
prime[++ cnt] = i;
for (int j = 2;i * j <= n;++ j)
not_prime[i * j] = true;
}
for (int i = 1;i <= n;++ i){
if (! not_prime[i])
val[i] = mtrand ();
else {
for (int j = 1;prime[j] * prime[j] <= i && j <= cnt;++ j)
if (i % prime[j] == 0){
val[i] = val[i / prime[j]] ^ val[prime[j]];
break;
}
}
jc[i] = jc[i - 1] ^ val[i];
s ^= jc[i];
mp[jc[i]] = i;
}
if (s == 0){
printf ("%lld\n", n);
FIN ();
}
if (mp.find (s) != mp.end ()){
out_set[mp[s]] = true;
printf ("%lld\n", n - 1);
FIN ();
}
for (int i = 1;i <= n;++ i)
if (mp.find (s ^ jc[i]) != mp.end ()){
int j = mp[s ^ jc[i]];
out_set[i] = out_set[j] = true;
printf ("%lld\n", n - 2);
FIN ();
}
out_set[n] = out_set[n / 2] = out_set[2] = true;
printf ("%lld\n", n - 3);
FIN ();
}
/*
** I'm a crazy fan of MasterCactus a.k.a. FastFourierTransform.
*/