Noip2013题解-顾霆枫.doc

Noip2013题解By GTFDay 1Circle考试当天早上大脑出现了神一样的变异，居然抽风地拿着手机去看快速幂。考试在熟悉环境时把它打了下来，题目一发下来我和我的小伙伴都惊呆了！第一题居然是快速幂！【问题描述】 n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，依此类推。 游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第m+1号位置，依此类推，第n m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，第 n-1 号位置上的小伙伴顺时针走到第m-1号位置。 现在，一共进行了 10k轮，请问x号小伙伴最后走到了第几号位置。 【输入】 输入文件名为circle.in。 输入共1行，包含 4个整数n、m、k、x，每两个整数之间用一个空格隔开。 【输出】 输出文件名为circle.out。 输出共1行，包含 1个整数，表示10k轮后 x号小伙伴所在的位置编号。 【输入输出样例】 circle.incircle.out10 3 4 5 5 【数据说明】 对于30%的数据，0 k 7； 对于80%的数据，0 k 107； 对于100%的数据，1 n 1,000,000，0 m n，1 x n，0 k 109。【题解】不难发现答案就是m+10kmod nO(log2k)的算法。因为 k109，算下来只有30！程序在下：#include #include #include #define LL long long#ifdef WIN32#define OTL %I64d#else#define OTL %lld#endifusing namespace std;LL n,m,k,x,ans;LL qm(LL a,LL b,LL m)LL r=1;LL bit=a;while (b!=0) if (b & 1 =1) r=r*bit%m;bit=bit*bit%m;b=b1;return r;int main()freopen(circle.in,r,stdin);freopen(circle.out,w,stdout);scanf(OTL OTL OTL OTL,&n,&m,&k,&x);ans=qm(10,k,n);ans=(m*ans)%n+x)%n;printf(OTL,ans);return 0;Match神奇地爆0了（其实也不神奇），后来才做出来。【问题描述】 涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：i=1nai-bi2 ，其中ai表示第一列火柴中第i个火柴的高度，bi表示第二列火柴中第 i个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对99,999,997取模的结果。 【输入】 输入文件为match.in。 共三行，第一行包含一个整数 n，表示每盒中火柴的数目。 第二行有n个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。 第三行有n个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。 【输出】 输出文件为match.out。 输出共一行，包含一个整数，表示最少交换次数对99,999,997取模的结果。 【输入输出样例1】 match.inmatch.out42 3 1 43 2 1 41【输入输出样例说明】最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。【输入输出样例2】match.inmatch.out41 3 4 21 7 2 42【输入输出样例说明】 最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第2列中后2根火柴的位置。 【数据范围】 对于10%的数据， 1 n 10； 对于30%的数据，1 n 100； 对于60%的数据，1 n 1,000； 对于100%的数据，1 n 100,000，0 火柴高度 231 1。【题解】对距离公式化简得：(ai-bi)2=(ai2-2aibi+bi2)=ai2+bi2-2aibi要求(ai-bi)2最小，就只需要aibi最大即可。这里有个贪心，当a1a2an，b1b2b,cd,且ac+bdad+bc，则a(c-d)b(c-d),则ab矛盾，所以若ab,cd，则ac+bdad+bc将此式子进行推广：当a1a2a3.an ,b1b2.bn的情况下aibi最大，即(ai-bi) 2最小。然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。求逆序对方法：1. 归并排序2. 把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同时查询比这个数大的数有几个，加入答案。复杂度 : O(nlog2n)Code：#include#include#includeusing namespace std;#define MAXN 100010#define lowbit(x)(x)+1)&x)#define MAX 99999997struct saver int v,t;saver aMAXN,bMAXN;bool cmp(saver x,saver y) return x.vy.v;int n,rMAXN,ans=0;int tMAXN;void Add(int x)for(int i=x;i=n;i+=lowbit(i) ti+;int Sum(int x) int rec=0; for(;x;x-=lowbit(x) rec+=tx; return rec;int main() scanf(%d,&n); for(int i=0;i+n;) scanf(%d,&ai.v),ai.t=i; for(int i=0;i+n;) scanf(%d,&bi.v),bi.t=i; sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp); for(int i=0;i+n;) rai.t=bi.t; for(int i=n;i;i-) ans+=Sum(ri),Add(ri),ans%=MAX; printf(%dn,ans); return 0;Truck这道题跟Running有相同之处，我居然没有看出来。话说倍增还没弄明白，最大生成树也仅仅是会打。看来得恶补一下了。【问题描述】 A 国有n座城市，编号从1到n，城市之间有 m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 【输入】 输入文件名为truck.in。 输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。 接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x 号城市到y号城市有一条限重为z的道路。注意：x不等于y，两座城市之间可能有多条道路。 接下来一行有一个整数 q，表示有q辆货车需要运货。 接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到y城市，注意：x不等于y。 【输出】 输出文件名为truck.out。 输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。 【输入输出样例】 ruck.out4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3 3 -1 3 【数据说明】 对于30%的数据，0 n 1,000，0 m 10,000，0 q 1,000； 对于60%的数据，0 n 1,000，0 m 50,000，0 q 1,000； 对于100%的数据， 0 n 10,000，0 m 50,000，0 q 30,000， 0 z 100,000。【题解】首先，我们可以确定贪心的正确性，我们先把边按权值从大到小排序，然后依次加入图中，如果该边的起末点不在同一连通块中，那么就把边加入，否则不加处理，很明显，这样生成的图，两点之间要么没有路径，要么唯一一条路径中权值的最小值最大。所以，我们只要先跑一次最大生成树，然后在求点对之间的树上路径最小值就可以了。#include #include #include 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; eMAXM; bool cmp(saver x,saver y) return x.dy.d; int fatherMAXN,n,m,q,QMAXQ2; int Find(int x) int i,j=x; for (i=x;fatheri;i=fatheri) ; while (fatherj) int k=fatherj; fatherj=i; j=k; return i;int upMAXNMAXD,MinMAXNMAXD,hMAXN;bool fMAXN; struct edge edge *next; int t,d; edge () next=NULL; *headMAXN; void Add(int s,int t,int d) edge *p=new(edge); p-t=t,p-d=d,p-next=heads; heads=p; void BuildTree(int v) fv=false; for (edge *p=headv;p;p=p-next) if (fp-t) upp-t0=v,Minp-t0=p-d,hp-t=hv+1; BuildTree(p-t); int Move(int &v,int H) int rec=inf; for (int i=MAXD-1;i=0;i-) if (hupvi=H) rec=min(rec,Minvi); v=upvi; return rec; int Query(int u,int v) if (Find(u)!=Find(v) return -1; int rec=inf; if (hu!=hv) rec=huhv?Move(u,hv):Move(v,hu); if (u=v) return rec; for (int i=MAXD-1;i=0;i-) if (upui!=upvi) rec=min(rec,min(Minui,Minvi); u=upui,v=upvi; rec=min(rec,min(Minu0,Minv0); return rec;int main() clear(father),clear(head),clear(up); scanf(%d%d,&n,&m); for (int i=0;im;i+) scanf(%d%d%d,&ei.s,&ei.t,&ei.d); sort(e,e+m,cmp); for (int i=0;im;i+) if (Find(ei.s)!=Find(ei.t) fatherFind(ei.s)=Find(ei.t); AddEdge(ei.s,ei.t,ei.d); memset(f,true,sizeof(f);for (int i=0;i+n;)if (fi)hi=0,BuildTree(i),Mini0=inf,upi0=i; for (int i=0;i+MAXD-1;) for (int j=0;j+n;) upji=upupji-1i-1; Minji=min(Minji-1,Minupji-1i-1); scanf(%d,&q); while (q-) int u,v; scanf(%d%d,&u,&v); printf(%dn,Query(u,v); return 0;Day 2Block十分钟解决的题。【问题描述】 春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。在搭建开始之前，没有任何积木（可以看成n块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间L,R，然后将第L块到第R块之间（含第 L 块和第 R 块）所有积木的高度分别增加1。小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。 【输入】 输入文件为block.in输入包含两行，第一行包含一个整数n，表示大厦的宽度。第二行包含n个整数，第i个整数为hi 。 【输出】 输出文件为block.out仅一行，即建造所需的最少操作数。【输入输出样例】 block.inblock.out52 3 4 1 25 【样例解释】其中一种可行的最佳方案，依次选择1,5 1,3 2,3 3,3 5,5【数据说明】 对于 30%的数据，有1 n 10；对于 70%的数据，有1 n 1000；对于 100%的数据，有1 n 100000，0 hi 10000。【题解】分治：找到min(hi)，答案加上它，全体减去它，再在左边和右边重复这么做。#include #include #include #define LL long long#ifdef WIN32#define OTL %I64d#else#define OTL %lld#endifLL n,h100050,ans;LL block(int l, int r) if (l=r) return hl; int i,j,k; LL result=0; k=l; for (i=l+1;i=r;i+) if (hihk) k=i; result+=hk; for (i=l;i=l) result+=block(l,k-1); if (k+1=r) result+=block(k+1,r); return result;int main() freopen(block.in,r,stdin); freopen(block.out,w,stdout); scanf(OTL,&n); int i; for (i=1;i g2i1，且g2i g2i+1；条件 B：对于所有的i，g2i g2i1，且g2i 1时最多有一个能满足。请问，栋栋最多能将多少株花留在原地。【输入】 输入文件为 flower .in。输入的第一行包含一个整数n，表示开始时花的株数。第二行包含n个整数，依次为h1, h2, , hn，表示每株花的高度。【输出】 输出文件为 flower .out。输出一行，包含一个整数n，表示最多能留在原地的花的株数。【输入输出样例】 block.inblock.out55 3 2 1 23 【输入输出样例说明】有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。【数据说明】 对于 20%的数据，n 10；对于 30%的数据，n 25；对于 70%的数据，n 1000，0 hi 1000；对于 100%的数据，1 n 100,000，0 hi 1,000,000，所有的hi 随机生成，所有随机数服从某区间内的均匀分布。【题解】有一种神奇的方法叫找拐点：从h2扫到hn-1，如果它不是拐点就删去它，计数器减一。貌似这个方法小学上信息培训班时就讲过，没看出来真可惜，如果加了这100分就一等奖了。O(n)搞定。#include #include #include #define LL long long#ifdef WIN32#define OTL %I64d#else#define OTL %lld#endifusing namespace std;LL N;LL V100050,Left100050,Right100050;void init()scanf(OTL,&N);for(int i=1;i=N;i+)scanf(OTL,&Vi);Lefti=i-1;Righti=i+1;void solve()LL ans=N;for(int i=2;i=Vi&Vi=VRighti)|(VLefti=Vi&Vi=VRighti)ans-;RightLefti=Righti;LeftRighti=Lefti;printf(OTL,ans);int main()init();solve();return 0;Puzzle很明显，这样的题目是不可能在考场上AC的。【问题描述】 小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：1. 在一个 n*m 棋盘上有 n*m 个格子，其中有且只有一个格子是空白的，其余 n*m-1个格子上每个格子上有一个棋子，每个棋子的大小都是 1*1 的；2. 有些棋子是固定的，有些棋子则是可以移动的；3. 任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。给定一个棋盘，游戏可以玩 q 次，当然，每次棋盘上固定的格子是不会变的， 但是棋盘上空白的格子的初始位置、 指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候， 空白的格子在第 EXi 行第 EYi 列，指定的可移动棋子的初始位置为第 SXi 行第 SYi列，目标位置为第 TXi 行第 TYi 列。假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。【输入】 输入文件为 puzzle.in。第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n、m 和 q；接下来的 n 行描述一个 n*m 的棋盘，每行有 m 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。接下来的 q 行，每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。【输出】 输出文件名为 puzzle.out。输出有 q 行，每行包含 1 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出1。【输入输出样例】 puzzle.inpuzzle.out3 4 20 1 1 10 1 1 00 1 0 03 2 1 2 2 21 2 2 2 3 22-1【输入输出样例说明】棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。1. 第一次游戏，空白格子的初始位置是 (3, 2)（图中空白所示），游戏的目标是将初始位置在(1, 2)上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置(2, 2)（图中红色的格子）