A
枚举每个矩形，前缀和优化即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2000+5;
char str[MAXN];
int n,k;
int sm[MAXN][MAXN];
int main(){
scanf("%d%d",&n,&k);
FOR(i,1,n){
scanf("%s",str+1);
FOR(j,1,n){
sm[i][j] = sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1]+str[j]-'0';
}
}
int ans = 0;
FOR(i,k,n){
FOR(j,k,n){
ans = std::max(ans,sm[i][j]-sm[i-k][j]-sm[i][j-k]+sm[i-k][j-k]);
}
}
printf("%d
",ans);
return 0;
}
B
(O(n2^n)) 可以做任意图，只需要考虑如何判断一个图是强连通图：有一个点在正图和反图上都能到达所有点。
这个题要注意到竞赛图缩点后 DAG 上拓扑序小的点向拓扑序大的点都有连边。
所以我们如果得到了一个集合 (S) 是强连通的，设属于它的所有的点的出边的交为 (T)，对于任意 (R subset T,R eq emptyset)，一定 (S | R) 是不合法的区间。而我们发现这样顶多会不重不漏遍历每个状态一次，所以均摊复杂度是 (O(2^n)) 的。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 24+1;
int n;
int e[MAXN],out[(1<<MAXN)+3],pc[(1<<MAXN)+3];
#define lowbit(x) ((x)&(-(x)))
bool f[(1<<MAXN)+3];
inline void Solve(){
scanf("%d",&n);CLR(e,0);CLR(f,0);
FOR(i,0,n-1){
FOR(j,0,n-1){
int x;scanf("%d",&x);
e[i] |= (x<<j);
}
}
out[0] = (1<<n)-1;
FOR(S,1,(1<<n)-1) out[S] = out[S-lowbit(S)]&e[pc[lowbit(S)]];
int ans = 1;
FOR(S,1,(1<<n)-1){
if(!f[S]){
ans++;
for(int T = out[S];T;T = (T-1)&out[S]){
f[S|T] = 1;
}
}
}
printf("%d
",ans);
}
int main(){
FOR(i,0,23) pc[1<<i] = i;
int T;scanf("%d",&T);
while(T--) Solve();
return 0;
}
C
我们先来观察一下什么情况是不合法的。我们按轮考虑：
设数字 (i) 在三个人的序列出现的位置分别是 (pa_i,pb_i,pc_i)；设在第 (i) 轮三个人选的数字是 (x,y,z)，合法当且仅当
- (x,y,z) 互不相同
- (x) 在 (B,C) 的喜好序列出现的位置在 (y,z) 后面，其余同理
所以我们发现我们如果确定了这三个人选什么数的话， C 的排列的方案数都是不变的，可以设 (g_{i,j}) 表示考虑确定了 C 的前 (i) 位，已经进行了 (j) 轮的方案数，转移可以枚举这一位是否是 C 最终选的数字中的一个位置，如果是就 (g_{i,j} = g_{i-1,j-1}(2j-(i-j)))，否则就直接 (g_{i,j} = g_{i-1,j})。
然后我们现在就是要对有多少种不同的选数方案进行dp；设 (f_{i,j,k}) 表示 A 选了它自己的序列中第 (i) 个，B 选了第 (j) 个，C 还空着 (k) 个的方案数。枚举下一次选的位置 (i',j')，我们发现首先 (i') 在 B 中出现的位置不能在 (j') 之前，(j') 在 A 中出现的位置不能在 (i') 之前。如果在 ([i,i'],[j,j']) 有个数字没有被选过，一定是被 (C) 选了，我们设这样的数字数量为 (x)。转移就是 (f_{i,j,k} o k^{underline x}f_{i',j',k+1-x})。
这样复杂度就是 (O(n^6)) 的。
首先我们可以预处理找 (x) 的过程，复杂度变成了 (O(n^5))。
我们考虑每次可以不用一起枚举 (i',j') ，可以设 (f1,f2) 表示两个人的 dp 数组，所以复杂度变成了 (O(n^4))。
我们发现每次只需要考虑 (i+1) 的位置是否选择，选择了就换到另一个人的 dp 数组转移，复杂度 (O(n^3))。注意到我们从第一个人转移到第二个人不用考虑任何限制，在第二个人转移回去的时候统一考虑即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 400+5;
const int ha = 1e9 + 7;
int n,a[MAXN],b[MAXN],pa[MAXN],pb[MAXN];
int f1[MAXN][MAXN][MAXN],f2[MAXN][MAXN][MAXN];
// A选了第i个,B选了第j个,C还能用k个
int g[MAXN][MAXN];
// 前i个 选了j个
inline void add(int &x,int y){
x += y;if(x >= ha) x -= ha;
}
int main(){
scanf("%d",&n);
FOR(i,1,n) scanf("%d",a+i),pa[a[i]] = i;
FOR(i,1,n) scanf("%d",b+i),pb[b[i]] = i;
f1[1][1][1] = 1;
FOR(i,1,n+1){
FOR(j,1,n+1){
FOR(k,0,n/3){
if(f1[i][j][k]){
if(k && pb[a[i+1]] > j) add(f1[i+1][j][k-1],1ll*f1[i][j][k]*k%ha);
if(pb[a[i+1]] <= j) add(f1[i+1][j][k],f1[i][j][k]);
add(f2[i+1][j][k],f1[i][j][k]);
}
if(f2[i][j][k]){
if(k && pa[b[j+1]] > i) add(f2[i][j+1][k-1],1ll*f2[i][j][k]*k%ha);
if(pa[b[j+1]] <= i) add(f2[i][j+1][k],f2[i][j][k]);
if(i == n+1 || j == n+1 || (pb[a[i]] > j+1 && pa[b[j+1]] > i)) add(f1[i][j+1][k+1],f2[i][j][k]);
}
}
}
}
g[0][0] = 1;
FOR(i,0,n-1){
FOR(j,0,n/3){
add(g[i+1][j+1],g[i][j]);
if(3*j-i > 0) add(g[i+1][j],1ll*g[i][j]*(3*j-i)%ha);
}
}
int ans = 1ll*f1[n+1][n+1][1]*g[n][n/3]%ha;
printf("%d
",ans);
return 0;
}
D
树上路径问题如果不会了可以考虑链分治，分开维护重链和轻边。
对于重链的颜色直接用线段树维护区间赋值即可。
轻边的颜色有两种可能改变：
- 有一次修改经过了这个轻边
- 有一次修改经过了轻边的两个端点之一，并没有经过轻边
我们只需要知道这两个操作最后一次的时间，就能判断出轻边的颜色，线段树维护即可。
要注意是轻边的两个端点都要查，因为可能有某个修改的 lca 到父亲的边是轻边的情况。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 3e5 + 5;
int n,q;
struct Edge{
int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;
inline void add(int u,int v){
e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}
#define lc ((x)<<1)
#define rc ((x)<<1|1)
int sm[MAXN<<2],ts[MAXN<<2],cov[MAXN<<2],tag[MAXN<<2];
// 0表示染黑 数字表示有个时间
inline void cover1(int x,int l,int r,int d){
sm[x] = (r-l+1)*d;cov[x] = d;
}
inline void cover2(int x,int l,int r,int d){
ts[x] = tag[x] = d;
}
inline void pushdown(int x,int l,int r){
int mid = (l + r) >> 1;
if(cov[x] != -1){
cover1(lc,l,mid,cov[x]);
cover1(rc,mid+1,r,cov[x]);
cov[x] = -1;
}
if(tag[x] != -1){
cover2(lc,l,mid,tag[x]);
cover2(rc,mid+1,r,tag[x]);
tag[x] = -1;
}
}
inline void modify(int x,int l,int r,int L,int R,int d){
if(L > R) return;
if(l == L && r == R){
cover1(x,l,r,d?0:1);
if(d) cover2(x,l,r,d);
return;
}
int mid = (l + r) >> 1;pushdown(x,l,r);
if(R <= mid) modify(lc,l,mid,L,R,d);
else if(L > mid) modify(rc,mid+1,r,L,R,d);
else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
sm[x] = sm[lc]+sm[rc];
}
inline void modify2(int x,int l,int r,int L,int R,int d){
if(L > R) return;
if(l == L && r == R){
cover2(x,l,r,d);
return;
}
int mid = (l + r) >> 1;pushdown(x,l,r);
if(R <= mid) modify2(lc,l,mid,L,R,d);
else if(L > mid) modify2(rc,mid+1,r,L,R,d);
else modify2(lc,l,mid,L,mid,d),modify2(rc,mid+1,r,mid+1,R,d);
sm[x] = sm[lc]+sm[rc];
}
inline int query(int x,int l,int r,int L,int R){
if(L > R) return 0;
if(l == L && r == R) return sm[x];
int mid = (l + r) >> 1;pushdown(x,l,r);
if(R <= mid) return query(lc,l,mid,L,R);
if(L > mid) return query(rc,mid+1,r,L,R);
return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R);
}
inline int queryt(int x,int l,int r,int p){
if(l == r) return ts[x];
int mid = (l + r) >> 1;pushdown(x,l,r);
if(p <= mid) return queryt(lc,l,mid,p);
else return queryt(rc,mid+1,r,p);
}
inline void build(int x,int l,int r){
sm[x] = r-l+1;tag[x] = cov[x] = -1;
if(l == r) return;
int mid = (l + r) >> 1;
build(lc,l,mid);build(rc,mid+1,r);
}
int dfn[MAXN],tp[MAXN],son[MAXN],dep[MAXN],fa[MAXN],sz[MAXN],_;
inline void dfs1(int v){
dep[v] = dep[fa[v]]+1;sz[v] = 1;
for(int i = head[v];i;i = e[i].nxt){
if(e[i].to == fa[v]) continue;
fa[e[i].to] = v;dfs1(e[i].to);
sz[v] += sz[e[i].to];
son[v] = sz[son[v]] > sz[e[i].to] ? son[v] : e[i].to;
}
}
inline void dfs2(int v,int tp=1){
dfn[v] = ++_;::tp[v] = tp;
if(son[v]) dfs2(son[v],tp);
for(int i = head[v];i;i = e[i].nxt){
if(e[i].to == fa[v] || e[i].to == son[v]) continue;
dfs2(e[i].to,e[i].to);
}
}
int tim[MAXN];
inline void modify(int x,int y){
if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
if(son[y]) modify(1,1,n,dfn[son[y]],dfn[son[y]],0);
while(tp[x] != tp[y]){
if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
if(son[tp[x]]) modify(1,1,n,dfn[son[tp[x]]],dfn[x],_);
modify2(1,1,n,dfn[tp[x]],dfn[tp[x]],_);
tim[tp[x]] = _;
x = fa[tp[x]];
if(son[x]) modify(1,1,n,dfn[son[x]],dfn[son[x]],0);
}
if(dep[x] > dep[y]) std::swap(x,y);
modify(1,1,n,dfn[x],dfn[y],_);
modify(1,1,n,dfn[x],dfn[x],0);
}
inline int query(int x,int y){
int res = 0;
while(tp[x] != tp[y]){
if(dep[tp[x]] < dep[tp[y]]) std::swap(x,y);
if(son[tp[x]]) res += query(1,1,n,dfn[son[tp[x]]],dfn[x]);
if(tim[tp[x]] < std::max(queryt(1,1,n,dfn[fa[tp[x]]]),queryt(1,1,n,dfn[tp[x]]))) res++;
x = fa[tp[x]];
}
if(dep[x] > dep[y]) std::swap(x,y);
if(son[x]) res += query(1,1,n,dfn[son[x]],dfn[y]);
return res;
}
int main(){
scanf("%d",&n);
FOR(i,2,n){
int u,v;scanf("%d%d",&u,&v);
add(u,v);
}
scanf("%d",&q);
dfs1(1);dfs2(1);build(1,1,n);
FOR(i,1,n) tim[i] = -1;
FOR(i,1,q){
_ = i;int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
// if(i == 2) FF = 1;
if(opt == 1) modify(x,y);
else printf("%d
",query(x,y));
}
return 0;
}