Preface
开始往回做AGC，发现这场是真的可以算做过的所有AGC里最水的一场了
A - Kenken Race
首先发现从(x)能走到(y)不管越过人的情况至少需要满足没有连续的两个障碍
如果需要让一个人越过另一个人怎么办，稍加分析我们发现只要用连续三个空地即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a,b,c,d,lst; char s[N]; bool flag;
int main()
{
RI i; scanf("%d%d%d%d%d%s",&n,&a,&b,&c,&d,s+1);
for (i=a;i<c;++i) if (s[i]=='#'&&s[i+1]=='#') return puts("No"),0;
for (i=b;i<d;++i) if (s[i]=='#'&&s[i+1]=='#') return puts("No"),0;
if (c<d) return puts("Yes"),0; for (flag=0,i=b;i<=d&&!flag;++i)
if (s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.') flag=1;
return puts(flag?"Yes":"No"),0;
}
B - ABC
考虑变换过程就是一个把(A)不断右移的过程
考虑数出当前有多少个没被挡住的(A)，如果有一段(BC)那么可以让这些(A)都跳过来
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,cur; char s[N]; long long ans;
int main()
{
RI i; for (scanf("%s",s+1),n=strlen(s+1),i=1;i<n;++i)
if (s[i]=='A') ++cur; else if (s[i]=='B')
{ if (s[i+1]=='C') ans+=cur,++i; else cur=0; } else cur=0;
return printf("%lld",ans),0;
}
C - Tests
刚开始脑抽了写挂了好多地方调的时间比后面题目都长
首先有一个很显然的结论，当(a_ile b_i)时我们令(c_i=l_i)，否则(c_i=r_i)
答案具有单调性，考虑二分答案(t)
考虑一个位置对总和的贡献是单调不降的，考虑如果我们要给一个位置增加必然要么加满要么把次数加完
因此我们设(c1=lfloor frac{t}{x} floor,c2=toperatorname{mod} x)，显然只要枚举一个位置填(c2)，然后在剩下的位置中找出填满时贡献最大的前(c1)个位置填满即可
按最大贡献排序之后用前缀和显然可以(O(n))check
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=100005;
struct element
{
int l,r,b; LL v;
friend inline bool operator < (const element& A,const element& B)
{
return A.v>B.v;
}
}a[N]; int n,x,b[N]; LL ans;
inline bool check(const LL& t)
{
int c1=t/x,c2=t%x; LL cur=0,dlt=0,ret=0; RI i; if (c1==n) return 1;
for (i=1;i<=c1;++i) cur+=1LL*(x-a[i].b)*a[i].r; for (i=c1+1;i<=n;++i) dlt+=1LL*a[i].b*a[i].l;
for (i=c1+1;i<=n;++i) if (cur+1LL*(c2>=a[i].b?a[i].r:a[i].l)*(c2-a[i].b)-(dlt-1LL*a[i].b*a[i].l)>=0) return 1;
for (cur+=1LL*(x-a[c1+1].b)*a[c1+1].r,dlt-=1LL*a[c1+1].b*a[c1+1].l,i=1;i<=c1;++i)
if (cur-(1LL*(x-a[i].b)*a[i].r)+1LL*(c2>=a[i].b?a[i].r:a[i].l)*(c2-a[i].b)-dlt>=0) return 1; return 0;
}
int main()
{
RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i)
scanf("%d%d%d",&a[i].b,&a[i].l,&a[i].r),a[i].v=1LL*a[i].b*a[i].l+1LL*(x-a[i].b)*a[i].r;
sort(a+1,a+n+1); LL l=0,r=1LL*x*n,mid; while (l<=r)
if (check(mid=l+r>>1)) ans=mid,r=mid-1; else l=mid+1;
return printf("%lld",ans),0;
}
D - Manhattan Max Matching
陈指导告诉我是网络流了，然后最近法老讲了这个技巧就很快会做了
首先我们考虑暴力建一个二分图跑MCMF，因为边数是(O(n^2))级别的所以直接GG了
考虑把绝对值拆开，运用经典套路：
[|x_1-x_2|+|y_1-y_2|\
=max(x_1-x_2+y_1-y_2,x_1-x_2+y_2-y_1.x_2-x_1+y_1-y_2,x_2-x_1+y_2-y_1)
]
我们发现我们可以建立四个虚点，每次红色点向四个点分别连(x+y,x-y,-x+y,-x-y)的边，然后四个点向每个蓝色点分别连(-x-y,-x+y,x-y,x+y)的边即可
由于跑MCMF的时候求的是最长路，因此一定能找出正确的路径，这样边数就是(O(n))级别的了
#include<cstdio>
#include<queue>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=2100,M=20*N,INF=1e9;
int n,c,x,y,s,t;
namespace NF //Network_Flow
{
struct edge
{
int to,nxt,v,c;
}e[M]; queue <int> q; bool vis[N];
int head[N],cnt=1,cap[N],pre[N],lst[N]; LL dis[N];
#define to e[i].to
inline bool SPFA(CI s,CI t)
{
RI i; for (i=s;i<=t;++i) dis[i]=-1e18,pre[i]=-1;
q.push(s); dis[s]=0; cap[s]=INF; vis[s]=1; while (!q.empty())
{
int now=q.front(); q.pop(); vis[now]=0;
for (i=head[now];i;i=e[i].nxt) if (e[i].v&&dis[now]+e[i].c>dis[to])
{
dis[to]=dis[now]+e[i].c; cap[to]=min(cap[now],e[i].v);
pre[to]=now; lst[to]=i; if (!vis[to]) vis[to]=1,q.push(to);
}
}
return ~pre[t];
#undef to
}
inline void addedge(CI x,CI y,CI v,CI c)
{
e[++cnt]=(edge){y,head[x],v,c}; head[x]=cnt;
e[++cnt]=(edge){x,head[y],0,-c}; head[y]=cnt;
}
inline LL MCMF(CI s,CI t)
{
LL ret=0; while (SPFA(s,t))
{
ret+=dis[t]*cap[t]; for (int nw=t;nw!=s;nw=pre[nw])
e[lst[nw]].v-=cap[t],e[lst[nw]^1].v+=cap[t];
}
return ret;
}
};
int main()
{
RI i; for (scanf("%d",&n),s=0,t=2*n+5,i=1;i<=n;++i)
scanf("%d%d%d",&x,&y,&c),NF::addedge(s,i,c,0),
NF::addedge(i,2*n+1,INF,x+y),NF::addedge(i,2*n+2,INF,x-y),
NF::addedge(i,2*n+3,INF,-x+y),NF::addedge(i,2*n+4,INF,-x-y);
for (i=1;i<=n;++i)
scanf("%d%d%d",&x,&y,&c),NF::addedge(n+i,t,c,0),
NF::addedge(2*n+1,n+i,INF,-x-y),NF::addedge(2*n+2,n+i,INF,-x+y),
NF::addedge(2*n+3,n+i,INF,x-y),NF::addedge(2*n+4,n+i,INF,x+y);
return printf("%lld",NF::MCMF(s,t)),0;
}
E - Complete Compress
刚开始没看数据范围以为是(O(nlog n))的，后来发现是(O(n^2))……
考虑我们枚举一个终点，现在每个点只需要向上移动了，所以我们求出一个(f_x)表示把(x)子树内所有有碎片的点移到(x)的代价和，答案就是(frac{f_{rt}}{2})？
我们发现这样显然有问题，因为对于某个点来说，在它同一个子树内的点是无法同时往上跳的
因此我们考虑对每个点再记一个(g_x)表示(x)子树内无法移动到(x)的点剩下多少次移动
考虑什么时候会有无法移动的情况，显然是在某个子树内的点太多了，其他所有子树都只和这个子树内的点移动都无法把它全部上移
我们对于每个点枚举一下每个子树，看看是否有一个子树是不合法的来更新即可
否则我们可以把(g_x)对(2)取模，因为此时一定存在一种移动方案将偶数时所有点移到(x)，奇数时只差一步
最后一个点作为根满足条件当且仅当(g_{rt}=0)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005,INF=1e9;
struct edge
{
int to,nxt;
}e[N<<1]; int n,head[N],cnt,x,y,f[N],sz[N],g[N],ans=INF; char s[N];
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt;
e[++cnt]=(edge){x,head[y]}; head[y]=cnt;
}
#define to e[i].to
inline void DFS(CI now,CI fa=0)
{
RI i; f[now]=g[now]=0; sz[now]=s[now]-'0';
for (i=head[now];i;i=e[i].nxt) if (to!=fa)
DFS(to,now),f[now]+=f[to]+sz[to],g[now]+=g[to]+sz[to],sz[now]+=sz[to];
int x,y; for (i=head[now];i;i=e[i].nxt) if (to!=fa)
if ((x=g[to]+sz[to])>(y=f[now]-(f[to]+sz[to]))) return (void)(g[now]=x-y); g[now]&=1;
}
#undef to
int main()
{
RI i; for (scanf("%d%s",&n,s+1),i=1;i<n;++i)
scanf("%d%d",&x,&y),addedge(x,y); for (i=1;i<=n;++i)
if (DFS(i),!g[i]) ans=min(ans,f[i]>>1);
if (ans==INF) puts("-1"); else printf("%d",ans); return 0;
}
F - RNG and XOR
首先我们有一个显然的暴力转移，设(f_x)表示第一次出现(x)的期望（(U=2^n-1)）
[f_x=
egin{cases}
sum_{yin U} f_{xoperatorname{xor} y} imes p_y+1 &(x
eq0)\
0&(x=0)\
end{cases}
]
显然当(x eq 0)是转移就是个异或卷积的形式，容易发现：
[f=fast p+h
]
其中(h=x+x^2+cdots +x^{2^n-1})，但是我们不知道(h)的常数项怎么办
由题意发现(sum_{tin U} p_t=1)，所以(fast p)每一项的系数和和(f)每一项的系数和相等，因此(h)的常数项为(-(2^n-1))
再移项化简一下就是：
[fast (p-1)=-h\
Leftrightarrow f=-hast(p-1)^{-1}
]
什么你说异或卷积的求逆是什么？考虑FWT中我们进行FWT时：
[h=fast gLeftrightarrow hat h=hat fcdothat g\
hat h_s=hat f_scdothat g_sLeftrightarrow hat f_s=frac{hat h_s}{hat g_s}
]
因此直接除即可，不难发现我们求出的(f)只是一组可行解，因为原来的(f_0=0)因此要将(f)的每一项都减去(f_0)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=18,mod=998244353;
int n,lim,cur,inv2,g[1<<N],f[1<<N],h[1<<N]; //f*g=h
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int sum(CI x,CI y)
{
int t=x+y; return t>=mod?t-mod:t;
}
inline int sub(CI x,CI y)
{
int t=x-y; return t<0?t+mod:t;
}
inline void FWT(int* f,CI opt)
{
for (RI i=1,j,k,x,y;i<lim;i<<=1) for (j=0;j<lim;j+=(i<<1)) for (k=0;k<i;++k)
x=f[j+k],y=f[i+j+k],f[j+k]=sum(x,y),f[i+j+k]=sub(x,y),
!~opt&&(f[j+k]=1LL*f[j+k]*inv2%mod,f[i+j+k]=1LL*f[i+j+k]*inv2%mod);
}
int main()
{
RI i; for (scanf("%d",&n),lim=1<<n,i=0;i<lim;++i)
scanf("%d",&g[i]),cur=sum(cur,g[i]);
for (cur=quick_pow(cur),i=0;i<lim;++i) g[i]=1LL*g[i]*cur%mod;
for (inv2=quick_pow(2),g[0]=sub(g[0],1),i=1;i<lim;++i) h[i]=mod-1;
for (h[0]=lim-1,FWT(g,1),FWT(h,1),i=0;i<lim;++i)
f[i]=1LL*h[i]*quick_pow(g[i])%mod; for (FWT(f,-1),i=0;i<lim;++i)
printf("%d
",sub(f[i],f[0])); return 0;
}
Postscript
E题送分F题就是板子，所以这场最难的是D题？