CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Rikka with Cake
根据平面上的欧拉定理，此题交点数+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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=3e5+99;
int T,n,m,k;
int tree[maxn*2];
char ch[10];
struct data
{
int ux,uy,dx,dy;
} f[maxn],g[maxn],t[maxn];
struct Ranker:vector<int>
{
void init()
{
sort(begin(),end()),resize(unique(begin(),end())-begin());
}
int ask(int x) const
{
return lower_bound(begin(),end(),x)-begin();
}
};
bool cmp1(data a,data b)
{
return (a.ux<b.ux);
}
bool cmp2(data a,data b)
{
return (a.dx<b.dx);
}
bool cmp3(data a,data b)
{
return (a.dx<b.dx);
}
void add(int loc,int val)
{
loc+=9;
while (loc<maxn*2)
{
tree[loc]+=val;
loc+=(loc&(-loc));
}
}
int query(int loc)
{
loc+=9;
int ans=0;
while (loc) ans+=tree[loc],loc-=(loc&(-loc));
return ans;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&n,&m,&k);
Ranker rk;
rk.push_back(0);
rk.push_back(n);
rk.push_back(m);
int fi=0,gi=0;
for (int i=1; i<=k; i++)
{
int x,y;
scanf("%d%d%s",&x,&y,ch);
rk.push_back(x);
rk.push_back(y);
if (ch[0]=='U')
{
f[++fi].ux=x;
f[fi].uy=m;
f[fi].dx=x;
f[fi].dy=y;
}
if (ch[0]=='D')
{
f[++fi].ux=x;
f[fi].uy=y;
f[fi].dx=x;
f[fi].dy=0;
}
if (ch[0]=='L')
{
g[++gi].ux=0;
g[gi].uy=y;
g[gi].dx=x;
g[gi].dy=y;
}
if (ch[0]=='R')
{
g[++gi].ux=x;
g[gi].uy=y;
g[gi].dx=n;
g[gi].dy=y;
}
}
rk.init();
for (int i=1; i<=fi; i++)
{
f[i].ux=rk.ask(f[i].ux);
f[i].uy=rk.ask(f[i].uy);
f[i].dx=rk.ask(f[i].dx);
f[i].dy=rk.ask(f[i].dy);
}
for (int i=1; i<=gi; i++)
{
g[i].ux=rk.ask(g[i].ux);
g[i].uy=rk.ask(g[i].uy);
g[i].dx=rk.ask(g[i].dx);
g[i].dy=rk.ask(g[i].dy);
t[i].ux=g[i].ux;
t[i].uy=g[i].uy;
t[i].dx=g[i].dx;
t[i].dy=g[i].dy;
}
fill(tree,tree+2*maxn,0);
sort(g+1,g+1+gi,cmp1);
sort(t+1,t+1+gi,cmp2);
sort(f+1,f+1+fi,cmp3);
int head=1,tail=1;
LL ans=1ll;
for (int i=1; i<=fi; i++)
{
while (g[head].ux<=f[i].ux && head<=gi)
{
add(g[head].uy,1);
head++;
}
while (t[tail].dx<f[i].ux && tail<=gi)
{
add(t[tail].uy,-1);
tail++;
}
int now=query(f[i].uy)-query(f[i].dy-1);//-1
ans+=(LL)now;
}
printf("%lld\n",ans);
}
return 0;
}
Rikka with Game
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int t;
char s[1000];
int main(void){
cin>>t;
while(t--){
cin>>s;
for(int i=0;s[i]!='\0';i++){
if(s[i]!='y'&&s[i]!='z')break;
if(s[i]=='z'){s[i]='b';break;}
}
cout<<s<<endl;
}
}
Rikka with Coin
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
#include <bits/stdc++.h>
using namespace std;
const int N = 127, INF = 1e9;
int t, n, ans, w[N];
int cal(int i5, int i2, int i1)
{
int ret = 0;
for (int i = 0; i < n; ++i)
{
int tmp = INF;
for (int j5 = 0; j5 <= i5; ++j5)
for (int j2 = 0; j2 <= i2; ++j2)
for (int j1 = 0; j1 <= i1; ++j1)
{
int sum = w[i] - j5 * 50 - j2 * 20 - j1 * 10;
if (sum >= 0 && sum % 100 == 0)
tmp = min(tmp, sum / 100);
}
ret = max(ret, tmp);
}
return ret;
}
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
ans = INF;
for (int i = 0; i < n; ++i)
scanf("%d", &w[i]);
for (int i5 = 0; i5 <= 1; ++i5)
for (int i2 = 0; i2 <= 4; ++i2)
for (int i1 = 0; i1 <= 1; ++i1)
ans = min(ans, cal(i5, i2, i1) + i5 + i2 + i1);
printf("%d\n", ans < INF ? ans : -1);
}
}
Rikka with Stable Marriage
和几天前做的多校五的 B 题完全相同，只是这里要求最大值。代码复用率很高。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NPOS = -1;
struct Trie
{
struct Node
{
int cnt, ch[2];
};
vector<Node> v;
Trie() : v(1, Node{0, {NPOS, NPOS}}) {}
void add(int x)
{
for (int rt = 0, i = 29; ~i; --i)
{
int nxt = x >> i & 1;
if (v[rt].ch[nxt] == NPOS)
{
v[rt].ch[nxt] = v.size();
v.push_back(Node{0, {NPOS, NPOS}});
}
rt = v[rt].ch[nxt];
++v[rt].cnt;
}
}
};
int main()
{
int t, n;
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
Trie t[2];
for (int i = 0; i < 2; ++i)
for (int j = 0, x; j < n; ++j)
scanf("%d", &x), t[i].add(x);
ll ans = 0;
for (int i = 0, val[2]; i < n; ++i)
{
for (int rt[2] = {val[0] = 0, val[1] = 0}, i = 29; ~i; --i)
{
#define OK(i, j) (t[i].v[rt[i]].ch[j] != NPOS && t[i].v[t[i].v[rt[i]].ch[j]].cnt)
if (OK(0, 1) && OK(1, 0))
rt[0] = t[0].v[rt[0]].ch[1], rt[1] = t[1].v[rt[1]].ch[0], val[0] = val[0] << 1 | 1, val[1] = val[1] << 1;
else if (OK(0, 0) && OK(1, 1))
rt[0] = t[0].v[rt[0]].ch[0], rt[1] = t[1].v[rt[1]].ch[1], val[0] = val[0] << 1, val[1] = val[1] << 1 | 1;
else if (OK(0, 1) && OK(1, 1))
rt[0] = t[0].v[rt[0]].ch[1], rt[1] = t[1].v[rt[1]].ch[1], val[0] = val[0] << 1 | 1, val[1] = val[1] << 1 | 1;
else
rt[0] = t[0].v[rt[0]].ch[0], rt[1] = t[1].v[rt[1]].ch[0], val[0] = val[0] << 1, val[1] = val[1] << 1;
--t[0].v[rt[0]].cnt, --t[1].v[rt[1]].cnt;
}
ans += val[0] ^ val[1];
}
printf("%lld\n", ans);
}
}