A. 全连

1s，256MB

E.Space 喜欢打音游。

但是他技术不好，总是拿不到全连（Full Combo）。

现在他面前有一份乐谱，乐谱的其中一段有 $n$个连续的单键音符。

相邻两个音符的到来时间均相等，我们可以认为第 $i$ 个音符会在第 $i$ 个时刻到来。

点击一个音符，E.Space 需要一段准备时间来进行移动手指之类的操作。由于音符的位置和周围情况不同，点击每个音符的准备时间也不同。

在一个音符的准备时间内，E.Space 没法做到去点击其它音符，但是不同音符的准备时间范围可以互相重叠。形式化地，令第 $i$ 个音符的准备时间为 ti​t_i​ti​​​ 个单位时间，那么如果 E.Space 选择去点击第 $i$ 个音符，那么他就没法点击所有到来时刻在 (i−ti,i+ti​​)(i − t_i ,i + t_i​​)(i−ti​,i+ti​​​) 中的音符。

为了获得更高的分数，E.Space 还计算了每个音符的性价比aia_iai​。一个音符的性价比等于点击这个音符得到的分数除以 E.Space 点击它所需要的准备时间。

E.Space 就不指望全连了，他只是想让你帮他计算一下他最多可以得到多少分数。

n&lt;=1e6,ai&lt;=1e9n&lt;=1e6,a_i&lt;=1e9n<=1e6,ai​<=1e9

题解

大大的良心题啊

很好想到dp:fif_ifi​表示前$i$个数，$i$为最后一个取的最高得分

显然fi=fj+ai∗tif_i=f_j+a_i*t_ifi​=fj​+ai​∗ti​

其中j+tj&lt;=i,i−ti&gt;=jj+t_j&lt;=i,i-t_i&gt;=jj+tj​<=i,i−ti​>=j

所以我们可以写个堆，里面的元素以x+txx+t_xx+tx​排序

当计算fif_ifi​的时候，就可以把堆里面小于$i$的元素弹出，将其dp值插入到线段树中，然后就是区间查找最大值

上代码

#include 
    
     #include 
     
      #include 
      
       #define Ls k<<1#define Rs k<<1|1#define mid ((l+r)>>1)#define LL long longusing namespace std;const int N=1e6+5;int n,t[N];LL f[N],ax[N*4],ans;struct O{	int x;	friend bool operator < (const O& A,const O& B){		return A.x+t[A.x]>B.x+t[B.x];	}};priority_queue
       
        q;void update(int k,int l,int r,int x,LL v){	if (l==r){ax[k]=v;return;}	if (mid>=x) update(Ls,l,mid,x,v);	else update(Rs,mid+1,r,x,v);	ax[k]=max(ax[Ls],ax[Rs]);}LL query(int k,int l,int r,int L,int R){	if (L>R) return 0;	if (L<=l && r<=R) return ax[k];	if (mid
        
         =R) return query(Ls,l,mid,L,R);	return max(query(Ls,l,mid,L,R),query(Rs,mid+1,r,L,R));}int main(){	freopen("fc.in","r",stdin);	freopen("fc.out","w",stdout);	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&t[i]);	for (int i=1;i<=n;i++){		LL x;scanf("%lld",&x);f[i]=x*t[i];		while(!q.empty()){			O k=q.top();if (k.x+t[k.x]>i) break;			q.pop();update(1,1,n,k.x,f[k.x]);		}		f[i]+=query(1,1,n,1,i-t[i]);		ans=max(ans,f[i]);q.push((O){i});	}	printf("%lld\n",ans);	return 0;}
        
       
      
     
    

B. 原样输出

3s，256MB

nealchen 是一只 copycat。

它会把输入按行读入，原封不动地复制到输出中去。

但是在一次更新以后，它的程序出了一些问题。

它没法输出换行符了。

并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行都会漏掉。

比如 orznight 可能会变成 rzni ，orz，h 或者空串。

现在你找到一份输入文件丢给 nealchen，你想知道它的输出可能有多少种情况，以及每种情况分别是什么。

由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可能包含 A，C，G，T 四种字符。

保证输入文件大小不超过 1MB ，保证输出文件大小不超过 200MB 。

题解

如果只有一个串，就是后缀自动机的基本应用

假设我们在匹配一个字符串能否成为答案，那我们就是贪心的匹配

所以我们从后往前建n个后缀自动机，然后在建立第i个SAM的时候看每个点是不是都有ACGT的出边，如果没有的话，那就往i+1的rt的对应出边节点连边

然后得到一个拓扑图，可以dp出答案，输出方案就直接dfs

上代码

#include 
    
     #define LL long longusing namespace std;const int N=3e6+5,P=1e9+7;int d[N],ans,sz,lst,k,n,m[N],las[4],rt[N],in[N];string s[N];queue
     
      q;vector
      
       gg[N];char g[N];struct SAM{int len,link,mp[4];}sam[N];void sam_con(int d,int ch){	int np=++sz,p=lst;	sam[np].len=sam[p].len+1;	while(p && !sam[p].mp[ch])		sam[p].mp[ch]=np,p=sam[p].link;	if (!p) sam[np].link=rt[d];	else{		int q=sam[p].mp[ch];		if (sam[q].len==sam[p].len+1)			sam[np].link=q;		else{			int nq=++sz;			sam[nq].len=sam[p].len+1;			sam[nq].link=sam[q].link;			for (int i=0;i<4;i++)				sam[nq].mp[i]=sam[q].mp[i];			sam[q].link=sam[np].link=nq;			while(p && sam[p].mp[ch]==q)				sam[p].mp[ch]=nq,p=sam[p].link;		}	}	lst=np;}void dfs(int id,int x,int j){	if (j==0) g[x]='A';if (j==1) g[x]='C';	if (j==2) g[x]='G';if (j==3) g[x]='T';	for (int i=0;i<=x;i++)		putchar(g[i]);putchar('\n');	for (int i=0;i<4;i++)		if (sam[id].mp[i])			dfs(sam[id].mp[i],x+1,i);}int main(){	freopen("copy.in","r",stdin);	freopen("copy.out","w",stdout);	scanf("%d",&n);	for (int i=1;i<=n;i++)		cin>>s[i],m[i]=s[i].length();	for (int i=n;i;i--){		lst=++sz;rt[i]=sz;		for (int y,j=0;j
      
     
    

C. 不同的缩写

1s,256MB

你在写一款 Galgame 的剧情（的代码）。

在这个游戏中一共有 n 个角色。你需要编写一些关于这些角色的对话内容。然而，在写这些对话内容之前，都要写一段关于角色信息的代码，就像这样：

Character(“Alex”, color = “#FFFC3A”)

你觉得这样好麻烦。你决定把它简化一下。你打算用角色名字的一个非空子序列（可以不连续）来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短，这样你打起代码就会方便一些。

n,len<=300

题解

首先二分答案mid，然后对于每个串，找出长度<=mid的子序列

注意：当找出n个子序列的时候就可以不用找了，因为这n个中肯定有一个可以作为答案

那我们就对找到的子序列建点，和字符串下标i连边，然后跑二分图匹配，如果满流则为合法

复杂度玄学，上代码

#include 
    
     #define LL unsigned long long#define K 793999using namespace std;bool G;const int N=333,M=444444;int n,Ax,l=1,r,g[N],cp,nex[M],d[M];int S,T,head[M],cur[M],V[M],W[M],t,dd[M];char s[N][N];LL h[M],gg;string H[M],ggg,ys[M];map
     
      p,q;queue
      
       Q;inline void ins(int u,int v){	V[++t]=v;W[t]=1;nex[t]=head[u];head[u]=t;	V[++t]=u;W[t]=0;nex[t]=head[v];head[v]=t;}inline bool bfs(){	for (int i=S;i<=T;i++) d[i]=-1;	Q.push(S);d[S]=0;	while(!Q.empty()){		int x=Q.front();Q.pop();		for (int i=head[x];i;i=nex[i])			if (d[V[i]]==-1 && W[i]) 				d[V[i]]=d[x]+1,Q.push(V[i]);	}	return d[T]>-1;}int dfs(int x,int ax){	if (x==T) return ax;	int sum=0,tt;	for (int& i=cur[x];i;i=nex[i]){		if (W[i] && d[V[i]]==d[x]+1		 && (tt=dfs(V[i],min(ax,W[i]))))			ax-=tt,W[i]-=tt,W[i^1]+=tt,sum+=tt;		if (!ax) break;	}	return sum;}inline void work(int d,int x){	for (int j=1,i=1;i<=g[d];i++)		for (int k=j;k;k--){			if (dd[k]==x) continue;			gg=h[k]*K+s[d][i];			if (G) ggg=H[k]+s[d][i];			if (q[gg]!=d){				h[++j]=gg,q[gg]=d;				dd[j]=dd[k]+1;				if (G) H[j]=ggg;				if (!p[gg]){					p[gg]=++cp;					if (G) ys[cp]=ggg;				}				ins(d,p[gg]+n);			}			if (j==n+1) return;		}}inline bool J(int x){	t=1;p.clear();cp=0;q.clear();	for (int i=S;i<=T;i++) head[i]=0;	for (int i=1;i<=n;i++)		ins(S,i),work(i,x);	T=cp+n+1;	for (int i=1;i<=cp;i++) ins(i+n,T);	int sum=0;while(bfs()){		for (int i=S;i<=T;i++)			cur[i]=head[i];		sum+=dfs(S,1e9);	}	if (G)		for (int i=1;i<=n;i++)			for (int j=head[i];j;j=nex[j])				if (V[j] && !W[j]){					int ll=ys[V[j]-n].length();					for (int l=0;l
       
        >1;		if (J(mid)) r=mid;		else l=mid+1;	}	if (l>Ax) puts("-1");	else{		printf("%d\n",l);G=1;		return !J(l);	}	return 0;}