Codeforces Round 970 (Div.3)

本文主要是介绍Codeforces Round 970 (Div.3)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

A. Sakurako's Exam

模拟，两个 2 能够自己变成 0，因此将 b 对 2 取余；多余的 2 还能跟两个 1 组合在一起变成 0；最后判断剩余的 1 的数量是奇数还是偶数。

#include <bits/stdc++.h>
using namespace std;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int main() {int t = read();while (t--) {int a = read(), b = read();b %= 2;while (a >= 2 && b) {a -= 2;b--;} if (b || (a % 2 == 1)) puts("NO");else puts("YES");}return 0;
}

B. Square or Not

首先，n 必须是一个完全平方数。为了实现起来较为简单，可以先构造一个期望的矩阵，再将矩阵转换成对应的字符串，最后判断该字符串是否与输入的字符串一致。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
string s, str;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}void solve() {int n = read();cin >> s;str = "";int num = sqrt(n);if (num * num < n) { puts("No"); return; }char a[num + 5][num + 5];for (int i = 1; i <= num; i++)for (int j = 1; j <= num; j++) a[i][j] = '0';for (int i = 1; i <= num; i++) a[1][i] = a[num][i] = a[i][1] = a[i][num] = '1';for (int i = 1; i <= num; i++)for (int j = 1; j <= num; j++) str += a[i][j];if (s == str) puts("Yes");else puts("No");
}int main() {int t = read();while (t--) {solve();}return 0;
}

C. Longest Good Array

题目要求的数列是数列本身单调递增，并且数列的差单调递增。要使数列最长，就要使数列的差尽可能的小，那么构造出来数列的差一定是 1，2，...，n。数列的第一位是 $l$ ，最后一位是 $l + \frac{n(n + 1)}{2}$ 。所以一定要满足 $l + \frac{n(n + 1)}{2} \le r$ ，即 $\frac{n(n + 1)}{2} \le r - l$ 。

我们只需要二分 n，n + 1 即为最大长度。

#include <bits/stdc++.h>
using namespace std;#define int long longinline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int solve() {int x = read(), y = read();int l = 1, r = y - x, ans = 0;while (l <= r) {int mid = l + r >> 1;if (mid * (mid + 1) / 2 <= y - x) ans = mid, l = mid + 1;else r = mid - 1;}return ans;
}signed main() {int t = read();while (t--) {printf("%lld\n", solve() + 1);}return 0;
}

D. Sakurako's Hobby

可以将该问题抽象成一张图，利用图论的知识完成。

如果 i 不等于 p[i]，那么我们建一条由 i 指向 p[i] 的有向边（可能会有环）。
进行拓扑排序，由于图中可能会有环，所以无法得到全部节点的答案。
我们很容易发现，同一个环中的每一个节点答案都是一样的，利用 dfs 将同一个环中的所有节点存入一个 vector 中并且记录该环的答案，再将答案填到对应节点。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
int n, p[N], f[N], head[N], in[N], vis[N], num = 0, sum;
string s;
struct edge { int to, nxt; } e[N];
vector<int> circle;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}void addEdge(int u, int v) { e[++num] = (edge){v, head[u]}, head[u] = num, in[v]++; }void dfs(int u) {circle.push_back(u); vis[u] = 1;if (s[u] == '0') sum++;for (int i = head[u], v; i; i = e[i].nxt) {v = e[i].to;if (!vis[v]) dfs(v);}
}int main() {int t = read();while (t--) {n = read();num = 0;for (int i = 1; i <= n; i++) p[i] = read(), head[i] = in[i] = vis[i] = f[i] = 0;for (int i = 1; i <= n; i++) {if (i != p[i]) addEdge(i, p[i]);}cin >> s;s = " " + s;queue<int> q;for (int i = 1; i <= n; i++) {if (!in[i]) q.push(i), vis[i] = 1;}while (!q.empty()) {int u = q.front(); q.pop();if (s[u] == '0') f[u]++;for (int i = head[u], v; i; i = e[i].nxt) {v = e[i].to; in[v]--;f[v] += f[u];if (!in[v] && !vis[v]) q.push(v), vis[v] = 1;}}for (int i = 1; i <= n; i++) {if (!vis[i]) {circle.clear();sum = 0;dfs(i);for (int j = 0; j < circle.size(); j++) f[circle[j]] = sum;}}for (int i = 1; i <= n; i++) {printf("%d", f[i]);if (i < n) putchar(' ');else putchar('\n');}}return 0;
}

F. Sakurako's Box

暴力求出所有乘积，最后利用乘法逆元得出结果。

#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 2e5 + 10, mod = 1e9 + 7;
int n, pre[N], a[N], P, Q;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int qpow(int x, int k) {int res = 1LL;while (k) {if (k & 1) res = res * x % mod;x = x * x % mod;k >>= 1;}return res % mod;
}signed main() {int t = read();while (t--) {n = read();for (int i = 1; i <= n; i++) a[i] = read(), pre[i] = (pre[i - 1] + a[i]) % mod;Q = (n * (n - 1) / 2) % mod, P = 0;for (int i = 1; i <= n; i++) P = (P + a[i] * pre[i - 1] % mod) % mod;printf("%lld\n", qpow(Q, mod - 2) * P % mod);}return 0;
}

这篇关于Codeforces Round 970 (Div.3)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！