头部背景图片
Decaku 's Blog |
Decaku 's Blog |

CF #616 F. Coffee Varieties

$ 题意:这是一道交互题,你有n个数和一个队列,队列的最大长度为k, \\
你可以询问第i个数,然后交互机会告诉你队列里是否有这个数,询问 \\
完后,队列如果没有满就把这个数塞进去,否则从队首弹出一个数后 \\
再把这个数塞进去,还有一个操作是把队列清空,要求询问次数不超过 \\
n^{2}/2,最后输出一共有多少种不同的数,题目保证n和k都是二的幂次。 \\$


$做法是对于数组分块,每块大小为k/2,然后每次你只要先清队列, \\
然后拿出两块询问就可以了,这个复杂度比较好算,算下来刚好是 \\
题目给的上界,询问次数还能优化,但是我这里已经懒得再写了。$

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=3e4+100;
int vis[maxn];
bool query(int x)
{
cout<<"? "<<x<<"\n";
string s;cin>>s;
return (s[0]=='Y');
}
int main()
{
int n,k;cin>>n>>k;
rep(i,1,n) vis[i]=1;
int sz=k/2,cnt=n/sz;

if(k!=1)
{
rep(i,1,cnt-1)
{
rep(j,i+1,cnt)
{
cout<<"R"<<"\n";
rep(k,(i-1)*sz+1,i*sz) if(query(k)) vis[k]=0;
rep(k,(j-1)*sz+1,j*sz) if(query(k)) vis[k]=0;
}
}
}
else{
rep(i,1,n-1)
{
rep(j,i+1,n)
{
cout<<"R"<<"\n";
query(i);
if(query(j)) vis[i]=0;
}
}
}
int ans=0;
rep(i,1,n) if(vis[i]) ans++;
cout<<"! "<<ans<<"\n";
}
avatar Decaku 菜菜菜