交互题练手

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-13 15:01:17

基本模型

交互题这类型不同于普通的题。可以理解为有个问题需要你解决，你通过输入某些东西。表示你要问系统的问题，这时系统会回答你的问题。在代码中的回答方式就是会输入某个东西就是系统给你的答案，通过这些信息你可以得到问题的解。你是不可以自己测试的，只能提交给系统测试。有个东西需要用到C++中的 fflush(stdout); ，这个东西是用来清空输出缓存区的。因为你一直提问，一直输出，就需要清空输出缓存区。不然就有一些异常。

举一个最简单的例子：猜数字我内心突然想到一个1到100之间的整数x。现在我让你来猜，最多给你7次机会，每次你可以猜一个数字。我会告诉你是大了，还是小了，还是猜对了。方法就是二分。

CF679A Bear and Prime

题目描述

这是一道交互题。有一个在闭区间[2,100]里面的整数X，你的任务是判断整数x是质数还是合数。你可以向系统询问一个数是否为该数的约数，询问方式如下：
1.你输出一个在闭区间[2,100]里面的整数
2.系统回答yes或者no(yes表示你输出的数是该数的约数，no表示你输出的数不是该数的约数)
注意：你最多只能提出20次询问！
每输出一个询问，你需要使用flush，下面提供一些语言的flush语法：
C++语言: fflush(stdout)
JAVA语言: System.out.flush()
Python语言: stdout.flush()
Pascal语言: flush(output)\

算法分析：找出100以内的质数，要找出其两个因子来，才能知道是合数。

77=7*11
25=5*5 
100以内的数最大为2*50，找到50以内最大的 素数47即可。

分成三种情况。

p,素数：只有1和他本身。不询问1，可能询问到本身。

p*p*p ,看要询问p*p判断是否为合数

多个因子p*q，一般情况。

参考代码：

#include<cstdio>
#include<cstring>
using namespace std;
int ask[20]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; \/\/存储需要询问的数。
int cnt;\/\/因数个数。
int main() {
	for(int i=0; i<15; i++) {
		printf("%d\n",ask[i]);\/\/询问。
		fflush(stdout);
		char status[4];
		scanf("%s",&status);
		if(status[0]=='y') { \/\/询问的数是x的因数。
			cnt++;
			if(ask[i]*ask[i]<=100) { \/\/询问的数的平方有可能是x的因数。
				printf("%d\n",ask[i]*ask[i]);\/\/再询问一次。
				fflush(stdout);
				scanf("%s",&status);
				if(status[0]=='y') {
					cnt++;
				}
			}
		}
		if(cnt>=2) { \/\/因数个数大于2。
			printf("composite\n");
			return 0;
		}
	}
	printf("prime\n");
	return 0;
}

ABC337E

题目大意，给定$n$种果汁,其中有一种坏了，和坏了的果汁会胃痛。你打算找最少的人数给你试吃，找出哪种坏了。试吃的适合取出x种果汁混子一起。只要有坏的，试吃的人就会胃痛。问你最少要找多少人试吃，怎么给他们分配试吃的果汁。然后根据反馈，找出坏的果汁。
题目分析

n=9 
可以拿出最后一个不处理。n--； 
算法思路：m，应该与log相关，怎么相关。先想的是分奇数偶数，每组2人，分m组。
后来发现不用每组2人。
分组  n=8 
第0组          12345678 
第一组 奇数 偶数  1357   2468	 可以分成奇数偶数，假设为奇数 偶数没有用了，删掉2468 1357 
第二组             1526   3748   假设又为奇数   保留了15  删掉了37  总共删掉了234678 
第三组             1234   5678   假设为偶数    删掉了1，保留了5
第0组变成第四组 9 
写不完了，不知道对不对
     奇数   偶数  根据进制 
 1： 1111   000   000
 2   1011   100   001
 3   1101   010   010
 4   1001   110   011
 5   1110   001   100
 6   1010   101   101
 7   1100   011   110
 8   1000   111   111
 9：0000 

怎么完成对应关系？用奇数有点奇怪，用偶数正合适 。
怎样用代码实现分配呢？ 
真好把对应位置上的1选出来：0-7 
2468 2^0次位1
3478 2^1次位1
5678 2^2次位1 
 
这个题目左右分组也可以，代码实现可能啰嗦一些。

参考代码


#include <bits\/stdc++.h>
using namespace std;
const int MAXN = 105;
int n;
string s;
int main() {
    cin>>n;
    int m = 0;
    while ((1 << m) < n) m++;
    cout<<m<<endl;
    for (int i = 0; i < m; i++) {
        vector<int> vec;
        for (int j = 0; j < n; j++) if (j >> i & 1) {
            vec.push_back(j + 1);
        }
        cout<<vec.size()<<" ";
        for (int j : vec) cout<<j<<" ";
        cout<<endl;
    }
    \/\/fflush(stdout);\/\/结束输入。 
    cin>>s;
    int ans = 0;
    for (int i =0; i <m; i++) {
        if (s[i] == '1') ans |= 1 << i;
    }
    ans++;
    cout<<ans<<endl;
    return 0;
}

lxn 的博客

博客

CF679A Bear and Prime

ABC337E

CF1167B Lost Numbers

P1947

ABC313D

ABC269E

ABC337E

评论

发表评论