CF549B Looksery Party

发布时间 2023-10-16 18:20:46作者: 空気力学の詩

这些题都是上周五写的了,周末两天因为比赛都没来得及写博客,只能到周一来补一补

这题做法很简单,考虑如果当前状态中\(\{a_i\}\)不含有\(0\)的话就已经得到一组合法解了

否则我们找到某个\(a_i=0\)的点,钦定让\(i\)这个人去派对即可,这样一定可以满足\(i\)这个人的条件,同时更新带来的影响即可

考虑这样做的正确性,因为每次会找出至少一个人使得其满足要求,而所有\(a_i\)的取值一共有\(n+1\)种,因此一定可以找出一组解

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int n,a[N]; char s[N][N]; vector <int> ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%s",s[i]+1);
	for (i=1;i<=n;++i) scanf("%d",&a[i]);
	auto find_zero=[&](void)
	{
		for (i=1;i<=n;++i) if (a[i]==0) return i; return 0;
	};
	int pos; while (pos=find_zero())
	for (ans.push_back(pos),i=1;i<=n;++i) if (s[pos][i]=='1') --a[i];
	printf("%d\n",ans.size()); for (auto x:ans) printf("%d ",x);
	return 0;
}