这场有点难，QAQ。补了好久(｡• ︿•̀｡) ，总算能写题解了(つд⊂)

题意

​ 求\([l,r](1\le l_i\le r_i\le 9\cdot 10^{18})\)的中的 可以被自己每一位上的数字整除的数 的个数。

题解：

​ 知识：如果m%a=0,则任意x, x%a = (x%m)%a。

​ 2520是2~9的lcm。因此任何时候都有2520%pre_lcm==0。

​ 因为2520%pre_lcm==0，所以x%pre_lcm==(x%2520)%pre_lcm

​ 数位DP，状态中记录当前位置pos，到当前为止除了0的每一位的最小公倍数pre_lcm以及乘积对2520的模pre_mod。

​ pre_lcm总共就50多个，因此可以离散化一下。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define M 2520#define ll long longint hash[M],digit[25];ll dp[25][M][60];void init(){//离散化pre_lcm    for(int i=1,cnt=0;i<=M;i++)        if(M%i==0)hash[i]=++cnt;}int gcd(int a,int b){    return b?gcd(b,a%b):a;}int lcm(int a,int b){    return a/gcd(a,b)*b;}ll dfs(int pos,int pre_mod,int pre_lcm,bool limit){    if(pos==0)return pre_mod%pre_lcm==0;    if(!limit&&~dp[pos][pre_mod][hash[pre_lcm]])        return dp[pos][pre_mod][hash[pre_lcm]];    int up=limit?digit[pos]:9;    ll ans=0;    for(int d=0;d<=up;d++)        ans+=dfs(pos-1,(pre_mod*10+d)%M,d?lcm(pre_lcm,d):pre_lcm,limit&&d==up);    if(!limit)dp[pos][pre_mod][hash[pre_lcm]]=ans;    return ans;}ll solve(ll n){    int i;    for(i=0;n;n/=10)digit[++i]=n%10;    return dfs(i,0,1,1);}int main() {    int t;    std::cin>>t;    init();    memset(dp,-1,sizeof dp);    while (t--) {        ll l,r;        std::cin>>l>>r;        std::cout<
        
         <<"\n";    }    return 0;}
        
       
      
     
    

题意

有n个商店，距离为\(d_i\)，商品单价为\(v_i\)，有m次询问：\(l_i,r_i,c_i,sum_i\)，下标在区间\([l_i,r_i]\)内的商店中，最大距离不超过\(c_i\)且购买的总价格为\(sum_i\)，是否有可能？输出一个长度为m的01串，1代表不可能，0代表可能。

题解

整体二分（cdq分治）。总的区间是\([l,r]\)，m个询问中有的是完全在\([l,mid]\)区间中，或者完全在\([mid+1,r]\)中，这些可以递归解决，还有一类跨越中点的：\(l_i<=mid,r_i>mid\) ，可以用动态规划来解决。

\(f[i][j]\)代表区间为\([i,mid]\)的总价值为j的最大距离的最小值。

\(g[i][j]\)代表区间为\([mid+1,i]\)的总价值为j的最大距离的最小值。

那么有

\[ f[i][j]= \begin{cases} min(f[i+1][j],max(f[i-1][j-v[i]],d[i])),\ v[i]\le j\le 100\\ f[i+1][j],\ j<v[i] \end{cases}\\ g[i][j]= \begin{cases} min(g[i-1][j],max(g[i+1][j-v[i]],d[i])),\ v[i]\le j\le 100\\ g[i-1][j],\ j<v[i] \end{cases} \]

对于区间\([i,j]\)的最大距离的最小值就是\(min(max(f[i][k],g[j][sum-k])),0\le k\le sum\)。

f和g可以放在一个二维数组中。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 20005#define M 100005#define inf 0x7fffffffusing namespace std;int T,n,m;int v[N],d[N],f[N][105];struct Query{    int l,r,c,sum,i;}q[M],tmp[M];int ans[M];void solve(int l,int r,int ql,int qr){    if(ql>qr)return;    if(l==r){        for(int i=ql;i<=qr;i++)            ans[q[i].i]=q[i].sum==v[r]&&d[r]<=q[i].c;        return;    }    int mid=l+r>>1;    int w1=ql,w2=qr,w3=0;    for(int i=ql;i<=qr;i++){//将三类询问划分一下        if(q[i].r<=mid)q[w1++]=q[i];        else if(q[i].l>mid)tmp[w2--]=q[i];        else tmp[w3++]=q[i];    }    if(w3){        for(int i=1;i<=100;i++)f[mid][i]=f[mid+1][i]=inf;        f[mid][v[mid]]=d[mid];f[mid][0]=0;        f[mid+1][v[mid+1]]=d[mid+1];f[mid+1][0]=0;        for(int i=mid-1;i>=l;i--)            for(int j=0;j<=100;j++)                if(j>=v[i])f[i][j]=min(f[i+1][j],max(f[i+1][j-v[i]],d[i]));                else f[i][j]=f[i+1][j];        for(int i=mid+2;i<=r;i++)            for(int j=0;j<=100;j++)                if(j>=v[i])f[i][j]=min(f[i-1][j],max(f[i-1][j-v[i]],d[i]));                else f[i][j]=f[i-1][j];        for(int i=0;i
       
      
     
    

题意

n盏灯，m个开关（\(n,m\le 500\)）。每个开关最多控制两盏灯，开关是并联的。

给出每盏灯能够亮的开关的状态，满足其中一个或多个都可以亮。

求所有开关的状态，使得所有灯都能亮。不存在则输出-1。

题解

解法1.网络流

建图：s->开关，若控制一盏灯或控制两盏灯却状态相反，则容量为1，否则为2；

​ 开关->控制的灯，容量1；

​ 灯->t，容量1。

若s流出的边满流则有解。判断一下最大流中开关流向的灯是哪一盏，就可以得出该开关的状态。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1005#define inf 0x3f3f3f3fusing namespace std;struct edge{int to,next,w;}e[5005];int head[N],g[N],cnt;int st,ed;int d[N],ans,tans;char o[4];int n,m;int swi[N][2],la[N][2];void add(int u,int v,int c){    e[cnt]=(edge){v,head[u],c};head[u]=cnt++;    e[cnt]=(edge){u,head[v],0};head[v]=cnt++;}void init(){    cnt=0;    memset(head,-1,sizeof head);}int bfs(){    memset(d,-1,sizeof d);    queue
         
          q; q.push(st); d[st]=0; while(!q.empty()){ int i,k=q.front(); q.pop(); for(i=head[k];~i;i=e[i].next){ int v=e[i].to; if(e[i].w>0&&d[v]==-1){ d[v]=d[k]+1; q.push(v); } } } return d[ed]>0;}int dinic(int k,int low){ if(k==ed||low==0)return low; int a,res=0; for(int &i=g[k];~i;i=e[i].next){ int v=e[i].to; if(d[v]==d[k]+1&&e[i].w>0&&(a=dinic(v,min(low,e[i].w)))){ res+=a; low-=a; e[i].w-=a; e[i^1].w+=a; if(!low)break; } } return res;}void solve(){ ans=0; while(bfs()){ memcpy(g,head,sizeof g); while(tans=dinic(st,inf))ans+=tans; }}int main() { while(~scanf("%d%d",&n,&m)){ memset(la,0,sizeof la); init(); ed=n+m+1; for(int i=1,k;i<=n;i++){ scanf("%d",&k); add(i+m,ed,1); for(int j=1,x;j<=k;j++){ scanf("%d %s",&x,o); swi[x][la[x][0]>0]=o[1]=='N'; la[x][la[x][0]>0]=i; add(x,i+m,1); } } for(int i=1;i<=m;i++) add(st,i,(la[i][1]&&swi[i][0]!=swi[i][1])?1:2); solve(); if(ans
         
        
       
      
     
    

解法2. 二分匹配

只控制一盏，或控制两盏且状态相同的开关，状态可以确定下来，点亮的灯做上标记，并且cnt++。

控制两盏灯且状态相反的开关，与未标记的灯进行二分匹配（匈牙利算法），因为这种开关只能开其中一盏灯，所以匹配成功就cnt++。若cnt==n则有解。

#include 
    
     #include 
     
      #define N 1005#define inf 0x3f3f3f3fchar o[4];int n,m;int swi[N][2],la[N][2],ans[N],ok[N];int vis[N],lk[N];bool find(int x){    for(int i=0;i<2;i++){        int v=la[x][i];        if(ok[v]||vis[v])continue;        vis[v]=1;        if(!lk[v]||find(lk[v])){            lk[v]=x;            ans[x]=swi[x][i];            return 1;        }    }    return 0;}int main() {    while(~scanf("%d%d",&n,&m)){        memset(la,0,sizeof la);        memset(lk,0,sizeof lk);        memset(ok,0,sizeof ok);        int cnt=0;        for(int i=1,k;i<=n;i++){            scanf("%d",&k);            for(int j=1,x;j<=k;j++){                scanf("%d %s",&x,o);                swi[x][la[x][0]>0]=o[1]=='N';                la[x][la[x][0]>0]=i;            }        }        for(int i=1;i<=m;i++)if(!la[i][1]||swi[i][0]==swi[i][1]){            ans[i]=swi[i][0];ok[la[i][0]]=ok[la[i][1]]=1;        }        for(int i=1;i<=m;i++)            if(la[i][1]&&swi[i][0]!=swi[i][1]){                memset(vis,0,sizeof vis);                if(find(i))cnt++;            }        for(int i=1;i<=n;i++)if(ok[i])cnt++;        if(cnt
     
    

解法3. 舞蹈链DLX

DLX重复覆盖问题。开关的两个状态为行，灯为列，所以是2m行n列。搜索时，开关的一个状态被用了，就不能用另一个状态了。

抄板子抄错1个字母居然也过了，900ms+，然后对照检查+实验了好久才发现。

#include 
    
     #include 
     
      #define N 1005*1005#define RN 1005#define CN 1005int sw[RN];struct DLX{    int size,n,m;    int D[N],U[N],L[N],R[N],row[N],col[N];    int H[RN],S[CN],cnt,ans[RN];    void init(int _n,int _m){        n=_n,m=_m,size=m;        for(int i=0;i<=m;i++){            D[i]=U[i]=i;            R[i]=i+1;            L[i]=i-1;            S[i]=0;        }        L[0]=m;R[m]=0;        for(int i=1;i<=n;i++)H[i]=-1;    }    void link(int r,int c){        ++S[col[++size]=c];        row[size]=r;        U[size]=U[c];        D[size]=c;        D[U[c]]=size;        U[c]=size;        if(H[r]<0) L[size]=R[size]=H[r]=size;        else{            R[size]=R[H[r]];            L[size]=H[r];            L[R[H[r]]]=size;            R[H[r]]=size;        }    }    void del(int p){        for(int i=D[p];i!=p;i=D[i])            R[L[i]]=R[i],L[R[i]]=L[i];    }    void reback(int p){        for(int i=U[p];i!=p;i=U[i])            R[L[i]]=i,L[R[i]]=i;    }    int dance(int x){        if(!R[0]){            cnt=x;            return 1;        }        int c=R[0];        for(int i=R[0];i;i=R[i])            if(S[i]
     
    

题意

给定两个n阶二维数组，0、90、180、270度旋转其中一个（不能翻转）,求与另一个重合的数字最多有多少个。

题解

不用模拟旋转，只要找出对应位置即可。我比赛时，t==3的地方写成{y,x},然后wa了一次，于是改成两个都旋转一下再和另一个不旋转时的比较，就水过去了。这让我发现，有很多时候AC的代码也是错误的。以下是我改正后的代码。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 35using namespace std;struct p{int x,y;};int n,a[2][N][N],ans;p rot(int x,int y,int t){    if(t==1)        return (p){y,n-1-x};    if(t==2)        return (p){n-1-x,n-1-y};    if(t==3)        return (p){n-1-y,x};    return (p){x,y};    }int main() {    while(scanf("%d",&n)&&n){        ans=0;        for(int k=0;k<2;k++)        for(int i=0;i
       
      
     
    

题意

给两个字符串，求最大公共子串的长度

题解

#include
    
     #include
     
      #include
      
       #include
       
        #define N 500005using namespace std;int wa[N],wb[N],wv[N],ss[N];int sa[N],rk[N],height[N];char s[N];void da(char *r,int *sa,int n){    int i,j,p,*x=wa,*y=wb,m=128;    for(i=0;i
        
         =0;i--)sa[--ss[x[i]]]=i;    for(j=1,p=1;p
         
          =j)y[p++]=sa[i]-j; for(i=0;i
          
           =0;i--)sa[--ss[wv[i]]]=y[i]; for(swap(x,y),p=1,x[sa[0]]=0,i=1;i
           
            =n&&sa[i-1]
            
             
              =n) ans=max(ans,height[i]); printf("%d\n",ans); return 0;}
             
            
           
          
         
        
       
      
     
    

题意

给定一棵树每个节点的父节点，有K个操作：C x为移除节点x和它到父节点的边；Q a b，询问a到b是否有路径。

题解

解法1. dfs染色

对于每个给定的p[a]，就加一条边p[a]->a，然后dfs染色。询问时判断一下是否是同色，移除时dfs(a)再染过一下颜色。这种做法没有TLE，但是如果给一条长链还是有可能超时的。

#include
    
     #include
     
      #include
      
       #include
       
        #define in(s) freopen(#s".in","r",stdin)#define out(s) freopen(#s".out","w",stdout);#define ll long long#define N 20005#define M 3000#define inf 0x3f3f3f3fusing namespace std;int t,n,k,p[N];struct edge{int v,next;}e[N];int head[N],cnt;bool vis[N];int c[N],cc;void dfs(int x){    c[x]=cc;    for(int i=head[x];i;i=e[i].next)if(p[e[i].v]){        dfs(e[i].v);    }}bool path(int a,int b){    if(c[a]==c[b])        return 1;    return 0;}int main() {    scanf("%d",&t);    for(int cas=1;cas<=t;cas++){        printf("Case #%d:\n",cas);        memset(p,0,sizeof p);        memset(head,0,sizeof head);        cc=cnt=0;        scanf("%d %d",&n,&k);        for(int i=1;i<=n;i++){            scanf("%d",&p[i]);            e[++cnt]=(edge){i,head[p[i]]};            head[p[i]]=cnt;        }        for(int i=1;i<=n;i++)if(p[i]==0){cc++;dfs(i);}        for(int i=1;i<=k;i++){            char op;int a,b;            scanf(" %c %d",&op,&a);            if(op=='C'){                p[a]=0;                cc++;                dfs(a);            }else{                scanf("%d",&b);                printf("%s\n",path(a,b)?"YES":"NO");            }        }    }    return 0;}
       
      
     
    

解法2. 逆向离线并查集

读入所有操作，再离线倒着处理，删边变成加边，并查集解决。要注意一个点可能移除多次，第一次移除时才能合并。

#include 
    
     #include 
     
      #define M 5005#define N 20005int a[M],b[M],ans[M];int T,n,m,p[N],f[N],c[N];int find(int x){    if(f[x]==x)return x;    return f[x]=find(f[x]);}void uni(int a,int b){    if(!b)return;    f[find(a)]=find(b);}int main() {    scanf("%d",&T);    for(int cas=1;cas<=T;cas++){        printf("Case #%d:\n",cas);        scanf("%d%d",&n,&m);        memset(b,0,sizeof b);        memset(c,0,sizeof c);        for(int i=1;i<=n;i++)scanf("%d",&p[i]),f[i]=i;        for(int i=1;i<=m;i++){            char o;            scanf(" %c%d",&o,&a[i]);            if(o=='C')c[a[i]]++;            else scanf("%d",&b[i]);        }        for(int i=1;i<=n;i++)if(!c[i])uni(i,p[i]);        for(int i=m;i;i--){            if(b[i])ans[i]=find(a[i])==find(b[i]);            else if(--c[a[i]]==0) uni(a[i],p[a[i]]);//c减为0才合并        }        for(int i=1;i<=m;i++)            if(b[i])printf("%s\n",ans[i]?"YES":"NO");    }    return 0;}
     
    

题意

1~n城市海拔从高到低，现在给出一些边，方向是从高到低。两个城市disjoint 当且仅当有两条路径从1出发，分别到这两个城市，且只在1节点相交。输出disjoint的城市有几对。

题解

分三类点，1. 与1直接相连，2. 所有1来的路径都必定经过某一点，3. 从1过来的路径没有必定经过的点。

第1和第3类点x，令f[x]=x，第2类点，令f[x]=p，p是必定经过的点的f。

第1类的好判断，判断2，3类需要利用已经计算出来的f：

因为边只能是海拔高到低的，下标小的海拔高，因此所有与 i 相连的比 i 小的点j 和k(\(j\neq k\))中若存在f[j]!=f[k]，就是第3类，否则是第2类，p就是f[j]。

这样 f 相同的就是同一组，同一组内的就是不disjoint的。用总对数减去每组内的对数就是答案了。

#include 
    
     #include 
     
      #define N 1005#define M 100005using namespace std;int n,m,g[N][N],num[N],f[N];int main() {    while(~scanf("%d%d",&n,&m)){        memset(g,0,sizeof g);        memset(num,0,sizeof num);        memset(f,0,sizeof f);        for(int i=1,u,v;i<=m;i++){            scanf("%d%d",&u,&v);            g[u][v]=g[v][u]=1;            if(u==1)f[v]=v;            if(v==1)f[u]=u;        }        f[1]=1;        for(int i=2;i<=n;i++)if(!f[i]){            int ok=1,p;            for(int j=1;j
     
    

题意

若0~k阶差分都是单调的，那么就称为k阶单调。

如果0阶差分是不单调的，输出“ugly series”，否则如果0~n-1阶都是单调的，就输出“nice series”，否则输出最大的k。

题解

直接模拟会超时，我们可以把0压缩一下，时间复杂度证明见下面的官方题解。如何压缩呢？用L，R游标的移动来实现。

#include 
    
     #include 
     
      using namespace std;#define N 100005#define ll long longint T,n;ll a[N];int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;i++)            scanf("%lld",&a[i]);        int i,j,L,R;        for(i=0,L=1,R=n;i
      
       
        a[j])inc=1;                else if(a[j+1]
        
         1)L--;//如果这是压缩过的串，L--，这次还要在左边加一个0。            R--;            while(L