自动搬运

查看原文

来自洛谷，原作者为

	Furina_Hate_Comma > 最后在线时间：2025年8月24日0时8分 < 由 exOIso 发送激光

搬运于2025-08-24 22:44:55，当前版本为作者最后更新于2023-02-10 23:12:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道方程数学题。

题目传送门

注意：

1. 由于 $t'$ 为乱序，所以我们不需要管输入的顺序，只需要关注 $0$ 与 $1$ 的数量。
2. $a$ 的 ASCII 码为 $97$，$z$ 的 ASCII 码为 $122$。 即 $01100001$ 到 $01111010$，其中含 $1$ 的数量不同情况分别有：
   $a$ 即 $01100001$，$c$ 即 $01100011$，$g$ 即 $011000111$，$o$ 即 $011001111$。
   他们分别代表了 $3,4,5,6$ 的情况(也可以是其他，但 $a,c,g,o$ 较小)。

至此，问题变成了用 $a,c,g,o$ 构造 $01$ 串。 接下来设 $S$ 表示 $t'$ 中 $1$ 的数量，$x_i$ 表示 ASCII 中含有 $i$ 个 $1$ 的字母在 $s$ 串中的数量 $(3 \le i \le 6)$。

列方程得： $\begin{cases} 3x_3 + 4x_4 + 5x_5 +6x_6= S\\x_3+x_4+x_5+x_6=n\end{cases}$

解得 $x_4+2x_5+3x_6=S-3n$。 所以当且仅当 $3n \le S \le 6n$ 时有解。

最后就是利用贪心构造让 $x_3$ 非负。只需要先让 $x_6$ 尽量大，再具体将剩下的情况分类讨论，即：

• 如果 $S-3n-3x_6=1$ 则 $x_4=1,x_5=1$。
• 如果 $S-3n-3x_6=2$ 则 $x_4=0,x_5=0$。

最后就是大家最期待的放代码环节了！

#include<bits/stdc++.h>
using namespace std;
char s[800010];
int main(){
	int n,S=0;
	cin>>n>>s;
	for(int i=0;i<8*n;i++)S+=s[i]-'0';
	if(S<3*n||S>6*n){
		cout<<"NIE";
		return 0;
	}
	int x[4];
	x[1]=0;
	x[2]=0;
	x[3]=0;
	x[0]=0;
	x[3]=(S-3*n)/3;
	x[S%3]=1;
	x[0]=n-x[3]-x[2]-x[1];
	while(x[0]--)cout<<'a';
	while(x[1]--)cout<<'c';
	while(x[2]--)cout<<'g';
	while(x[3]--)cout<<'o';
	return 0; 
}