目录
写在前面
比赛地址：https://codeforces.com/contest/1976
妈的昨晚硬撑打了场 edu 上午实验下午爬山考试困困困
妈的什么二进制场，C 吃了个爽呃呃写得什么史山
A
二进制。
一个显然的想法是选择区间 \([l, r]\) 中质因数次数之和最大的数。
特别指出了限制 \(2l < r\)，即区间 \([l, r]\) 中一定有至少一个 2 的幂，则显然最好的选择是 \(x=2^{\log_{2}^{r}}\)，答案即为 \(\log_2 r\)。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int l, r; std::cin >> l >> r;
std::cout << (int) log2(r) << "\n";
}
return 0;
}
B
二进制。
上来就打表的话可能会误入歧途。
首先手玩下容易发现，询问 \((n, m)\) 的结果即为 \(\max(0, n - m) \sim n + m\) 的二进制或。那么如何求得一段连续区间 \([l, r]\) 的二进制或呢？
考虑将区间看做一个从 \(l\) 开始不断加 1 直至 \(r\) 的变量，首先取上两端点 \(l, r\) 的贡献，然后可以发现其他贡献均来自于进位。若出现累加后进位 \(2^{i}\) 说明末尾 \(i\) 位变为了连续的 1，此时末尾的 \(i+1\) 位均会产生贡献，值为 \(2^{i + 1} - 1\)。
于是问题变为如何找到最高位的进位，显然有 \(l\) 中该位为 0，\(r\) 中该位为 1，于是仅需找到 \(l\oplus r\)（\(\oplus\) 为按位异或运算）中最高位即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
const int kN = 1e5 + 10;
int a[kN], b[kN];
//=============================================================
LL get(int n_, int m_) {
int l = std::max(0, n_ - m_), r = n_ + m_, ret = l | r;
for (int i = 30; i >= 0; -- i) {
int val = (1 << i);
if (val & (l ^ r)) {
ret |= (val | (val - 1));
break;
}
}
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n, m; std::cin >> n >> m;
if (m == 0) std::cout << n << "\n";
else std::cout << get(n, m) << "\n";
}
return 0;
}
C
二进制，构造，二叉树。
先特判下整个数列均为 -1 的情况，直接构造 1 2 1 2 ... 即可。然后发现 \(a'_i \not= i\) 的位置实际上将原数列分为了若干互不影响的段，仅需考虑如何构造每段 \([l, r]\)。
保证了 \(a_i\le 10^8 < \frac{10^9}{2}\)，于是第一段和最后一段分别构造为 \(\cdots a_{l}, 2\times a_{l}, a_{l}\) 和 \(a_{r}, 2\times a_r, a_r \cdots\) 即可。考虑其他的有两个端点 \(a_l, a_r\) 限制的段如何构造。
先直接特判掉长度为 2 的段是否合法。
发现一种很重要的特殊情况是 \(a_{l} = a_{r}\)，此时仅需检查区间长度的奇偶性即可判断是否有解，若有解仅需构造 \(a_l, 2\times a_l, a_l, \cdots, a_r, 2\times a_r, a_r\) 即可。
然后考虑一般情况。一个显然的想法是分别从两端 \(l, r\) 开始向内构造，找到某个位置 \(p\) 使得从两端开始构造在此处的元素相等。发现对于已知的 \(x\)，若元素 \(y\) 与它可以相邻，则一定是下列三种情况之一：
- \(y = \left\lfloor\frac{x}{2}\right\rfloor\)，由 \(x\) 删去二进制最后一位得到。
- \(y = 2\times x\)，由 \(x\) 在二进制最后添加 0 得到。
- \(y = 2\times x + 1\)，由 \(x\) 在二进制最后添加 1 得到。
显然从两端开始构造时，比较好的方案是首先不断进行第一种构造，删去 \(a_l, a_r\) 的末位直至两者出现公共前缀后，才可以使用另外两种构造。此时即可套用 \(a_l = a_r\) 的做法了。
实现时可以先对 \(a_l, a_r\) 进行二进制分解，对二进制串求最长公共前缀即可。如果在此过程中出现该段不够长的情况，或套用 \(a_l = a_r\) 做法时出现奇偶性不合法的则无解。
上述做法需要对 \(O(n)\) 数量级的元素进行二进制分解，总时间复杂度上界 \(O(n\log v)\) 级别。
实际上述做法还可以简化，并不需要限定删去 \(a_l, a_r\) 的末位直至两者出现的公共前缀一定是最长公共前缀。可以分别从两端开始一直删直到 1，并考虑此时构造了多少位出来。若构造的位数大于区间总长仅需把多余的忽略，若不足区间总长再套用 \(a_l = a_r\) 做法。
特别的，因为没有最小化删去数量并判断奇偶性，需要最后再枚举构造出的数列检查合法性。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
const int kLim = 1e9;
//=============================================================
int n, a[kN], ans[kN];
//=============================================================
std::string get(int val_) {
// if (val_ >= kLim || val_ <= 0) while(1);
std::string s;
while (val_) {
s.push_back(val_ % 2 + '0');
val_ /= 2;
}
std::reverse(s.begin(), s.end());
return s;
}
bool solve(int l_, int r_) {
ans[l_] = a[l_], ans[r_] = a[r_];
if (l_ == 0 && r_ == n + 1) {
for (int i = 1; i <= n; ++ i) {
if (i % 2 == 1) ans[i] = 1;
else ans[i] = 2;
}
return true;
} else if (l_ == 0) {
for (int i = r_ - 1; i; -- i) {
if ((r_ - i) % 2 == 1) ans[i] = 2 * ans[i + 1];
else ans[i] = ans[i + 1] / 2;
}
return true;
} else if (r_ == n + 1) {
for (int i = l_ + 1; i < r_; ++ i) {
if ((i - l_) % 2 == 1) ans[i] = 2 * ans[i - 1];
else ans[i] = ans[i - 1] / 2;
}
return true;
}
if (r_ == l_ + 1) return (a[l_] / 2 == a[r_]) || (a[r_] / 2 == a[l_]);
int logl = (int) log2(a[l_]), logr = (int) log2(a[r_]), d = abs(logr - logl);
if (d > r_ - l_) return false;
if ((r_ - l_) % 2 != d % 2) return false;
if (ans[l_] != ans[r_]) {
int maxlen = 0;
std::string sl = get(a[l_]), sr = get(a[r_]);
for (int i = 0; i < std::min(logl, logr) + 1; ++ i) {
if (sl[i] != sr[i]) break;
++ maxlen;
}
for (int i = 1; i <= logl - maxlen + 1 && l_ <= n; ++ i) {
++ l_, ans[l_] = ans[l_ - 1] / 2;
}
for (int i = 1; i <= logr - maxlen + 1 && r_; ++ i) {
-- r_, ans[r_] = ans[r_ + 1] / 2;
}
if (l_ > r_) return false;
}
for (int i = l_ + 1; i < r_; ++ i) {
if ((i - l_) % 2 == 1) ans[i] = 2 * ans[i - 1];
else ans[i] = ans[i - 1] / 2;
}
return true;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
int lst = 0, flag = 1;
for (int i = 1; i <= n; ++ i) {
if (a[i] == -1) continue;
flag &= solve(lst, i);
lst = i;
}
flag &= solve(lst, n + 1);
if (!flag) std::cout << -1 << "\n";
else {
for (int i = 1; i <= n; ++ i) std::cout << ans[i] << " ";
std::cout << "\n";
}
}
return 0;
}
D
构造，数论。
妈的好诡异的题拿到这题我都不知道我要干啥呃呃
写在最后
参考：
学到了什么：
- A：特别指出的反常限制————有诈！
- B：考虑贡献来自于什么过程。
- C：从二进制角度考虑。