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

Codeforces Round #265 (Div. 2)

Codeforces Round #265 (Div. 2)

题目链接

A:把数字变换后比较一下几个不一样即可

B:连续2个以上0当作一次操作,开头的0和结尾的0可以忽略

C:贪心从末尾去构造,由于保证一开始是回文,所以保证修改后出现回文只可能为长度2或3的,这样的话判断复杂度就很小了

D:暴力枚举情况,然后判断

E:把操作逆过来处理出每个数字对应的位数和相应数字,然后在for一遍计算答案即可

代码:

A:

#include <cstdio>
#include <cstring>

int n, num[105], sb[105];
char s[105];

int main() {
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 0; i < n; i++) {
        num[i] = s[i] - '0';
        sb[i] = num[i];
    }
    num[0]++;
    for (int i = 0; i < n; i++) {
        if (num[i] == 2) {
            num[i] = 0;
            num[i + 1]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (sb[i] != num[i])
            ans++;
    printf("%d\n", ans);
    return 0;
}

B:

#include <cstdio>
#include <cstring>

const int N = 1005;

int n, num[N];

int solve() {
	int ans = 0;
	int s = 0, e = n - 1;
	while (num[s] == 0 && s < n) s++;
	while (num[e] == 0 && e >= 0) e--;
	for (int i = s ; i <= e; i++) {
		if (num[i] == num[i - 1] && num[i] == 0)
			continue;
		ans++;
	}
	return ans;
}

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

C:

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

const int N = 1005;

int n, p;
char str[N];

bool solve(int u) {
	if (u < 0) return false;
	str[u]++;
	if (str[u] - 'a' == p) {
		if (solve(u - 1)) {
			str[u] = 'a' - 1;
			return solve(u);
		}
	} else {
		if (u - 1 >= 0 && str[u] == str[u - 1]) return solve(u);
		if (u - 2 >= 0 && str[u] == str[u - 2]) return solve(u);
		return true;
	}
}

int main() {
	scanf("%d%d", &n, &p);
	scanf("%s", str);
	if (solve(n - 1)) printf("%s\n", str);
	else printf("NO\n");
	return 0;
}

D:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

struct Point {
	int v[3];
	void read() {
		for (int i = 0; i < 3; i++)
			scanf("%d", &v[i]);
	}
	bool operator == (const Point& c) const {
		return (v[0] == c.v[0] && v[1] == c.v[1] && v[2] == c.v[2]);
	}
} p[10];

typedef long long ll;

ll dis(Point a, Point b) {
	ll dx = a.v[0] - b.v[0];
	ll dy = a.v[1] - b.v[1];
	ll dz = a.v[2] - b.v[2];
	return dx * dx + dy * dy + dz * dz;
}

ll d[10];

bool judge() {
	for (int i = 1; i < 8; i++)
		for (int j = 0; j < i; j++) {
			if (p[i] == p[j]) return false;
		}
	d[0] = 0;
	for (int i = 1; i < 8; i++)
		d[i] = dis(p[0], p[i]);
	sort(d, d + 8);
	ll a = d[1], b = d[4], c = d[7];
	if (a != d[2] || a != d[3] || d[2] != d[3]) return false;
	if (b != d[5] || b != d[6] || d[5] != d[6]) return false;
	if (2 * a != b) return false;
	if (a + b != c) return false;
	return true;
}

bool dfs(int u) {
	if (u == 8) {
		if (judge())
			return true;
		return false;
	}
	sort(p[u].v, p[u].v + 3);
	do {
		if (dfs(u + 1)) return true;
	} while (next_permutation(p[u].v, p[u].v + 3));
	return false;
}
int main() {
	for (int i = 0; i < 8; i++)
		p[i].read();
	if (!dfs(0)) printf("NO\n");
	else {
		printf("YES\n");
		for (int i = 0; i < 8; i++)
			printf("%d %d %d\n", p[i].v[0], p[i].v[1], p[i].v[2]);
	}
	return 0;
}

E:

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

typedef long long ll;
const ll MOD = 1000000007;
const int N = 100005;

char str[N], sss[N];
int n;

ll pow_mod(ll x, ll k) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = (ans * x) % MOD;
        x = x * x % MOD;
        k >>= 1;
    }
    return ans;
}

ll v[15], l[15];

ll idx(char c) {
    return c - '0';
}

struct State {
    ll u;
    vector<ll> v;
    void init(char *str) {
        int len = strlen(str);
        u = idx(str[0]);
        v.clear();
        for (int i = 3; i < len; i++)
            v.push_back(idx(str[i]));
    }
} s[N];

int main() {
    scanf("%s", str);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", sss);
        s[i].init(sss);
    }
    for (int i = 0; i < 10; i++) {
        v[i] = i;
        l[i] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        ll lt = 0, vt = 0;
        for (int j = 0; j < s[i].v.size(); j++) {
            ll nu = s[i].v[j];
            vt = (vt * pow_mod(10, l[nu]) % MOD + v[nu]) % MOD;
            lt = (lt + l[nu]) % (MOD - 1);
        }
        v[s[i].u] = vt;
        l[s[i].u] = lt;
    }
    ll ans = 0;
    for (int i = 0; i < strlen(str); i++) {
        ll nu = idx(str[i]);
        ans = (ans * pow_mod(10, l[nu]) % MOD + v[nu]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}


Codeforces Round #265 (Div. 2)