The 2019 Asia Nanchang First Round Online Programming Contest(B,E)

古城微笑少年丶 2023-06-01 11:14 10阅读 0赞

B. Fire-Fighting Hero

题意：一个消防员和多个队伍比赛，比较所有地方的最短路的最大值，消防员最后的值要乘1/C,求胜利的一方的最短路的最大值是多少。一直没读懂正确题意（内疚）。

思路：图论题-单源最短路径：添加一个顶点，连接各个救火团队所在的救火点，路径长度均设为 0，设该顶点为源，即变成了单源最短路径问题。使用两次Dijkstra算法可求出两个最短路径 的最大值。比较时将救火团队的乘以T进行比较可避免分数操作。（题解）

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn = 2e6+5;
     5 const ll INF = 1e18 + 10;
     6 typedef pair<ll,int> P;
     7 int n , m;
     8 struct edge{
     9     int to;
    10     ll cost;
    11 }es[maxn];
    12 vector <edge> G[maxn];
    13 ll d[maxn];
    14 ll dijkstra(int s)
    15 {
    16     priority_queue<P,vector<P>,greater<P> > que;
    17     fill(d,d+n+1,INF);
    18     d[s] = 0;
    19     que.push(P(0,s));
    20     while(!que.empty())
    21     {
    22         P p= que.top();que.pop();
    23         int v = p.second;
    24         if(d[v] < p.first) continue;
    25         for(int i = 0;i < G[v].size();i++)
    26         {
    27             edge e = G[v][i];;
    28             if(d[e.to] > d[v] + e.cost)
    29             {
    30 
    31                 d[e.to]= d[v] + e.cost;
    32                 que.push(P(d[e.to],e.to));
    33             }
    34         }
    35     }
    36     ll a = -INF;
    37     for(int i = 1;i <= n;i++){
    38         a = max(a, d[i]);
    39     }
    40     return a;
    41 }
    42 ll a[maxn];
    43 int  cnt;
    44 void add(int a, int b, ll c)
    45 {
    46     es[cnt].to = b;
    47     es[cnt].cost = c;
    48     G[a].push_back(es[cnt++]);
    49     es[cnt].to = a;
    50     es[cnt].cost = c;
    51     G[b].push_back(es[cnt++]);
    52 }
    53 int main()
    54 {
    55     std::ios::sync_with_stdio(false);
    56     int t, S, k;
    57     ll C;
    58     cin >> t;
    59     while(t--)
    60     {
    61         cin >> n >> m >> S >> k >> C;
    62         int u,v,w;
    63         cnt = 0;
    64         for(int i = 0;i <= n;i++)G[i].clear();
    65         for(int i = 1;i <= k;i++) cin >> a[i];
    66         for(int i = 0;i < m;i++)
    67         {
    68             cin >> u >> v >> w;
    69             add(u, v, w);
    70         }
    71         ll z = dijkstra(S);
    72        // cout << z << " = z" << endl;
    73         for(int i = 1;i <= k;i++)
    74             add(0,a[i],0);
    75         ll x = dijkstra(0);
    76         //cout << x << " " << endl;
    77         cout<<((z <= x * C) ? z : x) <<endl;
    78     }
    79     return 0;
    80 }

--------------------

E. Magic Master

思路：真没想过就是暴力模拟就行了，想了半天，一脸懵逼。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int main()
     4 {
     5     int t;
     6     scanf("%d",&t);
     7     while(t--){
     8         int n, m, q;
     9         scanf("%d%d%d",&n, &m, &q);
    10         deque<int>  dq;
    11         for(int i = n;i > 0;i--)
    12         {
    13             dq.push_front(i);
    14             if(i == 1)break;
    15             for(int j = 1;j <= m;j++)
    16             {
    17                 int x = dq.back();
    18                 dq.pop_back();
    19                 dq.push_front(x);
    20             }
    21         }
    22         while(q--)
    23         {
    24             int a;
    25             scanf("%d",&a);
    26             printf("%d\n",dq[a - 1]);
    27         }
    28     }
    29     return 0;
    30 }

--------------------

H. The Nth Item

待补

转载于:https://www.cnblogs.com/Carered/p/11489532.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/3d37ede8601347f79e07a8dc41c29c1f.png