ARC107 游记
这场相比上次还算好吧，涨了一点分。
F 比赛时还是没有想出来，网络流建模果然还是不太熟悉。
以后只写 D,E,F 的题解算了，前三题就不写了。
D Number of Multisets
题意简述
询问有多少个可重集 (S) 满足 (|S|=n) 并且 (S) 中所有元素的和为 (k) 并且 (S) 中的元素都可以表示为 (frac{1}{2^x}(xge 0)) （ (2) 的非负整数次幂的倒数），答案对 (998244353) 取模。
(1le kle nle 3000) 。
题目分析
考虑 dp ，设 (dp(i,j,t)) 表示满足 (|S|=i) 并且 (S) 中所有元素的和为 (j imes frac{1}{2^t}) 并且 (S) 中的元素都可以表示为 (frac{1}{2^x}(xge t)) 的可重集 (S) 的数量，不难发现， (dp(i,j,t)) 的值其实和 (t) 无关，所以我们可以把 (t) 这一维去掉，只设 (dp(i,j)) 。
转移可以枚举有多少个元素是 (frac{1}{2^t}) ：
另一种转移方法，看是否存在一个元素 (frac{1}{2^t}) ：
使用第二种转移方法，时间复杂度 (mathcal O(nk)) ，当然可以通过推式子的方式由第一种转移方法推出第二种转移方法。
参考代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
int f;char c;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
static char q[64];int cnt=0;
if(!x)pc('0');if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=3005,mod=998244353;
int mo(const int x){
return x>=mod?x-mod:x;
}
int dp[maxn][maxn];
int main(){
int n,k;read(n),read(k);
dp[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=i;j>=1;--j){
dp[i][j]=mo(dp[i-1][j-1]+(j*2<=i?dp[i][j*2]:0));
}
}
write(dp[n][k]),pc('
');
return 0;
}
E Mex Mat
比赛时被这题卡了好久，好在最后想出来了。
题意简述
(n imes n) 的矩阵 (a) ，其中的每个数的取值为 ({0,1,2}) ，矩阵满足 (a_{x,y}=mbox{mex}(a_{x-1,y},a_{x,y-1})(xge 2,yge 2)) ，现在给出 (a_{1,i}) 和 (a_{i,1}) ，询问整个矩阵中 (0,1,2) 的出现次数。
(1le nle 5 imes 10^5) 。
题目分析
如果 (a_{x,y}=0) ，那么 (a_{x+1,y}) 和 (a_{x,y+1}) 就非 (0) ，那么 (a_{x+1,y+1}=0) ，所以一个 (0) 会沿斜线传递下去。
如果两个 (0) 相邻 1 ，那么就会变成这样：
0 0
010
010
010
010
...
如果两个 (0) 相邻 2 ，那么就会变成这样：
0 20
0120
0120
0120
0120
0120
....
或者这样：
0 10
0210
0210
0210
0210
0210
....
两个 (0) 在执行了若干步后要么相邻 (1) 要么相邻 (2) ，所以在执行若干步后必然满足 (a_{x+1,y+1}=a_{x,y}) ，所以我们就可以先往下往右递推出前若干步，然后就可以直接计算了。
我的程序选择了递推前 (10) 行和前 (10) 列，官方题解好像是递推了前 (4) 行，好像是说枚举了前 (4) 行的所有情况就能发现必然有 (a_{5,5}=a_{4,4}) 。
参考代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
int f;char c;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
static char q[64];int cnt=0;
if(!x)pc('0');if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=500005;
long long cnt[3];
int Ma[3][3]={{1,2,1},{2,0,0},{1,0,0}};
int A[maxn],B[maxn];
int main(){
int n;read(n);
for(int i=1;i<=n;++i)read(A[i]),++cnt[A[i]];
for(int i=2;i<=n;++i)read(B[i]),++cnt[B[i]];
if(n<=10){
for(int i=2;i<=n;++i){
A[i-1]=B[i];
for(int j=i;j<=n;++j)
++cnt[A[j]=Ma[A[j]][A[j-1]]];
B[i]=A[i];
for(int j=i+1;j<=n;++j)
++cnt[B[j]=Ma[B[j]][B[j-1]]];
}
}
else{
for(int i=2;i<=10;++i){
A[i-1]=B[i];
for(int j=i;j<=n;++j)
++cnt[A[j]=Ma[A[j]][A[j-1]]];
B[i]=A[i];
for(int j=i+1;j<=n;++j)
++cnt[B[j]=Ma[B[j]][B[j-1]]];
}
for(int i=10;i<=n;++i)
cnt[A[i]]+=n-i;
for(int i=11;i<=n;++i)
cnt[B[i]]+=n-i;
}
write(cnt[0]),pc(' '),write(cnt[1]),pc(' '),write(cnt[2]),pc('
');
return 0;
}
F Sum of Abs
题意简述
(n) 个点 (m) 条边的无向图，你可以花费 (A_i) 的代价删除 (i) 点，最终你的收益是所有连通块 (B_i) 的和的绝对值之和，请最大化收益减代价和。
(1le n,mle 300,1le A_ile 10^6,-10^6le B_ile 10^6) 。
题目分析
数据范围极力暗示网络流，问题就是如何建模。
假如 (S) 中的点构成了一个连通块，那么最后对收益的贡献就是 (max(sum_{uin S}B_u,-sum_{uin S}B_u)=max(sum_{uin S}B_u,sum_{uin S}(-B_u))) ，也就是说，在同一个连通块中的点的 (B_i) 对答案造成贡献时乘以的系数是相同的，即乘以 (1) 或者 (-1) 。
每个点有三种选择：删除（给答案贡献 (-A_i) ），给答案贡献 (B_i) 、给答案贡献 (-B_i) 。三选一模式，考虑使用最小割模型，将点 (u) 拆成两个点 (u_0,u_1) ，然后连边方法是 (S o u_0 o u_1 o T) ，割掉 (S o u_0) 表示给答案贡献 (B_i) ，割掉 (u_0 o u_1) 表示删除点 (u) （给答案贡献 (-A_i) ），割掉 (u_1 o T) 表示给答案贡献 (-B_i) ，这样的话在同一个连通块里的点必须选择在同一侧，即要么都和 (S) 相连要么都和 (T) 相连。
连边是这样的： (S o u_0) 流量为 (-B_i) ， (u_0 o u_1) 流量为 (A_i) ， (u_1 o T) 流量为 (B_i) 。由于流量不能为负数，所以三条边流量和答案需要集体加上 (mbox{abs}(B_i)) 。
如果在原图中 (u,v) 有连边，说明 (u,v) 必须要在同一边，也就是不能同时满足割掉 (S o u_0) 并且割掉 (v_1 o T) （此时相当于保留了 (u_0 o u_1 o T) 和 (S o v_0 o v_1) ），或者不能同时满足割掉 (u_1 o T) 并且割掉 (S o v_0) （此时相当于保留了 (S o u_0 o u_1) 和 (v_0 o v_1 o T) ），所以 (v_1 o u_0) 流量 (infty) ， (u_1 o v_0) 流量 (infty) 。
参考代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
int f;char c;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
static char q[64];int cnt=0;
if(!x)pc('0');if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=305,maxm=305;
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxm*4+maxn*4];
int hd[maxn*2],num=1;
void qwq(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]),hd[u]=num;
}
void qvq(int u,int v,int w){
qwq(u,v,w);qwq(v,u,0);
}
int S=0,T=1,dis[maxn*2],q[maxn*2];
int bfs(void){
memset(dis,0,sizeof dis);
int fro=0,bac=0;dis[q[bac++]=S]=1;
while(fro<bac){
int u=q[fro++];
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(w&&!dis[v]){
dis[q[bac++]=v]=dis[u]+1;
}
}
}
return dis[T];
}
int cur[maxn*2];
int dfs(int u,int ep){
if(u==T)return ep;int re=0;
for(int&i=cur[u];i;i=e[i].nt){
int v=e[i].v,w=e[i].w;
if(w&&dis[v]==dis[u]+1){
int tmp=dfs(v,min(ep,w));
re+=tmp;ep-=tmp;
e[i].w-=tmp;e[i^1].w+=tmp;
if(!ep)break;
}
}
return re;
}
int dinic(void){
int re=0;
while(bfs()){
memcpy(cur,hd,sizeof hd);
re+=dfs(S,inf);
}
return re;
}
int A[maxn],B[maxn];
int main(){
int n,m;read(n),read(m);
for(int i=1;i<=n;++i)read(A[i]);
for(int i=1;i<=n;++i)read(B[i]);
int ans=0;
for(int i=1;i<=n;++i){
int a=A[i],b=B[i];
if(b<0)ans-=b,qvq(S,i*2 ,-2*b),qvq(i*2,i*2+1,a-b);
else ans+=b,qvq(i*2+1,T, 2*b),qvq(i*2,i*2+1,a+b);
}
for(int i=1;i<=m;++i){
int u,v;
read(u),read(v);
qvq(u*2+1,v*2,inf);
qvq(v*2+1,u*2,inf);
}
write(ans-dinic()),pc('
');
return 0;
}
总结
前几天还搞了图论来着，结果 F 网络流建模还是没有独立想出来，自己的思维建模能力还是不够啊。