AtCoder Beginner Contest 236题解
文章目录
A - chukodai
【题目链接】A - chukodai (atcoder.jp)
题意：交换字符串s中某两个位置的字符，然后求新串
【代码实现】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string s;
cin >> s;
int a, b;
cin >> a >> b;
swap(s[a - 1], s[b - 1]);
cout << s;
return 0;
}
B - Who is missing?
【题目链接】B - Who is missing? (atcoder.jp)
题意：1~n中每一个数有4个，其中缺少了一个，找出缺少的那一个数。
题解：哈希表统计每个数出现的次数，不为n的数即为缺少的那个数。
【代码实现】
#include <iostream>
#include <cstring>
#include <algorithm>
#include<unordered_map>
using namespace std;
int main()
{
int n;
cin >> n;
unordered_map<int, int> s;
for(int i = 1; i <= (4 * n - 1); i ++)
{
int x;
cin >> x;
s[x] ++;
}
for(int i = 1; i <= n; i ++)
{
if(s[i] != 4)
{
cout << i;
break;
}
}
return 0;
}
C - Route Map
【题目链接】C - Route Map (atcoder.jp)
题意：火车除了起点终点站要停车自外，途径的站点同时也是高铁站点它也要停。
题解：只要火车站点含有高铁站点，那么该站要停车。因此在遍历时，判断存储高铁站的集合是否包含火车站点即可！可以用STL操作。
【代码实现】
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#include<unordered_map>
using namespace std;
int main()
{
int n, m;
string s;
cin >> n >> m;
vector<string> list1;
for(int i = 1; i <= n; i ++)
{
cin >> s;
list1.push_back(s);
}
// 只要普通车站包含高铁站点，就会停，因此高铁站可以用set存储
set<string> list2;
for(int i = 1; i <= m; i ++)
{
cin >> s;
list2.insert(s);
}
for(auto c : list1)
{
if(list2.count(c)) puts("Yes");
else puts("No");
}
return 0;
}
D - LR insertion
【题目链接】D - Dance (atcoder.jp)
题意：两个组队，开心值异或，求最大开心值。
题解：由于N很小，因此可以dfs暴力枚举。注意一些特判和边界。
【代码实现】
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int a[20][20];
bool st[20];
LL ans = -1e18;
int n;
//dfs爆搜判断每种情况
void dfs(int u, LL val)
{
if(u > (2*n - 1))// 递归出口
{
ans = max(ans, val);
return ;
}
if(st[u])// 在同一行（自己组队不可能！）
{
dfs(u + 1, val);
return ;
}
for(int j = u + 1; j <= 2*n; j ++)
{
if(!st[j])
{
st[j] = true;
dfs(u + 1, val ^ a[u][j]);
st[j] = false;
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i < 2*n; i ++)
for(int j = i + 1; j <= 2*n; j ++)
scanf("%d", &a[i][j]);
dfs(1, 0);// 任何一个数和0异或都为它本身
printf("%lld", ans);
return 0;
}
后面的二分和dp，这些是真的不熟悉，以后在补E题了，QAQ…
注：如果文章有任何错误或不足，请各位大佬尽情指出，评论留言留下您宝贵的建议！如果这篇文章对你有些许帮助，希望可爱亲切的您点个赞推荐一手，非常感谢啦