Codeforces Round #546 (Div. 2)-蒲公英云

Codeforces Round #546 (Div. 2)

A. Nastya Is Reading a Book（水）

遍历一下，找到k所在的章数，总的减去已经读的……

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct node{
    int a,b;
}Q[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>Q[i].a>>Q[i].b;
    }
    int k;
    cin>>k;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(Q[i].a<=k&&Q[i].b>=k){
            ans=i;
            break;
        }
    }
    cout<<n-ans+1<<endl;
    return 0;
}

B. Nastya Is Playing Computer Games

贪心，先走到（最左，或者最右）端点，比较走到哪个端点比较小，然后再考虑扔和捡，（比如现在走到最左边）第一次肯定要扔到有一块石头的（假设扔到第二个位置），然后把第二个位置的石头都扔到第一个位置，然后把所有的石头都扔到已经走过的地方；

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int main(){
    int n,k;
    cin>>n>>k;
    if(n==1){
        cout<<"2"<<endl;
        return 0;
    }
    else if(n==2){
        cout<<"6"<<endl;
        return 0;
    }
    int ans=min(k-1,n-k);
    ans+=6;
    n-=2;
    for(int i=1;i<=n;i++)ans+=3;
    cout<<ans<<endl;
    return 0;
}

C. Nastya Is Transposing Matrices

题意：给你两个矩阵，问你是否可以根据每个子矩阵的主对角线置换来得到相同的矩阵；

me：想到了每个子矩阵的主对角线应该相同，但是不会处理……

look other：类似桶排序，用map来离散化存值；

#include <bits/stdc++.h>
using namespace std;
const int maxn=550;
int n,m;
int a[maxn][maxn],b[maxn][maxn];
map<int,int>mp[1010];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            mp[i+j][a[i][j]]++;
        }
    }
    int flag=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
            if(mp[i+j][b[i][j]]<=0){
                flag=0;
            }
            else mp[i+j][b[i][j]]--;
        }
    }
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

D. Nastya Is Buying Lunch

题意：有一个队列，你现在在最后一个，每个人都有一个数，当u，v相邻时可以交换u，v，问你最多能前进几个位置；

当时看错了，以为不相邻也可以交换，导致样例都没理解清楚，就结束了；

解：贪心，从后面一直往前更新，当这两个数满足相邻的时候就可以换；

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m,a[maxn],b[maxn];
vector<int>g[maxn];
bool cmp(int u,int v){
    return b[u]<b[v];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=n;i>0;i--){
        int u=a[i];
        sort(g[u].begin(),g[u].end(),cmp);
        for(auto it:g[u]){
            if(b[it]==b[u]+1){
                b[u]++;
                b[it]--;
            }
        }
    }
    cout<<n-b[a[n]]<<endl;
    return 0;
}