A. Remove One Character

容易发现 \(i,j\) 产生贡献当且仅当 \(\forall k\in[i,j],a_i=a_k=a_j\)，于是对于每个连通块分别计算贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,m;string s;
long long ans;
int main(){
	n=read();cin>>s;
	int cnt=1,pos=0;
	for(int i=1;i<n;i++){
		if(s[pos]!=s[i])pos=i,cnt=0;
		ans+=cnt;++cnt;
	}printf("%lld\n",ans);
	return 0;
}

B. Colorful Lines

首先离散化，考虑时光倒流计算贡献，那么若这一行/列已经被染过色则无贡献，否则贡献为行/列长度减去另一方向上已有直线个数。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=3e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int h,w,c,Q,b[2][maxn],C[2],vis[2][maxn];
long long ans[maxn];
struct query{int tp,id,col;}q[maxn];
int main(){
	h=read(),w=read(),c=read(),Q=read();
	for(int i=1,tp,id,col;i<=Q;i++){
		tp=read()-1,id=read(),col=read();
		q[i]=(query){tp,id,col};b[tp][++C[tp]]=id;
	}sort(b[0]+1,b[0]+1+C[0]);
	C[0]=unique(b[0]+1,b[0]+1+C[0])-b[0]-1;
	sort(b[1]+1,b[1]+1+C[1]);
	C[1]=unique(b[1]+1,b[1]+1+C[1])-b[1]-1;
	for(int i=1;i<=Q;i++){
		int tp=q[i].tp,id=q[i].id;
		q[i].id=lower_bound(b[tp]+1,b[tp]+1+C[tp],id)-b[tp];
	}C[0]=C[1]=0;
	for(int i=Q;i>=1;i--){
		int tp=q[i].tp,id=q[i].id,col=q[i].col;
		if(vis[tp][id])continue;vis[tp][id]=1;
		ans[col]+=(tp?h:w)-C[tp^1];++C[tp];
	}
	for(int i=1;i<=c;i++)
		printf("%lld ",ans[i]);puts("");
    return 0;
}

C. Digit Sum Minimization

考场上不会！其实是很简单的题目啊

首先我们自然的相法就是拼出最多的进位，这显然是正确的，我们想拼出尽量多的十，然后接尽量多的九。

仔细观察，其实我们只用拼出一个十，后面都拼九就可以，也就是 \(s_0+t_0\geqslant 10\)，\(i>1,s_i+t_i\geqslant 9\)

由于只有 \(s_0\) 和 \(t_0\) 是特殊的，于是考虑枚举这两个数就做完了。代码借鉴 He_Ren

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
#define str string
str s,t;
int n,m,cs[10],ct[10],ts[10],tt[10];
#define pip pair<int,pair<str,str>>
#define mkp make_pair
#define fi first
#define se second
inline pip calc(int a,int b){
	for(int i=1;i<=9;i++)ts[i]=cs[i],tt[i]=ct[i];
	string S(1,a+'0'),T(1,b+'0');int res=1;
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)if(i+j>=9){
			int c=min(ts[i],tt[j]);
			ts[i]-=c;tt[j]-=c;res+=c;
			S+=str(c,i+'0'),T+=str(c,j+'0');
		}
	res+=max(ts[9],tt[9]);
	for(int i=9;i>=1;i--)
		S+=str(ts[i],i+'0'),T+=str(tt[i],i+'0');
	reverse(S.begin(),S.end());
	reverse(T.begin(),T.end());
	return mkp(res,mkp(S,T));
} 
int main(){
	cin>>s>>t;
	pip ans=mkp(0,mkp(s,t));
	for(char c:s)cs[c-'0']++;
	for(char c:t)ct[c-'0']++;
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
			if(cs[i]&&ct[j]&&i+j>=10){
				cs[i]--,ct[j]--;
				ans=max(ans,calc(i,j));
				cs[i]++,ct[j]++;
			}
	cout<<ans.se.fi<<endl<<ans.se.se;
	return 0;
}

D. Zigzag Tree

简单题。肯定考虑树形背包，\(dp_{i,j,0/1}\) 表示 \(i\) 子树内，\(P_i\) 的排名为 \(j\)，\(P_i>P_{son_i}\) 的方案数。

合并的时候，可以枚举子树在 \(P_i\) 以前的个数，然后前缀和优化，时间 \(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=998244353;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int N=3e3+5;
int n,m,dp[N][N][2],S[N][N][2],ans,sz[N],f[N],g[N];
int beg[N],nex[N<<1],to[N<<1],e;
int fac[N<<1],ifc[N<<1],inv[N<<1];
inline int com(int x,int y){return 1ll*fac[x]*ifc[y]%mod*ifc[x-y]%mod;}
inline int Coef(int x,int y){return com(x+y,x);}
inline void add(int x,int y){
	++e;nex[e]=beg[x];beg[x]=e;to[e]=y;
	++e;nex[e]=beg[y];beg[y]=e;to[e]=x;
}
inline void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline void dfs(int x,int fa){
	sz[x]=1;dp[x][1][0]=dp[x][1][1]=1;
	for(int i=beg[x];i;i=nex[i]){
		int t=to[i];if(t==fa)continue;dfs(t,x);
		for(int a=1;a<=sz[x];a++){
			f[a]=dp[x][a][0],dp[x][a][0]=0;
			g[a]=dp[x][a][1],dp[x][a][1]=0;
		}
		for(int a=1;a<=sz[x];a++)
			for(int b=0;b<=sz[t];b++){
				int coef=1ll*com(a+b-1,b)*com(sz[x]+sz[t]-a-b,sz[t]-b)%mod;
				Add(dp[x][a+b][1],1ll*g[a]*coef%mod*S[t][b][0]%mod);
				Add(dp[x][a+b][0],1ll*f[a]*coef%mod*(S[t][sz[t]][1]-S[t][b][1]+mod)%mod);
			}
		sz[x]+=sz[t];
	}
	for(int i=1;i<=n;i++)f[i]=g[i]=0;
	for(int i=1;i<=n;i++){
		S[x][i][0]=S[x][i-1][0],S[x][i][1]=S[x][i-1][1];
		Add(S[x][i][0],dp[x][i][0]),Add(S[x][i][1],dp[x][i][1]);
	}
}
int main(){
	n=read();
	for(int i=1,x,y;i<n;i++)
		x=read(),y=read(),add(x,y);
	inv[1]=fac[0]=ifc[0]=1;
	for(int i=2;i<=n+n;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n+n;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1;i<=n+n;i++)
		ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
	dfs(1,0);
	for(int i=1;i<=n;i++)
		ans=(0ll+ans+dp[1][i][0]+dp[1][i][1])%mod;
	printf("%d\n",ans);
	return 0;
}

E. Increasing Minimum

对着 Froggay 的代码阅读理解的，没太懂细节，大概讲一下吧。

首先发现对于任意解其大小关系不变，于是只用使我们的构造解中的相等关系尽量多即为最优解。

我们不妨假设任意时刻，\(\max\limits_{i,j} |a_i-a_j|\leqslant 1\)，我们可以假设没有限制的位置为当前最小值。

整体加一当且仅当最近不重不漏地出现了每个出现过的元素，于是无解就好判断了。

最后再取那个当前的 \(\max a_i\)，再一个一个模拟减回去即可。

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=3e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,m,a[maxn],ans[maxn],las[maxn],cnt,lp,dep[maxn];
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		a[i]=read();
		if(!las[a[i]])++cnt;
		lp=max(lp,las[a[i]]);
		las[a[i]]=i;
		if(i-lp==cnt)dep[i]=dep[lp]+1;
		else dep[i]=inf+1;
	}int Mn=inf,pos=-1;
	for(int i=lp;i<=m;i++)
		if(dep[i]<=Mn)Mn=dep[i],pos=i;
	if(pos==-1)
		return puts("-1")&0;
	for(int i=1;i<=n;i++)ans[i]=Mn+1;
	for(int i=1;i<=pos;i++)ans[a[i]]--;
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);puts("");
	return 0;
}

F. Replace by Average

凸包？鸽了鸽了