目录
比赛链接:
A - Candy Button
题目链接:
题目描述:
数据范围:
输入样例:
输出样例:
样例解释:
分析:
代码:
B - Hands on Ring (Easy)
题目链接:
题目描述:
数据范围:
输入样例:
输出样例:
样例解释:
分析:
代码:
C - Prepare Another Box
题目链接:
题目描述:
数据范围:
输入样例:
输出样例:
样例解释:
分析:
代码:
D - Cycle
题目链接:
题目描述:
数据范围:
输入样例:
输出样例:
样例解释:
分析:
代码:
比赛链接:
AtCoder Beginner Contest 376 - AtCoder
A - Candy Button
题目链接:
A - Candy Button (atcoder.jp)
题目描述:
数据范围:
输入样例:
6 5
1 3 7 8 10 12
输出样例:
3
样例解释:
分析:
模拟,用一个变量记录上一次收到糖果的时间,然后对比当前这个时刻,他们这两个时间段的差,有没有满足条件。注意的是:第一次是可以直接拿的。
代码:
#include<bits/stdc++.h>
#define int long long using namespace std;signed main() {int n, m;cin >> n >> m;int ret = 0;int a[n + 10];
// a[0] = -1;int last = -1;for(int i = 1; i <= n; i ++ ) {cin >> a[i];if(last == -1) {last = a[i];ret ++;} else {if(a[i] - last >= m ) {ret ++ ;last = a[i];}}}cout << ret << endl;return 0;
}
B - Hands on Ring (Easy)
题目链接:
B - Hands on Ring (Easy) (atcoder.jp)
题目描述:
数据范围:
输入样例:
6 3
R 4
L 5
R 6
输出样例:
8
样例解释:
分析:
无脑打的暴力。这个运算次数最后是固定的,先试着顺时针一次,看看行不行(L和R会不会碰撞),要是顺时针撞的话,那么逆时针就一定不会装。
需要注意的是:
顺时针的时候,会转到大于n的,每一步走的时候,先去判断有没有大于n,大于n的时候让其更改为1。
逆时针的时候,会转到小于1,每一步走的时候,先去判断有没有小于1,小于1的时候让其更改为n。
代码:
#include<bits/stdc++.h>
#define int long longusing namespace std;signed main() {int n, t;cin >> n >> t;int l = 1, r = 2, ret = 0;while(t -- ) {string s;int pos;cin >> s >> pos;if(s == "L") {// L要移动bool flag = true;int p = 0;for(int j = l; ; j ++ ) {if(j > n) {j = 1; // 循环回来 }if(j == pos) {break;}if(j == r) {flag = false;break;}p ++ ; } if(flag) {ret += p;} else {// 反着来for(int j = l; ; j -- ) {// cout << "j = " << j << " pos = " << pos << endl; if(j == 0) {j = n;}if(j == pos) {break;}ret ++ ;} //ret += (n - pos + l);}l = pos; // 更新位置 } else {// R要移动bool flag = true;int p = 0;for(int j = r; ; j ++ ) {if(j > n) {j = 1; // 循环回来 }if(j == pos) {break;} if(j == l) {flag = false;break;}p ++ ;} if(flag) {ret += p;} else {for(int j = r; ; j -- ) {if(j == 0) {j = n;}if(j == pos) {break;}ret ++ ;}}r = pos;}//cout << "ret = " << ret << endl;}cout << ret << endl;return 0;
}
C - Prepare Another Box
题目链接:
C - Prepare Another Box (atcoder.jp)
题目描述:
给你n个玩具,n-1个盒子,让你把n-1个玩具放到盒子里面,剩下的一个最小是多少?
数据范围:
输入样例:
4
5 2 3 7
6 2 8
输出样例:
3
样例解释:
分析:
贪心,先让玩具和盒子从小到大排序。
然后从后往前,把玩具放到箱子(箱子也是从后往前放),这样把大的放进去,那么剩下的就是相对较小的了,答案的值也小。放到不能发(也就是第一个不能放的),然后再从前往后开始放,因为你从右往左第一个放不了的玩具,对应的第一个放不了的箱子的前面依然放不了。这第一个放不了的玩具可能就是最后的答案,为什么是可能呢?因为这个玩具的左边并不一定都能放到箱子里,要试一下能不能放,不能的话输出-1,否则的话输出第一个放不了的玩具的大小即可。
对样例的模拟:
先排序,都按照从小到大排序。
从右边往左开始尝试放玩具,看看是哪一个开始断开的(放不了的)。 样例1,从右往左第一个放不了的是2号玩具(大小是3)
上图可知,3可能是最后的答案。
从左往右看看在[1, 2-1]的这些玩具能不能都能放?发现是可以的,那么答案就是3.
当然也存在不可以的,比如:
2 3 5 7
1 6 8
代码:
#include<bits/stdc++.h>
#define int long longusing namespace std;signed main() {int n;cin >> n;int a[n + 10];int b[n + 10];for(int i = 1; i <= n; i ++ ) {cin >> a[i]; // 玩具 }for(int i = 1; i <= n - 1; i ++ ) {cin >> b[i]; // 盒子 }sort(a + 1, a + n + 1);sort(b + 1, b + n - 1 + 1);// 先拍后 int r = n - 1;for(; r >= 1; r -- ) {if(b[r] < a[r + 1]) {break;}//cout << "r = " << r << endl;}r ++ ;// [r, n - 1]是可以的int l = 1;
// cout << "l = " << l << " r = " << r << endl;for(; l < r; l ++ ) {if(b[l] < a[l]) {// cout << "!!!";break;}//cout << "l = " << l << endl;} l--;//cout << "l = " << l << " r = " << r << endl;// [1, l]是可以的if(r - l != 1) {cout << -1 << endl;} else {cout << a[l + 1] << endl;}return 0;
}
D - Cycle
题目链接:
D - Cycle (atcoder.jp)
题目描述:
数据范围:
输入样例:
3 3
1 2
2 3
3 1
输出样例:
3
样例解释:
分析:
板子题:bfs(队列)(queue)
用ret[i] 表示i到1的最短距离,其中ret[1] = 0。只要队列里面还有就要一直去更新,因为你不知道当前的ret[1] 是不是最小的。第一次更新ret[1]的时候要去直接更新,其余更新ret[1]的时候,就要ret[1] = min(ret[1], ret[j] + 1);其余的节点只有最小的时候才去更新,最有被更新的点才放到队列里面,下一次去更新其他的点。最后,如果ret[1] = 0,就表示1节点没被更新过,就不会存在环,因此输出-1.
代码:
#include<bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;vector<int>v[n + 10];bool flag = false;for(int i = 1; i <= m; i ++ ) {int x, y;cin >> x >> y;v[x].push_back(y);if(y == 1) {flag = true;}}if(!flag) {cout << -1 << endl;return 0;}int ret[n + 10];memset(ret, 0x3f, sizeof ret);ret[1] = 0;queue<int>q;q.push(1);bool p = false;while(q.size()) {int d = q.front();//cout << "d = " << d << endl;q.pop();for(int i = 0; i < v[d].size(); i ++ ) {int j = v[d][i];//cout << "j = " << j << endl;if(ret[j] > ret[d] + 1 || j == 1) {if(j == 1) {if(p == false) {ret[j] = ret[d] + 1;p = true;} else {ret[j] = min(ret[j], ret[d] + 1);}} else {ret[j] = ret[d] + 1;}q.push(j);}// cout << "ret[j] = " << ret[j] << endl;} }cout << (ret[1] == 0 ? -1 : ret[1] ) << endl;return 0;
}