Codeforces Round #384 (Div. 2) //复习状压... 罚时爆炸 BOOM

Codeforces Round #384 (Div. 2) //复习状压... 罚时爆炸 BOOM _DONE

阅读量：4981 次

发布时间：2019-06-12

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

不想欠题了..... 多打打CF才知道自己智商不足啊...

A. Vladik and flights

给你一个01串相同之间随便飞没有费用不同的飞需要费用为 abs i-j

真是题意杀啊，，，实际上我们只考虑01转换的代价一定为1如果目的地和起点相同费用为0

不相同肯定为1 因为0旁边必然有1

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;typedef long long ll;template 
              
               inline bool r(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) { return 0; //EOF } while (c != '-' && (c < '0' || c > '9')) { c = getchar(); } sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'); } ret *= sgn; return 1;}const int N = 1e5+10;char ch[N];int main(){ int n; r(n); int x,y; r(x),r(y); scanf("%s",ch+1); if(ch[x]==ch[y]) { printf("0\n"); } else{ printf("1\n"); } return 0;}

B. Chloe and the sequence

给一个n，然后按照 1 121 1213121 的第n个串

那么肯定是二分n次必得.... 赛场拿python写的（L+R）没加括号T1

n,k = map(int, input().split())def calc(k):    L = 0    R = 2**n    M = L+R//2    ans = 0    while(k!=M):        if(k>M):            L = M        else:            R = M        M = (L+R)//2        ans+=1    print(n-ans)calc(k)

C. Vladik and fractions

问2/n能不能由1/a+1/b+1/c（a,b,c互不相同）太粗心，没看到互不相同 wa1 没特判1 被hack 1

手推 a = n b = n+1 c = n*(n+1)

n=1分不出的

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;typedef long long ll;template 
              
               inline bool r(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) { return 0; //EOF } while (c != '-' && (c < '0' || c > '9')) { c = getchar(); } sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'); } ret *= sgn; return 1;}int main(){ int n; r(n); if(n==1) printf("-1"); else printf("%d %d %d\n",n,n+1,n*(n+1)); return 0;}

D.Chloe and pleasant prizes

带权有根树选两个不相交子树的之和最大，裸DFS。

吐槽一下自己奇差无比的代码。。。两个dfs才完成任务...

还因为各种写搓 wa了3次

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N = 2e5+10;vector
           
            g[N];ll sum[N];ll son[N];int a[N];void push(int x,int y){g[x].push_back(y);g[y].push_back(x);}bool flag = true;void UMAX(ll& a,ll& b,ll c){ if(c>a) { b = a; a = c; } else{ if(c>=b) { b = c; } }}ll dfs(int now,int pre){ sum[now] += a[now]; bool mk = true; for(int i=0;i

AC代码

贴一下陈老师的代码....

#include
      
       #include
       
        typedef long long ll;const int N=200010;const ll inf=1LL<<60;int n,i,x,y,a[N],g[N],v[N<<1],nxt[N<<1],ed;ll f[N],dp[N],ans=-inf;inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x,int y){  f[x]=a[x];  dp[x]=-inf;  for(int i=g[x];i;i=nxt[i]){    int u=v[i];    if(u==y)continue;    dfs(u,x);    f[x]+=f[u];    if(dp[x]>-inf)ans=std::max(ans,dp[x]+dp[u]);    dp[x]=std::max(dp[x],dp[u]);  }  dp[x]=std::max(dp[x],f[x]);}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  for(i=1;i
        
         -inf)printf("%I64d",ans);else puts("Impossible");}

claris

E. Vladik and cards

题意给以一个1-8组成的串选出一个子串（在原串中可以不连续）选出来的串每个数相同的一定相邻而且每种数的个数相差不超过1

比赛时只想到DFS的解，后来证实是错的

后来看别人的代码一脸蒙=。=... 后来一神说了两个数组的作用才明白...就这样参考claris的写法

而且....

这样也写了好久而且还少更新状态长度可以为0......

#include
      
       #include
       
        void Min(int &a,int b) {
    if(a>b) a=b;}void Max(int &a,int b) {
    if(a
        
         n)continue;                 for(int l=0;l<8;l++)                {                    if((1<