首页 > 分享 > jz集训 8.13

jz集训 8.13

萌宠菠菠乐园
2024-11-22 07:21

Day 13

155

T1

Description

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

Input

第一行，n和k,表示有n个学生，小R排倒数第k.
第二行，n个非负整数，表示这n个学生的成绩。

Output

一行，共k个数，从小到大输出。（相同成绩按不同排名算）

Sample Input

5 3
1 1 2 2 3

Sample Output

1 1 2

Solution

考点： C++ STL的熟练使用

T2

Description

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

Input

一行，要处理的字符串（都是小写字母）。

Output

一行若干个数字，从小到大输出，表示好名字的长度。

Sample Input

abcddabc

Sample Output

3 8

Solution

用KMP处理出字符串的next数组，因为next的数组定义是前缀和当前后缀完全匹配的位置。
从最后一位开始向前找next[t]

int t=len;while(nxt[t]){tmp[++cnt]=nxt[t];t=nxt[t];} 12345

T3

Description

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

Input

第一行，n，花盆的数量
第二行，n个数，表示对于每盆花的喜好值。
第三行：m, 改动的次数
以下m行，每行两个数ki 和di 。

Output

M行，每一行对应一个更改，表示连续的最大喜好值，且不能整圈都选。（注意：是在圈上找）

Sample Input

5
3 -2 1 2 -5
4
2 -2
5 -5
2 -4
5 -1

Sample Output

4
4
3
5

Solution

注意到这一题是在一个环上求最大子段和。
我们只要统计下来一段最大的子段和和最小的子段和就可以考虑到不过n号点和过n号点的情况了。不用断环为链。
我们定义8个变量minl,minr,maxl,maxr,mn,mx,minn,tot。
minl表示[l, r]区间内从 l 开始取得的最小子段和。
minr，maxl，maxr同理。
mn表示[l, r]区间内最小的子段和。
mx同理。
minn表示区间内最小的一个数。
tot表示区间内所有数的和。

push_up操作如下。

void push_up(int k){tr[k].mxl=max(tr[ls(k)].tot+tr[rs(k)].mxl, tr[ls(k)].mxl); //最小子段和可能越过整个左区间tr[k].mxr=max(tr[rs(k)].tot+tr[ls(k)].mxr, tr[rs(k)].mxr);tr[k].tot=tr[ls(k)].tot+tr[rs(k)].tot;tr[k].mnl=min(tr[ls(k)].tot+tr[rs(k)].mnl, tr[ls(k)].mnl);tr[k].mnr=min(tr[rs(k)].tot+tr[ls(k)].mnr, tr[rs(k)].mnr);tr[k].minn=min(tr[ls(k)].minn, tr[rs(k)].minn);tr[k].mn=min(tr[ls(k)].mn, min(tr[rs(k)].mn, min(tr[ls(k)].mnr+tr[rs(k)].mnl, max(tr[k].mnl, tr[k].mnr))));tr[k].mx=max(tr[ls(k)].mx, max(tr[rs(k)].mx, max(tr[ls(k)].mxr+tr[rs(k)].mxl, max(tr[k].mxl, tr[k].mxr)))); } 12345678910

ans如下：

ans=max(tr[1].mx==tr[1].tot ? tr[1].tot-tr[1].minn : tr[1].mx, tr[1].tot-tr[1].mn)) 1