AtCoder Beginner Contest 224
A – Tires
思路分析:
- 判断最后一个字符即可。
代码如下:
#include
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
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 > a[i][j];
}
}
bool flag = 0;
for (int i = 1; i < h; i++)
{ //i1
for (int j = i + 1; j 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
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 > 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
D – 8 Puzzle on Graph
思路分析:
- 比赛的时候看这题题目一直没看懂,最后十多分钟看懂了(要队友给我说了一遍题意)但是当时没有想法,最后十分钟发现数据范围可以暴力,但是没来得及写。
- 题目的意思就是先给出一个无向图,然后有八个块,每个块的序号和他所在的顶点序号不同,最后要你通过把块转移操作(块可以转移到没有块的顶点上),最后要使得每个块的序号和顶点序号一样,求需要多少次块转移操作,如果不能转移到要求的结果,输出-1。
- 首先我们要转换一下,转换成第(i)个顶点在第(j)块,并且用块(9)表示为空,比如第一个样例我们转换后就是931456782。然后我们要使得它变成123456789,我们就可以使用BFS来解决这题,我们把当前为空块顶点相连的边的块全部都转移一次,然后存到队列里,用队列解决问题,用map来储存答案。
代码如下:
#include
using namespace std;
const int maxn = 50;
vector e[maxn];
map 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 > u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i > x;
s[x - 1] = i + '0';
}
mp[s] = 0;
queue q;
q.push(s);
while (!q.empty())
{
string s = q.front();
q.pop();
int u = 0;
for (int i = 1; i
E – Integers on Grid
思路分析:
- 这题看题解的,但是题解很长还是英文,有点难看懂。
- 我直接讲做法吧,我们先把值对应到一个向量中,这样的话其实值在map里面已经排好序了,然后反向遍历map,这样可以使得我们当前拿到的是一个最大值,因为只有这样我们能保证正确性,因为只有比所选数小才能通过移动到达这个值,然后对于最大值他的答案肯定是(0),然后对于和他同一行同一列的元素来说,答案一个就是得到的值加1和之前算出来的答案比较得到的最大值。
- 状态转移其实就是(dp[i] = max(当前行的最大值,当前列的最大值))。
- (当前行的最大值 = max(dp[i] + 1,之前算出的最大值))。
- (当前列的最大值 = max(dp[i] + 1,之前算出的最大值))。
代码如下:
#include
using namespace std;
const int maxn = 2e5 + 10;
map> 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 > 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
Original: https://www.cnblogs.com/csu-yuuki/p/15451087.html
Author: zhy-cx
Title: AtCoder Beginner Contest 224
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/713417/
转载文章受原作者版权保护。转载请注明原作者出处!