A. Little Artem
题意
有一 $n{ imes}m$ 网格，输出一种使得 与白色相邻的黑色格数 = 与黑色相邻的白色格数 $+ 1$ 的染色方案。
思路
一角染白。
代码
#include <bits/stdc++.h> using namespace std; void solve() { int n, m; cin >> n >> m; char mp[n][m]; fill(*mp, *mp + n * m, 'B'); mp[0][0] = 'W'; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << mp[i][j] ; } cout << " "; } } int main() { int t; cin >> t; while (t--) solve(); }
B. Kind Anton
题意
数组 $a$ 由 ${-1,0,1}$ 组成，可以使 $a_i$ 加上左侧 $a_j$ 任意次，问数组 $a$ $b$ 能否相等。
思路
判断每个与 $b_i$ 不等的 $a_i$ 左侧是否有满足条件的 $a_j$，即记录最左侧的 $-1 / 1$ 。
代码
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int a[n]; for(int & i : a) cin>>i; int b[n]; for(int & i : b) cin>>i; int l_1 = find(a, a + n, -1) - a; int l1 = find(a, a + n, 1) - a; for (int i = 0; i < n; i++) { if ((b[i] > a[i] && l1 >= i) || (b[i] < a[i] && l_1 >= i)) { cout << "NO" << " "; return; } } cout << "YES" << " "; } int main() { int t; cin >> t; while (t--) solve(); }
C. Eugene and an array
题意
统计数组 $a$ 中有多少连续子序列，其本身及其连续子序列的和均不为 $0$ 。
思路
将数组从 $[0,n-1]$ 编号，若存在一和为 $0$ 的连续子序列 $[i,j]$，则 $pre\_sum[i-1] = pre\_sum[j]$，此 $0$ 序列与之前的 $i$ 个数共构成 $i+1$ 个 $0$ 序列，将之后的每个数接在 $0$ 序列的末尾也都会再构成 $i+1$ 个 $0$ 序列，若之后仍有 $0$ 序列，更新已知 $0$ 序列的最大长度后就又变成了和之前一样的情况。
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; map<ll, ll> MP; int main() { int n; cin >> n; int a[n]; for (int & i : a) cin >> i; MP[0] = 0; ll r = -1, sum = 0, ans = (n + 1LL) * n / 2; for (int i = 0; i < n; i++) { sum += a[i]; if (MP.count(sum)) r = max(r, MP[sum]); ans -= r + 1; MP[sum] = i + 1; } cout << ans; }
D. Challenges in school №41
题意
输出用 $k$ 轮将字符串中所有的 $RL$ 翻转成 $LR$ 的任一方案。
思路
$min_k$ = 每轮翻转串中所有已存在 $RL$ 需要的轮数，$max_k$ = 每轮翻转一个 $RL$ 需要的轮数，如果 $k$ 位于二者之间则一定有解，当 $k=min_k$ 时逐轮输出即可，当 $k>min_k$ 时需要将一些轮分解输出直至 $k = min_k - used_k$ 。
代码
#include <bits/stdc++.h> using namespace std; const int MAX_N = 3030; vector<int> v[MAX_N]; int n, k, min_k, max_k; char s[MAX_N]; int main() { cin >> n >> k >> (s + 1); while (1) { bool flag = true; for (int i = 1; i <= n; i++) { if (s[i] == 'R' && s[i + 1] == 'L') { v[min_k].push_back(i); flag = false; } } for (int i : v[min_k]) swap(s[i], s[i + 1]); max_k += v[min_k].size(); if (flag) break; ++min_k; } if (k < min_k || k > max_k) { cout << "-1"; return 0; } for (int i = 0; i < min_k; i++) { while (!v[i].empty() && k > min_k - i) { cout << "1 " << v[i].back() << " "; v[i].pop_back(); --k; } if (!v[i].empty()) { cout << v[i].size(); for (int j : v[i]) cout << ' ' << j; cout << " "; --k; } } }
F. Kate and imperfection
题意
有一集合 $S={1,2,3,...,n}$，构造大小为 $k(1<k≤n)$ 的集合，使得两两数间 $gcd$ 的最大值最小并输出该最小值。
思路
我们考虑如何构造两两间最大公因数的最大值最小的集合，首先肯定是把所有质数先丢进集合里，然后再把与已经在集合内的数的最大公因数 =2 的数丢进去，然后是 =3 的数……然后注意到，如果我们加入了一个合数，那么他的所有因子必定已经在集合内了，于是加入的这个数字能够产生的最大公因数就是他的最大因子，因此用埃筛维护这个贪心的过程，排序一遍输出即可。——st1vdy
代码
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> ans(n + 1, 1); for (int i = 2; i <= n; i++) { for (int j = i + i; j <= n; j += i) { ans[j] = i; } } sort(ans.begin(), ans.end()); for (int i = 2; i <= n; i++) cout << ans[i] << ' '; }
参考了： st1vdy 的博客。