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

Codeforces Round #546 (Div. 2)

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

A. Nastya Is Reading a Book

做法

暴力

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}