NOI2013 游记

【day 0】
嘛- –
坐飞机什么的
又晚点了= =
在飞机上写了个弹(dan)飞绵羊
编译过了
样例还没来得及测
后来又忘了。。
于是现在还不知道是对的错的
到了报道的地方后
报道了数小时
回宾馆(为闭幕式被dzd吐槽埋下了伏笔
全场无亮点
这几天安排如下
上午 下午
day1 开幕式 试机
day2 机试① 复测 讲题
day3 玩 玩
day4 机试② 复测 讲题 高校宣讲 签约
day5 团抗 闭幕式
day6 88~

【day1】
开幕式上
各种奇怪的人的奇怪的讲话
怎么感觉去年没那么多人blabla的样子- –
表演什么的还不错
不过有个摄像师全程台上卡位
无力吐槽,,
中午去了他们的食堂
除了没荤菜和全面贯彻落实了每道菜都是辣的的传统
其他还是不错的<其实不是很辣 下午试机 2:30~3:00是笔试 完了试机 笔试AK了! 令人欣慰 其实本来我选终止没有响应进程 我是用killall的 后来试了试 好像只能kill。。于是就换了。。 试机题嘛。。 第一题前队长讲过的后缀数组 我居然忘了QAQ 但是据说论文还有线性的做法orz 另外说下 我们宾馆的空调实在**** 于是今晚就到主任那房间睡 他出去玩了~ 【day2】 机试。。 早上6:40被闹钟叫醒 各种blabla 7:30左右出门了 到体育馆门口呆了会刚好进场 到考试开始整个过程 除了在电脑前等开始的时候有点困 其他来说心态还是比较良好的 8:00 翻开试卷 屹然看到提交答案4字 就有感觉这次考试有点hh了 第一题 60分完后 80分想了会没想出来 就去看第二题 我的解题策略习惯是这样的(这不一定是一个好的策略): 有提交答案 我一般会把它放在11点开始 做两个小时 在现在的情况 第一题的分性价比不是那么大 60分又实在好打 于是我决定接下来可以用大把的时间想第二题 想啊想啊想(具体怎么想的略过。。 到10点才想出一个n^2还会被卡精度的算法 快没什么时间了 果断拍 调 然后第一题 拍 不调 写随机 调 这样blabla完已经11:30 跟我预期有点差距。。 于是我开始拍第三题的前两个暴力点 这个暴力蛋疼 有因为略紧张了 调到考试前5min才调出来 赶快把暴力改了改 改成全1的 吧剩下点都跑了一遍 交卷。 在床上滚了一中午无视 下午看成绩 真心看成绩这心情才是压抑,,走路都腿软。。 第一题70 差不多 第三题29 也还好 虽然比预期低10分 后来发现是搜索尼玛写错了。。 第二题零 尼玛?。。。开始我以为是我的结论,b了 后来看了下输出 保留③位小数******* 论考试结束前看看题目输出格式的重要性。。。。。 其实这题是因为【Pa】 sdfasafgabklvjhasf【考挂自己弱!】 后来听讲题 第一题正解居然是随机性算法- - 第二题我那个结论是对的 只是还有个东西没推出来(+0.5)于是hh 这题我没hh的话+45分。。 第三题有人AK! 各种背包。。。 搜索没错应该可以40分 就是被-11 考挂自己弱不多说 后来好像也没什么亮点 就是知道金线差不多130的时候 “区区30分!二试再来大战30000000000回合!!!!!” 【day3】 玩什么的略显无聊= = 不说 晚上的时候 老师来我们房间发密码条 然后跟我说 第二题spj重写了 然后全场重测 我+45分! 全场重测!!业界良心 不能爽更多 【day4】 第一题 嗯 这不是矩阵嘛 嗯10^10^3啊 尼玛你确定这不是FJOI?! ↓ 第二题 "NOI" 你在逗我- - 果断不做= = ↓ 第三题 想啊想啊想 哦 原来是这样这样这样 有理有据 逆袭有望! ↓ 第一题 我记得有个mod phi定理?= = 就是你了 不管那么多了- - ↓ pa第一题正解 嗯 过样例了 不错不错 ↓ pa第一题暴力 嗯 也过样例了 不错不错 ↓ pa第一题对拍 嗯 correct for n次 不错不错 ↓ 怎么感觉有点有节奏感? 不科学。。 ↓ 原来没srand- -。。 ↓ 还是correct for n次 不错不错 ↓ pa第三题暴力 过样例了 很好! ↓ pa第三题正解 过样例了 很好! ↓ pa第三题对拍 ↓ 检查srand 好像是写了 ↓ correct for n次 very nice ↓ 各种检查输出格式n次 ↓ 考试结束= = 刚出考场就听clq说首长说第一题不能mod phi 而且就算mod phi 也要mod phi + phi QAQ 瞬间有种hh的赶脚 算了 不管那么多了 - - 【下午 又是一个更加坎坷的心情看成绩 先看到缩略图 第一题的result不是都一样的。。。 尼玛! 点开 一大片奇怪的因为 不是correct! 认真一看 Right Output Wahhhhhhhhhhh 第一题90分 然后迅速把它滚到下一页 又是一对一样的。。 直接拉到最后成绩了。。 90+0+100=190!!! 金牌无误了! 瞬间心情愉悦啊haaaaaaaaa 后面一大段全部略过~ 【get THU保送生协议 一份】 【day5】 团抗啊团抗 orz首长和ldf贡献的神代码 我就只是给神代码提提建议的蒟蒻T_T 穿橘黄色衣服特权:前排围观 开始被分到一个奇怪的组 轻松刷进甲组 然后第二次循环赛的时候 被赶到乙组了QAQ 虽然后面又上来了=v= 然后就一直在甲组 各种没出去 然后是分组赛 分到了甲2组 3个喜闻乐见的对手 直接进入第一组! 然后第一次从1~n的刷赛没出去! 这样就一定有前4了啊~ 求前3 求二等~ 【略过一大段 这里都在祈祷河北人民早日被刷掉。。可怕。。 决赛! 开始占据非常好的地形优势 四周无人 他们还都挤在一起 瞬间围出一个巨大的地 锁定胜局!! 后期各种压制+小范围圈地 RANK ONE GET!!!! 真心喜闻乐见 iPad抱回家 下午玩了一下午三国杀 5点开始颁奖(什么心态- - 福建这次是团体总分第二!! 太爽了hahaha 传说总分前三有福利?= = 【day6】 除了例行的晚点 其他也就没什么好说的了 一届又这么刷过了。。

【NOI】2009

变换序列
赤裸裸的匹配
字典序最小只要从后往前做
每次尽量用小的 就可以了
诗人小G
f[i]表示前i句话 拼起来要的最小代价
朴素的推就是枚举前面所有i 转移
是n^2的

不朴素的就是
这题显然决策单调 可以用决策单调版dp优化到nlogn
二叉查找树
可以发现 一个子树所有节点的数据值一定是连续的
可以离散掉数据值
f[i][j][k]表示i~j的数据值的点扔在一棵树 前k个已经付费了 要的最小代价
植物大战僵尸
最大权闭合子图
正权连源 负权连汇 有需求的连无穷边
管道取珠
这题十分奇葩啊= =
a[i]^2可以表示成方案相同的序列的对数。。
然后就可以用
f[i][j][k][l]表所第一个序列在上道取i 下道取j 第二个序列上道取k 下道取l的相同方案的对数。
各种推即可

【NOI】2010

能量采集
f[i] 表示gcd为i的个数
f[i] = (n / i) * (m / i) – f[i * j]
超级钢琴
这题开始只想到了一个很傻叉的nlog^2n的算法。。
就是二分第k大的权值
check可以用平衡树维护求出权值>=mid的个数
最后可以用同样的方法求出权值和

旅行路线

但是这种最后两个点会T= = 而且代码量跟正解也不是一个级别的- –

正解:
sum[i]为前缀和数组
对于所有以r为右端点的区间 设左端点的可行范围为[L, R]
则所有这些区间的最小权就是sum[r] – min(sum[i]) L <= i <= R
用一个堆维护所有右端点的这个值
这样就可以找出最大权值的区间
设这个区间的原l选取范围为[L, R]
最后选出的为li
则把这个区间分为[L, li – 1]和[li + 1, R]
在这两个里面分别找min 并放入堆中
这样找k次就可以了
复杂度nlogn
海拔
原题的提示有点略坑= =
ctsc上说遇到这种奇怪的题目就要
大胆猜想 小(bu)心(yong)证明

就是最小割
原图转对偶图 然后直接跑最短路就行了。。
航空管制
这个看这个把。。http://kilnyy.blogbus.com/logs/108637365.html

【NOI】2011

兔农
数论啊 = =
观察题目的fi % k的值
1 1 2 3 5 0
5 5 3 0
3 3 6 2 0
。。。。
可以发现:
1. 如果第i行的首项 为vi
则该行的第i项为 vi * fi % k(fi为fibonacci)
2. 每一行的首项=上一行的倒数第二项 以下称尾项
3. 如果首项循环 则整体循环
4. 一个首项为vi的行 长度为最小的满足fi*vi=1(mod k)的i
于是这题的做法就出现了 0 0
首先预处理出以某个数为首项的该行长度
做法如下:
num[i]表示以i为首项的长度
fi*vi = 1 (mod k)
这个有木有很像逆元~
对每个fi求出逆元(可以证明i = 1 ~ 3 * k)x
num[x] = min(num[x], i)
如果一个num[i]是没有长度的 则以这个为首项的行长为无限。。

求出num数组后 定义两个矩阵
1 1 0
1 0 0
0 0 1

1 1 0
1 0 0
-1 0 1
第一个是正常的fib矩阵
第二个是带把fi减一的矩阵
对于某一行 行长为k 就把ans矩阵乘第一个矩阵k-1次 再乘一下第二个矩阵

    对于一个已知的首项vi 可以快速算出尾项:
f[num[vi] – 1] * vi % k
这样就可以用logn的时间从一行推到下一行
显然首项<=k的时候就会循环
把循环的这一段的矩阵 和 总长度算出来
然后把ans矩阵 乘(n – used) / totlen次这个矩阵
然后继续用上面的方法逐行算 最后就可以GET ans了!
智能车比赛
利用斜率单调n^2建图 然后最短路即可
阿狸的打字机
裸AC自动机
对于一个写操作 就是往字典树上加一个节点 且把当前标记放到那里
对于一个B 就是把标记往上放一格
对于P 就是记录当前节点编号即可
对于一个询问(x, y)
如果x y在fail树上的lca不为x 则为0
否则为深度差
道路修建
这题太难了 不能直视 巨弱表示不会写。。
Noi嘉年华
先离散化
num[i][j]表示 a[i].l >= i && a[i].r <= j的个数
suc[i][j]表示 前i个时间 第一个嘉年华办j个活动 第二个嘉年华最多办几个
suc[i][j] = max(suc[k][j] + num[k][i], suc[k][j – num[k][i]])
pre[i][j]表所 i~m这些时间 第一个嘉年华办j个活动 第二个嘉年华最多办几个
基本同上
ans[i][j]表示 i~j时间的活动都有举行 最大的ans是多少
ans[i][j] = max(min(x + y + num[i][j], pre[i][x] + suc[j][y]))
因为y随x增而减 且x相同时 以y为自变量的函数单峰
所以这个可以n^3求解
第一问就是max(ans[i][j])
第二问 对于l, r
max(ans[i][j]) (i <= l &&  r <= j)
兔兔与蛋蛋
二分图匹配。
显然走出来的路径是黑白路径
黑白匹配 如果起点在一个最大匹配中 则必胜
否则必败
证明:
1.如果起点在一个最大匹配中 则必胜
反证:
psb (2)
如图 开始在 1 走到2
如果2走到3之后就没路了的话 那么1~2这个匹配就会被2~3替代
不符定义
2.  否则必败
这个其实只要证明从这个点一定会走入一个最大匹配点就行了
反证:
若从一个不在最大匹配的点走过去后仍然不在最大匹配中
则这条边可以加入最大匹配
不符定义
于是这题只要每次找出是非必胜
如果上次必胜
在这次操作后必败了
那这就是一个不科学的操作。

【NOI】2012

巨弱现在才开始刷noi历届= =。
做着2012
感慨去年的事态万千0 0,(如何被虐成傻叉= =

—————————题解———————————-
随机数生成器
裸的矩阵乘 加一个快速乘法
去年连这货也不会 果然喜闻乐见- –
骑行川藏 
 这题有两种做法
1。
可以考虑每一个极小的能量要分配在哪段路上最优
对每段路求导 可以得出每段路在没对能量进行分配时的极小能量贡献
然后把那段能量一直加 直到有跟他一样的 就一起加
这样好像不是很好写 <因为我太弱了- –
但是比起2 看起来会科学一点
2。
拉格朗日乘数法
这题可以列出一个约束方程和一个n变量函数
拉格朗日乘数法就是可以求这样一个带约束的多元函数极值的东西
以2元为例
约束方程:g(x, y) = k1s1(x – v1′) ^ 2 + k2s2(x – v2′) ^ 2 – E
函数:f(x, y) = s1/x + s2/y
梯度向量就是对这个函数的每个元求偏导得出的向量
f的偏导记为 ∇f
偏导就是以这个元为主元 对这个函数求导
令  ∇f = λ∇g

        会得到n+1个方程
-s1/x^2 = λ2k1s1(x – v1′)
        -s2/y^2 = λ2k2s2(y – v2′)
k1s1(x – v1′) ^ 2 + k2s2(y – v2′) ^ 2 – E = 0
求解之~
求解方法:
可以发现  λ越大各个v值越大
二分 λ如果 用当前 λ算出所有v
带入最后一个方程
如果<0 则 λ过小 否则过大

怎么用 λ算v?
就是求解方程2 λki(x – vi’)x ^ 2 + 1 = 0
二分之 如果设L1 = v1 可以发现这是单调的 就可以求解了
如果不是单调也可以用牛顿迭代

可以看这篇文章: http://www.cppblog.com/prime56/archive/2012/08/13/noi2012_bicycling.html  

魔幻棋盘


gcd(a, b, c, d) = gcd(a, b – a, c – b, d – c)
即 ai = ai – ai-1
拓展到二维 如图
如果1是中心 则对于4
就是a[i][j] = a[i][j] + a[i + 1][j + 1] – a[i + 1][j] – a[i][j + 1]

5 6 7同理

2 3只要按一维的做

1不变

psb (4)
用二维线段树维护区间gcd和 每次修改最多修改9个点
迷失游乐园
对于无环的情况:
随便指定一个点为根
down[i]表示点i往下走的期望长度
up[i]表示点i往上走到期望长度
可以很简单的算出down
然后按dfs序算 可以算出up数组
对于有环:
指定环上点为根 先算出所有down
然后算出所有环上点的up 即不走子树的期望长度
然后就跟无环的一样算其他点的up就行了

美食节
每个人建n个点表示第i次做 各种blabla
这题要动态加点
就是每个人第一次走的一定时最小的那个点
先加这个点
这个点被走过了再加下一个

至于那题提交答案。。 颓了很久那个游戏 然后就没有然后了- –
———————————————
唉=/=