[cf1290D]Coffee Varieties

思路

统计数的种类数，也等价于统计有多少个数满足其之前没有与其相同的数

将序列以$\frac{k}{2}$为块大小分块，那么即会有$m=\frac{2n}{k}$个块

（关于$k=1$的情况，以1为块大小分块即可，具体可以自行代入检验）

考虑$\forall 1\le i<j\le m$，将第$i$个块的数和第$j$个块中的数依次加入$S$中（然后清空），那么一个数有贡献当且仅当其每一次加入时$S$中都没有与其相同的数

另外，每一个块内部只要其被操作即会考虑，注意特判$m=1$时（此时必然是$n=k=1$）

考虑这样的询问次数，不难得到即为$k{m\choose 2}\approx\frac{2n^{2}}{k}$，显然无法通过

优化1

考虑优化，对于$1\le i<j<k\le m$，操作完第$i$个块和第$j$个块后可以不清空，直接操作第$j$个块和第$k$个块，这样只需要加入第$k$个块中的数即可，那么次数也即从$k$变为了$\frac{k}{2}$

具体的，可以看作一张$m$个点的单向完全图（即仅有$i<j$时满足$(i,j)\in E$），将所有的边划分为若干条链（不允许重复，重复不妨拆成两条链），最终询问次数即为$\frac{k}{2}{m\choose 2}+\frac{k}{2}$链数（长度非0）

关于如何划分，考虑枚举$d=j-i$，并将这类边按以下方式划分
$$
1-(d+1)-(2d+1)-...\\2-(d+2)-(2d+2)-...\\......\\d-2d-3d-...
$$
考虑链数，对$d$的值分类讨论：

1.若$d\le \frac{m}{2}$，显然只有$d$条链

2.若$d>\frac{m}{2}$，注意到若起点大于$m-d$，那么长度为0，因此也只有$m-d$条链

综上，链数即为$\sum_{d=1}^{\frac{m}{2}}d+\sum_{d=\frac{m}{2}+1}^{m}(m-d)=\frac{n^{2}}{k^{2}}$，代入可得询问次数约为$\frac{3n^{2}}{2k}$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 int n,m,k,ans,st[N],ed[N],vis[N];

 5 char s[1];

 6 void clear(){

 7     printf("R\n");

 8     fflush(stdout);

 9 }

10 void add(int x){

11     printf("? %d\n",x);

12     fflush(stdout);

13     scanf("%s",s);

14     if (s[0]=='Y')vis[x]=1;

15 }

16 void write(int x){

17     printf("! %d\n",x);

18     fflush(stdout);

19 }

20 int main(){

21     scanf("%d%d",&n,&k);

22     k=max(k/2,1),m=n/k;

23     if (m==1){

24         write(1);

25         return 0;

26     }

27     for(int i=1;i<=m;i++)st[i]=(i-1)*k+1,ed[i]=i*k;

28     for(int i=1;i<=m/2;i++)

29         for(int j=1;j<=i;j++){

30             clear();

31             for(int k=j;k<=m;k+=i)

32                 for(int l=st[k];l<=ed[k];l++)add(l);

33         }

34     for(int i=m/2+1;i<=m;i++)

35         for(int j=1;j<=m-i;j++){

36             clear();

37             for(int k=j;k<=m;k+=i)

38                 for(int l=st[k];l<=ed[k];l++)add(l);

39         }

40     for(int i=1;i<=n;i++)

41         if (!vis[i])ans++;

42     write(ans);

43     return 0;

44 }

优化2

注意到长度$>\frac{m}{2}$的链至多只有1条，因此$\frac{3n^{2}}{2k}$基本已经达到了下限，还需要新的优化

具体的，考虑在查询时，如果当前数已经确定没有贡献，就不再加入

这样优化的意义并不仅仅是减少了这一次操作，而是整张图并不一定要是DAG，即使出现环也可以保证每一种数恰好产生一个贡献（即保留一个）

此时，图即变成了无向图（每一条边可以任意定向），将$m$个点的无向完全图划分为$\frac{m}{2}$条路径（$m$为偶数）是一个经典的问题，具体方式即
$$
1-m-2-(m-1)-3-...-(\frac{m}{2}+1)\\2-1-3-m-4-...-(\frac{m}{2}+2)\\......\\\frac{m}{2}-(\frac{m}{2}-1)-(\frac{m}{2}+1)-(\frac{m}{2}-2)-(\frac{m}{2}+2)-...-m
$$
关于正确性，感性理解即将这$m$个点按$1,2,...,m$顺时针排列，每一次即将上一次的路径顺时针旋转一格，那么每一条边都恰好旋转了一圈，即遍历了逆时针方向该跨度的所有边

综上，链数即为$\frac{m}{2}$，代入可得询问次数为$\frac{n^{2}}{k}$（$\frac{mk}{4}$恰和前者${m\choose 2}$估计为$m^{2}$的误差抵消），可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 int n,m,k,ans,st[N],ed[N],vis[N];

 5 char s[1];

 6 void clear(){

 7     printf("R\n");

 8     fflush(stdout);

 9 }

10 void add(int x){

11     if (vis[x])return;

12     printf("? %d\n",x);

13     fflush(stdout);

14     scanf("%s",s);

15     if (s[0]=='Y')vis[x]=1;

16 }

17 void write(int x){

18     printf("! %d\n",x);

19     fflush(stdout);

20 }

21 int main(){

22     scanf("%d%d",&n,&k);

23     k=max(k/2,1),m=n/k;

24     if (m==1){

25         write(1);

26         return 0;

27     }

28     for(int i=1;i<=m;i++)st[i]=(i-1)*k+1,ed[i]=i*k;

29     for(int i=1;i<=m/2;i++){

30         clear();

31         int shift=0;

32         for(int j=1;j<=m;j++){

33             int pos=(i+shift+m-1)%m+1;

34             for(int k=st[pos];k<=ed[pos];k++)add(k);

35             if (j&1)shift++;

36             shift=-shift;

37         }

38     }

39     for(int i=1;i<=n;i++)

40         if (!vis[i])ans++;

41     write(ans);

42     return 0;

43 }

巴特西

[cf1290D]Coffee Varieties

思路

优化1

优化2

最新文章

热门文章