ABC263.

A. Full House

#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[15];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
signed main() {
	for(int i=1;i<=5;++i) ++h[read()];
	int f1=0, f2=0;
	for(int i=1;i<=13;++i) {
		if(h[i]==3) f1=1;
		else if(h[i]==2) f2=1;
	}
	if(f1&&f2) puts("Yes"); else puts("No");
}

B. Ancestor

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500;
int n, dep[N];
vector<int> p[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void dfs(int x,int fa) {
	dep[x]=dep[fa]+1;
	for(auto y:p[x]) {
		if(y==fa) continue;
		dfs(y,x);
	}
}
signed main() {
	n=read();
	for(int i=2;i<=n;++i) {
		int pp=read();
		p[i].push_back(pp), p[pp].push_back(i);
	}
	dfs(1,0);
	printf("%lld\n",dep[n]-1);
}

C. Monotonically Increasing

搜

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50;
int n, m, len, ans[N], c[N][N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void print(int* a) {
	for(int i=1;i<=n;++i) printf("%lld%c",a[i]," \n"[i==n]);
}
void dfs(int pos,int now) {
	if(now==n) { print(ans); return; }
	for(int i=pos+1;i<=m;++i) {
		ans[now+1]=i;
		dfs(i,now+1);
		ans[now+1]=0;
	}
}
signed main() {
	n=read(), m=read();
	dfs(0,0);
}

D. Left Right Operation

不难发现，让修改的前缀和后缀交错是没有任何意义的，所以可以认为 \(x\) 严格小于 \(n-y+1\)。

仿照 \(DP\) 的套路，注意到可以直接维护 \(p_i\) 表示 \([1,i]\) 的最小值，\(q_i\) 表示 \([i,n]\) 的最小值。 \[ p_i = \min\{ p_{i-1}+a_i,L \cdot i \} \]

\[ q_i = \min\{ q_{i+1}+a_i,R \cdot (n-i+1) \} \]

找到最小的 \(p_i + q_{i+1}\) 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n, L, R, ans, a[N], p[N], q[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
signed main() {
	n=read(), L=read(), R=read();
	p[0]=p[n+1]=0;
	for(int i=1;i<=n;++i) ans+=a[i]=read(), p[i]=min(p[i-1]+a[i],L*i);
	for(int i=n;i;--i) q[i]=min(q[i+1]+a[i],R*(n-i+1));
	for(int i=0;i<=n;++i) {
		ans=min(ans,p[i]+q[i+1]);
	}
	printf("%lld\n",ans);
}

E. Sugoroku 3

设 \(f_i\) 为从 \(i\) 到 \(n\) 的期望步数，有 \(f_n =0\)。 \[ f_i = 1 + \frac{\sum_{j=1}^{a_i} f(i+j) }{a_i +1} + \frac{f_i}{a_i+1} \] 含义：\(1\) 是投掷骰子这一步，结果是正数的总期望值是第二项，结果是 \(0\) 意味着还要再 \(i\) 呆一次，期望值是第三项。

简单化简 \[ f_i = \frac{\sum_{j=1}^{a_i}f(i+j) + a_i + 1}{a_i} \] 那个和式可以用后缀和 \(O(1)\) 得到。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5, mod=998244353;
int n, a[N], s[N], f[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int fp(int x,int y) {
	int z=1; x%=mod;
	for(;y;x=x*x%mod,y>>=1) if(y&1) z=z*x%mod;
	return z;
}
signed main() {
	n=read();
	for(int i=1;i<=n-1;++i) a[i]=read();
	f[n]=0;
	for(int i=n-1;i;--i) {
		int S=((s[i+1]-s[i+a[i]+1])%mod+a[i]+1)%mod;
		f[i]=S*fp(a[i],mod-2)%mod;
		s[i]=(s[i+1]+f[i])%mod;
	}
	printf("%lld\n",(f[1]+mod)%mod);
}

F. Tournament

人数是 \(2\) 的整数次幂，考虑一个类似分治的做法。

由于最终一定会留下一个获胜的人，设 \(f_i\) 为 \(i\) 获胜的最大收益。注意 \(C_{i,j}\) 是第 \(i\) 个人恰好赢了 \(j\) 场得到的收益，如果 \(i\) 多赢了一场，那么就要获得 \(C_{i,j+1}\)，去掉 \(C_{i,j}\)。

考虑一个自底向上的过程 \(solve(l,r,d)\)，表示编号在 \([l,r]\) 中的人，此时是第 \(d\) 场。令 \(mid = \frac{l+r}{2}\)。

在更新信息之前，设 \(p = \max_{i=l}^{mid}{\{ f_i \}}\)，\(q = \max_{i=mid+1}^r{\{ f_i \}}\)。

由于能够自由安排比赛，假设 \([l,mid]\) 中的人全部胜出，那么有 \(C_{i,d} - C_{i,d-1} \rightarrow f_i\)。由于 \(i\) 胜利之后必然有一个人告负，所以对于每个胜利者，都让打败的人在第 \(d-1\) 层得到的收益最大即可，所以 \(C_{i,d} - C_{i,d-1} + q \rightarrow f_i\)

反过来，若 \(i \in [mid+1,r]\)，\(C_{i,d} - C_{i,d-1} + p \rightarrow f_i\)。

答案为 \(\max{\{f_i \}}\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=16, mod=998244353;
int n, c[(1<<16)+5][N+5], f[(1<<16)+5];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve(int l,int r,int d) {
	if(l==r) return;
	int mid=(l+r)/2;
	solve(l,mid,d-1), solve(mid+1,r,d-1);
	int p=-1, q=-1;
	for(int i=l;i<=mid;++i) p=max(p,f[i]);
	for(int i=mid+1;i<=r;++i) q=max(q,f[i]);
	for(int i=l;i<=mid;++i) f[i]+=c[i][d]-c[i][d-1]+q;
	for(int i=mid+1;i<=r;++i) f[i]+=c[i][d]-c[i][d-1]+p;
}
signed main() {
	n=read();
	for(int i=1;i<=1<<n;++i) for(int j=1;j<=n;++j) c[i][j]=read();
	solve(1,1<<n,n);
	int ans=0;
	for(int i=1;i<=1<<n;++i) ans=max(ans,f[i]);
	printf("%lld\n",ans);
}

G. Erasing Prime Pairs

注意到，如果把奇数作为左部点，偶数作为右部点。如果一个左部点和一个右部点相加是个质数，那么在他们之间连边，这样就能形成一张二分图。而奇数与奇数，偶数与偶数的和必然不是质数，每个数能够使用多次，求它的最大多重匹配即可。

但是存在一个特例，数字 \(1\)。\(1\) 可以和自身匹配，也可以和偶数匹配。

一个错误的想法是直接将 \(1\) 加入图中，用最大流算法求出最大多重匹配之后，找到 \(1\) 在残量网络中对应的边，设其容量为 \(w\)，则让答案加上 \(\lfloor \frac{w}{2} \rfloor\)，含义是让剩下的 \(1\) 两两配对。

这个想法错在可能会有剩下的 \(1\)，这个 \(1\) 可能和没有在最大多重匹配之中的点匹配。

正确的做法是先不将 \(1\) 加入图中，跑出最大匹配。然后将 \(1\) 有关的边加入残量网络中，再跑一次最大匹配（因为 \(1\) 自己匹配和与别的点匹配，贡献都是 \(1\)），最后加上 \(\lfloor \frac{w}{2} \rfloor\) 即可。此时如果还有剩下的 \(1\)，那么这个 \(1\) 既不能和其他数匹配，又不能自己匹配，只能扔掉了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205, inf=1e15;
int n, s, t, one, ans, a[N], b[N], d[N];
int tot=1, h[N], to[6*N], w[6*N], nxt[6*N];
void add(int x,int y,int z) {
	to[++tot]=y, w[tot]=z, nxt[tot]=h[x], h[x]=tot;
}
void addedge(int x,int y,int z) { add(x,y,z), add(y,x,0); }
bool bfs() {
	queue<int> q;
	for(int i=0;i<=n+1;++i) d[i]=0;
	d[s]=1, q.push(s);
	while(q.size()) {
		int x=q.front(); q.pop();
		for(int i=h[x];i;i=nxt[i]) {
			int y=to[i], z=w[i];
			if(d[y]||!z) continue;
			d[y]=d[x]+1;
			q.push(y);
			if(y==t) return 1;
		}
	}
	return 0;
}
int dfs(int x,int flow) {
	if(x==t||!flow) return flow;
	int res=flow;
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i], z=w[i];
		if(d[y]!=d[x]+1||!z) continue;
		int k=dfs(y,min(res,z));
		if(!k) d[y]=0; else w[i]-=k, w[i^1]+=k, res-=k;
		if(!res) return flow;
	}
	return flow-res;
}
int dinic() {
	int ans=0;
	while(bfs()) ans+=dfs(s,inf);
	return ans;
}
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
bool isprime(int x) {
	for(int i=2;i*i<=x;++i) if(x%i==0) return 0;
	return 1;
}
signed main() {
	n=read();
	s=0, t=n+1;
	for(int i=1;i<=n;++i) {
		a[i]=read(), b[i]=read();
		if(a[i]&1) {
			if(a[i]==1) continue;
			addedge(s,i,b[i]);
		} else addedge(i,t,b[i]);
	}
	for(int i=1;i<=n;++i) if(a[i]&1) for(int j=1;j<=n;++j) {
		if(!(a[j]&1)&&isprime(a[i]+a[j])) addedge(i,j,inf);
	}
	ans=dinic();
	for(int i=1;i<=n;++i) if(a[i]==1) {
		addedge(s,i,b[i]), one=tot;
		for(int j=1;j<=n;++j) if(!(a[j]&1)&&isprime(1+a[j])) add(i,j,inf);
	}
	ans+=dinic();
	if(one) ans+=w[one-1]/2;
    // 边的编号从1开始
	printf("%lld\n",ans);
}