「杂题乱写」AGC 003
点击查看目录
目录
今日推歌是星尘唱的《光》,是尘 2021 年的官方生贺曲。
马上又要到 8.12 了。
手机里有一张“瑞安口腔”的图,有机会传一下。
点击查看歌词
如在黑夜中被熄灭了星空 荒原上看不到尽头
只有这一路相随的孤独 是我黑暗中唯一的盟友
如在寒风中被浇灭了篝火 残余的温度也被夺走
已不能分清颤抖着的身体和心哪个更冰冷 视线渐渐模糊
一路上我都在追逐什么 这些渴望哪个真属于我
他人的期待不过是我的枷锁
一路上我都在为何拼搏 这些目标哪个真适合我
从今以后只做属于我的选择
走吧 放下
走吧 放下
背靠着大地用全力深呼吸 手臂不由自主地上举
一定是对跌落的不甘心 不甘心刚到这里就放弃
面朝向天际重新起身站立 心也以脉搏给出回应
踏出的步伐向远方的黎明有力并始终坚信 日出的光明
一边走一边看四周风景 才发现被忽略过的美丽
所有的感受都将被铭记在心 不必劳烦群星指引
第一道曙光已划破天际 也知晓黑夜会再次光临
如今我已学会在黑夜中前行 已经无所畏惧
走吧 走吧
走吧 再出发
跟随风放飞脑海中的梦想 回应地以坚定的步伐
拥抱海拍打在身上的浪花 让心再次重燃出发
待到再迷茫时回头望 所有脚印会发出光芒
能为你照亮黑夜中专属于你的前行方向
走吧 走吧
走吧 走吧
A | Wanna go back home
N
和 S
必须同时存在或消失,W
和 E
必须同时存在或消失。
B | Simplified mahjong
直接,模拟。
C | BBuBBBlesort!
不难发现当一个数排序前的下标与排序后的下标奇偶性不同,那么一定会用一次操作一,否则只用二操作就可以排到正确的位置上。
那么答案就是排序前的下标与排序后的下标奇偶性不同的数的数量除以二,因为一次操作一其实改变了两个下标的奇偶性。
D | Anticube
首先想到暴力,然后发现数据范围太大了。
然后一个显而易见的思路是,对于一个数 \(x\) 我们把他分解质因数成 \(p_{1}^{k_1}p_{2}^{k_2}\cdots p_{n}^{k_n}\),会有一个对应数 \(x' = p_{1}^{k_1\bmod{3}}p_{2}^{k_2\bmod{3}}\cdots p_{n}^{k_n\bmod{3}}\),若存在一个 \(y\) 的对应数 \(y'\) 与 \(x'\) 的积为立方数,那么 \(x\) 与 \(y\) 的积也是立方数。
不难发现对于一个已知的 \(x'\),与它对应的 \(y'\) 也是一定的。那么对于一组对应的 \(x',y'\),选了其中一个就不能选另一个,且对其他数的选取不会产生任何影响。因此我们只需要统计出所以可能的 \(x'\) 的数量,在 \(x'\) 与其对应的 \(y'\) 中选取数量最多的一个。
对于一个已知的 \(x\),\(x'\) 是很好求的,只需要枚举 \([2, 10^{\frac{10}{3}}]\) 之间的质数的立方。问题是如何快速求对应的 \(y'\)?
首先我们把 \(x'\) 小于 \(10^{\frac{10}{3}}\) 的质因数 \(p_i\)全部除掉,并让 \(y'\) 乘上 \(p_i^{2k_i\bmod{3}}\),然后考虑剩下的数是什么情况(这里的质数都大于 \(10^{\frac{10}{3}}\)):
- 一个质数。
- 两个质数之积。
- 一个质数的平方。
对于前两种情况,令 \(y'\) 乘上这个数的平方;对于第三种情况,令 \(y'\) 乘上这个质数。
这里 \(10^{\frac{10}{3}}\) 可以直接取 \(2160\)。
点击查看代码
const ll N = 1e5 + 10;
namespace SOLVE {
ll n, a[N], b[N], vis[N], ans;
std::vector <ll> prime;
std::map <ll, ll> mp;
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void Pre () {
_for (i, 2, 2160) {
if (!vis[i]) prime.push_back (i);
far (j, prime) {
if (i * j > 2160) break;
vis[i * j] = 1;
if (!(i % j)) break;
}
}
return;
}
inline void In () {
n = rnt ();
_for (i, 1, n) a[i] = rnt ();
return;
}
inline void Solve () {
Pre ();
_for (i, 1, n) {
far (j, prime) {
ll x = j * j * j;
while (!(a[i] % x)) a[i] /= x;
}
ll qwq = a[i]; ++mp[a[i]], b[i] = 1;
far (j, prime) {
if (qwq % j) continue;
if (!(qwq % (j * j))) b[i] *= j;
else b[i] *= j * j;
while (!(qwq % j)) qwq /= j;
}
ll s = (ll)(sqrt (qwq));
if (s * s == qwq) b[i] *= s;
else b[i] *= a[i] * a[i];
}
_for (i, 1, n) {
if (a[i] == 1) continue;
ans += std::max (mp[a[i]], mp[b[i]]);
mp[a[i]] = mp[b[i]] = 0;
}
return;
}
inline void Out () {
printf ("%lld\n", ans + (bool)(mp[1]));
return;
}
}
E | Sequential operations on Sequence
首先发现很多操作都是无用的,那么单调栈搞出来一个单调递增的子序列 \(a\)。
那么当算到 \(a_i\) 时,显然每个数出现次数是其在序列长度为 \(a_{i - 1}\) 出现的次数乘上 \(\left\lfloor\frac{a_i}{a_{i - 1}}\right\rfloor\) 再加上其在 \([1, a_i\bmod{a_{i - 1}}]\) 中出现的次数。
\([1, a_i\bmod{a_{i - 1}}]\) 显然可以继续递归下去,直到右端点小于 \(a_1\)。
但是这个区间加不太好搞,所以考虑差分。
点击查看代码
const ll N = 1e5 + 10;
namespace SOLVE {
ll n, m, t, q[N], c[N], d[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline void F (ll l, ll add) {
ll p = std::lowb (q, t, l) - 1;
if (!p) d[1] += add, d[l + 1] -= add;
else c[p] += l / q[p] * add, F (l % q[p], add);
return;
}
inline void In () {
q[++t] = n = rnt (), m = rnt ();
_for (i, 1, m) {
ll x = rnt ();
while (t && x < q[t]) --t;
q[++t] = x;
}
return;
}
inline void Solve () {
c[t] = 1;
for_ (i, t, 2) {
c[i - 1] += q[i] / q[i - 1] * c[i];
F (q[i] % q[i - 1], c[i]);
}
d[1] += c[1], d[q[1] + 1] -= c[1];
_for (i, 2, n) d[i] += d[i - 1];
return;
}
inline void Out () {
_for (i, 1, n) printf ("%lld\n", d[i]);
return;
}
}
F | Fraction of Fractal
这个网格有三种情况:
- 边界上没有黑格。
- 并排放两个网格时和并列放两个网格时,黑格都是连通的。
- 并排放两个网格时和并列放两个网格时,只有一种时候下黑格是连通的。
不难发现对于第一种情况,一个网格内的黑格无法与外面连通,设有 \(x\) 个网格则答案为 \(x^{k - 1}\);对于第二种情况所有黑格都是连通的,答案是 \(1\);比较难处理的是第三种情况,这里只考虑并排放两个网格时黑格连通的情况,因为两种差不多。
这是样例一的二级分形:
图中出现了四个连通块。不难发现这是一级分形的连通块数量乘上黑格数量减去多算的连上了的连通块数量
那么设 \(f_{i}\) 表示 \(i\) 级分形有几个连通块,\(s_{i}\) 表示并排放的两个 \(i\) 级分形有几个连通块连上了,\(cnt_0\) 表示原网格中并排挨着的黑格数量,\(cnt_1\) 表示并排放的两个原网格之间并排挨着的黑格数量。
那么转移方程:
\[f_{i} = x\cdot f_{i - 1} - cnt_0 s_{i - 1}\\ s_{i} = cnt_1s_{i - 1} \]冲个矩阵快速幂。
点击查看代码