比赛传送门
总结
\(100+60+0+0=160\)，Rank 16，寄寄寄寄寄。
T1 优秀 \(\texttt{/}\) \(\texttt{Good}\)
题意
求 \(l\) 和 \(r\) 之间的 \(2\) 的整数次幂。
分析
解法 1
由于 \(l\) 和 \(r\) 非常小，所以可以直接模拟，没啥好说的。
时间复杂度 \(O(r)\)。
解法 2
充分发扬人类智慧，发现肯定只有 \(2^{\left \lceil \log_2 l \right \rceil}\) 到 \(2^{\lfloor \log_2 r \rfloor}\) 这些数，循环输出就行了。
时间复杂度 \(O(\log_2 r)\)。
寄因
没寄。
\(\color{red}\text{不要忘记输出 cnt！！！}\)
\(\color{red}\text{不然……}\)
\(\color{red}{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\!↑}\)
\(\color{red}{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \!}没有输出\ cnt\ 的皮卡丘\)
代码
自己写吧，这么简单。
解法 1
#include <bits/stdc++.h>
using namespace std;
int l, r;
vector<int> a;
int main() {
cin >> l >> r;
int logl = log2(l);
for (int i = 1 << logl; i <= r; i <<= 1) {
if (i >= l) {
a.push_back(i);
}
}
cout << a.size() << '\n';
for (int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
return 0;
}
解法 2
#include <bits/stdc++.h>
using namespace std;
int l, r;
vector<int> a;
int main() {
cin >> l >> r;
int logl = ceil(log2(l)), logr = floor(log2(r));
for (int i = 1 << logl; i <= 1 << logr; i <<= 1) {
a.push_back(i);
}
cout << a.size() << '\n';
for (int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
return 0;
}
T2 词典 \(\texttt{/}\) \(\texttt{dict}\)
题意
超级强化版
正常题意
给定 \(n\) 个字符串 \(s\)，\(q\) 次询问，每次询问给定一个字符串 \(t\)，问能否进行以下操作最多一次将 \(t\) 变成任意的 \(s\)，输出那个 \(s\)（保证唯一）；否则输出 No：
-
在 \(t\) 中删除一个字母；
-
在 \(t\) 中插入一个字母；
-
在 \(t\) 中修改一个字母。
分析
数据范围很小，所以 unordered_map / map 模拟一下就行了，当然你想用 trie 也没人拦着你。
时间复杂度 \(O(\sum |t|)\)，\(|t|\) 为字符串 \(t\) 的长度。
寄因
忘记判在最后加上字符的情况。
代码
#include <bits/stdc++.h>
using namespace std;
int n, q;
unordered_map<string, bool> dict;
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
dict[s] = 1;
}
for (int i = 1; i <= q; i++) {
string s;
cin >> s;
bool f = 1;
int l = s.size();
// -----------------------相等--------------------
if (dict[s]) {
cout << s << '\n';
continue;
}
// -------------------删去一个字符-----------------
for (int i = 0; i < l; i++) {
string s_ = s.substr(0, i) + s.substr(i + 1);
// cout << s_ << '\n';
if (dict[s_]) {
cout << s_ << '\n';
f = 0;
break;
}
}
// -------------------加上一个字符-----------------
for (char i = 'a'; i <= 'z'; i++) {
for (int j = 0; j <= l; j++) {
string s_ = s.substr(0, j) + i + s.substr(j);
// cout << s_ << '\n';
if (dict[s_]) {
cout << s_ << '\n';
f = 0;
break;
}
}
}
// -------------------修改一个字符-----------------
for (char i = 'a'; i <= 'z'; i++) {
for (int j = 0; j < l; j++) {
string s_ = s;
s_[j] = i;
// cout << s_ << '\n';
if (dict[s_]) {
cout << s_ << '\n';
f = 0;
break;
}
}
}
if (f) {
cout << "No\n";
}
}
return 0;
}
T3 积木 \(\texttt{/}\) \(\texttt{block}\)
题意
现在搭了 \(n\) 列积木，第 \(i\) 列已经搭好的积木高 \(h_i\) 个，在 \(a_{i, j}\) 加上一个积木需要满足 \(a_{i - 1, j}, a_{i, j - 1}, a_{i + 1, j - 1}\) 都已经搭好了，求加上 \(m\) 块积木最大的高度，即 \(\max {h'}_i\)。
\(\texttt{p.s:}\ 1 \le n \le 10^5, 1 \le m \le 10^9\)。
分析
看了这个数据范围，一眼顶针，望月身亡的，二分 \(m\)，然后 \(O(n)\) 的 \(\operatorname{check}\)，