交互题练手

wflengxuenong · 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

这个题目左右分组也可以，代码实现可能啰嗦一些。


- 参考代码
```cpp

#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;
}

交互题练手

CF679A Bear and Prime

ABC337E

CF1167B Lost Numbers

P1947

ABC313D

ABC269E

ABC337E