A. Alice’s Adventures in “Chess”
因为图小，可以直接按串跑 $100$ 遍等，反正暴力就行
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
|
#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,xx,yy;
string s;
map<pair<int,int>,vector<int>>vis;
void bfs(){
deque<pair<int,int>>q;
q.push_back({0,0});
vis[{0,0}].push_back(0);
int now=0;
while(q.size()){
int x=q.front().first,y=q.front().second;
q.pop_front();
if(s[now%n]=='N'){
y++;
}
else if(s[now%n]=='S'){
y--;
}
else if(s[now%n]=='E'){
x++;
}
else x--;
if(x==xx && y==yy){
cout<<"Yes\n";
return;
}
q.push_back({x,y});
now++;
if(now>1000){
cout<<"No\n";
return;
}
}
}
void solve() {
cin>>n>>xx>>yy>>s;
bfs();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("..//..//in_out//in.txt", "r", stdin);
// freopen("..//..//in_out//out.txt", "w", stdout);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
B. Alice’s Adventures in Permuting
观察到 $a$ 其实就是一个等差数列
当最小项大等于$n$ 时，只需要再进行 $n$ 次操作即可
若 $b$ 为零，即数组中都为 $c$ 时，如果这个 $c$ 小于一个界限，会导致后面的操作只会对某个数一直进行，这是唯一的无解情况
否则，只需要进行 $n-1$ 次操作，填满缺少的即可
如果 $b$ 不为 0，那么一定可行，进行次数即为数组中大于等于 $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
|
#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;
ll n,b,c;
void solve(){
cin>>n>>b>>c;
if(c>=n)cout<<n<<endl;
else if(b){
if(n-3>=c)cout<<-1<<endl;
else cout<<n-1<<endl;
}
else cout<<n-(n-c-1)/b-1<<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. Alice’s Adventures in Cutting Cake
因为必须分成 $m-1$ 块，Alice 取的一定是其中连续的片段，即这个片段左侧和右侧满足条件的片段要有 $m$ 个
我们可以先预处理从前往后，从后往前的片段中符合条件的个数，这样统计选取片段后其他片段符合条件的个数只需要 $O(1)$ 即可完成
接着就是如何确定这个片段，可以以 $1 \sim n$ 为左端点，接着二分找满足条件的最大的右端点，这样的时间复杂度为 $O(n \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
|
#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;
#define int long long
const int N=2e5+7, mod=1e9+7;
int n,m,v;
ll a[N],s[N],pre[N],suf[N];
bool check(int l,int r){
if(l>r)return 1;
int cnt=0,lst=1;
cnt+=pre[l-1]+suf[r+1];
return cnt>=m;
}
void solve(){
cin>>n>>m>>v;
for(int i=1;i<=n;i++)cin>>a[i];
int cnt=0,tmp=0;
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
tmp+=a[i];
if(tmp>=v)tmp=0,cnt++,pre[i]=pre[i-1]+1;
else pre[i]=pre[i-1];
}
tmp=0,suf[n+1]=0;
for(int i=n;i>0;i--){
tmp+=a[i];
if(tmp>=v)suf[i]=suf[i+1]+1,tmp=0;
else suf[i]=suf[i+1];
}
if(cnt<m){
cout<<"-1\n";
return;
}
ll res=0;
for(int i=1;i<=n;i++){
int l=i,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(check(i,mid)){
if(i<=mid)res=max(res,s[mid]-s[i-1]);
l=mid+1;
}
else r=mid-1;
}
}
cout<<res<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Alice’s Adventures in Cards
容易往图那方面想，虽然 CF 官方题解说这是 DP 题，但是按图的思想也能过
可以先按 bfs 来跑，遍历所有的能交换的卡片，这样就能找到通往所有能到达卡片的对应路，同时也是最短路
bfs 过程中如果能到达 $n$ 说明是 Yes
能到达就通过 dfs 来从 $1$ 遍历所有能到达的卡片，来找最短到达 $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
|
#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,flag;
int a[4][N],b[4][N];
bool vis[4][N],used[N];
vector<pair<char,int>>ans,g[N];
set<pair<int,int>>s[4];
void bfs(int x){
set<int>q;
q.insert(x);
used[x]=1;
while(q.size()){
int now=*q.begin();
q.erase(q.begin());
for(int i=a[1][now];i<=n;i++){
if(vis[1][i])break;
if(used[b[1][i]]&&b[1][i]>now){
g[now].push_back({'q',b[1][i]});
if(b[1][i]==n){
flag=1;
break;
}
used[b[1][i]]=1;
q.insert(b[1][i]);
}
vis[1][i]=1;
}
for(int i=a[2][now];i<=n;i++){
if(vis[2][i])break;
if(used[b[2][i]]&&b[2][i]>now){
g[now].push_back({'k',b[2][i]});
if(b[2][i]==n){
flag=1;
break;
}
used[b[2][i]]=1;
q.insert(b[2][i]);
}
vis[2][i]=1;
}
for(int i=a[3][now];i<=n;i++){
if(vis[3][i])break;
if(used[b[3][i]]&&b[3][i]>now){
g[now].push_back({'j',b[3][i]});
if(b[3][i]==n){
flag=1;
break;
}
used[b[3][i]]=1;
q.insert(b[3][i]);
}
vis[3][i]=1;
}
}
}
void dfs(int x){
used[x]=1;
if(x==n){
flag=1;
return;
}
for(auto j:g[x]){
if(used[j.second]){
ans.push_back(j);
dfs(j.second);
if(flag)return;
ans.pop_back();
}
}
}
void solve(){
cin>>n;
flag=0;
ans.clear();
for(int i=1;i<=3;i++){
s[i].clear();
for(int j=1;j<=n;j++){
int x;
cin>>x;
g[j].clear();
used[x]=0;
vis[i][j]=0;
s[i].insert({n-x+1,j});
}
int cnt=0;
for(auto [x,y]:s[i]){
cnt++;
a[i][y]=cnt;
b[i][cnt]=y;
}
}
bfs(1);
if(flag==0)cout<<"No\n";
else {
flag=0;
for(int i=1;i<=n;i++)used[i]=0;
dfs(1);
cout<<"Yes\n";
cout<<ans.size()<<endl;
for(auto [x,y]:ans){
cout<<x<<" "<<y<<endl;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
E. Alice’s Adventures in the Rabbit Hole
暂时有点思路，后面推出来补