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

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 提高组 解题报告.pdf
Noip 2013 提高组 解题报告 --By GreenCloudS Day
Noip_2013_提高组_Day2_解题报告.doc
Noip_2013_提高组_Day2_解题报告 - 第二题:花匠(动态规划) 1
Noip 2013 提高组 Day2 解题报告.doc
Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...
NOIp2013普及组解题报告.pdf
NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 NOIp2013 普及组 解题报告 By 绍兴文理学院附中 ...
noip2017提高组复赛解题报告.doc
noip2017 提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息
NOIP2013提高组初赛试题与答案.pdf
NOIP2013提高组初赛试题与答案 - 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C 语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:30 选手注意: ? ?...
【精选资料】Noip 提高组 Day2 解题报告.doc
【精选资料】Noip 提高组 Day2 解题报告_英语_初中教育_教育专区。文档均来自网络,如有侵权请联系我删除文档 Noip 2013 Day2 解题报告 --By GreenCloudS 第一...
CCF NOIP2013 解题报告&心得.doc
CCF NOIP2013 解题报告&心得 - 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 CCF NOIP2013 解题报告&心得 虽然已经过去很久了, 但是终于有机会...
NOIP2013提高组参考答案.pdf
第十九届全国青少年信息学奥林匹克联赛初赛 提高组参考答案一、单项选择题(共 15...NOIP2013提高组解题报告 8页 免费 NOIP2013提高组Pascal试... 12页 2下载...
NOIP2018提高组解题报告.doc
NOIP2018提高组解题报告_学科竞赛_高中教育_教育专区。第34届全国青少年信息学奥林匹克联赛NOIP2018提高组复赛解题报告此前的版本有少许笔误,已修订 ...
NOIP2013普及组复赛试题+解题报告.pdf
NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 NOIp2013 普及组 解题报告 By 绍兴文理学院附中 任轩笛 表达式求值(expr.pas/c/cpp) Time Limit:1000...
NOIP2013提高组复赛试题.doc
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 CCF 全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 1.转圈游戏 (circle.cpp/c/pas) 【问题描述】 ...
noip2013提高组 day1.pdf
全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day1 CCF 全国信息学奥林匹克...NOIP2013提高组复赛Day1 4页 免费 Noip 2013 Day1 解题报告... 8页 免费...
NOIP2018 提高组 解题报告.doc
NOIP2018 提高组 解题报告_学科竞赛_高中教育_教育专区。第二十四届全国青少年信息学奥林匹克联赛NOIP2018提高组解题报告,作者:南京师范大学附属中学 高二 陈天 ...
NOIP2013解题报告.doc
NOIP2013解题报告 第一题 计数问题(count.pas/c/cpp) 题目大意: 给出两个数...NOIP2013提高组解题报告 8页 免费 noip2013解题报告 11页 2下载券 CCF NOIP...
noip2013解题报告.pdf
NOIP2013解题报告长郡中学 黄鑫 1.circle 题目描述: n 个小伙伴(编号从 ...NOIP2013提高组解题报告 8页 免费 NOIp2013普及组解题报告 11页 1下载券 [...
NOIP2010提高组复赛试题及解题报告.doc
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
noip 2012 提高组 解题报告.doc
noip 2012 提高组 解题报告 Vigenère 密码模拟注意大小写 va
Noip 2013 解题报告与参赛总结(PASCAL版).doc
Noip 2013 解题报告与参赛总结(pascal 版) Noip 结束也有一段时间了,网上也能...NOIP2013提高组解题报告 8页 免费 Noip 2013 提高组 Day2 ... 14页 ...
NOIP2013初赛提高组c试题.doc
NOIP2013初赛提高组c试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2013 年 10 月 13 日 14:30~...