Codeforces Round #494 (Div. 3)爆炸记

一开始网站爆炸,502刷新了10min,那时就知道这场要gg了。。。
A.签到题
B.求一个01串包含a个0,b个1且恰好有x个位置s[i]不等于s[i+1];
考虑a,b大小关系确定第一个是0还是1,前面构造x-1个10或01,后面就连着输出相同的就好了。
没看到样例wa3两次。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define ll long long
#define out(a) printf("%d",a)
#define writeln printf("\n")
#define min(a,b) a<b?a:b;
#define max(a,b) a>b?a:b;
using namespace std;
int n,m,a,b,c,d,x,ans,now;
int read()
{
    int s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
ll readl()
{
    ll s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
int main()
{
    b=read(); a=read(); x=read(); 
    if (x==1) {
      for (int i=1;i<=a;i++)
        out(1);
      for (int i=1;i<=b;i++)
        out(0);
      return 0;
    }
    if (a>b) {
    for (int i=1;i<=x;i++)
      if (i&1) out(1),c++,now=1;
      else out(0),d++,now=0;
    }
    else {
    for (int i=1;i<=x;i++)
      if (i&1) out(0),d++,now=0;
      else out(1),c++,now=1;
    }
      a-=c; b-=d;
      if (now==1) {
        for (int i=1;i<=a;i++)
          out(1);
        for (int i=1;i<=b;i++)
          out(0);
      }
      else {
        for (int i=1;i<=b;i++)
          out(0);
         for (int i=1;i<=a;i++)
          out(1);
      }
    return 0;
}

C.找一个不小于k的区间平均值最大.
读错题意罚时爆炸QAQ。
记录前缀和然后二重循环扫一遍即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define ll long long
#define out(a) printf("%lld",a)
#define writeln printf("\n")
#define min(a,b) a<b?a:b;
#define max(a,b) a>b?a:b;
using namespace std;
int n,m,a,b,x,k,num;
double ans;
int sum[100050];
int read()
{
    int s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
ll readl()
{
    ll s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
int main()
{
    n=read(); k=read(); 
    for (int i=1;i<=n;i++) {
      x=read(); sum[i]=sum[i-1]+x;
    }
    for (int j=k;j<=n;j++) {
        num=-2333333;
    for (int i=j;i<=n;i++) 
      num=max(num,sum[i]-sum[i-j]);
    if ((double)num/j>ans) ans=(double)num/j;
    }
    printf("%.15f",ans);
    return 0;
}

D.给n个2的d次方的数,m个询问问是否有n个数的子集和等于x.
正解都想出来了,可就是没写出来,细节总是错错错QAQ
考虑把所有数都搞成2进制,如果这一位不够的话就往下一位拆。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define ll long long
#define out(a) printf("%d",a)
#define writeln printf("\n")
using namespace std;
int n,k;
int x,cnt,m,tot,ans;
int a[200050],b[200050];
bool flag;
int read()
{
    int s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
ll readl()
{
    ll s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
int main()
{
    n=read(),k=read();
    for (int i=1;i<=n;i++){
      x=read(); cnt=0;
      while (true) {
        if (x==1||x==0) break;
        cnt++; x/=2;
      }
      a[cnt]++; //out(cnt); writeln;
    }
    for (int i=1;i<=k;i++){
      m=read(); flag=false; tot=ans=0; b[0]=0;
      while (true) {
        b[++tot]=m%2;
        if (flag) break;
        m/=2;
        if (m==0||m==1) flag=true;
      }
      for (int j=tot;j>=0;j--)
        if (a[j-1]>=b[j]) ans+=b[j],b[j]=0;
        else {
          b[j]-=a[j-1];
          b[j-1]+=b[j]*2;
          ans+=a[j-1];
        }
      if (b[0]>0) out(-1);
      else out(ans); 
      writeln;
    }
    return 0;
}

总结
1.码力还是太差了,细节问题总出错。
2.心态问题,急忙交题不测样例是大忌,被一些bug卡的很烦。
3.读题能力差,现在由于cf复制的问题不太兹磁翻译,所以基本上都是读英语或dalao翻译,题意总是看错。
There is still a long way to go....

最后编辑于：2018.07.04 12:51:46