nbhkdz.com冰点文库

Noip

时间:2015-09-13


第二题:花匠(动态规划)
1.令 S[i][1]表示以 i 为结尾, 且降序到达 a[i]的最长抖动序列长度; 令 S[i][0]表示以 i 为结尾, 且升序到达 a[i]的最长抖动序列长度。依然设数组 S[i][0/1],但考虑如下递推公式:

(1)a[i+1]>a[i]: S[i+1][0]=max(S[i][1]+1,S[i][0]); S[i+1][1]=S[i][1]; (2)a[i+1]<a[i]: S[i+1][0]=S[i][0]; S[i+1][1]=max(S[i][0]+1,S[i][1]); (3)a[i+1]= =a[i]: S[i+1][0]=S[i][0]; S[i+1][1]=S[i][1]; S[1][0]=S[1][1]=1. 算法优化后,再一次编写程序,O(n)的时间复杂度,当然是顺利 AC 了,代码如 下:

2.这道题明显可以用类似最长上升子序列的动态规划求解,易得思路如下: 用 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; }

其实再进一步分析,发现问题可以简化成为求转折点数的问题,又是一个 O(n),对序列缩点,连续递减的点 和连续递增的点是可以缩到一个代表性的点上的,比如说样例给的 5 3 2 1 2,可以缩成 5,1,2 或 3,1,2 或 2,1,2,即 5 3 2 这三个连续递减的点实际上可以由一个点代替,1 是一个转折点,于是你也可以说是找转折点个数。

第三题:华容道 (最短路)
这道题的数据范围是 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;

}


NOIP2017.pdf

NOIP2017 - 全国信息学奥林匹克联赛(NOIP2017 复赛) 普及组 CCF 全国信息学奥林匹克联赛(NOIP2017)复赛 普及组 (请选手务必仔细阅读本页内容) 一、题目概况 ...

NOIP、NOI注意哪些?_图文.pdf

NOIP、NOI注意哪些? - 青少年信息学(计算机)奥林匹克竞赛(早期称为青少

NOIP2016普及组复赛试题讲解(c++版本)_图文.ppt

NOIP2016普及组复赛试题讲解(c++版本)_学科竞赛_初中教育_教育专区。NOIP2016 普及组题解分析总结 C++ 版本 试题分析 NOIP2016 普及组复赛题解 NOIP2016普及组C++ ...

NOIP2017普及组解题报告非官方.doc

NOIP2017普及组解题报告非官方_学科竞赛_初中教育_教育专区。NOIP2017,普及组,解题报告非官方 NOIP2017 普及组解题报告-by 郑佳睿 1. 成绩(score.cpp/c/pas) ...

NOIP复习_图文.ppt

NOIP复习 - NOIP初赛复习 第一部分:复习 标准过程与函数 ? 函数不能

NOIP2016初赛普及组C++试题及参考答案.pdf

NOIP2016初赛普及组C++试题及参考答案 - 第二十二届全国青少年信息学奥

CCF NOIP2016复赛提高组一等奖获奖名单.doc

CCF NOIP2016 复赛提高组一等奖获奖名单 高中阶段获历年 NOIP

NOIP易犯错误集锦.ppt

NOIP易犯错误集锦_学科竞赛_高中教育_教育专区。NOIP低级错误和常识集锦 NOIP容易犯错误汇总 低级错误 1. 2. 3. 4. 5. 6. 7. 未按题目要求添加文件读写 ...

NOIP基础算法综合_图文.ppt

[i]*w[i]; a[sum]=1; //标记 } for(i=1;i<=1000;i++)if(a[i])num++; //统计不同重量的个数 cout<<num<<endl; 例题2:火柴棒等式(NOIP...

NOIP数学基础知识.doc

NOIP数学基础知识_学科竞赛_高中教育_教育专区。基础知识 筛法求素数,惟一分

noip2015普及组解题报告.txt

noip2015普及组解题报告_学科竞赛_高中教育_教育专区。noip2015普及组满分解题报告(C语言版) n oip 2015 普及组题解 1. 金币 (coin.cpp/c/pas) 【问题描述】...

-NOIP2017初赛普及组C++及答案.doc

-NOIP2017初赛普及组C++及答案_学科竞赛_初中教育_教育专区。CCF-NOIP2017-初赛普及组-C++语言试题及参考答案 第二十三届全国青少年信息学奥林匹克联赛初赛普及组 ...

1995-2008 历届NOIP试题及详解.doc

AN-1 N 输出格式:第 18 页 | 共 209 页 NOIP 1996 提

noip2013提高组 day1.pdf

noip2013提高组 day1 - 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 (请选手务...

Noip 2013 提高组 解题报告.pdf

Noip 2013 提高组 解题报告 --By GreenCloudS Day

NOIP2012提高组day1.pdf

全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况中文题目...

NOIP2011 提高组 Day2.pdf

全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day2 全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况中文题目名称...

NOIP2004普及组.pdf

NOIP2004普及组 - 第十届全国青少年信息学奥林匹克联赛初赛试题 ( 普及

noip练习题.doc

noip练习题 - 1.质因数分解 描述 已知正整数 n 是两个不同的质数的乘积

极客晨星帮你做好编程入门规划,进阶NOIP!.doc

极客晨星帮你做好编程入门规划,进阶NOIP! - 极客晨星帮你做好编程入门规划,进阶 NOIP! 先来给大家普及一个概念,什么是 NOIP 算法编程? NOIP 算法编程,即“全国...