写在前面
比赛地址：https://codeforces.com/contest/1848。
我现在手里有三套题要补呃呃
这套是两天前补的了，所以简单写写。
太好玩辣，多校！
A
考虑一个 2x2 的矩阵，若小波奇和她的辣妹朋友位于对角线上就会被辣妹朋友堵在墙角，若相邻则永远抓不到。
发现移动后所有人坐标之和的奇偶性关系不变，则如果存在一个辣妹朋友坐标之和与小波奇的奇偶性相同，则小波奇就会被堵。
由于辣妹后动，可以假定聪明的辣妹总能把小波奇堵在墙角。于是仅需判断是否有辣妹和小波奇的坐标之和奇偶性相同即可。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int n = read(), m = read(), k = read();
int x = read(), y = read(), sum = (x + y) % 2, cnt = 0;
for (int i = 1; i <= k; ++ i) {
int xx = read(), yy = read(), summ = (xx + yy) % 2;
if (sum == summ) ++ cnt;
}
printf("%s\n", cnt >= 1 ? "NO" : "YES");
}
return 0;
}
B
直接做。
对于每种颜色统计相邻两者的间隔并把最大的间隔中间的位置刷成该颜色，比较所有颜色操作后的最大间隔即可。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 2e5 + 10;
//=============================================================
int n, k, last[kN];
std::vector <int> dis[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), k = read();
for (int i = 1; i <= k; ++ i) {
last[i] = 0;
dis[i].clear();
}
for (int i = 1; i <= n; ++ i) {
int a = read();
dis[a].push_back(-(i - last[a] - 1));
last[a] = i;
}
for (int i = 1; i <= k; ++ i) {
dis[i].push_back(-(n + 1 - last[i] - 1));
}
int ans = n;
for (int i = 1; i <= k; ++ i) {
std::sort(dis[i].begin(), dis[i].end());
int d1 = -dis[i][0], d2 = -dis[i][1];
d1 = d1 / 2;
// printf("--%d %d", d1, d2);
ans = std::min(ans, std::max(d1, d2));
}
printf("%d\n", ans);
}
return 0;
}
C
首先忽略初始为 0 0 的位置。
发现当某个位置的 \(a,b\) 满足其中一者为 0 后就会进入一个周期为 3 轮的循环。
于是计算出每个位置到达状态 0 0 的最早时间，如果所有位置的最早时间对 3 取模后均相等则可行。
怎么计算最早时间呢？发现进行 3 轮后状态就会由 \(b, a\) 变为 \(b, a - 2\times b\)，于是考虑一个类似辗转相除的做法，\(a>b\) 时直接除 \(2\times b\)，否则暴力操作。可以发现直接暴力操作就是主要慢在 \(a\) 远大于 \(b\) 的情况，所以这个算法的表现会很好。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN], b[kN];
LL t[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Calc(int pos_) {
int a_ = a[pos_], b_ = b[pos_];
t[pos_] = 0;
while (1) {
if (b_ != 0) {
int k = a_ / (2 * b_);
a_ = a_ - 2 * k * b_;
t[pos_] += 3 * k;
}
if (a_ == 0) break;
int temp = b_;
b_ = abs(a_ - b_), a_ = temp;
t[pos_] ++;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
int flag = 0;
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) {
b[i] = read();
Calc(i);
t[i] %= 3;
if (a[i] == 0 && b[i] == 0) t[i] = -1;
}
std::sort(t + 1, t + n + 1);
for (int i = 2; i <= n; ++ i) {
if (t[i - 1] == -1) continue;
if (t[i] != t[i - 1]) flag = 1;
}
// for (int i = 1; i <= n; ++ i) printf("%d ", t[i]);
printf("%s\n", flag ? "NO" : "YES");
}
return 0;
}
/*
1
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
1
6
0 0 0 0 1 0
0 0 1 0 0 0
*/
D
\(T\) 组数据，每组数据给定整数 \(s, k\)，给定两种操作：
- 获得 \(s\) 的价值。
- 令 \(s\) 加上其个位上的数。
两种操作一共可以进行 \(k\) 次，最大化可以获得的价值。
\(1\le T\le 10^5\)，\(0\le s\le 10^9\)，\(1\le k\le 10^9\)。
3S，256MB。
赛时差点、、、我好 spy。
显然先只进行操作二再进行操作一，于是猜测进行操作二的次数和价值之间是单峰的。
又发现进行操作二时 \(s\) 的最后一位，要么进行几次操作后保持为 0，这种情况直接暴力即可；要么进入循环节 \(2\rightarrow 4\rightarrow 8\rightarrow 6\rightarrow 2\) 的。于是可以先尝试把最后一位调整到 2，之后就可以 \(O(1)\) 算进行若干次操作二最后的价值了。
然后赛时稍微肉眼检验了一下就直接写了个三分……但是挂了。看来不是单峰的。怎么会是呢？
考虑设把 \(s\) 最后一位调整为 \(a(a\in \{2, 4, 6, 8\})\) 时获得了 \(b\) 的价值，之后还可以进行 \(c\) 次操作，然后考虑按一个循环节（4 次操作）为单位进行操作，若进行了 \(x\) 轮，显然最后的价值为：\((s + 20\times x)(c - 4\times x) + b\)。一个二次函数，显然单峰。
则可以把上述错误算法改为先尝试把最后一位调整到 2、4、6、8，之后把按一个循环节（4 次操作）为单位进行操作的次数看做变量，就可以三分或者套公式 \(O(1)\) 算价值的最大值了。
下面是一份三分的代码。
//
/*
By:Luckyblock
*/
#pragma GCC optimize(2)
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
//=============================================================
LL s, k, ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
LL Calc(LL times_) {
return 1ll * (s + 20ll * times_) * (k - 4 * times_);
}
void Solve() {
LL l = 1, r = k / 4;
for (; l <= r; ) {
LL mid1 = (2ll * l + r) / 3ll, mid2 = (l + 2ll * r) / 3ll;
LL ret1 = Calc(mid1), ret2 = Calc(mid2);
ans = std::max(ans, std::max(ret1, ret2));
if (ret1 <= ret2) {
l = mid1 + 1;
} else {
r = mid2 - 1;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
// freopen("2.txt", "w", stdout);
int T = read();
while (T --) {
s = 1ll * read(), k = 1ll * read(), ans = s * k;
if (s % 5ll == 0) {
s += s % 10, -- k;
ans = std::max(ans, s * k);
printf("%lld\n", ans);
continue;
}
while (k && s % 10 != 2) {
-- k;
s += s % 10;
ans = std::max(ans, s * k);
}
for (int i = 1; i <= 4 && k; ++ i) {
ans = std::max(ans, s * k);
Solve();
s += s % 10;
-- k;
}
printf("%lld\n", ans);
}
return 0;
}
E
寄吧手玩结论题，详细证明见官方题解。
发现每次打水漂儿弹起来的飞过的距离之和是一个等差数列的形式，把它写成与初始的距离 \(f\) 和弹起次数有关的一个函数，考虑函数值能否等于 \(X\)。稍微移个项再构造一下可以发现，当 \(f_i\) 为 \(X\) 的奇因数时总能满足条件，否则均不满足。
于是每次询问的答案即为 \(X\) 的奇因数的个数，即不包含质因子 2 的因数的个数。
如果只有一次询问——太典了，质因数分解 \(X\) 即可。但是有多次询问，但是每次询问都是在前一次基础上再乘上一个小于 \(10^6\) 的数——考虑预处理 \(1\sim 10^6\) 中所有数的质因数分解，再与当前询问的质因数分解合并即可。在此过程中顺便维护答案。
一个坑点是 \(X\) 的质因数分解中可能出现次数为模数 \(M\) 的情况——无法通过乘逆元恢复到乘上 \(M\) 之前的答案。注意特判一下，如果次数为 0 则不直接乘进答案，而是额外记录一个这种质因子的个数，个数不为 0 直接输出 0。
查了下约数个数的数量级：对于约数个数上界的估计 - Ubospica，可以粗略地估计 \(1\sim n\) 中所有数的约数个数的上界大概是 \(O(n\sqrt n)\) 级别。记 \(n=10^6\)，我的写法用了 map 预处理的时空复杂度约为 \(O(n\sqrt n\log w)\) 级别，每次询问复杂度约为 \(O(\sqrt{n}\log w)\)，则总复杂度上界为 \(O((n+q)\sqrt n\log w)\) 级别。实际上跑得挺快的，3S 时限才跑了 1.3 S。
//
/*
By:Luckyblock
*/
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int x, q, cntmod;
bool vis[kN];
std::vector <int> p[kN];
std::map <int, int> c[kN];
LL mod, ans = 1, cnt[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
LL Qpow(LL x_, LL y_) {
LL ret = 1;
while (y_) {
if (y_ & 1) ret = ret * x_ % mod;
x_ = x_ * x_ % mod;
y_ >>= 1;
}
return ret;
}
LL Inv(int x_) {
return Qpow(x_, mod - 2);
}
void Init() {
for (int i = 2; i < kN; ++ i) {
if (!vis[i]) p[i].push_back(i);
for (int j = 2; i * j < kN; ++ j) {
vis[i * j] = true;
if (!vis[i]) p[i * j].push_back(i);
}
for (int j = 0, sz = p[i].size(); j < sz; ++ j) {
int now = p[i][j];
if (!c[i / now].count(now)) c[i][now] = 1;
else c[i][now] = c[i / now][now] + 1;
}
while (!vis[i] && x % i == 0) ++ cnt[i], x /= i;
if (i != 2) ans = ans * (cnt[i] + 1ll) % mod;
}
if (x != 1) ans = ans * 2ll % mod;
}
void Solve(int xi_) {
for (int i = 0, sz = p[xi_].size(); i < sz; ++ i) {
int now = p[xi_][i], delta = c[xi_][now];
if (now == 2) continue;
if ((cnt[now] + 1ll) % mod != 0) ans = ans * Inv(cnt[now] + 1ll) % mod;
else -- cntmod;
cnt[now] = (cnt[now] + delta) % mod;
if ((cnt[now] + 1ll) % mod == 0) ++ cntmod;
else ans = ans * (cnt[now] + 1ll) % mod;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
x = read(), q = read(), mod = read();
Init();
// printf("--%lld\n", ans);
for (int i = 1; i <= q; ++ i) {
int xi = read();
Solve(xi);
printf("%lld\n", cntmod ? 0ll : ans);
}
return 0;
}
F
还没补就去打牛客了。
咕咕、、、
看着代码好短，好像还是手玩+数学。
数学场！
写在最后
学到了什么：
- 可以考虑小范围情况并假设一般情况总会变为小范围情况。
- 当你发现你可以把一个算法的复杂度瓶颈搞掉——那你已经赢了。
- 循环节是好的。
- 第一次遇到乘上模数的情况……学习了！
光钻池子砸了一百分除了涛宝草
没一井不要抽马娘，会变得不幸。
黛雅你带我走吧黛雅，黛雅酱我真的好喜欢你啊为了你我要复活世嘉！