本文最后更新于:2020年4月20日 凌晨
最近突然想回顾一下历年noip题目,就开个新坑吧,题解就从略了
题目链接 https://vijos.org/p/category/2013
D1T1 转圈游戏
公式就,现在一眼的事情当时想了很久orz
#include<bits/stdc++.h>
using namespace std;
int power(int x,int n,int mod)
{
int ans=1;
while(n)
{
if(n&1) ans=1LL*ans*x%mod;
x=1LL*x*x%mod;
n>>=1;
}
return ans;
}
int main()
{
int n,m,k,x;
while(scanf("%d%d%d%d",&n,&m,&k,&x)!=EOF)
{
int ans=(x+1LL*m*power(10,k,n))%n;
printf("%d\n",ans);
}
}
D1T2 火柴排队
首先肯定是小对小,大对大,才能使那个式子最小,这一点可以交换一下然后做差说明。并且题目保证了高度互不相同,也就是给了两个排列,问最少交换相邻元素多少次,才能使两个排列一样,再转化一步,假设第一个排列就是1,2,3,…n,问第二个排列最少交换相邻元素几次才能变成1,2,3,…n,这就是逆序对的定义了。
不知道如果不保证高度互不相同该怎么做orz
当时这个题爆零了,一点也不会QAQ
#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
#define N 100010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int a[N],b[N],h[N];
int c[N];
int n;
int lowbit(int x)
{
return x&(-x);
}
int ask(int x)
{
int ans=0;
for(;x<=n;x+=lowbit(x))
ans+=c[x];
return ans;
}
void change(int x,int y)
{
for(;x;x-=lowbit(x))
c[x]+=y;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
rep(i,1,n) scanf("%d",a+i),h[i]=a[i];
sort(h+1,h+n+1);
rep(i,1,n) a[i]=lower_bound(h+1,h+n+1,a[i])-h;
rep(i,1,n) scanf("%d",b+i),h[i]=b[i];
sort(h+1,h+n+1);
rep(i,1,n) b[i]=lower_bound(h+1,h+n+1,b[i])-h;
rep(i,1,n) h[a[i]]=i;
rep(i,1,n) b[i]=h[b[i]],c[i]=0;
int ans=0;
rep(i,1,n)
{
change(b[i],1);
ans+=ask(b[i]+1);
if(ans>=mod) ans-=mod;
}
printf("%d\n",ans);
}
}
D1T3 货车运输
这个不难看出是最大生成树上倍增求路径边权最小值。要注意的是可能是一个森林,当时蠢的用tarjan判连通性了,强行增加码量。还好在赛前刚给别人讲过倍增,这题满分了。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dow(i,l,r) for(int i=l;i>=r;--i)
#define N 10010
#define M 50010
const int INF=0x3f3f3f3f;
struct edge
{
int x,y,c;
} t[M];
int n,m,q;
int fa[N];
bool root[N];
bool cmp(const edge &a,const edge &b)
{
return a.c>b.c;
}
int getfa(int x)
{
return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
bool Union(int x,int y)
{
x=getfa(x);
y=getfa(y);
if(x==y) return false;
fa[x]=y;
return true;
}
namespace TREE
{
int e,head[M<<1],last[M<<1],w[M<<1],p[N];
int f[N][21],g[N][21];
int deep[N];
void add(int x,int y,int c)
{
head[++e]=y;w[e]=c;
last[e]=p[x];
p[x]=e;
}
void dfs(int x,int pre,int dep)
{
deep[x]=dep;
for(int j=p[x];j;j=last[j])
{
int y=head[j];
if(y==pre) continue;
f[y][0]=x;
g[y][0]=w[j];
rep(i,1,20)
{
f[y][i]=f[f[y][i-1]][i-1];
g[y][i]=min(g[y][i-1],g[f[y][i-1]][i-1]);
}
dfs(y,x,dep+1);
}
}
int askmax(int x,int y)
{
if(deep[x]>deep[y]) swap(x,y);
int ans=INF;
dow(i,20,0)
if(deep[f[y][i]]>=deep[x])
ans=min(ans,g[y][i]),y=f[y][i];
if(x==y) return ans;
dow(i,20,0)
if(f[x][i]!=f[y][i])
{
ans=min({ans,g[x][i],g[y][i]});
x=f[x][i],y=f[y][i];
}
ans=min({ans,g[x][0],g[y][0]});
return ans;
}
}//TREE
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,m)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
t[i]=edge{x,y,c};
}
sort(t+1,t+m+1,cmp);
rep(i,1,n) fa[i]=i;
rep(i,1,m)
{
int x=t[i].x;
int y=t[i].y;
int c=t[i].c;
if(Union(x,y))
{
TREE::add(x,y,c);
TREE::add(y,x,c);
}
}
rep(i,1,n) root[getfa(i)]=true;
memset(TREE::g,INF,sizeof(TREE::g));
rep(i,1,n)
if(root[i])
TREE::dfs(i,0,1);
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
if(getfa(x)!=getfa(y)) puts("-1");
else printf("%d\n",TREE::askmax(x,y));
}
}
D2T1 积木大赛
可能太简单,这题没什么印象了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int h[N];
int main()
{
scanf("%d",&n);
int ans=0;
rep(i,1,n)
{
scanf("%d",h+i);
ans+=max(0,h[i]-h[i-1]);
}
printf("%d\n",ans);
}
D2T2 花匠
当时从最长上升子序列的思路出发,然后推了推,写了个单调队列,具体怎么写的忘了,不过也是AC。实际上最简单的做法只需要扫一遍,求出拐点的个数,加2就是答案了。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int a[N];
int main()
{
scanf("%d",&n);
int ans=0;
int now=0;
rep(i,1,n)
{
scanf("%d",a+i);
if(i==1||a[i-1]==a[i]) continue;
if(a[i-1]<a[i])
{
if(now==-1) ++ans;
now=1;
}
if(a[i-1]>a[i])
{
if(now==1) ++ans;
now=-1;
}
}
printf("%d\n",ans+2);
}
D2T3 华容道
这题xjb搜,就得了5分…
正确做法是bfs预处理,拆点,建图跑最短路。
具体来说:可以观察到只有空白块位于指定块的四方向上,指定块才可以移动。本质上还有另外一种移动方式,就是指定块不动,空白块从它的上/下左/右中的一个移动到另一个。那么这样就可以bfs预处理了,状态也有了,(x,y,k)表示指定块在(x,y),空白块在相邻的k方向上。spfa求最短路即可。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int INF=0x3f3f3f3f;
const int dx[]= {0,0,1,-1};
const int dy[]= {1,-1,0,0};
const int N=31*31*4;
const int M=4*N;
struct node
{
int x,y;
} q[32*32*4];
int n,m,k;
int dis[32][32];
int can[32][32];
int e,head[M],last[M],w[M],p[N];
bool vis[N];
int dist[N];
bool ok(int x,int y)
{
return x>=0 && x<n && y>=0 && y<m && can[x][y];
}
void bfs(int sx,int sy)
{
memset(dis,INF,sizeof(dis));
dis[sx][sy]=0;
int l=0,r=0;
q[r++]=node{sx,sy};
while(l!=r)
{
int x=q[l].x;
int y=q[l].y;
l++;
rep(i,0,3)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(ok(xx,yy) && dis[xx][yy]==INF)
{
dis[xx][yy]=dis[x][y]+1;
q[r++]=node{xx,yy};
}
}
}
}
int calc(int x,int y,int k)
{
return x*m*4+y*4+k;
}
void add(int x,int y,int c)
{
head[++e]=y;
w[e]=c;
last[e]=p[x];
p[x]=e;
}
void init()
{
rep(i,0,n-1)
rep(j,0,m-1)
if(ok(i,j))
{
rep(k,0,3)
{
int x=i+dx[k];
int y=j+dy[k];
if(!ok(x,y)) continue;
can[i][j]=0;
bfs(x,y);
can[i][j]=1;
rep(h,0,3) if(h!=k)
{
int xx=i+dx[h];
int yy=j+dy[h];
if(ok(xx,yy) && dis[xx][yy]!=INF)
add(calc(i,j,k),calc(i,j,h),dis[xx][yy]);
}
add(calc(i,j,k),calc(x,y,k^1),1);
}
}
}
void spfa(int sx,int sy)
{
queue<int> q;
memset(vis,0,sizeof(vis));
memset(dist,INF,sizeof(dist));
rep(i,0,3)
if(ok(sx+dx[i],sy+dy[i]) && dis[sx+dx[i]][sy+dy[i]]!=INF)
{
int now=calc(sx,sy,i);
dist[now]=dis[sx+dx[i]][sy+dy[i]];
vis[now]=true;
q.push(now);
}
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=false;
for(int j=p[x]; j; j=last[j])
{
int y=head[j];
if(dist[y]>dist[x]+w[j])
{
dist[y]=dist[x]+w[j];
if(!vis[y])
{
vis[y]=true;
q.push(y);
}
}
}
}
}
int work(int x,int y,int sx,int sy,int tx,int ty)
{
if(sx==tx && sy==ty) return 0;
can[sx][sy]=0;
bfs(x,y);
can[sx][sy]=1;
spfa(sx,sy);
int ans=INF;
rep(i,0,3) ans=min(ans,dist[calc(tx,ty,i)]);
if(ans==INF) ans=-1;
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
rep(i,0,n-1)
rep(j,0,m-1)
scanf("%d",&can[i][j]);
init();
while(k--)
{
int x,y,sx,sy,tx,ty;
scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);
--x;--y;--sx;--sy;--tx;--ty;
printf("%d\n",work(x,y,sx,sy,tx,ty));
}
}
/*
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
*/
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!