https://codeforces.com/gym/102028

A. Xu Xiake in Henan Province

 

纯签到

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int t;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--) {
int cnt = 0;
for (int i = 0; i < 4; i++) {
int u;
cin >> u;
if (u != 0)cnt++;
}
switch (cnt)
{
case 0:cout << "Typically Otaku" << endl;
break;
case 1:cout << "Eye-opener" << endl;
break;
case 2:cout << "Young Traveller" << endl;
break;
case 3:cout << "Excellent Traveller" << endl;
break;
case 4:cout << "Contemporary Xu Xiake" << endl;
break;
}
}
return 0;
}

 

D. Keiichi Tsuchiya the Drift King

 

当角度d较小时,矩形左下还未进入环形轨道,要分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int T;
double a, b, r, d;
const double PI = acos(-1.0);
int main()
{
cin >> T;
while (T--) {
cin >> a >> b >> r >> d;
d *= PI / 180.0;
if ((r + a) * sin(d) > b * cos(d))
printf("%.12f\n", sqrt((a + r) * (a + r) + b * b) - r);
else printf("%.12f\n", (r + a) * cos(d) + b * sin(d) - r);
}
return 0;
}

 

E. Resistors in Parallel

 

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
def isPrime(a):
for i in range(2, int(a ** 0.5) + 1):
if (a % i == 0):
return False
return True

def gcd(aa, bb):
if (bb == 0):
return aa
return gcd(bb, aa % bb)

P = []
for i in range(2, 1000):
if (isPrime(i)):
P.append(i)
T = int(input())
for kase in range(T):
n = int(input())
prd = 1
i = -1
while prd <= n:
i += 1
prd *= P[i]
prd //= P[i]
up = 1
down = 1
for j in range(i):
up *= 1 + P[j]
down *= P[j]
d = gcd(up, down)
up //= d
down //= d
print("%d/%d" % (down, up))

 

F. Honeycomb

 

把图像转化成图。

记录每个蜂巢的中心点坐标,再判断六个面是否为空格。若为空格则图上连边。

bfs最短路。

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Pair;
const int maxn = 1e4, maxm = 1e6+5;
int T, r, c, s, t;
char dic[maxn][maxn], ch;
vector<int> G[maxm];
int vis[maxm];
Pair ij2xy(int i, int j)
{
return Pair(2 + 4 * i + 2 * (j % 2), 4 + 6 * j);
}

int ij2n(int i, int j)
{
return i * c + j;
}
int bfs()
{
queue<Pair> que;
memset(vis, 0, sizeof(vis));
que.push(Pair(1, s));
vis[s] = 1;
while (!que.empty()) {
Pair p = que.front(); que.pop();
if (p.second == t) return p.first;
for (int i : G[p.second]) if (!vis[i]) {
que.push(Pair(p.first + 1, i));
vis[i] = 1;
}

}
return -1;
}

int main()
{
cin >> T;
while (T--) {
cin >> r >> c;
getchar();
for (int i = 0; i < 4 * r + 3; ++i) {
int j = 0;
while ((ch = getchar()) != '\n') {
dic[i][j++] = ch;
}
}
for (int i = 0; i < r * c; ++i) G[i].clear();
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) {
Pair pp = ij2xy(i, j);
int x = pp.first, y = pp.second;
if (dic[x][y] == 'S') s = ij2n(i, j);
if (dic[x][y] == 'T') t = ij2n(i, j);
if (dic[x - 2][y] == ' ') G[ij2n(i, j)].push_back(ij2n(i - 1, j));
if (dic[x + 2][y] == ' ') G[ij2n(i, j)].push_back(ij2n(i + 1, j));
if (dic[x - 1][y - 3] == ' ') {
if (j % 2) G[ij2n(i, j)].push_back(ij2n(i, j - 1));
else G[ij2n(i, j)].push_back(ij2n(i - 1, j - 1));
}
if (dic[x + 1][y - 3] == ' ') {
if (j % 2) G[ij2n(i, j)].push_back(ij2n(i + 1, j - 1));
else G[ij2n(i, j)].push_back(ij2n(i, j - 1));
}
if (dic[x - 1][y + 3] == ' ') {
if (j % 2) G[ij2n(i, j)].push_back(ij2n(i, j + 1));
else G[ij2n(i, j)].push_back(ij2n(i - 1, j + 1));
}
if (dic[x + 1][y + 3] == ' ') {
if (j % 2) G[ij2n(i, j)].push_back(ij2n(i + 1, j + 1));
else G[ij2n(i, j)].push_back(ij2n(i, j + 1));
}
}
cout << bfs() << endl;

}
return 0;
}

 

H. Can You Solve the Harder Problem?

 

线段树+后缀数组

由于包含相同元素的区间只能计算一次,所以要找到本质相同的区间。自然想到后缀数组,若sa[i]与sa[i-1]的lcp!=0,则说明sa[i]的前一部分不能计算。

后缀数组的每一个区间左端点都不同,且左端点从1到n都取到。所以枚举区间左端点,计算以i为左端点的所有区间对答案的贡献。可以恰好在后缀数组上计算。

考虑sa[i]与sa[i-1]有lcp,则以sa[i]为左端点的所有区间中,右端点在lcp左侧的区间都被计算过了,所以ans只要加上以sa[i]为左端点,且右端点在sa[i]+lcp[i]右侧的区间。

单调栈预处理出每个位置右边第一个大于该位置上元素的位置。

线段树找到lcp左侧最大值,并找到这个值最接近lcp且在lcp左侧的位置pos,它右侧第一个比他大的位置ed,若区间右端点在pos和ed之间,则贡献为lcp左侧最大值* 区间右端点在pos和ed之间的区间的个数,若区间右端点在ed右侧,则这些区间以ed为最大值,它的贡献就等于以ed为左端点,的所有区间的贡献。可以预处理出来。

我这里离散化了,但只是减少了线段树的大小,并没有减复杂度,没想到卡过了。。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l + r)>> 1)
#define lch rt << 1, l, mid
#define rch (rt << 1) | 1, mid + 1, r
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int T, n, tot;
int a[maxn], tr[maxn << 2], q[maxn], lar[maxn];
ll w[maxn];
map<int, vector<int> >mp;
void pushup(int rt) {
tr[rt] = max(tr[rt << 1], tr[(rt << 1) | 1]);
}
void build(int rt, int l, int r) {
if (l == r) {
tr[rt] = a[l];
return;
}
build(lch);
build(rch);
pushup(rt);
}
int query(int ql, int qr, int rt, int l, int r) {
if (ql <= l && qr >= r)return tr[rt];
int res = 0;
if (ql <= mid)res = max(res, query(ql, qr, lch));
if (qr > mid)res = max(res, query(ql, qr, rch));
return res;
}

int rk[maxn], tmp[maxn], k, sa[maxn], lcp[maxn];
bool compare_sa(int i, int j) {
if (rk[i] != rk[j])return rk[i] < rk[j];
else {
int ri = i + k <= n ? rk[i + k] : -1;
int rj = j + k <= n ? rk[j + k] : -1;
return ri < rj;
}
}
void constract_sa(const int* S) {
for (int i = 0; i <= n; i++) {
sa[i] = i;
rk[i] = i < n ? S[i] : -1;
}
for (k = 1; k <= n; k *= 2) {
sort(sa, sa + n + 1, compare_sa);
tmp[sa[0]] = 0;
for (int i = 1; i <= n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i <= n; i++) {
rk[i] = tmp[i];
}
}
}
void constract_lcp(const int* S) {
for (int i = 0; i <= n; i++) {
rk[sa[i]] = i;
}
int h = 0;
lcp[1] = 0;
for (int i = 0; i < n; i++) {
int j = sa[rk[i] - 1];
if (h > 0)h--;
for (; j + h < n&&i + h < n; h++) {
if (S[j + h] != S[i + h])break;
}
lcp[rk[i]] = h;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
scanf("%d", &T);
while (T--) {
mp.clear();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
q[i] = a[i];
}
sort(q, q + n);
tot = unique(q, q + n) - q;
for (int i = 0; i < n; i++) {
a[i] = lower_bound(q, q + n, a[i]) - q;
mp[a[i]].push_back(i);
}
stack<int>st;
st.push(n);
a[n] = INF;
build(1, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
while (a[st.top()] <= a[i])st.pop();
lar[i] = st.top();
st.push(i);
}
w[n] = 0; w[n - 1] = q[a[n - 1]];
for (int i = n - 2; i >= 0; i--) {
w[i] = (ll)q[a[i]] * (lar[i] - i) + w[lar[i]];
}
constract_sa(a);
constract_lcp(a);
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (lcp[i] == 0) {
ans += w[sa[i]];
}
else {
int p = sa[i] + lcp[i] - 1;
int mx = query(sa[i], p, 1, 0, n - 1);
int pos;
int tp = lower_bound(mp[mx].begin(), mp[mx].end(), p) - mp[mx].begin();
if (tp == mp[mx].size())pos = mp[mx][tp - 1];
else {
if (mp[mx][tp] != p) pos = mp[mx][tp - 1];
else pos = mp[mx][tp];
}
int ed = lar[pos];
ans += (ll)q[a[pos]] * (ed - p - 1) + w[ed];
}
}
printf("%I64d\n", ans);
}
return 0;
}

 

I. Distance

 

每次都是选最外侧没被选过的点。

dp

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
int t;
int a[maxn], d[maxn];
ll L[maxn], sum[maxn], dp[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> t;
while (t--) {
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
int n;
cin >> n;
for (int i = 1; i <= n - 1; i++) {
cin >> d[i];
}
for (int i = 2; i <= n; i++) {
a[i] = a[i-1] + d[i-1];
}
int l = 1, r = n;
while (l <= r) {
L[l] = a[r] - a[l];
l++;
r--;
}
for (int i = 1; i <= l; i++) {
sum[i] = sum[i - 1] + L[i];
}
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + sum[i / 2];
}
for (int i = 1; i <= n; i++) {
cout << dp[i];
if (i != n)cout << ' ';
}
cout << endl;
}
return 0;
}