CF1336D Yui and Mahjong Set(交互)
题面大意
这是一道交互题。
有一个由 (n) 个数构成的集合 (S)，内部元素可以重复。
保证，内部元素的值 (a_i) 都满足 (1le a_ile n)，且对于一种值 (k) 保证 ((sum_{iin S} [a_i=k])le n)，即每种值在集合内不会出现超过 (n) 次。
定义一个 (mathbf {triplet}) 为 (S) 的一个大小为 (3) 的子集，且这三个元素的值相同。
定义一个 (mathbf{straight}) 为 (S) 的一个大小为 (3) 的子集，且这三个元素的值连续，例如 ({2,3,4}) 是一个 (mathbf{straight})，但是 ({1,3,5}) 不是一个 (mathbf{straight})
例如，对于集合 ({1,2,2,1,3}) 中，其 (mathbf{straight}) 的数量为 (4)
现在你可以进行至多 (n) 次查询操作和 (1) 次回答操作：
-
查询操作：将一个数 (x(1le xle n)) 插入集合 (S)，然后交互器会告诉你插入结束后集合 (S) 中的 (mathbf{triplet}) 和 (mathbf{straight}) 的数量。
-
回答操作：令 (c_i) 表示集合 (S) 中权值为 (c_i) 的数的个数，则你需要求出对于初始的集合 (S)，求出 (c_1,c_2sim c_n)
-
交互器会告诉您 (n) 以及初始时集合 (S) 中的 (mathbf{triplet}) 和 (mathbf{straight}) 的数量。
执行查询操作的格式为 + x，执行回答操作的格式为 ! c1 c2 c3 ... cn
数据范围
(4le nle 100)
解题思路
交互题怎么都那么强啊
显然我们看总量是没有什么用的，要看增量。
首先如果一个数出现个数大于等于 2，那么给它加一通过 (mathbf{triplet}) 的数量可以直接求出它到底出现了几次，否则它的出现情况就是 0 和 1。
进一步的，确定一个数最多只用两次。另外加 1 时的 (mathbf{straight}) 只会和 2，3 有关，根据我们头脑中的搜索剪枝，最终得到了这样的一个可行解。1，3，1 的顺序能让我们同时确定 1 和 2，确定 1 用 (mathbf{triplet}) 即可，确定 2 通过两次询问 (mathbf{straight}) 得到，即解方程组 (left{egin{matrix} bc=k_1\b(c+1)=k_2end{matrix} ight.) ，c 当 b 不等于 0 时能够解出，那么我们第一开始就把 b 加一就行了，这是我们用四次求出了前三个值，并且保证大于 0。
如果 (n = 4)，把 (mathbf{straight}) 的方程都列出来，直接解即可。
否则，我们发现通过前几次询问，我们能确定 4 是否是 0，这样我们询问 4 的时候就可以直接确定了，询问 4 的时候又可以得知 5 是否是 0，以此类推，直到 (n-1) 时，我们直接可以通过解个方程得到 (c_n) 了。
/*
／＞ フ
| _ _|
／`ミ _x 彡
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
*/
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;
template <typename T>
void read(T &x) {
x = 0; bool f = 0;
char c = getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
for (;isdigit(c);c=getchar()) x=x*10+(c^48);
if (f) x=-x;
}
template<typename F>
inline void write(F x, char ed = '
') {
static short st[30];short tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar(ed);
}
const int N = 5005;
ll f[N], cnt[N], vis[N], nc[N], n;
inline ll C(ll x) { return x * (x - 1) / 2; }
ll del(ll x, int t) {
if (x == 0) return vis[t];
for (int i = 2;i <= 200; i++)
if (x == C(i)) return i;
return 0;
}
ll Tp, Sp, T, S;
void query(int x, ll &T, ll &S) {
putchar('+'), putchar(' '), write(x);
fflush(stdout), read(T), read(S);
}
int main() {
read(n), read(Tp), read(Sp); ll d = 0;
query(2, Tp, Sp);
query(1, T, S), d = S - Sp;
Tp = T, Sp = S, query(3, T, S);
ll dd = S - Sp;
Tp = T, Sp = S, query(1, T, S);
vis[1] = 1, cnt[1] = del(T - Tp, 1) - 1;
cnt[2] = S - Sp - d - 1;
cnt[3] = d / (cnt[2] + 1);
if (n == 4) {
cnt[4] = dd - (cnt[1] + 1) * (cnt[2] + 1);
cnt[4] /= (cnt[2] + 1);
putchar('!'); putchar(' ');
for (int i = 1;i <= n; i++) write(cnt[i], ' ');
return 0;
}
nc[1] = cnt[1] + 2, nc[2] = cnt[2] + 1, nc[3] = cnt[3] + 1;
dd -= (cnt[1] + 1) * (cnt[2] + 1); vis[4] = dd ? 1 : 0;
for (int i = 4;i < n; i++) {
Tp = T, Sp = S, query(i, T, S);
ll res = S - Sp; res -= nc[i-1] * nc[i-2];
if (res > 0) vis[i + 1] = 1;
cnt[i] = del(T - Tp, i);
nc[i] = cnt[i] + 1;
}
S -= Sp + nc[n-2] * nc[n-3];
cnt[n] = S / nc[n-2];
putchar('!'); putchar(' ');
for (int i = 1;i <= n; i++) write(cnt[i], ' ');
return 0;
}
/*
5
1 6
1 12
2 18
5 24
8 32
8 48
*/