Codeforces Round #526 (Div. 1)-白红宇

Codeforces Round #526 (Div. 1)

阅读量：7050 次

发布时间：2019-06-28

本文共 1617 字，大约阅读时间需要 5 分钟。

毕竟是上紫之后的第一场div1，还是太菜了啊，看来我要滚回去打div2了。

A. The Fair Nut and the Best Path

这题本来是傻逼贪心dfs，结果我越写越麻烦，然后就只有150了。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;int to[Maxn],nxt[Maxn],first[Maxn],tot=1;int n,u,v;ll a[Maxn],ans,w[Maxn],wi;queue
             
              q;inline void add(int u,int v,ll wi) { to[tot]=v; nxt[tot]=first[u]; w[tot]=wi; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; w[tot]=wi; first[v]=tot++;}ll dfs(int root,int fa) { ll mx=0,cd=0,sxz=a[root]; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) { ll temp=dfs(to[i],root)-w[i]; if(temp>mx) cd=mx,mx=temp; else cd=max(cd,temp); } sxz+=mx; ans=max(ans,sxz+cd); return sxz;}int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); for(int i=1;i

B - The Fair Nut and Strings

这道题开始时看上去很毒瘤，但是仔细一想会发现这里面有个树的结构，具体讲不太明白，自己看看代码就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;int n,k;char a[Maxn],s[Maxn];int main() { scanf("%d%d",&n,&k); scanf("%s",a); scanf("%s",s); if(k==1||strcmp(a,s)==0) { printf("%d\n",n); return 0; } int temp=0;ll sxz=2,ans=0; while(a[temp]==s[temp]) temp++;ans+=temp;ans+=2; for(int i=temp+1;i
             
              =k) { ans+=1ll*(n-i)*k; break; } ans+=sxz; } printf("%I64d\n",ans); return 0;}