Noip 2013 day 2 被虐报告(+解题报告)
2018-10-03 本文已影响2人
AmadeusChan
今年的的Noip确实有些坑，Day2没有数论，而且还比day1容易。。。。。。
第一题：
直接模拟，如果h[i]>h[i-1],ans+=h[i]-h[i-1]，我白痴的写了离散化+模拟，硬是把复杂度从O(n)搞到了O(n log n)。。。
第二题：
动态规划+BIT优化：
用f(i,0)表示以i为结尾的且最后一段上升的子序列最大长度，f(i,1)表示表示以i为结尾的且最后一段下降的子序列最大长度，那么答案明显就是max{f(i,0),f(i,1)}
方程：
f(i,0)=max{f(j,1)}+1 0<=j<i且h[j]<h[i]
f(i,1)=max{f(j,0)}+1 0<=j<i且h[j]>h[i]
边界：f(0,0)=f(0,1)=0
这个方程直接DP复杂度是O(N^2)，但是，可以用两个BIT来维护max(f(j,0)),max(f(j,1)),这样复杂度就降到了O（n log n）,可以无压力过。
好像有大神说这道题的f(i)可以直接用f(i-1)推到，所以复杂度仅为O(n),求指点。
第三题：
这道题没什么把握，我写的是裸的q次BFS，后来觉得用双向BFS省去一半的搜索量应该可以过吧。。。。大概。。。。。
突然语文课上想到解法了，发一下：
首先，进行O(n^4)的预处理，预处理出要移动的棋子在某一位置，空格在其上下左右四个方向上，然后棋子上下左右移动一个的代价，然后每次查询跑最短路即可。
用Dijstra的话，复杂度:O(n^4+q n^2 log n)
总而言之，今年还是被NOIP坑的够呛，只能勉强求求不下一等了。。。。555
代码（都在SMART OJ的非官方数据上过了，应该没啥问题）（详细请见最下方附带的题解文件）：
T1:
#include <cstdio>
#define MAXN 100010
int h[MAXN],ans=0,n;
int main() {
h[0]=0;
scanf("%d",&n);
for (int i=0;i++<n;) {
scanf("%d",&h[i]);
if (h[i]>h[i-1]) ans+=h[i]-h[i-1];
}
printf("%d\n",ans);
return 0;
}
T2:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define lowbit(x)(((~(x))+1)&x)
#define MAXH 1000010
#define For(i,x) for (int i=x;i;i-=lowbit(i))
#define rep(i,x) for (int i=x;i<=maxh;i+=lowbit(i))
int t0[MAXH],t1[MAXH];
int h[MAXN],n,maxh=0;
int f[MAXN][2],ans=0;
void Add0(int x,int y) {
rep(i,x) t0[i]=max(t0[i],y);
}
void Add1(int x,int y) {
rep(i,x) t1[i]=max(t1[i],y);
}
int Max0(int x) {
int rec=0;
For(i,x) rec=max(rec,t0[i]);
return rec;
}
int Max1(int x) {
int rec=0;
For(i,x) rec=max(rec,t1[i]);
return rec;
}
int main() {
scanf("%d",&n);
for (int i=0;i++<n;) {
scanf("%d",&h[i]);
maxh=max(maxh,++h[i]);
f[i][0]=f[i][1]=1;
}
maxh++;
memset(t0,0,sizeof(t0)),memset(t1,0,sizeof(t1));
for (int i=0;i++<n;) {
f[i][0]=max(Max0(h[i]-1)+1,f[i][0]);
f[i][1]=max(Max1(maxh-h[i]-1)+1,f[i][1]);
Add0(h[i],f[i][1]),Add1(maxh-h[i],f[i][0]);
ans=max(ans,max(f[i][0],f[i][1]));
}
printf("%d\n",ans);
return 0;
}
T3(最短路):
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 32
#define MAXV 50010
#define inf (1<<26)
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct edge{
edge *next;
int t,d;
edge (){
next=NULL;
}
}*head[MAXV];
void AddEdge(int s,int t,int d){
edge *p=new(edge);
p->t=t,p->d=d;
p->next=head[s];
head[s]=p;
}
int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty,v[MAXN][MAXN][4],V=0,dist[MAXN][MAXN],Move[MAXN][MAXN][4][4],Dist[MAXV];
bool f[MAXV];
int S,T;
struct node{
int x,y;
node (int _x,int _y):x(_x),y(_y){}
};
queue<node>Q;
int Bfs(int Sx,int Sy,int Tx,int Ty){
if(Sx==Tx&&Sy==Ty)return 0;
while(!Q.empty()) Q.pop();
for(int i=0;i++<n;) for(int j=0;j++<m;)dist[i][j]=inf;
dist[Sx][Sy]=0;
Q.push(node(Sx,Sy));
while(!Q.empty()){
node u=Q.front();
Q.pop();
for(int i=0;i<4;i++){
if(Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i][0]][u.y+dir[i][1]]==inf){
dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u.y]+1;
if(u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty)return dist[u.x][u.y]+1;
Q.push(node(u.x+dir[i][0],u.y+dir[i][1]));
}
}
}
return inf;
}
struct Cmp{
bool operator()(int x,int y){
return Dist[x]>Dist[y];
}
};
priority_queue<int,vector<int>,Cmp>Pq;
int spfa(){
for(int i=0;i++<V;)Dist[i]=inf;
memset(f,true,sizeof(f));
while(!Pq.empty()) Pq.pop();
Dist[S]=0;
Pq.push(S);
while(!Pq.empty()){
int u=Pq.top();
Pq.pop();
if(!f[u])continue;
f[u]=false;
if(u==T)return Dist[T];
for(edge *p=head[u];p;p=p->next){
if(Dist[p->t]>Dist[u]+p->d){
Dist[p->t]=Dist[u]+p->d;
f[p->t]=true;
Pq.push(p->t);
}
}
}
return Dist[T]<inf?Dist[T]:-1;
}
int main(){
cin>>n>>m>>q;
memset(Map,0,sizeof(Map));
for(int i=0;i++<n;){
for(int j=0;j++<m;){
cin>>Map[i][j];
for(int k=0;k<4;k++){
v[i][j][k]=++V;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
for(int k=0;k<4;k++){
for(int h=0;h<4;h++)Move[i][j][k][h]=inf;
}
}
}
for(int i=0;i++<n;){
for(int j=0;j++<m;){
if(Map[i][j]){
Map[i][j]=0;
for(int k=0;k<4;k++){
if(Map[i+dir[k][0]][j+dir[k][1]]){
for(int h=0;h<4;h++){
if(Map[i+dir[h][0]][j+dir[h][1]]){
Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1;
}
}
}
}
Map[i][j]=1;
}
}
}
memset(head,0,sizeof(head));
for(int i=0;i++<n;) for(int j=0;j++<m;) for(int k=0;k<4;k++)for(int h=0;h<4;h++)
if(Move[i][j][k][h]<inf)AddEdge(v[i][j][k],v[i+dir[h][0]][j+dir[h][1]][h^1],Move[i][j][k][h]);
while(q--){
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){ cout<<0<<endl;continue;}
S=++V; T=++V;
if(Map[sx][sy]==0||Map[tx][ty]==0){cout<<-1<<endl; continue; }
Map[sx][sy]=0;
for(int i=0;i<4;i++){
if(Map[sx+dir[i][0]][sy+dir[i][1]]){
int D=Bfs(ex,ey,sx+dir[i][0],sy+dir[i][1]);
if(D<inf)AddEdge(S,v[sx][sy][i],D);
}
}
Map[sx][sy]=1;
for(int i=0;i<4;i++) if(Map[tx+dir[i][0]][ty+dir[i][1]])AddEdge(v[tx][ty][i],T,0);
cout<<spfa()<<endl;
}
return 0;
}
附：将Noip的思路整理了一下，顺便将题解和代码一起发了上来
（度娘盘网址：http://pan.baidu.com/s/1osWXY）
