提高组模拟5题解
syzxzqy
·
·
个人记录
12345（five）
q
题目大意
题目意为有若干个由 1、2、3、4、5 构成的 n 位数，求有多少个数满足 \pmod 3=1。
题目分析
对于任意一个数 x，x≡x 的数字和 \pmod 3。
原题意相当于有 n 个位置，在其中可以填入 1、2、3、4、5 这五个数，求他们的和模 3 余 1 的方案数。
这是一个典型的 DP 题目。
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define ri register int
#define p(i,j) (i+j+6)%3//计算i和j模3的和，加6是排除负数
using namespace std;
const int N=1e6+10,mod=1e5+7;
int n,f[N][3];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
freopen("five.in","r",stdin);
freopen("five.out","w",stdout);
cin>>n;f[0][0]=1;//初始化：什么数也不填，余数为1的方案数为1。
for(ri i=1;i<=n;++i)//枚举位置
for(ri j=0;j<3;++j)//枚举当前余数
for(ri k=1;k<=5;++k)//枚举当前的数
(f[i][j]+=f[i-1][p(j,-k)])%=mod;//方程式
cout<<f[n][1];
}
```
## [出题（Pro）](https://www.luogu.com.cn/problem/P2686)
### 题目分析
这也是一个典型的 DP 题目。
$dp_{i,j}$ 表示所有题目的左端点 $\leqslant i$ 以及右端点 $\leqslant j$ 的难度最大值。
$a_i$ 为题面长度的前缀和,$w_i$ 为难度的前缀和。
在左端点为 $i$ 以及右端点 $j$ 时分类讨论：
首先，$dp_{i,j}$ 可以从 $dp_{i-1,j}$ 中转移过来，意为不取当前点；
同理，$dp_{i,j}$ 也可以从 $dp_{i,j-1}$ 中转移过来；
当长度范围满足条件时 $(l\leqslant a_j-a_{i-1}\leqslant r)$，$dp_{i,j}$ 可以从 $dp_{i-1,j-1}$ 中转移过来，再加上当前难度 $w_j-w_{i-1}$。
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define ri register int
using namespace std;
const int N=1e3+10;
int n,l,r,x,f[N][N],a[N],w[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
freopen("pro.in","r",stdin);
freopen("pro.out","w",stdout);
cin>>n>>l>>r;
for(ri i=1;i<=n;++i)
cin>>a[i],a[i]+=a[i-1];//前缀和
for(ri i=1;i<=n;++i)
cin>>w[i],w[i]+=w[i-1];
for(ri i=1;i<=n;++i)
for(ri j=i;j<=n;++j){
f[i][j]=max(f[i-1][j],f[i][j-1]);//不取当前点
if(l<=a[j]-a[i-1]&&a[j]-a[i-1]<=r)
f[i][j]=max(f[i][j],f[i-1][j-1]+w[j]-w[i-1]);//取当前点
}
cout<<f[n][n];
}
```
## [蛋糕(Cake)](https://www.luogu.com.cn/problem/P1528)
### 题目分析
正解思路：贪心思想+二分答案+$dfs$ 判断。
但是纯贪心思想+二分答案就能 $70$ 分，这说明真实答案与此错解较为接近，我们为了避免繁杂的 $dfs$ 程序，可以应用随机化，进行随机化贪心。
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define ri register int
using namespace std;
const int N=1e6+10;
int l,r,ans,n,m,a[N],b[N],c[N];
bool check(int mid){
for(ri p=1,i,j;p<=1500;++p){//在时间范围内随机次数越多越好
for(i=1;i<=n;++i) c[i]=a[i];
random_shuffle(c+1,c+1+n);//随机化
bool flag=0;
for(i=mid;i>=1;--i){//贪心：从大的开始
for(j=1;j<=n;++j)
if(c[j]>=b[i]){//贪心：能取尽量取
c[j]-=b[i];break;
}
if(j>n){
flag=1;break;
}
}
if(!flag) return 1;
}
return 0;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
cin>>n;
for(ri i=1;i<=n;++i) cin>>a[i];
cin>>m;
for(ri i=1;i<=m;++i) cin>>b[i];
sort(b+1,b+1+m);//排序
l=1;r=m;
while(l<=r){
ri mid=l+r>>1;//二分答案
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans;
}
```