首页 > 代码库 > Codeforces Round #256 (Div. 2)

Codeforces Round #256 (Div. 2)

Codeforces Round #256 (Div. 2)

题目链接

A题:没什么好说的水题,判断一下两种各需要多少个,加起来看会不会超过即可
B题:首先计数字母,看b串有没有多余字符,判断掉need tree的情况,然后判断b是否能和a匹配,如果可以且长度不同,就是auto,如果不行且长度相同,就是array,否则就是both
C题:贪心,每次选择最低的去横向刷,刷完会多出几个子状态出来,利用递推去求解即可
D题:二分推理,二分答案,那么对于这个答案,后面n行中,对应第2行有m/2个,第3行有m/3...依次类推,就能求出该答案符不符合第k个,利用二分不断趋近答案求解
E题:暴力简直不敢信,把x因子处理出来dfs暴力递归输出答案,大力出奇迹啊

代码:

A:

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

int a[3], b[3], n;

int main() {
	int i;
	for (i = 0; i < 3; i++)
		scanf("%d", &a[i]);
	for (i = 0; i < 3; i++)
		scanf("%d", &b[i]);
	scanf("%d", &n);
	int aa = a[0] + a[1] + a[2];
	int bb = b[0] + b[1] + b[2];
	if (n >= (aa / 5 + (aa % 5 != 0) + bb / 10 + (bb % 10 != 0)))
		printf("YES\n");
	else printf("NO\n");
	return 0;
}

B:

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

char a[105], b[105];
int vis[30];

void solve(char *str, int val) {
	for (int i = 0; i < strlen(str); i++)
		vis[str[i] - 'a'] += val;
}

bool jud(char *a, char *b) {
	int i = 0, j = 0;
	while (i < strlen(a) && j < strlen(b)) {
		if (b[j] == a[i]) {
			i++; j++;
		}
		else i++;
	}
	if (j == strlen(b)) return true;
	return false;
}

void gao() {
	int i;
	for (i = 0; i < 26; i++) {
		if (vis[i] > 0) {
			printf("need tree\n");
			return;
		}
	}
	if (jud(a, b)) {
		printf("automaton\n");
	}
	else {
		if (strlen(a) == strlen(b)) printf("array\n");
		else printf("both\n");
	}
}

int main() {
	scanf("%s%s", a, b);
	solve(b, 1);
	solve(a, -1);
	gao();
	return 0;
}

C:

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

#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
int n, a[5005];

int dfs(int l, int r, int now) {
    if (l == r) return 0;
    int i, Min = INF;
    for (i = l; i < r; i++)
        Min = min(Min, a[i]);
    int ans = Min - now, L = l;
    for (i = l; i < r; i++) {
        if (a[i] == Min) {
            ans += dfs(L, i, Min);
            L = i + 1;
        }
    }
    ans += dfs(L, r, Min);
    return min(r - l, ans);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("%d\n", dfs(0, n, 0));
    return 0;
}

D:

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
__int64 n, m, k;

bool judge(__int64 mid) {
	__int64 sum = 0;
	for (__int64 i = 1; i <= n; i++) {
		sum += min(m, (mid / i));
	}
	return sum >= k;
}

__int64 solve() {
	__int64 l = 1, r = n * m;
	while (l < r) {
		__int64 mid = (l + r) / 2;
		if (judge(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main() {
	scanf("%I64d%I64d%I64d", &n, &m, &k);
	if (n > m) {
		__int64 t = n;
		n = m;
		m = t;
	}
	printf("%I64d\n", solve());
	return 0;
}

E:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

typedef __int64 ll;
const int N = 100005;
ll x, k, frac[N], fn = 0;

void tra(ll x) {
    ll m = (ll)sqrt(x);
    for (ll i = 1; i <= m; i++) {
        if (x % i) continue;
        frac[fn++] = i;
        if (x / i != i) frac[fn++] = x / i;
    }
    sort(frac, frac + fn);
}

ll s = 0;

void dfs(ll x, ll k) {
    if (s >= 100000) return;
    if (k == 0 || x == 1) {
        printf("%I64d ", x);
        s++;
        return;
    }
    for (ll i = 0; i < fn && frac[i] <= x; i++) {
        if (x % frac[i]) continue;
        dfs(frac[i], k - 1);
        if (s >= 100000) return;
    }
}

int main() {
    scanf("%I64d%I64d", &x, &k);
    tra(x);
    dfs(x, k);
    return 0;
}