比赛地址:AtCoder Beginner Contest 313 - AtCoder
后记:请正确理解题意后再做题!!!
A - To Be Saikyo
每个人有一个数值,问第一个人要加多少才能使得自己的数值变成最大的。
就这么个破题我还 WA 了一发
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 110;
int n, maxx, cnt;
int p[N];
int main() {
n = read<int>();
for (int i = 1; i <= n; ++ i) {
p[i] = read<int>();
if (maxx == p[i]) {
++ cnt;
} else {
maxx = max(maxx, p[i]);
cnt = 1;
}
}
sort(p + 2, p + n + 1, greater<int>());
if (p[2] < p[1]) {
puts("0");
} else {
cout << p[2] - p[1] + 1 << '\n';
}
return 0;
}
B - Who is Saikyo?
B - Who is Saikyo? (atcoder.jp)
给你一些关系 \((a, b)\),代表 \(a\) 比 \(b\) 强。问最强的人,无法判断则输出 \(-1\)。
判断入度为 \(0\) 的点的个数即可。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int n, m, maxx;
int in[100];
int main() {
n = read<int>(), m = read<int>();
for (int i = 1, a, b; i <= m; ++ i) {
cin >> a >> b;
++ in[b];
}
for (int i = 1; i <= n; ++ i) {
if (!in[i]) {
if (maxx) {
puts("-1");
return 0;
}
maxx = i;
}
}
cout << maxx << '\n';
return 0;
}
C - Approximate Equalization 2
C - Approximate Equalization 2 (atcoder.jp)
有一个操作,选择最大的数和最小的数,然后最小的数加一,最大的数减一,问最少操作多少次,可以使得最大的数和最小的数差值最大是 \(1\)。
求商和余数,有多少个余数就代表有多少个数只到达商 \(+ 1\) 的位置。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2e5 + 5;
ll sum, ans;
ll a[N];
int main() {
int n = read<int>();
for (int i = 1; i <= n; ++ i) {
a[i] = read<ll>();
sum += a[i];
}
sort(a + 1, a + n + 1);
ll res = sum % n, zc = sum / n;
for (int i = 1; i <= n - res; ++ i) {
ans += abs(zc - a[i]);
}
for (int i = n - res + 1; i <= n; ++ i) {
ans += abs(a[i] - zc - 1);
}
cout << ans / 2 << '\n';
return 0;
}
D - Odd or Even
这是一道交互题,本人是第一次做这种新题型。
题目大意:有一个序列 \(A\),每一个元素只可能是 \(0\) 或者 \(1\),现在,你可以从中任选 \(k\) 个位置,通过询问这 \(k\) 个位置的数它们的和的奇偶性,来判断每个元素是 \(0\) 还是 \(1\)。
对于前 \(k + 1\) 个数,我们一共选 \(k + 1\) 次,第 \(i\) 次空出第 \(i\) 个位置,计算出这些数的奇偶性,再依次异或,来得出前 \(k + 1\) 个数的奇偶性,后面的数只要把最后一个数换掉即可。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1010;
int n, k;
int ans[N];
void out(vector<int> x) {
int siz = x.size();
for (int i = 0; i < siz; ++ i) {
cout << x[i] << " \n"[i + 1 == siz];
}
}
int main() {
n = read<int>(), k = read<int>();
auto send = [&](vector<int> v) {
for (int &x : v) {
++ x;
}
cout << "? ";
out(v);
cout.flush();
int x;
x = read<int>();
return x;
};
vector<int> ans(n);
int r = 0;
for (int i = 0; i < k + 1; ++ i) {
vector<int> v;
for (int j = 0; j < k + 1; ++ j) {
if (i != j) {
v.emplace_back(j);
}
}
ans[i] = send(v);
r ^= ans[i];
}
for (int i = 0; i < k + 1; ++ i) {
ans[i] ^= r;
}
vector<int> v(k);
int s = 0;
for (int i = 0; i < k - 1; ++ i) {
v[i] = i;
s ^= ans[i];
}
for (int i = k + 1; i < n; ++ i) {
v.back() = i;
int t = send(v);
ans[i] = s ^ t;
}
cout << "! ";
out(ans);
cout.flush();
return 0;
}
E 的题目……说实话,没读懂……
- Beginner AtCoder Contest 报告 313beginner atcoder contest 313 beginner atcoder contest报告 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315