A - ACM中的A题
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
const int N = 10;
char s[N];
i32 main() {
int a, b, c;
cin >> a >> b >> c;
int A = a * 2, B = b * 2, C = c * 2;
if (A + b > c and A + c > b and b + c > A) {
cout << "Yes\n";
} else if (a + B > c and a + c > B and B + c > a) {
cout << "Yes\n";
} else if (a + b > C and a + C > b and b + C > a) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
B - ACM中的C题
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
const int N = 10;
char s[N];
i32 main() {
int n;
cin >> n;
if (n == 1) {
cout << -1;
} else {
cout << (n + 1) / 2;
}
return 0;
}
C - ACM中的M题
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
map<int, int> cnt;
for (int i = 1, x; i <= n; i++)
cin >> x, cnt[x]++;
int res = 0;
for (auto [_, b]: cnt) {
if (b < 2) {
cout << -1;
return 0;
}
res += (b + 1) / 2;
}
cout << res;
return 0;
}
D - ACM中的AC题
首先我们可以先用一遍 BFS 计算出每个点到最近的传送门的距离。
然后我们从起点开始进行 BFS,另世你和你关于起点对称。因此只维护你的位置就好,当你移动的时候,只要保证另世你的移动也合法即可。当你移动到传送门后,让另世你直接按照最短路移动到传送门即可,把两个距离求和就是答案。但是这里答案就是不满足单调了,所以找到所有的答案取最小值就好。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, sx, sy;
cin >> n >> m >> sx >> sy, sx--, sy--;
vector<string> g(n);
for (auto &i: g) cin >> i;
vector dis1(n, vi(m, -1));
queue<pii> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@') q.emplace(i, j), dis1[i][j] = 0;
while (not q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0, fx, fy; i < 4; i++) {
fx = x + dx[i], fy = y + dy[i];
if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
if (g[fx][fy] == '#') continue;
if (dis1[fx][fy] != -1) continue;
dis1[fx][fy] = dis1[x][y] + 1, q.emplace(fx, fy);
}
}
vector dis(n, vi(m, -1));
dis[sx][sy] = 0, q.emplace(sx, sy);
sx = sx * 2, sy = sy * 2;
int res = INF;
while (not q.empty()) {
auto [ax, ay] = q.front();
q.pop();
int bx = sx - ax, by = sy - ay;
if (g[ax][ay] == '@' and dis1[bx][by] != -1)
res = min(res, dis[ax][ay] + dis1[bx][by]);
for (int i = 0, fx, fy, gx, gy; i < 4; i++) {
fx = ax + dx[i], fy = ay + dy[i], gx = sx - fx, gy = sy - fy;
if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
if (gx < 0 or gy < 0 or gx >= n or gy >= m) continue;
if (g[fx][fy] == '#' or g[gx][gy] == '#') continue;
if (dis[fx][fy] != -1) continue;
dis[fx][fy] = dis[ax][ay] + 1;
q.emplace(fx, fy);
}
}
if (res >= INF) cout << -1;
else cout << res;
return 0;
}
E - ACM中的CM题
最优解肯定是先把\(m\)变大,然后再贪心覆盖区间就好了。
可以想到的情况是,随\(m\)变化,代价大概是符合三分的性质的。但是通过打表很容易就能找到不符合的情况。因此我们可以考虑通过三分大概先把区间变的小一点,然后再暴力的扫描剩下的区间。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;
using node = array<int, 4>;
const node T = {-1, -1, -1, -1};
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
ranges::sort(a);
auto [ret, lst] = ranges::unique(a);
a.erase(ret, lst);
int l = 0, r = a.back() - a.front();
auto calc = [=](int m) -> int {
int ans1 = 0, ans2 = 0;
for (int i = 0, lst = -INF; i < a.size(); i++)
if (a[i] > lst)
ans1++, lst = a[i] + m;
for (int i = a.size() - 1, lst = INF; i >= 0; i--)
if (a[i] < lst)
ans2++, lst = a[i] - m;
return min(ans1, ans2) + m;
};
int T = 1e8 / a.size();
while (r - l > T) {
int len = (r - l) / 3, lmid = l + len, rmid = r - len;
if (calc(lmid) < calc(rmid)) r = rmid;
else l = lmid;
}
int res = INF;
for (int i = l; i <= r; i++)
res = min(res, calc(i));
cout << res;
return 0;
}
但是上述的代码的calc
是\(O(n)\)的。但实际上,因为有序,所以但我们知道左端点\(l\)时,是可以直接二分出右端点的。那么此时最多的二分次数也就是$\frac n m $。
这样的话,我们实际可以直接枚举\(m\),总复杂度就是\(O(\sum \frac{n}{m} \log n) = O(n\log ^ 2 n)\)。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
const i64 INF = LLONG_MAX / 2;
using node = array<int, 4>;
const node T = {-1, -1, -1, -1};
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
ranges::sort(a);
auto [ret, lst] = ranges::unique(a);
a.erase(ret, lst);
auto calc = [=](int m) -> int {
int ans = m;
for (int pos, lst = -INF; lst < a.back();) {
ans++;
pos = ranges::upper_bound(a, lst) - a.begin();
lst = a[pos] + m;
}
return ans;
};
int res = INF;
for (int i = 0; i <= a.back(); i++)
res = min(res, calc(i));
cout << res;
return 0;
}
F - ACM中的ACM题
一个比较典的三元环问题,我们可以把无向图转换为有向图,规则是边一定从度数小的指向度数大的,如果度数相同从编号小的指向编号大的。这样的话有向图可以满足是一个有向无环图,且每个点的出度不超过\(\sqrt m\)。
我们可以把和\(x\)相邻的所有点染色,然后枚举\(x\)的子节点\(y\),然后看\(y\)的子节点中有没有被染色的点。如果有则说明会形成三元环。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
#define int i64
const ldb eps = 1e-9;
using vi = vector<int>;
using pii = pair<int, int>;
const i64 mod = 998244353;
class dsu {
private:
vector<int> fa;
public:
dsu(int n = 1) {
fa = vector<int>(n + 1, -1), fa[0] = 0;
}
int getfa(int x) {
if (fa[x] < 0) return x;
return fa[x] = getfa(fa[x]);
}
void merge(int x, int y) {
x = getfa(x), y = getfa(y);
if (x == y) return;
if (fa[x] > fa[y]) swap(x, y);
fa[x] += fa[y], fa[y] = x;
}
bool same(int x, int y) {
x = getfa(x), y = getfa(y);
return (x == y);
}
int size(int x) {
x = getfa(x);
return -fa[x];
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<pii> edge(m);
vi deg(n + 1);
for (auto &[x, y]: edge)
cin >> x >> y, deg[x]++, deg[y]++;
vector<vector<pii>> e(n + 1);
for (int cnt = 0; auto &[x, y]: edge) {
if (deg[x] > deg[y]) swap(x, y);
else if (deg[x] == deg[y] and x > y) swap(x, y);
e[x].emplace_back(y, ++cnt);
}
dsu d(m);
vi color(n + 1);
for (int x = 1; x <= n; x++) {
for (auto [y, i]: e[x]) color[y] = i;
for (auto [y, i]: e[x])
for (auto [z, j]: e[y])
if (color[z])
d.merge(i, j), d.merge(color[z], i);
for (auto [y, i]: e[x]) color[y] = 0;
}
if (d.size(1) == m) cout << "Yes\n";
else cout << "No\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T-- > 0)
solve();
return 0;
}
标签:fy,fx,int,vi,i64,牛客,小白月赛,using,100
From: https://www.cnblogs.com/PHarr/p/18405194