2024年3月7日发(作者：)
Noip 2013 Day2
解题报告
--By GreenCloudS
第一题：积木大赛 （模拟）
直接贪心，每次取最大一个连续区间，然后模拟即可。
令h[0]=0,答案就是：∑h[i]-h[i-1](0
复杂度:O(n)
代码1(Cpp)：
#include
#define MAXN 100010
int h[MAXN],ans=0,n;
int main() {
h[0]=0;
scanf("%d",&n);
for (int i=0;i++ scanf("%d",&h[i]); if (h[i]>h[i-1]) ans+=h[i]-h[i-1]; } printf("%dn",ans); return 0; } 代码2（先对高度进行基数排序，然后逐行计算区间数，复杂度也是O(n)）(Cpp): #include #include using namespace std; #define MAXH 10010 #define MAXN 100010 struct node { } *head[MAXH]; int maxh=0; void Insert(int h,int t) { } int n,h,delta=1,ans=0; bool f[MAXN]; int main() { memset(f,true,sizeof(f)),memset(head,0,sizeof(head)); cin>>n; f[0]=f[n+1]=false; for (int i=0;i++ for (int i=0;i<=maxh;i++) { if (i) ans+=delta; maxh=max(maxh,h); node *p=new(node); p->t=t,p->next=head[h]; head[h]=p; node *next; int t; node () { } next=NULL; } } for (node *p=head[i];p;p=p->next) { } if (f[p->t-1]&&f[p->t+1]) delta++; if ((!f[p->t-1])&&(!f[p->t+1])) delta--; f[p->t]=false; cout< return 0; 第二题:花匠（动态规划） 这道题明显可以用类似最长上升子序列的动态规划求解，易得思路如下： 用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 f(i,1)=max{f(j,0)}+1 0<=j 边界：f(0,0)=f(0,1)=0 如果直接DP毫无疑问复杂度是O(n^2)，会TLE，但是，考虑到我们每次取最值时候取得都是一个区间里的数，如f(i,0)=max{f(j,1)}+1 0<=j 得就是区间[0,h[i]-1]里的最值，所以可以使用线段树或者是BIT（树状数组）来优化，这样复杂度就是O(n log n)，可以过全部数据。 这道题还有一个解法，直接求拐点数目，然后就可以神奇的做到O(n)了，由于我找不到满意的证明，就不发上来了。 代码(DP+BIT)(Cpp): #include #include #include 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++ 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++ 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("%dn",ans); return 0; } 第三题：华容道 （最短路） 这道题的数据范围是n<=30，所以，我们可以看到，裸的O(n^4)的BFS对于求解q较小的情况是无压力的，但是在q大的情况下，毫无疑问会TLE，明显，在q较大的情况下，我们需要将每次BFS中重复搜索的冗余信息除去，所以我们可以先分析题 目性质： （这里称要移动的棋子为目标棋子） 首先，如果要移动目标棋子，那么我们首先必须要将空格移到该棋子的上下左右四个方向上相邻位置之一，然后才可以移动该棋子。 然后，我们分析该棋子移动时候的性质： 棋子每次可以移动，仅当空格位于其相邻位置的时候，每次移动完棋子，空格总会在棋子相邻的位置，那么我们发现，对于棋子在某一位置，然后空格又在其四个方向上某一相邻位置时，棋子要想某一方向移动一个时的花费的步数是一定的，那么，就可以先进行一次预处理，预处理出对于目标棋子在上述条件下每次移动所需的步数。 然后，预处理完成之后，我们会发现每次查询都会变成一个求最短路的问题，用Dijstra或SPFA的话，可以在时限范围内解决。 实现： 定义一个数组Step[x][y][k][h]，表示目标棋子在位置（x，y）且空格在目标棋子的k方向上的相邻格子时，目标棋子往h方向移动1格所需的步数，然后用状态[x][y][k]作为节点建图，用各个状态的关系连边，每次询问时重新定义一个源点跟终点，跑最短路就可以得出答案。(预处理时跑n^2次O(n^2)的BFS就可以了) 复杂度（Dijstra）：（n^4+n^2 log n） 复杂度（SPFA）：（n^4+n^2） 代码（SPFA）（Cpp）： #include #include #include #include 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 { } *head[MAXV]; void AddEdge(int s,int t,int d) { } int Map[MAXN][MAXN],n,m,q,ex,ey,sx,sy,tx,ty; int v[MAXN][MAXN][4],V=0; int dist[MAXN][MAXN],Move[MAXN][MAXN][4][4]; int Dist[MAXV]; edge *p=new(edge); p->t=t,p->d=d; p->next=head[s]; head[s]=p; edge *next; int t,d; edge () { } next=NULL; bool f[MAXV]; int S,T; struct node { }; queue int Bfs(int Sx,int Sy,int Tx,int Ty) { if (Sx==Tx&&Sy==Ty) return 0; while (!()) (); for (int i=0;i++ } dist[Sx][Sy]=0; (node(Sx,Sy)); while (!()) { node u=(); (); for (int i=0;i<4;i++) { if (Map[u.x+dir[i][0]][u.y+dir[i][1]]&&dist[u.x+dir[i]for (int j=0;j++ } dist[i][j]=inf; int x,y; node (int _x,int _y):x(_x),y(_y) { } [0]][u.y+dir[i][1]]==inf) { y]+1; dist[u.x+dir[i][0]][u.y+dir[i][1]]=dist[u.x][u. if (u.x+dir[i][0]==Tx&&u.y+dir[i][1]==Ty) return dist[u.x][u.y]+1; } struct Cmp { }; priority_queue int spfa() { for (int i=0;i++ memset(f,true,sizeof(f)); while (!()) (); Dist[S]=0; (S); while (!()) { int u=(); (); 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) { bool operator()(int x,int y) { } return Dist[x]>Dist[y]; } return inf; } } (node(u.x+dir[i][0],u.y+dir[i][1])); } int main() { Dist[p->t]=Dist[u]+p->d; f[p->t]=true; (p->t); } } } return Dist[T] cin>>n>>m>>q; memset(Map,0,sizeof(Map)); for (int i=0;i++ for (int j=0;j++ cin>>Map[i][j]; for (int k=0;k<4;k++) { v[i][j][k]=++V; } } } for (int i=0;i++ for (int j=0;j++ 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++ ir[h][1]]) { for (int j=0;j++ 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+d Move[i][j][k][h]=Bfs(i+dir[k][0],j+dir[k][1],i+dir[h][0],j+dir[h][1])+1; } memset(head,0,sizeof(head)); for (int i=0;i++ for (int j=0;j++ for (int k=0;k<4;k++) { for (int h=0;h<4;h++) { if (Move[i][j][k][h] AddEdge(v[i][j][k],v[i+dir[h][0]] } } } Map[i][j]=1; } } } [j+dir[h][1]][h^1],Move[i][j][k][h]); } } } } } while (q--) { } return 0; cin>>ex>>ey>>sx>>sy>>tx>>ty; if (sx==tx&&sy==ty) { } S=++V; T=++V; if (Map[sx][sy]==0||Map[tx][ty]==0) { } Map[sx][sy]=0; for (int i=0;i<4;i++) { } Map[sx][sy]=1; for (int i=0;i<4;i++) { } cout< if (Map[tx+dir[i][0]][ty+dir[i][1]]) { } AddEdge(v[tx][ty][i],T,0); 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 } AddEdge(S,v[sx][sy][i],D); cout<<-1< continue; cout<<0< continue; }
发布评论