【比赛】高一高考集训总结赛seo优化

【比赛】高一高考集训总结赛

news/2024/10/5 11:14:28

一场比赛四道 DP
乐了
集训全学 DP 你还真给我全考 DP 啊

T1 乌龟棋 70 Pts

题面

设 $f_{i,j,k,w}$ 表示已经翻开 $i$ 张步数为 $1$ 的牌，$j$ 张步数为 $2$ 的牌，以此类推，暴力 DP 即可。
但赛时先开了个五维 DP 数组，然后发现开不下；
正常人到这就会想到要压掉一位了，但我直接用 滚动数组 强行开下了。
然后就 $\text{TLE} \to 70 $

点击查看代码

#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=355;
int f[45][45][45][45];
int n,m,x;
int a[N],c[10];
inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x;
}
int main(){freopen("a.in","r",stdin); freopen("a.out","w",stdout); n=read();m=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=m;i++)c[read()]++;f[0][0][0][0]=a[1];for(int i1=0;i1<=c[1];i1++){for(int i2=0;i2<=c[2];i2++){for(int i3=0;i3<=c[3];i3++){for(int i4=0;i4<=c[4];i4++){int now=1+i1+i2*2+i3*3+i4*4;int &v=f[i1][i2][i3][i4];if(i1!=0)v=max(v,f[i1-1][i2][i3][i4]+a[now]);if(i2!=0)v=max(v,f[i1][i2-1][i3][i4]+a[now]);if(i3!=0)v=max(v,f[i1][i2][i3-1][i4]+a[now]);if(i4!=0)v=max(v,f[i1][i2][i3][i4-1]+a[now]);}}}}cout<<f[c[1]][c[2]][c[3]][c[4]];return 0;
}

T2 划分大理石 100Pts

题面

多重背包，二进制拆分。
数据过水导致很多乱搞做法可以通过。

赛后这题被加了 $6$ 组测试数据。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20005;
int a[7],sum;
int w[N],f[N],cnt;
int main(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);while(1){scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6]);sum=a[1]+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6;if(!sum)break;if((sum&1)){puts("Can't");continue;}sum/=2;f[0]=1;for(int i=1;i<=6;i++){int tmp=a[i],j=1;while(tmp>j){tmp-=j;w[++cnt]=j*i;j<<=1;}if(tmp)w[++cnt]=tmp;}for(int i=1;i<=cnt;i++){for(int j=sum;j>=w[i];j--){f[j]=(f[j]||f[j-w[i]]);}}if(f[sum])puts("Can");else puts("Can't");}return 0;
}

T3 干草堆 47Pts

题面

神仙斜率优化 DP，反正我没想出来。

倒序输入和处理，设 $sum_i$ 表示前 $i$ 块的前缀和，$f_i$ 表示处理到第 $i$ 块时的最大高度，$g_i$ 表示处理到第 $i$ 块时的最小宽度，有转移方程：

\[f_i=f_{j+1}+1 \]

\[g_i=sum_i-sum_{j+1} \]

其中 $j$ 为从 $i$ 到 $n$ 中最小的使得 $g_{j+1} \le sum_i-sum_{k+1}$ 的 $j$。

由于数据过水，这个 $O(n^2)$ 的代码已经可以 A 了。
但我们可以使用单调栈维护这个式子，将复杂度降至 $O(n)$。

赛时先打了贪心做法，小样例直接过，大样例直接死，发现贪心假了；
然后死活想不出来 DP 状态怎么设计，然后测试点分治贪心 + 爆搜；
然后分治出了点小锅，T 了一个点，$53 \to 47$。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int f[N],w[N],sum[N],g[N];
int n;
int q[N],l=1,r=0;
int main(){freopen("c.in","r",stdin);freopen("c.out","w",stdout);cin>>n;for(int i=n;i;i--){cin>>w[i];}for(int i=1;i<=n;i++){sum[i]=sum[i-1]+w[i];}q[++r]=0;for(int i=1;i<=n;i++){while(l<r&&sum[q[l+1]]+g[q[l+1]]<=sum[i])l++;f[i]=f[q[l]]+1;g[i]=sum[i]-sum[q[l]];while(l<r&&sum[q[r]]+g[q[r]]>=sum[i]+g[i])r--;q[++r]=i;}cout<<f[n];return 0;
}

T4 围栏障碍训练场 100Pts

题面

数据结构优化 DP。

设 $f_{i,0}$ 表示到第 $i$ 条栅栏后从左边走的最小值，$f_{i,1}$ 表示从右边走的最大值。
设 $l_i$ 表示栅栏 $i$ 的左端点，$r_i$ 表示右端点，则有转移方程：

\[\begin{gather*}f_{j,0}=f_{i,0}+|l_i-l_j|\\f_{j,1}=f_{i,0}+|r_j-l_i|\\f_{k,0}=f_{i,1}+|r_i-l_k|\\f_{k,1}=f_{i,1}+|r_k-r_i| \end{gather*} \]

其中，$j$ 为 $i+1$ 到 $n$ 中满足 $l_j<l_i<r_j$ 的第一个 $j$，$k$ 为满足 $l_k<r_i<r_k$ 的第一个 $k$。

然后数据水了，$O(n^2)$ 的暴力过了。
但是这题 $n$ 只有 $3 \times 10^4$，卡不掉 $n^2$。
所以没补正解。整洁转自涛哥。

$O(n^2)$

#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
using namespace std;
typedef long long ll;
const int N=3e4+5;
int f[N][2],n,s;
int l[N],r[N];
int ans=INT_MAX;
int main(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);scanf("%d%d",&n,&s);for(int i=n;i;i--)scanf("%d%d",&l[i],&r[i]);memset(f,0x3f,sizeof(f));f[1][0]=s-l[1],f[1][1]=r[1]-s;for(int i=1;i<=n;i++){if(f[i][0]==0x3f3f3f3f&&f[i][1]==0x3f3f3f3f)continue;int a=l[i],b=r[i];bool fa=0,fb=0;for(int j=i+1;j<=n;j++){if(fa==1&&fb==1)break;if(l[j]<a&&a<r[j]&&(!fa)){f[j][0]=min(f[j][0],f[i][0]+a-l[j]);f[j][1]=min(f[j][1],f[i][0]+r[j]-a);fa=1;}if(l[j]<b&&b<r[j]&&(!fb)){f[j][0]=min(f[j][0],f[i][1]+b-l[j]);f[j][1]=min(f[j][1],f[i][1]+r[j]-b);fb=1;}}if(!fa)ans=min(ans,f[i][0]+abs(a));if(!fb)ans=min(ans,f[i][1]+abs(b));}printf("%d",ans);return 0;
}

正解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,s,a[N],b[N],res[N][2];
int t[N<<3];
inline void pushdown(int x)
{if(t[x]){t[x<<1]=t[x<<1|1]=t[x];t[x]=0;}return ;
}
inline void change(int x,int l,int r,int ql,int qr,int q)
{if(ql<=l&&r<=qr){t[x]=q;return ;}pushdown(x);int mid=l+r>>1;if(ql<=mid)change(x<<1,l,mid,ql,qr,q);if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,q);return ;
}
inline int query(int x,int l,int r,int q)
{if(l==r)return t[x];pushdown(x);int mid=l+r>>1;if(q<=mid)return query(x<<1,l,mid,q);return query(x<<1|1,mid+1,r,q);
}
int main()
{freopen("d.in","r",stdin);freopen("d.out","w",stdout);cin>>n>>s;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];for(int i=1,q;i<=n;i++){q=query(1,-N,N,a[i]);res[i][0]=min(res[q][0]+abs(a[i]-a[q]),res[q][1]+abs(b[q]-a[i]));q=query(1,-N,N,b[i]);res[i][1]=min(res[q][0]+abs(b[i]-a[q]),res[q][1]+abs(b[q]-b[i]));change(1,-N,N,a[i],b[i],i);}cout<<min(res[n][0]+abs(a[n]-s),res[n][1]+abs(b[n]-s));return 0;
}