CSP-S考前冲刺DAY1

今天第一天集训,虽然难度不算难,但出现了亿些些不会写的东西。

[题目1]线段树

正如这道题的名字一样,正解就是线段树,只不过还要维护乘法(暴力没有分!!),线段树不熟,挂了


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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=10007;
ll n,m;
ll a[100010],Jsum[500010],Csum[500010];
void build(ll k,ll l,ll r)//建树
{
    if(l==r)
    {
        Jsum[k]=Csum[k]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
    Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
void change(ll k,ll l,ll r,ll x,ll v)//更改数值
{
    if(l==r)
    {
        Jsum[k]=Csum[k]=v;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)change(k<<1,l,mid,x,v);
    else change(k<<1|1,mid+1,r,x,v);
    Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
    Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
ll queryC(ll k,ll l,ll r,ll x,ll y)//查询乘法
{
    if(r<x||l>y)return 1;
    if(x<=l&&r<=y)return Csum[k];
    ll mid=(l+r)>>1;
    ll res1,res2;
    res1=queryC(k<<1,l,mid,x,y);
    res2=queryC(k<<1|1,mid+1,r,x,y);
    return (res1*res2)%mod;
}
ll queryJ(ll k,ll l,ll r,ll x,ll y)//查询加法
{
    if(r<x||l>y)return 0;
    if(x<=l&&r<=y)return Jsum[k];
    ll mid=(l+r)>>1;
    ll res1,res2;
    res1=queryJ(k<<1,l,mid,x,y);
    res2=queryJ(k<<1|1,mid+1,r,x,y);
    return (res1+res2)%mod;
}
// 初始化部分

线段树真的特别长,而且特别容易写挂,在OJ上交了好几次0分的代码………………(还有一本通的线段树的模板题是不用写build()函数的……,于是把build()打挂提交了好几次)

这个是不带懒标记的,带懒标记的题目有这个

附代码:


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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,w[N];
struct node
{
    int l,r;
    LL sum,add;
}tree[N*4];
void pushup(int u)
{
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void pushdown(int u)
{
    auto &root=tree[u],&left=tree[u<<1],&right=tree[u<<1|1];
    if(root.add)
    {
        left.add+=root.add;
        left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add;
        right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}
void build(int u,int l,int r)
{
    if(l==r)tree[u]={l,r,w[r],0};
    else
    {
        tree[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int d)
{
    if(tree[u].l>=l&&tree[u].r<=r)
    {
        tree[u].sum+=(LL)(tree[u].r-tree[u].l+1)*d;
        tree[u].add+=d;
    }
    else
    {
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,d);
        if(r>mid)modify(u<<1|1,l,r,d);
        pushup(u);
    }
}
LL query(int u,int l,int r)
{
    if(tree[u].l>=l&&tree[u].r<=r)return tree[u].sum;
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    LL sum=0;
    if(l<=mid)sum+=query(u<<1,l,r);
    if(r>mid)sum+=query(u<<1|1,l,r);
    return sum;
}
//一些初始化......

不会的第二题……

[第三题]礼物

DP......


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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005,mod=1e7+7;
int f[N][N],c[N];
int n,m,sum;
int main()
{
    freopen("gift.in","r",stdin);
    freopen("gift.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        sum+=c[i];
    }
    if(sum<=m)//特判所有物品价格的和不大于m的情况,此时只有一种方案
    {
        printf("1");
        return 0;
    }
    sort(c+1,c+n+1);//设f[i][j]表示考虑前i件物品,剩余j元的方案数
    f[n][c[n]]=1;
    f[n][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=c[i])f[i][j]=(f[i][j]+f[i+1][j-c[i]])%mod;
            f[i][j]=(f[i][j]+f[i+1][j])%mod;
        }
    }
    int rest=0,ans=0;
    for(int k=1;k<=n;k++)
    {
        rest=m;
        for(int i=1;i<k;i++)rest-=c[i];
        if(rest<0)break;
        for(int i=max(rest-c[k]+1,0);i<=rest;i++)ans=(ans+f[k+1][i])%mod;
    }
    printf("%d",ans);
    return 0;
}

[第四题]宋伊雪的惩罚

长乐OJ原题,枚举中心点,二分最大的边长,判断相等时用二维HASH,真是不错的一道题目呢


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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int n,m;
typedef unsigned long long ULL;
const ULL base1=87,base2=31;//模数随便取(要质数)
ULL a[N][N],b[N][N],c[N][N],Hasha[N][N],Hashb[N][N],Hashc[N][N],fact1[N],fact2[N],ans;
bool check(int len,int x,int y)
{
    if(x>n||y>m||x<len||y<len)return 0;
    ULL HASHa=0,HASHb=0,HASHc=0;
    HASHa=Hasha[x][y]-Hasha[x-len][y]*fact2[len]-Hasha[x][y-len]*fact1[len]+Hasha[x-len][y-len]*fact1[len]*fact2[len];
    int t=y;
    y=m-(y-len);
    HASHb=Hashb[x][y]-Hashb[x-len][y]*fact2[len]-Hashb[x][y-len]*fact1[len]+Hashb[x-len][y-len]*fact1[len]*fact2[len];
    y=t;
    x=n-(x-len);
    HASHc=Hashc[x][y]-Hashc[x-len][y]*fact2[len]-Hashc[x][y-len]*fact1[len]+Hashc[x-len][y-len]*fact1[len]*fact2[len];
    return HASHa==HASHb&&HASHb==HASHc;
}
ULL B(int i,int j,int x=0)
{
    int l=0,r=min(i,j)+f,Ans=x;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid*2-x,i+mid,j+mid))
        {
            l=mid+1;
            Ans=mid*2-x;
        }
        else r=mid-1;
    }
    return (Ans+1)/2;
}
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    fact1[0]=fact2[0]=1ULL;
    for(int i=1;i<=n;i++)fact1[i]=fact1[i-1]*base1;
    for(int i=1;i<=m;i++)fact2[i]=fact2[i-1]*base2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][m-j+1]=c[n-i+1][j]=a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            Hasha[i][j]+=Hasha[i][j-1]*base1+a[i][j];
            Hashb[i][j]+=Hashb[i][j-1]*base1+b[i][j];
            Hashc[i][j]+=Hashc[i][j-1]*base1+c[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            Hasha[i][j]+=Hasha[i-1][j]*base2;
            Hashb[i][j]+=Hashb[i-1][j]*base2;
            Hashc[i][j]+=Hashc[i-1][j]*base2;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)ans+=B(i,j,1)+B(i,j);
    }
    printf("%llu",ans);
    return 0;
}

一涉及提高组字数就多到爆炸......

发表评论

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