2023年9月18日
今天上午写了Atcoder的翻译，以后对于我这种菜鸡来说，多多少少有点用了。前两个题是贪心，第三个是BFS。
Acwing908 最大不相交区间数量
题目理解
- 全部按右端点进行排序
- 然后如果下一个点的左，比我的右端点还大，那么就肯定不在一个区间
- 然后更新目前的右端点即可
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
pair<ll, ll> q[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n ; i++)
cin >> q[i].y >> q[i].x;
sort(q, q + n);
int res = 1;
ll point = q[0].x;
for(int i = 1; i < n; i++)
{
if(q[i].y > point)
{
res++;
point = q[i].x;
}
}
cout << res;
return 0;
}
AcWing905 区间选点
题目理解
- 以右端点排序
- 每次选右端点，如果没被覆盖就要+1，并且更新端点为右端点
- 不然的就不用变了
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
pair<ll, ll> p[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
cin >> p[i].y >> p[i].x;
sort(p, p + n);
int res = 1;
int point = p[0].x;
for(int i = 1; i < n; i++)
{
if(point <= p[i].x && point >= p[i].y)
continue;
else
{
res++;
point = p[i].x;
}
}
cout << res;
return 0;
}
AcWing845 八数码
题目理解
给出九宫格，然后求如何通过最小的操作步数来得到最后的12345678x。
通过以下几步得到：
- 我们可以把每一个状态转为一个字符串存储。
- 把整个问题看成权值为1的最短路。只不过不是坐标，而是每一步的状态。
- 用map来存每一个状态的距离，用队列来存字符串（状态）进行bfs即可。
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e5;
char g[5][5];
int bfs()
{
unordered_map<string, int> mp;
queue<string> q;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
string s = "";
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
s += g[i][j];
q.push(s);
mp[s] = 0;
while(q.size())
{
string curr = q.front();
q.pop();
if(curr == "12345678x")
return mp[curr];
int x, y;
for(int i = 0; i < 9; i++)
if(curr[i] == 'x')
x = i / 3, y = i % 3;
int d = mp[curr];
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 3 || b >= 3 || b < 0) continue;
swap(curr[x * 3 + y], curr[a * 3 + b]);
if(!mp.count(curr))
{
mp[curr] = d + 1;
q.push(curr);
}
swap(curr[x * 3 + y], curr[a * 3 + b]);
}
}
return -1;
}
int main()
{
int x, y;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
cin >> g[i][j];
if(g[i][j] == 'x')
x = i, y = j;
}
cout << bfs();
return 0;
}
AtCoder ABC042 A
题目理解
只要5出现两次，7出现一次即可
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
int cnt[11];
int main()
{
ll a, b, c;
cin >> a >> b >> c;
cnt[a]++;
cnt[b]++;
cnt[c]++;
if(cnt[5] == 2 && cnt[7] == 1)
cout << "YES";
else
cout << "NO";
return 0;
}
AtCoder ABC042 B
题目理解
对字符串，排序后输出即可,因为每个字符串都要输出。那么保证每一个的开头是最小的顺序输出就是字典序最小了。
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
vector<string> v;
ll n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
v.push_back(s);
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++)
cout << v[i];
return 0;
}
AtCoder ABC042 C
题目理解
这个题目数据范围很小，我们暴力枚举从n开始的每一个答案即可。判断里面是否存在不喜欢的数。
代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
bool st[11];
ll n, k;
vector<int> a;
string s;
bool check(ll k)
{
while(k)
{
int t = k % 10;
if(st[t])
return true;
k /= 10;
}
return false;
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= k; i++)
{
int b;
cin >> b;
st[b] = true;
}
while(check(n))
n++;
cout << n;
return 0;
}