NOIp2014 解题报告

有史以来第一届面向社会征题的NOIp结束了。最开始以为面向社会征题会很难，但是这是我参加的最水的一次NOIp了。

由于停了两月的课，所以现在正在补文化科目就没时间打代码了。所以所有的题目就均不给出代码了啦啦啦~为了方便没有参加NOIP的童鞋们我把题目网址放到了每道题题解的最后。

晚了两周的题解如下：

Day1T1 生活大爆炸版石头剪刀布

我就不说了。。近几年来NOIp最水的第一题（我会告诉你我去年第一题用的是30分算法？）我们这里有一位小伙伴本地测试AC，但是官方爆0了。我们特意下载了NOI Linux帮他重测，原因是什么呢？没有#include<cstdio>就freopen+stdin。stdin是定义在cstdio里面的好吗！！所以他第一天愉快的爆0。。但是第二天他神奇的加上了#include <fstream>，这个里面有定义stdin。。简直没话说。。另外他的D1T2和D1T3上交的是main.cpp，全部没有收上去。不过收上去也是CE。。

感谢后世人，戒之慎勿忘！

一定养成检查文件名、头文件的好习惯！头文件最好一开始就全部打上去，不管用不用得到。在此分享一下我的代码模板：

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <string>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #include <list>

 #include <vector>

 #include <ctime>

 #include <functional>

 #include <iterator>

 using namespace std;

 typedef long long LL;

 typedef unsigned int Uint;

 const int INF=0x3fffffff;

 //==============struct declaration==============

 //==============var declaration=================

 //==============function declaration============

 //==============main code=======================

 int main()

 {

 #define FILE__

 #ifdef FILE__

   freopen("spyweb.in","r",stdin);

   freopen("spyweb.out","w",stdout);

 #endif

   return ;

 }

 //================fuction code====================

Template

回到正题，n<=200，不同的人会有不同的做法：

普通青年：打表判断获胜关系。

文艺青年：将两个外星人调换顺序，那么就可以直接比较大小判断胜负了。

二逼青年：16或者25个 if。。。。

http://218.28.19.228/cogs/problem/problem.php?pid=1803

Day1T2 联合权值

30分算法：FLOYED算出每两个点之间的距离，然后枚举距离为2的点。算法复杂度O（n³）。

70分算法：对于每一个点，BFS向外扩展两层。时间复杂度O（n²）。可以轻易的用菊花图卡掉。（比如1号点直接链接9999个点）

100分算法：距离为2的点之间一定是有一个点的，我们对每个点进行维护，那么最后的答案就是每个点任意两个孩子权值和的乘积，如果直接枚举的话时间复杂度还是O（n²）,我们这里用前序和优化，时间复杂度O（n）。

http://218.28.19.228/cogs/problem/problem.php?pid=1804

Day1T3 飞扬的小鸟

不知道为什么我总是喜欢把这一题叫做愤怒的小鸟。。

话说每年总是有广告题。。选择客栈，玛雅游戏什么的我就不说了。。

30分算法：没有管道的话。。我还没想有什么算法0_0

50分算法：暴搜一点问题都没有

70分算法：用f[x][h]表示飞到(x,h)这个地方最少要点几次屏幕，那么动态转移方程很好写吧：

f[x+1][h+n*x_i]=min{f[x+1][h+n*x_i]，f[x][h]+n}

f[x+1][h-y_i]=min{f[x+1][h-y_i],f[x][h]}

然后水管全部设置为INF就行，初值f[0][i]=0

时间复杂度O（n*m²）

100分算法：发现我们重复计算了很多次同一个状态，这就导致转移状态的复杂度太高，所以我们把h mod x_i相等的高度一起计算，时间复杂度优化到O（n*m）。

http://218.28.19.228/cogs/problem/problem.php?pid=1805

Day1总结：

还是挺水的，其实不知道各位是否看出来最后一题就是一个向上完全背包，向下0/1背包的模型。考试的时候没能看出来有点可惜了。用的记忆化搜索，可能是因为有一些不能达到的状态没有走到的原因吧，有75分。

那么第一天275分拿到手了。第一天拿一个100/70/50是很容易的，那么就有220分了。

Day2T1 无线网络发射器选址

为什么每天的第一题名字都是这么长。。

那么这里再用我的一个小伙伴的亲身经历告诉大家考试方法，那就是不作死就不会死。

很简单的一题，枚举每一个点作为放置路由器的地方，然后统计比较就行。时间复杂度O（128*128*n），针对最大n是20的范围完全可以通过。

某个小伙伴认为他可以优化一下，写了个前序和。。然后不知道哪里写错了。。70分还是60分来着。然后枚举点只从(d,d)枚举到(128-d,128-d)

其实能有这么多分都是万幸了。。要我出数据就专门卡这些乱优化的。

还见到有人写2维树状数组的= =吃饱了没事做。。不过树状数组好在不容易写错。

http://218.28.19.228/cogs/problem/problem.php?pid=1806

Day2T2 寻找道路

看到这一题第一反应就是强联通分量，想了15min才发现沙茶了O_o

30分算法：应该是给搜索的，但是我不知道怎么搜= =

60分算法：对于每一个点跑一边BFS看看是否能够到达终点，然后从起点BFS，避开那些不能到达终点的点。时间复杂度O（n²）。

或者是floyed判断是否能到达终点似乎方便一些？时间也是够用的。

100分算法：难道没有发现对于每一个点BFS判断是否能到达终点就等价于在反图中从终点开始BFS?将不能到的点打上标记，然后正向BFS避开即可。时间富O（n）。

P.S.我看见了写邻接矩阵完美MLE的。

有想到正解的实力居然不知道开邻接表也是醉了。。。还看到C++邻接表写挂的，Vector不能用吗= =反正NOIp又不会卡你STL。

http://218.28.19.228/cogs/problem/problem.php?pid=1807

Day2T3 解方程

这个题我最开始就想到求导和二分法求根了。。怎么办我没救了！！

那么30分算法：n<=2不会我也没办法。。

50分算法：高精度强行1-m搞起，本来我是想写这个的

70分算法1：高精度+FFT/高精度+秦九韶/高精度+秦九韶+FFT 然后1-m试一次。但是还是很难写

70分算法2：将每一个系数均MOD一个大质数，就是计算该方程在模意义下的解。如果你怕不保险就多取几个质数，不过据说这次没有卡1e8+7和2^31-1这两个质数，时间复杂度O（n*m）

100分算法1：我们知道，如果在模p意义下X不是方程的解，那么X+p一定也不是方程的解，我们选取20-30个10000左右的质数，这样的话理论上可以优化到O(n*sqrt(m))

100分算法2：我们发现70分算法最后跑出来大概需要1.2S，说明是被卡常数了。于是我们位运算加速MOD过程，取2^32-1这个数比较好。虽然不是质数不过也还好。那么我们就让unsigned int自然溢出可好。。这个方法没有实践过，不保证一定AC。

http://218.28.19.228/cogs/problem/problem.php?pid=1808

Day2总结：

也挺水的，Day2的基本分数应该是100/70/30，那么就是200分，加上Day1一共420分，在HN应该是踩线1等。

不过这只是保底分。。你Day2T3如果只是能想出30分算法也没办法是吧。。所以这次比赛一等在除了ZJ和GD应该不难。ZJ530,GD520只要你每天前两题AC，第三题70也没问题。

那么我是100/100/75/100/100/70，一共545分，HN一等。

HNOIへ！然后参加了HNOI之后估计就要滚粗了吧- -

巴特西