Div1 526

• 这个E考试的时候没调出来真的是耻辱.jpg

A

求个直径就完事

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll long longstruct miku{    int to,next,val;}e[600010];int a[300010];int head[300010];int cnt;int n;ll ans;ll f[300010];void add(int x,int y,int z){    e[cnt]=(miku){y,head[x],z};    head[x]=cnt++;}void dfs(int x,int from){    f[x]=a[x];    ans=max(ans,(ll)a[x]);    for(int i=head[x];i!=-1;i=e[i].next)    {        int to1=e[i].to;        if(to1!=from)        {            dfs(to1,x);            ans=max(ans,f[x]+f[to1]-e[i].val);            f[x]=max(f[x],f[to1]+a[x]-e[i].val);        }    }}int main(){    scanf("%d",&n);    memset(head,-1,sizeof(head));    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    for(int i=1,x,y,z;i
        
       
      
     
    

B

可以发现，最优答案显然是能劈叉就劈叉...

然后这还是个特判题，有一些边界条件需要处理清楚...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 500005#define ll long longchar s[N],t[N];ll ans;int n,k,now,tmp;int main(){ scanf("%d%d%s%s",&n,&k,s+1,t+1);s[n+1]='#'; if(k==1)return printf("%d\n",n),0; for(now=1;s[now]==t[now];now++); if(now>n)return printf("%d\n",n),0;ans=now+1; for(int i=now+1;i<=n;i++) { tmp=tmp<<1; if(s[i]=='a')tmp++; if(t[i]=='b')tmp++; tmp=min(k-2,tmp); ans+=tmp+2; } printf("%lld\n",ans);}//
           
          
         
        
       
      
     
    

C

• 打死我也不会写的
• （极有可能真香

一看就知道是个傻逼题。

线段树维护值域，然后就是求出$l,r$这段的链长啥样就行...

然后判断这俩链是否能转化为同一个链...

D

$O(n^2)$枚举+验证就可以了...

然后可以想到维护处$L_i$和$R_i$表示$i$这个数左边第一个和它一样的，和右边第一个和它一样的...

然后考虑以$i$为结尾的答案是什么，$ans=\sum\limits_{j=1}[i,j]\times (j-\max{ L_{j...i}})\times(\min{R_{j...i}}-i)$，$[i,j]$表示，$i...j$满足要求

那么考虑$[i,j]$可以直接在枚举$i$的时候维护出来，$L_j$和$R_j$也可以在同时用单调栈维护出来，那么上面这个式子可以拆成$4$个部分，分别在线段树上再维护一下就好了...

代码没有

E

傻逼斜率优化！

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005#define ll long longstruct node{ll x,y,val;}a[N];int sta[N],top,n;ll f[N],ans;inline bool cmp(const node &a,const node &b){return a.x==b.x?a.y
            
             
              =y;}int find(int x){ int l=0,r=top; while(l
              
               >1; if(Y(sta[m],x)
               
                =1&&cmp1(i,sta[top-1],sta[top]))top--; sta[++top]=i; } printf("%lld\n",ans);}
               
              
             
            
           
          
         
        
       
      
     
    

F

是个根号算法，就算了.jpg