学步园

Problem A: New Year Candles (379A)

题目大意：给出a和b，表示有现在有a根蜡烛，烧完b根蜡烛后可以换取新的一根蜡烛，问最多可以点多少根蜡烛。

解题思路：水题。

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

int main() {
	int ans = 0, a, b;
	scanf("%d%d", &a, &b);
	while (a >= b) {
		ans += (a / b) * b;
		a = a / b + a % b;
	}
	printf("%d\n", ans + a);
	return 0;
}

Problem B: New Year Present (379B)

题目大意：机器人为桌子上的钱包塞硬币，给出每个钱包需要放多少个硬币，然后机器人从最左边开始放硬币，不能连续放两次硬币，输出机器人的操纵。

解题思路：因为不需要说最少步数，所以每个位置放一次礼物后就移动到旁边再移动回来就可以了，注意最左边的只能往右移动。

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

const int N = 305;

int n, c[N];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &c[i]);
	for (int i = 0; i < c[0]; i++) printf("PRL");

	for (int i = 1; i < n; i++) {
		printf("R");
		for (int j = 0; j < c[i]; j++) printf("PLR");
	}
	printf("\n");
	return 0;
}

Problem C:New Year Ratings Change(379C)

题目大意：有n个人，每个人在新年有想要礼物的个数，你需要满足所有人的需求，即礼物个数大于等于他想要的个数，并且送给每个人的礼物数不能相同。

解题思路：将需求从小到大排序，然后维持一个最小礼物数即可。

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

using namespace std;

const int N = 300005;

struct state {
	int x, id;
}s[N];
int n, c[N];

bool cmp(const state& a, const state& b) {
	return a.x < b.x;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &s[i].x);
		s[i].id = i;
	}
	sort(s, s + n, cmp);
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		c[s[i].id] = max(s[i].x, tmp);
		tmp = c[s[i].id] + 1;
	}
	printf("%d", c[0]);
	for (int i = 1; i < n; i++) printf(" %d", c[i]);
	printf("\n");
	return 0;
}

Problem D:New Year Letter(379D)

题目大意：给出k，x，n，m。现在有字符串s1，s2长度分别为n和m。si = si-2 + si-1。问说能否找出sk中正好含有x个"AC"。

解题思路：要注意s1=A，s2=C，那么s3=AC这样一类情况。原先是ci=ci-2+ci-1，但是出现刚才的情况就会变成ci=ci-2+ci-1 + 1。所以要枚举s1和s2的头尾，以及AC个数。

#include <stdio.h>
#include <iostream>

using namespace std;
typedef long long ll;
const char sign[3] = {'A', 'B', 'C' };

int k, n, m;
ll x;

int count(int c, int pre, int end) {
	if (pre != 0) c--;
	if (end != 2) c--;
	return c / 2;
}

bool judge(ll p, ll q, char fpre, char fend, char spre, char send) {
	for (int i = 3; i <= k; i++) {
		ll t = p + q;
		char ch = fpre;
		if (fend == 'A' && spre == 'C') t++;

		p = q; fpre = spre; fend = send;
		q = t; spre = ch;
	}
	return q == x;
}

void put(int c, int s, int pre, int end) {
	printf("%c", sign[pre]);
	if (s == 1) return;
	s--;

	if (c && pre == 0) {
		printf("C"); c--; s--;
	}

	for (int i = 0; i < c; i++) printf("AC");
	s -= 2 * c;
	for (int i = 1; i < s; i++) printf("B");
	if (s) printf("%c", sign[end]);
}

bool solve() {

	for (int fpre = 0; fpre < 3; fpre++) {
		for (int fend = 0; fend < 3; fend++) {
			if (n == 1 && fpre != fend) continue;
			for (int spre = 0; spre < 3; spre++) {
				for (int send = 0; send < 3; send++) {
					if (m == 1 && spre != send) continue;

					int p = count(n, fpre, fend), q = count(m, spre, send);
					for (int i = 0; i <= p; i++) {
						for (int j = 0; j <= q; j++) {
							if (judge(i, j, sign[fpre], sign[fend], sign[spre], sign[send])) {
								put(i, n, fpre, fend); printf("\n");
								put(j, m, spre, send); printf("\n");
								return true;
							}
						}
					}
				}
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &k);
	cin >> x;
	scanf("%d%d", &n, &m);
	if (!solve()) printf("Happy new year!\n");
	return 0;
}