A. Closest Point
可以发现只有两个点且二者不相邻的时候才有答案
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
int a[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
if(n>2){
cout<<"No\n";
}
else{
if(a[1]+1==a[2])cout<<"No\n";
else cout<<"Yes\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Game with Doors
相交片段的门一定都要关上，如果两端不重合就多关一扇
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;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int l, r, L, R;
cin >> l >> r >> L >> R;
int ans = min(r, R) - max(l, L);
if (ans < 0) {
ans = 1;
} else {
ans += (l != L);
ans += (r != R);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
C. Splitting Items
都取最优手段，那么都是拿当前最大值的物品，降序排序后，Bob 只能利用当前的 k 去弥补与 Alice 上一次拿的物品的差距，即最大只能和 Alice 拿的物品相同
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n,k;
int a[N];
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n,greater<int>());
ll ali,bob;
ali=bob=0;
for(int i=1;i<=n;i+=2){
ali+=a[i];
if(i+1<=n){
bob+=a[i+1];
int de=a[i]-a[i+1];
if(k>=de)bob+=de,k-=de;
else bob+=k,k=0;
}
}
cout<<ali-bob<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Colored Portals
如果两个城市有交点，那么答案就是二者的距离之差
如果二者没有交点，就要找点最近的传送城市
例如用 $1, 2, 3, 4$ 来代表颜色，一城市位于 $1, 2$ 另一城市位于 $3, 4$，那么二者只需要传送到另一个不和本身相同的城市即可，如 $1$ 传送到 $1, 3$ 此时即可完成任务，只需要考虑代价最小的传送方案即可
开两个数组 $pre,suf$ 来代表某个城市向前和向后传送的最小代价，计算代价时只需要结合考虑即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define lowbit(x) ((x)&(-x))
const int N=2e5+7, mod=1e9+7;
const int inf=1e9;
int n,q,l,r;
int pre[N],suf[N];
string s[N];
map<string,int>mp;
vector<string>v;
string rs(string s){
if(s=="BG")return "RY";
if(s=="BR")return "GY";
if(s=="GR")return "BY";
if(s=="RY")return "BG";
if(s=="GY")return "BR";
if(s=="BY")return "GR";
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>s[i];
pre[i]=0;
suf[i]=1e9;
}
mp.clear();
for(int i=1;i<=n;i++){
for(auto x:v){
if(x!=rs(s[i])&&s[i]!=x)pre[i]=max(pre[i],mp[x]);
}
mp[s[i]]=i;
}
mp.clear();
for(int i=n;i>0;i--){
for(auto x:v){
if(x!=rs(s[i])&&s[i]!=x)suf[i]=min(suf[i],(mp[x]==0?inf:mp[x]));
}
mp[s[i]]=i;
}
while(q--){
cin>>l>>r;
if(l>r)swap(l,r);
if(rs(s[l])!=s[r])cout<<r-l<<endl;
else{
int ans=1e9;
if(pre[l]!=0)ans=min(r-pre[l]+l-pre[l],ans);
if(suf[r]!=1e9)ans=min(suf[r]-r+suf[r]-l,ans);
if(pre[r]!=0){
if(pre[r]>=l)ans=min(r-l,ans);
if(pre[r]<=l)ans=min(r-pre[r]+l-pre[r],ans);
}
if(suf[l]!=1e9){
if(suf[l]<=r)ans=min(r-l,ans);
if(suf[l]>=r)ans=min(suf[l]-r+suf[l]-l,ans);
}
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
v.push_back("BG");
v.push_back("BR");
v.push_back("GR");
v.push_back("GY");
v.push_back("RY");
v.push_back("BY");
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
E. Not a Nim Problem
一眼顶针，鉴定为打表，打表后发现偶数都为 $0$，同时质数是依次递增，奇数非质的 $sg$ 值是它最小的质数因子的 $sg$ 值
只需要预处理所有的 $sg$ 值即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e7+7, mod=1e9+7;
bool prime[N];
int sg[N],mn[N];
int n,x;
void init(int n){
memset(prime, false, sizeof(prime));
memset(mn, 0, sizeof(mn));
prime[0] = prime[1] = true;
for(int i = 2; i <= n; i++){
if(!prime[i]){
for(int j = i * 2; j <= n; j += i){
mn[j]=(mn[j]==0?i:mn[j]);
prime[j] = true;
}
}
}
}
void init2(int n){
int now=2;
sg[0]=0,sg[1]=1,sg[2]=0;
for(int i=3;i<=n;i++){
if(i&1){
if(!prime[i])sg[i]=now++;
else{
sg[i]=sg[mn[i]];
}
}
else sg[i]=0;
}
}
void solve(){
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>x;
ans^=sg[x];
}
if(!ans)cout<<"Bob\n";
else cout<<"Alice\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
init(N);
init2(N);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|