当前位置:首页 >> 学科竞赛 >>

Noip 2013 提高组 Day2 解题报告


Noip 2013 Day2 解题报告
--By GreenCloudS

第一题:积木大赛 (模拟)
直接贪心,每次取最大一个连续区间,然后模拟即可。 令 h[0]=0,答案就是:∑h[i]-h[i-1](0<i<=n,h[i]>h[i-1]) 复杂度:O(n)

代码 1(Cpp):
#

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; }

代码 2 (先对高度进行基数排序, 然后逐行计算区间数, 复杂度也是 O(n)) (Cpp):
#include <iostream> #include <cstring>

using namespace std;

#define MAXH 10010 #define MAXN 100010

struct node { node *next; int t; node () { next=NULL; } } *head[MAXH];

int maxh=0;

void Insert(int h,int t) { maxh=max(maxh,h); node *p=new(node); p->t=t,p->next=head[h]; head[h]=p; }

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++<n;) cin>>h,Insert(h,i); for (int i=0;i<=maxh;i++) { if (i) ans+=delta;

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<<ans<<endl; 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<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),会 TLE,但是,考虑到我们每次取最值 时候取得都是一个区间里的数,如 f(i,0)=max{f(j,1)}+1 0<=j<i 且 h[j]<h[i]取

得就是区间[0,h[i]-1]里的最值,所以可以使用线段树或者是 BIT(树状数组)来优 化,这样复杂度就是 O(n log n),可以过全部数据。 这道题还有一个解法,直接求拐点数目,然后就可以神奇的做到 O(n)了,由于我找 不到满意的证明,就不发上来了。

代码(DP+BIT)(Cpp):
#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; }

第三题:华容道 (最短路)
这道题的数据范围是 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 <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; int v[MAXN][MAXN][4],V=0; int dist[MAXN][MAXN],Move[MAXN][MAXN][4][4];

int 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) retur n 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+d ir[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;

}


相关文章:
NOIP2011提高组解题报告day2
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 ...1/2 相关文档推荐 Noip 2013 提高组 Day2 ... 14页 免费 noip2011 解题...
NOIP2013提高组复赛试题
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...
学军中学NOIP2013提高组原创模拟题day2
学军中学NOIP2013提高组原创模拟题day2_IT/计算机_专业资料。学军中学noip模拟题 学军中学 NOIP2013 提高组原创模拟题 day2 测试时间:3.5 小时 中文题目名称 ...
Bf-bcpyoNOIP2009提高组解题报告
NOIP2013提高组解题报告 8页 免费 NOIP2010提高组解题报告1 2页 免费喜欢此文档的还喜欢 最优贸易(trade)_图论_改进... 5页 1财富值 NOIP2009提高组解题报告...
Noip 2013 解题报告与参赛总结(PASCAL版)
Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013...Noip 2013 Day1 解题报告... 8页 免费 Noip 2013 提高组 Day2 ... 14页...
NOIP2015提高组解题报告
NOIP2015复赛提高组day2 6页 1下载券 NOIP2010提高组解题报告 6页 免费 noip 2012 提高组 解题报... 19页 免费 Noip 2013 提高组 解题报... 21页 免...
NOIP2011DAY2解题报告
NOIP2011DAY2解题报告_初三英语_英语_初中教育_教育专区。NOIP2011提高组复赛DAY2解题报告 NOIP2011DAY2 解题报告 ——by 北京一零一中学 张子威(c++) 今天的题...
noip 2012 提高组 解题报告
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育...2. 3. 4. program day13; label 1; type ...文档贡献者 西莲公主 贡献于2013-07-20 相关文档...
NOIP2013初赛提高组Pascal试题及答案
NOIP2013初赛提高组Pascal试题及答案_学科竞赛_高中教育_教育专区。NOIP2013初赛提高...? 试题纸共有 12 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,...
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告...[i-1]mod 10000); i:=i-2; end; while i>...NOIP2013提高组解题报告 8页 免费 第十九届全国青少年...
更多相关标签:
noip2016解题报告 | noip解题报告 | noip2015解题报告 | noip2016day2 | noip2011 day2 | noip2012day2 | noip2015 day2 | noip2014 day2t1 |