526互联

练习记录-cf-Educational Codeforces Round 152 (Rated for Div. 2)（A-D）

发布时间 2023-07-28 01:07:15作者: xishuiw

A. Morning Sandwich

题意：有面包片和火腿和芝士 问最多能组成几层三明治

题解：直接输出单考虑面包片和单考虑火腿和芝士的数量 取min

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
void solve(){
    int a,b,c;cin>>a>>b>>c;
    cout<<min({(a-1)*2+1,(b+c)*2+1})<<"\n";
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}
View Code

B. Monsters

题意：有很多怪物，每次砍m血，优先血多的，血一样多就优先序号小的，问死亡顺序

题解：想象一下过程，每个怪物最后都会被砍到1-m血，然后砍一刀就死了 就对血量取模，特判整除，然后sort排序即可

用优先队列模拟会tle

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  1e6+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
struct node{
    int k,id;
}N[MAXN]; 
bool bj(node a,node b){
    if(a.k!=b.k) return a.k>b.k;
    else return a.id<b.id; 
}
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>N[i].k;
        if(N[i].k%m!=0)
        N[i].k%=m;
        else N[i].k=m;
        N[i].id=i;
    }
    sort(N+1,N+1+n,bj);
    for(int i=1;i<=n;i++){
        cout<<N[i].id<<" ";
    }
    cout<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}
View Code

C. Binary String Copying

题意：给一个长度为n的01字符串，m个操作，给l,r，对字符串lr进行排序，问最后的结果有多少不同的字符串

题解：对于一次排序 如果排序为0010111 很明显，只有（3，4）的区间的被排序了的，其他区间都是无效，那么l=1，r=6和l=2，r=5其实是一样的。

那么我们考虑记录所有的有效排序区间，即会变化的区间，有效区间的左端点就是l开始从左往右边数的第一个1 右端点就是r开始从右往左数的第一个0。

如何快速查找这个0和1，我记录了所有0和1的pos 对这些位置进行lower_bound即可，1是要找大于等于l的第一个数，0是找小于等于r的第一个数 这个实现应该比较方便。

如果找到的pos1和pos0不满足pos1<pos0 就往set里面塞一个（-1，-1）,否则塞两个pos

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
//查找左往右第一个0 和右往左第一个1 
vector<int> v[2];
set<pair<int,int> > sz;
void solve(){
    int n,m;cin>>n>>m;
    sz.clear();
    v[0].clear();
    v[1].clear(); 
    string s;cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1') v[1].push_back(i);
        else v[0].push_back(i*-1);
    }
    v[0].push_back(0);
    v[1].push_back(inf);
    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        int pos1=*(lower_bound(v[1].begin(),v[1].end(),l));
        int pos0=*(lower_bound(v[0].begin(),v[0].end(),r*-1));
        pos0*=-1;
        if(pos1>=pos0||pos1>=r||pos0<=l){
            sz.insert({-1,-1});
        }
        else sz.insert({pos1,pos0});
    } 
    cout<<sz.size()<<'\n';
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}
View Code

D. Array Painting

题意：可以消耗1个cost把染色，已经染色的块如果值>0 可以-1，让周围的一个未染色块染色

题解：考虑对这些数字分块，记录成只有0的块和没有0的块，对于每个没有0的块，染色费用为1，如果里面至少有1个2，就可以对左右两边的全0块都染一个，否则选一个染。

我们枚举所有块，遇到全0块就看看左右的非0块能不能提供贡献，注意一下别算多了

wa23：考虑下0块的消耗是不是变成负的了

wa28：考虑下是不是多占用了一个1块 比如 4 1 0 1 0 这组数据 我当时出的3

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
//查找左往右第一个0 和右往左第一个1 
vector<int> v[2];
set<pair<int,int> > sz;
void solve(){
    int n,m;cin>>n>>m;
    sz.clear();
    v[0].clear();
    v[1].clear(); 
    string s;cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1') v[1].push_back(i);
        else v[0].push_back(i*-1);
    }
    v[0].push_back(0);
    v[1].push_back(inf);
    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        int pos1=*(lower_bound(v[1].begin(),v[1].end(),l));
        int pos0=*(lower_bound(v[0].begin(),v[0].end(),r*-1));
        pos0*=-1;
        if(pos1>=pos0||pos1>=r||pos0<=l){
            sz.insert({-1,-1});
        }
        else sz.insert({pos1,pos0});
    } 
    cout<<sz.size()<<'\n';
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}
View Code

这场A-D都是签到 有空补补后面的再补全（还有好多帐欠着呢