nbhkdz.com冰点文库

Noip 2013 提高组 解题报告


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

Day 1:

第一题:转圈游戏(快速幂)
根据题目, 答案明显是(x+10^km) mod n, 化简一下, 就成了(x + m (10^k mod n) mod n) mod n,所以, 只需要求出 10^k mod n 即可, 可以使用快速

幂来求解,复杂度 O(log k)。 (另一个算法, f(i)=10^i mod n,则 f(i)=f(i-1)*10 mod n,然后求出 f(i)的循环节, 设 复杂度 O(n)) 代码(C++):
#include <cstdio> #include <cstring> int k; long long ans; int n,m,x; long long Exp(int y){ if(!y)return 1; if(y==1)return 10%n; if(y&1){ return(((Exp(y>>1)*Exp(y>>1))%n)*10)%n; }else return(Exp(y>>1)*Exp(y>>1))%n; } int main(){ scanf("%d%d%d%d",&n,&m,&k,&x); ans=Exp(k); ans*=m; ans%=n; ans+=x; ans%=n; printf("%lld",ans);

return 0; }

第二题:火柴排队(贪心+逆序对)
对距离公式化简得: ∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi 要求∑(ai-bi)^2 最小,就只 需要∑aibi 最大即可。这里有个贪心,当 a1<a2<…<an,b1<b2<..<bn 时,∑aibi 最 大。证明如下: 若存在 a>b,c>d,且 ac+bd<ad+bc,则 a(c-d)<b(c-d),则 a<b,与 a>b 矛盾,所以若 a>b,c>d,则 ac+bd>ad+bc 将此式子进行推广: 当 a1<a2<a3<...<an ,b1<b2<...<bn 的情况下∑aibi 最大,即∑(ai-bi)^2 最小。

然后,将两个序列分别排序,确定每对数的对应关系,明显,同时移动两个序列 中的数等效于只移动一个序列中的数,那么,我们就保持一个序列不动,然后根 据另外那个序列中的数对应的数的位置,重新定义一个数组,求逆序对个数,就 是答案。 例如: 对于数据: 4 2314

3214 先排序: 1234 1234 保持序列 1 不动,那么序列 2 中的 3 就对应序列 1 中的 2 位置,2 就对应序列 1 中的 1 位置,1 就对应序列 1 中的 3 位置,4 就对应序列 1 中的 4 位置,那么重定 义数组为: 2134 这个序列的逆序对为(2,1),所以答案是 1。

求逆序对方法: 1. 2. 归并排序 把数组扫一遍,顺序把每个数加入 BIT 或者是线段树等数据结构中, 同 时查询比这个数大的数有几个,加入答案。 复杂度 : O(n log n)

代码(C++) (树状数组) :
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define MAXN 100010 #define lowbit(x)(((~(x))+1)&x) #define MAX 99999997

struct saver{ int v,t; }; saver a[MAXN],b[MAXN]; bool cmp(saver x,saver y){ return x.v<y.v; } int n,r[MAXN],ans=0; int t[MAXN]; void Add(int x){for(int i=x;i<=n;i+=lowbit(i)) t[i]++;} int Sum(int x){ int rec=0; for(;x;x-=lowbit(x)) rec+=t[x]; return rec; } int main(){ scanf("%d",&n); for(int i=0;i++<n;) scanf("%d",&a[i].v),a[i].t=i; for(int i=0;i++<n;) scanf("%d",&b[i].v),b[i].t=i; sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp); for(int i=0;i++<n;) r[a[i].t]=b[i].t; for(int i=n;i;i--) ans+=Sum(r[i]),Add(r[i]),ans%=MAX; printf("%d\n",ans); return 0; }

第三题:货车运输(贪心+最大生成树+树上路径倍增)

首先,我们可以确定贪心的正确性,我们先把边按权值从大到小排序,然后依次 加入图中,如果该边的起末点不在同一连通块中,那么就把边加入,否则不加处

理,很明显,这样生成的图,两点之间要么没有路径,要么唯一一条路径中权值 的最小值最大。所以,我们只要先跑一次最大生成树,然后在求点对之间的树上 路径最小值就可以了。

复杂度:O(m log m + q log n)

代码(C++) (MST+树上倍增) :
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define MAXN 10010 #define MAXM 50010 #define MAXQ 30010 #define MAXD 20 #define clear(x) memset(x,0,sizeof(x)) #define AddEdge(s,t,d) Add(s,t,d),Add(t,s,d) #define inf 0x7fffffff struct saver { int s,t,d; } e[MAXM]; bool cmp(saver x,saver y) { return x.d>y.d; } int father[MAXN],n,m,q,Q[MAXQ][2]; int Find(int x) { int i,j=x; for (i=x;father[i];i=father[i]) ; while (father[j]) { int k=father[j]; father[j]=i;

j=k; } return i; } int up[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN]; bool f[MAXN]; struct edge { edge *next; int t,d; edge () { next=NULL; } } *head[MAXN]; void Add(int s,int t,int d) { edge *p=new(edge); p->t=t,p->d=d,p->next=head[s]; head[s]=p; } void BuildTree(int v) { f[v]=false; for (edge *p=head[v];p;p=p->next) if (f[p->t]) { up[p->t][0]=v,Min[p->t][0]=p->d,h[p->t]=h[v]+1; BuildTree(p->t); } } int Move(int &v,int H) { int rec=inf; for (int i=MAXD-1;i>=0;i--) { if (h[up[v][i]]>=H) { rec=min(rec,Min[v][i]); v=up[v][i]; } } return rec; } int Query(int u,int v) { if (Find(u)!=Find(v)) return -1; int rec=inf;

if (h[u]!=h[v]) rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]); // printf("%d\n",rec); if (u==v) return rec; for (int i=MAXD-1;i>=0;i--) { if (up[u][i]!=up[v][i]) { rec=min(rec,min(Min[u][i],Min[v][i])); u=up[u][i],v=up[v][i]; } } rec=min(rec,min(Min[u][0],Min[v][0])); return rec; } int main() { clear(father),clear(head),clear(up); scanf("%d%d",&n,&m); for (int i=0;i<m;i++) scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].d); sort(e,e+m,cmp); for (int i=0;i<m;i++) if (Find(e[i].s)!=Find(e[i].t)) { father[Find(e[i].s)]=Find(e[i].t); AddEdge(e[i].s,e[i].t,e[i].d); } memset(f,true,sizeof(f)); for (int i=0;i++<n;) if (f[i]) h[i]=0,BuildTree(i),Min[i][0]=inf,up[i][0]=i; for (int i=0;i++<MAXD-1;) { for (int j=0;j++<n;) { up[j][i]=up[up[j][i-1]][i-1]; Min[j][i]=min(Min[j][i-1],Min[up[j][i-1]][i-1]); } } scanf("%d",&q); while (q--) { int u,v; scanf("%d%d",&u,&v); printf("%d\n",Query(u,v)); } return 0; }

Day 2:
第一题:积木大赛 (模拟)
直接贪心,每次取最大一个连续区间,然后模拟即可。 令 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+q n^2 log n) : 复杂度(SPFA)(n^4+q 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) re turn 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; }

若需下载代码文件请戳: http://pan.baidu.com/s/17pOA5


noip 2012 提高组 解题报告

noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 ...文档贡献者 西莲公主 贡献于2013-07-20 相关文档推荐 暂无相关推荐文档 ...

NOIP2013解题报告

NOIP2013解题报告_计算机软件及应用_IT/计算机_专业资料。NOIP2013解题报告 第一...NOIP2013提高组解题报告 8页 免费 Noip 2013 解题报告与参... 18页 免费 Noip...

NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...Noip 2013 提高组 解题报... 21页 免费 喜欢此文档的还喜欢 NOIP2015提高组...

NOIP2013提高组复赛试题

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...

Noip 2013 Day1 解题报告

Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据...noip2013解题报告 11页 免费 Noip 2003 提高组 解题报... 12页 免费喜欢...

Noip 2013 解题报告与参赛总结(PASCAL版)

Noip 2013 解题报告与参赛总结(PASCAL版)_学科竞赛_高中教育_教育专区。noip2013...NOIP2013第十九届信息学... 10页 4下载券 NOIP2013初赛提高组Pasc... 13页...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告...NOIP2013提高组解题报告 8页 免费 NOIP2000-2009提高组解题... 47页 5下载券...

NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...

NOIP2013复赛模拟8解题报告

NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述]...

NOIP 2013 初赛提高组 问题求解

NOIP 2013 初赛提高组 问题求解_计算机软件及应用_IT/计算机_专业资料。【NOIP 2013 初赛提高组 问题求解】 1、 某系统自称使用了一种防窃听的方式验证用户密码。...