「NOWCODER」CSP-S模拟赛第3场
「NOWCODER」CSP模拟赛第3场
感觉是比较好的一套题 因为几乎都有思路
可惜只打了一个小时
附一下出题人的玄学题解
T1 货物收集
题目
考场思路即正解
一道比较简单的题，结果 PPLPPLPPL 因为编译器原因爆 000 了 咕咕咕
我的时间复杂度 O(N⋅log2N)O(N\cdot log_2^N)O(N⋅log2N)。
就是处理出到达每个点所需要的最小武力值，再按照其从小到大排序。
最后用一个 lower_bound() 找到只需要到哪个点就行了。
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
#define rep(q,__a,__b) for(int q=__a,q##_end_=__b;q<=q##_end_;++q)
#define dep(q,__a,__b) for(int q=__a,q##_end_=__b;q>=q##_end_;--q)
template<class T>inline void qread(T& x){
char c;bool f=false;x=0;
while((c=getchar())<'0'||'9'<c)if(c=='-')f=true;
for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
inline int rqread(){
char c;bool f=false;int x=0;
while((c=getchar())<'0'||'9'<c)if(c=='-')f=true;
for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int r,const int MOD)
{inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;}
const int MAXN=1e6;
struct edge{
int to,nxt,w;
edge(){}
edge(const int T,const int N,const int W):to(T),nxt(N),w(W){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],cnt;
inline void add_edge(const int u,const int v,const int w){
e[++cnt]=edge(v,tail[u],w);tail[u]=cnt;
e[++cnt]=edge(u,tail[v],w);tail[v]=cnt;
}
struct node{int v,low;
bool operator<(const node a)const{return low<a.low;}
}p[MAXN+5];
int N,W,pre[MAXN+5];
void dfs(const int u,const int pre,const int w){
p[u].low=w;
for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
dfs(v,u,Max(w,e[i].w));
}
signed main(){
// freopen("2.in","r",stdin);
qread(N,W);
for(int i=2;i<=N;++i)qread(p[i].v);
for(int i=1,u,v,w;i<N;++i){
qread(u,v,w);
add_edge(u,v,w);
}
dfs(1,0,0);
sort(p+1,p+N+1);
rep(i,1,N)pre[i]=pre[i-1]+p[i].v;
// rep(i,1,N)printf("%d ",pre[i]);
int ansp=lower_bound(pre+1,pre+N+1,W)-pre;
printf("%lld\n",p[ansp].low);
return 0;
}
T2 货物分组
题目
考场思路
定义 dp[i][j]dp[i][j]dp[i][j]：第 iii 个物品及之前划分出 jjj 个背包
那么状转dp[i][j]=Min(dp[i][j],dp[k][j−1]+j∗(pre[i]−pre[k])+(maxx−minn))dp[i][j]=Min(dp[i][j],dp[k][j-1]+j*(pre[i]-pre[k])+(maxx-minn))dp[i][j]=Min(dp[i][j],dp[k][j−1]+j∗(pre[i]−pre[k])+(maxx−minn))时间复杂度 O(N3)O(N^3)O(N3)。
考虑到从后往前 dpdpdp ，再使用单调栈优化，然后…没时间码了…
考场代码：
#include<cstdio>
#include<cstring>
#define int long long
#define rep(__i,__a,__b) for(int __i=__a,__i##_end_=__b;__i<=__i##_end_;++__i)
#define dep(__i,__a,__b) for(int __i=__a,__i##_end_=__b;__i>=__i##_end_;--__i)
#define lc (i<<1)
#define rc (i<<1|1)
template<class T>inline void qread(T& x){
char c;bool f=false;x=0;
while((c=getchar())<'0'||'9'<c)if(c=='-')f=true;
for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
inline int rqread(){
char c;bool f=false;int x=0;
while((c=getchar())<'0'||'9'<c)if(c=='-')f=true;
for(x=(c^48);'0'<=(c=getchar())&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int r,const int MOD)
{inv[0]=inv[1]=1;for(int i=2;i<=r;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;}
const int MAXN=5000;
const int INF=1ll<<60;
int N,W,a[MAXN+5],dp[MAXN+5][MAXN+5],pre[MAXN+5];
signed main(){
qread(N,W);
rep(i,1,N)qread(a[i]),pre[i]=pre[i-1]+a[i];
for(int i=0;i<=N;++i)for(int j=0;j<=N;++j)dp[i][j]=INF;
dp[0][0]=0;
int maxx,minn;
rep(i,1,N)rep(j,1,i){
maxx=minn=a[i];
dep(k,i-1,0){//从 k+1 到 i 是一个新的背包
//i:当前点
//j:打包数量
//k:上一个打包的起点
if(pre[i]-pre[k]>W)break;//背包爆掉
dp[i][j]=Min(dp[i][j],dp[k][j-1]+j*(pre[i]-pre[k])+(maxx-minn));
maxx=Max(maxx,a[k]);
minn=Min(minn,a[k]);
}
}
// rep(i,1,N){
// printf("Now i==%-20lld\n",i);
// printf("debug:>arr : ");
// rep(j,1,i)printf("%-20lld ",dp[i][j]);
// puts("");
// }
int ans=INF;
rep(j,1,N)ans=Min(ans,dp[N][j]);
printf("%lld\n",ans);
return 0;
}
题解
60pts 算法：一维 DP
我们的状态是二维的，转移是一维的，考虑怎么降维进行 dpdpdp。
考虑压缩状态，这里有一道题十分类似：小奇探险
这道题有什么共通之处呢？前面的选择都会影响后面选择的价值。
而 小奇探险 选择倒着 dpdpdp ，每次前面选择都再 *k 就处理好后面的选择因为前面选择而造成的影响。
这道题也可以用类似的思想，就可以剪掉一层循环。
定义 dp[i]dp[i]dp[i] ：前 iii 个点分了一些组，最后一个组以 iii 为结尾时的最小花费。
而这个 dpdpdp 还要算上后面的花费，不清楚？看看状转：
dp[i]=dp[j−1]+{a[k]max−a[k]min∣k∈[j,i]}+∑l=i+1l≤Na[l],j∈[1,i]dp[i]=dp[j-1]+\{a[k]_{max}-a[k]_{min}|k\in [j,i]\}+\sum_{l=i+1}^{l\le N}a[l],j\in [1,i]dp[i]=dp[j−1]+{a[k]max−a[k]min∣k∈[j,i]}+l=i+1∑l≤Na[l],j∈[1,i]后面的 ∑\sum∑ 求得就是前面的选择对于后面的花费造成的影响。
这样，我们就剪掉一维，实现 60pts60pts60pts 的算法了。
100pts 算法：一维 DP ？线段树 + 单调栈 优化 ！
我们设 dp′[j]=dp[j]+{a[k]max−a[k]min∣k∈[j+1,i]}dp'[j]=dp[j]+\{a[k]_{max}-a[k]_{min}|k\in [j+1,i]\}dp′[j]=dp[j]+{a[k]max−a[k]min∣k∈[j+1,i]}。
Q 为什么没有 ∑\sum∑ 部分？
因为每个 dpdpdp 都会加上一个求和部分。
所以对于 dpdpdp 数组来说，它是平等的，只需在最后都加上 ∑\sum∑ 部分即可。
那么，对于每一个 dp[i]dp[i]dp[i] 来说，状转即可化简为：
dp[i]=min{dp′[j]}+∑l=i+1l≤Na[l],j∈[0,i)dp[i]=min\{dp'[j]\}+\sum_{l=i+1}^{l\le N}a[l],j\in [0,i)dp[i]=min{dp′[j]}+l=i+1∑l≤Na[l],j∈[0,i)对于这个状态转移，似乎是没有什么问题的，但是当你实现起来，就会发现，这个 dp′[j]dp'[j]dp′[j] 中涉及的 {a[k]max−a[k]min∣k∈[j+1,i]}\{a[k]_{max}-a[k]_{min}|k\in [j+1,i]\}{a[k]max−a[k]min∣k∈[j+1,i]} 似乎是很难求出来的，如果要使用状态转移，就还需要一个线段树用一个 log2log_2log2 来询问区间最值。
但是为什么题目要挂一个单调栈的优化呢？这是老师的优化，但是我觉得多此一举。
维护一个单调递增的维护最大值的单调栈。
维护一个单调递减的维护最小值的单调栈。
有什么用呢？每当 iii 更改的时候，所有的对于这个维度的 dp′[j]dp'[j]dp′[j] 都会因为最大值最小值因为 iii 的更改而更改，所以，单调栈变动时，用线段树区间修改 dp′[j]dp'[j]dp′[j] 的值即可。
但既然都用线段树区间修改了，何不就只用线段树解决最大最小值呢？
这还多了一个单调栈的优化，我蒟蒻认为似乎有些麻烦。
没时间补题啊
T3 地形计算
题目
考场思路
考试的时候 T2T2T2 打到一半就走了，这道题都没来得及看。
正解
首先想暴力算法。
30pts 算法
暴力枚举四个点，再进行判断，细节不用做过多赘述，时间复杂度 O(N4)O(N^4)O(N4)。
显然可以拿到 30pts30pts30pts 的高分 老师是这么说的
60pts 算法
那么他为什么要给 60pts60pts60pts 的数据呢？
肯定是有算法呗。
只需枚举两条边，再匹配这两条边的四个点即可，这样的时间复杂度是 O(N2)O(N^2)O(N2)。
这样是可以得 60pts60pts60pts 的。
出题人说还有一个玄学情况，时间复杂度是 O(N2poly(log(n)))O(N^2poly(log(n)))O(N2poly(log(n))) ，这种也是有 60pts60pts60pts 的。
100pts 算法
似乎已经没有更好的方法了，但是我们考虑对于60分的做法，我们切换枚举顺序，从度数最大的点开始枚举。每次枚举完毕以后，删去度数最大的点，然后重复这个过程，也能统计出答案。正确性显然，我们考虑这个做法的复杂度。每次都使 nnn 减小 111，那么复杂度为 O(n+(n−1)+(n−2)+...+1)=O(n2)O(n+(n-1)+(n-2)+...+1)=O(n^2)O(n+(n−1)+(n−2)+...+1)=O(n2) 看起来没什么用，只是多了一个12\frac{1}{2}21的常数。
但是因为Venn在这种做法上施加了魔法，所以复杂度是正确的。
其实我们上述复杂度的分析，给出的复杂度上界达不到，我们考虑 O(n2)O(n^2)O(n2) 并不是他的时间复杂度。我们换一种分析方式，对于选择的每一个度数小于 m\sqrt{m}m 的点，他向外会扩展最多 m\sqrt{m}m 次。对于度数大于 m\sqrt{m}m 的点，他会向外扩展多次，但是由于所有点的度数之和不能超过 222 倍的 mmm ,所以单次均摊是 mmm 次扩展，这样的点不会超过 m\sqrt{m}m 个，因为所有点的度数之和等于 2m2m2m 。那么总时间复杂度就为 O(mm)O(m\sqrt{m})O(mm)
我觉得这一段写得还不错，直接摘录了
没时间补题啊
最新文章
- Digital Roots 1013
- javascript - 二叉树
- WPF 中动态创建、删除控件，注册控件名字，根据名字查找控件
- JS模板引擎 ：ArtTemplate （1）
- delphi 插入 HTML代码 播放器
- php编译安装configure完全配置够日常所用功能
- python之6-2高阶函数
- PHP 查询脚本
- MemoryStream生成Excel
- 【springboot】之自动配置原理
- 使用ajax请求后端程序时，关于目标程序路径问题
- FTP服务-filezilla server 配置
- Apache Commons Beanutils 二 （动态Bean - DynaBeans）
- Python之matplotlib库学习
- Ext.NET Ext.JS 常用代码片段摘录
- 【371】Twitter 分类相关
- BZOJ2303 APIO2011方格染色（并查集）
- 前端架构之路：Windows下安装Nodejs步骤
- mysql 操作sql语句 操作数据库
- 基于ffmpegSDK的开发