Codeforces Round #401 (Div. 2) A B C D E

Codeforces Round #401 (Div. 2)

第一套。

刷100套cf，加油加油！！！

ps：写题解时没看题，题意可能有错

A:Shell Game

题意：三个杯子，其中一个下面有东西，操作：先交换左和中间，再交换右和中间。给出n次操作后的状态，东西在x（0,1，或2）位置，让你求出初始东西在哪个位置。

0 1 2

1 0 2

1 2 0

2 1 0

2 0 1

0 2 1

0 1 2

周期为6

#include<bits/stdc++.h>
using namespace std;

int n,x;
int main(){
    cin>>n>>x;
    n=n%6;
    if(n==1&&x!=2) x=x^1;
    else if(n==2){
        if(x==2) x=0;
        else if(x==1) x=2;
        else x=1;
    }
    else if(n==3){
        x=2-x;
    }
    else if(n==4){
        if(x==0) x=2;
        else if(x==1) x=0;
        else if(x==2) x=1;
    }
    else if(n==5){
        if(x!=0){
            x=(x)%2+1;
        }
    }
    cout<<x<<"
";
    return 0;
}

B:Game of Credit Cards

题意：给你两个序列，任意顺序，求序列1中元素最少有多少个大于序列2中元素， 求序列2中元素最多有多少个大于序列1中元素，

#include<bits/stdc++.h>
using namespace std;

int n;
char str1[2000],str2[2000];
int main(){
    scanf("%d",&n);
    scanf("%s%s",str1,str2);
    sort(str1,str1+n);
    sort(str2,str2+n);
    int ans=0;
    int j=n-1;
    for(int i=n-1;i>=0;i--){
        if(str1[i]>str2[j]){
            ans++;
            j++;
        }
        j--;
    }
    int res=0;
    j=0;
    for(int i=0;i<n;i++){
        if(str2[i]>str1[j]){
            res++;
        }else{
            j--;
        }
        j++;
    }
    printf("%d
%d
",ans,res);
    return 0;
}

C:Alyona and Spreadsheet

 题意：给你一个矩阵，让你判断从l行到r行之间，是否存在一列是不递减的

从每一列开始遍历，第i列： st表示连续序列的起点，if 第j行值大于等于j-1行，那么pre[j]=st（从st到j是连续的）,否则 st=j（不连续，从j开始找连续序列）

#include<bits/stdc++.h>
using namespace std;


int n,m,c;
int k;

int main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    int a[n+10][m+10];
    int pre[n+10];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        pre[i]=i;
    }
    for(int i=0;i<m;i++){
        int st=0;
        pre[0]=0;
        for(int j=1;j<n;j++){
            if(a[j][i]>=a[j-1][i]){
                pre[j]=min(st,pre[j]);
            }else{
                st=j;
            }
        }
    }
    cin>>k;
    while(k--){
        int l,r;
        cin>>l>>r;
        if(pre[r-1]<=l-1) cout<<"Yes
";
        else cout<<"No
";
    }
    return 0;
}

D:Cloud of Hashtags

给你n行字符串，让你删除一些字母，让它们变成按字典序排序，删除的字母尽量少

贪心，从后往前遍历，字符串从尾往头删，将倒数第二个字符串的尾部字母删掉，使其小于等于倒数第一个

#include<bits/stdc++.h> 
using namespace std;
const int N=5e5+100;

int n;
char c;
string str[N];

int solve(int x,int i){
    string s(str[i-1],0,x);
    
    if(s>str[i]) return 1;
    else return 0;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>c;
        cin>>str[i];
    }
    /*for(int i=0;i<n;i++){
        cout<<str[i]<<endl;
    }*/
    for(int i=n-1;i>=1;i--){
        int l=0,r=max(str[i].length(),str[i-1].length());
        int mid;
        while(l<=r){
            mid=(l+r)/2;
            if(solve(mid,i)) r=mid-1;
            else l=mid+1;
        }
        //cout<<r<<"..
";
        str[i-1]=string (str[i-1],0,r);
        //cout<<str[i-1]<<"..
";
    }
    for(int i=0;i<n;i++){
        cout<<"#"<<str[i]<<endl;
    }
    return 0;
}

E:Hanoi Factory

我们对这些圆盘先按照b从大到小排序,如果b相同,那么就要按照a从大到小排序,这是为什么呢？

这是因为如果有b相同的我们要优先使用那个a大的,因为你想越往上b越小,你要想让b>a的话那么就要让a也小,这样才能让h更大一些

if 出现一个b<=塔上环的a 

那么说明剩下所有的环都不能再堆在塔上面了，

现在有两个选择，1将剩下的舍弃，2 将塔上使b<=a的环舍去，再往上加环

当然两种方式择优，先记下目前的最大高度max，高度ans，将上面的环舍去ans - =h，直至b>塔上环的a，加环ans+=h’，取max和ans最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+100;

int n;
struct ring{
    int a,b,h;
    bool operator <(const ring &r) const{
        if(b!=r.b)return b>r.b;
        else  return a>r.a;
    }
}ri[N];

stack<ring> s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>ri[i].a>>ri[i].b>>ri[i].h;
    }
    sort(ri,ri+n);
    ll res=(ll)ri[0].h,ans=res;
    s.push(ri[0]);
    for(int i=1;i<n;i++){
        while(!s.empty()&&ri[i].b<=s.top().a){
            res-=s.top().h;
            s.pop();
        }
        res+=(ll) ri[i].h;
        ans=max(ans,res);
        s.push(ri[i]);
    }
    cout<<ans<<"
";
    return 0;
}