Codeforces Round #694 (Div. 1)
B - Strange Definition
来看一些结论：
1、两个数 (x,y) 满足条件等价于 (xy=k^2) (两数乘积是完全平方数)
证：若 (xy=k^2)，则有(frac{lcm(x,y)}{gcd(x,y)}=frac{xy}{gcd(x,y)^2}=(frac{sqrt{xy}}{gcd(x,y)})^2=(frac{k}{gcd(x,y)})^2)
对于每一个质因数，(k) 的指数取 (x,y) 指数的平均值，而 (gcd(x,y)) 取较小值，所以 (gcd(x,y)|k)，原式是完全平方数
2、如果 (x,y) 满足条件且 (x,z) 满足条件，则 (y,z) 满足条件
证：结合第一个结论，则 (xy,xz) 是完全平方数。还是考虑 (yz) 每一个质因数的指数，发现一定是偶数，结论成立
3、设 (x=p_1^{k_1}p_2^{k_2}...p_n^{k_n})，(p(x)=p_1^{k_1 & 1}p_2^{k_2 & 1}...p_n^{k_n & 1})。 (x,y) adjacent，当且仅当 (p(x)=p(y))
所以，adjacent 的数初始可以按照结论三划分位几个不重合的集合。如果一个集合的大小为偶数，一次操作后所有 (p(x)) 都变为 (1)
因此对 (w=1) 和 (w>1) 分类考虑，具体答案是什么可以思考一下
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; int f = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar(); }
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
if (f) x = -x;
} const int N = 3e5 + 5;
int n, a[N], c[N], m, p[N];
unordered_map<int, int> cnt;
void find () {
for (int i = 2; i <= 1000; ++i) {
int tag = 1;
for (int j = 2; j * j <= i; ++j)
if (i % j == 0) { tag = 0; break; }
if (tag) p[++m] = i;
}
}
signed main() {
int T; read (T); find ();
while (T--) {
cnt.clear(); read (n);
for (int i = 1; i <= n; ++i) {
int x, y = 1; read (x);
for (int j = 1; j <= m; ++j) {
int cnt = 0;
while (x % p[j] == 0) x /= p[j], cnt ^= 1;
if (cnt) y *= p[j];
}
++cnt[y * x];
}
int a = 0, b = 0, s = 0;
for (auto i : cnt) {
if (i.first == 1) b = max (b, i.second), s += i.second;
else if (i.second & 1) a = max (a, i.second);
else b = max (b, i.second), s += i.second;
}
int q, w; read (q);
while (q--) {
read (w);
if (w == 0) printf ("%lld
", max (a, b));
else printf ("%lld
", max (a, s));
}
}
}
C - Strange Shuffle
1、前 (frac{n}{2}) 轮，(>k) 的数量每次加一，相当于每次扩散 (1)
2、牌的数量从 impostor 开始逆时针递减。感性理解一下，impostor 相当于一个水泵，把左侧的水抽到右侧，逆时针地势逐渐降低。当然 官方题解 有证明。
3、impostor 的位置恒为 (k) ，且左侧 (<k)，右侧 (>k)
官方题解的做法是先等 (sqrt{n}) 轮，然后分成 (sqrt{n}) 块，每块查询一次，一定有一个点是 (>k)，然后二分或暴力根据结论三判断是否是 impostor
但不用先等，直接开始查询有用信息，第 (i) 次跳 (i) 的距离，也 (ok)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 1e5 + 5;
int n, k, m, p, now;
int ask (int x) {
printf ("? %lld
", x + 1); fflush (stdout); cin >> x; return x;
}
signed main() {
ios_base::sync_with_stdio (0);
cin.tie (0);
cin >> n >> k;
for (int i = 1; ; ++i) {
int x = ask (now);
if (x == k) now = (now + i) % n;
else {
if (x < k) {
for (int j = now; ; j = (j + 1) % n)
if (ask (j) == k && ask ((j + 1) % n) > k && ask ((j + n - 1) % n) < k)
return printf ("! %lld
", j + 1), 0;
} else {
for (int j = now; ; j = (j + n - 1) % n)
if (ask (j) == k && ask ((j + 1) % n) > k && ask ((j + n - 1) % n) < k)
return printf ("! %lld
", j + 1), 0;
}
}
}
return 0;
}
D - Strange Housing
很明显的题了。如果图不连通显然无解。如果连通一定优解，构造方法如下：
对整张图进行二分图染色。当然可能不是二分图，也不用管，就是在满足“一条边两端不能同时选”的前提下尽可能染色。
证：如果一个点连出的所有边的另一端都未染色，则把这个点染色，然后一圈点都连通了。
如果存在某条边的另一端已经染色，则已经连通，符合条件
#include <bits/stdc++.h>
using namespace std;
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 3e5 + 5;
int n, m, k[N], c, a[N], vis[N]; vector<int> g[N];
#define pb push_back
void dfs (int u) {
if (k[u] == 1) {
for (int v : g[u])
if (!k[v]) k[v] = 2, vis[v] = 1;
for (int v : g[u])
if (vis[v]) dfs (v); return;
}
for (int v : g[u]) {
if (!k[v]) k[v] = 1, dfs (v);
}
}
signed main() {
int T; read (T);
while (T--) {
read (n), read (m); c = 0;
for (int i = 1; i <= n; ++i)
k[i] = vis[i] = 0, g[i].clear();
for (int i = 1, u, v; i <= m; ++i)
read (u), read (v), g[u].pb (v), g[v].pb (u);
k[1] = 1, dfs (1); int tag = 1;
for (int i = 1; i <= n; ++i)
if (!k[i]) { tag = 0; break; }
if (!tag) puts ("NO");
else {
puts ("YES");
for (int i = 1; i <= n; ++i)
if (k[i] == 1) a[++c] = i;
printf ("%d
", c);
for (int i = 1; i <= c; ++i)
printf ("%d ", a[i]); puts ("");
}
}
return 0;
}
E - Strange Permutation
对于长度为 (n) 的序列花费不超过 (c) 的方案数为 (ways(n,c)=sum_{i=0}^{c}C_{n-1}^{i})，(在两个数之间插一块板，选板的方案数)，且每个方案对应一个不同的排列
用 (f(x,c,k)) 表示后缀 ([x,n]) ，花费最大为 (c)，排名为 (k) 的操作方案中最左端的操作（用一个二元组表示）。假设已经知道了所有 (f)，做法就比较显然了：每次查询当前的 (f(x,c,k))，减去操作的花费，把 (x) 更新为 (r+1) 迭代查询，最多查询 (c) 次就能得到答案
(f) 的状态数很多，但需要用到的只是离散的一小部分，所以可以构建另一张表来查询 (f)
定义 (L(x,c)) 表示后缀 ([x,n]) ，最大花费为 (c)，排名从小到大的操作方案中最左端操作的一张列表，但这里用三元组 ((l,r,w)) 表示：操作了 (l,r) 序列，操作后还能弄出多少种排列。从 (L(x+1,c)) 推向 (L(x,c))，多出来的就是 (l=x) 的操作，最多 (c) 个，且这些操作一定加在原序列的左端或右端，可以用 (deque) 维护。
查询 (f(x,c,k)) 的时候在 (L(x,c)) 中二分，二分依据是 (w) 的前缀和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 5e4 + 5, M = 5;
int C (int x, int y) {
if (x < 1) return (y == 0);
if (x < y) return 0; int s = 1;
for (int i = 0; i < y; ++i) s *= (x - i);
for (int i = 2; i <= y; ++i) s /= i;
return s;
}
int ways (int len, int c) {
int s = 0;
for (int i = 0; i <= c; ++i)
s += C (len - 1, i); return s;
}
int n, c, Q, a[N], L[5], R[5], ll[5][N], rr[5][N], s[5][N * M * 2];
struct node {
int l, r, w;
void set (int L, int R, int p) {
l = L, r = R, w = ways (n - r, p - (r - l));
}
} q[5][N * M * 2];
int o[10]; int tp;
bool cmp (int x, int y) { return a[x] < a[y]; }
void prework () {
for (int i = 1; i <= c; ++i)
L[i] = n * c, R[i] = L[i], q[i][R[i]] = {n, n, 1};
L[0] = R[0] = 1, q[0][1] = {n, n, 1};
for (int i = n; i >= 1; --i) {
ll[0][i] = rr[0][i] = 1;
for (int j = 1; j <= c; ++j) {
tp = 0;
for (int k = 1; k <= j && i + k <= n; ++k) o[++tp] = i + k;
sort (o + 1, o + tp + 1, cmp);
for (int k = tp, l = i, r; k >= 1; --k)
if (a[r = o[k]] < a[l]) --L[j], q[j][L[j]].set (l, r, j);
for (int k = 1, l = i, r; k <= tp; ++k)
if (a[r = o[k]] > a[l]) ++R[j], q[j][R[j]].set (l, r, j);
ll[j][i] = L[j], rr[j][i] = R[j];
}
}
for (int i = 1; i <= c; ++i)
for (int j = L[i]; j <= R[i]; ++j)
s[i][j] = s[i][j - 1] + q[i][j].w;
}
int sum (int c, int l, int r) {
return s[c][r] - s[c][l - 1];
}
node get (int x, int c, int k) {
int l = ll[c][x], r = rr[c][x], mid, res;
while (l <= r) {
mid = l + r >> 1;
if (sum (c, ll[c][x], mid) >= k) res = mid, r = mid - 1;
else l = mid + 1;
}
return {q[c][res].l, q[c][res].r, sum (c, ll[c][x], res - 1)};
}
signed main() {
int T; read (T);
while (T--) {
read (n), read (c), read (Q);
for (int i = 1; i <= n; ++i) read (a[i]);
int x = 0, y = 0, now, cnt, res; prework ();
while (Q--) {
read (y), read (x); now = 1, cnt = c, res = a[y];
if (ways (n, c) < x) { puts ("-1"); continue; }
while (x && cnt && now <= n) {
node tmp = get (now, cnt, x);
if (tmp.l <= y && tmp.r >= y) {
res = a[tmp.l + tmp.r - y]; break;
}
now = tmp.r + 1, cnt -= (tmp.r - tmp.l), x -= tmp.w;
}
printf ("%lld
", res);
}
}
return 0;
}