「CSP-S模拟赛」2019第三场
2024-08-24 06:01:09
目录
这次考试感觉好悲哀啊。
\(T2\) 过掉了，而且居然还跑了 \(LOJ\) 上最快的纪录。
结果 \(T1\) 挖穿了...
\(T3\) 一如既往地不可做...
膜拜 \(\text{JZM}\) 大佬当场 \(A\) 掉 \(T3\)（虽然他的
writeint没开 \(long\space long\) 把他自己坑掉了 \(90pts\)）
因此再引用一下这句话十年准备一场空，不开 \(long\space long\) 见祖宗
这句话其实是很精辟的。
所以说，#deding int long long其实是很有用的...
T1 「POI2007」山峰和山谷 Ridges and Valleys
题目
考场思路（几近正解）
很简单呀，就是跑一边 dfs （其实 bfs 也可以）。
结果我手残多打了一个地方，导致我的算法正确性被自己坑掉了...
#include<cstdio>
// #define FILEOI
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define dep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&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 qread(){
int x=0;char c;bool f=1;
while(cg<'0'||'9'<c)if(c=='-')f=0;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?x:-x;
}
#undef cg
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;}
template<class T>void fwrit(T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>10)fwrit(x/10);
return (void)(putchar(x%10^48));
}
const int MAXN=1e3;
const int chkDir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int scDir[][2]={{0,1},{0,-1},{1,0},{-1,0},{1,-1},{1,1},{-1,1},{-1,-1}};
int w[MAXN+5][MAXN+5],n,tot0,tot1;
bool vis[MAXN+5][MAXN+5];
inline void init(){
qread(n);
rep(i,1,n)rep(j,1,n)qread(w[i][j]);
}
inline bool inside(const int x,const int y){
return 0<x&&x<=n&&0<y&&y<=n;
}
inline bool check(const int x,const int y,const bool f){
//若 f 为 1, 则检测四周不能大于它
//若 f 为 0, 则检测四周不能小于它
int tx,ty;
if(f){
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(inside(tx,ty)&&w[tx][ty]>w[x][y])return false;
}
}
else{
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(inside(tx,ty)&&w[tx][ty]<w[x][y])return false;
}
}
return true;
}
inline bool dfs(const int x,const int y,const bool f){
vis[x][y]=true;
int tx,ty;bool ret=true;
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(!inside(tx,ty)||w[tx][ty]!=w[x][y]||vis[tx][ty])continue;
ret=ret&check(tx,ty,f);
ret=ret&dfs(tx,ty,f);
}
return ret;
}
inline void algor(){
rep(i,1,n)rep(j,1,n)if(!vis[i][j]){
if(!check(i,j,0)&&!check(i,j,1)){//这个地方有问题...
vis[i][j]=true;
continue;
}
if(check(i,j,0)&&dfs(i,j,0))++tot0;
if(check(i,j,1)&&dfs(i,j,1))++tot1;
}
}
signed main(){
#ifdef FILEOI
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
#endif
init();
algor();
printf("%d %d\n",tot1,tot0);
return 0;
}
正解
其实就是这个代码，去掉一个点（代码中有标记）。
为什么呢？因为如果我将这个点标记上 \(true\)，那么后面的搜索可能会排除掉这个有问题的点而被计入答案。
将其去掉即可。
#include<cstdio>
// #define FILEOI
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define dep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&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 qread(){
int x=0;char c;bool f=1;
while(cg<'0'||'9'<c)if(c=='-')f=0;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?x:-x;
}
#undef cg
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;}
template<class T>void fwrit(T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>10)fwrit(x/10);
return (void)(putchar(x%10^48));
}
const int MAXN=1e3;
const int chkDir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
const int scDir[][2]={{0,1},{0,-1},{1,0},{-1,0},{1,-1},{1,1},{-1,1},{-1,-1}};
int w[MAXN+5][MAXN+5],n,tot0,tot1;
bool vis[MAXN+5][MAXN+5];
inline void init(){
qread(n);
rep(i,1,n)rep(j,1,n)qread(w[i][j]);
}
inline bool inside(const int x,const int y){
return 0<x&&x<=n&&0<y&&y<=n;
}
inline bool check(const int x,const int y,const bool f){
//若 f 为 1, 则检测四周不能大于它
//若 f 为 0, 则检测四周不能小于它
int tx,ty;
if(f){
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(inside(tx,ty)&&w[tx][ty]>w[x][y])return false;
}
}
else{
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(inside(tx,ty)&&w[tx][ty]<w[x][y])return false;
}
}
return true;
}
inline bool dfs(const int x,const int y,const bool f){
vis[x][y]=true;
int tx,ty;bool ret=true;
rep(i,0,7){
tx=x+scDir[i][0],ty=y+scDir[i][1];
if(!inside(tx,ty)||w[tx][ty]!=w[x][y]||vis[tx][ty])continue;
ret=ret&check(tx,ty,f);
ret=ret&dfs(tx,ty,f);
}
return ret;
}
inline void algor(){
rep(i,1,n)rep(j,1,n)if(!vis[i][j]){
if(check(i,j,0)&&dfs(i,j,0))++tot0;
if(check(i,j,1)&&dfs(i,j,1))++tot1;
}
}
signed main(){
#ifdef FILEOI
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
#endif
init();
algor();
printf("%d %d\n",tot1,tot0);
return 0;
}
T2 「JOI 2013 Final」 现代豪宅
题目
考场思路（正解）
稍作分析，即可看出这是一个图论题。
将同行同列的点建边连起来，最后特判开始和结束即可，这个题直接看代码，其实还是很清晰的。
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
// #define FILEOI
#define int long long
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define dep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&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 qread(){
int x=0;char c;bool f=1;
while(cg<'0'||'9'<c)if(c=='-')f=0;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?x:-x;
}
#undef cg
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;}
template<class T>void fwrit(T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>10)fwrit(x/10);
return (void)(putchar(x%10^48));
}
const int MAXN=1e5;
const int MAXK=2e5;
int M,N,K,s,t;bool sp,tp;
struct node{
int x,y,id;
node(){}
node(const int X,const int Y,const int I):x(X),y(Y),id(I){}
};
inline bool cmpx(const node tt,const node t){return tt.x<t.x;}
inline bool cmpy(const node tt,const node t){return tt.y<t.y;}
vector<node>n[MAXN+5];
vector<node>m[MAXN+5];
struct edge{
int to,nxt,d,w;
edge(){}
edge(const int T,const int N,const int D,const int W):to(T),nxt(N),d(D),w(W){}
}e[(MAXK<<3)+5];
int tail[MAXK+5],ecnt;
inline void add_edge(const int u,const int v,const int d,const int w){
e[++ecnt]=edge(v,tail[u],d,w);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v],d,w);tail[v]=ecnt;
}
inline void init(){
qread(M,N,K);
int x,y;
for(int i=1;i<=K;++i){qread(x,y);
if(x==1&&y==1)sp=true,s=i;
if(x==M&&y==N)tp=true,t=i;
m[x].push_back(node(x,y,i));
n[y].push_back(node(x,y,i));
}
return;
}
inline void buildGragh(){
for(int i=1;i<=M;++i)if(m[i].size()>1){
sort(m[i].begin(),m[i].end(),cmpy);
for(int j=1,siz=m[i].size();j<siz;++j)
add_edge(m[i][j-1].id,m[i][j].id,m[i][j].y-m[i][j-1].y,1);
}
for(int i=1;i<=N;++i)if(n[i].size()>1){
sort(n[i].begin(),n[i].end(),cmpx);
for(int j=1,siz=n[i].size();j<siz;++j)
add_edge(n[i][j-1].id,n[i][j].id,n[i][j].x-n[i][j-1].x,0);
}
if(!sp){
s=0;
if(!m[1].empty())add_edge(s,m[1][0].id,m[1][0].y-1,1);
}
if(!tp){
t=K+1;
if(!n[N].empty())add_edge(t,n[N][n[N].size()-1].id,M-n[N][n[N].size()-1].x,0);
if(!m[M].empty())add_edge(t,m[M][m[M].size()-1].id,N-m[M][m[M].size()-1].y,1);
}
}
const int INF=(1ll<<50);
int dis[MAXK+5];
struct info{
int u,d,w;
info(){}
info(const int U,const int D,const int W):u(U),d(D),w(W){}
bool operator<(const info a)const{return !(d<a.d);}
};
priority_queue<info>Q;
inline void dijkstra(){
rep(i,0,K+1)dis[i]=INF;
dis[s]=0;
Q.push(info(s,0,1));
while(!Q.empty()){
info now=Q.top();Q.pop();
// printf("Now : %lld %lld %lld\n",now.u,now.d,now.w);
if(now.d>dis[now.u])continue;
for(int i=tail[now.u],v,w;i;i=e[i].nxt){
v=e[i].to;
w=now.d+e[i].d+(now.w!=e[i].w);
if(w<dis[v]){
dis[v]=w;
if(v!=t)Q.push(info(v,w,e[i].w));
}
}
}
}
signed main(){
#ifdef FILEOI
freopen("mansion.in","r",stdin);
freopen("mansion.out","w",stdout);
#endif
init();
buildGragh();
dijkstra();
if(dis[t]==INF)printf("-1\n");
else printf("%lld\n",dis[t]);
return 0;
}
T3 「SCOI2015」小凸玩密室
题目
考场思路
题目读错了，导致我暴力都打不出来...
其实题目要求的是一定要将某一棵子树全部扫完再去扫其他的子树。
而不是左边扫一下，右边扫一下...
正解
首先，这里补充一个数据范围 （考试的时候也有）
对于 \(10\%\) 的数据，\(1≤n≤10\)；
另有 \(10\%\) 的数据， \(1≤n≤20\) ；
另有 \(10\%\) 的数据， \(1≤n≤2000\) ；
另有 \(20\%\) 的数据， \(1≤n≤20000\) ；
对于 \(100\%\) 的数据， \(1≤n≤2\times 10^5\) ， \(1≤A_i≤10^5\) ， \(1≤B_i≤10^5\) 。
再次引用这句话 虽然是我自己编的
所谓信息竞赛，其实就是面向数据编程
其实，根据数据范围，一步一步想出算法并优化其实也是一个解题的好方法。
子方案 1 (10pts)
首先，看前 \(10\%\) 的数据，这个地方我们可以怎么做呢？
这样的暴力其实很简单，用 \(O(n!)\) 枚举我们访问的顺序。
再判断这个顺序是否合法，最后计算花费即可。
子方案 2 (20pts)
但是很明显，对于 \(10pts\) 的算法，是过不了第二个 \(10pts\) 的数据点的。
怎么进行优化？
注意到子方案 \(1\) 中有这样的操作：
随意枚举顺序，再判断是否合法。
这样做让我们用很多时间枚举了很多不合法的访问顺序。
那么我们是否可以让我们枚举的序列本来就合法，只需直接去算花费？
这是肯定可以的，时间复杂度 \(O(2^n)\)，因为我们要分左、右儿子去构造访问顺序。
这样，时间复杂度应该是 \(O(n2^n\cdot nlog^n_2)\)。
子方案 3 (50pts)
对于子方案 \(2\) 的优化显然是很好的，但是这都基于 暴力 这一思想，接下来我们需要转换思路。
考虑我们是怎么点亮一个子树的。
对于一个子树，它的根是 \(u\)，左儿子是 \(lc\)，右儿子是 \(rc\)。
假若我们先访问左子树，先不管它是怎么访问的。
那么，我们在左子树里面的访问顺序是否对后面的状态有影响？
是有的，证明如下： 本人数学不好，没有严格数学书写顺序
假设我们在左子树里面的访问顺序中的某一种是以 \(x\) 结尾。
很显然这个 \(x\) 有很多个。
而当我们从左子树到右子树去的时候，先要访问右子树的树根，即 \(rc\)。
那么这个花费显然是 \(dis(x,rc)*A[rc]\)。
而又因为这个 \(x\) 有很多个，那么很显然。不同的 \(x\) 是会有不同的花费。
因而左子树里面的访问顺序是对后面的状态有影响。
而且很显然，对后面状态有影响的只有最后访问的那个点在哪里。
所以，我们就可以定义状态 \(f[u][x]\) 为访问完以 \(u\) 为根的子树（不包含 \(u\)）且结尾在 \(x\) 时的最小花费。
那么，就可以分类进行状转：
- 当 \(x\) 在左子树上时，\(f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}\)
- 当 \(x\) 在右子树上时，\(f[u][y]=min\{dis(u,rc)\times A[rc]+f[rc][x]+dis(x,lc)\times A[lc]+f[lc][y]\}\)
很显然，状转中 \(x、y\) 都是需要循环枚举的，因而这个状转大概是 \(O(n^2)\) 的复杂度。
所以总复杂度是 \(O(n^3)\)。
但其实这样的计算是不准确的，准确复杂度应该是 \(\sum\frac{n^2}{2^{x+2}}\)。
这个复杂度是通过分层计算得出。
不难看出，这个复杂度可得到 \(50pts\) 的高分。
子方法 4 (正解)
我们发现，对于子方法三，其实已经快要过掉这道题了。
但是哪里的时间复杂度较高呢？
毋庸置疑的，状转的 \(O(n^2)\) 其实已经非常高了。
怎么减下来？肯定是要针对其状转简化。
观察状转：
- 当 \(x\) 在左子树上时，\(f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}\)
- 当 \(x\) 在右子树上时，\(f[u][y]=min\{dis(u,rc)\times A[rc]+f[rc][x]+dis(x,lc)\times A[lc]+f[lc][y]\}\)
我们先考虑其中一个状转，另一个其实是对应的。
拿第一个算式来说
\[f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}
\]
\]
考虑将其分解：
对于 \(dis(x,rc)\) ，其实不难看出
\[dis(x,rx)=dis(x,u)+dis(u,rc)
\]
\]
而这里面，只有 \(dis(x,u)\) 是改变的。
那么我们只需将 \(dis(x,u)\) 也存入状态中，就可以同时考虑它的最小值了。
所以，访问一边的最小花费就是
\[ans2=f[lc][x]+dis(u,rc)\times A[rc]+[dis(u,x)+dis(u,rc)]\times A[rc]
\]
\]
最后的花费，就是 \(ans2+f[lc][x]\) 了。
最后，根据这个 \(x\) 到底在左边还是在右边进行分类转移即可。
但是，这就是最后的答案了吗？
肯定不是，题目并未要求我们必须从 \(1\) 开始。
所以，定义另一个状态 \(t[i][j]\)：访问完 \(i\) 的子树，结尾在 \(j\) 时的最小花费。
那么这个怎么转移呢？
这里可以自行思考了
如果还是想不出来，看看代码吧，看看代码总有好处的
std version
#include<bits/stdc++.h>
#define mz 1000000007
using namespace std;
long long inf=mz*1LL*mz;
long long dep[200005];
int n,a[200005],b[200005];
vector <long long> dp[200005],dis[200005],dpp[200005];
void dfs(int x)
{
dep[x]=dep[x/2]+b[x];//计算伪深度, 方便计算距离
if(x*2<=n)//有左儿子
{
dfs(x*2);//先访问左儿子
int t=dp[x*2].size();//得到左儿子的叶子共有多少个
if(x*2+1<=n)//如果有右儿子
{
dfs(x*2+1);//访问右儿子
long long ans1=inf,ans2=inf,ansp1=inf,ansp2=inf;
//分别是 f, t
for(int i=0;i<dp[x].size();i++)
{
if(i<t)//如果这个点是左子树上的点
{
ans1=min(ans1,dp[x*2][i]+1LL*b[x*2]*a[x*2]+(dis[x][i]+b[x*2+1])*a[x*2+1]);
ansp1=min(ansp1,dpp[x*2][i]+dis[x][i]*a[x]+1LL*b[x*2+1]*a[x*2+1]);
}
else//当这个点是右子树上的点
{
ans2=min(ans2,dp[x*2+1][i-t]+1LL*b[x*2+1]*a[x*2+1]+(dis[x][i]+b[x*2])*a[x*2]);
ansp2=min(ansp2,dpp[x*2+1][i-t]+dis[x][i]*a[x]+1LL*b[x*2]*a[x*2]);
}
}
for(int i=0;i<dp[x].size();i++)
{
if(i<t)//如果它是左儿子
{
dp[x][i]=ans2+dp[x*2][i];
dpp[x][i]=min(dp[x][i],ansp2+dp[x*2][i]);
}
else//是右儿子
{
dp[x][i]=ans1+dp[x*2+1][i-t];
dpp[x][i]=min(dp[x][i],ansp1+dp[x*2+1][i-t]);
}
}
}
else//没有右儿子
{
for(int i=x;i>=1;i=i/2)
{
dp[i].push_back(0);
dpp[i].push_back(0);
dis[i].push_back(dep[x]-dep[i]);
}
dp[x][0]=1LL*b[x*2]*a[x*2];
dpp[x][0]=inf;
dp[x][1]=inf;
dpp[x][1]=1LL*b[x*2]*a[x];
}
}
else//没有后辈
{
for(int i=x;i>=1;i=i/2)
{
dp[i].push_back(0);
dpp[i].push_back(0);
dis[i].push_back(dep[x]-dep[i]);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
scanf("%d",&b[i]);
dfs(1);
long long ans=inf;
for(int i=0;i<dp[1].size();i++)
ans=min(ans,dpp[1][i]);
printf("%lld\n",ans);
return 0;
}
最新文章
- [LeetCode] Closest Binary Search Tree Value 最近的二分搜索树的值
- 前端组件化Polymer入门教程(8)——事件
- 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)
- TOCControl上实现右键
- yield和python（如何生成斐波那契數列）
- bzoj1691[Usaco2007 Dec]挑剔的美食家 平衡树treap
- (转)实例分析：MySQL优化经验
- jquery添加的html元素按钮为什么不执行类样式绑定的click事件
- [转] 使用C#开发ActiveX控件
- POJ 2778 DNA sequence
- 前端程序员：月薪 5K 到 5 万，我干了啥
- 在java中可有两种方式实现多线程，一种是继承Thread类，一种是实现Runnable接口
- SOA一些资料
- Oracle笔试题库之问答题篇-总共60道
- python爆破zip脚本
- HTML5 开发APP(打开相册以及图片上传)
- iOS开发的另类神器：libimobiledevice开源包【类似android adb 方便获取iOS设备信息】
- docker快速搭建几个常用的第三方服务
- 你以为的MongoDB副本集的高可用是真的高可用了吗?
- redis 集群搭建碰到的问题