铁饭饭（ironricerice）题解

第一次出交互题。

铁饭饭 (ironricerice)

题目信息

时间限制：$8000\,\text{ms}$。
空间限制：$512\,\texttt{MB}$。
本题仅支持 C++ 系列语言的提交。
这是一道交互题。

题目背景

作为一名软妹、魔法少女、机房偶像，同时也是一名附中学生的 Vxlimo 桀桀，她午餐最爱去的店便是食堂的「初大妈铁板饭」。这家店因套餐价格实惠、分量十足，收到广大附中同学的喜爱。同时这家店的套餐种类也十分多样，光是主食就有铁板饭、铁板面、铁饭饭、铁板板四种，配菜种类更是多到数不过来。除了传统的黑椒牛柳、咖喱鸡排这样四种主食均可搭配的种类，也有并非可搭配每种主食的独特种类，例如只能搭配铁板板的咖喱肥牛。

来到附中快两年了，Vxlimo 她还是没有把整个菜单摸透。据说到高三「初大妈铁板饭」又要推出新款主食铁面面了，Vxlimo 想要赶紧把现在的菜单摸清楚，以便之后点菜方便。

题目描述

可以知道的是，所有主菜加配菜的搭配方式共有 $N$ 种，Vxlimo 将其编号为 $1\sim N$。

Vxlimo 她可以选择去点一份被她编号为 $i$ 的套餐，你不需要知道为什么食堂工作人员可以听懂她点的是哪份套餐。吃完后，Vxlimo 会和自己的记忆进行比对，并判断出今天吃的配菜是否有与自己记忆中吃过的相同的。但是即使聪明如 Vxlimo，吃饭这样的琐事，她也只能记住最多 $K$ 天的信息，例如：如果她只能记 $1$ 天的信息，那么第二天吃完饭，和第一天的记忆比对完后，到了第三天她便忘记了，只剩下第二天的记忆。

Vxlimo 也可以选择这段时间（超过 $K$ 天）不去「初大妈铁板饭」吃饭了，去别的店换换口味。

离高三不远了，所以点餐的次数 $P$ 和换口味的次数 $Q$ 都分别不能超过一定值。

Vxlimo 的第一个目标便是把一共有多少种配菜搞清楚。

作为马猴烧酒，Vxlimo 桀桀可以穿梭于 $T$ 个平行宇宙中，她想把每个宇宙中的菜单都摸清楚。

实现细节

你不需要，也不应该实现主函数，你只需要实现函数 FindOut(N, K)，这个函数的返回值应是配菜的种类数，$N,K$ 的意义如题面所示。

你可以通过调用如下两个函数来和交互库进行交互：

• Order(x)：
  调用这个函数表示 Vxlimo 桀桀选择去点一份编号为 $x$ 的套餐。
  注意：你需要保证 $x$ 为整数且 $1\le x\le N$，否则会被认为执行非法操作，该组数据得 $0$ 分。
• Change()：
  调用这个函数代表 Vxlimo 桀桀选择换换口味，去其他的店吃饭。

评测时，交互库会恰好调用 FindOut $T$ 次。

本题保证数据在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。

数据保证在调用次数限制下，交互库运行所需的时间不超过 $1\,\text{s}$；交互库使用的内存大小固定，且不超过 $128\,\text{MB}$。

实现方法

附加文件中已经提供了一个 template_ironricerice.cpp，请将这个文件拷贝一份，重命名为 ironricerice.cpp，然后在其基础上答题。

请确保你的程序开头有 #include "ironricerice.h"。

你需要实现的函数 FindOut 的接口信息如下：

int FindOut(int N, int K);

你可以调用的交互函数的接口如下：

bool Order(int x);
void Change();

测试程序方式

试题目录下的 grader.cpp 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

你需要在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp ironricerice.cpp -o ironricerice -O2 -std=c++14 -lm

对于编译得到的可执行程序，其将从标准输入读入以下格式的数据：

• 第一行包含一个整数 $T$，表示数据组数。
• 接下来对于每组数据，第一行四个整数 $N,K$，意义如题面描述；第二行 $N$ 个整数，第 $i$ 个整数为 $A_i$，表示编号为 $i$ 的套餐配菜种类是 $A_i$。
• 读入完成之后，交互库将调用恰好 $T$ 次函数 FindOut，并用输入的数据测试你的函数。每次你的函数正确返回后，交互库会判断你的计算是否正确，并会输出相应的信息。

评分方式

最终评测只会收取 ironricerice.cpp，修改选手目录下其他文件对评测无效。

本题首先会受到和传统题相同的限制。由于本题只有 $1$ 组评测数据，编译错误、运行错误、超时、内存超限等错误都会导致本题总分为 $0$ 分。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点的一组数据中，如题意所示，你的程序调用 Order、Change 函数的次数分别为 $P,Q$，设标准答案为 $F$，你实现的 FindOut 函数返回的答案为 $G$，再设 $S$ 为该测试点满分除以数据组数，则你在改组数据的得分，按照如下方式计算：

• 若函数 FindOut 不正常返回，或者存在非法操作，得 $0$ 分。
• 若 $F\ne G$，或者 $P>N^2$，或者 $Q>N^2$，得 $0$ 分。
• 若不满足以上两个条件，设 $p_1=\dfrac{N^2}{K},p_2=\dfrac{3N^2}{2K},p_3=\dfrac{2N^2}{K}$，$q_1=\dfrac{N}{K},q_2=\dfrac{N^2}{K^2},q_3=\dfrac{2N^2}{K^2}$，则得

  $\Large 0.75^{\sum_{i=1}^3{[P>p_i]}}\times 0.9^{\sum_{i=1}^3{[Q>q_i]}}\times S$

  分。
• 注意：若你的程序尝试以任何形式攻击交互库，整题得 $0$ 分。

对于一个测试点，得分为该测试点下所有组数据的得分之和。

样例

假设可执行文件读入的数据为：

2
4 2
1 4 1 3
8 8
1 2 3 4 5 6 6 6

下面是一个正确但是没法得到满分的交互过程。

选手程序	交互库	说明
	调用 FindOut(4, 2)。	开始测试第 $1$ 组数据。
调用 Order(1)。	返回 false。	Vxlimo 点了一份编号为 $1$ 的套餐，并比对记忆。
调用 Order(2)。	返回 false。	Vxlimo 点了一份编号为 $2$ 的套餐，并比对记忆。
调用 Order(3)。	返回 true。	Vxlimo 点了一份编号为 $3$ 的套餐，并比对记忆。
调用 Order(4)。	返回 false。	Vxlimo 点了一份编号为 $4$ 的套餐，并比对记忆。
调用 Change。		Vxlimo 选择去换换口味。
调用 Order(4)。	返回 false。	Vxlimo 点了一份编号为 $4$ 的套餐，并比对记忆。
调用 Order(1)。	返回 false。	Vxlimo 点了一份编号为 $1$ 的套餐，并比对记忆。
调用 Order(2)。	返回 false。	Vxlimo 点了一份编号为 $2$ 的套餐，并比对记忆。
调用 Order(4)。	返回 false。	Vxlimo 点了一份编号为 $4$ 的套餐，并比对记忆。
调用 Order(1)。	返回 false。	Vxlimo 点了一份编号为 $1$ 的套餐，并比对记忆。
FindOut(4, 2) 返回 $3$。	向屏幕打印相应信息	第 $1$ 组数据交互结束，答案正确，但是点餐 的次数超过限制，得 $0.75\times 50=37.5$ 分。
	调用 FindOut(8, 8)。	开始测试第 $2$ 组数据。
调用 Order(2)。	返回 false。	Vxlimo 点了一份编号为 $2$ 的套餐，并比对记忆。
调用 Order(6)。	返回 false。	Vxlimo 点了一份编号为 $6$ 的套餐，并比对记忆。
调用 Order(4)。	返回 false。	Vxlimo 点了一份编号为 $4$ 的套餐，并比对记忆。
调用 Order(2)。	返回 true。	Vxlimo 点了一份编号为 $2$ 的套餐，并比对记忆。
调用 Order(5)。	返回 false。	Vxlimo 点了一份编号为 $5$ 的套餐，并比对记忆。
FindOut(8, 8) 返回 $6$。	向屏幕打印相应信息。	第 $2$ 组数据交互结束，答案正确，得 $50$ 分。
	向屏幕打印最后总得分。	总得分为 $37.5+50=87.5$ 分。

数据范围与提示

对于 $100\%$ 的数据，$T=100$，$1\le K\le N\le 1024$，$\forall 1\le i\le N,1\le A_i \le N$，保证 $N,K$ 均是 $2$ 的整数次幂且 $\dfrac{N^2}{K}\le 10000$。

再次提醒，题目保证测试数据在交互开始之前已经完全确定，而不会根据和你的程序的交互动态构造。
再次提醒，若你的程序尝试以任何形式攻击交互库，整题得 $0$ 分。
再次提醒，由于本题只有 $1$ 组评测数据，编译错误、运行错误、超时、内存超限等错误都会导致本题总分为 $0$ 分。建议仔细检查避免此类错误。

题解

原题：https://codeforces.com/problemset/problem/1290/D

我永远喜欢 Vxlimo！！！

简要题意

有一个长度为 $N$ 的正整数序列 $\{A_i\}$，你知道 $N$，但你不知道里面每个 $A_i$ 具体是多少。你还有一个队列，其容量为 $K$。

你可以通过以下两种操作获取信息：

1. 选择一个下标 $x$，你可以得到当前队列中是否有元素与 $A_x$ 相同的信息。然后将 $A_x$ 放入队尾。放入后若队列元素个数超过 $K$，则弹出队头。
2. 清空整个队列。

两种操作的次数都有一定限制。

你要回答整个序列 $\{A_i\}$ 中有多少种不同的值。

$T=100$，$1\le K\le N\le 1024$，$\forall 1\le i\le N,1\le A_i \le N$，保证 $N,K$ 均是 $2$ 的整数次幂且 $\dfrac{N^2}{K}\le 10000$。

解法一

其实原问题相当于要对序列去重。

去重最朴素的就是考虑每一对元素是否相同，如果 $A_i=A_j$，就给其中一个打上标记。最后答案就是没有被打上标记的点的数量。

这样做每次加完 $i$ 和 $j$ 后就要清空队列，所以清空次数为 $N(N-1)/2$，查询次数为 $N(N-1)$，不知道可以得几分。

解法二

发现解法一中每次加入两个数就清空太过浪费，没有充分利用队列容量为 $K$ 的条件。

发现通过使用队列，我们可以对任意不超过 $K$ 个数去重，于是考虑分块处理。因为我们还要对块之间进行去重，所以我们每 $K/2$ 分一块，实际上相当于把 $K/2$ 个点一起缩成了一个带权的点。然后先对每一块去重，剩下和解法一一样。

此做法清空次数为 $\dfrac{2N}{K}\left(\dfrac{2N}{K}-1\right)\div 2=\dfrac{2N^2}{K^2}-\dfrac{N}{K}$，查询次数为清空次数乘上 $K$，即 $\dfrac{2N^2}{K}-N$，可以得到 $55$ 分。

解法三

有满足清空次数不超过 $\dfrac{N^2}{K^2}$，查询次数不超过 $\dfrac{3N^2}{2K}$ 的做法，但我个人认为还不如满分做法直观，故略去不讲，想知道可以去看这篇博客。可以得到 $72$ 分。

解法四

我们考虑将问题抽象一下。

我们把每一个块看成一个点，块与块之间需要去重，不如看成边，这样就得到了一个有 $\dfrac{2N}{K}$ 个点的完全图。走过一条路径就相当于先后把路径上相邻的两个点代表的块去重。

那么我们就是要选出若干条路径（路径内部要满足点不相交），使得每条边被覆盖一次以上。

这样清空次数就是路径的数量，而查询次数是总的走过的边数加上清空次数的和再乘上块大小。

为什么路径要内部点不相交呢？举个例子，考虑如果点 $1,2,3$ 都有 $x$ 这个元素，那选 $1\to 2\to 3\to 1$ 这样的路径。走完 $1\to 2\to 3$ 时，$2,3$ 里面的 $x$ 都被打上了标记，而 $1$ 里面的 $x$ 没有标记，这样是对的，$x$ 会被统计到答案里；但如果再走 $3\to 1$，因为 $3$ 里面有 $x$，那么 $1$ 里面的 $x$ 也会被打上标记，则 $x$ 元素便被误删了，没办法统计到答案里。

完全图有着十分漂亮的覆盖方式：之字形划分（zig-zag pattern）。一个 $n$ 个点，$n$ 为偶数的完全图，我们枚举起点 $1\le s\le n/2$，然后走如下路径直到 $n$ 个点都被走过一遍：$s\to s-1\to s+1\to s-2\to s+2\to \cdots$，如果加减完不在 $[1,n]$ 范围内，模一个 $n$ 就好了。模拟一下，发现这样走完 $n/2$ 条链后，每条边都被恰好覆盖到一次。

证明就是考虑，如果将编号从小到大按顺时针排成一圈，那么对于相差奇数的边会顺时针覆盖到，偶数的话会逆时针覆盖到。于是每条边会被覆盖到恰好一次。

这样我们的清空次数就下降到了 $\dfrac{N}{K}$，查询次数降为 $\dfrac{K}{2}\left(\dfrac{2N}{K}\left(\dfrac{2N}{K}-1 \right)\div 2+\dfrac{N}{K} \right)=\dfrac{N^2}{K}$。可以得到 $100$ 分。

其实如果 $n$ 不是偶数上述覆盖方式也是优秀的，我们将起点 $s$ 的范围扩大到 $1\sim n$，可以发现这样不过是把每条边都覆盖了两次。我们可以考虑将块大小放大成 $K$，因为每个两块会正着反着各加一次，没有影响。同样可以做到和每 $\dfrac{K}{2}$ 个分一块一样的清空和查询次数。一样可以得到 $100$ 分。

Code

#include "ironricerice.h"
#include <bits/stdc++.h>
#define il inline
const int N=1030;

int m,s; bool o[N];

il void Work(int x){int i; for (i=x*s-s+1; i<=x*s; i++) if (o[i]&&Order(i)) o[i]=0;}

int FindOut(int n,int k)
{
    s=std::max(k/2,1),m=n/s,memset(o,1,n+1); int i,j,x,E=0;
    for (i=1; i<=n/k; Change(),i++) for (j=1,x=0; j<=m; j++,x=(x<1)-x) Work((i+x+m)%m+1);
    for (i=1; i<=n; i++) E+=o[i];
    return E;
}