NOIP游记[doge]

刚刚过去的NOIP2021大家还好吗?

DAY -1:看考场

DAY0:

[报数]

考场的时候没有想到预处理,害怕1e7数组会爆掉,打了一个暴力就溜了。

这个题其实就是预处理,方法有点类似于朴素筛法,

稍微做了一点点改动(时间复杂度O(nlogn))。

一个坑点:当输入的x=(1e7-2)的时候,答案是会等于1e7+1的,所以要预处理到1e7+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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e7+10;
int st[N],ans[N],pos[N],cnt;//st[i]=1时表示不可以报,ans[i]表示第i个可以报的数
//pos[i]表示i是下一个可以报的数在ans里的下标,cnt用来记录一共有几个可以报的数
int s(int x)
{
    while(x)
    {
        if(x%10==7)return 1;
        x/=10;
    }
    return 0;
}
void get_sevens(int n)
{
    for(int i=1;i<=n;i++)
    {
       if(!st[i])
       {
           if(i%7==0||(s(i)))
        {
            for(int j=i;j<=n;j+=i)st[j]=1;
        }
        else
        {
            ans[cnt]=i;
            pos[i]=++cnt;
        }
    }
     }
}
int main()
{
    get_sevens(1e7+2);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x;
        scanf("%d",&x);
        if(st[x])
        {
            puts("-1");
            continue;
        }
        printf("%d\n",ans[pos[x]]);
    }
    return 0;
 }

[数列]

考场的时候写了一个暴力,民间数据还全部挂掉了。。。

这题果然是DP,类似于数位DP,考虑直接把进位放在状态里。
定义f[z][u][a][b]对于二进制位的后z位,已经放进去u个数,此时进位到下一位的值是a,后i位中留下了b个1,此时的权值总和。

此时有:dp[z][u][a][b]=dp[z+1][u+i][a+((b+i)&1)][(b+i)>>1)]*(power[z]的i次方)*(C[u+i][i])(C表示组合数)(记得%998244353


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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1LL*998244353;
LL n,m,k,v[105],dp[105][35][35][35];
LL C[105][105],power[105][105];
LL count_one(LL x)
{
    LL ans=0;
    while(x)
    {
        x-=x&(-x);
        ans++;
    }
    return ans;
}
LL dfs(LL z,LL u,LL a,LL b)
{
    if(u==n)return (bool)(a+count_one(b)<=k);
    if(z>m)return 0;
    if(dp[z][u][a][b]!=-1)return dp[z][u][a][b];
    LL res=0;
    for(LL i=0;i<=n-u;i++)res=(res+dfs(z+1,u+i,a+((b+i)&1),(b+i)>>1)*power[z][i]%mod*C[u+i][i]%mod)%mod;
    return dp[z][u][a][b]=res;
}
int main()
{
    memset(dp,1LL*(-1),sizeof(dp));
    scanf("%lld%lld%lld",&n,&m,&k);
    for(LL i=0;i<=m;i++)scanf("%lld",&v[i]);
    C[0][0]=1; 
    for(LL i=1;i<=n;i++)
    {
        for(LL j=C[i][0]=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    for(LL i=0;i<=m;i++)
    {
        power[i][0]=1;
        for(LL j=1;j<=n;j++)power[i][j]=(power[i][j-1]*v[i])%mod;
    }
    printf("%lld",dfs(0,0,0,0));
    return 0;
}
[方差]

考虑a[]的差分数组b[]。

将a[i]变成a[i-1]+a[i+1]-a[i],其实就是b[]相邻的两项交换!

再通过肉眼观察,就可以得到b[]最好的情况下是先单调递减,再单调递增,这样会使得方差最小,在这里,可以使用dfs(),时间复杂度O(n!),预估?分

再次回到DP这一个思路上,有:

f[i+1][j+b[i+1]*(i+1)]=min(f[i+1][j+b[i+1]*(i+1)],f[i][j]+j*2*b[i+1]+(i+1)*b[i+1]*b[i+1])

于是我们写出了这样一个好玩的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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a[10005],b[10005],f[405][240005],nowsum=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
    sort(b+1,b+n);
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<n-1;i++)
    {
        nowsum+=b[i+1];
        for(int j=0;j<=240000;j++)
        {
            f[i+1][j+nowsum]=min(f[i+1][j+nowsum],f[i][j]+nowsum*nowsum);
            f[i+1][j+b[i+1]*(i+1)]=min(f[i+1][j+b[i+1]*(i+1)],f[i][j]+j*2*b[i+1]+(i+1)*b[i+1]*b[i+1]);
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=24000;i++)ans=min(ans,n*f[n-1][i]-i*i);
    printf("%lld",ans);
    return 0;
}

你瞧,真好看!

当然上面一个代码会出问题,因为我们的DP要使用滚动数组压维度,还有j不能每次都循环240000次。

洛谷评测机好像炸了...To be continued...

发表评论

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