A. Artifacts

建立语法分析树，首先根据上下界判断是否有解，然后将所有数按下界填充，线段树判断是否存在和超过$K$的子区间。

 

B. Brackets and Dots

最优解中一定包含一对中间都是点的$()$，set维护所有这种pair即可。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef pair
         
          P;const int N=500010;int n,i,m,x,y;set
          
           A;set
           
B;char a[N];inline bool gao(int x,int y){ set
           
::iterator it=B.lower_bound(P(x,-1)); if(it==B.end())return 0; if(it->second>y)return 0; int l=it->first,r=it->second; B.erase(it); set
            
             ::iterator i=A.find(l),j=A.find(r); int pre=0,nxt=0; if(i!=A.begin()){ i--; if(a[*i]=='(')pre=*i; } j++; if(j!=A.end()){ if(a[*j]==')')nxt=*j; } A.erase(l); A.erase(r); if(pre&&nxt)B.insert(P(pre,nxt)); return 1;}int main(){ scanf("%s",a+1); n=strlen(a+1); for(i=1;i<=n;i++){ A.insert(i); if(a[i]=='('&&a[i+1]==')')B.insert(P(i,i+1)); } scanf("%d",&m); while(m--){ scanf("%d%d",&x,&y); int ans=0; while(gao(x,y))ans++; printf("%d\n",ans*2); }}
            
          
         
        
       
      
     

　　

C. Crossword

首先$O(n^2)$预处理出竖着的两条对于每种间隔的贡献，然后$O(n^2)$枚举横着的摆法，再根据预处理的数组求出每个位置竖着的放法，前缀和优化即可。

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;string a[9];int q[9],i;long long ans;int f[555],g[555];int wc[160][29][29],wd[160][29][29];inline int cal(const string&A,int d,char x,char y){ int ret=0; for(int i=d;i
           
            >a[i]; for(int j=0;j
           
          
         
        
       
      
     

　　

D. Digit

从高位到低位贪心。

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

　　

E. Enormous Table

找规律。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N= 1e6 + 10;typedef long long LL;LL a, b;int main(){	while(~ scanf("%lld%lld", &a, &b)){		LL x = a + b - 2;		LL y = (1 + x) * x / 2;		LL ans;		if((a + b) & 1) ans = y + a;		else ans = y + b;		printf("%lld\n", ans);	}	}/*4 7 1 41 21 21 42 32 33 43 44 3 1 21 22 44 35 8 3 13 25 23 44 54 12 13 53 1*/
        
       
      
     

　　

F. Funny Language

首先可以$O(n\log n)$枚举出所有位于同一段序列内部的区间$\gcd$，只需要考虑横跨了多个序列的情况。

考虑容斥，设$f_d$表示$d|\gcd$的方案数，则实际值$g_d=f_d-g_{2d}-g_{3d}-...$，可以在$O(n\log n)$的时间内求出所有$g$。

考虑如何求$f_d$：对于每个序列计算有多少个前后缀是$d$的倍数，以及整个序列是否是$d$的倍数，枚举横跨序列的个数用组合数计算答案即可。

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

#include
     
      #include
      
       using namespace std;const int N=80010,P=1000000007;int D,i,j,fac[N],inv[N],ans[N],fin;int n,len[N],st[N],en[N],pool[N],cur,base;int vis[N],vl[N],vr[N],ok[N],all,m,q[N];int sl[2],sr[2],slr[2];vector
       
        vpre[N],vsuf[N],vall[N];int gcd(int a,int b){return b?gcd(b,a%b):a;}inline int C(int n,int m){return n
        
         1&&gcd(a[i],v[l[j]-1])==gcd(a[i],v[j]))l[j]=l[l[j]-1];		up(ans[v[j]],1LL*(j-l[j]+1)*base%P);	}}inline void visit(int x){	if(vis[x]==D)return;	vis[x]=D;	vl[x]=vr[x]=ok[x]=0;	q[++m]=x;}inline int work(){	int i,j,k,x,y,ret,ans=0;	all=m=0;	for(i=D;i
         
          =st[i];j--){			suf=gcd(suf,pool[j]);			vsuf[suf].push_back(i);		}	}	for(D=1;D
         
        
       
      
     

　　

G. Game of Tic-Tac-Toe

总状态只有$2\times 3^9$，博弈DP后即可得到下棋策略。

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

　　

H. Hill and Subhill

高维差分。

#include
     
      #include
      
       #define FOR(i,a,b) for(int i=a;i<=b;i++)#define FOV(i,a,b) for(int i=a;i>=b;i--)#define CLR(a) memset(a,0,sizeof a)#define U 105][105][105#define FFF FOR(i,1,N)FOR(j,1,i)FOR(k,1,j)#define VVV FOV(i,N,1)FOV(j,i,1)FOV(k,j,1)typedef long long LL;int N,M,Q,x,y,z,a,d3as[U],d3ae[U],d3ds[U],d3de[U];LL d2a[U],d2d[U],d1[U],suffix1d[U],suffix2d[U],s1[U],s2[U],s31[U],s32[U];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}void solve(){  int x,y,z,a;  CLR(d3as);  CLR(d3ae);  CLR(d3ds);  CLR(d3de);  CLR(d2a);  CLR(d2d);  CLR(d1);  CLR(suffix1d);  CLR(suffix2d);  CLR(s1);  CLR(s2);  CLR(s31);  CLR(s32);  for(int i=0;i
      
     

　　

I. It is panic?

按题意模拟。

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

　　

J. JokeCoin

按左端点排序，树状数组维护右端点即可优化DP至$O(n\log n)$。

#include
     
      #include
      
       #include
       
        using namespace std;typedef vector
        
         V;typedef long long ll;const int N=200010,M=25,P=1000000007;int n, m;struct A{	int st, ed, v;}a[N];inline bool cmp(const A&a,const A&b){	return a.st
        
       
      
     

　　

K. King and ICPC

分治，预处理出$mid$到$[l,r]$每个点的背包，然后利用这个信息处理所有经过$mid$的询问。

时间复杂度$O((nd+m)\log n+md)$。

#include
     
      #include
      
       using namespace std;typedef vector
       
        V;typedef long long ll;const int N=50010,M=55;const ll inf=1LL<<60;int n,m,q,i,j,a[N][3];ll f[N][M],g[N][M];int e[300010][2];ll ans[300010];inline void up(ll&a,ll b){a
        
         r||!v.size())return;	int mid=(l+r)>>1;	int i,j,k;	//[l..mid] [mid+1..r]	for(i=l;i<=mid+1;i++)for(j=0;j
         
          =l;i--)for(j=0;j
          
           <3;k++)up(f[i][(j+a[i][k])%m],f[i+1][j]+a[i][k]); for(i=mid;i<=r;i++)for(j=0;j
           
            mid)vr.push_back(x); else{ for(j=0;j
           
          
         
        
       
      
     

　　

L. Longest Simple Paths

Dijkstra求出最短路树后点分治统计即可。

#include
     
      #include
      
       const int N=30010,M=120010,inf=~0U>>1;int n,m,k,i,x,y,z,g[N],v[M],w[M],nxt[M],ok[M],ed,d[N],vis[N],son[N],f[N],size,now,T,pos[N];struct E{int x,y,w;E(){}E(int _x,int _y,int _z){x=_x,y=_y,w=_z;}}a[M];inline bool cmp(E a,E b){return a.x==b.x?a.y>b.y:a.x
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];ok[ed]=1;g[x]=ed;}struct Num{  int x,y;  Num(){x=y=0;}  Num(int _x,int _y){x=_x,y=_y;}  inline Num operator+(Num b){    if(x==b.x)return Num(x,y+b.y);    return x
        
         >1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}inline void change(int x,int a,int b,int c,int d){  if(a==b){val[x].x=d;return;}  int mid=(a+b)>>1;  c<=mid?change(x<<1,a,mid,c,d):change(x<<1|1,mid+1,b,c,d);  val[x]=val[x<<1]+val[x<<1|1];}void dfs(int x){  vis[x]=1;  for(int i=g[x];i;i=nxt[i])if(!vis[v[i]]&&d[x]+w[i]==d[v[i]])a[++m]=E(x,v[i],w[i]),dfs(v[i]);}void findroot(int x,int pre){  son[x]=1;f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(size-son[x]>f[x])f[x]=size-son[x];  if(f[x]
         
          =k)return;  Num t=get(k-dep);  if(t.y)ans+=Num(t.x+sum,t.y);  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre)dfscal(v[i],x,dep+1,sum+w[i]);}void dfsadd(int x,int pre,int dep,int sum){  if(dep>=k)return;  up(dep,Num(sum,1));  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre)dfsadd(v[i],x,dep+1,sum+w[i]);}void solve(int x){  int i;  T++,up(1,Num(0,1));  for(i=g[x];i;i=nxt[i])if(ok[i])dfscal(v[i],x,2,w[i]),dfsadd(v[i],x,2,w[i]);  for(i=g[x];i;i=nxt[i])if(ok[i])ok[i^1]=0,f[0]=size=son[v[i]],findroot(v[i],now=0),solve(now);}int main(){  read(n),read(m),read(k);k++;  for(i=1;i<=m;i++){    read(x),read(y),read(z);    a[i]=E(x,y,z);    a[i+m]=E(y,x,z);  }  std::sort(a+1,a+m+m+1,cmp);  for(i=1;i<=m+m;i++)add(a[i].x,a[i].y,a[i].w);  for(i=2;i<=n;i++)d[i]=inf;  build(1,1,n),change(1,1,n,1,0);  while(val[1].x