Codeforces Round #235 (Div. 2)

Problems

 

 

#	Name
A	Vanya and Cards standard input/output 1 s, 256 MB		x2537
B	Sereja and Contests standard input/output 1 s, 256 MB		x1911
C	Team standard input/output 1 s, 256 MB		x1573
D	Roman and Numbers standard input/output 4 s, 512 MB		x464
E	Olympic Games standard input/output 2 s, 256 MB		x63

A题：水题，先计算总和，尽量往大了取，所以答案就是sum / x + (sum % x != 0)。

B题：最多的情况是全是DIV2，最少的情况是尽量有DIV1和DIV2和开，用一个vis数组记录已经开过的场，for循环找过去即可。

C题：n个0，m个1，1只能有1个或2个组成一起，然后有n个0，最少就要n - 1个1，最多可以有(n + 1) * 2 （1可以多放两边）所以先判断n - 1 <= m <= (n + 1) * 2，然后在去模拟放就可以了。

D题：记忆化搜索，dp[s][m]代表集合为s，取模为mo的状态，然后去一个新的数字放在后面，m变成(mo * 10 + num) % m,进行记忆化搜索即可。

代码：

A题：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n, x, sum;

int main() {
	int num;
	scanf("%d%d", &n, &x);
	while (n--) {
		scanf("%d", &num);
		sum += num;
	}
	printf("%d\n", abs(sum) / x + (abs(sum) % x != 0));
	return 0;
}

#include <stdio.h>
#include <string.h>

int x, n, vis[4005];

int main() {
    scanf("%d%d", &x, &n);
    int v, d1, d2;
    while (n--) {
        scanf("%d", &v);
        if (v == 1) {
            scanf("%d%d", &d1, &d2);
            vis[d1] = 1; vis[d2] = 1;
        }
        else {
            scanf("%d", &d2);
            vis[d2] = 1;
        }
    }
    vis[0] = 1;
    int ans1 = 0, ans2 = 0, i;
    for (i = 1; i < x; i++)
        if (!vis[i]) ans1++;
    for (i = 1; i < x; i++)
        if (!vis[i] && !vis[i - 1]) {
            ans2++;
            vis[i] = vis[i - 1] = 1;
        }
    for (i = 1; i < x; i++)
        if (!vis[i]) ans2++;
    printf("%d %d\n", ans2, ans1);
    return 0;
}

#include <stdio.h>
#include <string.h>

int n, m;

int main() {
    scanf("%d%d", &n, &m);
    if (m < n - 1 || m > (n + 1) * 2) {
        printf("-1\n");
        return 0;
    }
    if (m - (n - 1) * 2 == 1)
        printf("1");
    if (m - (n - 1) * 2 >= 2)
        printf("11");
    int mm;
    if (m > (n - 1) * 2) mm = (n - 1) * 2;
    else mm = m;
    int m2 = mm - (n - 1);
    int m1 = (n - 1) - m2;
    int nn = n;
    while (m2--) {
        if (nn--) printf("0");
        printf("11");
    }
    while (m1--) {
        if (nn--) printf("0");
        printf("1");
    }
    if (nn--)printf("0");
    if (m - (n - 1) * 2 == 3)
        printf("1");
    if (m - (n - 1) * 2 == 4)
        printf("11");
    printf("\n");
    return 0;
}

#include <stdio.h>
#include <string.h>

char str[20];
int num[20], m, n, vis[(1<<18)][105];
__int64 dp[(1<<18)][105];

__int64 dfs(int s, int mo) {
	__int64 &ans = dp[s][mo];
	if (vis[s][mo]) return ans;
	vis[s][mo] = 1;
	int v[10];
	memset(v, 0, sizeof(v));
	if (s == (1<<n) - 1 && mo == 0)
		return ans = 1;
	for (int i = 0; i < n; i++) {
		if (s == 0 && num[i] == 0) continue;
		if (s&(1<<i)) continue;
		if (v[num[i]]) continue;
		v[num[i]] = 1;
		ans += dfs(s^(1<<i), (mo * 10 + num[i]) % m);
	}
	return ans;
}

int main() {
	scanf("%s%d", str, &m);
	n = strlen(str);
	for (int i = 0; str[i]; i++)
		num[i] = str[i] - ‘0‘;
	printf("%I64d\n", dfs(0, 0));
	return 0;
}

Codeforces Round #235 (Div. 2),布布扣,bubuko.com

Codeforces Round #235 (Div. 2)

原文：http://blog.csdn.net/accelerator_/article/details/21113957