题意:
现在举行聚会,有n个人,如果某个人去了聚会,他会给自己和某几个其他人发短信(没有去就不发),现在有个人预测了这n个人收到短信的数量,需要你构造一个邀请方案,使得预测全错
思路:
首先,当某个人收到的短信数量已经超过预期的时候,我们就不用考虑他了,因为其他人的变化,对他来说只能是增加短信数量,这样的话怎么都不会达到预测的数量
而注意到题目说某个人去了的话,必定给自己发一个短信,那么如果此刻某个人收到短信恰好为预测数量,那么我们就可以选择他,这样就能保证两件事,第一,这个人收到短信的数量一定是不等于预测数量了,第二,根据之前的分析,之后我们绝对不会再次选择他了,这样就能保证每个人最多选择一次了
最后我们还需要考虑一个问题,就是什么时候我们无法找到一个合适的答案,我们发现,对于一个人来说,如果他选择过了,那么他一定不等于预测数了,而我们新选中一个人,也只会让那些没有被选中过的人的数量等于预测值,这样,我们就必定能找到一个解了
错误及反思:
因为没看到必定给自己发短信,想了好久。读题要仔细啊
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
int arr[maxn][maxn];
int guess[maxn];
int n;
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%1d",&arr[i][j]);for(int i=0;i<n;i++)scanf("%d",&guess[i]);vector<int> ans;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(guess[j]==0){for(int k=0;k<n;k++)guess[k]-=arr[j][k];ans.push_back(j+1);}}}printf("%d\n",ans.size());for(int i=0;i<ans.size();i++){if(i) printf(" %d",ans[i]);else printf("%d",ans[i]);}puts("");}