AtCoder Beginner Contest 224
A - Tires
思路分析：
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
string temp;
if (s[s.size() - 1] == 'r')
{
cout << "er" << endl;
}
else
{
cout << "ist" << endl;
}
return 0;
}
B - Mongeness
思路分析：
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 60;
int a[maxn][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= w; j++)
{
cin >> a[i][j];
}
}
bool flag = 0;
for (int i = 1; i < h; i++)
{ //i1
for (int j = i + 1; j <= h; j++)
{ //i2
for (int k = 1; k < w; k++)
{ //j1
for (int x = k + 1; x <= w; x++)
{ //j2
int x1 = a[i][k] + a[j][x];
int x2 = a[j][k] + a[i][x];
if (x1 > x2)
{
flag = 1;
break;
}
else
continue;
}
if (flag)
break;
}
if (flag)
break;
}
if (flag)
break;
}
if (flag)
{
cout << "No" << endl;
}
else
cout << "Yes" << endl;
return 0;
}
C - Triangle?
思路分析：
- 在坐标系随便取三个点，如果这三个点不在同一条直线上，那么必然组成一个三角形，所以只需要判断哪三个点在同一条直线上减去即可,然后数据范围决定可以暴力。
- 注意如何判断是否在同一条直线，我用的是斜率但是要改成乘法（因为会有0）。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500;
int x[maxn], y[maxn];
const double eps = 1e-6;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];
}
long long ans = n * (n - 1) * (n - 2) / (3 * 2);
for (int i = 1; i < n - 1; i++)
{
//1
for (int j = i + 1; j < n; j++)
{
//2
for (int k = j + 1; k <= n; k++)
{
//3
int x1 = x[i], y1 = y[i];
int x2 = x[j], y2 = y[j];
int x3 = x[k], y3 = y[k];
if (x3 * y2 - x1 * y2 - x3 * y1 == x2 * y3 - x2 * y1 - x1 * y3)
ans--;
}
}
}
cout << ans << endl;
return 0;
}
D - 8 Puzzle on Graph
思路分析：
- 比赛的时候看这题题目一直没看懂，最后十多分钟看懂了（要队友给我说了一遍题意）但是当时没有想法，最后十分钟发现数据范围可以暴力，但是没来得及写。
- 题目的意思就是先给出一个无向图，然后有八个块，每个块的序号和他所在的顶点序号不同，最后要你通过把块转移操作（块可以转移到没有块的顶点上），最后要使得每个块的序号和顶点序号一样，求需要多少次块转移操作，如果不能转移到要求的结果，输出-1。
- 首先我们要转换一下，转换成第\(i\)个顶点在第\(j\)块，并且用块\(9\)表示为空，比如第一个样例我们转换后就是931456782。然后我们要使得它变成123456789，我们就可以使用BFS来解决这题，我们把当前为空块顶点相连的边的块全部都转移一次，然后存到队列里，用队列解决问题，用map来储存答案。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50;
vector<int> e[maxn];
map<string, int> mp;
int main()
{
string s = "999999999";
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= 8; i++)
{
int x;
cin >> x;
s[x - 1] = i + '0';
}
mp[s] = 0;
queue<string> q;
q.push(s);
while (!q.empty())
{
string s = q.front();
q.pop();
int u = 0;
for (int i = 1; i <= 9; i++)
{
if (s[i - 1] == '9')
{
u = i;
}
}
for (auto x : e[u])
{
string t = s;
swap(t[u - 1], t[x - 1]);
//每一个相邻的边都操作一次
if (mp.count(t))
continue;
//出现过了
mp[t] = mp[s] + 1;
q.push(t);
}
}
if (mp.count("123456789") == 0)
{
cout << -1 << endl;
}
else
{
cout << mp["123456789"] << endl;
}
return 0;
}
E - Integers on Grid
思路分析：
- 这题看题解的，但是题解很长还是英文，有点难看懂。
- 我直接讲做法吧，我们先把值对应到一个向量中，这样的话其实值在map里面已经排好序了，然后反向遍历map，这样可以使得我们当前拿到的是一个最大值，因为只有这样我们能保证正确性，因为只有比所选数小才能通过移动到达这个值，然后对于最大值他的答案肯定是\(0\)，然后对于和他同一行同一列的元素来说，答案一个就是得到的值加1和之前算出来的答案比较得到的最大值。
- 状态转移其实就是\(dp[i] = max(当前行的最大值,当前列的最大值)\)。
- \(当前行的最大值 = max(dp[i] + 1,之前算出的最大值)\)。
- \(当前列的最大值 = max(dp[i] + 1,之前算出的最大值)\)。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
map<int, vector<int>> mp;
int r[maxn];
int c[maxn];
int val[maxn];
int dp[maxn];
int rmax[maxn];
int cmax[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int h, w, n;
cin >> h >> w >> n;
for (int i = 1; i <= n; i++)
{
cin >> r[i] >> c[i] >> val[i];
mp[val[i]].push_back(i);
}
for (auto it = mp.rbegin(); it != mp.rend(); it++)
{
for (auto i : it->second)
{
dp[i] = max(rmax[r[i]], cmax[c[i]]);
}
for (auto i : it->second)
{
rmax[r[i]] = max(rmax[r[i]], dp[i] + 1);
cmax[c[i]] = max(cmax[c[i]], dp[i] + 1);
}
}
for (int i = 1; i <= n; i++)
{
cout << dp[i] << endl;
}
return 0;
}