刚刚过去的NOIP2021大家还好吗?
DAY -1:看考场
DAY0：
[报数]
考场的时候没有想到预处理，害怕1e7数组会爆掉，打了一个暴力就溜了。
这个题其实就是预处理，方法有点类似于朴素筛法，
稍微做了一点点改动（时间复杂度O(nlogn)）。
一个坑点：当输入的x=(1e7-2)的时候，答案是会等于1e7+1的，所以要预处理到1e7+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<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）
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
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
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
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...
，则
（倍数形式）
（莫比乌斯函数性质）
（③式推导，gcd问题常用）
