「杂题乱写」AtCoderDP26 题
前言
最近听说 \(\text{AtCoder}\) 上有个 \(\text{DP26}\) 题挺好的，于是向 @\(\text{SoyTony}\) 要了题单并开始做，希望可以加强我的 DP 能力。
果然我还是爱 DP 的。预计暑假集训结束前正好做完，希望能完成这个 \(\text{flag}\)。
开头的题比较简单，就不写太多了。
2022/08/11。
寒假开始前做完还差不多
其实就剩三个题了，但咕了四个月。2022/12/25
正文
A: Frog 1
思路
\[f_{i}=\min(f_{i-1}+\left|h_i-h_{i-1}\right|,f_{i-2}+\left|h_i-h_{i-2}\right|)
\]
\]
代码
点击查看代码
n=rnt(),a[0]=inf;
_for(i,1,n){
a[i]=rnt();
if(i!=1)
f[i]=min(f[i-1]+abs(a[i]-a[i-1]),f[i-2]+abs(a[i]-a[i-2]));
}
printf("%lld\n",f[n]);
B: Frog 2
思路
\[f_{i}=\min_{j=i-k}^i\{f_{j}+\left|h_i-h_{j}\right|\}
\]
\]
代码
点击查看代码
n=rnt(),k=rnt();
_for(i,1,n){
a[i]=rnt(),f[i]=i!=1?inf:0;
_for(j,max(1ll,i-k),i-1)
f[i]=min(f[i],f[j]+abs(a[i]-a[j]));
}
printf("%lld\n",f[n]);
C: Vacation
思路
\[\begin{aligned}
f_{i,0}&=\max\{f_{i-1,1},f_{i-1,2}\}+a_i\\
f_{i,1}&=\max\{f_{i-1,0},f_{i-1,2}\}+b_i\\
f_{i,2}&=\max\{f_{i-1,1},f_{i-1,0}\}+c_i\\
\end{aligned}
\]
f_{i,0}&=\max\{f_{i-1,1},f_{i-1,2}\}+a_i\\
f_{i,1}&=\max\{f_{i-1,0},f_{i-1,2}\}+b_i\\
f_{i,2}&=\max\{f_{i-1,1},f_{i-1,0}\}+c_i\\
\end{aligned}
\]
代码
点击查看代码
n=rnt();
_for(i,1,n){
a[i]=rnt(),b[i]=rnt(),c[i]=rnt();
f[i][0]=max(f[i-1][1],f[i-1][2])+a[i];
f[i][1]=max(f[i-1][0],f[i-1][2])+b[i];
f[i][2]=max(f[i-1][1],f[i-1][0])+c[i];
}
printf("%lld\n",max(f[n][0],max(f[n][1],f[n][2])));
D: Knapsack 1
思路
背包板子。
代码
点击查看代码
n=rnt(),m=rnt();
_for(i,1,n){
w[i]=rnt(),v[i]=rnt();
for_(j,m,w[i])f[j]=max(f[j],v[i]+f[j-w[i]]);
}
printf("%lld\n",f[m]);
E: Knapsack 2
思路
这道题中 \(w\) 很大，我们可以把背包倒着用。
即我们设 \(f_{i,j}\) 表示在前 \(i\) 能选出价值为 \(j\) 的最小体积。
转移方程显然为：
\[f_{i,j}=\min\{f_{i,j},f_{i-1,j-v_i}+w_i\}
\]
\]
代码
点击查看代码
n=rnt(),m=rnt(),f[0]=1;
_for(i,1,1e5)f[i]=inf;
_for(i,1,n){
w[i]=rnt(),v[i]=rnt();
for_(j,1e5,v[i])if(f[j-v[i]]<inf)f[j]=min(f[j],f[j-v[i]]+w[i]);
}
_for(i,1,1e5)if(f[i]-1<=m)ans=i;
printf("%lld\n",ans);
F: LCS
思路
又是个板子。
转移方程：
\[f_{i,j}=
\begin{cases}
\max\{f_{i-1,j},f_{i,j-1}\}&s_i\neq t_j\\
\max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1\}&s_i=t_j\\
\end{cases}
\]
\begin{cases}
\max\{f_{i-1,j},f_{i,j-1}\}&s_i\neq t_j\\
\max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1\}&s_i=t_j\\
\end{cases}
\]
代码
点击查看代码
const ll N=3010,inf=1ll<<40;
ll n,m,f[N][N],jl[N][N],li[N][N],lj[N][N],ans,w;
char s[N],t[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
void print(ll i,ll j){
if(li[i][j]&&lj[i][j])print(li[i][j],lj[i][j]);
if(jl[i][j])putchar(s[i]);
}
inline void In(){
scanf("%s",s+1),n=strlen(s+1);
scanf("%s",t+1),m=strlen(t+1);
_for(i,1,n){
_for(j,1,m){
if(f[i-1][j]<f[i][j-1])f[i][j]=f[i][j-1],li[i][j]=i,lj[i][j]=j-1,jl[i][j]=0;
else f[i][j]=f[i-1][j],li[i][j]=i-1,lj[i][j]=j,jl[i][j]=0;
if(s[i]==t[j]&&f[i][j]<=f[i-1][j-1]+1)f[i][j]=f[i-1][j-1]+1,li[i][j]=i-1,lj[i][j]=j-1,jl[i][j]=1;
}
}
_for(i,1,n)if(ans<f[i][m])ans=f[i][m],w=i;
print(w,m),puts("");
return;
}
}
G: Longest Path
思路
经典拓扑题。
设 \(dis_u\) 是到 \(u\) 的最长路，则显然有转移方程：
\[dis_u=\max_{(v,u)\in\mathbb{E}}\{dis_v\}+1
\]
\]
可以发现最后一个到点 \(u\) 的点 \(v\) 一定是层数最深的，也是 \(\max_{(v,u)\in\mathbb{E}}\{dis_v\}\)。
那么我们每次到点 \(u\) 都将其入度减一，如果有一个点把它的入度减成了 \(0\)，那么这个点就是我们要求的点 \(v\)。
时间复杂度 \(\Theta(n+m)\)。
代码
点击查看代码
const ll N=1e5+10,inf=1ll<<40;
ll n,m,dis[N],in[N],ans;vector<ll>tu[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void GetDis(){
queue<pair<ll,ll> >q;
_for(i,1,n)if(!in[i])q.push(make_pair(i,0));
while(!q.empty()){
ll u=q.front().first;
dis[u]=q.front().second,q.pop();
far(v,tu[u]){
--in[v];
if(!in[v])q.push(make_pair(v,dis[u]+1));
}
}
return;
}
inline void In(){
n=rnt(),m=rnt();
_for(i,1,m){
ll x=rnt(),y=rnt();
++in[y],tu[x].push_back(y);
}
GetDis();
_for(i,1,n)ans=max(ans,dis[i]);
printf("%lld\n",ans);
return;
}
}
H: Grid 1
思路
\[f_{i,j}=
\begin{cases}
\max{f_{i,j},f_{i-1,j}} &a_{i-1,j}&=\ '\!\#'\\
\max{f_{i,j},f_{i,j-1}} &a_{i,j-1}&=\ '\!\#'\\
0 &a_{i,j}&=\ '\!\#'
\end{cases}
\]
\begin{cases}
\max{f_{i,j},f_{i-1,j}} &a_{i-1,j}&=\ '\!\#'\\
\max{f_{i,j},f_{i,j-1}} &a_{i,j-1}&=\ '\!\#'\\
0 &a_{i,j}&=\ '\!\#'
\end{cases}
\]
代码
点击查看代码
const ll N=1010,P=1e9+7,inf=1ll<<40;
ll n,m,f[N][N];char a[N][N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline ll rch(){
char c=getchar();
while(c!='.'&&c!='#')c=getchar();
return c;
}
inline void In(){
n=rnt(),m=rnt();
_for(i,1,n){
_for(j,1,m){
a[i][j]=rch();
if(a[i][j]!='#'){
if(i==1&&j==1){f[i][j]=1;continue;}
if(a[i-1][j]=='.')f[i][j]=(f[i][j]+f[i-1][j])%P;
if(a[i][j-1]=='.')f[i][j]=(f[i][j]+f[i][j-1])%P;
}
}
}
printf("%lld\n",f[n][m]);
return;
}
}
I: Coins
思路
期望 DP。
设 \(f_{i,j}\) 表示前 \(i\) 个硬币里正面朝上的硬币有 \(j\) 个的概率，则转移方程为：
\[f_{i,j}=f_{i-1,j-1}\times p_i+f_{i-1,j}\times(1-p_i)
\]
\]
最终答案为：
\[\sum_{i=\left\lceil\tfrac{n}{2}\right\rceil}^{n}f_{n,i}
\]
\]
代码
点击查看代码
const ll N=3010,inf=1ll<<40;
ll n;ldb a[N],f[N][N],ans;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline ll rch(){
char c=getchar();
while(c!='.'&&c!='#')c=getchar();
return c;
}
inline void In(){
n=rnt();
f[0][0]=1.0;
_for(i,1,n){
scanf("%Lf",&a[i]);
_for(j,0,i){
f[i][j]=f[i-1][j]*(1-a[i]);
if(j)f[i][j]+=f[i-1][j-1]*a[i];
}
}
_for(i,((n-1)>>1)+1,n)ans+=f[n][i];
printf("%.12Lf\n",ans);
return;
}
}
J: Sushi
思路
设 \(f_{i,j,k}\) 表示当前有 \(i\) 盘剩 \(1\) 个，有 \(j\) 盘剩 \(2\) 个，有 \(k\) 盘剩 \(3\) 个。
剩一个的盘子吃完就吃完了，剩两个的盘子吃完会多一个剩一个的盘子，剩三个的盘子吃完会多一个剩两个的盘子。所以 \(f_{i,j,k}\) 应从 \(f_{i-1,j,k},f_{i+1,j-1,k},f_{i,j+1,k-1}\) 转移过来。
直接算一下每种盘子被选中的概率即可，转移方程：
\[\begin{aligned}
f_{i,j,k}&=1+\frac{n-i-j-k}{n}\times f_{i,j,k}+\frac{i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{n}\\
\frac{i+j+k}{n}\times f_{i,j,k}&=1+\frac{i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{n}\\
f_{i,j,k}&=\frac{n+i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{i+j+k}\\
\end{aligned}
\]
f_{i,j,k}&=1+\frac{n-i-j-k}{n}\times f_{i,j,k}+\frac{i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{n}\\
\frac{i+j+k}{n}\times f_{i,j,k}&=1+\frac{i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{n}\\
f_{i,j,k}&=\frac{n+i\times f_{i-1,j,k}+j\times f_{i+1,j-1,k}+k\times f_{i,j+1,k-1}}{i+j+k}\\
\end{aligned}
\]
时间复杂度 \(\Theta(n^3)\)。
代码
点击查看代码
n=rnt();
_for(i,1,n){
a[i]=rnt();
if(a[i]==1)++c1;
if(a[i]==2)++c2;
if(a[i]==3)++c3;
}
_for(k,0,n){
_for(j,0,n){
_for(i,0,n){
if(i)f[i][j][k]+=f[i-1][j][k]*(ldb(i)/ldb(i+j+k));
if(j)f[i][j][k]+=f[i+1][j-1][k]*(ldb(j)/ldb(i+j+k));
if(k)f[i][j][k]+=f[i][j+1][k-1]*(ldb(k)/ldb(i+j+k));
if(i||j||k)f[i][j][k]+=(ldb(n)/ldb(i+j+k));
}
}
}
printf("%.10Lf\n",f[c1][c2][c3]);
K: Stones
思路
设 \(f_i\) 表示剩余 \(i\) 个石子时先手取能不能赢。
可以发现如果 \(f_{i-a_j}=0\) ，那么先手肯定会取 \(a_j\) 个石子改变局势。
所以转移方程为：
\[f_i=\left[\sum_{j=1}^{n}\ !f_{i-a_j}\right]
\]
\]
代码
点击查看代码
n=rnt(),k=rnt();
_for(i,1,n)a[i]=rnt();
_for(i,1,k)_for(j,1,n)if(i>=a[j]&&!f[i-a[j]])f[i]=1;
puts(f[k]?"First":"Second");
L: Deque
思路
区间 DP。
通过当前枚举的区间的长度来判断是先手下还是后手下再转移。
转移方程为：
\[f_{i,i+k}=
\begin{cases}
\max\{f_{i+1,i+k}+a_i,f_{i,i+k-1}+a_{i+k}\} &[(n-k)\&1]\\
\min\{f_{i+1,i+k}-a_i,f_{i,i+k-1}-a_{i+k}\} &[!(n-k)\&1]\\
\end{cases}
\]
\begin{cases}
\max\{f_{i+1,i+k}+a_i,f_{i,i+k-1}+a_{i+k}\} &[(n-k)\&1]\\
\min\{f_{i+1,i+k}-a_i,f_{i,i+k-1}-a_{i+k}\} &[!(n-k)\&1]\\
\end{cases}
\]
代码
点击查看代码
n=rnt();
_for(i,1,n){
a[i]=rnt();
ll b=(n&1)?1:-1;
f[i][i]=b*a[i];
}
_for(k,1,n-1){
ll b=((n-k)&1);
_for(i,1,n-k){
if(b)f[i][i+k]=max(f[i+1][i+k]+a[i],f[i][i+k-1]+a[i+k]);
if(!b)f[i][i+k]=min(f[i+1][i+k]-a[i],f[i][i+k-1]-a[i+k]);
}
}
printf("%lld\n",f[1][n]);
M: Candies
思路
很典的前缀和优化。
设 \(g_{i,j}\) 表示选 \(j\) 颗糖恰好分给前 \(i\) 个人的方案数，转移方程为：
\[g_{i,j}=\sum_{k=j-a_i}^{j}g_{i-1,k}
\]
\]
时间复杂度 \(\Theta(nk^2)\)，需要优化一下。
那么设 \(f_{i,j}\) 表示最多选 \(j\) 颗糖分给前 \(i\) 个人的方案数，转移方程为：
\[f_{i,j}=f_{i-1,j}-f_{i-1,\max\{0,j-a_i-1\}}
\]
\]
时间复杂度 \(\Theta(nk)\)，初始状态 \(f_{0,i}=1(0\le i\le k)\)，答案为 \((f_{n,k}-f_{n,k-1})\)。
可以用滚动数组滚掉一维。
代码
点击查看代码
n=rnt(),k=rnt();
_for(i,0,k)f[i]=1;
_for(i,1,n){
a[i]=rnt();
for_(j,k,1)f[j]=(f[j]-((j<=a[i])?0:f[j-a[i]-1])+P)%P;
_for(j,0,k)f[j]=(f[j-1]+f[j])%P;
}
printf("%lld\n",(f[k]-f[k-1]+P)%P);
N: Slimes
思路
弱化版石子合并。
设 \(f_{i,j}\) 表示将 \(i\) 到 \(j\) 的数字合起来的最小代价，显然转移方程为：
\[f_{i,j}=max_{k=i}^{j-1}\{f_{i,k}+f_{k+1,j}\}\\
\]
\]
代码
点击查看代码
n=rnt();
_for(i,1,n)s[i]=s[i-1]+rnt();
_for(k,2,n){
_for(i,1,n-k+1){
f[i][i+k-1]=inf;
_for(j,i+1,i+k-1)f[i][i+k-1]=min(f[i][i+k-1],f[i][j-1]+f[j][i+k-1]);
f[i][i+k-1]+=s[i+k-1]-s[i-1];
}
}
printf("%lld\n",f[1][n]);
O: Matching
思路
数据范围 \(1\le n\le 21\)，显然是状压 DP。
设 \(f_{i,j}\) 表示前 \(i\) 个人的匹配状态为 \(j\)，因为 \(i\) 个人只能匹配上 \(i\) 个人，所以 匹配条件为\(j\) 的二进制下 \(1\) 的个数为 \(i\)，可以省掉第一位。转移方程：
\[f_j=\sum_{(\operatorname{CntOne}(j),k)\in\mathbb{E}}f_{j\oplus2^{k-1}}
\]
\]
时间复杂度 \(\Theta(n2^n)\)。
代码
点击查看代码
const ll N=25,P=1e9+7,inf=1ll<<40;
ll n,U,tu[N],f[1<<21],ans;vector<ll>qk[N];
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline ll CntOne(ll num){ll c=0;while(num)++c,num-=(num&-num);return c;}
inline void Pre(){_for(i,1,U)qk[CntOne(i)].push_back(i);return;}
inline void DP(){
f[0]=1;
_for(i,1,n){
far(j,qk[i]){
ll k=j;
while(k){
if(tu[i]&(k&-k))f[j]=(f[j]+f[j^(k&-k)])%P;
k-=(k&-k);
}
}
}
}
inline void In(){
n=rnt(),U=(1<<n)-1;
_for(i,1,n)_for(j,1,n)tu[i]|=rnt()<<(j-1);
Pre(),DP();
printf("%lld\n",f[U]);
return;
}
}
P: Independent Set
思路
很典的树形 DP。
设 \(f_{u,0/1}\) 表示节点 \(u\) 颜色为 \(0/1\) 时的方案数（\(0\) 白 \(1\) 黑）。
转移方程：
\[\begin{aligned}
f_{u,0}&=\sum_{v\ is\ u's\ son}f_{v,0}+f_{v,1}\\
f_{u,1}&=\sum_{v\ is\ u's\ son}f_{v,0}\\
\end{aligned}
\]
f_{u,0}&=\sum_{v\ is\ u's\ son}f_{v,0}+f_{v,1}\\
f_{u,1}&=\sum_{v\ is\ u's\ son}f_{v,0}\\
\end{aligned}
\]
代码
点击查看代码
const ll N=1e5+10,P=1e9+7,inf=1ll<<40;
ll n,f[N][2];vector<ll>tu[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
void Dfs(ll u,ll fa){
f[u][0]=f[u][1]=1;
far(v,tu[u]){
if(v==fa)continue;
Dfs(v,u);
f[u][0]=f[u][0]*(f[v][0]+f[v][1])%P;
f[u][1]=f[u][1]*f[v][0]%P;
}
return;
}
inline void In(){
n=rnt();
_for(i,1,n-1){
ll x=rnt(),y=rnt();
tu[x].push_back(y);
tu[y].push_back(x);
}
Dfs(1,0);
printf("%lld\n",(f[1][0]+f[1][1])%P);
return;
}
}
Q: Flowers
思路
线段树优化 DP。
设 \(f_{i}\) 表示选第 \(i\) 瓶花时最大权值，转移方程显然为：
\[f_{i}=\max_{1\le j\le i}[h_j<h_i]\times f_j
\]
\]
那么我们用线段树维护一下小于 \(h_i\) 的最大 \(f_i\) 即可。
代码
点击查看代码
const ll N=2e5+10,inf=1ll<<40;
ll n,rt,h[N],a[N],f[N],ans;
class SegmentTree{
public:
ll tot=0;
class TREE{public:ll mx,ls,rs;}tr[N<<2];
#define mx(p) tr[p].mx
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define l_s(p) ls(p),l,mid
#define r_s(p) rs(p),mid+1,r
void Update(ll &p,ll l,ll r,ll x,ll val){
if(x<l||r<x)return;
if(!p)p=++tot;
if(l==r)mx(p)=max(val,mx(p));
else{
bdmd;
Update(l_s(p),x,val);
Update(r_s(p),x,val);
mx(p)=max(mx(ls(p)),mx(rs(p)));
}
return;
}
ll Query(ll &p,ll l,ll r,ll le,ll ri){
if(ri<l||r<le||!p)return 0;
if(le<=l&&r<=ri)return mx(p);
else{
bdmd;
return max(Query(l_s(p),le,ri),Query(r_s(p),le,ri));
}
}
}tr;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline void In(){
n=rnt();
_for(i,1,n)h[i]=rnt();
_for(i,1,n)a[i]=rnt();
_for(i,1,n){
f[i]=tr.Query(rt,1,n,1,h[i])+a[i];
tr.Update(rt,1,n,h[i],f[i]);
ans=max(ans,f[i]);
}
printf("%lld\n",ans);
return;
}
}
R: Walk
思路
想一下 Floyed 是怎么跑的：
\[t_{i,j}=\max_{k=1}^{n}\{t_{i,k}+t_{k,j}\}
\]
\]
即把两条路拼起来。
本道题也可以用类似的思路。设 \(g_{i,j}\) 表示原邻接矩阵，\(f_{k,i,j}\) 表示长度为 \(k\) 的从 \(i\) 到 \(j\) 的路径有多少条。转移方程：
\[f_{k,i,j}=\sum_{d=1}^{n}f_{k-1,i,d}\times g_{d,j}
\]
\]
发现这是个矩阵乘法，于是冲个矩阵快速幂就行了。
时间复杂度 \(\Theta(n^3\log_2k)\)。
代码
点击查看代码
const ll N=110,P=1e9+7,inf=1ll<<40;
ll n,k,a[N],ans;
class Matrix{
public:
ll a[N][N];
inline void Clear(){memset(a,0,sizeof(a));return;}
inline void One(){_for(i,1,n)a[i][i]=1;return;}
inline ll* operator[](const ll x){return a[x];}
inline Matrix operator*(Matrix q){
Matrix ans;ans.Clear();
_for(i,1,n)_for(j,1,n)_for(k,1,n)
ans[i][j]=(ans[i][j]+a[i][k]*q[k][j]%P)%P;
return ans;
}
}ma;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline Matrix ksm(Matrix mat,ll b){
Matrix ans;ans.Clear(),ans.One();
while(b){
if(b&1)ans=ans*mat;
mat=mat*mat,b>>=1;
}
return ans;
}
inline ll GetAnswer(Matrix mat){
ll ans=0;
_for(i,1,n)_for(j,1,n)ans=(ans+mat[i][j])%P;
return ans;
}
inline void In(){
n=rnt(),k=rnt();
_for(i,1,n)_for(j,1,n)ma[i][j]=rnt();
printf("%lld\n",GetAnswer(ksm(ma,k)));
return;
}
}
S: Digit Sum
思路
数位 DP。
设 \(a_i\) 表示上限的第 \(i\) 位（从高位开始数），\(f_{i,j,k}(k\in\{0,1\})\) 表示第 \(i\) 位为 \(j\) 且有（\(k=1\)）无（\(k=0\)）限制的方案数。（限制指前 \(i-1\) 位是否和上限数的前 \(i-1\) 位相同）
然后就非常好转移了，初始状态 \(f_{0,0,1}=1\)，转移方程：
\[\begin{aligned}
令\ &la_1=(j-k)\mod{d}\\&la_2=(j-a_i)\mod{d}\\
&f_{i,j,k}=
\begin{cases}
\sum_{l=0}^{9}f_{i-1,la_1,0}+\sum_{l=0}^{a_{i}-1}f_{i-1,la_1,1}&k=0\\
f_{i-1,la_2,1}&k=1\\
\end{cases}
\end{aligned}
\]
令\ &la_1=(j-k)\mod{d}\\&la_2=(j-a_i)\mod{d}\\
&f_{i,j,k}=
\begin{cases}
\sum_{l=0}^{9}f_{i-1,la_1,0}+\sum_{l=0}^{a_{i}-1}f_{i-1,la_1,1}&k=0\\
f_{i-1,la_2,1}&k=1\\
\end{cases}
\end{aligned}
\]
答案为 \(f_{\operatorname{lenth}(n),0,0}+f_{\operatorname{lenth}(n),0,1}-1\)（去掉 \(0\)）。
代码
点击查看代码
const ll N=1e4+10,P=1e9+7,inf=1ll<<40;
ll d,len,ans,num,f[N][110][2];char a[N];
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline void In(){
scanf("%s",a+1),d=rnt();
len=strlen(a+1);
f[0][0][1]=1;
_for(i,1,len){
a[i]-='0';
_for(j,0,d-1){
f[i][j][1]=f[i-1][((j-a[i])%d+d)%d][1];
_for(k,0,9)f[i][j][0]=(f[i][j][0]+f[i-1][((j-k)%d+d)%d][0])%P;
_for(k,0,a[i]-1)f[i][j][0]=(f[i][j][0]+f[i-1][((j-k)%d+d)%d][1])%P;
}
}
printf("%lld\n",(f[len][0][0]+f[len][0][1]-1+P)%P);
return;
}
}
T: Permutation
思路
设 \(f_{i,j}\) 表示第 \(i\) 个数是前 \(i\) 个数中第 \(j\) 大的方案数。
转移方程：
\[f_{i,j}=
\begin{cases}
\sum_{k=1}^{j-1}f_{i-1,k}&s_i=\texttt{'<'}\\
\sum_{k=j}^{i-1}f_{i-1,k}&s_i=\texttt{'>'}\\
\end{cases}
\]
\begin{cases}
\sum_{k=1}^{j-1}f_{i-1,k}&s_i=\texttt{'<'}\\
\sum_{k=j}^{i-1}f_{i-1,k}&s_i=\texttt{'>'}\\
\end{cases}
\]
代码
点击查看代码
const ll N=3e3+10,P=1e9+7,inf=1ll<<40;
ll n,f[N],sum[N],ans;char s[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void In(){
n=rnt(),scanf("%s",s+2);
_for(i,1,n){
_for(j,1,n){
if(i==1)f[j]=1;
else if(s[i]=='<')f[j]=sum[j-1];
else f[j]=(sum[i-1]-sum[j-1]+P)%P;
}
_for(j,1,n)sum[j]=(sum[j-1]+f[j])%P;
}
printf("%lld",sum[n]);
return;
}
}
U: Grouping
思路
如果你会枚举子集的话应该看一眼就知道怎么做了，但我不会。
看数据范围知状压，首先预处理出 \(val_i\)，表示把状态 \(i\) 中的每个数放在一组的得分，时间复杂度 \(\Theta(2^nn^2)\)。
然后对于每一个状态，把它的一个子集当成一组，剩下的部分从当成上一个部分转移来。即：
\[f_{i}=\max_{s\in i}f_{i\oplus s}+val_{s}
\]
\]
这部分需要枚举子集，时间复杂度 \(\Theta(3^n)\)。
代码
点击查看代码
const ll N=20,U=1<<17,inf=1ll<<40;
ll n,u,a[N][N],val[U],f[U],ans;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void Pre(){
_for(i,1,u)_for(j,1,n)if((i>>(j-1))&1)
_for(k,j+1,n)if((i>>(k-1))&1)val[i]+=a[j][k];
return;
}
inline void DP(){
_for(i,1,u)for(int j=i;j;j=(j-1)&i)
f[i]=max(f[i],f[i^j]+val[j]);
return;
}
inline void In(){
n=rnt(),u=(1<<n)-1;
_for(i,1,n)_for(j,1,n)a[i][j]=rnt();
Pre(),DP();
printf("%lld",f[u]);
return;
}
}
V: Subtree
思路
咕咕咕。
代码
点击查看代码
W: Intervals
思路
咕咕咕。
代码
点击查看代码
X: Tower
思路
比较平凡的的背包 DP。
有一个限重，那么上限就不能是 \(2\times10^4\) 了，而应该是 \(s_i+w_i\)。
然后发现直接按原顺序跑会有问题，因为有的箱子承重拉不满，会有剩余。这时只要按 \(s_i+w_i\) （即上限）排个序就行了。
不是很理解 橙题+改上限+排序 为什么等于 蓝题。
代码
点击查看代码
const ll N=1e7+10,inf=1ll<<40;
ll n,f[N],ans;
class BOX{
public:
ll w,s,v;
inline bool operator<(const BOX &bx)const{
return w+s<bx.w+bx.s;
}
}b[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void In(){
n=rnt(),f[0]=1;
_for(i,1,n)b[i].w=rnt(),b[i].s=rnt(),b[i].v=rnt();
sort(b+1,b+n+1);
_for(i,1,n)for_(j,b[i].s+b[i].w,b[i].w)
if(f[j-b[i].w])f[j]=max(f[j],f[j-b[i].w]+b[i].v);
_for(i,1,2e4)ans=max(ans,f[i]);
printf("%lld",ans-1);
return;
}
}
Y: Grid 2
思路
容斥 DP。
首先我们知道从 \((x1,y1)\) 走到 \((x2,y2)\) 的方案数为 \(cnt(x1,y1,x2,y2)=\dbinom{\left|x1+y1-x2-y2\right|}{\left|x1-x2\right|}\)。
（从 \((x1,y1)\) 走到 \((x2,y2)\) 必然需要 \(\left|x1+y1-x2-y2\right|\) 步，在其中选出 \(\left|x1-x2\right|\) 步作为向下走）
然后我们考虑一下从 \((1,1)\) 走到一个不能经过的点 \((x_i,y_i)\) 有多少种方案。答案显然不是 \(cnt(1,1,x_i,y_i)\)，因为路上会有不能经过的点。
那么进行一下容斥：用总方案数减去经过不能经过的点的方案数。
那么设 \(f_i\) 表示从 \((1,1)\) 走到一个不能经过的点 \((x_i,y_i)\) 有多少种方案，则：
\[f_i=cnt(1,1,x_i,y_i)-(\sum_{i\neq j}[x_j\le x_i][y_j\le y_i]\times cnt(x_i,y_i,x_j,y_j)\times f_j)
\]
\]
答案显然就是：
\[cnt(1,1,h,w)-\sum_{1\le i\le n}cnt(h,w,x_i,y_i)\times f_i
\]
\]
时间复杂度 \(O(n^2)\)。
代码
点击查看代码
namespace SOLVE {
typedef long double ldb;
typedef long long ll;
typedef double db;
const ll N = 1e6 + 10, M = 1e6, P = 1e9 + 7;
ll h, w, n, fac[N], inv[N], f[N], ans;
class hinder {
public:
ll x, y;
inline bool operator < (const hinder another) const {
return (x == another.x) ? (y < another.y) : (x < another.x);
}
} hd[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline ll FastPow (ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P, b >>= 1;
}
return ans;
}
inline void Pre () {
fac[0] = 1;
_for (i, 1, M) fac[i] = fac[i - 1] * i % P;
inv[M] = FastPow (fac[M], P - 2);
for_ (i, M - 1, 0) inv[i] = inv[i + 1] * (i + 1) % P;
return;
}
inline ll C (ll n, ll m) {
if (!m) return 1;
if (n < m) return 0;
return fac[n] * inv[n - m] % P * inv[m] % P;
}
inline ll GetCnt (ll i, ll j) {
return C (hd[i].x - hd[j].x + hd[i].y - hd[j].y, hd[i].x - hd[j].x);
}
inline void In () {
h = rnt (), w = rnt (), n = rnt ();
_for (i, 1, n) hd[i].x = rnt (), hd[i].y = rnt ();
std::sort (hd + 1, hd + n + 1);
hd[0].x = hd[0].y = 1, hd[n + 1].x = h, hd[n + 1].y = w;
return;
}
inline void Solve () {
_for (i, 1, n) {
f[i] = GetCnt (i, 0);
_for (j, 1, i - 1) {
if (hd[j].y > hd[i].y) continue;
f[i] = (f[i] - GetCnt (i, j) * f[j] % P + P) % P;
}
}
ans = GetCnt (n + 1, 0);
_for (j, 1, n) ans = (ans - GetCnt (n + 1, j) * f[j] % P + P) % P;
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
Z: Frog3
思路
正序开不动了，那就尝试一下倒序开题破局！
斜率优化 DP 板子。
随便推一推可得到式子：
\[h_j^2+f_j=2h_ih_j+f_i-h_i^2-c
\]
\]
令：
\[\begin{cases}
x=h_j\\
y=h_j^2+f_j\\
k=2h_i\\
b=f_i-h_i^2-c
\end{cases}
\]
x=h_j\\
y=h_j^2+f_j\\
k=2h_i\\
b=f_i-h_i^2-c
\end{cases}
\]
然后直接套个斜率优化结束。
代码
点击查看代码
const ll N=2e5+10,inf=1ll<<40;
ll n,c,h[N],f[N],ans;
ll q[N],hd=1,tl=1;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline ll k(ll i){return 2*h[i];}
inline ll b(ll i){return f[i]-h[i]*h[i]-c;}
inline ll x(ll i){return h[i];}
inline ll y(ll i){return h[i]*h[i]+f[i];}
inline void DP(){
q[1]=1;
_for(i,2,n){
while(hd<tl&&(y(q[hd+1])-y(q[hd]))<=k(i)*(x(q[hd+1])-x(q[hd])))++hd;
f[i]=y(q[hd])-k(i)*x(q[hd])-b(i);
while(hd<tl&&(x(q[tl])-x(q[tl-1]))*(y(i)-y(q[tl]))<=(x(i)-x(q[tl]))*(y(q[tl])-y(q[tl-1])))--tl;
q[++tl]=i;
}
return;
}
inline void In(){
n=rnt(),c=rnt();
_for(i,1,n)h[i]=rnt();
DP();
printf("%lld\n",f[n]);
return;
}
}
