• 【NOI模拟赛】毒药(交互,构造(?))


    题面



    题解

    题目只是保证有解,交互库是自适应的,说明我们得找出最优解。

    常用的二进制分组,组合数分组,说白了都是每个结果唯一对应一个答案,并根据对应方式安排询问。

    这道题保证有解,就说明最终死亡数不超过 m − k m-k mk 的所有情况总数至少为 n n n 。我们可以将这些方案与 n n n 瓶药对应起来。假设第 i i i 瓶药对应的情况是 { t 0 , t 1 , . . . , t m } \{t_0,t_1,...,t_m\} {t0,t1,...,tm} t j t_j tj 表示第 j j j 只白鼠最早在第 t j t_j tj 轮实验挂掉(如果最终挂掉的话)),那么我们在第 t j t_j tj 轮实验时给 j j j 喂第 i i i 瓶药(前提是这时候 j j j 没死)。

    可以发现最终结果一定是对应正确的毒药的。

    预处理每一种情况时可以用dfs+哈希。

    时间复杂度 O ( n m t ) O(nmt) O(nmt)

    CODE

    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #pragma GCC optimize(2)
    using namespace std;
    namespace ME{
    #define MAXN 10005
    #define LL long long
    #define ULL unsigned LL
    #define DB double
    #define lowbit(x) (-(x)&(x))
    #define ENDL putchar('\n')
    #define FI first
    #define SE second
    #define PR pair<int,int>
    inline int xchar() {
    	static const int maxn = 1000000;
    	static char b[maxn];
    	static int pos = 0,len = 0;
    	if(pos == len) pos=0,len=fread(b,1,maxn,stdin);
    	if(pos == len) return -1;
    	return b[pos ++];
    }
    // #define getchar() xchar()
    inline LL read() {
    	LL f=1,x=0;int s=getchar();
    	while(s<'0'||s>'9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
    	while(s>='0'&&s<='9') {x = (x<<3)+(x<<1)+(s^48);s=getchar();}
    	return f*x;
    }
    void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
    void putnum(LL x) {
    	if(!x) {putchar('0');return ;}
    	if(x<0) putchar('-'),x=-x;
    	return putpos(x);
    }
    void AIput(LL x,int c) {putnum(x);putchar(c);}
    
    int n,m,k;
    int t;
    int ar[MAXN][16][16],p[16][16],cnt;
    map<ULL,int> mp;
    void dfs(int x,int ct) {
    	if(ct > m-k) return ;
    	if(cnt >= n) return ;
    	if(x == m) {
    		ULL hs = 0;
    		for(int i = 0;i < t;i ++) {
    			for(int j = 0;j < m;j ++) {
    				ar[cnt][i][j] = p[i][j];
    				hs = hs*37 + (p[i][j]+5);
    			}
    		}
    		mp[hs] = cnt; cnt ++;
    		return ;
    	}
    	dfs(x+1,ct);
    	for(int i = 0;i < t && cnt < n;i ++) {
    		p[i][x] = 1;
    		dfs(x+1,ct+1);
    		p[i][x] = 0;
    	}
    	return ;
    }
    }
    #include"poison.h"
    int solve(int N,int M,int K,int T)
    {
    	ME::n=N;ME::m=M;ME::k=K;ME::t=T;
    	ME::dfs(0,0);
    	bool f[20] = {};
    	ULL hs = 0;
    	for(int i = 0;i < T;i ++) {
    		for(int x = 0;x < N;x ++) {
    			for(int j = 0;j < M;j ++) {
    				if(!f[j] && ME::ar[x][i][j]) {
    					feed(x,j);
    				}
    			}
    		}
    		int S = done();
    		for(int j = 0;j < M;j ++) {
    			int nw = 0;
    			if(!f[j] && !(S>>j&1)) {
    				nw = 1; f[j] = 1;
    			}
    			hs = hs*37 + (nw+5);
    		}
    	}
    	return ME::mp[hs];
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
  • 相关阅读:
    $ vue -Vbash: vue: command not found
    [CISCN2019 华北赛区 Day1 Web1]Dropbox
    AVR汇编(二):AVR架构介绍
    Node.js:Jest测试框架
    企业DevOps之路:Jenkins 流水线
    算法套路学习笔记(第二章) 动态规划系列 2.13-2.19
    Java日期格式
    python中的继承
    【代码学习】聚类方法及实现记录
    【Qt课设】基于Qt实现的中国象棋
  • 原文地址:https://blog.csdn.net/weixin_43960414/article/details/126377827