A
01 矩阵，每次可以对一个子矩阵取反，问最少多少次操作后，存在一条只向下或右走，只经过 0，从左上角到右下角的路径。
\(n,m\le 1000\).
这个 dp 还是非常 trival 的。
#include<bits/stdc++.h>
#define N 1010
#define inf (1<<25)
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
bool b[N][N];
int n,m,f[N][N],t1,t2;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(i==1&&j==1){
f[i][j]=b[i][j];
continue;
}
if(!b[i][j])t1=i>1?f[i-1][j]:inf,t2=j>1?f[i][j-1]:inf;
else t1=i>1?f[i-1][j]+(!b[i-1][j]):inf,t2=j>1?f[i][j-1]+(!b[i][j-1]):inf;
f[i][j]=min(t1,t2);
}
printf("%d\n",f[n][m]);
return 0;
}
B
每次选择树上的两个叶子节点，将它们路径上每个点的值减一。当路径存在为 0 的数时操作不合法，问能否清空所有点.
\(n\le 10^5\)，\(0\le a_i\le 10^9\).
先对 \(n=2\) 的情况特判。然后选择一个度非 \(1\) 的点作为根。
设 \(f_u\) 为点 \(u\) 可以向上拓展的路径数量。显然对于叶子节点有 \(f_u=a_u\).
设 \(\displaystyle s_u=\sum_{v\in\operatorname{son}(u)}f_v\)，即从儿子拓展上来的路径条数。
路径可以合并或者继续往上拓展。
后者为 \(f_u\)，前者为 \(\displaystyle\frac{s_u-f_u}{2}\).
两者每两条清楚一个石头，后者每一条清除一个石头，所以有
\[a_u=\frac{s_u-f_u}{2}+f_u=\frac{s_u+f_u}{2} \]得到
\[f_u=2a_u-s_u \]思考如何判定，显然应有 \(f_u,s_u\ge0\).
-
\(f_u\le a_u\)，穿过 \(u\) 的路径不可能多于 \(a_u\).
-
\(\displaystyle\frac{s_u-f_u}{2}\le s_u-\max_{v\in\operatorname{son}(u)}f_v\)，儿子提供的路径可能有剩余，每次令最多的分支与最少的分支配对，满足这个条件则一定有合法的配对方案。
当 \(u\) 为根时额外要求 \(f_u=0\).
#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int T,n,deg[N],rt;
int head[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
nxt[++tot]=head[u];
ver[tot]=v;
head[u]=tot;
}
ll a[N],f[N],s[N],mf[N];
void dfs(int u,int fa){
if(deg[u]==1){
f[u]=a[u];
s[fa]+=f[u],mf[fa]=max(mf[fa],f[u]);
return;
}
for(int i=head[u],v;i;i=nxt[i]){
if((v=ver[i])!=fa)dfs(v,u);
}
f[u]=2*a[u]-s[u];
s[fa]+=f[u],mf[fa]=max(mf[fa],f[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);
deg[u]++,deg[v]++;
}
if(n==2){
printf(a[1]==a[2]?"YES\n":"NO\n");
return 0;
}
for(int i=1;i<=n;i++)
if(deg[i]!=1){rt=i;break;}
dfs(rt,0);
bool flag=true;
for(int u=1;u<=n;u++){
if(f[u]<0||s[u]<0||f[u]>a[u]||s[u]-f[u]>(s[u]-mf[u])*2){
flag=false;break;
}
}
if(f[rt])flag=false;
printf(flag?"YES\n":"NO\n");
return 0;
}
C
对于有向图的每一条边，判断其方向改变后强连通分量数目是否改变。
\(n\le 1000\)，\(m\le 2\times 10^5\).
\(1.\) \(u,v\) 在一个 scc 内。
个数不可能增加，该 scc 可能被破坏。
不变当且仅当存在一条 \(u\rightarrow v\) 的路径，且不经过该边。
\(2.\) \(u,v\) 不在一个 scc 内。
若存在不含该边的 \(u\rightarrow v\) 的路径，数量加一。
记 \(f(u,v)\) 表示 \(u,v\) 在同一个 scc 内，\(g(u,v)\) 表示存在不含边 \(u\rightarrow v\) 的 \(u\rightarrow v\) 的路径。
那么边 \(u\rightarrow v\) 的答案为 \(1\) 当且仅当 \(f(u,v)\)，\(g(u,v)\) 二者之一为 \(1\).
\(f\) 也就是是否存在 \(v\rightarrow u\) 的路径，可以直接 \(O(nm)\) dfs 出来，考虑如何求解 \(g\).
对于每个 \(u\) 试求出 \(g(u,v)\).
从 \(u\) 开始 dfs，将 \(u\) 的边表顺序翻转，再次 dfs.
若 \(v\) 在两个 dfs 树中深度均为 \(1\)，则 \(g(u,v)=0\)，否则为 \(1\).
- 若 \(g(u,v)=0\)，\(v\) 在两个 dfs 树中深度均为 \(1\).
思考一下其实比较显然。容易用 vector 实现。
存在 \(\displaystyle O(\frac{n^3}{\omega}+m)\) 和 \(O(m)\) 的做法。
#include<bits/stdc++.h>
#define N 1010
#define M 200010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,U[M],V[M];
vector<int>e[N];
bool f[N][N],g[N][N],vis[N];
void dfs1(int u){
vis[u]=true;
for(auto v:e[u])
if(!vis[v])dfs1(v);
}
void dfs2(int u,int rt){
vis[u]=true;
for(auto v:e[u]){
if(vis[v]&&u==rt)g[rt][v]=true;
if(!vis[v])dfs2(v,rt);
}
}
void dfs3(int u,int rt){
vis[u]=true;
for(int i=e[u].size()-1,v;i>=0;i--){
v=e[u][i];
if(vis[v]&&u==rt)g[rt][v]=true;
if(!vis[v])dfs3(v,rt);
}
}
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;i++){
u=U[i]=read(),v=V[i]=read();
e[u].push_back(v);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis)),dfs1(i);
for(int j=1;j<=n;j++)
f[j][i]=vis[j];
memset(vis,0,sizeof(vis)),dfs2(i,i);
memset(vis,0,sizeof(vis)),dfs3(i,i);
}
for(int i=1;i<=m;i++){
bool tp=(f[U[i]][V[i]]+g[U[i]][V[i]])&1;
printf(tp?"diff\n":"same\n");
}
return 0;
}
D
初始有 \(n\) 个白色的球。
给一个操作序列，\(r\) 表示可以选择一段球染为红色，\(b\) 表示可以选择一段红球染为蓝色，可以不染。
问最终球的颜色序列的方案总数。
\(n,k\le70\).
判定颜色序列能否生成
定义颜色序列 \(C\) 的最简操作序列 \(P\)，表示序列 \(P\) 能染出 \(C\)，但其任意子序列反之。
不考虑 \(W\)，不妨将极长的相同颜色视为一段，这样 \(R\) 和 \(B\) 交错。
若有 \(k\) 个蓝色段，那么所需染色次数应为 \(k+1\) 次。
还有染色顺序的限制。若要做 \(a\) 次 \(b\)，最好的方案是：先做一次 \(r\)，再做 \(a-1\) 次 \(b\)，然后染一大段 \(B\)，接着在这一段上染完剩下的 \(R\).
对最简操作序列的充要要求为：个数 \(k+1\)，第一个为 \(r\)，第二个为 \(b\)，后面任意。
然后考虑有 \(W\) 分隔的多段有色区间。
不考虑纯红色段，设有 \(c\) 个杂色段。现在要在给定的操作序列中选出 \(c\) 个不交的子序列作为每个有色区间的最简操作序列。
应先选出 \(c\) 个子序列 \(\{r,b\}\) 作为它们的开头。
接下来为每个最简操作序列添加指定数目的字符且满足在开头的 \(\{r,b\}\) 右侧。
记第 \(i\) 个 \(\{r,b\}\) 后剩余的未选择字符数目为 \(t_i\)，对应最简操作序列需 \(s_i\) 个字符。
经典贪心策略，按 \(t_i\) 从大到小（按开头位置从左到右）排序，依次考虑并尽量靠左取字符。
形式化地，有解的充要条件为
\[\forall i,t_i\ge\sum_{j=i}^{c}s_j \]不难发现将 \(s\) 降序排列更优。
考虑有 \(a\) 个纯红色段的情况，由贪心可知应取出 \(a\) 个靠前的 \(r\) 处理。
DP 计数
Part 1
枚举 \(a,c\)，不难确定 \(t_{1\sim c}\).
考虑确定 \(s\) 后如何计算颜色序列方案数。
先考虑颜色段之间的排列顺序，杂色段和纯红色段混合的方案数为 \(\displaystyle\binom{a+c}{a,c}\).
杂色段内部顺序数，即 \(s\) 的不同排列数，记 \(\displaystyle c_i=\sum_{j}[s_j=i]\)，方案数应为 \(\large\displaystyle\frac{(\sum_{i}c_i)!}{\prod_{i}c_i!}\).
考虑确定顺序后的方案数，将各个长度不定的颜色段视为装球的盒子。
对于杂色段对应的 \(s_i\)，总字符数为 \(s_i+2\)，蓝色段个数为 \(s_i+1\)，会产生 \(2s_i+1\) 个至少有一个球的颜色段，以及两端的 \(2\) 个可以为空的红球段。
对于 \(a\)，会产生 \(a\) 个至少有一个球的纯红颜色段。
对于 \(W\)，会产生 \(a+c-1\) 至少有一个球的纯白颜色段，以及两端的 \(2\) 个可以为空的白球段。
综上，非空盒个数为 \(2\sum s_i+c+2a-1\)，可空盒为个数为 \(2c+2\)，总球数为 \(n\)，不难用组合数计算答案。
Part 2
现在对所有不同的 \(\{s\}\) 进行统计。
记 \(dp_{i,j,k}\) 为填写了 \(s_{i\sim c}\)，目前 \(\sum s=j\)，且 \(s_i=k\) 的方案数。
枚举在 \(s\) 中选取多少 \(k\)，有转移
\[dp_{i,j,k}=\sum_{p\ge1}\binom{c-i+1}{p}\sum_{g<k}dp_{i+p,j-pk,g} \]这个组合数用于处理多重排列，是将 \(p\) 个 \(k\) 归并入目前的 \(s\) 的方案数。
对于前文提到的充要条件
\[\forall i,t_i\ge\sum_{j=i}^{c}s_j \]这里体现为 \(j\le t_i\) 且 \(\forall p'\in[1,p]\)，\(j-p'k\le t_{i+p'}\).
所求答案为 \(\sum dp_{1,j,k}\).
这个 dp 方程的复杂度是 \(O(n^4\log n)\)，前缀和优化可做到 \(O(n^3\log n)\).
枚举 \(a,c\) 后总复杂度 \(O(n^5\log n)\) 小常数。
这题放了 \(\rm 4s\) 还是能过的，只不过代码真的太抽象了。贺完跑路。
#include<bits/stdc++.h>
#define N 75
#define _N 45
#define M 205
#define P 1000000007
using namespace std;
void add(int &x,int y){
x+=y;
if(x>=P)x-=P;
}
int n,m,ans;char a[N];
int t[N],cnt[N],w[N],binom[M][M],dp[N][_N][_N];
bool vis[N];
int solve(int C,int A){
if(!A&&!C)return 1;
int now=0,ret=0;
t[0]=0,memset(vis,0,sizeof(vis)),memset(dp,0,sizeof(dp));
for(int i=1,pos;i<=m;i++){
if(a[i]=='b')continue;
if(now<C){
pos=0,now++;
for(int j=i+1;j<=m;j++){
if(a[j]=='b'&&!vis[j]){
pos=j;break;
}
}
if(!pos)return 0;
vis[i]=vis[pos]=true,t[++t[0]]=pos;
}
else if(now<A+C)now++,vis[i]=true;
}
if(now<A+C)return 0;
for(int i=m;i;i--)
cnt[i]=cnt[i+1]+(!vis[i]);
for(int i=1;i<=t[0];i++)
w[i]=cnt[t[t[0]-i+1]]+i;
dp[0][0][0]=1;
for(int i=0;i<t[0];i++)
for(int j=0;j<=w[i]&&(j+A)*2-1<=n;j++)
for(int k=1,s=dp[i][j][0];j+k<=w[i+1]&&(j+k+A)*2-1<=n;k++){
for(int l=1;i+l<=t[0]&&j+k*l<=w[i+l]&&(j+k*l+A)*2-1<=n;l++)
add(dp[i+l][j+k*l][k],1ll*s*binom[i+l][l]%P);
add(s,dp[i][j][k]);
}
for(int i=0,s,t1,t2;i<=w[t[0]]&&(i+A)*2-1<=n;i++){
s=0,t1=(i+A)*2-1,t2=C*2+2;
for(int j=0;j<=i;j++)
add(s,dp[t[0]][i][j]);
add(ret,1ll*s*binom[n+t2-1][t1+t2-1]%P);
}
ret=1ll*ret*binom[C+A][C]%P;
return ret;
}
int main(){
scanf("%d%d%s",&n,&m,a+1);
binom[0][0]=1;
for(int i=1;i<M;i++){
binom[i][0]=binom[i][i]=1;
for(int j=1;j<M;j++)
binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%P;
}
int ans=0;
for(int C=0;C*2<=m;C++)
for(int A=0;C*2+A<=m;A++)
add(ans,solve(C,A));
printf("%d\n",ans);
return 0;
}
打摆分数 \(100+0+40+0=140\).
AC 第一题，赢！
标签：le,int,sum,vis,ch,序列,2023.8 From： https://www.cnblogs.com/SError0819/p/17609927.html