Featured image of post 20210712测试

20210712测试

封面来源

Pixiv 沙花叉クロヱ-95626459

[problem.pdf](https://blog.stevelbr.top/usr/uploads/2021/07/3409190873.pdf)

T1

题目描述

农夫约翰的 N(3≤N≤50000)头牛被定在了平面内的不同的位置。他想用栅栏(平 行于 x 和 y 轴)围住所有的牛。他想这个栅栏尽可能小(牛在边界上也被视作围住)。 他因为牛奶产量低而感到经费紧张,所以他想卖掉 1 头牛再围起剩下的牛,请算出精 心挑选出一头奶牛卖掉后栅栏此时能围出的最小面积。 请把牛看作一个点,把一个围栏看做四条线段拼成。 请注意,答案可以是零,例如,如果所有剩余的牛最终站在一个共同的垂直或水平线 上。

输入样例

4 2 4 1 1 5 2 17 25

输出样例

12

思路

找最大值最小值,枚举每一个点,看去掉后结果,找最小值

代码
 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
/*
limits:
1s
256M
*/

#include<iostream>
using namespace std;
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define endl "\n"
#define min(x,y) x>y?y:x
int n;
const int N = 50100;
struct Point{
    int x,y;
}pos[N];
int x1,x2,x3,x4,y1,y2,y3,y4;
void maintaince(Point t){
    if(t.x<x1){
        x2=x1,x1=t.x;
    }else if(t.x<x2){
        x2=t.x;
    }
    if(t.x>x4){
        x3=x4,x4=t.x;
    }else if(t.x>x3){
        x3=t.x;
    }
    if(t.y<y1){
        y2=y1,y1=t.y;
    }else if(t.y<y2){
        y2=t.y;
    }
    if(t.y>y4){
        y3=y4,y4=t.y;
    }else if(t.y>y3){
        y3=t.y;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("reduce.in","r",stdin);
    // freopen("reduce.out","w",stdout);
    cin>>n;
    x1=x2=y1=y2=N;
    x3=x4=y3=y4=-1;
    FOR(i,1,n){
        cin>>pos[i].x>>pos[i].y;
        maintaince(pos[i]);
    }
    int ans=(x4-x1)*(y4-y1);
    FOR(i,1,n){
        ans=min(ans,((pos[i].x==x1?x2:x1)-(pos[i].x==x4?x3:x4))*((pos[i].y==y1?y2:y1)-(pos[i].y==y4?y3:y4)));
    }
    cout<<ans<<endl;
}

T2

咕了

T3

直接模拟

T4

题目描述

某国有 n 座城市,这些城市之间通过 m 条单向道路相连,已知每条道路的长度。 不过,小 X 只对其中 k 座城市感兴趣。 为了更好地规划模拟旅行路线,提升模拟旅行的体验,小 X 想要知道他感兴趣的 城市之间两. 两. 最. 短. 路. 的最小值(即在他感兴趣的城市中,最近的一对的最短距离)。 作为一个肥宅,小 X 根本懒得写程序来解决这道问题,于是他把这个问题丢给 了你。

输入

6 7 3 1 5 3 2 3 5 1 4 3 5 3 2 4 6 5 4 3 7 5 6 4 1 3 6

输出

5

分析

一道改编题,出自P5304 [GXOI/GZOI2019]旅行者.,方法就是dijkstra

代码
 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
71
72
73
74
75
76
77
/*
limits:
2s
512M
*/
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int n,m,k;
int x,y,z;
const int maxn = 3*1e5+10,maxm = 1e6+10;
struct Edge{
    int to,next,w;
    // Edge(int x,int y,int z):to(x),next(y),w(z){    }
}edge[maxm];
int tot,head[maxm];
inline void addEdge(int u,int v,int w){
    edge[++tot]=(Edge){v,head[u],w};
    head[u]=tot;
}
int dis[maxn];
struct node{
    int u,d;
    bool operator < (const node &cp) const{
        return d>cp.d;
    }
};
priority_queue<node> q;
bool vis[maxn],need[maxn];
int dijkstra(int start){
    while(!q.empty()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    q.push((node){start,0});
    dis[start]=0;
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(need[u]&&u!=start){//就是想去这个点
            return dis[u];
        }
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next){
                int v=edge[i].to,w=edge[i].w;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push((node){v,dis[v]});
                }
            }
        }
    }
    return 0x3f3f3f3f;
}
int main(){
    // freopen("tour1.in","r",stdin);
    // freopen("tour.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        addEdge(x,y,z);
    }
    for(int i=1;i<=k;i++){
        cin>>x;
        need[x]=1;
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        if(need[i]==1){
            ans=min(dijkstra(i),ans);
        }
    }
    cout<<ans<<endl;
}
所念皆星河
Built with Hugo
主题 StackJimmy 设计