2022 NowCoder Multi-University Training Contest 7

B. Rotate Sum 3

给一个凸包,每次操作将凸包按某个对称轴在三维空间里旋转任意角度,求无数次操作后扫过的体积。

如果只有一个对称轴,答案就是若干个圆台的体积之和。

如果有超过一个对称轴,由于所有对称轴都过重心,最终的旋转体会形成一个球,半径是凸包顶点和重心的最远距离。

找对称轴:将凸包展开成角度和边长的序列,然后复制一遍跑 manacher ,如果某个中心的回文半径大于 2n 即为对称轴。

  • 构造序列:角 \(ABC\) 用点积 \(|BA||BC|\cos \alpha\) 代替( \(\cos\alpha\) 可以区分 \([0,\pi)\) 的所有角度, 此外对称要求两侧边也一样长,所以不用除掉模长),边长用长度平方代替,这样就都是整数,没有精度问题了。

  • 计数对称轴:由于一个对称轴可能会被找到两次,需要去重,因为都过重心,所以方向向量叉积不等于 \(0\) 即为不同。

算体积:取直线一侧的点,按照逆时针顺序依次算。代码里偷懒,直接复制出来一遍做,一定有一段是包含完整的点集。

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline ll rd() {
ll 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;
}

typedef long double T;
#define lett const T
#define letp const P // P for point
#define lets const S // S for segment
#define letl const L // L for line
#define letc const C // C for convex

#define z(x) (abs((x)) <= eps) // is zero

const T eps = 1e-8;
const T inf = 1e18;
constexpr long double pi = 3.1415926535897932384;

struct P {
T x, y;
P (T x = 0, T 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 * (lett &d) const {return {x * d, y * d};}
P operator / (lett &d) const {return {x / d, y / d};}

T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross

bool operator == (letp &p) const {return z(x - p.x) && z(y - p.y);}
bool operator != (letp &p) const {return ! operator == (p);}
bool operator < (letp &p) const {return z(x - p.x) ? y < p.y : x < p.x;}
bool operator > (letp &p) const {return !(*this < p || *this == p);}


int ori(letp &p) const {T t = (*this) ^ p; return (t > eps) - (t < -eps);}

T norm() const {return x * x + y * y;}
P proj (letp &p) const {return (*this) * (((*this) | p) / norm());}
P refl (letp &p) const {return proj(p) * 2 - p;}

} zero;

long double abs(letp &p) {return sqrt(p.norm());}
P normalize(letp &p) {return p / abs(p);}
P perp(letp &p) {return {-p.y, p.x};} // turn pi / 2 left
P perpr(letp &p) {return {p.y, -p.x};} // turn pi / 2 right

bool orth(letp &p, letp &q) {return (p | q) == 0;}
bool para(letp &p, letp &q) {return (p ^ q) == 0;}

struct L {
P p, v;
int ori (letp &a) const {return v.ori(a - p);}
P inter(letl &l) const {return p + v * ((l.v ^ (p - l.p)) / (v ^ l.v));}
L shift(letp &d) const {return {p + d, v};}
L shiftl(double d) const {return {p + perp(v) * d / abs(v), v};}
long double dis(letp &a) const {return abs(v ^ (a - p)) / abs(v);}
};

vector<P> c;

#define N 400007

long double a[N];

int p[N];

#define pre(x) (x == 0 ? n - 1 : x - 1)
#define nxt(x) (x == n - 1 ? 0 : x + 1)

vector<int> s;

long double v(long double r, long double R, long double h) {
return 1 / 3.0 * pi * h * (r * r + R * R + r * R);
}

int main() {
int n = rd();
P cent; cent.x = cent.y = 0;
for (int i = 1; i <= n; ++i) {
long double x = rd(), y = rd();
cent.x += x; cent.y += y;
c.pb({x, y});
}
cent = cent / n;
int tot = 0;
for (int i = 0; i < n; ++i) {
a[++tot] = ((c[pre(i)] - c[i]) | (c[nxt(i)] - c[i]));
a[++tot] = (c[nxt(i)] - c[i]).norm();
}
for (int i = 2 * n + 1; i <= 4 * n; ++i) a[i] = a[i - 2 * n];
tot = 4 * n;
int pos = 0, R = 0;
for (int i = 1; i <= 2 * n; ++i) {
if (i < R) p[i] = min(p[(pos << 1) - i], R - i);
else p[i] = 1;
while (1 <= i - p[i] && i + p[i] <= tot && z(a[i - p[i]] - a[i + p[i]])) ++p[i];
if (i + p[i] > R) pos = i, R = i + p[i];
if (2 * p[i] - 1 >= 2 * n) s.pb(i);
}
long double d = 0;
for (int i = 0; i < n; ++i) d = max(d, abs(cent - c[i]));
long double ball = 4.0 / 3.0 * pi * d * d * d;
bool fl = 0;
P dir;
for (auto i : s) {
if (i & 1) { // node
int cur = i / 2;
P dr = c[cur] - cent;
if (!fl) {dir = dr; fl = 1;}
else {
if (!z(dir ^ dr)) {printf("%.12Lf\n", ball); return 0;}
}
} else {
int cur = i / 2 - 1;
P ct = (c[cur] + c[nxt(cur)]) / 2;
P dr = ct - cent;
if (!fl) {dir = dr; fl = 1;}
else {
if (!z(dir ^ dr)) {printf("%.12Lf\n", ball); return 0;}
}
}
}
if (!fl) {puts("0"); return 0;}
L l{cent, dir};
fl = 0;
for (int i = 0; i < n; ++i) c.pb(c[i]);
long double ans = 0, tmp = 0;
P lstp;
for (auto nw : c) {
if (l.ori(nw) >= 0) {
if (fl) {
tmp += v(l.dis(lstp), l.dis(nw), fabs(((lstp - nw) | l.v) / abs(l.v)));
}
fl = 1; lstp = nw;
} else {ans = max(ans, tmp); fl = 0; tmp = 0;}
}
ans = max(ans, tmp);
printf("%.12Lf\n", ans);
return 0;
}

一道类似的多边形找对称轴题:[POI 2007] Axes of Symmetry

F. Candies

\(n\) 个数字形成一个环,每次可以删掉两个相邻的相同或和为 \(a\) 的两个数字,问最多能删几次。

每次暴力找到一个位置删除即可。证明比较巧妙:

对于所有的 \(x\in [a / 2, a]\)\(x\) 变为 \(a-x\) ,可以发现原本允许消除的数对现在依然允许消除。

因此只剩下相邻且相同的数字才可以消除,此时贪心显然是对的,删除顺序不会改变答案大小。

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>
using namespace std;

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;
}

deque<int> s;

int main() {
int n = rd(), a = rd(), ans = 0;
for (int i = 1; i <= n; ++i) {
s.push_back(rd());
while (s.size() >= 2) {
int x = s[s.size() - 1], y = s[s.size() - 2];
if (x != y && x + y != a) break;
++ans; s.pop_back(); s.pop_back();
}
}
while (s.size() >= 2) {
if (s.front() == s.back() || s.front() + s.back() == a) {
++ans; s.pop_front(); s.pop_back();
} else break;
}
printf("%d\n", ans);
return 0;
}

K. Great Party

\(n\) 堆石子,每堆 \(a_i\) 个,每次选一堆拿走若干个,剩余的可以选择合并到某一堆现存的中。

每次询问一个区间,问有多少个子区间先手必胜。

少见的做出来的博弈题,按堆数从小到大考虑。

只有一堆,必胜;只有两堆,如果一样的话,因为不敢合并,所以可以对称操作,必败,否则必胜;三堆的必胜,因为可以通过拿+合并变成两堆一样多的;四堆的情况谁拿成三堆就输,因为三堆必胜,所以四堆的时候可以看成是 \(a_i-1\) 的 NIM 游戏,因为都拿到 \(1\) 就不得不合并了。五堆的时候一定可以对最大的操作使得变成四堆且 NIM 和为 \(0\) 。因此:

  • 偶数个即为 \(a_i - 1\) 的 NIM 游戏,因为转换成奇数的那个人必败。

  • 奇数先手必胜,先手对最大那堆石子操作,使得剩偶数个且石子个数减一的异或和为0的局面。

所以变成了查询区间内有多少个偶数长度的子区间异或和为 \(0\) ,莫队分奇偶统计即可。(让胖胖写的)

L. Maximum Range