首页 > 代码库 > Codeforces Round #289 (Div. 2, ACM ICPC Rules) (A, B, C, E)

Codeforces Round #289 (Div. 2, ACM ICPC Rules) (A, B, C, E)

A:水题,根据题目预处理一下输出即可

B:先把最大和最小找出来,可以让最小全是1,然后最大比最小多出的部分就放1,2,3,4,5...所以如果MAX - MIN > k就是NO,不然就根据这个构造出答案

C:贪心的策略,每次要让数字尽量小,那么就和上一个数字比较,如果需要的和比上一个小,就先找到一个新数字,使得和小于所需数字,并且该数字是大于上一个数字的最小值,找的方法就是从末尾不断放0进位。那么现在情况就只剩下需要的和比上一个大的了,这个就贪心,从末尾尽量变成9即可

E:一个计数问题,其实只要考虑每个字母所加成的值即可,每个字母而言,长度满足能到最左和最右的就是+1,而中间到不了最大的则为,1/ i + 1 / (i +1) + 1 / ( i +2)....,i在该数字到两边的距离之间的值,比如总长度为7当前位置为2,那么i就是从长度为3到长度6,而这样并没有计算完,因为还有后面超过6的情况,只要在加上从后面往前算的 1 / (n - i + 1) * i 之和即可,所以要预处理两个数组进行计数,具体看代码:

A:

#include <cstdio>
#include <cstring>
using namespace std;

int n, a[15][15];

int main() {
    for (int i = 1; i <= 10; i++) a[1][i] = a[i][1] = 1;
    for (int i = 2; i <= 10; i++)
        for (int j = 2; j <= 10; j++)
            a[i][j] = a[i - 1][j] + a[i][j - 1];
    while (~scanf("%d", &n)){
        printf("%d\n", a[n][n]);
    }
    return 0;
}

B:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, k, a[105];

int main() {
    while (~scanf("%d%d", &n, &k)) {
        int Min = 105, Max = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            Min = min(Min, a[i]);
            Max = max(Max, a[i]);
        }
        int use = min(k, Min);
        int one = Min / use;
        int yu = Min % use;
        if (Max - Min > k) printf("NO\n");
        else {
            printf("YES\n");
            for (int i = 0; i < n; i++) {
                printf("1");
                for (int j = 2; j <= Min; j++)
                    printf(" 1");
                for (int j = Min + 1; j <= a[i]; j++)
                    printf(" %d", j - Min);
                printf("\n");
            }
        }
    }
    return 0;
}

C:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 305;

int n, b[N];
int num[10005], nn;

void find(int cha) {
    for (int i = 0; i < nn; i++) {
        if (cha > 0) {
            num[i] += 1;
            for (int j = i; j < nn; j++) {
                num[j + 1] += num[j] / 10;
                num[j] %= 10;
            }
            if (num[nn]) nn++;
            return;
        }
        cha += num[i];
        num[i] = 0;
    }
    num[nn++] = 1;
}

int main() {
    while (~scanf("%d", &n)) {
        nn = 1;
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++)
            scanf("%d", &b[i]);
        for (int i = 0; i < n; i++) {
            int tmp = 0;
            for (int i = 0; i < nn; i++)
                tmp += num[i];
            int cha = b[i] - tmp;

            if (cha <= 0) find(cha);

            tmp = 0;
            for (int i = 0; i < nn; i++)
                tmp += num[i];
            cha = b[i] - tmp;
            for (int i = 0; i < nn; i++) {
                if (num[i] + cha <= 9) {
                    num[i] += cha;
                    cha = 0;
                    break;
                } else {
                    cha = max(cha - 9 + num[i], 0);
                    num[i] = 9;
                }
            }
            if (cha) {
                while (cha) {
                    num[nn++] = min(cha, 9);
                    cha = max(cha - 9, 0);
                }
            }
            for (int i = nn - 1; i >= 0; i--)
                printf("%d", num[i]);
            printf("\n");
        }
    }
    return 0;
}

E:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 500005;

char str[N];

double cal1[N], cal2[N];
int vis[1005];
double ans;

int main() {
    gets(str + 1);
    int n = strlen(str + 1);
    for (int i = 1; i <= n; i++) {
        cal1[i] = cal1[i - 1] + 1.0 / i;
        cal2[i] = cal2[i - 1] + 1.0 / (n - i + 1) * i;
    }
    ans = 0;
    memset(vis, 0, sizeof(vis));
    vis['I'] = vis['E'] = vis['A'] = vis['O'] = vis['U'] = vis['Y'] = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[str[i]]) {
            int c = min(i,  n - i + 1);
            ans += c * (cal1[n - c + 1] - cal1[c]) + c + cal2[c - 1];
        }
    }
    printf("%.10lf\n", ans);
    return 0;
}


Codeforces Round #289 (Div. 2, ACM ICPC Rules) (A, B, C, E)