T1.码灵鼠

手推f[2],f[3]可以发现f[i]=i-1

给出归纳证明：

为什么E(ai)+E(aj)==2E(ai)？因为i和j是相互独立的。

记得long long

#include
      
       #include
       
        using namespace std;inline long long rd(){    long long ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}long long n;int main(){    n=rd();    for(int i=1;i<=n;i++){        long long x=rd();        printf("%lld\n",x+1ll);    }}
       
      

T2.So many prefix?

感觉是kmp，可是发现状态叠状态，很难做，暴力走人了

正解是这样的，那些重叠的状态，实际上i的上一个重叠位置就是fail[i]，因此f[i]可以由f[fail[i]]转移来，这样就解决了。

#include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=200005;char s[MAXN];int fail[MAXN];long long f[MAXN];int main(){    scanf("%s",s+1);    int lens=strlen(s+1);    for(int i=2,j=0;i<=lens;i++){        while(j>0&&s[i]!=s[j+1]) j=fail[j];        if(s[i]==s[j+1]) j++;        fail[i]=j;    }    long long ans=0;    for(int i=1;i<=lens;i++) f[i]=f[fail[i]]+1ll*(!(i&1));    for(int i=1;i<=lens;i++) ans+=f[i];    cout<
        
       
      

T3.Travel

之前A组的题，并没有写，考场上现推有点难受

考虑把R降序排序，从大到小枚举Ri，保证了上边界递减，然后从小到大枚举L，只考虑R大于Ri的部分，这样保证右边界一定为Ri，由于L是递增的，所以可以一条一条加边，第一次使得1和n连通便是L的最小值，这时候的L和Ri便是一组解，更新即可。

由于是从大到小枚举的R，所以每次更新，最后便是字典序最小的解。

复杂度O(αn^2)

#include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=1024;const int M=2048*4;int n,m;int frm[M],to[M],L[M],R[M],idr[M],idl[M];bool cmpr(int x,int y){
    return R[x]>R[y];}bool cmpl(int x,int y){
    return L[x]
         
          =ansr-ansl) {            ansr=R[v];            ansl=tmp;            continue;        }    }    if(ansr==-1) return puts("0"),0;    printf("%d\n",ansr-ansl+1);    for(int i=ansl;i<=ansr;i++) printf("%d ",i);    return 0;}