题目
Codeforces Round 690 (Div. 3) - Codeforces
Problem - A - Codeforces
方法一：模拟
思路
按题意模拟即可。
当输入序列 的长度为奇数时：
- 把 分别放在 ；
- 把 分别放在 。
当输入序列 的长度为偶数时：
- 把 分别放在 ；
- 把 分别放在 。
数组从 0 开始也差不多，改下标即可。
代码
#include <cstdio>
using namespace std;
const int N = 310;
int t, n;
int a[N];
void solve() {
scanf("%d", &n);
for (int i = 0, j = n - 1 - (n & 1); i < n; ++i) {
if (i < n / 2 + (n & 1)) scanf("%d", &a[i * 2]);
else scanf("%d", &a[j]), j -= 2;
}
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
putchar('\n');
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - B - Codeforces
方法一：模拟
思路
把 "2020" 分别拆成 "2" 和 "020" ，"20" 和 "20" ，"202" 和 "2" ，"2020"，分别在字符串头尾匹配，如果匹配成功输出 "Yes" 即可。
代码
#include <cstdio>
using namespace std;
const int N = 210;
int t, n;
char s[N];
void solve() {
scanf("%d%s", &n, s);
if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[3] == '0') {
puts("Yes");
return;
}
if (s[n - 4] == '2' && s[n - 3] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
puts("Yes");
return;
}
if (s[0] == '2' && s[n - 3] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
puts("Yes");
return;
}
if (s[0] == '2' && s[1] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
puts("Yes");
return;
}
if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[n - 1] == '0') {
puts("Yes");
return;
}
puts("No");
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - C - Codeforces
方法一：枚举 构造
思路
考虑到每位数都不能重复（且 0 对数位和没有贡献），所以最多能构造一个 9 位的数 123456789 ，也就是说无法构造出数位和 的数，如果输入的 直接输出 "-1" 即可。
构造时直接从高到低枚举每一位，从大到小枚举可以填的数（不重复）就能构造出符合条件的最小的数。
实际实现的时候可以从低位到高位枚举构造，然后反转输出即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n;
void solve() {
scanf("%d", &n);
if (n > 45) {
puts("-1");
return;
}
int ans = 0;
for (int d = 9; d >= 1; --d) {
if (d <= n) {
ans = ans * 10 + d;
n -= d;
}
}
while (ans) {
printf("%d", ans % 10);
ans /= 10;
}
putchar('\n');
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - D - Codeforces
方法一：暴力枚举
思路
这题用 的做法是可以做的。
尝试枚举第一段子数组的长度 len ，然后从 len 向后枚举之后的段，如果后面的子数组和 第一段子数组和，就说明以 为第一段的答案不存在，继续枚举 len ，如果后面的子数组和 第一段子数组和，就继续向后枚举其他段，枚举到数组结尾时就说明该答案可行。此时，若第一段子数组和为 avg ，则操作数最小值为 。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3010;
int t, n;
int a[N];
void solve() {
scanf("%d", &n);
int mx = 0, tot = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
tot += a[i];
}
int avg = 0;
for (int len = 1; len <= n; ++len) {
avg += a[len - 1];
if (avg < mx) continue;
int sum = 0;
for (int i = len; i < n; ++i) {
if (sum + a[i] < avg) sum += a[i];
else if (sum + a[i] == avg) sum = 0;
else {
sum = -1;
break;
}
}
if (sum == avg || sum == 0) {
printf("%d\n", n - (tot / avg));
return;
}
}
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - E1 - Codeforces
方法一：二分 组合数学
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int t, n;
int a[N];
int right_bound(int l, int r, int x) {
while (l < r) {
int m = l + r + 1 >> 1;
if (a[m] <= x) l = m;
else r = m - 1;
}
return r;
}
void solve() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a + n);
LL ans = 0;
for (int i = 0; i < n; ++i) {
int cnt = right_bound(i + 1, n - 1, a[i] + 2) - i;
ans += 1LL * cnt * (cnt - 1) / 2;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem - E2 - Codeforces
方法一：二分 组合数学 快速幂
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int t, n, m, k;
int a[N];
int fac[N], ifac[N];
LL kasumi(LL base, LL exp, LL mod) {
LL res = 1LL;
while (exp) {
if (exp & 1) res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
int right_bound(int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
return r;
}
LL C(int n, int m) {
if (n < m) return 0;
if (n == m) return 1;
return 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void solve() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a + n);
LL ans = 0LL;
for (int i = 0; i < n; ++i) {
int cnt = right_bound(0, n - 1, a[i] + k) - i;
ans = (ans + C(cnt, m - 1)) % MOD;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &t);
fac[0] = ifac[0] = 1;
for (int i = 1; i <= 2e5; ++i) {
fac[i] = (int) (1LL * i * fac[i - 1] % MOD);
ifac[i] = (int) kasumi(fac[i], MOD - 2, MOD);
}
while (t--) solve();
return 0;
}
Problem - F - Codeforces
方法一：离散化 树状数组
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int t, n;
PII segs[N];
int alls[N * 2];
int tr[2][N * 2];
int lowbit(int x) {
return x & -x;
}
void add(int u, int i, int x) {
for (; i <= n * 2; i += lowbit(i)) tr[u][i] += x;
}
int qry(int u, int i) {
int res = 0;
for (; i > 0; i -= lowbit(i)) res += tr[u][i];
return res;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
segs[i] = {l, r};
alls[i] = l, alls[i + n] = r;
}
sort(alls + 1, alls + n * 2 + 1);
int sz = (unique(alls + 1, alls + n * 2 + 1) - (alls + 1));
sort(segs + 1, segs + n + 1);
for (int i = 1; i <= sz; ++i) tr[0][i] = tr[1][i] = 0;
for (int i = 1; i <= n; ++i) {
segs[i].fi = lower_bound(alls + 1, alls + sz + 1, segs[i].fi) - alls;
segs[i].se = lower_bound(alls + 1, alls + sz + 1, segs[i].se) - alls;
}
for (int i = 1; i <= n; ++i) {
add(1, segs[i].fi, 1);
}
int mx = 0;
for (int i = 1; i <= n; ++i) {
const int& l = segs[i].fi, & r = segs[i].se;
int lc = qry(0, sz) - qry(0, l - 1);
int rc = qry(1, r) - qry(1, l - 1);
int cnt = lc + rc;
mx = max(mx, cnt);
add(1, l, -1);
add(0, r, 1);
}
printf("%d\n", n - mx);
}
int main() {
scanf("%d", &t);
while (t--) solve();
return 0;
}
评论区