2019JZ集训Day13

今天又晴空万里。

今天又没能AC。

我真是太菜了。


T1:【rank】(传送门

  • 评测姬正常波动30分。
  • 据说别人只快排过了,mf快排60分,我快排70分。
  • 然后由于题面有点问题反正你只要知道从小到大排序后输出前k个数就好。快排+快读能过。桶排能过。(由于定向思维考试时没有想过桶排)
  • 论我一个不会快读的人是如何存活至今的。

T2:【seek】(传送门

  • 哈希或者kmp都行。由于我太菜了,所以我用的是比较慢的hash。(mf大佬的kmp超快的)
  • 扫一遍字符串,用s[i]存储子串0到i的哈希值。枚举长度,再加加减减计算出后缀的第一个字符在哪里,然后套个公式(s[j]-s[i-1]*26j-i+1%mo+mo)%mo求出后缀的哈希值。比较哈希值。(快速幂千万不要打错!我就是掉坑了找了好久才发现)

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int len,p=998244353,d[400005],head=1,tail;
long long s[400005],x,f1,f2;
char a[400005];
int ksm(int a,int m)
{
    long long res=1,g=a;
    while(m)
    {
        if(m&1) res=(res*g)%p;
        g=(g*g)%p;m>>=1;
    }
    return (int)res;
}
int main()
{
    scanf("%s",a);
    len=strlen(a);
    for(int i=0;i<len;i++)
    {
        x=(x*26+a[i]-97)%p;
        s[i]=x;
    }
    for(int i=len-1;i>=1;--i)
        if(a[i]==a[0])
            d[++tail]=i;
    while(head<=tail)
    {
        f1=s[len-d[head]-1];
        f2=((s[len-1]-(s[d[head]-1]*ksm(26,len-d[head])%p))%p+p)%p;
        if(f1==f2)
            printf("%d ",len-d[head]);
        head++;
    }
    printf("%d",len);
    return 0;
}

T3:【pot】(传送门

  • 个人感觉又是恶心的题面。没读懂样例导致没打。
  • 一句话概括就是每次单点修改后,询问环上最大区间和。
  • 有点思维难度的是,如何处理环上最大区间和。环上最大区间和可以分为两种情况,一种是在正常的序列上,另一种便是挖掉中间一部分(即最小区间和)头一部分尾一部分的剩下的区间和。那么问题就转换成了求三个东西,最大区间和,最小区间和,所有元素和。
  • 看到这个玩意儿当然就是线段树啦。但是这个线段树要维护七个元素。区间和,最大子串和,最小子串和,以左边第一个元素开头的最大子串和,以左边第一个元素开头的最小子串和,以右边最后一个元素结尾的最大子串和,以右边最后一个元素结尾的最小子串和。然后转移自己用点脑子推一下就是了。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,x[100005],k,d;
struct tree
{
    int sum;
    int maxx,rmax,lmax;
    int minn,rmin,lmin;
}q[400040];
int Max(int a,int b,int c,int d)
{
    if(a>=b&&a>=c&&a>=d) return a;
    if(b>=a&&b>=c&&b>=d) return b;
    if(c>=a&&c>=b&&c>=d) return c;
    return d;
}
int Min(int a,int b,int c,int d)
{
    if(a<=b&&a<=c&&a<=d) return a;
    if(b<=a&&b<=c&&b<=d) return b;
    if(c<=a&&c<=b&&c<=d) return c;
    return d;
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        q[k].sum=x[l];
        q[k].maxx=x[l];q[k].rmax=x[l];q[k].lmax=x[l];
        q[k].minn=x[l];q[k].rmin=x[l];q[k].lmin=x[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    q[k].sum=q[k<<1].sum+q[k<<1|1].sum;
   
    q[k].maxx=Max(q[k].sum,q[k<<1].sum+q[k<<1|1].lmax,q[k<<1].rmax+q[k<<1|1].sum,q[k<<1].rmax+q[k<<1|1].lmax);
    q[k].maxx=Max(q[k].maxx,q[k<<1].maxx,q[k<<1|1].maxx,-999999999);
   
    q[k].rmax=Max(q[k].sum,q[k<<1|1].sum,q[k<<1|1].rmax,q[k<<1].rmax+q[k<<1|1].sum);
    q[k].lmax=Max(q[k].sum,q[k<<1].sum,q[k<<1].lmax,q[k<<1].sum+q[k<<1|1].lmax);
   
    q[k].minn=Min(q[k].sum,q[k<<1].sum+q[k<<1|1].lmin,q[k<<1].rmin+q[k<<1|1].sum,q[k<<1].rmin+q[k<<1|1].lmin);
    q[k].minn=Min(q[k].minn,q[k<<1].minn,q[k<<1|1].minn,999999999);
   
    q[k].rmin=Min(q[k].sum,q[k<<1|1].sum,q[k<<1|1].rmin,q[k<<1].rmin+q[k<<1|1].sum);
    q[k].lmin=Min(q[k].sum,q[k<<1].sum,q[k<<1].lmin,q[k<<1].sum+q[k<<1|1].lmin);
}

void updata(int k,int l,int r,int pos,int v)
{
    if(l==r&&l==pos)
    {
        q[k].sum=v;
        q[k].maxx=v;q[k].rmax=v;q[k].lmax=v;
        q[k].minn=v;q[k].rmin=v;q[k].lmin=v;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) updata(k<<1,l,mid,pos,v);
    else updata(k<<1|1,mid+1,r,pos,v);
   
    q[k].sum=q[k<<1].sum+q[k<<1|1].sum;
   
    q[k].maxx=Max(q[k].sum,q[k<<1].sum+q[k<<1|1].lmax,q[k<<1].rmax+q[k<<1|1].sum,q[k<<1].rmax+q[k<<1|1].lmax);
    q[k].maxx=Max(q[k].maxx,q[k<<1].maxx,q[k<<1|1].maxx,-999999999);
   
    q[k].rmax=Max(q[k].sum,q[k<<1|1].sum,q[k<<1|1].rmax,q[k<<1].rmax+q[k<<1|1].sum);
    q[k].lmax=Max(q[k].sum,q[k<<1].sum,q[k<<1].lmax,q[k<<1].sum+q[k<<1|1].lmax);
   
    q[k].minn=Min(q[k].sum,q[k<<1].sum+q[k<<1|1].lmin,q[k<<1].rmin+q[k<<1|1].sum,q[k<<1].rmin+q[k<<1|1].lmin);
    q[k].minn=Min(q[k].minn,q[k<<1].minn,q[k<<1|1].minn,999999999);
   
    q[k].rmin=Min(q[k].sum,q[k<<1|1].sum,q[k<<1|1].rmin,q[k<<1].rmin+q[k<<1|1].sum);
    q[k].lmin=Min(q[k].sum,q[k<<1].sum,q[k<<1].lmin,q[k<<1].sum+q[k<<1|1].lmin);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&k,&d);
        updata(1,1,n,k,d);
        printf("%d\n",max(q[1].maxx,q[1].sum-q[1].minn));
    }
    return 0;
}

T4:【游戏节目】(传送门

  • 暴力搜索40分。
  • 对于正解先不考虑A赢的限制。先来搞出选出不少于k个节目的方案数。显然,用不限制个数的总方案数-节目个数<k的方案数就是了。节目个数<k的方案数暴力枚举即可。那么对于总方案数考虑用折半搜索,先搜n/2的左边这一部分,对于每一次的方案保留两个数据ai=A-B,bi=A-C(A,B,C表示选取的节目分数总和)。要满足A赢的条件,对于另一部分的搜索的aj与bj就一定要满足,ai+aj>0(aj>-ai),bi+bj>0(bj>-bi)。然后用什么二维偏序搞这个东西,我就不会了。(扫描线?数据结构维护?)

今天是zyn的生日。祝他生日快乐!

我们还因此改善了一下伙食。

题目难度虽然降了点,但还是考得不好。用阿kiao的话讲就是每个人这个礼拜都是不同程度的下滑。因为和舍友熟了晚上就各种聊骚。晚上睡不着,早上起不来。

6:40起床7:10到食堂吃的只有凉的叉烧包了,和各种面包、白粥,连豆浆都没有。还导致我一整个早上都困得要死。害!

——end。

发表评论

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