Codeforces Round 855 (Div. 3) A~E

A - Rudolf and the Ticket

鲁道夫要去拜访伯纳德，他决定乘坐地铁去找他。车票可以在接受两个硬币的机器上购买，这两个硬币的总和不超过 $k$ 。

鲁道夫有两个装硬币的口袋。左边口袋里有 $n$ 枚面值为 $b_1, b_2, \dots, b_n$ 的硬币。右边口袋里有 $m$ 枚面值为 $c_1, c_2, \dots, c_m$ 的硬币。他想从左边口袋和右边口袋各取出一枚硬币（共两枚）。

请帮助鲁道夫判断有多少种方法可以选择指数 $f$ 和 $s$ ，从而使 $b_f + c_s \le k$ .

水题，对任意一个口袋的硬币排序后直接遍历另一个口袋，upper_bound收集答案即可。

void solve(){
    CIN(n);CIN(m);CIN(k);
    vector<int> a,b;
    FOR(i,1,n){
        CIN(tmp);a.push_back(tmp);
    }
    FOR(i,1,m){
        CIN(tmp);b.push_back(tmp);
    }
    sort(b.begin(),b.end());
    ll ans=0;
    for(auto i:a){
        ans+=upper_bound(b.begin(),b.end(),k-i)-b.begin();
    }
    cout<<ans<<ET;
}

B - Rudolf and 121

Rudolf 有一个由 $n$ 个整数组成的数组 $a$ ，元素的编号从 $1$ 到 $n$ 。

在一次操作中，他可以选择索引 $i$ ( $2 \le i \le n - 1$ ) 并赋值：

$a_{i - 1} = a_{i - 1} - 1$
$a_i = a_i - 2$
$a_{i + 1} = a_{i + 1} - 1$

鲁道夫可以任意多次使用这个运算。任何索引 $i$ 都可以使用 0 次或更多次。

他能用这个运算使数组中的所有元素都等于零吗？

还是水题，贪心即可。注意不合法的判断。

void solve(){
    CIN(n);
    vector<int> a;a.push_back(0);
    FOR(i,1,n){
        CIN(tmp);a.push_back(tmp);
    }
    FOR(i,2,n-1){//一开始只写了a[i]<0，被卡了
        if(a[i-1]<0||a[i]<0||a[i+1]<0){cout<<"NO"<<ET;return;}
        a[i+1]-=a[i-1];
        a[i]-=2*a[i-1];
        a[i-1]=0;
    }
    FOR(i,1,n){
        if(a[i]!=0){cout<<"NO"<<ET;return;}
    }
    cout<<"Yes"<<ET;
}

C - Rudolf and the Ugly String

题意：最少删除几次可以把map和pie全删掉？

暴力就能过。

void solve(){
    CIN(n);
    string s;cin>>s;s=" "+s;
    if(n<3){
        cout<<0<<ET;return;
    }
    ll mapc=0,piec=0,mapie=0;
    FOR(i,3,n){
        if(s[i-2]=='m'&&s[i-1]=='a'&&s[i]=='p')mapc++;
        if(s[i-2]=='p'&&s[i-1]=='i'&&s[i]=='e')piec++;
    }
    FOR(i,5,n){
        if(s[i-4]=='m'&&s[i-3]=='a'&&s[i-2]=='p'&&s[i-1]=='i'&&s[i]=='e')mapie++;
    }
    cout<<mapc+piec-mapie<<ET;
}

翻到的别人的代码(按自己的马蜂抄了一遍)：

void solve(){
    CIN(n);
    string s;cin>>s;s=" "+s;
    if(n<3){cout<<0<<ET;return;}
    ll ans=0;
    FOR(i,1,n-2)
        if(s.substr(i,3)=="map"||s.substr(i,3)=="pie"){ans++;i+=2;}
    cout<<ans<<ET;
}

D - Rudolf and the Ball Game

超级阅读题，看懂了就知道其实很简单，因为记不清方向，只记得传递间隔，问你最后这个球可能在哪些人手上，显然在每次忘记时分裂成两个方向，分开统计就行。自然而然就是DFS（写BFS应该也行）。有枝你不剪？记得剪枝。

bool vis[1002][1002];
void solve(){
    CIN(n);CIN(m);CIN(i);
    map<int,bool> could;
    vector<pair<int,char>> a;
    FOR(i,1,m){
        CIN(tmp);char c;cin>>c;
        a.push_back({tmp,c});
    }
    memset(vis,0,sizeof vis);
    auto dfs=[&](auto dfs,int now,int cnt){
        now--;
        now=(now%n+n)%n;//经典二连取模，保证now非负且在0到n内
        now++;
        if(vis[cnt][now])return;
        vis[cnt][now]=1;
        if(cnt==0){
            could[now]=1;
            return;
        }
        if(a[m-cnt].second=='0'){
            dfs(dfs,(now+a[m-cnt].first-1)%n+1,cnt-1);
        }else if(a[m-cnt].second=='1'){
            dfs(dfs,(now-a[m-cnt].first-1)%n+1,cnt-1);
        }else{
            dfs(dfs,(now+a[m-cnt].first-1)%n+1,cnt-1);
            dfs(dfs,(now-a[m-cnt].first-1)%n+1,cnt-1);
        }
    };
    dfs(dfs,i,m);
    cout<<could.size()<<ET;
    //for(auto &[i,v]:could)cout<<i<<"]";
    FOR(i,1,n){
        if(could.count(i))cout<<i<<' ';
    }
    cout<<ET;
}

E - Rudolf and k Bridges

伯纳德喜欢拜访鲁道夫，但他总是迟到。问题是伯纳德必须乘渡船过河。鲁道夫决定帮助他的朋友解决这个问题。

这条河是由 $n$ 行和 $m$ 列组成的网格。第 $i$ 行和第 $j$ 列的交点包含数字 $a_{i,j}$ –相应单元格的深度。第一列和最后列中的所有单元格都与河岸相对应，因此它们的深度为 $0$ 。

河流可能是这样的。

鲁道夫可以选择第 $(i,1), (i,2), \ldots, (i,m)$ 行，并在上面建造一座桥。在该行的每个单元格中，他都可以为桥安装一个支架。在第 $(i,j)$ 格安装支架的成本为 $a_{i,j}+1$ 。安装支架必须满足以下条件：

必须在单元格 $(i,1)$ 中安装一个支架；
单元格 $(i,m)$ 中必须安装一个支架；
任何一对相邻支架之间的距离不得大于** $d$ 。支架 $(i, j_1)$ 和 $(i, j_2)$ 之间的距离为 $|j_1 - j_2| - 1$ 。

只建一座桥是很无聊的。因此，鲁道夫决定在河上连续行建造 $k$ 座桥，即选择一些 $i$ （ $1 \le i \le n - k + 1$ ），独立建造 $k$ 座桥。( $1 \le i \le n - k + 1$ ) 并分别在每一行的 $i, i + 1, \ldots, i + k - 1$ 上建一座桥。帮助鲁道夫最小化安装支架的总成本。

阅读题，读懂了就知道直接对每行都跑一次单调队列优化DP，再前缀和查最小答案就行了。(特别注意那个连续，要是我注意到了，估计这场就能过5题了，可惜了，最气人的一场。)

struct P{
    ll i,v;
    bool operator<(const P &b)const{
        if(v==b.v)return i<b.i;
        return v>b.v;
    }
}t;
void solve(){
    CIN(n);CIN(m);CIN(d);CIN(k);
    vector<ll> ans;ans.push_back(0);
    FOR(i,1,n){
        vector<ll> a;a.push_back(0);
        FOR(j,1,m){
            CIN(tmp);
            a.push_back(tmp);
        }
        priority_queue<P> q;
        q.push({1,1});
        FOR(i,2,m){
            while(!q.empty()&&k<i-q.top().i-1)q.pop();
            //cout<<q.top().v<<"]";
            if(i!=m)q.push({i,a[i]+1+q.top().v});
            else ans.push_back(a[i]+1+q.top().v);
        }
        //cout<<ET;
    }
    ll anss=1e18;
    vector<ll> pre;pre.push_back(0);
    FOR(i,1,n)pre.push_back(pre[i-1]+ans[i]);
    FOR(i,d,n)anss=min(anss,pre[i]-pre[i-d]);
    //sort(ans.begin(),ans.end());//reverse(ans.begin(),ans.end());
    //FOR(i,0,d-1)anss+=ans[i];
    cout<<anss<<ET;
}

附录

这里贴上头部定义和main函数部分：

#include<iostream>
#include<vector>
#include<bits\stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
//没有C++20就不能用ranges了
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

//solve函数代码

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //pre();
    CIN(t);while(t--)
    solve();
    return 0;
}

Codeforces Round 933 (Div. 3)