目录

2020/05/16 牛客假日团队赛41

比赛信息

日期： 2020/05/16 链接： https://ac.nowcoder.com/acm/contest/5208#question
做题统计：王瑞琦： 冯宇扬： 常程：2

题解

A

solved by, upsolved by .

题意：
题解：

B photo

solved by 常程, upsolved by .

题意：N（$2\le N\le10^9$）头牛站成一排照相。有K（$1\le K\le1000$）对牛不想被照在同一张相片里。求最少照的次数。
题解：这道题在中途分界并没有能减少照的次数————不冲突的分配给那个区间都无所谓，冲突的必须分区间，因此直接贪心，发现矛盾就换区间。

code

code 

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
int n,k,line[2005],t=0,f[2005],ans=1;
map<int,int>to,vist;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&line[++t],&line[++t]);
        to[line[t-1]]=line[t];
        to[line[t]]=line[t-1];
    }
    sort(line+1,line+t+1);
    for(int i=1,v=1;i<=t;i++)
    {
        if(vist[to[line[i]]]==v)
        {
            v++;
            ans++;
        }
        vist[line[i]]=v;
    }
    printf("%d",ans);
    return 0;
}

C

solved by, upsolved by .

题意：
题解：

D

solved by, upsolved by .

题意：
题解：

E

solved by, upsolved by .

题意：
题解：

F

solved by, upsolved by .

题意：
题解：

G

solved by, upsolved by .

题意：
题解：

H

solved by, upsolved by .

题意：
题解：

I

solved by 常程, upsolved by .

题意：N（$1\le N\le5\times10^4$）只牛排成一排，每只牛有一个id，id相同、距离不到K（$1\le K<N$）的两只牛称为“crowded”。求最大的“crowded”的牛的id。
题解：大水题。直接记录每一个id上一次出现的位置就好了。

code

code 

#include<cstdio>
#include<map>
using namespace std;
int n,k,a,ans=-1;
map<int,int>last;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if(last[a]&&i-last[a]<=k&&a>ans)
            ans=a;
        last[a]=i;
    }
    printf("%d",ans);
    return 0;
}

J

solved by, upsolved by .

题意：
题解：

K

solved by, upsolved by .

题意：
题解：

L

solved by, upsolved by .

题意：
题解：

replay

总结