【CodeForces】Round#614

前言:

还是太菜了。同样的想法,写的比别人丑还复杂,说明自己的功力还是不到家。

dp训练还有那么多没有做。

A. ConneR and the A.R.C. Markland-N

题意:

有n楼,每一楼都有餐馆,你现在在s楼,有k个餐馆关门了,问最少移动几层能到开门的餐馆

思路

直接搜

代码
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;

int main(){
int t,n,s,k;
cin >> t;
while(t--){
map<int,int>vis;
cin >> n >> s >> k;
for(int i = 0;i < k;i++){
int a;cin >> a;
vis[a] = 1;
}
int ans = 0;
while(1){
if(ans+s <= n && vis[ans+s] == 0){
break;
}
if(s-ans >= 1 && vis[s-ans] == 0){
break;
}
ans++;
}
cout << ans << endl;
}
}

再附一份别人的代码。

别人的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<set>
using namespace std;
int main()
{
int t,n,a,k,s;
cin>>t;
while(t--)
{
set<int>set;
cin>>n>>s>>k;
for(int i=1;i<=k;i++)
cin>>a,set.insert(a);
int ans=0;
while((set.count(s+ans)||s+ans>n)&&(set.count(s-ans)||s<=ans)) ans++;
cout<<ans<<endl;
}
}

B. JOE is on TV!

题意

有 n 个人,若每轮淘汰 s 人,则获得 s/n 元收益,问如何淘汰所有其他人,获得最高收益

思路

一个一个淘汰

$ans = \sum_{i = 1}^n \dfrac 1 i$

代码
1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
double sum = 0.0;
for(int i = 1;i <= n;i++){
sum += 1.0/i;
}
cout << sum << endl;
}

C. NEKO’s Maze Game

题意

有一个2*n的迷宫, 你的目的是从(1,1) 走到(2,n)
有 q 个时刻,每个时刻都有一个方块 变化状态, 即从可行变成不可行,从不可行变成可行,对于每个时刻,询问能否到达

思路

维护一个 cnt,cnt是形成阻挡的对数,例如
(1,5)增加一个方块,若(2,4),(2,5),(2,6)三个位置存在方块,则cnt加1,去除方块时同理,
若 cnt 大于 0 ,则无法到达,否则可以到达

代码
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
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;

int n, q;
const int maxn = 1e5 + 10;
int Mp[3][maxn];
int Bt[3][maxn];
int cnt;

int main() {
cin >> n >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
Mp[a][b] ^= 1;
if (Mp[a][b] == 1) { //add
if (Mp[((a - 1) ^ 1) + 1][b - 1] == 1){
cnt++;
Bt[a][b]++;
Bt[((a - 1) ^ 1) + 1][b - 1]++;
}
if (Mp[((a - 1) ^ 1) + 1][b] == 1){
cnt++;
Bt[a][b]++;
Bt[((a - 1) ^ 1) + 1][b]++;
}
if (Mp[((a - 1) ^ 1) + 1][b + 1] == 1) {
cnt++;
Bt[a][b]++;
Bt[((a - 1) ^ 1) + 1][b + 1]++;
}
}
else { //remove
if (Mp[((a - 1) ^ 1) + 1][b - 1] == 1){
cnt--;
Bt[a][b]--;
Bt[((a - 1) ^ 1) + 1][b - 1]--;
}
if (Mp[((a - 1) ^ 1) + 1][b] == 1){
cnt--;
Bt[a][b]--;
Bt[((a - 1) ^ 1) + 1][b]--;
}
if (Mp[((a - 1) ^ 1) + 1][b + 1] == 1){
cnt--;
Bt[a][b]--;
Bt[((a - 1) ^ 1) + 1][b + 1]--;
}
}
if (cnt > 0) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
}

我又去找了别人的代码,我就知道自己的代码写丑了。惨

代码
1
2
3
4
5
6
7
8
9
10
11
n, q = (int(i) for i in input().split())
lava = [0] * (n*2)
pairs = 0
for i in range(q):
r, c = (int(j)-1 for j in input().split())
j = c*2+r
lava[j] ^= 1
for k in (j-2, j, j+2):
if 0<=k<2*n and lava[k^1]:
pairs += lava[j]*2-1
print('Yes' if pairs == 0 else 'No')

思路是一样的,但是别人的代码真的简洁又漂亮

D. Aroma’s Search

我昨天被这道题气死了,本来可以直接拿下的,那时候才过了200人,唉。菜是原罪

题意:

你跑到了系统空间里,认为是一个无限的二维平面,你在一个初始位置,你每挪动一格耗费一能量,有 t 能量,有无限个数据节点在 OS 空间里,第一个是 (x0,y0),每后一个数据节点对前一个做线性变换,系数是 ax,bx,ay,by

有一个重要的信息就是数据范围。
在这里插入图片描述

思路

注意到,ax,ay 在 [2,100] 的范围内,所以 x 坐标是指数增长,所以在 [2e16,2e16]范围内,不超过 100 个点,可以直接处理出范围内的这些点。
策略一定是先到某个数据点,然后一直向一个方向前进(前或者后),一直更新最大值即可

代码
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
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

#define int long long

int x0,y0,ax,ay,bx,by,xs,ys,t;
const int maxx = 2e16+10;

int x[100];
int y[100];
int cnt;
int vis[100];
int res;
void init(){
x[++cnt] = x0;y[cnt] = y0;
int nowx = x0, nowy = y0;
while(nowx <= maxx && nowy <= maxx){
x[++cnt] = nowx*ax + bx;
y[cnt] = nowy*ay + by;
nowx = x[cnt];
nowy = y[cnt];
}
}

int dis(int i,int j){
int dx = abs(x[i]-x[j]);
int dy = abs(y[i]-y[j]);
return dx + dy;
}

signed main(){
cin >> x0 >> y0 >> ax >> ay >> bx >> by;
cin >> xs >> ys >> t;
init();
for(int i = 1;i <= cnt;i++){

int mt = t - (abs(x[i]-xs) + abs(y[i]-ys));
if(mt < 0)continue;
int id = i;
int ans = 0;
while(mt >= 0){
ans++;
id--;
if(id < 1)break;
mt -= dis(id,id+1);
}
res = max(res,ans);

ans = 0;mt = t - (abs(x[i]-xs) + abs(y[i]-ys));
id = i;

while(mt >= 0){
ans++;
id++;
if(id > cnt)break;
mt -= dis(id,id-1);
}
res = max(res,ans);
}
cout << res << endl;
}

今天仔细想了一下,其实不需要这样一步一步的走,我忽略了一点:这里的距离不是直线距离

所以直接找就行了

别人的代码
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
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n=1,x[10000],y[10000],ax,bx,ay,by,t;

int d(int i, int j){
return abs(x[i]-x[j])+abs(y[i]-y[j]);
}

main()
{
cin >> x[1] >> y[1] >> ax >> ay >> bx >> by;
cin >> x[0] >> y[0] >> t;
for(int i=2; ; ++i){
x[i]=x[i-1]*ax+bx;
y[i]=y[i-1]*ay+by;
if(x[i]>2e16 || y[i]>2e16)break;
n=i;
}
int res=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(d(0,i)+d(i,j)<=t)res=max(res,abs(i-j)+1);
cout << res;


}