E Transition Game
拓扑跑环。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector<int> deg(n);
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
g[i].push_back(a[i]);
g[a[i]].push_back(i);
deg[a[i]]++;
deg[i]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) {
q.push(i);
}
}
int ans = n;
while (!q.empty()) {
auto cur = q.front();
q.pop();
ans--;
for (auto nex : g[cur]) {
if (--deg[nex] == 1) {
q.push(nex);
}
}
}
cout << ans << '\n';
return 0;
}
F Simultaneous Swap
graph TD;
A[<u>1</u> 2 3 4 5 <u>6</u> 7 8<br>7 8 5 <u>6</u> 4 <u>3</u> 1 2]--操作一次-->B[<u>6</u> 2 3 4 5 <u>1</u> 7 8<br>7 8 5 <u>3</u> 4 <u>6</u> 1 2]
graph TD;
A[<u>6</u> 2 3 4 5 <u>1</u> 7 8<br>7 8 5 3 4 <u>6</u> 1 <u>2</u>]--操作一次-->B[<u>1</u> 2 3 4 5 <u>6</u> 7 8<br>7 8 5 3 4 <u>2</u> 1 <u>6</u>]
graph TD;
A[1 2 3 4 5 6 7 8<br>7 8 5 <u>6</u> 4 <u>3</u> 1 <u>2</u>]--操作两次-->B[1 2 3 4 5 6 7 8<br>7 8 5 <u>3</u> 4 <u>2</u> 1 <u>6</u>]
操作两次相当于选择 \(i,j,k\) \((i<j<k)\),令 \(b_{i},b_{j},b_{k}=b_{j},b_{k},b_{i}\)。
那么:
graph TD;
A[7 8 5 <u>6</u> 4 <u>3</u> 1 <u>2</u>]--操作两次-->B[7 8 5 <u>3</u> 4 <u>2</u> 1 <u>6</u>]
graph TD;
A[7 <u>8</u> 5 <u>3</u> 4 <u>2</u> 1 6]--操作两次-->B[7 <u>3</u> 5 <u>2</u> 4 <u>8</u> 1 6]
graph TD;
A[7 <u>8</u> 5 <u>6</u> 4 <u>3</u> 1 <u>2</u>]--操作四次-->B[7 <u>3</u> 5 <u>2</u> 4 <u>8</u> 1 <u>6</u>]
可以发现操作四次就是选择 \(i,j,x,y\) \((i<j<x<y)\),令 \(b_{i},b_{j}=b_{j},b_{i}\),\(b_{x},b_{y}=b_{y},b_{x}\)。
我们可以发现若 \(b\) 中存在两个元素相同,那么我们就可以通过四次操作交换 \(b\) 任意两个位置的元素。
并且当 \(a,b\) 逆序对数量同奇偶则一定 Yes
,并且最后把 \(a,b\) 都还原成正序。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(const int n = 0) : n(n), a(n, T()) {}
void modify(int p, T x) {
for (p += 1; p <= n; p += p & -p) {
a[p - 1] += x;
}
}
T get(int p) {
T res = T();
for ( ; p > 0; p -= p & -p) {
res += a[p - 1];
}
return res;
}
T sum(int l, int r) { // [l, r)
return get(r) - get(l);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
b[i]--;
}
auto c = a;
auto d = b;
sort(c.begin(), c.end());
sort(d.begin(), d.end());
if (c != d) {
cout << "No\n";
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (c[i] == c[i + 1]) {
cout << "Yes\n";
return 0;
}
}
auto get = [&](const vector<int> &a) {
Fenwick<i64> f(n);
i64 res = 0;
for (int i = 0; i < n; i++) {
res += f.get(a[i]);
f.modify(a[i], 1);
}
return res;
};
if (get(a) % 2 == get(b) % 2) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
G Polygon and Points
计算几何,\(O(\log n)\) 求点与多边形位置关系。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Real = i64;
using Point = complex<Real>;
#define x real
#define y imag
constexpr Real eps = 0;
int sign(const Real &x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
Real cross(const Point &a, const Point &b) {
return (conj(a) * b).y();
}
Real dot(const Point &a, const Point &b) {
return (conj(a) * b).x();
}
struct Line {
Point a, b;
Line(const Point &a, const Point &b) : a(a), b(b) {}
};
struct Segment : Line {
Segment() = default;
using Line::Line;
Real len() const {
return abs(a - b);
}
};
bool onSegment(const Point &p, const Segment &s) {
return sign(cross(p - s.a, s.b - s.a)) == 0 && sign(dot(p - s.a, p - s.b)) <= 0;
}
using Polygon = vector<Point>;
// left : 1, right : -1
int onLeft(const Point &p, const Line &l) {
return sign(cross(l.b - l.a, p - l.a));
}
// ON : -1, OUT : 0, IN : 1
int contains(const Point &p, const Polygon &g) {
if (g.size() == 1) {
return p == g[0] ? -1 : 0;
}
if (g.size() == 2) {
return onSegment(p, Segment(g[0], g[1]));
}
if (p == g[0]) {
return -1;
}
if (onLeft(p, Segment(g[0], g[1])) == -1 || onLeft(p, Segment(g[0], g.back())) == 1) {
return 0;
}
const auto cmp = [&](const Point &u, const Point &v) {
return onLeft(v, Segment(g[0], u)) == 1;
};
const size_t i = lower_bound(g.begin() + 1, g.end(), p, cmp) - g.begin();
if (i == 1) {
return onSegment(p, Segment(g[0], g[i])) ? -1 : 0;
}
if (i == g.size() - 1 && onSegment(p, Segment(g[0], g[i]))) {
return -1;
}
if (onSegment(p, Segment(g[i - 1], g[i]))) {
return -1;
}
return onLeft(p, Segment(g[i - 1], g[i])) > 0;
}
string ans[] = {"ON", "OUT", "IN"};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
Polygon a(n);
for (int i = 0; i < n; i++) {
i64 x, y;
cin >> x >> y;
a[i] = Point(x, y);
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
i64 x, y;
cin >> x >> y;
Point p(x, y);
cout << ans[contains(p, a) + 1] << '\n';
}
return 0;
}
- Beginner AtCoder Contest 296beginner atcoder contest 296 contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 315