当前位置：首页 > news >正文

算法题解：找不到百草枯

news 2025/1/15 22:55:51

问题描述：有瓶有毒药水不知道是那个。经过m次混和，求哪一次可以得到药水和药水的编号；否则，输出可能的药水编号。

思路：用dy表示当前可能为毒药的个数，notdy表示一定不是毒药的个数。同时开个vis数组，vis中0表示未知，1表示可能有毒，2表示一定没有毒。

每次读入记录有毒次数。对有毒和无毒进行操作，得到dy和notdy的个数。当且仅当dy == 1 || notdy == n - 1时可以得到答案，记录当前询问次数，之后在进行处理。

不能准确判断是否有毒，按顺序进行遍历即可。

时间线性。

代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pair<int,int> PII;const int INF = 0x3f3f3f3f;
const int N = 5e5 + 21;
int vis[N]; // 0 未知 1 可能有毒 2 一定没毒
int cnt[N];
int a[N];
inline int fread() // 快读
{int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * f;
}void inpfile();
void solve() {int n,m; n = fread(), m = fread();// dy -- 是毒药的个数// notdy -- 不是毒药的个数// sum -- 查询中混有毒药的个数int sum = 0, dy = 0, notdy = 0;int tim = 0;for(int i = 0; i < m; ++i) {int k; k = fread();for(int j = 0; j < k; ++j) a[j] = fread();int isdu; isdu = fread();if(isdu) { // 如果是有毒药的话sum++; // 查询有毒药的次数 + 1int now = 0; // 判断可能是毒药的个数// 当sum更新，上一次可能是毒药的，这一次就可能不是了，因此需要一个now进行记录for(int j = 0; j < k; ++j) {cnt[a[j]]++; // 先将这个可能是毒药的次数+1if(vis[a[j]] == 2) continue; // 如果一定不是毒药if(cnt[a[j]] == sum) { // 是毒药的判断是：该药编号 在查询有毒药的询问中都出现，即等于sumnow++; // 如果满足，now 新的dy加1vis[a[j]] = 1; // 将这个设置为可能是毒药} else { // 否则就一定不是毒药vis[a[j]] = 2;notdy++;}}// 将新的查询回合中可能是毒药的次数进行更新dy = now;} else { // 如果这里没有毒药，就简单了for(int j = 0; j < k; ++j) {if(vis[a[j]] != 2) notdy++; // 如果不是 2， notdy++if(vis[a[j]] == 1 && cnt[a[j]] == sum) dy--; // 如果是1，需要将毒药个数-1vis[a[j]] = 2; // 设置为 一定没有毒药}}if(dy == 1 || notdy == n - 1) { // 如果dy个数为1，或者 一定不是毒药的个数为 n - 1tim = i + 1; // 一定可能判断出毒药break;}}if(tim) { // 如果找到了毒药puts("Yes");printf("%d ",tim);for(int i = 1; i <= n; ++i) {// 找到每次查询是毒药时都出现的那个药，并且这个编号一定是毒药（多余了感觉if(cnt[i] == sum && vis[i] != 2) { cout<<i;return ;}}} else {puts("No");for(int i = 1; i <= n; ++i) {// 否则，将可能是毒药的进行输出if(vis[i] != 2 && cnt[i] == sum) {printf("%d ", i);}}}
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}/*** 3 2
2 1 2 1
2 2 3 1Yes
2 2
*/