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_2013_提高组_Day2_解题报告

Noip_2013_提高组_Day2_解题报告_计算机软件及应用_IT/计算机_专业资料。第二题:花匠(动态规划) 1.令 S[i][1]表示以 i 为结尾, 且降序到达 a[i]的最长...

Noip 2013 提高组 Day2 解题报告

Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...

NOIP2013解题报告

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

CCF NOIP2013 解题报告&心得

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 CCF NOIP2013 解题报告&心得虽然已经过去很久了, 但是终于有机会有时间写一下解题 报告 ——By 黄锦松 FJ-...

NOIP2015提高组解题报告

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

Noip 2013 Day1 解题报告

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

2011noip提高组解题报告

6页 1财富值 NOIP2013提高组解题报告 8页 免费喜欢此文档的还喜欢 ...的反集同组} if y<>x0 then f[y]:=x0;{令y与x的反集同组} 的话 ...

noip 2012 提高组 解题报告

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

NOIP2013提高组复赛试题

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