2019 纪中 Day 13

生日♂快乐~!the man♂

T1 rank

题面:

小h和小R正在看之前的期末&三校联考成绩,小R看完成绩之后很伤心,共有n(n<=5*10^6)个学生,第i个学生有一个总成绩Xi(0<=Xi<=10^5),因为他的排名是倒数第k(1<=k<=n)个,于是小R想知道那些成绩比他低(包括成绩和他一样)的同学的成绩,这样能让他没那么伤心。

今日签到题。

因为成绩值很小,所以可以用桶排而且在100000下表现优异~

只可惜时限开了2000ms,所以快排加读入优化也可以较稳的水过~


T2 seek

题面:

俗话说“好命不如好名”,小h准备给他的宠物狗起个新的名字,于是他把一些英文的名字全抄下来了,写成一行长长的字符串,小h觉得一个名字如果是好名字,那么这个名字在这个串中既是前缀,又是后缀,即是这个名字从前面开始可以匹配,从后面开始也可以匹配,例如abc在 abcddabc中既是前缀,也是后缀,而ab就不是,可是长达4*10^5的字符让小h几乎昏过去了,为了给自己的小狗起个好名字,小h向你求救,并且他要求要将所有的好名字的长度都输出来。

这题的数据显然暴力枚举过不了。

但是不会KMP啊!于是考场上只能打暴力水40分了。

代码:


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
#include<cstdio>
#include<cstring>
using namespace std;
const int M=101010;
char ch[4*M];
int i,j;
int Next[4*M];
int ans[4*M];
int flag;
int lena;
int main()
{
    scanf("%s",ch+1);
    lena=strlen(ch+1);
    for(register int i=1;i<lena;i++){
        if(ch[i]!=ch[i+1]){
            flag=1;
            break;
        }
    }
    if(!flag){
        for(register int i=1;i<=lena;i++)
            printf("%d ",i);
        return 0;
    }
    for(register int i=2;i<lena;i++){
        while(j&&ch[j+1]!=ch[i])
            j=Next[j];
        if(ch[j+1]==ch[i])
            Next[i]=j+1;
        j=Next[i];
    }
    Next[0]=-1;
    int tot=0;
    while(j>=0){
        if(ch[j+1]==ch[lena])
            ans[++tot]=j+1;
        j=Next[j];
    }
    ans[0]=lena;
    for(register int i=tot;i>=0;i--)
        printf("%d ",ans[i]);
    return 0;
}

努力研究KMP吧。


T3 pot

题面:

这个假期,小h在自家院子里种了许多花,它们围成了一个圈,从1..n编号(n<=100000),小h 对每盆花都有一个喜好值xi,(-1000<=xi<=1000),小h现在觉得这样一成不变很枯燥,于是他做了m(m<=100000)个改动,每次把第ki盘花改成喜好值为di的花,然后小h要你告诉他,在这个花圈中,连续的最大喜好值是多少。

线段树维护区间最大子段和和最小子段和。

然后就是这样:


1
2
3
4
5
6
        if(tree[1].flag==n)
            printf("%d\n",tree[1].sum-tree[1].zdmin);
        if(tree[1].flag==-n)
            printf("%d\n",tree[1].zdmax);
        if(tree[1].flag!=n&&tree[1].flag!=-n)
            printf("%d\n",Max(tree[1].zdmax,tree[1].sum-tree[1].zdmin));

要注意序列全负数或者全正数的情况。(虽然他没有出这两个数据。)


T4 游戏节目(show)

题面:

有三支队伍,分别是A,B,C。有n个游戏节目,玩第i个游戏,队伍A可以得到的分数是A[i],队伍B可以得到的分数是B[i],队伍C可以得到的分数是C[i]。由于时间有限,可能不是每个节目都能玩,于是节目主持人决定要从n个游戏节目里面挑选至少k个节目出来(被选中的节目不分次序),使得队伍A成为赢家。队伍A能成为赢家的条件是队伍A的总得分要比队伍B的总得分要高,同时也要比队伍C的总得分要高。节目主持人有多少种不同的选取方案?

看完题面,显然不会。

只能打暴力为生了。

关于正解:

来自某纪中dalao,没错,和昨天是同一个。


到此。

今天聚餐真好!还不用花钱!

要是每天组里都有人生日就好了~

Good  night 吧!

发表评论

电子邮件地址不会被公开。 必填项已用*标注