Educational Codeforces Round 74
2024-08-27 04:15:26
目录
Contest Info
[Practice Link](https://codeforces.com/contest/1238)
| Solved | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 6/7 | O | O | O | O | Ø | Ø | - |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Prime Subtraction
签到。
B. Kill 'Em All
签到。
C. Standard Free2play
贪心即可。
代码：
view code
#include <bits/stdc++.h>
#define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n"
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 2e5 + 10;
int h, n, a[N];
void run() {
cin >> h >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n == 1) return pt(0);
int res = 0, lst = h;
for (int i = 2; i <= n; ++i) {
if (lst <= a[i]) continue;
lst = a[i] + 1;
if (i == n) {
if (lst >= 3) ++res;
break;
}
if (lst - a[i + 1] >= 3) {
++res;
lst = a[i + 1] + 1;
} else {
lst = a[i + 1];
}
}
pt(res);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout << fixed << setprecision(20);
int _T; cin >> _T;
while (_T--) run();
return 0;
}
D. AB-string
题意：
给出一个字符串\(S\)，其字符集只有'A', 'B'，现在统计有多少个子串是符合要求的，一个子串是符合要求的当且仅当其中每个字符都属于一个长度大于\(1\)的回文子串中。
思路：
考虑符合要求的串的长度肯定大于等于\(2\)，那么只有一种字符是符合要求的。
再考虑，枚举每个左端点，找多少个右端点是符合的。
首先\(AB\)是不符合的，但是\(ABA\)，并且后面不管加什么字符都是符合的。
那么\(AAAABA\)后面不管加什么字符都是符合的。
对于首字母是\(B\)的同理考虑即可。
代码：
view code
#include <bits/stdc++.h>
#define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n"
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 3e5 + 10;
int n; char s[N];
vector <int> A, B;
void run() {
cin >> (s + 1);
A.clear(); B.clear();
for (int i = 1; i <= n; ++i) {
if (s[i] == 'A') A.push_back(i);
else B.push_back(i);
}
ll res = 0;
for (int i = 1; i < n; ++i) {
if (s[i] == 'A') {
auto nx = upper_bound(B.begin(), B.end(), i);
if (nx == B.end()) {
res += (n - i);
} else if (*nx == i + 1) {
auto nnx = upper_bound(A.begin(), A.end(), *nx);
if (nnx != A.end()) {
res += n - *nnx + 1;
}
} else {
res += n - i - 1;
}
} else {
auto nx = upper_bound(A.begin(), A.end(), i);
if (nx == A.end()) {
res += n - i;
} else if (*nx == i + 1) {
auto nnx = upper_bound(B.begin(), B.end(), *nx);
if (nnx != B.end()) {
res += n - *nnx + 1;
}
} else {
res += n - i - 1;
}
}
}
pt(res);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout << fixed << setprecision(20);
while (cin >> n) run();
return 0;
}
E. Keyboard Purchase
题意：
给出一个字符串\(S\)，现在要造一个键盘，这个键盘只有一排键，要敲打这段字符串\(S\)，花费是：
\[\begin{eqnarray*}
\sum\limits_{i = 2}^n |pos_{s_{i - 1}} - pos_{s_i}|
\end{eqnarray*}
\]
\sum\limits_{i = 2}^n |pos_{s_{i - 1}} - pos_{s_i}|
\end{eqnarray*}
\]
现在问最小代价，在选择合适的键盘下，键盘上键位是自定的。
思路：
我们考虑拆绝对值，那么对于两个相邻的\((a, b)\)，那么我们只需要关心\(pos_a\)是在\(pos_b\)的前面还是后面即可，这样就确定了绝对值中的符号。
那么用\(f[i][j]\)表示前\(i\)个位置，选择的字符二进制状态为\(j\)的最小代价。
那么只需要考虑\(f[i][S]\)转移到\(f[i + 1][S \cup \{v\}] for\;v \notin S\)
代码：
view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n"
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 1e5 + 10;
int n, m, w[30][30], f[1 << 21], g[1 << 21][22], num[1 << 21], lg[1 << 21]; char s[N];
void run() {
cin >> (s + 1);
memset(w, 0, sizeof w);
for (int i = 1; i < n; ++i) {
int c = s[i] - 'a', c2 = s[i + 1] - 'a';
if (c == c2) continue;
++w[c][c2];
++w[c2][c];
}
int lim = 1 << m;
memset(g, 0, sizeof g);
for (int i = 1; i < lim; ++i) {
for (int j = 0; j < m; ++j) {
int lb = i & -i;
g[i][j] = g[i ^ lb][j] + w[j][lg[lb]];
}
}
memset(f, 0x3f, sizeof f); f[0] = 0;
for (int i = 0; i < lim; ++i) {
for (int j = 0; j < m; ++j) {
if (!((i >> j) & 1)) {
int pos = num[i] + 1;
chmin(f[i ^ (1 << j)], f[i] + g[i][j] * pos - g[(lim - 1) ^ i ^ (1 << j)][j] * pos);
}
}
}
pt(f[lim - 1]);
}
int main() {
memset(num, 0, sizeof num);
for (int i = 1; i < 1 << 20; ++i)
num[i] = num[i ^ (i & -i)] + 1;
memset(lg, 0, sizeof lg);
lg[0] = -1; lg[1] = 0;
for (int i = 2; i < 1 << 20; i <<= 1) lg[i] = lg[i >> 1] + 1;
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout << fixed << setprecision(20);
while (cin >> n >> m) run();
return 0;
}
F. The Maximum Subtree
题意：
定义一张图是合法的当且仅当，每个点表示一个一维数轴上的线段的时候，两个点有边当且仅当他们表示的线段有交集。
现在给出一棵树，问最多选择多少个点构成的子树是合法的。
思路：
多\(wa\)几发就可以发现一个点如果之和父亲有边，那么这种点是随便加的。
那么对于一个点如果它和儿子连了边，那么它要和其父亲连边，那么其父亲最多连这样的点两个，并且其父亲是根。
然后再用每个点的子树的最大值更新答案。
代码：
view code
#include <bits/stdc++.h>
#define debug(...) { printf("# "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n"
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 3e5 + 10;
int n, f[N], rt, res;
vector <vector<int>> G;
void dfs(int u, int fa) {
int Max[2] = {0, 0};
int sons = 0;
for (auto &v : G[u]) {
if (v == fa) continue;
++sons;
dfs(v, u);
if (f[v] > Max[0]) {
swap(Max[0], Max[1]);
Max[0] = f[v];
} else if (f[v] > Max[1]) Max[1] = f[v];
}
if (u != rt) {
f[u] = Max[0] + 1 + max(0, sons - 1);
chmax(res, Max[0] + Max[1] + 1 + max(0, sons - 1));
} else {
f[u] = Max[0] + Max[1] + 1 + max(0, sons - 2);
chmax(res, f[u]);
}
}
void run() {
cin >> n;
memset(f, 0, sizeof (f[0]) * (n + 10));
G.clear(); G.resize(n + 1);
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
rt = 1; res = 0;
for (int i = 2; i <= n; ++i) {
if (G[i].size() > 1) {
rt = i;
break;
}
}
dfs(rt, rt);
pt(res);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout << fixed << setprecision(20);
int _T; cin >> _T;
while (_T--) run();
return 0;
}
最新文章
- 多预览小图焦点轮播插件lrtk
- workflow createPath
- ThinkPHP魔术方法
- 配置 AEM CQ6 (author + publish + apache dispatcher + ubuntu )
- SQL 删除存在于A表但是不存在B表中的记录
- Dynamic Web Project创建及版本修改的问题
- 升级iOS10之后调用摄像头/麦克风等硬件程序崩溃闪退的问题
- SelectList
- query specified join fetching, but the owner of the fetched association was not present in the select list
- SCI写作经典替换词，瞬间高大上！(转)
- 在线CRC校验
- Matplotlib中文显示的问题
- redis-dump安装与导出redis数据
- AtCoder Regular Contest 102 E Stop. Otherwise...
- html5-textarea元素
- 关于这次安装Oracle
- Spark笔记之使用UDF（User Define Function）
- WSAEventSelect模型编程 详解
- 解决nginx下不能require根目录以外的文件
- B-spline Curves 学习之B样条基函数计算实例（3）