2020“图灵杯”趣味网络邀请赛 B. 回文串（构造+二分）

2020“图灵杯”趣味网络邀请赛 B. 回文串

题解

• 第一档部分分存在 k k k使得 m = k ( k + 1 ) / 2 m=k(k+1)/2 m=k(k+1)/2起到了很大提示作用（其实没有的话也十分容易想到），
• 回文串最多必然是所有字符相同，此时需满足 m = k ( k + 1 ) / 2 ( k ∈ Z ) m=k(k+1)/2(k\in Z) m=k(k+1)/2(k∈Z)，则答案为 k k k个 a a a；不满足时，可以尽可能增大 k k k的值，使总长度接近 m m m，中间再用两个字符 b c bc bc隔开，然后剩下的部分再找到最大的 k k k，继续做下去直到 m m m剩余 0 0 0。其中 k k k的取值可以解方程或二分。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define ld long double
ll read() {
	ll s = 0;
	char x = getchar();
	while(x < '0' || x > '9') x = getchar();
	while(x >= '0' && x <= '9') s = s * 10 + x - 48, x = getchar();
	return s;
}
int main() {
	int tn = read();
	while(tn--) {
		int n = read();
		while(n) {
			int l = 1, r = n, t;
			while(l <= r) {
				int mid = (l + r) / 2;
				if(mid * (mid + 1) / 2 <= n) t = mid, l = mid + 1; else r = mid - 1;
			}
			for(int i = 1; i <= t; i++) printf("a");
			n -= t * (t + 1) / 2;
			if(n == 1) printf("b"), n--;
			else if(n >= 2) printf("bc"), n -= 2;
		}
		printf("\n");
	}
	return 0;
}