20210811考试

20210811考试

封面来源

bathroom-95649046

20210811考试

T1

补票

企鹅国最近开通了高铁,高铁一共有$ M $站(站台编号从$ 1$ 到 $M$),第 $i $站和第 $i+1$ 站之间 的距离是$Ai$。由于正值暑假有不少企鹅购票乘坐高铁,但是也有一些没有买票的企鹅也溜上了列车。在一轮查票之后,找出了 $N$ 只没有购票的企鹅,第 $i$ 只企鹅在$Si$站上车,$Ti$站下车, 体重为$Wi$。 企鹅国的高铁票价机制为,对于一只需要乘坐距离$ L$,体重 $W$ 的企鹅,高铁票价为 $L × W$。 现在你需要计算出这 $N$​ 只企鹅一共需要花多少钱补票

模拟题,维护站点间距离的前缀和,可以在$O(1)$​时间内求出$s$​到$t$​​距离

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>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 1e5+7,M=1e5+7;
int n,m;
int a[M];
int sum;
inline int calc(int s,int t,int w){
return w*(a[t]-a[s]);
}
signed main(){
cin>>n>>m;
a[1]=0;
FOR(i,2,m){
cin>>a[i];
a[i]+=a[i-1];
}
FOR(i,1,n){
int s,t,w;
cin>>s>>t>>w;
sum+=calc(s,t,w);
}
cout<<sum<<endl;
return 0;
}

T2

N 个数排成一列,zxn 和 fsf 轮流进行以下操作,zxn 先手: 假设目前还剩 M 个数(M>=2),操作者任选一个整数 K(2<=K<=M),将当前数列的最左边 K 个数擦去,并在最左边添上一个新的数,这个新的数等于刚刚擦去的所有数的和。 每一次操作,操作者都可以得到一个分数,这个分数等于新添上去的数的值。 当数列只剩一个数时,游戏结束。 zxn 和 fsf 都是无限聪明的,她们都希望自己所有操作的得分和减去对方所有 操作的得分和的值最大。那么,最后 zxn 的得分和会比 fsf

一道搬运题。原题CF731E,大概方法就是dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],f[N],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
int ans = a[n];
for(register int i=n-1;i>=1;i--){
f[i]=ans;
ans=max(ans,a[i]-f[i]);
}
cout<<f[1]<<endl;
}

T3

企鹅豆豆拿到一列数字(我也不知道他怎么拿到的),这些数字很乱,他看着很不爽,于是他准备删掉一些数字,使得剩下的数字尽可能多的数字满足从左往右第 i 个数字的值是 i。 你需要告诉他最多能有多少个数字满足如上条件?

树状数组+DP

T4

在企鹅国,企鹅们是通过滑冰出行的。每次滑冰需要选择一个营地作为起点,一个营地 作为终点,然后从营地 $A(ax , ay)$滑到营地 $B(bx , by)$需要的时间是 $min{|ax − bx |,|ay − by |}$。 现在企鹅豆豆在 1 号营地,他需要赶到 N 号营地参加活动,他想知道他最少需要花费多 少时间? 可能存在营地重合的情况

简单单源最短路问题,有点麻烦的主要是对边的处理但是根据题目中的关于时间的限制,我们可以很简单地处理这个问题

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
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;i++)
#define Graph(i,u) for(register int i=head[u];i;i=e[i].next)
using namespace std;
int n;
const int N = 2e6+10;
const int inf = 1<<31-1;
struct Edge{
int u,v,w,next;
}e[N];
int tot,head[N];
inline void addEdge(int u,int v,int w){
e[++tot].u=u;
e[tot].v=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
int dis[N],vis[N];
void spfa(){
queue<int> q;
FOR(i,1,n){
dis[i]=inf;
}
FOR(i,1,n){
vis[i]=0;
}
dis[1]=0;
q.push(1);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u]=0;
Graph(i,u){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
struct node{
int x,y,id;
}a[N];
bool cmpx(const node &w,const node &t){return w.x<t.x;}
bool cmpy(const node &w,const node &t){return w.y<t.y;}
int minn(node w,node t){return min(abs(w.x-t.x),abs(w.y-t.y));}
signed main(){
cin>>n;
FOR(i,1,n){cin>>a[i].x>>a[i].y;a[i].id=i;}
sort(a+1,a+1+n,cmpx);
FOR(i,1,n-1){
int u = minn(a[i],a[i+1]);
addEdge(a[i].id,a[i+1].id,u);
addEdge(a[i+1].id,a[i].id,u);
}
sort(a+1,a+1+n,cmpy);
FOR(i,1,n-1){
int u = minn(a[i],a[i+1]);
addEdge(a[i].id,a[i+1].id,u);
addEdge(a[i+1].id,a[i].id,u);
}
spfa();
cout<<dis[n];
}
作者

Steve Li

发布于

2021-08-11

更新于

2022-01-22

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×