格雷码
第 (n) 位格雷码 ：g(n) = n^(n>>1); 。
正确性证明： ((n)_2 = cdots0111111 Rightarrow (n+1)_2 = cdots100000)， 比较显然。
逆变换：
int rv_g(int g) {
int n = 0;
for(;g;g>>=1) n^=g;
return g;
}
括号树
求点到根有多少个后缀是合法括号串的方法：
设有两节点 (x,y)， 其中 (y) 是 (x) 的祖先， 那么 (ycdots x) 是合法括号串的条件是：
- x 是右括号
- y…fa[x] 任意节点到 y 的左括号个数都大于右括号个数
- y…fa[x] 左括号个数只比右括号个数大 1
然后就可以用 DP 求了。
然而还有一种方法, 更易于理解：
考虑合法括号串的形式：
- ((o))
- (((sda)(sadad))()()cdots(o))
那么维护每个节点匹配到的左括号的节点的编号就可以方便地算出答案了。
#include<cstdio>
#include<iostream>
#include<algorithm>
const int MN = 500003;
int n, fa[MN];
char s[MN];
int ct, hd[MN], nt[MN<<1], vr[MN<<1];
long long ans[MN];
int tp, sta[MN];
void dfs(int x) {
if(s[x] == '(') {
sta[++tp] = x;
for(int i=hd[x];i;i=nt[i]) dfs(vr[i]);
sta[--tp];
} else {
bool ok = (tp>0);
int tmp = 0;
if(ok) {
tmp = sta[tp--];
ans[x] = ans[fa[tmp]] + 1ll;
}
for(int i=hd[x];i;i=nt[i]) dfs(vr[i]);
if(ok) sta[++tp] = tmp;
}
}
void ad(int x,int y) {vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct;}
void dfs2(int x) {
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
ans[y] += ans[x];
dfs2(y);
}
}
int main() {
std::cin>>n;
scanf("%s", s+1);
for(int i=2;i<=n;++i) {
scanf("%d",&fa[i]); ad(fa[i],i);
}
dfs(1);
dfs2(1);
long long Ans = 0ll;
for(int i=1;i<=n;++i) Ans = Ans ^ (ans[i] * 1ll * i);
std::cout << Ans;
return 0;
}
树上的数
基本思路就是贪心， 先考虑 1 最后停留的节点， 再考虑 2 ……
抄一下出题人的题解。
- 某个数要从某个节点的某条边离开， 那么这条边一定是这个节点第一条被选择的边
- 某个数要从某个节点的某条边进入并停在这一点， 那么这条边一定是这个节点最后一条被选择的边
- 某个数要从某个节点的 x 边进入， y 边离开， 那么关于这个节点的断边顺序一定是 x，y 相邻。
链的部分分
对于链， 每个节点的度数不超过 2， 所以所有的条件都变成 “某条边要比另一条边先断开”。
从小到大枚举数字， 贪心地枚举这个数字的最终节点， 用拓扑排序检查是否与之前的方案矛盾， 总复杂度 (sf O(N^3))。
优化： 枚举最终节点的时候， 把当前数字所在的节点拎出来当做根， 用 dfs 枚举最终节点， 然后每个点对应的一大堆边的限制都和父亲节点有一点微小的限制， 就可以判断了。
这个部分分最后代码大概长这样， 不是很想写完， 因为没数据可以用来调试……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MN = 2003;
int n, id[MN], a[MN];
int bigger[MN][MN], deg[MN];
// about the index of edges :
// edge(i) means the edge connect node i and i+1 (1<=i<n)
int now;
void sol() {
for(int i=1;i<=n;++i) {
now = n+1;
dfs(id[i]);
int l=min(i,now), r=max(i,now);
if(l>1) bigger[l][l-1]=true, ++deg[l-1];
if(r<n) bigger[r][r-1]=true, ++deg[r-1];
for(int j=l;j<=r-2;++j) bigger[j][j+1] = true, ++deg[j+1];
}
std::queue<int> q;
while(!q.empty()) q.pop();
for(int i=1;i<n;++i) if(!deg[i]) q.push(i);
while(!q.empty()) {
int x=q.front(); q.pop();
swap(a[x],a[x+1]);
for(int y=1;y<n;++y) {
if(bigger[x][y]) {
if(--deg[y] == 0) q.push(y);
}
}
}
for(int i=1;)
}
int main() {
int T;std::cin>>T; while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&id[i]); a[id[i]]=i;
for(int j=1;j<=n;++j)bigger[i][j]=0;
deg[i]=0;
}
for(int i=1;i<n;++i) {int x,y;scanf("%d%d",&x,&y);}
sol(); putchar('
');
}
return 0;
}
菊花图的部分分
某数字要从中心节点的 x 边进入， 从 y 边离开， 那么中心节点相关的断边序列中 x，y 是相邻的。
100pts
（抄一下仓鼠的题解）
由于所有的对于边的限制条件必然是 DAG（只有相邻的边才会产生至多一条限制）， 所以只需要 (sf O(n^2)) 贪心就好了， 要用数据结构维护。
具体地：
对于 (n
eq 1) 的情况， 从小到大枚举数字， 贪心地选取其最终停留的节点， 这会给一些边（这些边一定是相邻的）留下一些 “限制”， 即 “最先断”、“最后断“ 以及 “这条边一定在那条边之前被断”。
选取最终节点的时候， 应注意需要不与前面的选择留下的限制冲突， 然后在加上选取这个最终节点的限制。
Emiya家今天的饭
题目就是选出矩形中的一些格子， 权值是格子的权值乘起来， 要求求所有方案数的权值和。
选格子的限制是：
- 至少选一个格子
- 一行中不能选多个
- 不能有超过格子总数 (dfrac{1}2) 的格子在同一列中
考虑容斥， 先算出满足前两个限制的权值和， 再减去满足前两个限制但不满足最后一个限制的权值和。
只满足前两个限制的权值和很好算。
对于不满足最后一个限制的权值和， 可以枚举超过的那一列是哪一列， 然后算就行了。
具体地， 设枚举的那一列是 (pos)， 那么：
设 (f_{i,othnum,posnum}) 表示第 (i) 行选了 (othnum) 个不在 (pos) 这一列的格子和 (posnum) 个在 (pos) 这一列的权值和， 最后答案就是 (sum f_{n,ot,po})， 满足 (ot > lfloor dfrac{ot+po}{2}
floor) 。
状态可以简化， 依据是 (sum f_{n,ot,po})， 满足 (ot > lfloor dfrac{ot+po}{2} floor Rightarrow 2*ot > ot+po Rightarrow ot > po) 。
于是设状态 (f_{i,delta}) 表示第 (i) 行 (othnum - posnum = delta) 的权值和， 最后答案取 (sum f_{n,ok}) 满足 (ok > 0) 的就可以了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
const int MN = 103;
const int MM = 2003;
const int mod = 998244353;
const int base = 110;
int n,m;
long long a[MN][MM], sum[MN];
long long Ans = 1ll;
long long f[MN][3*MN];
int main() {
std::cin>>n>>m;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
scanf("%lld",&a[i][j]);
sum[i] += a[i][j];
sum[i] %= mod;
}
Ans = 1ll * Ans * (sum[i]+1) %mod;
}
// --Ans;if(Ans<0) Ans += mod;
for(int pos=1;pos<=m;++pos) {
memset(f,0,sizeof f);
f[1][1+base] = a[1][pos];
f[1][-1+base] = (sum[1]-a[1][pos])%mod;
f[1][0+base] = 1ll;
for(int i=2;i<=n;++i)
for(int j=-i;j<=i;++j) {
f[i][j+base] += f[i-1][j+base];
f[i][j+base] %= mod;
f[i][j+base] += f[i-1][j-1+base] * a[i][pos];
f[i][j+base] %= mod;
f[i][j+base] += f[i-1][j+1+base] * (sum[i] - a[i][pos]);
f[i][j+base] %= mod;
}
for(int i=1;i<=n;++i) {
Ans -= f[n][i+base];
Ans %= mod;
if(Ans<0) Ans+=mod;
}
}
std::cout << ((Ans-1)%mod+mod)%mod;
return 0;
}
树的重心
[白白浪费了多少时间orz
]
只要把根设为重心， 这题就好做了。
好做的一匹啊。
只能在loj、洛谷上过， uoj过不了：
#include<bits/stdc++.h>
using namespace std;
const int MN = 300003;
const int Mi = 19;
int read() {
int x=0;
char c = getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {
x = x*10+c-'0';
c=getchar();
}
return x;
}
int n, zx, rt;
int ct, hd[MN], nt[MN<<1], vr[MN<<1];
void ad(int x,int y) {vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct; }
int siz[MN], son1[MN], son2[MN], tP[MN];
int f[21][MN]; // Mi = 19
long long Ans;
void rfs(int x) {
f[0][x] = son1[x];
for(int i=1;i<=19;++i)
f[i][x] = f[i-1][f[i-1][x]];
}
void dfs1(int x,int fa) {
int max_part = 0;
siz[x] = 1;
son1[x] = son2[x] = 0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
dfs1(y,x);
siz[x] += siz[y];
max_part = max(max_part, siz[y]);
if(!son1[x] || siz[y]>siz[son1[x]]) son2[x]=son1[x], son1[x]=y;
else if(!son2[x] || siz[y]>siz[son2[x]]) son2[x] = y;
}
max_part = max(max_part, n-siz[x]);
if(max_part <= (n/2)) zx = x;
rfs(x);
}
void tg(int x, int fa) {
tP[x] = rt;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
tg(y,x);
}
}
void fid(int x) {
int t = x;
for(int i=19;i>=0;--i)
if(siz[f[i][t]] > siz[x]/2)
t = f[i][t];
if(siz[x]-siz[t] <= siz[x]/2) {
Ans += 1ll * t;
// printf("#%d",t);
}
t = f[0][t];
if(siz[x]-siz[t] <= siz[x]/2) {
Ans += 1ll * t;
// printf("#%d",t);
}
// puts("");
}
void sol(int x,int fa) {
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
fid(y);
sol(y,x);
/*
2 18
3 32
*/
if(tP[y] != rt) {
// cout << y << '
';
siz[rt] -= siz[y];
fid(rt);
siz[rt] += siz[y];
}
else {
if(siz[son1[rt]]-siz[y] > siz[son2[rt]]) {
// cout << y << '
';
siz[rt] -= siz[y];
siz[son1[rt]] -= siz[y];
// fid(rt);
Ans += 1ll * rt;
if(siz[rt]-siz[son1[rt]] <= siz[rt]/2) Ans += 1ll * rt;
siz[son1[rt]] += siz[y];
siz[rt] += siz[y];
}
else {
// cout << y << '
';
int t1 = son1[rt];
son1[rt] = son2[rt];
rfs(rt);
siz[rt] -= siz[y];
fid(rt);
siz[rt] += siz[y];
son1[rt] = t1;
rfs(rt);
}
}
}
}
int main() {
int T;cin>>T;while(T--) {
Ans = 0ll;
ct = 0;
n = read();
// scanf("%d", &n);
for(int i=1;i<=n;++i) hd[i]=tP[i]=0;
for(int i=1,x,y;i<n;++i) {x=read(); y=read();//scanf("%d%d",&x,&y);
ad(x,y); ad(y,x); }
dfs1(1,0);
rt = zx;
dfs1(rt,0);
tg(son1[rt],rt);
sol(rt,0);
// siz[rt] -= siz[2];
// fid(rt);
// siz[rt] += siz[2];
// for(int i=1;i<=n;++i) cout << tP[i] << ' ';puts("");
// cout << rt << ' ' << Ans << '
';
cout << Ans << '
';
}
return 0;
}
下面两个是失败合集。
一个结论是：所有重心一定在根所在的重链上。
那么就可以找倍增找重心， 具体地， 倍增维护往重链走了多少步， 可以到达哪个节点 。
然而如果断的是根的重链上的边， 就没法很快地维护倍增数组……所以可以对于根的重链的断边后上面的那棵树单独处理出另一个向上的倍增数组。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
const int MN = 300005;
const int Mi = 19;
int n, siz[MN], son1[MN], son2[MN], toP[MN];
int ct, hd[MN], vr[MN<<1], nt[MN<<1];
int f[20][MN], g[20][MN];
long long Ans;
void ad(int x,int y) { vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct;}
/*
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
}
神奇模板助我快速编码
*/
void rfs(int x) {
f[0][x] = son1[x];
for(int i=1;i<=Mi;++i)
f[i][x] = f[i-1][f[i-1][x]];
}
void dfs(int x,int fa) {
g[0][x] = fa;
son1[x]=son2[x]=0;
siz[x] = 1;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
dfs(y,x);
siz[x] += siz[y];
if(siz[y]>siz[son1[x]]) son2[x]=son1[x], son1[x]=y;
else if(siz[y]>siz[son2[x]]) son2[x]=y;
}
rfs(x);
}
void po(int x,int fa,int tp) {
toP[x] = tp;
if(son1[x]) po(son1[x],x,tp);
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa || y == son1[x]) continue;
po(y,x,y);
}
}
void fid(int x) {
int t = x;
for(int i=Mi;i>=0;--i)
if(siz[f[i][x]] > siz[t]/2)
x = f[i][x];
if(siz[t]-siz[x]<=siz[t]/2)
Ans += 1ll * x;//, printf("%d ",x);
x = f[0][x];
if(siz[t]-siz[x]<=siz[t]/2)
Ans += 1ll * x;//, printf("%d ",x);
}
void sol(int x,int fa) {
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
// printf("%d :
", y);
fid(y);
// puts("
");
sol(y,x);
siz[1] -= siz[y];
if(toP[y] != 1) fid(1);
else if(siz[son1[1]]-siz[y] <= siz[son2[1]]) {
// printf("# %d %d
", y, son2[1]);
int t1 = son1[1];
son1[1] = son2[1];
rfs(1);
fid(1);
son1[1] = t1;
rfs(1);
}
siz[1] += siz[y];
}
}
/*
27
49
*/
// int f_i_d(int x) {
// int t = x;
// for(int i=Mi;i>=0;--i)
// if(siz[f[i][x]] > siz[t]/2)
// x = f[i][x];
// if(siz[t]-siz[f[0][x]]<=siz[t]/2)
// return f[0][x];
// return x;
// }
void Emilia_M_T(int x, int fa) {
// 吧 x 到 fa[x] 的那条边断开， 根节点所在树的重心。
// 保证断开之后根节点的重儿子还是原来的重儿子
printf("# %d %d %d
", fa, x, son2[fa]);
int S = siz[1] - siz[x];
if(son2[fa]) {
int t = son2[fa];
for(int i=Mi;i>=0;--i)
if(siz[f[i][t]] > S/2)
t = f[i][t];
if(S-siz[t] <= S/2)
Ans += 1ll * t;
if(S-siz[f[0][t]] <= S/2)
Ans += 1ll * f[0][t];
std::cout << t << ' ';
}
// if(fa==3) return;
int t = 1;
for(int i=Mi;i>=0;--i)
if(siz[f[i][t]]>=siz[fa] && siz[f[i][t]]-siz[x]>S/2)
t = f[i][t];
std::cout << t << '
';
if(S-siz[t]+siz[x] <= S/2)
Ans += 1ll * t;
if(t!=fa && S-siz[f[0][t]]+siz[x] <= S/2)
Ans += 1ll * f[0][t];
}
int main() {
int T;std::cin>>T;while(T-- ){
Ans = 0ll;
ct = 0;
scanf("%d",&n);
for(int i=1;i<=n;++i) {hd[i]=0;}
for(int i=1,x,y;i<n;++i) {scanf("%d%d",&x,&y);ad(x,y);ad(y,x);}
dfs(1,0);
po(1,0,1);
// for(int i=1;i<=n;++i) printf("%d --> siz = %d, toP = %d, son1 = %d, son2 = %d
", i, siz[i], toP[i], son1[i], son2[i]);puts("");
sol(1,0); // 先处理一部分
for(int i=1;i<=Mi;++i)
for(int x=1;x<=n;++x)
g[i][x] = g[i-1][g[i-1][x]];
int p = 1;
while(son1[p]) {
if(siz[son1[1]]-siz[son1[p]] <= siz[son2[1]]) {
p = son1[p];
continue;
}
Emilia_M_T(son1[p], p);
p = son1[p];
}
printf("%d
", Ans);
}
return 0;
}
另一种做法： 统计每个点 x 被当做重心的次数。（暂时没想出来， 以后再想）
设 (siz[x]) 表示以 (x) 为根的子树大小， (root) 表示整棵树的根（把一个重心拿出来当根）。
-
若 x 是整棵树的重心， 由于 x 最多有两个， 就可以先以 x 为根 dfs 求出若干信息， 然后再搞。 假设切掉的子树为 (del)， 设切掉后 (x) 的最大子树大小为 (mx)（这个算出 x 的不切时的最大和次大子树即可很快算出）， 那么需要满足 (mxle lfloor dfrac{siz[x]-siz[del]}{2} floor) ，化简一下就是 (siz[del] le siz[x]-2mx) 。这个条件不是很好做， 但是可以考虑切掉的子树要是在原来的最大子树里， 那么切掉后原来的最大子树也会满足条件， 只需要判断原来的次大子树是否满足条件； 要是切掉的子树不在原来的最大子树里， 那么切掉后只需要判断原来的最大子树是否满足条件， 总之， 这样就分两种情况固定了 (mx)， 剩下的问题就是求出整棵树有多少子树满足其 (siz) 小于一个固定值， 这个可以一次 dfs。
-
若 x 不是整棵树的重心，那么割掉的子树一定不在 x 的子树内。（反之可以推出当前整棵树的根不是重心） 设 x 的最大子树为 y， 那么切掉的点 (del) 需要满足以下两个条件：
[egin{cases} siz[y] le lfloor dfrac{|T|-siz[del]}{2} floor \ |T|-siz[x]-siz[del] le lfloor dfrac{|T|-siz[del]}{2} floor end{cases} ]化简加合并就是 ： (|T|-2*siz[x] le siz[del] le |T|-2*siz[y])， 这个东西显然就可以树状数组维护值域， 至于怎么维护， 是两个差分的套路， 一个差分是整棵树的值域减去某颗子树的值域， 另一个差分是子树的值域可以在 dfs 的过程中差分得到（这个好像 IOI2009Region的根号分治做法就用到了， 弱校选手伤不起……啥都不会）。
然而这个思路有问题……不做了不做了， 弃了弃了。
//这当然是错误的代码啦……
#include<bits/stdc++.h>
using namespace std;
const int MN = 300005;
int n;
int ct, hd[MN], nt[MN<<1], vr[MN<<1];
void ad(int x,int y) {vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct;}
int zxcnt, zx[3];
int siz[MN], son[MN], top[MN];
long long Ans=0ll;
struct fenwick{
int tree[MN];
void clear() {for(int i=1;i<=n;++i) tree[i]=0;}
inline int lowbit(int x) {return x&(-x);}
void ins(int pos) {for(;pos<=n;pos+=lowbit(pos)) ++tree[pos];}
int ask(int pos) {int res=0; for(;pos;pos-=lowbit(pos))res+=tree[pos]; return res;}
int query(int l,int r) {return ask(r)-ask(l-1);}
} T1, T2, T3;
void dfs3(int x,int fa) {
int mx=0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y==fa) continue;
if(!mx || siz[y]>siz[mx]) mx=y;
}
int res=0;
if(x!=zx[1] && x!=zx[2]) {
Ans += x*T2.query(n-2*siz[x], n-2*siz[mx]), res+=T2.query(n-2*siz[x], n-2*siz[mx]);
Ans -= x*T3.query(n-2*siz[x], n-2*siz[mx]), res-=T3.query(n-2*siz[x], n-2*siz[mx]);
Ans += x*T3.query(n-2*siz[x], n-2*siz[mx]), res+=T3.query(n-2*siz[x], n-2*siz[mx]);
}
T2.ins(siz[x]);
T3.ins(siz[x]);
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y!=fa) dfs3(y,x);
}
T3.del(siz[x]);
if(x!=zx[1] && x!=zx[2]) {
Ans -= x*T2.query(n-2*siz[x], n-2*siz[mx]);
Ans += x*T1.query(n-2*siz[x], n-2*siz[mx]);
res -= T2.query(n-2*siz[x], n-2*siz[mx]);
res += T1.query(n-2*siz[x], n-2*siz[mx]);
cout << x << ' ' << res << "
";
if(siz[mx]<=(siz[x]/2)) Ans += x, ++res;
cout << x << ' ' << res << "
";
}
}
void dfs1(int x,int fa) {
siz[x] = 1;
int max_part=0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y==fa) continue;
dfs1(y,x);
siz[x] += siz[y];
max_part = max(max_part, siz[y]);
}
max_part = max(max_part, n-siz[x]);
if(max_part <= (n/2)) zx[++zxcnt] = x;
}
void dfs2(int x,int fa) {
siz[x] = 1;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y==fa) continue;
dfs2(y,x);
siz[x] += siz[y];
}
}
int calc(int x, int lim, int fa) {
int res = 0;
if(siz[x] <= lim) res=1;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(y == fa) continue;
res += calc(y,lim,x);
}
return res;
}
int main() {
int T; cin>>T; while(T--) {
Ans = 0ll;
ct=0; memset(hd,0,sizeof hd);
zxcnt = 0;
scanf("%d",&n);
for(int i=1;i<n;++i) {int x,y;scanf("%d%d",&x,&y);ad(x,y);ad(y,x);}
dfs1(1,0);
for(int i=1;i<=zxcnt;++i) {
int mx1=0, mx2=0;
int x = zx[i];
// cout << "ZX : " << x << '
';
dfs2(x,0);
for(int j=hd[x];j;j=nt[j]) {
int y = vr[j];
if(!mx1 || siz[y]>siz[mx1]) mx2=mx1, mx1=y;
else if(!mx2 || siz[y]>siz[mx2]) mx2=y;
}
for(int j=hd[x];j;j=nt[j]) {
int y = vr[j];
if(y == mx1) Ans += x*calc(y, n-2*siz[mx2], x);
else Ans += x*calc(y, n-2*siz[mx1], x);
}
}
putchar('
');
// // calc zhongxin
T1.clear();
T2.clear();
T3.clear();
for(int i=1;i<=n;++i) T1.ins(siz[i]);
dfs3(zx[zxcnt],0);
cout << Ans << '
';
}
return 0;
}