# Before
[本文章在博客园同步发布]()
[Contest-Link](https://www.luogu.com.cn/contest/137474)
预期 $100 + 100 + 5 + 0 = 205$。
实际 $0+100(0)+5+0=105(5)$。（括号是重测前）
挂分 $200$。
rk21，直接垫底。~~菜死了~~
为什么会挂 $200$ 呢？且听下文分解。
# T1
## Description
求 $[l, r]$ 中 $2$ 的幂。
输入一行两个整数 $l$ 和 $r$。
**输出第一行一个整数** $\mathbf{cnt}$ **表示区间里** $\mathbf{2}$ **的幂的个数**，第二行输出这些数。
$0 \le l \le r \le 10^6$。
## Solution
直接开个标记数组标记不超过范围的 $2$ 次幂，这里可以直接用 `pow`，然后 $O(n)$ 扫一遍即可。
当然也可以 $O(\log n)$ 判是否在范围内就输出。
`Q:` 那你为什么保龄了？
`A:` 没有输出上文 `Description` 中加粗的输入中的 $\text{cnt}$。因为读题不仔细痛失 $\text{100pts}$。
考场想法：模拟。
考场寄因：如上。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。
## Code
$\text{100pts:}$
```cpp
// 2023/10/5 PikachuQAQ
#include <iostream>
#include <cmath>
using namespace std;
int l, r, b[3000000], cnt;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> l >> r;
for (int i = 0; i <= 20; i++) {
int x = pow(2, i);
b[x] = 1;
}
for (int i = l; i <= r; i++) {
cnt += b[i];
}
cout << cnt << '\n';
for (int i = l; i <= r; i++) {
if (b[i]) {
cout << i << ' ';
}
}
return 0;
}
```
$\text{0pts:}$
```cpp
// 2023/10/5 PikachuQAQ
#include <iostream>
#include <cmath>
using namespace std;
int l, r, b[3000000];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> l >> r;
for (int i = 0; i <= 20; i++) {
int x = pow(2, i);
b[x] = 1;
}
for (int i = l; i <= r; i++) {
if (b[i]) {
cout << i << ' ';
}
}
return 0;
}
```
# T2
## Description
给定 $n$ 个字符串组成字典，然后进行 $q$ 次查询，每次给出一个字符串问字典中是否存在与其编辑距离为 $1$ 的串。
输入一行两个整数 $n$ 和 $q$，接下来 $n$ 行，$n$ 个字符串表示字典，接下来 $q$ 行，$q$ 个字符串，每给出一个字符串表示一次询问。
输出 $q$ 行，每行一个字符串，如果字典中有符合条件的字符串，输出这个字符串，如果有多个输出在字典中下标最小的那个。如果没有条件的字符串输出 **`No`**。
$1 \le n \le 50$，$1 \le q \le 50$，$1 \le len \le 20$，其中 $len$ 为任意一个单词的长度，单词仅由小写字母构成。
## Solution
开题 `20min` 首先写了个字典树，但发现~~字典树不会写了~~数据范围很小，所以可以直接暴力增删改，然后直接匹配即可。亦可以直接字典树，但比较麻烦。
`Q:` 那你为什么保龄了？
`A:` 没有输出上文 `Description` 中加粗的输出 `No`，我输出了 `NO`。因为读题不仔细又痛失 $\text{100pts}$。哈哈。
考场想法：暴力匹配。
考场寄因：如上。
时间复杂度 $O(qn^2\times len)$，带 $26$ 的常数，空间复杂度 $O(n)$。
## Code
$\text{100pts:}$
```cpp
// 2023/10/5 PikachuQAQ
#include <iostream>
using namespace std;
const int kMaxN = 57, INF = 100;
int n, q;
string a[kMaxN], b;
string substr(string s, int l) {
string res = "";
for (int i = 0; i < s.length(); i++) {
if (i ^ l) {
res += s[i];
}
}
return res;
}
string insert(string s, int x, char c) {
string res = "";
int r = s.length() + (x == s.length());
for (int i = 0; i < r; i++) {
if (i ^ x) {
res += s[i];
} else {
res += c;
if (i < s.length()) {
res += s[i];
}
}
}
return res;
}
int match(string a, string b) {
if (a == b) {
return 0;
}
string f = b;
int ln = b.length();
for (int i = 0; i <= ln; i++) {
for (int j = 'a'; j <= 'z'; j++) {
f = insert(f, i, j);
if (f == a) {
return 1;
}
f = b;
}
}
for (int i = 0; i < ln; i++) {
if (substr(f, i) == a) {
return 1;
}
}
for (int i = 0; i < ln; i++) {
for (int j = 'a'; j <= 'z'; j++) {
f[i] = j;
if (f == a) {
return 1;
}
}
f = b;
}
return -1;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1, sol; i <= q; i++) {
cin >> b;
for (int j = 1; j <= n; j++) {
if (match(a[j], b) != -1) {
sol = 1;
cout << a[j] << '\n';
break;
}
}
if (sol == 0) {
cout << "No\n";
}
sol = 0;
}
return 0;
}
```
$\text{0pts:}$
```cpp
// 2023/10/5 PikachuQAQ
#include <iostream>
using namespace std;
const int kMaxN = 57, INF = 100;
int n, q;
string a[kMaxN], b;
string substr(string s, int l) {
string res = "";
for (int i = 0; i < s.length(); i++) {
if (i ^ l) {
res += s[i];
}
}
return res;
}
string insert(string s, int x, char c) {
string res = "";
int r = s.length() + (x == s.length());
for (int i = 0; i < r; i++) {
if (i ^ x) {
res += s[i];
} else {
res += c;
if (i < s.length()) {
res += s[i];
}
}
}
return res;
}
int match(string a, string b) {
if (a == b) {
return 0;
}
string f = b;
int ln = b.length();
for (int i = 0; i <= ln; i++) {
for (int j = 'a'; j <= 'z'; j++) {
f = insert(f, i, j);
if (f == a) {
return 1;
}
f = b;
}
}
for (int i = 0; i < ln; i++) {
if (substr(f, i) == a) {
return 1;
}
}
for (int i = 0; i < ln; i++) {
for (int j = 'a'; j <= 'z'; j++) {
f[i] = j;
if (f == a) {
return 1;
}
}
f = b;
}
return -1;
}
int main() {
freopen("dict.in", "r", stdin);
freopen("dict.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1, sol; i <= q; i++) {
cin >> b;
for (int j = 1; j <= n; j++) {
if (match(a[j], b) != -1) {
sol = 1;
cout << a[j] << '\n';
break;
}
}
if (sol == 0) {
cout << "No\n";
}
sol = 0;
}
return 0;
}
```
# T3
## Description
## Solution
## Code
# T4
## Description
## Solution
## Code
# Summary
**需要掌握的：仔细读题**。
标签：总结,10,return,string,int,res,cin,##,模拟 From： https://www.cnblogs.com/Accepted100pts/p/10-5-contest-ji-yin.html