LRLC 内部测试赛 Part1

· · 个人记录

目前所有题都已经AC，我将在本篇文章内说一下我的做法。但无法绝对保证正确性。因此有人有时间的话欢迎来hack我的做法。

A.Combination Of Numbers

设f[i][j]表示前i个数中选取的数的总和为j的方案数。答案显然为f[n][t]。初始化f[0][0]=1。

对于第i个数仅有2种选择：选或者不选。因此f[i][j]=f[i-1][j]+f[i-1][j-a[i]]

#include <bits/stdc++.h>
#include <ext/rope>
namespace mxr{
    #define inc(i,a,b) for(register int i=a;i<=b;i++)
    #define dec(i,a,b) for(register int i=a;i>=b;i--)
    using namespace std;
    using namespace __gnu_cxx;
    template<class nT>
    void read(nT& x){
        char c;while(c=getchar(),!isdigit(c));
        x=c^48;while(c=getchar(),isdigit(c)) x=x*10+c-48;
    }
}
using namespace mxr;
long long f[25][1010],n,t,a[26];
int main(){
    read(n); read(t);
    f[0][0]=1;
    inc(i,1,n) read(a[i]);
    inc(i,1,n){
        inc(j,0,t) f[i][j]=f[i-1][j];
        inc(j,a[i],t) f[i][j]+=f[i-1][j-a[i]];
    }
    cout<<f[n][t];
}

显然这道题是个dp模板题

B.Word Game

我们假设有一个26个点的图，每个点代表一个小写字符。

我们发现对于一个字符串可以视为从该串开头的字符所代表的点向结尾所代表的点连一条有向边。

那么题目问题转化为是否存在一种方案，使得每条边都不重不漏地经过一次。

这样一来问题就转化成了经典地有向欧拉图和半欧拉图问题。

对于有向半欧拉图地判定：所有点的入度和出度相等，或者仅有2个点的入度和出度不等，但这两个点的入读和出度的差的和必须等于0（就是说rudu[a]-chudu[b]+rudu[b]-chudu[b]=0）

#include <bits/stdc++.h>
#include <ext/rope>
namespace mxr{
    #define inc(i,a,b) for(register int i=a;i<=b;i++)
    #define dec(i,a,b) for(register int i=a;i>=b;i--)
    using namespace std;
    using namespace __gnu_cxx;
    template<class nT>
    void read(nT& x){
        char c;while(c=getchar(),!isdigit(c));
        x=c^48;while(c=getchar(),isdigit(c)) x=x*10+c-48;
    }
}
using namespace mxr;
int n,rudu[110],chudu[110];
char s[200010];
int ans[4],tot;
int judge(){
    inc(i,0,25) if(rudu[i]!=chudu[i]) ans[++tot]=i;
    int ans1=rudu[ans[1]]-chudu[ans[1]],ans2=rudu[ans[2]]-chudu[ans[2]];
    return (ans1+ans2==0);
}
int main(){
    read(n);
    inc(i,1,n){
        scanf("%s",s+1);
        int m=strlen(s+1);
        chudu[s[1]-'a'+1]++; rudu[s[m]-'a'+1]++;
    }
    int tot1=0;
    inc(i,0,25){
        if(rudu[i]!=chudu[i]) ++tot1;
    }
    if(tot1==0) printf("Yes");
    else if(tot1==2&&judge()) printf("Yes"); 
    else printf("No");
}

显然这道题又是个欧拉图模板题

C.Bullet Time

显然存在状压dp的做法。我们设f[i][j][k][s]表示前i个时间内，目前剩余子弹数为j,再打k发子弹就可以把逃犯打死，并且目前已经使用过的弹夹的集合的状态为s的这种情况是否能达到。

显然f的值有且仅有1和0两种。

因此bitset可以做到高度时间空间优化。

显然这是个状压模板题

#include <bits/stdc++.h>
#include <ext/rope>
namespace mxr{
    #define inc(i,a,b) for(register int i=a;i<=b;i++)
    #define dec(i,a,b) for(register int i=a;i>=b;i--)
    using namespace std;
    using namespace __gnu_cxx;
    template<class nT>
    void read(nT& x){
        char c;while(c=getchar(),!isdigit(c));
        x=c^48;while(c=getchar(),isdigit(c)) x=x*10+c-48;
    }
}
using namespace mxr;
int n,m,k,s,r;
int a[1010],b[1010],bo[1010],stop[1010];
int f[21][21][21][1024];
int main(){
    read(n); read(m); read(k); read(s); read(r);
    inc(i,0,k-1) read(a[i]),bo[a[i]]=1; 
    inc(i,1,r) read(b[i]),stop[b[i]]=1;
    f[0][m][n][0]=1;
    inc(i,1,10){
        if(stop[i]){
            inc(j,0,10){
                dec(w,n,n-i){
                    inc(l,0,(1<<k)-1) f[i][j][w][l]=f[i][j][w][l]|f[i-1][j][w][l];
                }
            }   
        }
        else{
            inc(j,0,10){
                dec(w,n,n-i){
                    inc(l,0,(1<<k)-1) f[i][j][w][l]=f[i][j][w][l]|f[i-1][j+1][w+1][l]|f[i-1][j][w][l];
                }
            }   
        }       
        dec(w,n,n-i){
            inc(prel,0,(1<<k)-1){
                inc(j,0,k) if((prel&(1<<j))==0){
                    f[i+s][a[j]][w][prel^(1<<j)]|=f[i][0][w][prel];
                }
            }   
        }       
    }
    inc(i,1,10){
        inc(j,0,10){
            inc(l,0,(1<<k)-1){
                if(f[i][j][0][l]){
                    cout<<i;
                    return 0;
                }
            }
        }
    }
}

D.Epidemic Diffusion

高精乘/加/取模模板。

#include<bits/stdc++.h>
using namespace std;
#define ST static
#define C const
#define int int
#define RT return
#define OP operator
#define LL long long
#define B bool
#define F friend
#define TH this
#define V void
#define W while
struct inf
{
    ST C int mod=100000000;
    ST C int width=8;
    B sign;
    size_t length;
    vector<int>num;
    inf(LL x=0){*TH=x;}
    inf(C string&x){*TH=x;}
    inf(C inf&x){*TH=x;}
    V cutLeadingZero(){W(num.back()==0&&num.size()!=1)num.pop_back();}
    V setLength()
    {
        cutLeadingZero();
        int tmp=num.back();
        if(tmp==0)length=1;
        else{length=(num.size()-1)*width;W(tmp>0)++length,tmp/=10;}
    }
    inf&OP=(LL x)
    {
        num.clear();
        if(x>=0)sign=1;else{sign=0;x=-x;}
        do{num.push_back(x%mod);x/=mod;}W(x>0);
        setLength();
        RT*TH;
    }
    inf&OP=(C string&str)
    {
        num.clear();
        sign=(str[0]!='-');
        int x,len=(str.size()-1-(!sign))/width+1;
        for(int i=0;i<len;i++)
        {
            int End=str.length()-i*width;
            int start=max((int)(!sign),End-width);
            sscanf(str.substr(start,End-start).c_str(),"%d",&x);
            num.push_back(x);
        }
        setLength();
        RT*TH;
    }
    inf&OP=(C inf&tmp)
    {
        num=tmp.num;
        sign=tmp.sign;
        length=tmp.length;
        RT*TH;
    }
    size_t size()C{RT length;}
    inf e(size_t n)C
    {
        int tmp=n%width;
        inf ans;
        ans.length=n+1;
        n/=width;
        W(ans.num.size()<=n)
            ans.num.push_back(0);
        ans.num[n]=1;
        W(tmp--)ans.num[n]*=10;
        RT ans* (*TH);
    }
    inf abs()C
    {
        inf ans(*TH);
        ans.sign=1;
        RT ans;
    }
    C inf&OP+()C{RT*TH;}
    inf OP+(C inf&b)C
    {
        if(!b.sign)RT*TH-(-b);
        if(!sign)RT b-(-*TH);
        inf ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if(g==0&&i>=num.size()&&i>=b.num.size())break;
            int x=g;
            if(i<num.size())x+=num[i];
            if(i<b.num.size())x+=b.num[i];
            ans.num.push_back(x%mod);
            g=x/mod;
        }
        ans.setLength();
        RT ans;
    }
    inf OP-()C
    {
        inf ans(*TH);
        if(ans!=0)ans.sign=!ans.sign;
        RT ans;
    }
    inf OP-(C inf&b)C
    {
        if(!b.sign)RT*TH+(-b);
        if(!sign)RT-((-*TH)+b);
        if(*TH<b)RT-(b-*TH);
        inf ans;
        ans.num.clear();
        for(int i=0,g=0;;i++)
        {
            if(g==0&&i>=num.size()&&i>=b.num.size())break;
            int x=g;
            g=0;
            if(i<num.size())x+=num[i];
            if(i<b.num.size())x-=b.num[i];
            if(x<0)
            {
                x+=mod;
                g=-1;
            }
            ans.num.push_back(x);
        }
        ans.setLength();
        RT ans;
    }
    inf OP*(C inf&b)C
    {
        int lena=num.size(),lenb=b.num.size();
        vector<LL> ansLL;
        for(int i=0;i<lena+lenb;i++)ansLL.push_back(0);
        for(int i=0;i<lena;i++)
            for(int j=0;j<lenb;j++)
                ansLL[i+j]+=(LL)num[i]* (LL)b.num[j];
        W(ansLL.back()==0&&ansLL.size()!=1)ansLL.pop_back();
        int len=ansLL.size();
        LL g=0,tmp;
        inf ans;
        ans.sign=(ansLL.size()==1&&ansLL[0]==0)||(sign==b.sign);
        ans.num.clear();
        for(int i=0;i<len;i++)
        {
            tmp=ansLL[i];
            ans.num.push_back((tmp+g)%mod);
            g=(tmp+g)/mod;
        }
        if(g> 0)ans.num.push_back(g);
        ans.setLength();
        RT ans;
    }
    inf OP/(C LL&b)C
    {
        inf c;
        c.num.clear();
        for(int i=0;i<num.size();i++)
            c.num.push_back(0);
        LL g=0;
        for(int i=num.size()-1;i>=0;i--)
        {
            c.num[i]=int((num[i]+g* mod)/b);
            g=num[i]+g* mod-c.num[i]* b;
        }
        for(int i=num.size()-1;c.num[i]==0;i--)
            c.num.pop_back();
        RT c;
    }
    inf OP/(C inf&b)C
    {
        inf aa((*TH).abs());
        inf bb(b.abs());
        if(aa<bb)RT 0;
        char*str=new char[aa.size()+1];
        memset(str,0,sizeof(char)*(aa.size()+1));
        inf tmp;
        int lena=aa.length,lenb=bb.length;
        for(int i=0;i<=lena-lenb;i++)
        {
            tmp=bb.e(lena-lenb-i);
            W(aa>=tmp)
            {
                ++str[i];
                aa=aa-tmp;
            }
            str[i]+='0';
        }
        inf ans(str);
        delete[]str;
        ans.sign=(ans==0||sign==b.sign);
        RT ans;
    }
    inf OP%(C LL&b)C
    {
        LL ans=0;
        for(int i=num.size()-1;i>=0;i--)ans=(ans*mod+num[i])%b;
        RT ans;
    }
    inf OP%(C inf&b)C{RT*TH-*TH/b*b;}
    inf&OP++(){*TH=*TH+1;RT*TH;}
    inf&OP--(){*TH=*TH-1;RT*TH;}
    inf&OP+=(C inf&b){*TH=*TH+b;RT*TH;}
    inf&OP-=(C inf&b){*TH=*TH-b;RT*TH;}
    inf&OP*=(C inf&b){*TH=*TH*b;RT*TH;}
    inf&OP/=(C LL&b){*TH=*TH/b;RT*TH;}
    inf&OP/=(C inf&b){*TH=*TH/b;RT*TH;}
    inf&OP%=(C LL&b){*TH=*TH%b;RT*TH;}
    inf&OP%=(C inf&b){*TH=*TH%b;RT*TH;}
    B OP<(C inf&b)C
    {
        if(sign&&!b.sign)RT 0;
        if(!sign&&b.sign)RT 1;
        if(!sign&&!b.sign)RT-b<-*TH;
        if(num.size()!=b.num.size())RT num.size()<b.num.size();
        for(int i=num.size()-1;i>=0;i--)
            if(num[i]!=b.num[i])RT num[i]<b.num[i];
        RT 0;
    }
    B OP>(C inf&b)C{RT b<*TH;}
    B OP<=(C inf&b)C{RT!(b<*TH);}
    B OP>=(C inf&b)C{RT!(*TH<b);}
    B OP!=(C inf&b)C{RT b<*TH||*TH<b;}
    B OP==(C inf&b)C{RT!(b<*TH)&&!(*TH<b);}
    B OP||(C inf&b)C{RT*TH!=0||b!=0;}
    B OP&&(C inf&b)C{RT*TH!=0&&b!=0;}
    B OP!(){RT(B)(*TH==0);}
    F ostream&OP<<(ostream&out,C inf&x)
    {
        if(!x.sign)out<<'-';
        out<<x.num.back();
        for(int i=x.num.size()-2;i>=0;i--)
        {
            char buf[10];
            sprintf(buf,"%08d",x.num[i]);
            for(int j=0;j<strlen(buf);j++)out<<buf[j];
        }
        RT out;
    }
    F istream&OP>>(istream&in,inf&x)
    {
        string str;
        in>>str;
        size_t len=str.size();
        int start=0;
        if(str[0]=='-')start=1;
        if(str[start]=='\0')
            RT in;
        for(int i=start;i<len;i++)
            if(str[i]<'0'||str[i]>'9')
                RT in;
        x.sign=!start;
        x=str.c_str();
        RT in;
    }
    inf pow(int n)
    {
        inf ans=1,base=*TH;
        W(n)
        {
            if(n&1)ans=ans*base;
            base=base*base;
            n>>=1;
        }
        RT ans;
    }
};
int main()
{
    inf n,m,t,p;
    cin>>n>>m>>t>>p;
    cout<<(m*t+n)%p;
}

显然这道题是个高精模板题

E.膨胀的木棍

我们会发现，直接求并不好求，因此可以考虑二分答案来验证。

显然，这条弦对应的圆心角越大，弧的长度就越长。具有单调性。

我们二分圆心角的度数。答案显然就是\frac{L}{2}tan(\frac{\theta}{2})

#include <bits/stdc++.h>
#include <ext/rope>
namespace mxr{
    #define inc(i,a,b) for(register int i=a;i<=b;i++)
    #define dec(i,a,b) for(register int i=a;i>=b;i--)
    using namespace std;
    using namespace __gnu_cxx;
    template<class nT>
    void read(nT& x){
        char c;while(c=getchar(),!isdigit(c));
        x=c^48;while(c=getchar(),isdigit(c)) x=x*10+c-48;
    }
}
using namespace mxr;
double Pi=acos(-1.0);
double L,n,C;
int main(){
    cin>>L>>n>>C;
    double L1=(1+n*C)*L;
    double l=0,r=Pi/2,ans=0.0;
    while(l+1e-16<=r){
        double mid=(l+r)/2;
        if(L1*sin(mid)/mid<=L){
            r=mid-(1e-16),ans=mid;
        }
        else l=mid+(1e-16);
    }
    printf("%.3lf",L/2*tan(ans/2));
}

显然这是个二分模板题

F.烁金的强迫症

显然最少的情况就是以右半部分作为模板，仅仅改变左半部分。模拟即可。

#include <bits/stdc++.h>
#include <ext/rope>
namespace mxr{
    #define inc(i,a,b) for(register int i=a;i<=b;i++)
    #define dec(i,a,b) for(register int i=a;i>=b;i--)
    using namespace std;
    using namespace __gnu_cxx;
    template<class nT>
    void read(nT& x){
        char c;while(c=getchar(),!isdigit(c));
        x=c^48;while(c=getchar(),isdigit(c)) x=x*10+c-48;
    }
}
using namespace mxr;
int n,m;
char a[2010][2010];
int main(){
    read(n); read(m);
    long long ans=0;
    inc(i,1,n) scanf("%s",a[i]+1);
    inc(i,1,n) inc(j,1,(m+1)/2){
        ans+=abs(a[i][j]-a[i][m-j+1]);
    }
    cout<<ans;
}

显然这道题是个模拟模板题

G.思维小水题

显然，尽可能多删除数一定会让答案更优。

仔细观察，发现大于\frac{n}{2}的数之间任意的gcd都是1。

那么我们枚举所有数的最大质因数p，并把它加入到集合S[p]中。

比如说n=9。刨除1不算，我们得到集合：S[2]=2,4,8，S[3]=3,6,9，S[1]=1,5,7。

注意，其中S[1]并不是表示最大质因数p是1，只是表示本身为质数或者1。另外由于是枚举的质因数，所以x不是质数的S[x]中一定没有元素。

简单分析可以得出两个性质：对于x>n/2的所有集合S[x]都不会有任何元素。除了S[1]以外的集合每个集合都至少有2个数(最少存在x和2x，但也有可能存在3x,4x,......)。

对于集合p如果元素个数是偶数，那么两两配对写到写字板中。否则将其中必定存在的元素2p扔到S[0]这个特殊的集合中代以后使用。

在上面的操作完成后，我们考虑S[0]中的集合。因为S[0]中的元素都是形如2p这种形式，所以gcd最少也是2。因此他们也可以两两配对。如果S[0]的元素个数是奇数特判一下就好啦。

至于剩下的S[1]这个集合。我们只能把他们全部留在脑子中。

根据上面的算法，假设[\frac{n}{2}+1,n]之间的质数个数为m，那么答案显然是1+m+\frac{(n-m-1+1)}{2}。

现在问题转化为了求1~n之间的质数的个数。（n<=1e12）

线性筛什么的不可能，只可能通过n<=1e7的数据。所以我们只能靠min25筛这种亚线性算法。

min25筛的复杂度是O(\frac{n^{\frac{3}{4}}}{log_2n})可以通过此题。

如果不会这种亚线性算法我们可以考虑分块打表大法，但要注意代码的长度限制。

#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
long long prime[10000010],num,sp1[10000010];
long long n,sqrtn,w[10000010],tot,g1[10000010],ind1[10000010],ind2[10000010];
int vis[10000010];
void pre(int n){
    vis[1]=1;
    inc(i,1,n){
        if(vis[i]==0){
            prime[++num]=i;
            sp1[num]=sp1[num-1]+1;
        }
        for(register int j=1;j<=num&&prime[j]*i<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
double dd[10000010];
long long ffind(long long n){
    num=0; tot=0;
    sqrtn=sqrt(n); pre(sqrtn);    
    for(register long long i=1;i<=n;){
        long long j=n/(n/i);
        w[++tot]=n/i; g1[tot]=w[tot]-1;
        if(n/i<=sqrtn) ind1[n/i]=tot;
        else ind2[n/(n/i)]=tot;
        i=j+1;
    }    
    inc(i,1,num) dd[i]=(double)(1.00/prime[i]);
    inc(i,1,num){
        for(register int j=1;j<=tot;j++){
            if(prime[i]*prime[i]>w[j]) break;
            long long ttmp=(w[j]*dd[i]+1e-9);
            long long k=ttmp<=sqrtn?ind1[ttmp]:ind2[n/ttmp];
            g1[j]-=g1[k]-sp1[i-1];
        }
    }
    return g1[1];
}
int main(){
    cin>>n;    
    long long m=ffind(n);
    long long mp=ffind(n/2);
    m=m-mp; long long tmp=(n-m)/2;        
    printf("%lld\n",m+tmp+1); 
}

显然这道题是个min25筛或者杜教筛模板题。

H.字符串水题

我们先考虑n<=1000的情况： 这种情况我们对于每个字符串看成一个点。每两个集合的点之间连线，构成一张二分图。显然跑二分图最小带权匹配就好了。

由于二分图带权匹配可以看作网络流中的最小费用最大流的模板，而且这道题的建边方式还这么憨憨。所以完全可以考虑模拟费用流。

回到原题，看到有关于后缀的情报我们立马考虑后缀自动机，反过来建立后缀树。

然后套模拟费用流的老鼠和洞的模型。

我们可以花费一定代价移动老鼠和洞，使得所有老鼠均进洞，我们需要最小化总代价。

为了方便，我们将每个老鼠的值设为-inf。表示将该老鼠和某一个洞匹配后额外的代价。由于我们会最小化总代价，因此这样将保证所有老鼠均进洞。

这样算到最后，我们只需要把答案加上 老鼠的个数\times inf就好了。

我们看这副图。假如我们知道a是老鼠b是洞，那么贡献显然是dep[a]+dep[b]-2*dep[lca]。

但是这并不代表答案就是它了。因为可能以后会反悔。

这时候一个性质会被我们需要：一个点最多反悔1次，也就是说要么就是老鼠反悔要么就是洞反悔。

看图就很容易明白：不交叉永远比交叉好。

我们考虑假如洞b变成了洞d，那么：

答案变成了什么呢？我们考虑原来的答案是：dep[a]+dep[b]-2dep[lca]，而现在的变成了dep[a]+dep[d]-2dep[g]。

这其中改变了什么呢？我们可以这么看：如果将a的权值改成-dep[b]+2dep[lca]，再次选择a(相当于之后反悔a了)就相当于将原来的答案-dep[b]+2dep[lca]变成了dep[a]，然后和洞d合并变成dep[a]+dep[d]-2dep[g]。

对于洞也和老鼠一样进行类似的反悔操作。这样就可以完成模拟费用流啦。（当dep[a]+dep[b]-2dep[lca]<0的时候允许进行反悔）

但是这道题并不需要这么麻烦对吧，因为后缀自动机endpos集合的优良性质，我们仅仅模拟数组就能确保答案等价于用堆维护的带反悔贪心。

#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
#define dec(i,a,b) for(register int i=a;i>=b;i--)
using namespace std;
class node{
    public:
    int ch[27],len;
    int link;
}sam[600010];
int last=1,size=1,judge1[600010],judge2[600010];
void addsam(int to){
    int u=last,cur=++size;
    sam[cur].len=sam[last].len+1;
    for(;u&&!sam[u].ch[to];u=sam[u].link) sam[u].ch[to]=cur;
    if(!u) sam[cur].link=1;
    else{
        int q=sam[u].ch[to];
        if(sam[q].len==sam[u].len+1) sam[cur].link=q;
        else{
            int neww=++size;
            sam[neww]=sam[q];
            sam[neww].len=sam[u].len+1;
            for(;u&&sam[u].ch[to]==q;u=sam[u].link) sam[u].ch[to]=neww;
            sam[q].link=neww; sam[cur].link=neww;
        }
    }
    last=cur;
}
int n,k;
char a[200010],b[200010];
int head[600010],cnt;
class littlestar{
    public:
    int to,nxt;
    void add(int u,int v){
        to=v; nxt=head[u];
        head[u]=cnt;
    }
}star[1200010];
int f[600010][21];
void dfs(int u){
    inc(i,0,19) f[u][i+1]=f[f[u][i]][i];
    for(int i=head[u];i;i=star[i].nxt){
        int v=star[i].to;
        f[v][0]=u;
        dfs(v);
    }
}
long long suma[600010],sumb[600010];
long long ans=0;
void dfs2(int u){
    suma[u]+=judge1[u];
    sumb[u]+=judge2[u];
    for(int i=head[u];i;i=star[i].nxt){
        int v=star[i].to;
        dfs2(v);
        suma[u]+=suma[v];
        sumb[u]+=sumb[v];
    }
    long long tmp=min(suma[u],sumb[u]);
    ans=(ans+max(0,(k-sam[u].len))*tmp);
    suma[u]-=tmp; sumb[u]-=tmp;
}
int main(){
    //freopen("string10.in","r",stdin);
    //freopen("string10.out","w",stdout);
    cin>>n>>k;
    scanf("%s",a+1);
    scanf("%s",b+1);
    reverse(a+1,a+1+n);
    reverse(b+1,b+1+n);
    inc(i,1,n) addsam(a[i]-'a');    
    last=1; 
    inc(i,1,n) addsam(b[i]-'a');    
    inc(i,1,size){
        star[++cnt].add(sam[i].link,i);
    }
    dfs(1);
    int u=1;
    inc(i,1,n){
        u=sam[u].ch[a[i]-'a'];
        if(i<k) continue;
        int v=u;
        dec(i,20,0){
            if(sam[f[v][i]].len>=k){
                v=f[v][i];
            }           
        }
        judge1[v]++;
    }
    u=1;
    inc(i,1,n){
        u=sam[u].ch[b[i]-'a'];
        if(i<k) continue;
        int v=u;
        dec(i,20,0){
            if(sam[f[v][i]].len>=k){
                v=f[v][i];
            }           
        }
        judge2[v]++;
    }
    dfs2(1);
    cout<<ans;
}

显然这是个后缀树上跑模拟费用流的模板题

I.报名签到

模拟即可，显然贡献为了不算重我们仅仅看每个人后面的距离最短是多少即可。

#include <bits/stdc++.h>
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n,a[1000010];
int main(){
    cin>>n;
    inc(i,1,n) scanf("%d",&a[i]);
    long long ans=0;
    inc(i,1,n-1){
        ans=(ans+max(a[i],a[i+1]));
    }
    cout<<ans;
}

显然这又是个模拟的模板题