[Codeforces Round #546 (Div. 2)题解]

Codeforces Round #546 (Div. 2)

D题题目读错把爷给整自闭了，此篇题解除了D都只有代码了

A. Nastya Is Reading a Book

做法

暴力

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n;
vector<int> ve;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        int l,r;scanf("%d%d",&l,&r);
        ve.push_back(r);
    }
    int page; scanf("%d",&page);
    int idx = lower_bound(ve.begin(),ve.end(),page) - ve.begin();
    printf("%d\n",n-idx);

    return 0;
}

B. Nastya Is Playing Computer Games

题解

找规律。 两个一组要六次。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    int n,a;
    scanf("%d%d",&n,&a);
    int ans = 0;
    if(n&1) ans+=3,ans += (n-1)*3;
    else ans += n*3;
    int mmin = min(n-a,a-1);
    ans += mmin;
    printf("%d\n",ans);


    return 0;
}

C. Nastya Is Transposing Matrices

题解

只有从左下到右上的有用。找规律。

我写得坐标变换有点绕。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 5e2+10;
int mx1[maxn][maxn], mx2[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx1[i]+j);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx2[i]+j);
    bool ans = true;
    n = max(n,m);
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,i+1){
            mmp[mx1[i-j][j]]++;
        }
        rep(j,0,i+1){
            mmp[mx2[i-j][j]]--;
            if(mmp[mx2[i-j][j]] == 0) mmp.erase(mx2[i-j][j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,n-i){
            mmp[mx1[n-j][i+j]]++;
        }
        rep(j,0,n-i){
            mmp[mx2[n-j][i+j]]--;
            if(mmp[mx2[n-j][i+j]] == 0) mmp.erase(mx2[n-j][i+j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }

    if(ans) puts("YES");
    else puts("NO");
    return 0;
}

D. Nastya Is Buying Lunch

题意

Nastya去排队，队伍中有这样一个规律。

• 已知有$m$对$(i,j)$，他们如果是相邻的话，并且$i$在$j$的前面，那么他们就可以调换位置。

问Nastya能够往前调换多少次位置，已知Nastya在最后一名。

题解

一开始我是看错题意，以为是可以隔空调换，直接想着用图论找一个环或者是找一个树来做。没有想到必须要相邻才能换，那么我们就可以这样想，我们的答案最多就只有$Nastya能够往前交换的人的数量$。之后我们尽可能的就是将不能交换的人往前面移动，能交换的人往后面移动。之后由于是一个一个相邻的同学移动，所以如果从前开始尽量往后移动的话，有可能会有的同学到达不到Nasyta的范围了。从后往前交换，那么我们就是将不可换的同学尽量地想前面推，之后如果前面的同学先交换到后面，那么对河Nasyta可以到达的来说，他也是一定能交换到Nasyta到达的点的。

举个栗子:

4 4

1 2 3 4

2 4

1 4

1 2

1 3

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 3e5+10;
int idx[maxn];
set<int> st[maxn];
int a[maxn];
int vis[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,n+1){
        int x; scanf("%d",&x);
        a[i] = x; idx[x] = i;
    }
    rep(i,0,m){
        int x,y; scanf("%d%d",&x,&y);
        st[x].insert(y);
        if(y == a[n]) vis[x] = 1;
    }
    per(i,1,n-1){
        if(vis[a[i]] == 0) continue;
        int t = i;
        while(t<n-1 && st[a[t]].find(a[t+1]) != st[a[t]].end()){
            swap(a[t],a[t+1]);
            t++;
        }
    }
    int ans = 0;
    per(i,1,n){
        if(vis[a[i]] == 0) break;
        ans++;
    }
    printf("%d",ans);
    return 0;
}