8月13日题目（w
_Cloud_
2020-08-14 00:40:10
- 写在前面：
受朋友之约，加上自己早就想写一篇关于每天做的题目的解析（方便自己找找思路），于是就有了这篇文章。（看前警告：作者文笔不好，语句不畅请谅解）
------------
## 1. 找a+b=c(add)
[题目链接](https://www.luogu.com.cn/problem/U126961)
此题介绍两种方法，一种是暴力枚举，另一种是优化的暴力枚举。
1. 暴力枚举：
将A集合的每个元素与B集合每个元素相加得到 $N^2$ 个答案记录在桶 $T_i$
中，最后在进行每次 $O(1)$ 判断输出。 时间复杂度： $O(N*M*Q)$。
## $Code$
```cpp
#include <cstdio>
bool t[200005];
int a[10005], b[10005];
int main() {
// freopen("add.in", "r", stdin);
// freopen("add.out", "w", stdout);
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
t[a[i] + b[j]] = true;
}
}// 将每个可能值放入桶T里
for (int i = 1; i <= q; i++) {
int qu;
scanf("%d", &qu);
if (t[qu] == true)
printf("Yes\n");
else
printf("No\n");//O(1)判断
}
return 0;
}
```
2. 优化的枚举：
这次我们换一个思路来枚举，依然是用桶来记数值，但是这次用到两个桶 $T1, T2$ 来记录每个集合的元素，然后在每个 $q$ 输入时再枚举。 时间复杂度：$O(N^2 * Q)$ 这个的时间复杂度就小于上面的方法了（这是最差情况，上面是每次的固定复杂度）。
## $Code$
```cpp
#include <cstdio>
const int N=100005;
bool a[N], b[N];
void in(int &x){
char c=getchar();
while (c<'0' || c>'9') c=getchar();
for (x=0; c>='0' && c<='9'; c=getchar())
x=x*10+c-'0';
}
int main(){
//freopen("add.in","r",stdin);
//freopen("add.out","w",stdout);
int n, m, q, x;
scanf("%d %d %d", &n, &m, &q);
for (int i=0; i<n; i++) {
in(x); //scanf("%d", &x);
a[x]=1;
}
for (int i=0; i<m; i++) {
in(x); //scanf("%d", &x);
b[x]=1;
} //两个桶记录
while (q--){
in(x); //scanf("%d", &x);
bool ok=0;
for (int i=1; !ok && i<N && i<x; i++)
if (a[i] && x-i<N && b[x-i])
ok=1;//枚举所有可能的A集合元素
puts(ok ? "Yes" : "No");
}
return 0;
}
```
------------
## 2. 字符串变换(convert)
[题目链接](https://www.luogu.com.cn/problem/U126963)
这道题目就是W老师最爱的贪心结论题（自己瞎取得名字）。
那他怎么贪？结论又是什么呢？
分析：只要把最小的放在前面就可以保证字典序最小了（易证）。
我们定义两个数组，cnt和flag，分别记录这个字符有没有出现过和这个字符在$flag[i]$ 之前有没有出现过。（具体见代码）
## $Code$
```cpp
#include <cstdio>
char s[100005];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%s", s + 1);
int flag[27] = {0}, cnt[27] = {0}, a = -1, b = -1;
for (int i = 1; s[i]; i++)
cnt[s[i] - 'a' + 1]++;//记录每个字母在s中出现多少次， a,b表示要交换两字母。
for (int i = 1; s[i]; i++)
{
flag[s[i] - 'a' + 1] = 1;
if (a != -1)
break;//如果a取到值了，那么表示有一对互换的
if (s[i] == 'a')
continue;
else
{
for (int j = 1; j < s[i] - 'a' + 1; j++)
{
if (cnt[j] && !flag[j])
{
a = s[i] - 'a' + 1, b = j;
break;
}
}
}
}
if (a == -1)
puts(s + 1);
else
{
for (int i = 1; s[i]; i++)
{
if (s[i] - 'a' + 1 == a)
s[i] = b + 'a' - 1;
else if (s[i] - 'a' + 1 == b)
s[i] = a + 'a' - 1;
}
puts(s + 1);
}
}
return 0;
}
```
PS:今天先写到这吧，困死我了