首页 > > 程序设计 > C/C++ >

CodeChef March Lunchtime 2018 div2

2018-06-17 20:27:22来源：未知阅读 ()

地址https://www.codechef.com/LTIME58B?order=desc&sortBy=successful_submissions

简单做了一下，前三题比较水，第四题应该算是经典题

AChef and Friends

直接暴力枚举即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1001, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, ans = 0;
char s[MAXN];
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read();
    for(int i = 1; i <= N; i++) {
        scanf("%s", s + 1);
        int L = strlen(s + 1);
        for(int j = 1; j <= L - 1; j++) {
            if((s[j] == 'c' && s[j + 1] == 'h')||
               (s[j] == 'h' && s[j + 1] == 'e')||
               (s[j] == 'e' && s[j + 1] == 'f'))
               {ans++; break;}
        }
    }
    printf("%d", ans);
}

BMagic Elements

维护一个所有元素的和，直接模拟即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K, ans = 0;
int a[MAXN];
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    int T = read();
    while(T--) {
        N = read(); K = read();
        int sum = 0, ans = 0;
        for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];
        for(int i = 1; i <= N; i++) 
            if(a[i] + K > sum - a[i])
                ans++;
        printf("%d\n", ans);
    }
}

CThree Integers

把式子化成$2B = A +C$的形式，不难看出改B一定是最优的。

特判一下奇偶性即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    int N = read();
    while(N--) {
        int A = read(), B = read(), C = read();
        int ans = abs(2 * B - A - C);
        if(ans & 1) printf("%lld\n", ans / 2 + 1);
        else printf("%lld\n", ans / 2);
    }
}

DPartitions

个人感觉是一道比较好的题

设所有元素的和为$sum$

不难发现，不论如何分，分成的段数一定是$sum$的因子

而且不论如何分，第一段一定是$1-x$（以$1$为起点）

这样我们遇到一个因子就枚举一边序列暴力分割就可以

这题TM居然卡常

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int a[MAXN];
char ans[MAXN];
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    int T = read();
    while(T--) {
        int N = read(), sum = 0;
        for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];
        for(int i = 1; i <= N; i++) {
            if(sum % i != 0) {ans[i] = '0'; continue;}
            int cur = 0, num = 0;
            for(int j = 1; j <= N; j++) {
                cur += a[j];
                if(cur == sum / i) cur = 0;
                else if(cur > sum / i) {ans[i] = '0'; break;}
            }
            ans[i] = (cur == 0 ? '1' : '0');
        }
        for(int i = 1; i <= N; i++) 
            putchar(ans[i]);
        puts("");
    }
}