P9048题解

amaimaic · 2023-02-10 23:12:11 · 题解

一道方程数学题。

题目传送门

注意：

1. 由于 t' 为乱序，所以我们不需要管输入的顺序，只需要关注 0 与 1 的数量。
2. 即 $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)。

列方程得：

解得 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; 
}