(A-D)AtCoder Beginner Contest 376

目录

比赛链接：

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;
}