当前位置: 代码迷 >> 综合 >> Codeforces Looksery Cup 2015 B - Looksery Party (构造)
  详细解决方案

Codeforces Looksery Cup 2015 B - Looksery Party (构造)

热度:24   发布时间:2023-12-17 03:37:04.0

题意:

现在举行聚会,有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("");}
  相关解决方案