Vika and Her Friends
给定一张网格图，Vika 在 \((x, y)\) 处，她的 \(k\) 个朋友分别在 \((x_{1 \sim k}, y_{1 \sim k})\) 处，每次所有人都必须移动到相邻各格子，询问 Vika 能否永远逃离她烦人的朋友
考虑对格子进行黑白染色，每次移动一定会变换格子颜色，那么只有相同颜色的人才会碰面
#include <bits/stdc++.h>
using namespace std;
signed main() {
int T;
scanf("%d", &T);
for (int n, m, k, x, y; T; --T) {
scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
int me = (x + y) & 1;
bool checker = false;
for (; k; --k) {
scanf("%d%d", &x, &y);
if (me == ((x + y) & 1))
checker = true;
}
puts(checker ? "NO" : "YES");
}
return 0;
}
Vika and the Bridge
有 \(n\) 块木板排成一排，第 \(i\) 块木板的颜色是 \(c_i\)，你站在第一块木板前面，需要跳跃到第 \(n\) 块木板后面，每一次只能跳相同颜色的木板。现在你可以更改一块木板的颜色，使得你每一次跳跃的距离(指两块木板中间部分，不计两端点)的最大值最小，请求出这个值
考虑求出每种颜色木板的最大间隔 \(a\) 与次大间隔 \(b\) ，则答案即为
\[\min (\max(\lfloor \dfrac{a}{2} \rfloor, b)) \]#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
pair<int, int> mx[N];
int a[N], lst[N];
int T, n, K;
inline void clear() {
for (int i = 1; i <= K; ++i)
lst[i] = 0, mx[i] = make_pair(0, 0);
}
inline void update(pair<int, int> &x, int y) {
if (y > x.first)
x.second = x.first, x.first = y;
else if (y > x.second)
x.second = y;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d%d", &n, &K);
clear();
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
for (int i = 1; i <= n; ++i) {
update(mx[a[i]], i - lst[a[i]] - 1);
lst[a[i]] = i;
}
for (int i = 1; i <= K; ++i)
update(mx[i], n + 1 - lst[i] - 1);
int ans = n;
for (int i = 1; i <= K; ++i)
if (lst[i])
ans = min(ans, max(mx[i].first / 2, mx[i].second));
printf("%d\n", ans);
}
return 0;
}
Vika and Price Tags
你有两个长度均为 \(n(1 \le n \le 10^5)\) 的序列 \(a,b(0 \le a_i,b_i \le 10^9)\)，每一次操作令所有 \(a_i = b_i,b_i = |a_i - b_i|\)。问若干次操作后，是否能让所有的 \(a_i\) 值都为 \(0\)。多测。
不难想到将 \(a_i, b_i\) 的 \(\gcd\) 提出来作为公因数，答案不变
设 \(\gcd(a_i, b_i) = g, a' = \dfrac{a_i}{g}, b' = \dfrac{b_i}{g}\) ，那么 \(a_i, b_i\) 其中一个变为 \(0\) 所需步数与 \(a', b'\) 其中一个变为 \(0\) 所需步数相等
注意到每次都是 （偶，奇） -> （奇，奇） -> （奇，偶）为循环，若所有的数都可以同时变为 \(0\) ，则所有的 \(a', b'\) 必为同一种情况
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int a[N], b[N];
int T, n;
inline int gcd(int a, int b) {
if (!a || !b)
return a | b;
while (a ^= b ^= a ^= b %= a);
return b;
}
signed main() {
scanf("%d", &T);
for (; T; --T) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
for (int i = 1; i <= n; ++i)
scanf("%d", b + i);
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 1; i <= n; ++i) {
if (!a[i] && !b[i])
continue;
int g = gcd(a[i], b[i]);
a[i] /= g, b[i] /= g;
if (!(a[i] & 1))
cnt1 = 1;
else if (!(b[i] & 1))
cnt2 = 1;
else
cnt3 = 1;
}
puts(cnt1 + cnt2 + cnt3 <= 1 ? "YES" : "NO");
}
return 0;
}
Vika and Bonuses
共 \(T\leq 10^5\) 组数据。
每组数据给定 \(s,k\)（\(s,k\leq 10^9\)）。
你需要维护一个计数器 \(C\) （初始为 \(0\)）并进行 \(k\) 次操作，每次操作形如二者之一：
\(C\leftarrow C+s\).
\(s\leftarrow s+s\bmod 10\).
输出 \(k\) 次操作后 \(C\) 的最大值。
设 \(f(s, k)\) 为答案
- 当个位为奇数时，答案必为 \(\max(s \times k, f(s + s \bmod{10}, k))\)
- 当个位为 \(0\) 时，\(s + s \bmod{10} = s\) ，此时答案即为 \(s \times k\)
- 否则，个位一定是 \(2 \to 4 \to 8 \to 6\) 的循环，且一次循环增加 \(20\) 。设一共循环 \(n\) 次，则答案为 \((s + 20n)(k - 4n) = -80n^2 + (20k - 4s)n + sk\) ，套用二次函数顶点公式即可
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll EasySolve(ll s, ll k) {
ll ans = s * k;
ll n = max(min((5ll * k - s) / 40ll, k / 4ll), 0ll);
ans = max(ans, -80ll * n * n + (20ll * k - 4ll * s) * n + s * k);
n = min(n + 1, k / 4ll);
ans = max(ans, -80ll * n * n + (20ll * k - 4ll * s) * n + s * k);
return ans;
}
inline ll solve(ll s, ll k) {
if (!(s % 10))
return s * k;
else if ((s % 10) & 1)
return max(s * k, solve(s + s % 10, k - 1));
else {
ll ans = s * k;
for (int i = 1; i <= 4 && k; ++i) {
ans = max(ans, EasySolve(s, k));
s += s % 10, --k;
}
return ans;
}
}
signed main() {
int T;
scanf("%d", &T);
for (ll s, k; T; --T) {
scanf("%lld%lld", &s, &k);
printf("%lld\n", solve(s, k));
}
return 0;
}
Vika and Stone Skipping
打水漂，假设一个人在海岸线以 \(f\) (\(f\) 是正整数)的力量扔出了石子，则石子会在 \(f,f+(f-1),f+(f-1)+(f- 2),...,f+(f-1)+(f-2)+\ldots+1\) 处坐标接触水面(海岸线坐标为 \(0\))。
现在给出一个坐标 \(x\) 和 \(q\) 次询问，对于每次询问，都会给出一个 \(y\) 值，坐标 \(x\) 将变为 \(x \cdot y\)。假设石子在 \(x\) 坐标处接触水面，询问从海岸线扔出石子的力量 \(f\) 有多少种可能，由于数据会比较大，需要将答案对 \(M\) 取模后输出(\(M\) 保证为质数)。
由等差数列公式，得
\[f + (f - 1) + \cdots (f + (c - 1)) = x = \dfrac{(2f - (c - 1))c}{2} \]- 若 \(c\) 为奇数，那么 \(x = (f - \dfrac{c - 1}{2}) \times c\) ，记 \(k - \dfrac{c - 1}{2}, p = f - k\) ，则 \(x = p \times (2k + 1)\) 。因为 \(c - 1 < f\) ，所以 \(p > k\)
- 若 \(c\) 为偶数，则 \(x = (2f - (c - 1)) \times \dfrac{c}{2}\)，记 \(p = \dfrac{c}{2}, k - f - p\) ，则 \(x = (2k + 1) \times p\) 。因为 \(c \leq f\) ，所以 \(p \leq k\)
发现对于 \(x\) 的每个奇因子 \(2k + 1\) ，都能唯一对应一个 \(p\) ，所以答案就是 \(x\) 的奇因子个数
考虑对 \(x\) 是质因数分解，那么答案即为所有奇质数的指数 \(+1\) 之积
用线段树维护单点修改，全局求积即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int X, n, Mod;
namespace SMT {
int s[N << 2];
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
inline void pushup(int x) {
s[x] = 1ll * s[ls(x)] * s[rs(x)] % Mod;
}
void build(int x, int l, int r) {
s[x] = 1;
if (l == r)
return;
int mid = (l + r) >> 1;
build(ls(x), l, mid), build(rs(x), mid + 1, r);
}
void update(int x, int nl, int nr, int pos, int val) {
if (nl == nr) {
s[x] = (s[x] + val) % Mod;
return;
}
int mid = (nl + nr) >> 1;
if (pos <= mid)
update(ls(x), nl, mid, pos, val);
else
update(rs(x), mid + 1, nr, pos, val);
pushup(x);
}
} // namespace SMT
inline int lowbit(int x) {
return x & (~x + 1);
}
signed main() {
scanf("%d%d%d", &X, &n, &Mod);
X /= lowbit(X);
SMT::build(1, 1, 1e6);
int ans = 1;
for (int i = 3; i * i <= X; ++i)
if (!(X % i)) {
int cnt = 0;
while (!(X % i))
X /= i, ++cnt;
if (i <= 1e6)
SMT::update(1, 1, 1e6, i, cnt);
else
ans = 1ll * ans * (cnt + 1) % Mod;
}
if (X > 1)
if (X <= 1e6)
SMT::update(1, 1, 1e6, X, 1);
else
ans = 2ll * ans % Mod;
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
x /= lowbit(x);
for (int j = 3; j * j <= x; ++j)
if (!(x % j)) {
int cnt = 0;
while (!(x % j))
x /= j, ++cnt;
SMT::update(1, 1, 1e6, j, cnt);
}
if (x > 1)
if (x <= 1e6)
SMT::update(1, 1, 1e6, x, 1);
else
ans = 2ll * ans % Mod;
printf("%d\n", 1ll * ans * SMT::s[1] % Mod);
}
return 0;
}
Vika and Wiki
给定长度为 \(n\) 的数组 \(a\) ，每次将所有的 \(a_i\) 变化为 \(a_i \oplus a_{i+1}\) ，特别的，对于 \(a_{n-1}\),其变化为 \(a_{n-1} \oplus a_0\)。
求经过几次变化能使数组 \(a\) 都变化为 \(0\) ，如果永远无法将 \(a\) 都变化为 \(0\) 则输出 \(-1\)。
（此处 \(\oplus\) 指异或，数组下标 \(i\) 由 \(0\) 开始）
设 \(f_{i, j}\) 表示 \(i\) 次操作后 \(j\) 位置上的数，则
\[f_{i, j} = \oplus_{k = 0}^i (\dbinom{i}{k} \bmod 2) \times a_{(j + k) \bmod n} \]注意到 \(\dbinom{i}{j}\) 是奇数当且仅当二进制位上 \(j\) 是 \(i\) 的子集
因为 \(n\) 是 \(2\) 的幂，所以操作 \(n\) 次后一定全是 \(0\) ，答案上界为 \(n\)
直接做一遍高维前缀异或和就能得到 \(f_{1 \sim n, 0}\)
要找到一个 \(ans\) 使得 \(f_{ans, 0 \sim n - 1} = 0\)
首先要 \(f_{ans, 0} = 0\) ，如果在 \(x\) 次操作后位置 \(0\) 清零了但是存在别的位置没清零，设第一个没清零的位置为 \(i\) ，则 \(f_{x + i, 0} \not = 0\) ，所以
\[f_{x, 0 \sim n - 1} = 0 \iff f_{x \sim \infty, 0} = 0 \]#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20 | 1;
int a[N];
int n;
signed main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", a + i);
for (int i = 0; i < 20; ++i)
for (int j = 0; j < (1 << 20); ++j)
if ((j >> i) & 1)
a[j] ^= a[j ^ (1 << i)];
for (int i = n - 1; ~i; --i)
if (a[i]) {
printf("%d", i + 1);
return 0;
}
putchar('0');
return 0;
}