A. Ability Draft

记忆化搜索。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

B. Short Random Problem

积分DP。

 

C. Block, Stock and Two Smoking Galaxy Notes

枚举领导者$S$，它需要满足度数至少为$\frac{n}{2}$。

枚举完领导后，将和$S$认识和不认识的分成两组二分图匹配即可。

时间复杂度$O(m^2)$。

#include
     
      #include
      
       using namespace std;const int N=1010,M=10010;int n,m,i,e[M][2],g[N],v[M],nxt[M],ed,f[N],b[N],T,right[N],deg[N];inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}bool find(int x){	for(int i=g[x];i;i=nxt[i])if(b[v[i]]
       
        =n/2-5)solve(i);	puts("No");}/*5 41 22 33 44 5*/
       
      
     

　　

D. Lunch Queue

用一棵平衡树$S$维护整个队列，再对每个队伍用一棵平衡树$T_i$维护。

那么对于新来的一个人，先在$S$中找出满足距离限制最紧的那个点$x$，再在$T_{c_i}$中查找$x$之后最靠前的点作为插队位置。

瓶颈在于最后一步比较两个人在$S$中的前后关系，将$S$用替罪羊树维护，同时维护动态标号即可$O(1)$比较。

时间复杂度$O(n\log n)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=400010;typedef unsigned long long ll;const ll inf=1ULL<<63;const double A=0.8;ll tl[N],tr[N],tm[N];int size[N],son[N][2],f[N],tot,root;int id[N],cnt;int n,i,a[N];void dfs(int x){  if(son[x][0])dfs(son[x][0]);  id[++cnt]=x;  if(son[x][1])dfs(son[x][1]);}int build(int fa,int l,int r,ll a,ll b){  int mid=(l+r)>>1,x=id[mid];  f[x]=fa;son[x][0]=son[x][1]=0;size[x]=1;tl[x]=a;tr[x]=b;tm[x]=(a+b)>>1;  if(l==r)return x;  if(l
        
         mid)size[x]+=size[son[x][1]=build(x,mid+1,r,tm[x],b)];  return x;}inline int kth(int k){  if(k<1)return 0;  int x=root,rank;  while(1){    rank=size[son[x][0]]+1;    if(k==rank)return x;    if(k
         
          >1;    return;  }  while(1){    if(!son[A][B]){      son[A][B]=x;      f[x]=A;      if(!B){        tl[x]=tl[A];        tr[x]=tm[A];      }else{        tl[x]=tm[A];        tr[x]=tr[A];      }      tm[x]=(tl[x]+tr[x])>>1;      break;    }    A=son[A][B];  }  fix(x);}inline void insd(int A,int B,int x){  if(!son[A][B]){    son[A][B]=x;    f[x]=A;    if(!B){      tl[x]=tl[A];      tr[x]=tm[A];    }else{      tl[x]=tm[A];      tr[x]=tr[A];    }    tm[x]=(tl[x]+tr[x])>>1;    fix(x);    return;  }  ins(son[A][B],B^1,x);}void show(int x){  if(son[x][0])show(son[x][0]);  printf("%d ",x);  if(son[x][1])show(son[x][1]);}namespace DS{int root[N],son[N][2],f[N];inline void rotate(int x){  int y=f[x],w=son[y][1]==x;  son[y][w]=son[x][w^1];  if(son[x][w^1])f[son[x][w^1]]=y;  if(f[y]){    int z=f[y];    if(son[z][0]==y)son[z][0]=x;    else if(son[z][1]==y)son[z][1]=x;  }  f[x]=f[y];son[x][w^1]=y;f[y]=x;}inline void splay(int x){  while(f[x]){    int y=f[x];    if(f[y]){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}    rotate(x);  }}inline void insert(int&x,int y){  if(!x){x=y;return;}  int z=x;  while(1){    int b=tm[y]>tm[z];    if(son[z][b])z=son[z][b];    else{      son[z][b]=y;      f[y]=z;      break;    }  }  splay(x=y);}int ask(int&o,int y){  int t=0,z=0,x=o;  while(x){    z=x;    if(tm[x]>tm[y]){      t=x;      x=son[x][0];    }else{      x=son[x][1];    }  }  if(z)splay(o=z);  return t;}}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++){    int x,dis;    scanf("%d%d",&x,&dis);    a[i]=x;    if(i==1)ins(0,0,i);    else{      int y=kth(i-dis-1);      if(a[y]==x)insd(y,1,i);      else{        int z=DS::ask(DS::root[x],y);        if(z)insd(z,0,i);        else ins(root,1,i);      }    }    DS::insert(DS::root[x],i);  }  show(root);}
         
        
       
      
     

　　

E. Oneness

$ans=\lfloor\frac{n}{11}\rfloor+\lfloor\frac{n}{111}\rfloor+\lfloor\frac{n}{1111}\rfloor+...$。

令$N=9n$，则$ans=\lfloor\frac{N}{99}\rfloor+\lfloor\frac{N}{999}\rfloor+\lfloor\frac{N}{9999}\rfloor+...$。

对于整数部分FFT计算答案，对于小数部分用实数近似计算即可。

时间复杂度$O(|n|\log |n|)$。

 

F. Shuffle

对于置换中的每个循环，通过KMP求出所有可能的匹配位置，它们必然是一个等差数列。

那么对于所有循环分别列同余方程，然后扩展欧几里得求解即可。

时间复杂度$O(n)$。

#include
     
      #include
      
       #include
       
        using namespace std;typedef int ll;const int N=1000010;int n,i,j,p[N],vis[N],q[N];char a[N],b[N],c[N],S[N],T[N];int nxt[N],w[N*4];int ans=1;int _a[N],_b[N],tot;namespace NT{int flag=1;ll k=1,m,a,r,d,x,y;ll exgcd(ll a,ll b,ll&x,ll&y){	if(!b)return x=1,y=0,a;	ll d=exgcd(b,a%b,x,y),t=x;	return x=y,y=t-a/b*y,d;}inline void add(ll a,ll r){	if(r>=a)while(1);	r%=a;	if(!flag)return;	d=exgcd(k,a,x,y);	if((r-m)%d){flag=0;return;}	x=(x*(r-m)/d+a/d)%(a/d),y=k/d*a,m=((x*k+m)%y)%y;	if(m<0)m+=y;	k=y;}void write(ll x){	if(x>=10)write(x/10);	int t=x%10;	printf("%d",t);}void show(){	if(flag)write(m);	else puts("-1");}}inline void solve(int len){	int i,j,k,cnt=0;	for(i=1;i<=len;i++)T[i]=b[q[i]],S[i]=a[q[i]];	//printf("len=%d\n",len);	//for(i=1;i<=len;i++)putchar(T[i]);puts("");	//for(i=1;i<=len;i++)putchar(S[i]);puts("");	for(nxt[1]=j=0,i=2;i<=len;nxt[i++]=j){		while(j&&S[j+1]!=S[i])j=nxt[j];		if(S[j+1]==S[i])j++;	}	//for(i=1;i<=len;i++)printf("nxt[%d]=%d\n",i,nxt[i]);	for(i=1,j=0,k=1;i<=len*4;i++){		while(j&&S[j+1]!=T[k])j=nxt[j];		if(S[j+1]==T[k]){			j++;			if(j==len){				w[++cnt]=i-len;				j=nxt[j];				//printf("find %d\n",i);			}		}		k++;		if(k>len)k=1;	}	if(!cnt){		puts("-1");		exit(0);	}	if(cnt<2)while(1);	for(i=2;i<=cnt;i++)if(w[i]-w[i-1]!=w[2]-w[1])while(1);	//printf("per=%d occ=%d\n",w[2]-w[1],w[1]);	NT::add(w[2]-w[1],w[1]);}int gcd(int a,int b){return b?gcd(b,a%b):a;}int main(){	scanf("%s%s",a+1,b+1);	n=strlen(a+1);	for(i=1;i<=n;i++){		int x;		if(i<=n/2)x=i*2-1;		else x=i*2-n;		//printf("! %d %d\n",i,x);		p[x]=i;	}	for(i=1;i<=n;i++)if(!vis[i]){		int cnt=0;		for(j=i;!vis[j];j=p[j])vis[j]=1,q[++cnt]=j;		//for(j=1;j<=cnt;j++)printf("%d ",q[j]);puts("");		solve(cnt);	}	NT::show();}/*aaababbbbbbabbbbabaabbabbababbbabbbbbabaaabbaabbaaaababa*/
       
      
     

　　

G. Piecewise Linearity

按题意反解出每个函数即可，精度可以取模控制，不过使用__float128也可以通过全部数据。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

H. Sketch

贪心将原序列复制下来，然后构造递减数列，注意特判原序列非法的情况。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

I. $\leq$ or $\geq$

最优策略：将元素个数为$k$的栈的栈顶元素的权重设置为$2^{k-1}$，然后取加权中位数。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

J. Stairways

设$pre[i]=\max(a[1..i])$，则对于任意一个前缀$i$来说，两个子序列必有一个的最大值为$pre[i]$，设$f[i][j]$表示考虑前缀$i$，除了$pre[i]$之外另一个子序列最大值为$j$时的最小代价，考虑如何从$f[i-1][]$转移到$f[i][]$。

若$a[i]=pre[i]$，那么显然将它归到较大一侧最优，故$f[i][j]=f[i-1][j]+a[i]$，只需要把答案加上$a[i]$即可。

否则$a[i]<pre[i]$，那么假设它不作为最大值，则对于$[a[i],pre[i]]$的$j$，有$f[i][j]=f[i-1][j]+j$，对于$[0,a[i])$的$j$，有$f[i][j]=f[i-1][j]+pre[i]$。

而如果它作为最大值，则有$f[i][a[i]]=\min(f[i-1][0..a[i]])+a[i]$。

故需要一个数据结构维护$f[j]$，支持区间加上一个数，区间每个位置$j$加上$j$，以及区间查询最小值，单点修改。

将$f$分块，每块维护凸壳和标记即可，因为查询横坐标递增，故不断将凸壳的队首弹出即可均摊$O(\sqrt{n})$每次查询。

时间复杂度$O(n\sqrt{n})$。

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010,K=330;const ll inf=1000000000000010LL;int n,m,lim,i,a[N],b[N],pre[N],pos[N],st[K],en[K],tx[K],q[N],head[K],tail[K];ll base,f[N],tb[K];inline void up(ll&a,ll b){a>b?(a=b):0;}inline double slope(int x,int y){return 1.0*(f[x]-f[y])/(b[y]-b[x]);}inline void build(int x){  int&h=head[x],&t=tail[x],l=st[x],r=en[x];  h=l,t=h-1;  for(int i=r;i>=l;q[++t]=i--)while(h
       
        slope(q[t],i))t--;}inline void addx(int l){  int L=pos[l];  for(int i=l;i<=en[L];i++)f[i]+=b[i];  for(int i=pos[m];i>L;i--)tx[i]++;}inline void addf(int r,int p){  int R=pos[r];  for(int i=st[R];i<=r;i++)f[i]+=p;  build(R);  for(int i=0;i
        
         cal(q[h+1],o))h++;  return cal(q[h],o);}inline ll query(int r){  ll ret=inf;  int R=pos[r];  for(int i=st[R];i<=r;i++)up(ret,f[i]+1LL*tx[R]*b[i]+tb[R]);  for(int i=0;i
        
       
      
     

　　

K. Hiding a Tree

将所有可以修改编号的点的编号随机设置，然后再挑选一个影响答案的点修正异或值。

若当前方案不合法，则在有解的情况下是小概率事件，多轮随机即可。

注意生成随机编号的时候要避免与之前编号相同，因为根据生日悖论，在$10^9$内取$10^5$个随机数中有重复元素的概率超过$50\%$，会导致这一轮随机作废。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=100010;int n,i,a[N],e[N][2],b[N],c[N],q[N],m,v[N];int used[N];set
          
           T;inline int ask(){ while(1){ int x=rand()%1000000000+1; if(x
           
            1000000000)return; c[i]=b[i]; } sort(c+1,c+n+1); for(i=1;i