文章目录

A题

题意简述：给你一个$m$个数的数列，现在规定把一个数列的$1,2,...,k$分成第一组，把$k+1,k+2,...,2k$分成第二组,…,这样把前$n\ast k$个数分成$n$组，现在给你$s$个数，你可以删去至多$m-n\ast k$个数使得新数列按照上述方式分组可以分出来至少一个组满足$s$个数都在里面出现（如果$s$个数中$a$出现$b$次则分出来满足条件的组中$a$出现至少$b$次），求任意方案。

---

思路：

我们用双指针统计一下就行了，注意细节。

代码：

#include
    
     #define ri register intusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}const int N=5e5+5;int cnt[N],tot[N],lim[N],a[N],okcnt=0,m,n,k,s,det=0;bool in[N];inline void check(int l,int r){
    	int blo=l==l/k*k?(l/k-1)*k+1:l/k*k+1;	if(r-blo+1-k>(n-m*k))return;	if(r-blo+1-k<=0)puts("0"),exit(0);	int ccnt=0;	for(ri i=blo;i<=r;++i)ccnt+=in[i];	cout<
     
      <<'\n';	for(ri i=blo,j=1;i<=r&&j<=r-blo+1-k;++i){
    		if(lim[a[i]]&&tot[a[i]]
      
       1)++det;	}	for(ri l=1,r=0;;){
    		while(r
      
     
    

---

B题

题意简述：给你两个等长的数字串$a,b$，你可以把$a$中的任意相邻两个数同时$+1/-1$，问能否把$a$变成$b$以及输出操作方案数和具体方案。

---

思路：

一道比较显然的贪心吧。

直接一位一位匹配就行了，如果aia_iai​比bib_ibi​小就给ai,ai+1a_i,a_{i+1}ai​,ai+1​同时加上bi−aib_i-a_ibi​−ai​；如果aia_iai​比bib_ibi​大就给aia_iai​和ai+1a_{i+1}ai+1​同时减去ai−bia_i-b_iai​−bi​；如果相等就跳过位置$i$。

然后构造方案直接暴力构造，因为可以证明每个数的增量是很小的。

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}typedef long long ll;const int N=1e5+5;char s[N];int n,a[N],b[N],det[N];ll ans=0;int main(){
    	n=read();	scanf("%s",s+1);	for(ri i=1;i<=n;++i)a[i]=s[i]^48;	scanf("%s",s+1);	for(ri i=1;i<=n;++i)b[i]=s[i]^48;	det[1]=b[1]-a[1];	for(ri i=2;i<=n;++i)det[i]=b[i]-det[i-1]-a[i];	if(det[n])return puts("-1"),0;	for(ri i=1;i
     
      0?det[i]:-det[i];	cout<
      
       <<'\n';	ans=min(ans,100000ll);	int p=1,cur=1,tmp;	while(ans--){
    		while(!det[p])++p,++cur;		while((det[cur]>0&&a[cur+1]==9)||(det[cur]<0&&a[cur+1]==0))++cur;		tmp=det[cur]>0?1:-1;		cout<
       
        <<' '<
        
         <<'\n';		a[cur]+=tmp,a[cur+1]+=tmp,det[cur]-=tmp;		cur=max(cur-1,p);	}	return 0;}
        
       
      
     
    

---

C题

题意简述：要求你压缩一个字符串，假设你将$S$压缩成了t1t2...tkt_1t_2...t_kt1​t2​...tk​，那么对于一个串tit_iti​。

若∣ti∣=1|t_i|=1∣ti​∣=1可以花$a$压缩，如果tit_iti​是t1t2..ti−1t_1t_2..t_{i-1}t1​t2​..ti−1​的子集可以花$b$压缩，问压缩的最小代价。

---

思路：

直接用$sam$加$dp$。

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}const int N=5005;int n,a,b,f[N];char s[N];namespace sam{
    	int son[N<<1][26],len[N<<1],link[N<<1],tot=1,last=1;	inline void insert(const int&x){
    		int p=last,np=++tot;		len[last=np]=len[p]+1;		while(p&&!son[p][x])son[p][x]=np,p=link[p];		if(!p){
    link[np]=1;return;}		int q=son[p][x],nq;		if(len[q]==len[p]+1){
    link[np]=q;return;}		len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q];		link[q]=link[np]=nq;		while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];	}}int main(){
    	n=read(),a=read(),b=read(),scanf("%s",s+1);	memset(f,0x3f,sizeof(f));	f[1]=a;	for(ri i=1;i
    

---

D题

题意简述：

给一棵树，现在$A$可以从树上面选一些点出来,选$i$的花费为aia_iai​,然后$B$给所有叶子结点赋值，然后$A$可以对所有选出来的点进行一次操作：使得以它为根的子树中的所有叶子结点全部减去一个相同的值，问如果$A$想保证无论$B$怎么赋值自己操作之后每个叶子的权值都为$0$那么选出来点的最少代价是多少并要求列出所有可能被选出的点。

---

思路：

先考虑构造出任意一种方案然后再统计。

这个最优值可以非常简单的树形$DP$出来，然后对于一次儿子对父亲的转移我们把可行的方案都记下来，最后统计即可。

细节见代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}typedef pair
     
       pii;typedef long long ll;const int N=2e5+5;int n,a[N],fa[N],nxt[N];bool pass_on[N],vis[N];vector
      
       e[N],Ans;ll ans=0;pii dfs(int p){
    	pii ret=pii(a[p],p),mx;	vector
       
        tmp;	for(ri i=0,v;i
        
         ());	mx=tmp[0];	int cnt=0;	for(ri i=0;i
         
          1)pass_on[mx.se]=1; if(ret.fi^mx.fi)return min(ret,mx); return nxt[ret.se]=mx.se,ret;}int main(){ n=read(); for(ri i=1;i<=n;++i)a[i]=read(); for(ri i=1,u,v;i
         
        
       
      
     
    

---

E题

题意简述：给出一个$a,(a\le 1000)$，现在要求找出一个$n$满足：S(a∗n)=S(n)a,S(x)S(a*n)=\frac{S(n)}a,S(x)S(a∗n)=aS(n)​,S(x)表示$x$各位数字之和。

---

思路：

如果先要完全正确的思路请看官方题解的$solution1$，博主写的是$solution2$一种有点假的算法。

考虑构造一个$balance(x)=S(a\ast n)a-S(n)$，显然这个值为$0$的时候说明满足题意。

这样我们构造一个二元组来进行$bfs$直到搜出来一个环为止。

然后当$|balance|>a$的时候可以剪个枝。

代码：

#include
    
     #define ri register int#define fi first#define se second#define id(x) ((x)+1500)using namespace std;typedef pair
     
       pii;const int N=3005;int hd,tl,sta[N][N],dig[N][N];pii q[N*1500],pre[N][N],tt;inline string solve(int A){
    	memset(sta,-1,sizeof(sta));	sta[0][id(0)]=0;	q[hd=tl=1]=pii(0,0);	while(hd<=tl){
    		int car=q[hd].fi,bal=q[hd].se;		for(ri tmp,ncar,nbal,num=hd>1?0:1;num<10;++num){
    			tmp=car*10+num;			ncar=tmp%A;			nbal=bal+A*num-tmp/A;			if(id(nbal)>3000||id(nbal)<0)continue;			if(!nbal&&!ncar){
    				string ret="",tret="";				tret+=(char)(num^48);				while(car||bal){
    					tret+=(char)(dig[car][id(bal)]^48);					tt=pre[car][id(bal)];					car=tt.fi,bal=tt.se;				}				reverse(tret.begin(),tret.end());				for(ri sum=0,i=0,up=tret.size();i^up;++i){
    					sum=sum*10+(tret[i]^48);					if(sum/A||ret.size())ret+=(char)((sum/A)^48);					sum%=A;				}				return ret;			}			if(sta[ncar][id(nbal)]==-1){
    				sta[ncar][id(nbal)]=sta[car][id(bal)]+1;				q[++tl]=pii(ncar,nbal);				pre[ncar][id(nbal)]=pii(car,bal);				dig[ncar][id(nbal)]=num;			}		}		++hd;	}	return "-1";}int main(){
    	int A;	scanf("%d",&A);	cout<
     
    

---

F题

题意简述：

两个人$W,P$需要互相送信。

现在有$n$个时间点t1,t2,...,tnt_1,t_2,...,t_nt1​,t2​,...,tn​，每个时间点$W/P$负责送信，以及一个结束时间点tn+1t_{n+1}tn+1​。

有两种选择：

1. 直接花$d$的代价送给对方
2. 将信寄存在$R$那里，设从寄存到拿信花了$T$个单位时间，代价是$c\ast T$。

一个人可以在$R$那儿拿信当且仅当自己去$R$送信或者时间为tn+1t_{n+1}tn+1​

---

思路：

考虑$dp$.

考虑现在$W$两次去$R$之间$P$的送信情况。

显然应该是最开始可能去一次$R$,最后连续一段可能去$R$，中间一段直接送。

然后这就是一个显然的O(n2)dpO(n^2)dpO(n2)dp，发现本质其实是一堆线段里取最值。

那么上李超树优化一波复杂度O(nlogn2)O(nlog_n^2)O(nlogn2​)

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=getchar();	return ans;}typedef long long ll;typedef pair
     
       pii;const int N=1e5+5;const ll inf=1e9;inline ll calc(const pii&coe,const int&x0){
    return coe.fi*x0+coe.se;}inline pii operator+(const pii&a,const pii&b){
    return pii(a.fi+b.fi,a.se+b.se);}inline void operator+=(pii&a,const pii&b){
    a=a+b;}int t[N],n;ll c,d;struct SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (l+r>>1)	pii val[N<<2],add[N<<2];	inline void pushnow(int p,pii v){
    val[p]+=v,add[p]+=v;}	inline void pushdown(int p){
    if(add[p]!=pii(0ll,0ll))pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=pii(0ll,0ll);}	inline void change(int p,int l,int r,pii v){
    		if(calc(v,t[l])<=calc(val[p],t[l]))swap(val[p],v);		if(calc(val[p],t[r])<=calc(v,t[r]))return;		pushdown(p);		if(calc(val[p],t[mid])<=calc(v,t[mid]))change(rc,mid+1,r,v);		else swap(v,val[p]),change(lc,l,mid,v);	}	inline void update(int p,int l,int r,int k){
    		ll v1=c*(t[l]-t[k])-d,v2=c*(t[r]-t[k])-d;		if(v2<=0)return pushnow(p,pii(c,-c*t[k]));		if(v1>=0)return pushnow(p,pii(0,d));		pushdown(p);		change(lc,l,mid,val[p]),change(rc,mid+1,r,val[p]);		val[p]=pii(inf,inf);		update(lc,l,mid,k),update(rc,mid+1,r,k);	}	inline ll query(int p,int l,int r,int k){
    		ll ret=calc(val[p],t[k]);		if(l==r)return ret;		pushdown(p);		return min(ret,k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k));	}	#undef lc	#undef rc	#undef mid}f[2];char S[2];bool type[N];int main(){
    	n=read(),c=read(),d=read();	for(ri i=1;i<=n;++i)t[i]=read(),scanf("%s",S),type[i]=(S[0]=='W');	t[n+1]=read();	for(ri i=1;i<=n;++i){
    		f[type[i]].update(1,1,n+1,i);		f[type[i]].change(1,1,n+1,pii(c,f[type[i]^1].query(1,1,n+1,i)-c*t[i]));		f[type[i]^1].pushnow(1,pii(0,d));	}	cout<