首页 > 代码库 > CodeForces 398A Cards 贪心 暴力 瞎搞

CodeForces 398A Cards 贪心 暴力 瞎搞

搞了一晚上了快,各种YY乱搞啊,终于过了,一开始YY的都是错的,觉得 这道题目a,b的范围都是10^5,那就暴力枚举b被分成了几份,然后再继续YY,只用一个o去分隔x,这样最后剩下的o再集中在一起,也就是x的份数总是比o的份数多一份,也就是尽可能把x分开,尽可能把o集中在一块,前面都把x分开了,一个o分开两份x,后面还能有一大堆的o在一起,这样就满足了,然后又出错了,因为分成几份,有余数的,比如b = 6,你要分成4份,我以开始是分成 1  1  1  3这样子,这样不行,应该分成 1 1 2 2把余数平均冯前面1个,直到分光了位置,主要就是 减少b的存在,其实a的部分很好控制,a的部分 减去前面要去分隔x的,每个分隔只需消耗一个o,剩下的乘一下 加上前面多少个,b就要分两部分计算,一部分是 得到了余数分配的,还有一部分就是 整除所得的值

ll aa,bb;

ll ans ;

string ret;

void init() {

}

bool input() {
	while(cin>>aa>>bb) {
		return false;
	}
	return true;
}

void cal() {
	ll mark;
	ans = 0ll;
	ret = "";
	if(aa == 0) {
		ans = -bb * bb;
		ll q = bb;
		while(q--)ret += "x";
		return ;
	}
	if(bb == 0) {
		ans = aa * aa;
		ll q = aa;
		while(q--)ret += "o";
		return ;
	}
	ans = -INF;
	for(ll i=2;i<=aa + 1;i++) {
		ll now = (aa - i + 2) * (aa - i + 2) + i - 2;
		ll tmp = bb/i;
		ll tt = bb - tmp * i;
		now -= tt * (tmp + 1ll) * (tmp + 1ll) + (i - tt) * tmp * tmp;
		if(now > ans) {
			ans = now;
			mark = i;
		}
	}
	ll tmp = bb/mark;
	ll tt = bb - tmp * mark;
	bool flag = false;
	ll cnt = 0;
	for(ll i=1;i<mark;i++) {
		if(flag)ret += "o";
		if(cnt < tt) {ret += "x";cnt++;}
		for(ll j=0;j<tmp;j++)ret += "x";
		flag = true;
	}
	for(ll i=0;i<(aa - mark + 2);i++)ret += "o";
	for(ll i=0;i<tmp;i++)ret += "x";
}

void output() {
	cout<<ans<<endl;
	cout<<ret<<endl;
}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}





CodeForces 398A Cards 贪心 暴力 瞎搞