Educational Codeforces Round 161 (Rated for Div. 2)
C. Closest Cities
题意
有n个城市， 他们分别在坐标轴上的点$a_1,a_2…,a_n$ ，我们定义从城市i到城市j之间的花费的金币为：
- 如果 $j$是$i$的最近城市，那么花费1个金币
- 否则花费 $|a_j - a_i|$ 个金币
现在给出一些询问，需要你回答从$x_i$号城市到 $y_i$号城市之间的花费的最少金币
思路
首先我们知道：一个城市的最近城市 一定是和他相邻的两个城市中的一个。
因此我们根据贪心思想可以知道， 如果我们要从第i个城市到第j个城市， 那么我们将中间的城市全部依次经过一遍是最优的（因为经过的话就有可能只花费1金币）
于是本题就转换为了区间和的问题，可以用前缀和来解决：
当$x<y$时，我们使用一个数组$nxtcost$来记录从i到i+1花费的金币， 如果i+1是i的最近城市，那么$nxtcost[i] = 1$， 否则$nxtcost[i] = a_{i+1} - a_i$ ， 那么从x到y的金币花费就是 $nxtcost[y] - nxtcost[x-1]$
当$x > y$时，同理使用倒序的前缀和（后缀和）即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
int n;
cin>>n;
vector<int> vec(n+5);
vector<int> pre(n+5);
vector<int> last(n+5);
vector<int> sign(n+5);
vec[0] = -INF;
vec[n+1] = INF;
rep(i,1,n){
cin>>vec[i];
}
rep(i,1,n){
if(vec[i] - vec[i-1] < vec[i+1]-vec[i]){
sign[i] = -1;
}else sign[i] = 1;
}
rep(i,2,n){
if(sign[i-1] == 1) pre[i] = 1;
else pre[i] = vec[i]-vec[i-1];
pre[i] += pre[i-1];
}
per(i,n-1,1){
if(sign[i+1] == -1) last[i] = 1;
else last[i] = vec[i+1]-vec[i];
last[i] += last[i+1];
}
int q;
cin>>q;
while(q--){
int u,v;
cin>>u>>v;
if(u < v) {
cout<<pre[v] - pre[u]<<'\n';
}else{
cout<<last[v] - last[u]<<'\n';
}
}
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
D. Berserk Monsters
题意
有n个怪兽并排，给出一些怪兽的攻击力a和防御值d，下面进行n轮如下操作：
每一个怪兽会收到相邻的活着的怪兽攻击力之和的伤害，如果伤害大于自身的防御值d ，那么自己就会在这轮结束时死亡。
请你指出每轮有几只怪兽死亡
思路
每轮过后怪兽的左右邻居都可能会改变， 所以这题适合用双链表来存储怪兽之间的相邻关系。
我们发现当一个怪兽死亡后，只有和他相邻的怪兽， 在下一轮才有可能死亡。（如果一个怪兽的两个邻居都没有死亡，并且自己也没有死亡，那么下一轮这个怪兽同样不会被这两个邻居杀死）
因此在第$i+1$的判断中， 只需要判断第$i$轮中死亡的怪兽的邻居们就好
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
int n;
cin>>n;
vector<int> a(n+5);
vector<int> d(n+5);
rep(i,1,n) cin>>a[i];
rep(i,1,n) cin>>d[i];
vector<bool> over(n+5);
vector<int> next;
vector<int> pre(n+5);
vector<int> nxt(n+5);
rep(i,1,n){
pre[i] = i-1;nxt[i] = i+1;
next.push_back(i);
}
rep(i,1,n){
vector<int> tmp;
vector<int> pp;
int ans = 0;
for(auto p : next){
if(over[p]) continue;
if(a[pre[p]] + a[nxt[p]] > d[p]){
over[p] = 1;
if(pre[p]!=0) tmp.push_back(pre[p]);
if(nxt[p]!=n+1) tmp.push_back(nxt[p]);
ans ++;
pp.push_back(p);
}
}
for(auto p : pp){
pre[nxt[p]] = pre[p];
nxt[pre[p]] = nxt[p];
}
cout<<ans<<' ';
next = tmp;
}
puts("");
return ;
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
