题解 CF1227G 【Not Same】
Owen_codeisking
2020-11-23 21:30:55
给出一个我自己都不会证的构造方法。
可以直观的想到：若我们每次取的集合都包含最小值且不相同，当最小值被删去后，再进入子问题，这样所有集合都不相同。
至多 $n+1$ 次操作，我们可以维护集合 $A$ 使得 $\max_A\le |A|+1$ 且取到上界最多一次。
这样可以分类讨论。
- 若 $\min A=\max A=|A|$，可以简单构造。
- 若 $\min A>1$，取当前没取过最小值的下标 $k$ （不包括最小值） 不选，其他值均选。
- 若 $\min A=1$，取当前没取过最小值的下标 $k$（不包括最小值） 不选，将一个 $1$ 和其他不为 $1$ 的数（除下标 $k$） $-1$。
可以看出，除了只有一种或两种本质不同的数的情况，最大值一定 $-1$。那么我们多选一次集合简单构造，使得 $\max A\le |A|$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,a[maxn],tot;
vector<int> id;
char s[maxn][maxn];
inline int check()
{
bool fl=0;
vector<int> res; res.clear();
for(auto x:id)
if(a[x]>0) res.push_back(x);
else fl=1;
id=res;
return fl;
}
inline bool cmp(const int &x,const int &y) { return a[x]<a[y]; }
inline void solve()
{
if(check()) return;
sort(id.begin(),id.end(),cmp);
bool fl=0;
if(a[id[0]]>1 || a[id.back()]==1)
{
tot++;
for(int i=1;i<=n;i++) s[tot][i]='0';
for(auto x:id) a[x]--,s[tot][x]='1';
fl=1;
if(check()) return;
}
if(a[id[0]]==a[id.back()] && a[id[0]]==(int)id.size()-1)
{
for(auto x:id)
{
tot++;
for(int i=1;i<=n;i++) s[tot][i]='0';
for(auto y:id)
if(y!=x) a[y]--,s[tot][y]='1';
}
check(); return;
}
int k;
for(k=1;k<(int)id.size();k++)
{
if(a[id[0]]==1) break;
tot++;
for(int i=1;i<=n;i++) s[tot][i]='0';
for(auto y:id)
if(y!=id[k]) a[y]--,s[tot][y]='1';
if(check()) return;
}
tot++;
for(int i=1;i<=n;i++) s[tot][i]='0';
int y=(fl && a[id[k]]>1)?id[k]:0;
for(auto x:id)
if((x==id[0] || a[x]>1) && x!=y) a[x]--,s[tot][x]='1';
check();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),id.push_back(i);
while(!id.empty()) solve();
printf("%d\n",tot);
for(int i=1;i<=tot;i++) printf("%s\n",s[i]+1);
return 0;
}
```