目录
Contest InfoSolutions A. Prime MinisterB. WOW FactorC. TilesD. Prime GraphE. ArchaeologyF1. Short Colorful StripPractice Link
SolvedABCDEF1F2GH6/9OOOOOØ--- O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到题。
#include <bits/stdc++.h> using namespace std; #define N 110 int n, a[N], b[N]; int main() { while (scanf("%d", &n) != EOF) { memset(b, 0, sizeof b); int sum = 0, other = 0; for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum += a[i]; b[1] = 1; other = a[1]; for (int i = 2; i <= n; ++i) { if (a[1] >= a[i] * 2) { other += a[i]; b[i] = 1; } } if (other > sum / 2) { int sze = 0; vector <int> vec; for (int i = 1; i <= n; ++i) { if (b[i]) { ++sze; vec.push_back(i); } } printf("%d\n", sze); for (int i = 0; i < sze; ++i) printf("%d%c", vec[i], " \n"[i == sze - 1]); } else { puts("0"); } } return 0; }题意： 将连续的两个\(v\)可以看成一个\(w\)，询问给出的字符串中只包含字符\(v\)和\(o\)，询问有多少个子序列组成\(wow\)
思路： 先处理出每个\(o\)左边有多少个\(w\)以及右边有多少个\(w\)，然后计算贡献即可。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 1000010 int n; ll l[N], r[N]; char s[N]; int main() { while (scanf("%s", s + 1) != EOF) { n = strlen(s + 1); l[0] = 0; for (int i = 1; i <= n; ++i) { l[i] = l[i - 1]; if (i > 1 && s[i] == 'v' && s[i - 1] == 'v') { ++l[i]; } } r[n + 1] = 0; for (int i = n; i >= 1; --i) { r[i] = r[i + 1]; if (i < n && s[i] == 'v' && s[i + 1] == 'v') { ++r[i]; } } ll res = 0; for (int i = 1; i <= n; ++i) { if (s[i] == 'o') { res += 1ll * l[i - 1] * r[i + 1]; } } printf("%lld\n", res); } return 0; }题意： 有这样的瓷砖： 用来拼\(n \cdot m\)的地板，要求任意相邻的边两边的颜色不能相同。
思路： 显然第一个位置可以有四种选择，并且第一排的后面的每个位置都有两种选择，因为不能和前面的边相同。 那么第一列后面的位置也有两种选择，那么剩下的位置都只有一种选择，因为它们相邻了两条边。 所以答案就是\(4 \cdot 2^{n + m - 2}\)
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long const ll p = 998244353; ll qmod (ll base, ll n) { ll res = 1; while (n) { if (n & 1) { res = res * base % p; } base = base * base % p; n >>= 1; } return res; } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { printf("%lld\n", qmod(2, n - 1) * qmod(2, m - 1) % p * 4 % p); } return 0; }题意： 给出\(n\)个点，要求构成一个简单图，使得边的总数是素数，并且每个点的度数也是素数。
思路：
首先考虑每个点的度数至少为\(2\)，那么先把这些点连成一个环，所有点的度数就是\(2\)了。再考虑边的数量是素数，一个显然的想法是所有数都可以表示成\(2x + 3y\)的形式，所以我们将环中的点分成两部分，每次各取一个点连边，就增加一条边，并且让两个度数为\(2\)的点变成度数为\(3\)的。那么只要满足我们找一个\(>= n\)的最近的素数\(y\)，使得\(y - n \leq \frac{n}{2}\)即可这样构造。素数的密度很高，或者\(n\)只有\(1000\)可以打表验证一下，这样是可以的。代码：
#include <bits/stdc++.h> using namespace std; #define N 1010 #define pii pair <int, int> #define fi first #define se second int n; bool isprime(int x) { for (int i = 2; i < x; ++i) { if (x % i == 0) return 0; } return 1; } int main() { while (scanf("%d", &n) != EOF) { int tot = n; for (int i = tot; ; ++i) { if (isprime(i)) { tot = i; break; } } vector <pii> vec; for (int i = 2; i <= n; ++i) vec.push_back(pii(i - 1, i)); vec.push_back(pii(1, n)); int remind = tot - n; int pos = n / 2 + 1; for (int i = 1; i <= remind; ++i) { vec.push_back(pii(i, pos)); ++pos; } printf("%d\n", tot); for (auto it : vec) printf("%d %d\n", it.fi, it.se); } return 0; }题意： 给出一个只包含'a', 'b', 'c'的字符串，保证任意两个连续的字符都不相同，要求选出一个子序列\(t\)使得它是一个回文串，并且\(|t| \geq \left\lfloor \frac{|s|}{2} \right\rfloor\)
思路： 贪心从两端取即可。 因为左端的两个字符和右端的两个字符，必然会有两个相等，因为保证了任意两个连续的字符不同，那么这样就是说每\(4\)个字符，至少有\(2\)个有贡献，显然满足题目限制。 其实也可以枚举一样，看看： 假如左端的\(ab\)，那么右端的取值有以下几种：
\(ab\)\(ac\)\(bc\) 显然都满足要求。代码：
#include <bits/stdc++.h> using namespace std; #define N 1000010 #define INF 0x3f3f3f3f int n, m, f[N][3], g[N][3], nx[3]; char s[N], t[N]; int vis[N]; bool ok() { m = 0; for (int i = 1; i <= n; ++i) if (vis[i]) { t[++m] = s[i]; } t[m + 1] = 0; if (m >= n / 2) { printf("%s\n", t + 1); return 1; } return 0; } int main() { while (scanf("%s", s + 1) != EOF) { n = strlen(s + 1); for (int i = 1; i <= n; ++i) vis[i] = 0; nx[0] = nx[1] = nx[2] = 0; for (int i = 1; i <= n + 1; ++i) { for (int j = 0; j < 3; ++j) { g[i][j] = nx[j]; } if (i <= n) { nx[s[i] - 'a'] = i; } } nx[0] = nx[1] = nx[2] = n + 1; for (int i = n; i >= 0; --i) { for (int j = 0; j < 3; ++j) { f[i][j] = nx[j]; } if (i > 0) { nx[s[i] - 'a'] = i; } } int l = 0, r = n + 1; while (l <= r) { int Min = INF, pos = -1; for (int i = 0; i < 3; ++i) { if (f[l][i] < g[r][i] && f[l][i] - l + r - g[r][i] < Min) { Min = f[l][i] - l + r - g[r][i]; pos = i; } } if (pos == -1) break; l = f[l][pos]; r = g[r][pos]; vis[l] = vis[r] = 1; } if (l < r - 1) { vis[l + 1] = 1; } if (!ok()) printf("IMPOSSIBLE\n"); } return 0; }题意： 有一个长度为\(n\)的方格纸，现在要求做\(n\)次涂刷操作，每次选择一个区间将其刷成颜色\(i\)，刚开始全都为颜色\(0\)，问最后方格纸上第\(i\)格颜色为\(c_i\)的方案数。\(n = m\)。
思路： 令\(f[l][r]\)表示完成区间\([l, r]\)的涂刷的方案数。 考虑对于一个区间\([l, r]\)，那么我们第一次涂的肯定是\(c_i\)最小的，然后以\(c_i\)最小的那个格子为界，划分成两边，令\(pos[i]\)表示当前区间\(c_i\)最小的格子的下标，那么有转移方程：\[ \begin{eqnarray*} f[l][r] = \sum\limits_{a} \sum\limits_{b} f[l][a - 1] \cdot f[a][pos[i] - 1] \cdot f[pos[i] + 1][i - 1] \cdot f[i +1][r] \end{eqnarray*} \] 注意到划分出两个区间后，左边右边独立，所以可以分开计算，最后乘起来即可。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 510 const ll p = 998244353; int n, m, a[N]; ll f[N][N]; void add(ll &x, ll y) { x += y; if (x >= p) x -= p; } ll dp(int l, int r) { if (l > r) return 1; if (f[l][r] != -1) return f[l][r]; if (l == r) return f[l][r] = 1; f[l][r] = 0; int pos = l; for (int i = l + 1; i <= r; ++i) { if (a[i] < a[pos]) pos = i; } ll L = dp(l, pos - 1), R = dp(pos + 1, r); for (int i = l; i < pos; ++i) { add(L, dp(l, i) * dp(i + 1, pos - 1) % p); } for (int i = pos + 1; i <= r; ++i) { add(R, dp(pos + 1, i) * dp(i + 1, r) % p); } return f[l][r] = L * R % p; } int main() { while (scanf("%d%d", &n, &m) != EOF) { memset(f, -1, sizeof f); for (int i = 1; i <= n; ++i) scanf("%d", a + i); printf("%lld\n", dp(1, n)); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11220155.html
