A. Rudolf and the Ticket

题目链接

题意

左口袋有$n$枚硬币，右口袋有$m$枚硬币，问有多少种组合硬币的总价值小于等于$k$

分析

看数据范围发现完全可以暴力解决

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>b(n+1),c(m+1);
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=m;i++){
        cin>>c[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i]+c[j]<=k){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

B. Bazoka and Mocha’s Array

题目链接

题意

有一个长度为$n$的数组$a$，你可以进行如下操作若干次:

  • 把数组拆成两部分$b$和$c$，满足$a=b+c$
  • 把原来的数组$a$替换成$c+b$，即$a:=c+b$
    问能否让数组a变成不降数组

分析

可以发现无论怎么选最后都等价于选前$n-1$和最后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
void solve(){
    int n;
    cin>>n;
    vector<int>vt(2*n+10);
    for(int i=1;i<=n;i++){
        cin>>vt[i];
    }
    for(int i=n+1;i<=2*n;i++){
        vt[i]=vt[i-n];
    }
    
    for(int i=1;i<=n;i++){
        int flag=1;
        for(int j=i+1;j<=i+n-1;j++){
            if(vt[j]<vt[j-1]){
                flag=0;
                break;
            }
        }
        if(flag){
            cout<<"Yes"<<endl;
            return;
        }
    }
    cout<<"No"<<endl;
}

C. Rudolf and the Ugly String

题目链接

题意

有一个字符串$s$，其中字符串map和pie被看作是坏的，为了不然$s$出现坏字符串，最少要删除多少个元素

分析

模拟即可，注意出现mapie时只要删去中间的p即可

代码

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
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=s+"      ";
    int ans=0;
    for(int i=0;i<n;i++){
        if(s.substr(i,5)=="mapie"){
            ans++;
            i+=4;
            continue;
        }
        else if(s.substr(i,3)=="map"){
            ans++;
            i+=2;
            continue;
        }
        else if(s.substr(i,3)=="pie"){
            ans++;
            i+=2;
            continue;
        }
    }
    cout<<ans<<endl;
}

D. Chamo and Mocha’s Array

题目链接

题意

有一个长度为$n$的数组$a$，你可以依次进行下面的操作若干次直到最后数组里的数字全都相等:

  • 选择$l$和$r$，满足$(1 \leq l \leq r \leq n)$
  • 记$[a_l,a{l+1}, \dots ,a{r}]$的中位数为x
  • 将$a_l,a_{l+1}, \dots ,a_r$变为x
    问数组里的数字最大是多少

分析

观察到如果一个数组里面一个数至少连续出现两次，那么这个数就能覆盖整个数组，那么我们怎么能把一个数连续出现两次呢。注意到相邻的两个数的中位数是两者的较小值，并且如果一个数比两边都小，那么可以是两边两个数的较小值(比如$[4，3，5]$)

代码

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
void solve(){
    int n;
    cin>>n;
    vector<int>vt(n+1);
    for(int i=1;i<=n;i++){
        cin>>vt[i];
    }
    int ans=-1;
    if(vt[1]<=vt[2]){
        ans=max(ans,vt[1]);
    }
    if(vt[n]<=vt[n-1]){
        ans=max(ans,vt[n]);
    }
    for(int i=2;i<=n-1;i++){
        if(vt[i]<=vt[i-1] || vt[i]<=vt[i+1]){
            ans=max(ans,vt[i]);
        }
    }
    for(int i=2;i<=n-1;i++){
        if(vt[i]<=vt[i-1] && vt[i]<=vt[i+1]){
            ans=max(ans,min(vt[i-1],vt[i+1]));
        }
    }
    cout<<ans<<endl;
}

E. Rudolf and the Ball Game

题目链接

题意

$n$个人围成一圈，有一个飞盘，开局在$x$手中，有$m$次指令，每次会给你飞的距离$r$和指令$c(c=1，2，?)$，问最后飞盘会在谁手中

分析

看数据范围发现可以暴力，我们每一轮存飞盘会在谁手中，存过一次的不用再存了。设当前飞盘在$k$中，那么

  • 顺时针飞r距离会传给$(k-1+r)\%n+1$
  • 逆时针飞r距离会传给$(k-1-r+n)\%n+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
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<pair<int,char> >vt(m+1);
    vector<int>flag(n+1);
    for(int i=1;i<=m;i++){
        cin>>vt[i].first>>vt[i].second;
    }
    queue<int>qu;
    qu.push(k);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            flag[j]=0;
        }
        int p=qu.size();
        for(int j=0;j<p;j++){
            int q=qu.front();
            qu.pop();
            if(vt[i].second=='?'){
                int o=((q-1+vt[i].first)%n+1);
                if(!flag[o]){
                    flag[o]=1;
                    qu.push(o);
                }
                o=((q-1-vt[i].first+n)%n+1);
                if(!flag[o]){
                    flag[o]=1;
                    qu.push(o);
                }
            }
            if(vt[i].second=='0'){
                int o=((q-1+vt[i].first)%n+1);
                if(!flag[o]){
                    qu.push(o);
                }
            }
            if(vt[i].second=='1'){
                int o=((q-1-vt[i].first+n)%n+1);
                if(!flag[o]){
                    qu.push(o);
                }
            }
        }
    }
    vector<int>ans;
    while(!qu.empty()){
        ans.push_back(qu.front());
        qu.pop();
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it<<" ";
    }
    cout<<endl;
}

F. Rudolf and k Bridges

题目链接

题意

有$n$行，每行$m$个数，在这一行中要造若干桥墩，桥墩之间的距离不能超过$d$，造桥墩的代价是$a_{i,j}+1$第1和第m个位置必须造桥墩，我们设第$i(1 \leq i \leq n)$行最小的代价为$x_i$，问连续的$k$个$x$的最小值

分析

每行相互独立，所以我们先一行一行考虑
首先我们考虑$dp$，$dp_i$表示修建第$i$个桥墩最少需要的代价，初始化$dp_1=1$很容易得到转移方程$$dp_i=min(dp_{i-d-1},dp_{i-d}, \dots dp_{i-1})+a_i+1$$如果直接去找最小值肯定会超时，我们考虑用单调队列(滑动窗口)优化。最后得到的结果存入数组$ans$中
接下来我们思考如何得到连续个$k$的结果的最小值，看数据范围完全可以暴力解决。这里给出另一种前缀和解法，其结果就是$$max(sum_i-sum_{i-k})(k \leq i)$$

代码

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
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
void solve(){
    int n,m,d,k;
    cin>>n>>m>>k>>d;
    d++;
    vector<vector<int> >vt(n+1,vector<int>(m+1) );
    vector<int>ans(n+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>vt[i][j];
        }
        vector<int>dp(m+1);
        dp[1]=1;
        deque<pair<int,int> >qu;
        qu.push_back({1,1});
        for(int j=2;j<=m;j++){
            if(j<=d+1){
                dp[j]=dp[1]+vt[i][j]+1;
                while(qu.back().second>dp[j]){
                    qu.pop_back();
                }
                qu.push_back({j,dp[j]});
            }
            else{
                if(dp[j-d-1]==qu.front().second){
                    qu.pop_front();
                }
                dp[j]=dp[qu.front().first]+vt[i][j]+1;
                while(qu.back().second>dp[j]){
                    qu.pop_back();
                }
                qu.push_back({j,dp[j]});
            }
        }
        ans[i]=dp[m];
    }
    vector<int>sum(n+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+ans[i];
    }
    int mn=1e18;
    for(int i=k;i<=n;i++){
        mn=min(mn,(ll)sum[i]-sum[i-k]);
    }
    cout<<mn<<endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

G. Paint the Tree

题目链接

题意

有一棵树，一开始所有节点都是白色的，有两个棋子$A，B$，$A$如果走过白色节点的就会把白色的节点染成蓝色$B$走过蓝色的节点会把节点染成蓝色，每一轮都是$A$先走$B$后走，问最少要几轮才能把全部节点染成蓝色

分析

$B$要走过$A$走过的路才能把节点染成蓝色，所以我们先让他们相遇，再把相遇的那个节点设为根节点$r$，相遇之后就没$A$什么事了，找到根节点后要遍历所有的节点并返回根节点，那么要走的步数就是$2*(n-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
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<vector<int>>vt(n+1);
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        vt[u].push_back(v);
        vt[v].push_back(u);
    }
    vector<int>flag(n+1);
    flag[a]=flag[b]=1;
    queue<pair<int,int> >qu;
    qu.push({a,1});
    qu.push({b,2});
    int r=-1;
    while(!qu.empty()){
        if(r!=-1){
            break;
        }
        auto q=qu.front();
        qu.pop();
        for(auto it:vt[q.first]){
            if(flag[it]==0 || (q.second==1 && flag[it]!=1)){
                flag[it]=q.second;
                qu.push({it,q.second});
            }
            if(q.second==2){
                if(flag[it]==1){
                    r=it;
                    break;
                }
            }
        }
    }
    queue<int>q;
    q.push(r);
    int dp=0;
    int ans=2*n-2;
    for(int i=1;i<=n;i++){
        flag[i]=0;
    }
    flag[r]=1;
    while(!q.empty()){
        dp++;
        int cs=q.size();
        while(cs--){
            int qq=q.front();
            q.pop();
            for(auto it:vt[qq]){
                if(!flag[it]){
                    flag[it]=1;
                    if(it==b){
                        ans+=dp;
                    }
                    q.push(it);
                }
            }
        }
    }
    ans-=(dp-1);
    cout<<ans<<endl;
}