1003——Codeforces Round #494 (Div. 3)

http://codeforces.com/contest/1003

codeforces

2018.7.3参加（ABCD）
2018.7.4整理（E）

A：

模拟,求出最长的一段相同的数的个数。

B：

构造，先构造一个类似01010或者10101的字符串，假设x=6，就是0101010，哪个多，哪个放在前面。然后把剩余的数放到对应的位置，连起来。详见代码。

C：

n^2求前缀和，取max

D：

统计2^t的硬币有多少个，t=0,1,2...
因为要求最少的硬币，所以从大的往小的开始取，将b二进制分解后，从高位往低位扫，假设第i位 位1，说明需要一个2^(i-1)的硬币，查看有没有，没有就分解陈两个2^(i-2)的硬币，查看有没有。以此类推。

E：

构造，先构造一条链，然后往链上加点。（好像化学上的同分异构。。。）

A：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[1090];
int main () {
    int n = read();
    for (int i=1; i<=n; ++i) {
        a[i] = read();
    }
    sort(a+1,a+n+1);
    int ans = 0,cnt = 0;
    a[0] = -1;
    for (int i=1; i<=n; ++i) {
        if (a[i] == a[i-1]) cnt++;
        else {
            ans = max(ans,cnt+1);
            cnt = 0;
        }
    }
    ans = max(ans,cnt+1); // 漏写一句，卡了5分钟。。。
    cout << ans;
    return 0;
}

B：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int s[1000];
void work(int a,int b,int c,int x) {
    for (int i=1; i<=x+1; ++i) {
        if (i & 1) s[i] = c,a--;
        else s[i] = (!c),b--;
    }/*
    if (x & 1) s[x+1] = (!c),b--;
    else s[x+1] = c,a--;
    */
    for (int i=1; i<=x+1; ++i) {
        if (s[i] == c) {
            cout << c;
            while (a>0) cout << c,a--;
        }
        else {
            cout << (!c);
            while (b>0) cout << (!c),b--; // 写成cout<<(!b);卡了13分钟。。。
        }
    }   
}
int main () {
    int a,b,x;
    cin >> a >> b >> x;
    if (a > b) work(a,b,0,x);
    else work(b,a,1,x);
    return 0;
}

C：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int a[5005],sum[5005];
int main () {
    int n = read(),k = read();
    for (int i=1; i<=n; ++i) a[i] = read(),sum[i] = a[i] + sum[i-1];
    double ans = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=(i+k-1); j<=n; ++j) {
            double t1 = 1.0 * (sum[j] - sum[i-1]);
            double t2 = 1.0 * (j - i + 1);
            ans = max(ans, (t1/t2));
        }
    }
    printf("%.10lf",ans);
    return 0;
}

D：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200010;
int a[N],c[100];
void solve() {
    int b = read(),ans = 0,cnt = 0;
    for (int i=30; i>=0; --i) {
        if ((b >> i) & 1) cnt ++;
        if (cnt > 0) {
            if (c[i] >= cnt) ans += cnt,cnt = 0;
            else {
                cnt -= c[i];
                ans += c[i];
                cnt *= 2;
            }
        }
    }
    if (cnt) puts("-1");
    else cout << ans << "\n";
}
int main () {
    int n = read(),m = read();
    for (int i=1; i<=n; ++i) {
        a[i] = read();
        int t = log2(a[i]);
        c[t]++;
    }
    while (m--) solve();
    return 0;
}
/*
4 1
8 2 2 2
14
*/

E：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500100;
int n,d,k,tn;
int g[N];
void dfs(int u,int cur,int mx,int cnt) { // 点，当前深度，最大深度，儿子节点
    if (cur == mx) return; 
    int id;
    for (int i=1; i<=cnt; ++i) {
        ++tn;
        g[tn] = u;
        if (tn == n) {
            puts("YES");
            for (int i=2; i<=n; ++i) 
                printf("%d %d\n",i,g[i]);
            exit(0);
        }
        dfs(tn,cur+1,mx,k-1);
    }
}
int main () {
    n = read(),d = read(),k = read(); // d-zhijing k-dushu
    if (d+1 > n) {puts("NO");return 0;}
    if (n == 1) {
        if (d==0) printf("YES");
        else printf("NO");
        return 0;
    }
    if (n==2) {
        if (d == 1 && k >= 1) printf("YES\n2 1");
        else puts("NO");
        return 0;
    }
    if (k < 2) {puts("NO");return 0;}
    for (int i=1; i<=d; ++i) g[i+1] = i;
    tn = d + 1;
    if (tn == n) { // 没在这判断。。卡到比赛结束。。。也没A
        puts("YES");
        for (int i=2; i<=n; ++i) 
            printf("%d %d\n",i,g[i]);
        return 0; 
    }
    if (d & 1) {
        int t = (d + 1) / 2;
        for (int i=2; i<=t; ++i) dfs(i,1,i,k-2);
        for (int i=t+1; i<=d; ++i) dfs(i,1,(d+1-i+1),k-2);
    }
    else {
        int t = d / 2 + 1;
        for (int i=2; i<=t; ++i) dfs(i,1,i,k-2);
        for (int i=t+1; i<=d; ++i) dfs(i,1,(d+1-i+1),k-2);
    }
    if (tn == n) {
        puts("YES");
        for (int i=2; i<=n; ++i) 
            printf("%d %d\n",i,g[i]);
    }
    else if (tn < n) puts("NO");
    return 0;
}
/*
17 5 4
*/

总结：

敲代码经常出错。。。
集中注意力敲代码，养足精力打比赛！