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];
}