牛客练习赛50 部分题解

题解

牛客练习赛50

老年选手已经拿不动刀了，但残存的一些斗志和激情足以支撑自己靠着仅剩的一点点经验继续下去。

A tokitsukaze and Connection

题意：给你一个字符串，判断所有相同的字母是否都在一起。
直接模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N];
int vis[101];
int main(){
    int n;
    while(~scanf("%d",&n))
    {
        scanf("%s",s);
        memset(vis,0,sizeof(vis));
        int f=1;
        for(int i=0;i<n;i++)
        {
            if(vis[s[i]-'a']&&s[i-1]!=s[i]) f=0;
            vis[s[i]-'a']=1;
        }
        if(f) puts("YES");
        else puts("NO");
    }
    return 0;
}

B tokitsukaze and Hash Table

题意：长度为n的哈希表，采用余数定址法，冲突便往右循环查找，求最终排列。
并差集做法，将循环相邻位置合并，递归查找更新。
STL做法，把允许存放的单元扔进set中，lower_bound存放位置然后删除即可。

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int nex[N],a[N];
int find(int x)
{
    return nex[x]==-1?x:nex[x]=find(nex[x]);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(nex,-1,sizeof(nex));
        memset(a,-1,sizeof(a));
        int x,tc;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            tc=x%n;
            if(a[tc]!=-1) tc=find(tc);
            nex[tc]=(tc+1)%n;
            a[tc]=x;
        }
        for(int i=0;i<n;i++)
            printf("%d%c",a[i],i==n-1?'\n':' ');
    }
    return 0;
}

C tokitsukaze and Soldier

题意：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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    int v,s;
    friend bool operator<(node a,node b)
    {
        return a.v>b.v;
    }
}a[N];
int cmp(node a,node b)
{
    if(a.s!=b.s) return a.s>b.s;
    return a.v>b.v;
}
priority_queue<node>q;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        while(!q.empty()) q.pop();
        long long ans=0,tmp=0;
        for(int i=0;i<n;i++)
            scanf("%d%d",&a[i].v,&a[i].s);
        sort(a,a+n,cmp);
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            q.push(a[i]);
            cnt++;
            tmp+=a[i].v;
            while(cnt>a[i].s) // 需要拿出战斗力最小的几个，优先队列按战斗力最小优先
            {
                tmp-=q.top().v;
                q.pop();
                cnt--;
            }
            ans=max(ans,tmp);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
 
/*
6
1 2
3 3
2 2
2 4
1 4
4 5
*/

D tokitsukaze and Event

题意：给你一张图，每条边有两个权值，代表两种状态下走的花费，现可以更改一次状态且到达终点后状态必须改变，若限制某些点不可更改状态从s点到t点的最小花费。
两边最短路，然后扔进最小优先队列中，只要当前点不可更改直接弹出。或者后缀取min。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
typedef unsigned long long ul;
//#define sc(x) scanf("%d",&x)
#define pd(x) printf("%d\n",x)
const double eps=1e-8;
const double PI=acos(-1.0);
const ll INF=1e16;
const int mod=1e9+7;
const int N=1e5+10;
ll d[2][N];
int n,m,tot,head[N],vis[N];
struct Edge
{
    int to,next,day,night;
} e[N*2];
struct node
{
    int v;
    ll hurt;
    friend bool operator<(node a,node b)
    {
        return a.hurt>b.hurt;
    }
};
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int day,int night)
{
    e[tot].to=v,e[tot].next=head[u],e[tot].day=day,e[tot].night=night;
    head[u]=tot++;
    e[tot].to=u,e[tot].next=head[v],e[tot].day=day,e[tot].night=night;
    head[v]=tot++;
}
priority_queue<node>q,q1;
void dijkstra_heap(int s,int flag)
{
    while(!q.empty())
        q.pop();
    for(int i=1; i<=n; i++)
    {
        if(flag)
            d[1][i]=(i==s?0:INF);
        else
            d[0][i]=(i==s?0:INF);
        vis[i]=0;
    }
    q.push(node{s,0});
    node tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u]) continue;
        vis[tmp.v]=1;
        for(int i=head[u]; i+1; i=e[i].next)
        {
            int v=e[i].to;
            if(flag)
            {
                if(d[1][v]>d[1][u]+e[i].night)
                {
                    d[1][v]=d[1][u]+e[i].night;
                        q.push(node{v,d[1][v]});
                }
            }
            else
            {
                if(d[0][v]>d[0][u]+e[i].day)
                {
                    d[0][v]=d[0][u]+e[i].day;
                        q.push(node{v,d[0][v]});
                }
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        int s,t,v,u,day,night;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d%d",&u,&v,&day,&night);
            add(u,v,day,night);
        }
        scanf("%d%d",&s,&t);
        dijkstra_heap(s,0);
        dijkstra_heap(t,1);
        while(!q1.empty())
            q1.pop();
        for(int i=1; i<=n; i++)
            q1.push(node{i,d[0][i]+d[1][i]});
        for(int i=1; i<=n; i++)
        {
            while(q1.top().v<i) q1.pop();
            printf("%lld\n",q1.top().hurt);
        }
    }
    return 0;
}

后面的不会了。
放上题解：【题解】牛客练习赛50