Codeforces Round 855 (Div. 3) A~E

A. Is It a Cat?

题意：判断是不是猫叫，直接模拟即可

#include<bits/stdc++.h>
using ll=long long;
using 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 PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

void solve(){
    CIN(n);
    bool m=0,e=0,o=0,w=0;
    char lst='-';//记录上一个音节
    bool no=0;
    FOR(i,1,n){
        char tmp;cin>>tmp;
        if(no)continue;
        if(tmp!='m'&&tmp!='e'&&tmp!='o'&&tmp!='w'&&
        tmp!='M'&&tmp!='E'&&tmp!='O'&&tmp!='W'){//特判不属于猫的用词直接NO
            cout<<"NO"<<ET;
            no=1;
        }
        if((tmp=='m'||tmp=='M')){
            if(!(lst=='-'||lst=='m')){
                cout<<"NO"<<ET;
                no=1;                
            }else {lst='m';continue;}
        }
        if((tmp=='e'||tmp=='E')){
            if(!(lst=='m'||lst=='e')){
                cout<<"NO"<<ET;
                no=1;
            }else {lst='e';continue;}
        }
        if((tmp=='o'||tmp=='O')){
            if(!(lst=='e'||lst=='o')){
                cout<<"NO"<<ET;
                no=1;                
            }else {lst='o';continue;}
        }
        if((tmp=='w'||tmp=='W')){
            if(!(lst=='o'||lst=='w')){
                cout<<"NO"<<ET;
                no=1;                
            }else {lst='w';continue;}
        }
    }
    if(no)return;
    if(lst!='w')cout<<"NO"<<ET;//如果最后一次不是w，就不是完整猫叫
    else cout<<"YES"<<ET;
    return;
}

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

B. Count the Number of Pairs

题意：给你一个字符串，将同类字母的大小写凑一对可得一分，给你至多k次大小写转换机会，问你分数最大是多少

直接先统计每种字符出现次数，然后遍历配对算分，最后计算剩下未配对的最多能贡献多少即可，答案即为：$\sum \min(c_i,C_i)+\min(k,\sum \frac{abs(c_i-C_i)}{2})$

#include<bits/stdc++.h>
using ll=long long;
using 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 PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

int cnt[128];
void solve(){
    CIN(n);CIN(k);
    memset(cnt,0,sizeof cnt);
    FOR(i,1,n){
        char tmp;cin>>tmp;
        cnt[tmp]++;
    }
    ll sc=0;ll un=0;
    FOR(c,'a','z'){
        sc+=min(cnt[c],cnt[c+'A'-'a']);
        un+=(abs(cnt[c]-cnt[c+'A'-'a'])>>1);
    }
    cout<<sc+min(k,un)<<ET;
}

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

C. Powering the Hero

题意：有一副由 n 张牌组成的扑克牌，每张牌都有自己的牌力。牌有两种：

英雄牌，这种牌的威力总是等于 0
奖励牌，这种牌的牌力总是正数。

您可以对这副牌进行以下操作：

从牌组顶端抽取一张牌；
如果这张牌是奖励牌，你可以把它放在奖励牌组的顶层或丢弃；
如果这张牌是英雄牌，则将奖励卡组最上面张牌的威力加到他的威力上(如果卡组不是空的)，然后将英雄加到你的军队中，用过的奖励丢弃。

您的任务就是利用这些行动来组建一支总战力最大的军队。

解：直接优先队列，遇到一次0就弹出队首加到答案里，因为在队列非空的情况下，玩家总是有能力将队列里的值从大到小收集依次收集。

#include<bits/stdc++.h>
using ll=long long;
using 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 PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

void solve(){
    CIN(n);
    priority_queue<int,vector<int>,less<int>> q;
    ll sc=0;
    FOR(i,1,n){
        CIN(tmp);
        if(tmp==0){
            if(!q.empty()){
                sc+=q.top();q.pop();
            }
        }else{
            q.push(tmp);
        }
    }
    cout<<sc<<ET;
}

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

D. Remove Two Letters

题意：给定字符串s，任意删除连续的两个字符，能构成多少种不同串？

以指针 $i$ 从左到右 [3, n] 扫描一遍，找到$s_i \neq s_{i-2}$就统计一次，因为当字符串每存在这样相异的字符时，可以保证擦除$[i-1,i]$和$[i-2,i-1]$所产生的字符串肯定相异，而且从左到右滑动保证了每两对字符串相异的位置不同，靠这样统计的相异字符串是两两不同的

#include<bits/stdc++.h>
using ll=long long;
using 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 PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};

void solve(){
    CIN(n);ll ans=1;
    string st;cin>>st;st=" "+st;
    FOR(i,3,n){
        ans+=(st[i]!=st[i-2]);
    }
    cout<<ans<<ET;
}

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

E. Unforgivable Curse

题意：给你两个字符串，你可以对其中一个字符串进行任意次下标差为k或k+1的字符交换（$s_i\leftrightarrow s_{i+k}$），问你是否能把一个字符串变成另一个。

先特判边缘条件:

$s1=s2$直接YES
用两临时字符串缓存后直接排序，再判断两者是否相等，如果不等说明没办法完成目标变换，输出NO
如果排序后字符串相等，但是$k>n$，那么就没法对字符串做任何修改，因此输出NO
如果排序后字符串相等，且$k=1$，那么一定可以完成变化，输出YES

再针对一般情况设计算法，我们考虑任意字符串，当固定左端$s_i$时，其右端可达$s_{i+k}$或$s_{i+k+1}$，换句话说，$s_{i+k}和s_{i+k+1}$是可互换的。

接下来让$s_i$在字符串上随意滑动，易知：

当$k> n-k$时，$[k,n]$这个区间内的字符可任意排序，同理我们也能证明$[1,n-k]$也可任意排序。又因为左右区间的元素可通过这个跨度为$k$或$k+1$的交换桥互通，所以对于这两个区间，判断能否排序就和前面的方法一样，把他们连接成一个子串然后排序判相等。

但我们也会注意到，字符串上存在一段区间是交换桥不可达的，我们称其为“恒区间”。这段区间因为没法排序，所以在判断答案的时候还要判断两个恒区间是否相等。

当$k< n-k$时，左区间与右区间把中间的恒区间夹没了，这种情况下字符串可任意排序，直接输出YES即可。

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
#define ET '\n'
#define CIN(a) ll a;cin>>a;
string ANS[2]={"NO","YES"};

void solve(){
    CIN(n);CIN(k);
    string s1,s2,s1_,s2_;
    cin>>s1>>s2;
    //特判
    if(s1==s2){cout<<"YES"<<ET;return;}
    s1_=s1,s2_=s2;
    sort(s1_.begin(),s1_.end());sort(s2_.begin(),s2_.end());
    if(s1_!=s2_){cout<<"NO"<<ET;return;}
    if(k>n){cout<<"NO"<<ET;return;}
    //中间串判断
    cout<<ANS[2*k<=n||(s1.substr(n-k,2*k-n)==s2.substr(n-k,2*k-n))]<<ET;
}

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

F和G

有时间写写

Codeforces Round 855 (Div. 3)