A - ab
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
for( int i = 1 ; i < n ; i ++ ){
if( s[i] == 'a' and s[i-1] == 'b' ) {
cout << "Yes\n";
return 0;
}else if( s[i] == 'b' and s[i-1] == 'a' ){
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
B - A^A
b = int(input())
a = 1
while (a ** a) < b:
a += 1
if (a ** a) == b:
print(a)
else:
print(-1)
C - Number Place
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
int power(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = ans * x;
x = x * x, y /= 2;
}
return ans;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n = 9;
vector a(n, vi(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++) {
set<int> vis;
for (int j = 0; j < n; j++)
vis.insert(a[i][j]);
if (vis.size() != n) {
cout << "No\n";
return 0;
}
}
for (int i = 0; i < n; i++) {
set<int> vis;
for (int j = 0; j < n; j++)
vis.insert(a[j][i]);
if (vis.size() != n) {
cout << "No\n";
return 0;
}
}
for (int i = 0; i < n; i += 3) {
for (int j = 0; j < n; j += 3) {
set<int> vis;
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++)
vis.insert(a[i + x][j + y]);
if (vis.size() != n) {
cout << "No\n";
return 0;
}
}
}
cout << "Yes\n";
return 0;
}
D - Good Tuple Problem
赛时的思考还是有些欠缺,一看到这道题,就直接抄了个 2-SAT 的板子,结果还 wa 了一发。
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9;
int N;
vector<vi> e;
vi dfn, inStk, low, scc;
int cnt, sc;
stack<int> stk;
void tarjan(int x) {
low[x] = dfn[x] = ++cnt;
inStk[x] = 1, stk.push(x);
for (auto y: e[x]) {
if (!dfn[y]) {
tarjan(y), low[x] = min(low[x], low[y]);
} else if (inStk[y]) {
low[x] = min(low[x], dfn[y]);
}
}
if (low[x] == dfn[x]) {
sc++;
for (int y; true;) {
y = stk.top(), stk.pop();
inStk[y] = 0, scc[y] = sc;
if (x == y) break;
}
}
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(m + 1), b(m + 1);
for (int i = 1; i <= m; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
N = n * 2 + 2;
e = vector<vi>(N);
dfn = inStk = low = scc = vi(N);
for (int i = 1; i <= m; i++) {
if (a[i] == b[i]) {
cout << "No\n";
return 0;
}
e[2 * a[i]].push_back(2 * b[i] + 1);
e[2 * a[i] + 1].push_back(2 * b[i]);
}
for (int i = 2; i <= n * 2 + 1; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i++) {
if (scc[i * 2] == scc[i * 2 + 1]) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
其实认真思考后,发现符合条件的情况一定是二分图的,所以直接进行黑白染色就好了。
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
using ldb = long double;
const int inf = 1e9;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vi> e(n);
vector<int> a(m), b(m);
for (auto &i: a) cin >> i, i--;
for (auto &i: b) cin >> i, i--;
for (int i = 0; i < m; i++)
e[a[i]].push_back(b[i]), e[b[i]].push_back(a[i]);
vi v(n + n, -1);
auto dfs = [&v, e](auto &&self, int x, int w) -> void {
for (auto y: e[x]) {
if (v[y] == -1) {
v[y] = w ^ 1, self(self, y, v[y]);
} else if (v[y] == w) {
cout << "No\n";
exit(0);
}
}
};
for (int i = 0; i < n; i++) {
if (v[i] >= 0) continue;
v[i] = 0;
dfs(dfs, i, 0);
}
cout << "Yes\n";
return 0;
}
当然也可以用判定二分图的方式。
E - Maximize Rating
观察式子,发现当\(k\)确定时,只有\(\sum (0.9)^{k-i} Q_i\)是变换的,其他部分都是常量。对于这个值,可以直接背包求一下。
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
using ldb = long double;
const int inf = 1e9;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<ldb> a(n + 1), q(n + 1), s(n + 1), t(n + 1);
for (int i = n; i >= 1; i--) cin >> a[i];
q[1] = 1;
for (int i = 2; i <= n; i++) q[i] = q[i - 1] * 0.9;
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + q[i];
for (int i = 1; i <= n; i++) t[i] = 1200.0 / sqrt((ldb) i);
vector<vector<ldb>> f(n + 1, vector<ldb>(n + 1, -1E18));
ldb res = -1E18;
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = 0;
for (int j = 1; j <= i; j++) {
f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + q[j] * a[i]);
res = max(res, f[i][j] / s[j] - t[j]);
}
}
cout << fixed << setprecision(10) << res << "\n";
return 0;
}
F - Apples
其实本质上是个二维数点问题,问用$w\times d $的矩形最多可以框选多少个点。
用一种类似扫描线的方式在\(t\)时给\(x\)加一,然后在\(t+d\)时给\(x\)减一,这样可以优化掉一维,对于剩下的一维可以采用类似双指针的方式此时复杂度是\(O(N^2)\)的依旧不行。
我们考虑每次扫描线后每次都是考虑宽度\(w\)范围有多少个点,我们不如反过来思考,考虑每个点对那些区间产生贡献,答案是\([x,x+w)\),所以每次对这个区间加一,询问时只要询问全局最优解就好了。
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct Node {
int l, r, maxVal, lazy;
Node *left, *right;
Node(int l, int r, Node *left, Node *right)
: l(l), r(r), left(left), right(right) {
maxVal = lazy = 0;
}
} *root;
Node *build(int l, int r) {
if (l == r) return new Node(l, r, nullptr, nullptr);
int mid = (l + r) / 2;
auto left = build(l, mid), right = build(mid + 1, r);
return new Node(l, r, left, right);
}
void pushDown(Node *rt) {
rt->left->maxVal += rt->lazy, rt->left->lazy += rt->lazy;
rt->right->maxVal += rt->lazy, rt->right->lazy += rt->lazy;
rt->lazy = 0;
return;
}
void modify(Node *rt, int l, int r, int v) {
if (l > rt->r or r < rt->l) return;
if (l <= rt->l and rt->r <= r) {
rt->maxVal += v, rt->lazy += v;
return;
}
pushDown(rt);
int mid = (rt->l + rt->r) / 2;
if (l <= mid) modify(rt->left, l, r, v);
if (r > mid) modify(rt->right, l, r, v);
rt->maxVal = max(rt->left->maxVal, rt->right->maxVal);
return;
}
const int N = 4e5;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, d, w;
cin >> n >> d >> w;
vector<vector<pii> > f(N + 1);
for (int t, x, i = 1; i <= n; i++) {
cin >> t >> x;
f[t].emplace_back(x, 1);
if (t + d <= N) f[t + d].emplace_back(x, -1);
}
root = build(1, N);
int res = 0;
for (int x = 1; x <= N; x++) {
for (const auto &[y, v]: f[x])
modify(root, y, min(N, y + w - 1), v);
res = max(res, root->maxVal);
}
cout << res << "\n";
return 0;
}
- Beginner AtCoder Contest 327beginner atcoder contest 327 327 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334