Educational Codeforces Round 7
https://codeforces.com/contest/622/problems
3/6: ABD
A. Infinite Sequence
水题
#include <bits/stdc++.h>
using namespace std;
int main () {
long long x;
cin >> x;
long long n = sqrt (2 * x), m = (n + 1) * n / 2;
//cout << m << ' ';
if (x <= m) {
cout << n - (m - x);
}
else {
cout << x - m;
}
}
B. The Time
水题
#include <bits/stdc++.h>
using namespace std;
int main () {
int hh, mm, dx;
scanf ("%d:%d", &hh, &mm);
scanf ("%d", &dx);
//cout << hh << ' ' << mm << ' ' << dx << endl;
mm += dx;
hh += mm / 60, mm %= 60, hh %= 24;
//cout << hh << ' ' << mm;
cout << setw(2) << setfill('0') << hh << ':';
cout << setw(2) << setfill('0') << mm << endl;
}
C. Not Equal on a Segment
这题思路很难想，个人想不到pos[]数组要这样做
一开始二分找，超时了
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 1e6 + 5;
int a[N], n, m;
int pos[N]; //i前面第一个相同的的下标
int main () {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
if (a[i] == a[i-1]) pos[i] = pos[i-1];
else pos[i] = i;
}
while (m --) {
int l, r, x;
scanf ("%d%d%d", &l, &r, &x);
if (a[r] != x) printf ("%d\n", r);
else {
if (pos[r] <= l) printf ("-1\n");
else printf ("%d\n", pos[r] - 1);
}
}
}
//找到[l,r]区间内不等于x的数的下标
//[1,1e6]
D. Optimal Number Permutation
非常开心！做出了一道1900
构造题，观察式子：
\(i,n\)都是固定的，所以就想一下怎么安排能够使得 \(d_i\) 的值近可能靠近 \(n-i\)。不妨设两个 \(i\) 之间的距离间隔即 \(d_i=n-i\)，则可以像下图一样构造：
（最后的 \(n\) 无论如何摆放贡献都是0，所以只需补最后一位的空即可）
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = N * 2;
int n, a[M];
int main () {
cin >> n;
for (int i = 1, j = 1; i <= n; i += 2, j++) a[j] = a[n-j+1] = i;
for (int i = 2, j = 1; i <= n; i += 2, j++) a[n+j] = a[2*n-j] = i;
a[2 * n] = n;
for (int i = 1; i <= 2 * n; i++) cout << a[i] << ' ';
}
/*
1: 1, n
2: n+1, 2*n-1
3: 2, n-1
4: n+2, 2n-2
...
*/