FJOI倒数21天

1. 不要忘记开long long int。
2. 不要忘记取模。
3. 不要忘记初始化数组。（高精度 / Floyd）
4. 注意计算函数的位置。
5. 提交前先查看计算结果。
6. 提交前多做几组数据，特别是做数据难度不大的时候。
7. 注意输出格式，特别是没有SPJ的带小数的时候。
8. 注意查询区间max/min时，暂存变量的变量类型。
9. abs不是模板函数，double类型使用fabs。

照叶犇说的Register了bzoj开始刷。下午一节课加上一个晚自习。

“这个命有点难续啊。。
疯狂地做bzoj可能可以补救一下。。”

我也这么觉得。
正文中对于名词的超链接均蕴含“这是什么玩意”。
P1000 A+B Problem (Accepted)
深呼吸，一切正常，下一题。
P1001 [BeiJing2006]狼抓兔子 (Accepted)
这是什么玩意… 满脑子都是暴力，懵逼之后点开Google。
平面图的最小割，转对偶图求最短路。
具体操作就是，把(1,1)和(n,m)连一条边，构成一个新面，记为ext。把原来的外面的面记为0。
对于每条边（除了刚才连的那条），把它两侧的面连起来，代价即边权。
然后求[0]到[ext]的最短路，就AC了。
P1002 [FJOI2007]轮状病毒 (Accepted)
打表找规律，f[i] = 3 f[i-1] – f[i-2] + 2，要高精度。
但是据说正解是用基尔霍夫矩阵推的，这是什么玩意……
P1003 [ZJOI2006]物流运输 (Accepted)
嘿嘿嘿这题我之前写过了（趴）
最短路加上DP，没有什么搞不懂的。
P1004 [HNOI2008]Cards (Accepted)
这是什么玩意……
要打标签的话好像是DP，置换，逆元，Burnside引理。有点像求简化剩余系的感觉（虽然完全不是一个东西）。
呃，这里参考VFK的博客，DP方面参考IT大道的这篇文章。
|X/G|就是解？求G中所有置换的d值的平均值就可以啦？

“X中经过G[i]的作用后仍旧为没有变化的元素个数为d(i)，
置换群G在有限集合X作用下等价类的数目等于d(1),d(2),d(3)…d(n)的平均数。”

好吧，那怎么求d(i)？

“对于某一个置换要使置换后得到的与原来的相同，就应该把置换形成的环染成同一种颜色，也就是说属于一个环内的元素颜色一定相同，然后一定要有一定量的红蓝绿色，因此用一个完全背包即可。
f[i][j][k]表示选了i张红色j张蓝色k张绿色的方案数，f[i][j][k]=f[i][j][k]+f[i-sum][j][k]+f[i][j-sum][k]+f[i][j][k-sum](sum表示当前环大小，然后i,j,k一定要判是不是大于sum），最后还有就是任何时候都不要忘了不动也是一个置换，因此有m+1个置换。”

恩……然后……就AC了。
这题调了半天在洛谷上各种WA和TLE，百思不得其解。
然后发现我把本来只要跑一次的计算函数重复跑了n次，放在input函数里了。

恩……早上的政治课和地理课就……算了吧……？
P1005 [HNOI2008]明明的烦恼 (Accepted)
这题据说要用Prüfer序列。

“一棵树要得到普吕弗序列，方法是逐次去掉树的顶点，直到剩下两个顶点。考虑树T，其顶点为{1, 2, …, n}。在第i步，去掉标号最小的叶，并把普吕弗序列的第i项设为这叶的邻顶点的标号。
一棵树的序列明显是唯一的，而且长为n − 2。”

另外有个Cayley定理，n顶点的标号树共有nⁿ⁻²棵。（虽然这题好像没用）。
总之，这个树可以表示为n-2长度的序列，要往里面插入(tot=度数和-1)个序号；插第一个节点的方法x插第二个节点的方法…再x无度数限制的m个排列在剩余(n-2-tot)个空间中。
参考是这篇博文，还有这篇。
我感觉我要死了Orz
我艹！A了！
高精度稍微改了一下，这回居然没出错。
我还想着这个数据规模怎么可能会TLE，结果是因为忘了把之前改的地方改回来导致质因数数量变成了负数……
结果两节课就做了两题（还有一题是昨天的）（趴）。
P1006 [HNOI2008]神奇的国度 (Accepted)
刚才打的五百多个字不见了，真是日狗。
算了，这题就是弦图染色。
参考资料是弦图与区间图的PPT。
解法似乎有两种：
字典序BFS（这个我并没有看懂）

• Initialize a sequence Σ of sets, to contain a single set containing all vertices.
• Initialize the output sequence of vertices to be empty.
• While Σ is non-empty:
  • Find and remove a vertex v from the first set in Σ
  • If the first set in Σ is now empty, remove it from Σ
  • Add v to the end of the output sequence.
  • For each edge v-w such that w still belongs to a set S in Σ:
    • If the set S containing w has not yet been replaced while processing v, create a new empty replacement set T and place it prior to S in the sequence; otherwise, let T be the set prior to S.
    • Move w from S to T, and if this causes S to become empty remove S from Σ.

最大势算法，但是按照英文名好像应该叫最大匹配搜索？
这个倒是挺好理解的，从n到1标号。每次标号的对象是现在势最大的点，其中势定义为相连的已标号的点数。标号为i的就是完美消除序列的第i个。

“先求出完美消除序列，再依照完美消除序列，从后向前，依次贪心染色，每次尽量染编号小的颜色。
最后输出最大颜色编号即可。”

那，写看看……WA了。
遂发现好像写的不对。
打出queue一看，发现有重复的，什么都明白了……
然后现在回头看jcvb说的就明白啦。

维护每个结点的“势”。并维护n个链表，分别表示势为0~n-1的结点各有哪些。
维护一个best值表示当前最大的势。
再开一个bool数组记录每个点是否已被取出放入序列。
初始时每个点势为0，都放在0号链表里。best=0。
①更新操作：某结点u的势从x变为x+1时，只要把u插到x+1链表的头部，无需将其从x链表中删除（所以不用写双向链表）。然后更新best值。
②取最大操作：取最大势结点时从best链表的头开始取，如果取到的是已被放入序列的结点就删除并继续往后取，仍取不到则–best，直到取到一个未被放入序列的点。
操作①每次O(1)，总共执行O(m)次。best++也被执行O(m)次，那么操作②中–best也只有O(m)次。操作①每次插一个结点，则总共有O(n+m)个结点，而操作②中每往后取一个就删一个，所以也是O(n+m)。

哎，我还是把以前的那个blockquote的css搬过来吧。
恩，AC了。
第二次的WA死于贪心逆序，应该从后往前涂色，而不是从前往后涂色。不过到底怎么找“最小的可用的颜色”效率比较高呢？我直接扫了一遍周围的所有点，然后拿bool数组标记，再找最小的可用值。
P1007 [HNOI2008]水平可见直线 (Accepted)
看起来是道几何题，随便搜了一下……半凸包是什么玩意儿？
这题说不定可以直接写（？）
虽然我不知道半凸包是什么玩意儿但是我写了个二分（大概吧）就AC了。
具体来说，按第一关键字斜率升序，第二关键字截距降序排序。
第一条直线(a)和最后一条直线(b)显然是可见的嘛。
然后算出它们的交点(x1,y1)，再从(a,b)范围内查找在x1时y最大的一条直线(c)，这个也可见。
分别把a和c，c和b拖出来重复如上操作，然后就没有然后了。
来吧，下一题。
P1008 [HNOI2008]越狱 (Accepted)
这题应该就是普通的组合数学？……其实是快速幂模板题。
用Python交了一波…忘记取模（捂脸）
用C++交了一波…居然对指数取了模（捂脸）
没脸见人了……
P1009 [HNOI2008]GT考试 (Accepted)
一眼看上去好像是组合。
仔细一想好像哪里不对啊…
这题怎么列式子啊…
Google之，发现这玩意是DP（捂脸）
Google还说是AC自动机(KMP)。
KMP是退化的AC自动机，即模式串只有一个的情况。这里参考这篇博文来学习。
题解的话，这篇博文好像可以参考一下。但是他没说P是什么东西。
说实话我还是不太懂KMP和这题的关系orz
看了这里的代码好像懂了DP长什么样。
可是KMP？
这题的DP似乎要用到矩阵乘法x快速幂来加速。
不过我现在被编辑追着，先打点稿子…
最后我对着别人的代码打了一遍。
然后我打出了一个
[cpp]num[i] = str[i] – 0;[/cpp]
被自己蠢到了……
但是我还是没搞太懂怎么推出来的。回头问叶犇……

今天早上花了好多时间在P1009上Orz。
P1010 [HNOI2008]玩具装箱toy (Accepted)
待会我要打这个玩w。
O(n²) 的做法倒是比较显然，就是一个区间动规，但是这样显然过不去，需要斜率优化。
这题参考这里，说得比较清楚。
说起来我又忘了加long long int。刚才不小心在机房睡着，班主任进来把我叫醒，差点没吓死orz
说起来题解里面也提到了凸包…？
代码里有两个while是用来维护队列的left和right，但是条件不是很懂。
#753A Santa Claus and Candies (Accepted)
轻松愉快的水题。
#753B Interactive Bulls and Cows (Easy) (Accepted)
这是我第一次做交互式题目，想想还有点兴奋呢w
题目大意是这样的，有四个互不相同的数字给你猜，每次反馈是正确位置的数字个数和错误位置的数字个数。
比方说答案是2378，猜2113的话就会得到1/1的结果。
Problem B的确简单，因为你可以猜50次。一个数字一个数字试下去都没问题；或者也可以经由0000 / 1111 / … 来找出四个数字，然后next_permutation搞下去。（我是这么做的）
好了，那么我的问题是，Problem C的Hard限制在7次 — 换句话说，在6次内要算出正解。怎么搞呢？
P1011 [HNOI2008]遥远的行星 (Accepted)
虽然我还是迷迷糊糊的，但是总算来到了HNOI2008的最后一题。
今天好困啊，效率不行。中午还挪出来打稿子了…不过终于一件落着（等等，我好像拖了一个月？那我是不是要开始打下一篇了…）
这题是瞎搞题吧……
需要数的数字在一定以下就暴力算，否则把j全部当成平均值一次算出来……气哭.jpg
P1012 [JSOI2008]最大数maxnumber (Accepted)
简单的线段树模板题，据说还有一些玄学做法？
因为是单点修改所以连lazy都不用打，轻松加愉快。
当初是对着这篇博文学的。

如果不出意外的话，今晚打 Good Bye 2016。
早上吃饭的时候突然对会考感到了不安Orz
P1013 [JSOI2008]球形空间产生器sphere (Accepted)
这题要用高斯消元来做。一开始我还在想怎么解一堆方程orz
自己写了个O(n^2)的算法，显然不对orz
好像还是不太懂（趴）。
参考Wiki写的
P1014 [JSOI2008]火星人prefix (Suspended)
黄学长的题解表示这题是splay维护字符串，然后二分+hash判断。
叶犇表示splay可以先鸽掉……真的没问题吗？
那就咕咕咕咕咕……

昨晚打了比赛，Solve 2 out 8 Orz
Problem B不知道为什么WA掉了。该死的北极熊（。
Problem F明明知道解法，在时限前没打出来，垃圾网络毁我青春（打滚）
心好累……
P1015 [JSOI2008]星球大战starwar (Accepted)
反向并查集。
好像还是不太懂（趴）。

喵喵喵。

感觉会考不妙了啊orz恐怕得开个Page整理文科知识点了……（慌张）
P1016 [JSOI2008]最小生成树计数 (Accepted)
这题用到的性质我大概是没法自己想出来的罢（望天）
大体上的思路我明白了，就是同一张图的最小生成树中，相同边权的边的数量是固定的。所以只要搜索每种边权可能的组合数乘起来就好了。
搜索函数是这样的：
[cpp]
int fu = findSet(e.u), fv = findSet(e.v);
if (fu != fv) {
fa[fu] = fv;
search(id, p + 1, step + 1);
fa[fu] = fu;
fa[fv] = fv;
}
search(id, p + 1, step);
[/cpp]
问题有两个：

1. 为什么不能用路径压缩呢？
2. 回溯的时候为什么是fa[fu] = fu而不是fa[e.u] = fu呢？

第二个问题其实跟第一个一样，因为那么做了就相当于路径压缩。
第一个问题大约是因为路径压缩了就不好回溯到原来的状态了吧。

Day 8 [January 3, 2017]

Day 9 [January 4, 2017]

Day 10 [January 5, 2017]

Day 11 [January 6, 2017]

过一遍这些算法？