A. Balloon Robot

假设机器人$0$时刻位于$0$号位置，那么每个气球所需的时间为$(s_a-b)\bmod m$。

将所有气球按这个时间排序，枚举每个气球的时间作为偏移量，得出最优解即可。

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

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=1000010;int T,n,m,p,i,s[N];ll f[N],init,ans;int main(){	scanf("%d",&T);	while(T--){		scanf("%d%d%d",&n,&m,&p);		for(i=1;i<=n;i++)scanf("%d",&s[i]);		init=0;		for(i=1;i<=p;i++){			int a,b;			scanf("%d%d",&a,&b);			f[i]=((s[a]-b)%m+m)%m;			init+=f[i];		}		ans=init;		sort(f+1,f+p+1);		for(i=1;i<=p;i++)ans=min(ans,init-1LL*p*f[i]+1LL*(i-1)*m);		printf("%lld\n",ans);	}}
      
     

　　

B. Expected Waiting Time

设$f_n$表示长度为$n$的合法括号序列个数，则奇数为$0$，偶数为卡特兰数。

分母一定是$f_{2n}$，而对于分子，可以考虑每个位置作为左右括号的贡献，假设是第$i$个位置作为左括号，那么枚举与其配对的右括号的距离$j$，则中间的方案数为$f_{j-1}$，剩下部分的方案数为$f_{2n-j-1}$，故总方案数为$\sum_{j=1}^{2n-i}f_{j-1}f_{2n-j-1}$。

注意到$i$只影响上式的求和上界，故直接计算出每个的值即可。

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

#include
     
      typedef long long ll;const int N=5000000;int n,P,b,A,B,T,i,a[N],sum,ans;int h[N],inv[N];inline ll po(ll a,ll b){	ll t=1;	for(;b;b>>=1,a=a*a%P)if(b&1)t=t*a%P;	return t;}inline int C(int n){	if(n&1)return 0;	return h[n>>1];}int main(){	scanf("%d",&T);	while(T--){		scanf("%d%d%d%d%d",&n,&P,&b,&A,&B);		h[0]=1;		h[1]=1;		inv[0]=inv[1]=1;		for(i=2;i<=n+1;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;		for(i=2;i<=n;i++)h[i]=1LL*h[i-1]*(i*4-2)%P*inv[i+1]%P;		n*=2;		for(i=1;i<=n;i++){			b=(1LL*b*A+B)%P;			a[i]=(1LL*a[i-1]+1LL*b+1)%P;		}		sum=0;		ans=0;		for(i=1;i
     

　　

C. Crusaders Quest

爆搜所有可行方案即可。

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

　　

D. Graph Generator

从后往前还原整个过程。

若图只有一个点，那么方案显然。

若图由多个连通块构成，那么每个连通块之间是独立的，分开处理即可。

否则图只剩下一个大小至少为$2$的连通块，那么最后一步操作必然选择一个到其它每个点都有边的点，然后将图继续分裂成若干连通块。

注意到对于$n$个点的连通块，边数会减少$n-1$，故迭代层数不超过$O(\sqrt{n})$。

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

#include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
         P;const int N=100010,M=200010;int Case,n,m,i,qa[N],qb[M],tmp[M];int fin[N];//should reversevector
         
          ans[N];int stage;bool err;struct E{	int x,y;}e[M];int deg[N],g[N],v[M<<1],nxt[M<<1],ed;int vis[N];int cnt;int q[N],cq;int pos[M];inline void add(int x,int y){	v[++ed]=y;	nxt[ed]=g[x];	g[x]=ed;	deg[x]++;}void dfs(int x){	if(vis[x])return;	vis[x]=cnt;	q[++cq]=x;	for(int i=g[x];i;i=nxt[i])dfs(v[i]);}void solve(int nl,int nr,int ml,int mr,vector
          
           &old){ if(err)return; //for(int i=nl;i<=nr;i++)printf("%d ",qa[i]);puts(""); if(nl==nr){ fin[++stage]=qa[nl]; old.push_back(qa[nl]); return; } //find connect comp int i,j; cnt=ed=0; for(i=nl;i<=nr;i++){ int x=qa[i]; deg[x]=g[x]=vis[x]=0; } for(i=ml;i<=mr;i++)add(e[qb[i]].x,e[qb[i]].y),add(e[qb[i]].y,e[qb[i]].x); cq=0; for(i=nl;i<=nr;i++){ int x=qa[i]; if(!vis[x]){ old.push_back(x); cnt++; dfs(x); } } if(cnt==1){ int cv=nr-nl; for(i=nl;i<=nr;i++)if(deg[qa[i]]==cv)break; if(i>nr){ err=1; return; } int x=qa[i]; swap(qa[nl],qa[i]); int L=ml,R=ml-1; for(i=ml;i<=mr;i++){ int u=e[qb[i]].x,v=e[qb[i]].y; if(u==x||v==x)continue; tmp[++R]=qb[i]; } for(i=L;i<=R;i++)qb[i]=tmp[i]; fin[++stage]=x; solve(nl+1,nr,L,R,ans[stage]); }else{ vector
           
nson,mson; int l=nl; for(i=1;i<=cq;i=j){ int r=l-1; for(j=i;j<=cq&&vis[q[i]]==vis[q[j]];j++){ qa[++r]=q[j]; } nson.push_back(P(l,r)); l=r+1; } for(i=1;i<=cnt;i++)pos[i]=0; pos[0]=ml-1; for(i=ml;i<=mr;i++)pos[vis[e[qb[i]].x]]++; for(i=1;i<=cnt;i++)pos[i]+=pos[i-1]; for(i=1;i<=cnt;i++)mson.push_back(P(pos[i-1]+1,pos[i])); for(i=ml;i<=mr;i++){ int x=vis[e[qb[i]].x]; tmp[pos[x]--]=qb[i]; } for(i=ml;i<=mr;i++)qb[i]=tmp[i]; int _cnt=cnt; for(i=0;i<_cnt;i++){ ans[0].clear(); solve(nson[i].first,nson[i].second,mson[i].first,mson[i].second,ans[0]); } }}int main(){ scanf("%d",&Case); while(Case--){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)qa[i]=i; for(i=1;i<=m;i++)qb[i]=i; for(i=1;i<=m;i++)scanf("%d%d",&e[i].x,&e[i].y); stage=err=0; for(i=0;i<=n;i++)ans[i].clear(); solve(1,n,1,m,ans[0]); if(err)puts("No");else{ puts("Yes"); for(i=n;i;i--){ printf("%d %d",fin[i],ans[i].size()); for(int j=0;j
          
         
        
       
      
     

　　

E. String of CCPC

设$f[i][j][k]$表示考虑前$i$个字符，目前购买了$j$次，与“CCPC”KMP的指针为$k$的最大净收益。

注意到最优解中$j$为个位数，令其不超过$9$即可。

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

#include
     
      const int N=200010,M=10;int T,n,m,i,j,k,t,ans,b[N],nxt[N],g[M][2],w[M][2];int f[N][M][4];char a[N];inline void up(int&a,int b){a
     

　　

F. Getting Lost

留坑。

 

G. Numbers

在二进制下从高位到低位贪心考虑。

若答案这一位可以为$0$，那么全部填$0$，否则尽量填$1$。

import java.util.*;import javax.swing.text.TabableView;import java.io.*;import java.math.*;public class Main{	static final int N = (int)1e5 + 10;	static Scanner cin = new Scanner(System.in);	static BigInteger v0 = BigInteger.valueOf(0);	static BigInteger v1 = BigInteger.valueOf(1);	static BigInteger v2 = BigInteger.valueOf(2);	static BigInteger b[] = new BigInteger [4000];	public static void main(String args[])	{		b[0] = v1;		for(int i = 1; i < 4000; ++i)b[i] = b[i - 1].multiply(v2);		int casenum = cin.nextInt();		for(int casei = 1; casei <= casenum; ++casei)		{			BigInteger n = cin.nextBigInteger();			BigInteger m = cin.nextBigInteger();			BigInteger top = n.add(m).subtract(v1).divide(m);			int w = 0;			while(b[w].compareTo(top) <= 0)++w;			BigInteger ans = v0;			for(int k = w; k >= 0; --k)			{				if(n.compareTo( b[k].subtract(v1).multiply(m) ) <= 0)				{									}				else				{					BigInteger g = n.divide(b[k]);					if(g.compareTo(m) > 0)g = m;					n = n.subtract(g.multiply(b[k]));					ans = ans.add(b[k]);				}			}			System.out.println(ans);		}	}}

　　

H. Prime Set

按奇偶建立二分图匹配模型，先忽略$1$求出最大匹配，再考虑$1$继续求最大匹配，每个匹配都将贡献$2$。

对于剩下的数，再检查能否与已选的数配对，每次配对贡献$1$。

注意特殊处理$1$内部的匹配。

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

　　

I. Triangulation

留坑。

 

J. Tree Equation

留坑。

 

K. Diversity and Variance

留坑。

 

L. One-Dimensional Maze

答案为$\min([2,m]中R的个数,[m,n-1]中L的个数)$。

#include
     
      #include
      
       using namespace std;const int N=1000010;int T,n,m,i,A,B;char a[N];int main(){	scanf("%d",&T);	while(T--){		scanf("%d%d%s",&n,&m,a+1);		A=B=0;		for(i=2;i<=m;i++)if(a[i]=='R')A++;		for(i=m;i
      
     

　　

M. Safest Buildings

下一轮安全区的圆心可行范围可以用圆表示，圆交求出概率即可。

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