526互联

练习记录-cf-Educational Codeforces Round 147 （A-D）

发布时间 2023-04-21 01:56:36作者: xishuiw

打的很烂的一场 C想了很久 D的贪心没有贪好 赛后一小时补起来了  谁是nc 我是nc！

A. Matching

问有多少种情况能匹配 就计算？的个数 x10x10......

如果第一个是？ 那么就是9x10x10...

如果第一个是0 不能有前导0 就输出0 

#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;
const ll INF =0x3f3f3f3f3f3f3f3f;
int f[2];
void solve(){
    string s;cin>>s;
    f[0]=0,f[1]=0;
    int n=s.length();
    int flag=0,res=0,cnt=0;
    int ans=1;
    for(int i=0;i<n;i++){
        if(s[i]=='?'){
            if(flag==0) {
                
                res=1;
                
            }cnt++;flag=1;
            f[0]=f[0]*10+9;
        }
        else{
            flag=1;
            int k=s[i]-'0';
            f[0]=f[0]*10+k;
        }
    }
    for(int i=0;i<cnt;i++){
        if(res) ans*=9,res--;
        else ans*=10;
    }
    if(f[0]==0||s[0]=='0') ans=0;
    cout<<ans<<"\n";
}
signed main(){
    close;
    int t;cin>>t;
    while(t--) 
    solve();
}
View Code

 

B. Sort the Subarray

题目没看清 这个题就是问你 执行一次操作 使第一个数组等于第二个  问选择区间最长的区间

以为可以执行很多次 但是其实只有一次 因此上下不同的数字肯定要丢上去 所以我直接记录第二个数组的非递减长度，如果上下不一样 flag=1 才能取max 如果非递减结束 flag=0 防止后续影响

#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;
const ll INF =0x3f3f3f3f3f3f3f3f;
int a[MAXN],b[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    int maxs=0,cnt=1,r;
    int flag=0;
    for(int i=2;i<=n;i++){
        if(a[i]!=b[i]) flag=1;
        if(a[i]>=a[i-1]) {
            cnt++;
        }
        else{
            cnt=1;
            flag=0;
        }
        if(cnt>maxs&& flag){
            maxs=cnt;
            r=i;
        }
    }
    cout<<r-maxs+1<<" "<<r<<"\n";
}
signed main(){
//    close; 
    int t ;cin>>t;
    while(t--)
    solve();
}
View Code

 

 

C. Tear It Apart

想了很久怎么搞 但实际上打个表就知道怎么搞了。。。

设某个字符char切割后的字符串有至少两个区间（反正取一个区间的必不可能是最优解，消不掉而且最大 不用管） 那么 区间消的次数肯定是以最大的为准

两个区间最大的为1  只需要一次就行

　　2---2

　　3---2

　　4---3

　　5---3

　　........

　　8----4

我们发现 这个最大值都是log2（n）+1 

然后就可以直接写了

#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;
const ll INF =0x3f3f3f3f3f3f3f3f;

int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    string s;
    cin>>s;
    int n=s.length();
    int ans=inf;
    for(char i='a';i<='z';i++){
        int cnt=0,maxs=0;
        for(int j=0;j<n;j++){
            if(s[j]==i) cnt=0;
            else cnt++;
            maxs=max(cnt,maxs); 
        }
        ans=min(ans,maxs);
    }
    if(ans==0) cout<<0<<"\n";
    else{
        int k=log2(ans);
        cout<<k+1<<"\n";
    }
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}
View Code

 

D. Black Cells

给定很多个不相交的区间 从0开始走 往无限大走，可以执行3个操纵 1-往右走一步 2-按下shift 开始标记路径 3-松开shift 结束标记

只有在给定区间 才能按下/松开shift

这个题的关键在于长度为1的区间 下面给出一个例子方便理解

9 7

1 3 5 7 9 11 13 15 18

1 3 5 7 9 11 13 16 25

我们需要取的是7个 前面1刚好有7个 但是这样显然不是最优解 显然取 15-16，18-22才是最优解

因为在黑色格子后面还能连续的时候 往后走一位只是让总数+1 但是去掉一个前面的1会让总数-2 会赚一个

我的思路就是 枚举每一个区间 当这个区间为结束区间的时候 需要的步数是多少 取最大值即可

显然的 区间长度>=2就必须取上 后面不管怎么样都是赚 就从前往后扫每个区间 如果加上这个区间后的总数(res)>=需要的数(m)

那么我们相当于有res-m的空挡可以用来交换前面的1 此时指针结束的位置就是 r(右端点)-res+m+min(res-m,cnt);

换掉多少个1 就给记录 取区间个数的变量(sum) -2  给剩余可交换的减少这么多

再往后遍历区间 因为1特别多的情况下 可能出现取很多个后面的区间仍然是赚的情况 所以不能break

代码比较乱 如下 中间传vector是之前看错题目 以为区间相交 无视就行orz

#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;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
struct node{
    int l,r;
}a[MAXN];
vector<pair<int,int> > sz;
bool bj(node p,node q){
    if(p.l!=p.l) return p.l<q.l;
    else return p.r<q.r;
}
void solve(){
    int n,m;cin>>n>>m;
    sz.clear();
    for(int i=0;i<n;i++){
        cin>>a[i].l;
    }
    for(int i=0;i<n;i++){
        cin>>a[i].r;
    }
    sort(a,a+n,bj);
//    int last=-2;
    for(int i=0;i<n;i++){
        int ll=sz.size();
    //    if(a[i].l==last+1){
    //        sz[last-1].second=a[i].r;
    //        last=a[i].r;
    //    }
    //    else {
            sz.push_back({a[i].l,a[i].r});
    //        last=a[i].r;
    //    }
    }
    int cnt=0,res=0,sum=0,ans=inf;
    for(auto i:sz){
        int l=i.first,r=i.second;
        if(r-l==0) cnt++;//记录个数
        res+=r-l+1;//目前区间的长度和
        sum+=2; 
        if(res>=m){
            int k=res-m;
            k=min(k,cnt);int last;
            last=r-res+m+k;//记录结束点
            cnt-=k;//肯定要减去 因为这个区间必须要取（如果这个是1 不影响） 才能往后
            sum-=2*(k);
            ans=min(ans,sum+last);
            res=m;//防止之后的操作出问题，要变回m 计算下个区间
        }
    }
    if(ans==inf) ans=-1;
    cout<<ans<<"\n";
}
signed main(){
    int t;cin>>t;
    while(t--)
    solve();
}
View Code

E之后再补 我是菜鸡 写错轻喷 感谢大佬能看完ORZ