2022-2023 ICPC North Western Russia Regional

比赛地址 ：Codeforces Gym 104012

待补：DFGHJM

A - Absolutely Flat

签到题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
int ii() {
    int x;
    scanf("%d", &x);
    return x;
}
int main() {
    int a[4];
    for (int i = 0; i < 4; ++i) a[i] = ii();
    int b = ii();
    std::sort(a, a + 4);
    if (a[0] == a[1] && a[0] == a[2] && a[0] == a[3])
        puts("1");
    else if (a[0] + b == a[1] && a[0] + b == a[2] && a[0] + b == a[3])
        puts("1");
    else
        puts("0");
}

B - Bricks in the Wall

给一个矩阵由 # 和 . 组成，执行两次操作：在某一行或某一列中选择一段连续的 . ，将其改为 # 。

求两次操作能修改的最大 . 的个数。

分类讨论，两次都选行/列肯定不会冲突，所以维护最大和次大即可。

如果选一行一列，交点处如果是 # 也直接选最大和次大即可，否则要枚举断掉哪个方向。

每行每列的线段开个 set 维护即可。复杂度 \(\mathcal{O}(nm\log \max(n,m))\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

#define N 2000007

bool mp[N];

int u[N], d[N], l[N], r[N];

multiset<int, greater<int> > R[N], C[N];

inline void work() {
	int n, m; scanf("%d%d", &n, &m);
	auto p = [&](int x, int y) {return (x - 1) * m + y;};

	for (int i = 1; i <= n; ++i) R[i].clear();
	for (int j = 1; j <= m; ++j) C[j].clear();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			char c = getchar();
			while (c != '.' && c != '#') c = getchar();
			int pos = p(i, j);
			mp[pos] = (c == '#');
			u[pos] = d[pos] = l[pos] = r[pos] = 0;
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) 
			if (!mp[pos = p(i, j)]) {
				u[pos] = (i > 1 ? u[p(i - 1, j)] + 1 : 1);
				l[pos] = (j > 1 ? l[p(i, j - 1)] + 1 : 1);
			}
	for (int i = n; i; --i)
		for (int j = m, pos; j; --j) 
			if (!mp[pos = p(i, j)]) {
				d[pos] = (i < n ? d[p(i + 1, j)] + 1 : 1);
				r[pos] = (j < m ? r[p(i, j + 1)] + 1 : 1);
			}
	for (int i = 1, pos; i <= n; ++i) {
		if (!mp[pos = p(i, 1)]) R[i].insert(r[pos]);
		for (int j = 1; j < m; ++j)
			if (mp[p(i, j)] && !mp[pos = p(i, j + 1)]) R[i].insert(r[pos]);
	}
	for (int j = 1, pos; j <= m; ++j) {
		if (!mp[pos = p(1, j)]) C[j].insert(d[pos]);
		for (int i = 1; i < n; ++i)
			if (mp[p(i, j)] && !mp[pos = p(i + 1, j)]) C[j].insert(d[pos]);
	}
	int mx = 0, mxx = 0;
	auto upd = [&](int x) {
		if (mx < x) {mxx = mx; mx = x;}
		else if (mxx < x) mxx = x;
	};
	for (int i = 1; i <= n; ++i) {
		int sz = R[i].size();
		if (sz) upd(*R[i].begin());
		if (sz > 1) upd(*++R[i].begin());
	}
	int ans = mx + mxx;
	mx = mxx = 0;
	for (int j = 1; j <= m; ++j) {
		int sz = C[j].size();
		if (sz) upd(*C[j].begin());
		if (sz > 1) upd(*++C[j].begin());
	}
	ans = max(ans, mx + mxx);
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) 
			if (!mp[pos = p(i, j)]) 
                ans = max(ans, u[pos] + d[pos] + l[pos] + r[pos] - 2 - min({u[pos], d[pos], l[pos], r[pos]}));
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) {
			if (!mp[pos = p(i, j)]) {
				int lr = l[pos] + r[pos] - 1;
				int ud = u[pos] + d[pos] - 1;
				// cut lr
				R[i].erase(R[i].lower_bound(lr));
				R[i].insert(l[pos] - 1); R[i].insert(r[pos] - 1);
				mx = 0; mxx = 0;
				int sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
				R[i].erase(R[i].lower_bound(l[pos] - 1));
				R[i].erase(R[i].lower_bound(r[pos] - 1));
				R[i].insert(lr);
				// cut ud
				C[j].erase(C[j].lower_bound(ud));
				C[j].insert(u[pos] - 1); C[j].insert(d[pos] - 1);
				mx = 0; mxx = 0;
				sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
				C[j].erase(C[j].lower_bound(u[pos] - 1));
				C[j].erase(C[j].lower_bound(d[pos] - 1));
				C[j].insert(ud);
			} else {
				mx = 0; mxx = 0;
				int sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
			}
		}
	printf("%d\n", ans);
}

int main() {
	int t; scanf("%d", &t);
	for (int i = 1; i <= t; ++i) work();
	return 0;
}

C - Computer Network

签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
int ii() {
    int x;
    scanf("%d", &x);
    return x;
}
int main() {
    int n = ii();
    int k = ii();
    std::priority_queue<int> vec;
    for (int i = 0; i < k; ++i) vec.push(0);
    int a[n];
    for (int i = 0; i < n; ++i) a[i] = ii();
    std::sort(a, a + n);
    long long ans{};
    for (int i = 0; i < n; ++i) {
        int x = -vec.top();
        vec.pop();
        int y = -x - a[i];
        ans += x + a[i];
        vec.push(y);
    }
    std::cout << ans << std::endl;
}

*D - Dice Grid

*E - Easily Distinguishable Triangles

给一个矩阵由 #.? 组成，# 代表黑色，. 代表白色，你需要将 ? 的一个角（一半面积）染成黑色。

使得最终对于每个三角形，他所染黑的两条边不和任何其他黑色边界相邻。求方案数。

玩一下发现行列是独立的，换句话说，染色相当于从左右中选一个边染色，上下中选一个边染色。

行列单独计数，以某行为例，如果左右都是黑色的就不行，一侧黑色方案数为 \(1\) ，没有黑色方案数为 \(len+1\) 。

对每个行 / 列连通块执行上述过程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

#define N 1007
#define mod 998244353

char mp[N][N];

int main() {
	int n, ans = 1; scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", mp[i] + 1); mp[i][0] = mp[i][n + 1] = '.';
		for (int j = 1, l = 0; j <= n + 1; ++j) 
			if (mp[i][j] == '?' && mp[i][j - 1] != '?') l = j - 1;
			else if (mp[i][j] != '?' && mp[i][j - 1] == '?') {
				int cnt = (mp[i][l] == '#') + (mp[i][j] == '#');
				if (cnt == 2) {puts("0"); return 0;}
				ans = 1ll * ans * (cnt ? 1 : j - l) % mod;
			}
	}
	for (int j = 1; j <= n; ++j) {
		mp[0][j] = mp[n + 1][j] = '.';
		for (int i = 1, l = 0; i <= n + 1; ++i) 
			if (mp[i][j] == '?' && mp[i - 1][j] != '?') l = i - 1;
			else if (mp[i][j] != '?' && mp[i - 1][j] == '?') {
				int cnt = (mp[l][j] == '#') + (mp[i][j] == '#');
				if (cnt == 2) {puts("0"); return 0;}
				ans = 1ll * ans * (cnt ? 1 : i - l) % mod;
			}
	}
	printf("%d\n", ans);
	return 0;
}

*I - IQ Game

\(n\le 10^9\) 个点围成一圈，有 \(k\le 200\) 个是黑点，其余是白点，且 \(k\) 个点中有一个是炸弹。

每轮随机选一个点，然后找到他顺时针方向的第一个黑点，如果是炸弹游戏结束，否则将这个黑点变白。

问游戏进行的期望轮数。

首先要有一个核心思路，对于值恒正的随机变量 \(x\) ，有 \(E(x)=\sum_{i=1}^{\infty} P(x\ge i)\) 。

注意到游戏 \(k\) 轮之后必定结束，所以只要求出 \(0\le i< k\) 轮游戏不结束的概率即可。

考虑将换从炸弹处断开，按照逆时针方向以炸弹为起点向后延申，以特殊点分段。

那么游戏不结束的要求就是：第一段里的点不能选，第二段最多选一个，前三段最多选两个，以此类推。

发现要求是前 \(i\) 段最多选 \(i-1\) 个，设 \(f[i][j]\) 表示在前 \(i\) 段选了 \(j\) 次，没有违背要求的概率，答案就是 \(\sum_{j=0}^{k-1} f[n][j]\) 。

转移枚举最后一段选了几个，然后再将这些插入到此前的操作序列中，即 \(f[i][j] = \sum_{k=0}^j f[i-1][j-k]\times {j\choose k}\times (\frac{len_i}{n})^k\)

直接做复杂度 \(\mathcal{O}(n^3)\) 的可过，不过转移是个卷积的形式，可以优化到 \(\mathcal{O}(n^2\log n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 207
#define mod 998244353

inline int fpow(int x, int t) {
	int res = 1;
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) res = 1ll * res * x % mod;
	return res;
}

ll pos[N], p[N][N], c[N][N], f[N][N];

int main() {
	int n = rd(), m = rd(), s = rd();
	int invn = fpow(n, mod - 2);
	for (int i = 0; i <= m; ++i) {
		c[i][0] = 1;
		for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}
	for (int i = 1; i <= m; ++i) {
		pos[i] = rd(); if (pos[i] > s) pos[i] -= n;
	}
	pos[0] = s - n;
	sort(pos + 1, pos + 1 + m);
	for (int i = 1; i <= m; ++i) {
		p[i][0] = 1;
		p[i][1] = 1ll * (pos[m - i + 1] - pos[m - i]) * invn % mod;
		for (int j = 2; j <= m; ++j) p[i][j] = p[i][j - 1] * p[i][1] % mod;
	}
	f[0][0] = 1;
	for (int i = 1; i <= m; ++i)
		for (int j = 0; j < i; ++j)
			for (int k = 0; k <= j; ++k) 
				f[i][j] = (f[i][j] + c[j][k] * f[i - 1][j - k] % mod * p[i][k]) % mod;
	ll ans = 0;
	for (int j = 0; j < m; ++j) ans = (ans + f[m][j]) % mod;
	printf("%lld\n", ans);
	return 0;
}

K - K-Shaped Figures

给定平面上 \(n\le 10^3\) 个线段，问有多少个 \(K\) ，定义三条线段构成了一个 K ：

  • 其中两条交于一点，且这一点在第三条线段内（不能是端点）
  • 前两条线在第三条线的同侧，且三条线两两不共线。

做法一

自然的枚举这个中心点，找出来穿过该点的线段 \(\{A\}\)，和以该点为端点的线段 \(\{B\}\) ，都按该点为中心极角序排序。

然后对于每个穿过该点的线段 \(A\) ，线段两侧的 \(B\) 线段下标一定依极角序连续，双指针找出来这个区间即可。

对于不能共线，问题相当于计数给定 \(n\) 个集合，先选两个集合，再从这两个集合中各自选一个数的方案数。

考虑减掉不合法的方案数，则答案为 \({\sum a_i\choose 2} - \sum {a_i\choose 2}\) ，分两项维护即可。

为了避免讨论，我们需要保证任意时刻直线每一侧都有点，因此加入四个垂直方向的虚拟点即可。

注意到双指针旋转时，如果角度超过了 \(180^\circ\) 可能会出现问题，所以再插入垂直方向的四条直线即可。

复杂度为 \(\mathcal{O}(n^2\log n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1007
#define letp const P

struct P {
	ll x, y;
	P(ll x = 0, ll y = 0) : x(x), y(y) {}
	P operator + (letp &p) const {return {x + p.x, y + p.y};}
	P operator - (letp &p) const {return {x - p.x, y - p.y};}
	ll operator | (letp &p) const {return x * p.x + y * p.y;} // dot
	ll operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross
	bool operator < (letp &p) const {return x < p.x || (x == p.x && y < p.y);}
	bool operator == (letp &p) const {return x == p.x && y == p.y;}
	int ori(letp &p) const {ll t = (*this) ^ p; return (t > 0) - (t < 0);}
};

vector<P> pt;

struct argcmp {
	bool operator() (letp &a, letp &b) const {
		const auto quad = [](letp &a) {
			if (a.y < 0) return 1;
			if (a.y > 0) return 4;
			if (a.x < 0) return 5;
			if (a.x > 0) return 3;
			return 2;
		};
		const int qa = quad(a), qb = quad(b);
		if (qa != qb) return qa < qb;
		const auto t = (a ^ b);
		return t > 0;
	}
};

struct S {
	P a, b;
	int is_on(letp &p) const {
		if (p == a || p == b) return -1;
		return (p - a).ori(p - b) == 0 && ((p - a) | (p - b)) < 0;
	}
	int ori(letp &p) const {return (b - a).ori(p - a);}
} s[N];

vector<pair<P, S>> Cr;

vector<P> out;

vector<pair<P, int>> Out;

inline ll c2(int x) {return 1ll * x * (x - 1) / 2;}

inline void work() {
	int n = rd(); pt.clear();
	for (int i = 1; i <= n; ++i) {
		P a, b; a.x = rd(); a.y = rd(); b.x = rd(); b.y = rd();
		pt.push_back(a); pt.push_back(b); s[i] = {a, b}; 
	}
	sort(pt.begin(), pt.end());
	pt.erase(unique(pt.begin(), pt.end()), pt.end());
	
	ll ans = 0;
	for (auto p : pt) {
		Cr.clear(); out.clear(); Out.clear();
		for (int i = 1; i <= n; ++i) {
			int fl = s[i].is_on(p);
			if (fl == 1) {
				Cr.push_back(make_pair(s[i].a, S{s[i].a, s[i].b}));
				Cr.push_back(make_pair(s[i].b, S{s[i].b, s[i].a}));
			} else if (fl == -1) {
				out.push_back(p == s[i].a ? s[i].b : s[i].a);
			}
		}
		if (Cr.empty()) continue;
		if (out.empty()) continue;
		Cr.push_back(make_pair(P{p.x - 100000000, p.y}, S{P{p.x - 100000000, p.y}, P{p.x + 1, p.y}}));
		Cr.push_back(make_pair(P{p.x + 100000000, p.y}, S{P{p.x + 100000000, p.y}, P{p.x - 1, p.y}}));
		Cr.push_back(make_pair(P{p.x, p.y - 100000000}, S{P{p.x, p.y - 100000000}, P{p.x, p.y + 1}}));
		Cr.push_back(make_pair(P{p.x, p.y + 100000000}, S{P{p.x, p.y + 100000000}, P{p.x, p.y - 1}}));
		auto cmp = [&](P &a, P &b) {return argcmp()(a - p, b - p);};
		auto cmpCr = [&](pair<P, S> &a, pair<P, S> &b) {return cmp(a.first, b.first);};
		auto cmpOut = [&](pair<P, int> &a, pair<P, int> &b) {return cmp(a.first, b.first);};

		sort(Cr.begin(), Cr.end(), cmpCr);
		sort(out.begin(), out.end(), cmp);
		auto para = [&](P &a, P &b) {return ((a - p) ^ (b - p)) == 0 && ((a - p) | (b - p)) > 0;};
		for (auto x : out)
			if (Out.empty() || !para(Out.back().first, x)) Out.push_back(make_pair(x, 1));
			else ++Out[Out.size() - 1].second;
		Out.push_back(make_pair(P{p.x + 1, p.y}, 0));
		Out.push_back(make_pair(P{p.x - 1, p.y}, 0));
		Out.push_back(make_pair(P{p.x, p.y + 1}, 0));
		Out.push_back(make_pair(P{p.x, p.y - 1}, 0));
		sort(Out.begin(), Out.end(), cmpOut);
		int sz = Out.size();
		auto nxt = [&](int x) {return x == sz - 1 ? 0 : x + 1;};
		auto pre = [&](int x) {return x == 0 ? sz - 1 : x - 1;};
		int l = 0, r = 0;
		auto pos = [&](S &l, P &x) {return l.ori(x) > 0;};
		ll sum = 0, del = 0;
		while (!pos(Cr[0].second, Out[r].first)) r = nxt(r);
		while (pos(Cr[0].second, Out[r].first)) r = nxt(r);
		r = pre(r); l = r;
		while (pos(Cr[0].second, Out[l].first)) l = pre(l);
		l = nxt(l);
		for (int i = l; i != nxt(r); i = nxt(i)) {
			sum += Out[i].second; del += c2(Out[i].second);
		}
		for (auto [tmp, s] : Cr) {
			while (pos(s, Out[nxt(r)].first)) {
				r = nxt(r); sum += Out[r].second; del += c2(Out[r].second);
			}
			while (!pos(s, Out[l].first)) {
				sum -= Out[l].second; del -= c2(Out[l].second); l = nxt(l);
			}
			if (max(abs(tmp.x), abs(tmp.y)) <= 10000000) ans += c2(sum) - del;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int t; scanf("%d", &t);
	for (int i = 1; i <= t; ++i) work();
	return 0;
}

做法二

因为这题是要求全部的 \(K\) 的个数，所以其实暴力的复杂度是对的。

先枚举中心点，再枚举穿过他的线，再枚举所有以它为端点的线计算答案，计算方式与上一做法相同。

同向去重需要一些技巧，比如 unordered_map 以方向向量除 \(\gcd\) 做下标即可统计。

考虑以枚举点为端点的线段数的和，看似是 \(\mathcal{O}(n^2)\) 实际上是 \(\mathcal{O}(n)\) 的，所以总复杂度是 \(\mathcal{O}(n^2)\) 的。

实际上由于 unordered_map 比 sort 常数还大，所以跑起来并不快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

#define N    1007
#define letp const P

struct P {
	ll x, y;
	P(ll x = 0, ll y = 0) : x(x), y(y) {}
	P operator + (letp &p) const {return {x + p.x, y + p.y};}
	P operator - (letp &p) const {return {x - p.x, y - p.y};}
	P operator / (int t) const {return {x / t, y / t};}
	ll operator | (letp &p) const {return x * p.x + y * p.y;} // dot
	ll operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross
	bool operator < (letp &p) const {return x < p.x || (x == p.x && y < p.y);}
	bool operator == (letp &p) const {return x == p.x && y == p.y;}
	int ori(letp &p) const {ll t = (*this) ^ p; return (t > 0) - (t < 0);}
};

vector<P> pt;

struct argcmp {
	bool operator() (letp &a, letp &b) const {
		const auto quad = [](letp &a) {
			if (a.y < 0) return 1;
			if (a.y > 0) return 4;
			if (a.x < 0) return 5;
			if (a.x > 0) return 3;
			return 2;
		};
		const int qa = quad(a), qb = quad(b);
		if (qa != qb) return qa < qb;
		const auto t = (a ^ b);
		return t > 0;
	}
};

struct S {
	P a, b;
	int is_on(letp &p) const {
		if (p == a || p == b) return -1;
		return (p - a).ori(p - b) == 0 && ((p - a) | (p - b)) < 0;
	}
	int ori(letp &p) const {return (b - a).ori(p - a);}
} s[N];

vector<P> B;

vector<S> A;

unordered_map<ll, int> cnt;

inline ll trans(P x) {
	static const ll bs = 10000000;
	return (x.x + bs) * 2 * bs + (x.y + bs);
}

inline ll c2(int x) {return 1ll * x * (x - 1) / 2;}

inline void work() {
	int n = rd(); pt.clear();
	for (int i = 1; i <= n; ++i) {
		P a, b; a.x = rd(); a.y = rd(); b.x = rd(); b.y = rd();
		pt.push_back(a); pt.push_back(b); s[i] = {a, b}; 
	}
	sort(pt.begin(), pt.end());
	pt.erase(unique(pt.begin(), pt.end()), pt.end());
	ll ans = 0;
	for (auto p : pt) {
		A.clear(); B.clear();
		for (int i = 1; i <= n; ++i) 
			if (p == s[i].a || p == s[i].b) {
				P dlt = (p == s[i].a ? s[i].b : s[i].a) - p;
				dlt = dlt / gcd(abs(dlt.x), abs(dlt.y));
				B.push_back(dlt);
			} else if (s[i].is_on(p)) A.push_back(s[i]);
		for (auto seg : A) {
			cnt.clear();
			int suml = 0, sumr = 0, dell = 0, delr = 0;
			auto addl = [&](ll x) {
				suml -= cnt[x]; dell -= c2(cnt[x]);
				++cnt[x];
				suml += cnt[x]; dell += c2(cnt[x]);
			};
			auto addr = [&](ll x) {
				sumr -= cnt[x]; delr -= c2(cnt[x]);
				++cnt[x];
				sumr += cnt[x]; delr += c2(cnt[x]);
			};
			for (auto dlt : B) {
				int dir = seg.ori(dlt + p);
				if (dir == 1) addl(trans(dlt));
				if (dir == -1) addr(trans(dlt));
			}
			ans += c2(suml) + c2(sumr) - dell - delr;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int t; scanf("%d", &t);
	for (int i = 1; i <= t; ++i) work();
	return 0;
}

L - Limited Swaps

签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
int ii() {
    int x;
    scanf("%d", &x);
    return x;
}
int main() {
    int n = ii();
    int a[n];
    for (int i = 0; i < n; ++i) a[i] = ii();
    int b[n];
    for (int i = 0; i < n; ++i) b[i] = ii();
    std::vector<int> ans;
    for (int i = 0; i < n; ++i) {
        int k = 0;
        for (int j = i; j < n; ++j)
            if (a[j] == b[i])
                k = j;
        for (; k > i; --k)
            if (abs(a[k - 1] - a[k]) < 2) {
                puts("-1");
                return 0;
            } else {
                ans.push_back(k);
                std::swap(a[k - 1], a[k]);
            }
    }
    int m = ans.size();
    std::cout << ans.size() << std::endl;
    for (int i = 0; i < m; ++i)
        std::cout << ans[i] << " \n"[i == m - 1];
}

M - Mex and Cards

给定一个数集，开始 \(i\) 有 \(a_i\) 个，把数集分成若干个集合，最大化所有分出来的集合 MEX 的和。

支持每次插入 / 删除一个数字，维护答案。

线段树。讨论一下即可。可以做到一个 \(\log\) ，回头再补。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<2;

int n,te,a[maxn+5];
int MIN[maxt+5];pair<LL,int> res[maxt+5];

inline int Miner(int x,int y) {return a[x]<a[y] || a[x]==a[y] && x>y?x:y;}
pair<LL,int> Find(int L,int R,int p,int who){
	if (L==R) return a[L]<=a[who]?mp((LL)(a[who]-a[L])*(L-1),L):mp(0LL,who);
	int mid=L+(R-L>>1);
	if (a[who]<a[MIN[p<<1]]) return Find(mid+1,R,p<<1|1,who); else {
		pair<LL,int> ls=Find(L,mid,p<<1,who);
		return mp(ls.fr+res[p].fr,res[p].sc);
	}
}
void Build(int l,int r,int p=1){
	if (l==r) {MIN[p]=l;return;}
	int mid=l+(r-l>>1);
	Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
	MIN[p]=Miner(MIN[p<<1],MIN[p<<1|1]);
	res[p]=Find(mid+1,r,p<<1|1,MIN[p<<1]);
}
void Update(int pos,int l=1,int r=n,int p=1){
	if (l==r) return;
	int mid=l+(r-l>>1);
	pos<=mid?Update(pos,l,mid,p<<1):Update(pos,mid+1,r,p<<1|1);
	MIN[p]=Miner(MIN[p<<1],MIN[p<<1|1]);
	res[p]=Find(mid+1,r,p<<1|1,MIN[p<<1]);
}
int main(){
	scanf("%d",&n);n++;
	for (int i=1;i<n;i++) scanf("%d",&a[i]);
	a[0]=1e9;Build(1,n);
	printf("%lld\n",Find(1,n,1,0).fr);
	for (scanf("%d",&te);te;te--){
		int tp,x;scanf("%d%d",&tp,&x);x++;
		a[x]+=(tp==1?1:-1);Update(x);
		printf("%lld\n",Find(1,n,1,0).fr);
	}
	return 0;
}

N - New Time

签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
using namespace std;

int a,b,c,d,ans;

int main(){
	scanf("%d:%d%d:%d",&a,&b,&c,&d);
	if (b<=d){
		ans+=d-b;
		if (a<=c) ans+=c-a;
		else ans+=24-a+c;
	} else {
		ans+=60-b+d;
		a=(a+1)%24;
		if (a<=c) ans+=c-a;
		else ans+=24-a+c;
	}
	printf("%d\n",ans);
	return 0;
}