最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球微动态丨「杂题乱写」AtCoderDP26 题

来源：博客园

「杂题乱写」AtCoderDP26 题

\(\text{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}\]

代码

点击查看代码
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]]

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}\]

代码

点击查看代码
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]

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;vectortu[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 >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}\]

代码

点击查看代码
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}\]

时间复杂度 \(\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}\]

代码

点击查看代码
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;vectorqk[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<

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}\]

代码

点击查看代码
const ll N=1e5+10,P=1e9+7,inf=1ll<<40;ll n,f[N][2];vectortu[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\) 的最大 \(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,rvoid Update(ll &p,ll l,ll r,ll x,ll val){if(x

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}\]

答案为 \(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}\]

代码

点击查看代码
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)\)。

枚举子集为什么是 \(\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<

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
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}\]
然后直接套个斜率优化结束。
代码
点击查看代码
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
                 

关键词：         
       点击查看 
              
       转移方程 
              
       时间复杂度