A. Lucky Permutation Triple

source code

0到n-1有三个排列a,b,c，若a[i] + b[i] = c[i] (mod n)，则称(a,b,c)为lucky permutation triple，给定n，若方案存在输出任意一个，否则输出-1。

因为a[i] + b[i] = c[i] (mod n)则sigma(a[i]) + sigma(b[i]) = sigma(c[i]) (mod n)，即n*(n-1) = n*(n-1)/2 (mod n)，那么n*(n-1)/2 = 0 (mod n)，可知当n为偶数时使不可能的，所以n只能是奇数，我们有恰好可以构造出n为奇数时的方案：

a	0	1	2	...n-2	n-1		
c	n-2	n-3	n-4	...0	n-1
b	calculate me! & prove it is legal

B. Rectangle Puzzle II

source code

给矩形[0,n]x[0,m]，矩形内有一点P(x,y)，求一个面积最大的矩形[x1,x2]x[y1,y2]包含P且(x2-x1)/(y2-y1)=a/b。若有多解，则选择矩形中心距离P最近的，若还有多解则选择序列x1y1x2y2中字典序最小的。

构造。首先使(a,b)=1，则矩形边长为ak,bk，首先满足面积最大的要求则ak<=n,bk<=n，求出最大的k，这样矩形边长就确定了，然后就是怎么摆的问题了，即要满足距离最小的要求，尽量使长度为ak的线段中心往x靠就行了，在这个基础上尽量使x1,y1小就可以了。

C. Minimum Modular

source code

给一个序列{ai}，找出最小的m使得ai关于m两两不同余，你可以在{ai}中去掉k(<=4)个数以达到目的。

可知M=max{ai}+1满足要求，即m<=M。若ai和aj关于m同余，则m|ai-aj，预处理出所有ai-aj，然后枚举m，看有多少ai-aj整除m，当数目大于k*(k+1)/2时，直接跳出接着测试下一个数。要使集合A={i|存在j属于A使得m|ai-aj}的数目尽量小但是造成m|ai-aj的影响尽可能大，那么只能是下面的情况x1,x2,…xk,x(k+1)，m|xi-x(i-1)，这样构成的(i,j)对共有1+2+…+k=k(k+1)/2。当通过这个测试时然后暴力检测m就可以了。

D. Rotatable Number

source code

给定数字长度n，和数制上限x找出最大的数制b<x，使得存在一个长度为n的Cylic Number。

cyclic number形式为(b^(p-1)-1)/p，p为素数,(b,p)=1，且b为模p的原根。那么首先n=p-1，即n+1要为素数，然后暴力枚举b直到b为一个模p的原根就可以了。

E. Random Ranking

source code

一场比赛选手i的比赛成绩均匀分布在[li,ri]区间，得分越低排名越高，求每个选手i排第j名的概率。

一开始我想预处理出每个选手i排在选手j前面的概率，然后对于每个选手i用p[n][m]表示前n个选手有m个排到i之前的概率，但是后来发现是不对的，因为{rank(x)<i}和{rank(y)<i}不是独立的，比如[0,2],[1,3],[2,4]若1排到2之后，则3肯定在2之后，为了处理这个问题，分区间来讨论。预处理出所有的相邻区间，即(a,b)内不存在其他分点li或ri，这样枚举第i个人处于第k个分数区间，p[n][m]表示当前有n个人的分数在这个区间之前，m个人的分数也在这个区间之内的概率，那么第i个人排到第j名的概率为p[n][m]/m，j>=n+1。

Summary

这场比赛时间很好，CST21:00。这场比赛基本上一直在搞B，一开始思考错方向，后来醒悟过来是构造，但是sample2过不了，看了好长时间还是觉得自己的解更优，后来问了judge才发现面积最大的条件漏掉了，改了之后又wa了三次，有一次还是代码复制的时候出错的，最后过pretest的时候已经只有100来分了。。写B最后太急了，至少后两次wa应该都是可以避免的，冷静啊冷静。后来20min就乱搞C，后来发现果然使乱搞，太急了，连同余最基本的等价条件都不能够想到。C和D虽然都会写，但是复杂度方面还是不太会搞啊，D直接从10^9暴搜啊，原根是怎么分布的啊。啊啊啊，数学弱爆了啊。

A. Yaroslav and Sequence

source code

给定一个2n-1长度的数列，可以选取这个数列中的n个数然后取其相反数，这样的操作不限次数。问这个数列所有元素和最大可能是多少。

比如头两次选取重复的部分的长度为L，那么两次操作后改变符号的元素为2(n-L)个，若能使2(n-L)=n+1，那么接下来在做一次操作，便可以达到只改变一个元素的效果，此时L=(n-1)/2，只有当n为奇数的时候才有可能，当n为偶数时能够改变的最小元素个数为2，因为假若经过若干次变换达到了只改变一个元素的效果，考虑不变量，假设每操作一个元素那么加1，则操作k次后的和为kn。那么考虑只有一个元素改变的情况，其他元素被操作的次数为偶数，于是总的改变元素的次数为奇数，而kn为偶数，矛盾，所以若干次操作最少也会改变两个元素，且这个界是可以达到的，取L=n/2+1就可以了。

B. Yaroslav and Time

source code

从i到j需要消耗(|xi-xj|+|yi-yj|)*d单位的资源，i可以增加ai单位的资源，但是第二次到i的时候不会重复增加，期间可以购买资源，问从要从1到n最少需要购买多少资源。

由于经过i后不管去向哪里都会增加ai，于是将dis(i,j)可以看作ij曼哈顿距离乘以d减去ai，然后正常求最短路就可以了。

C. Yaroslav and Algorithm

source code

有这样一个算法A：

1. A接受一个字符串a为输入
2. A包含了一些命令。命令i要么为si>>wi，或者si<>wi，si和wi是长度不大于7的字符串，包含数字和'?'
3. 每一次迭代过程中，A找到最小的一个索引i，使得si是a中的一个子串。若没有找到则算法结束
4. 用k表示每次迭代找到的命令，将a中si用wi代替，若为>>则继续迭代，若为<>则算法结束
5. 算法结束后的a作为A的输出

现在给定n（<=100）个数字，要求每个数字经过算法A后都加一。要求输出一系列的命令构成算法A完成要求，其中对A有如下限制：

1. 每一个命令都是合法的
2. 命令总数不能超过50
3. 算法会将每个输入的数字加一
4. 对于每个数字迭代次数不能超过200

很直接的想法就是对于每个输入x<>x+1，然而由于输入有100个，而命令不能超过50，所以这样是不可以的，于是需要想一个适用于所有数字的命令而不是针对特定数字的。

需要用’?’来完成要求，以123来举例，我们首先可以随便找一个数，比如找到了1，将1变为1?，则123->1?23，然后不断的将?后移变为123?，然后将3?变为4就可以了，比较麻烦的是需要进位的情况，这样就需要往前处理，比如99变为99?后我们可以将9?变为9??，此时99->99??，然后99??->9??0->??00->100。

D. Yaroslav and Divisors

source code

给定一个大小为n（<=200000）的数组p，p为1-n的一个排列，然后有m（<=200000）个查询l，r，问在p[l..r]中满足pi整数pj的数对ij有多少。

对于每个i在1-n中i的倍数为n/i个，则共有n/1+n/2+…+n/n=nln(n)个满足整除关系的点对，按数组索引预处理出这样的点对，比如对索引i，找出所有的j<=i使得p[j]整除p[i]或p[i]整除p[j]。然后从p左侧开始扫描，引入计数数组c，当扫描到i时，对于区间[1,j]中的每个k，c[k]+=1，则对于查询[l,i]的结果即c[l]。

E. Yaroslav and Arrangements

source code

定义good array {an}为：

1. a1 = min{an}
2. |a1 - a2| = 1, |a2 - a3| = 1, ..., |a(n-1) - an| = 1, |an - a1| = 1

定义great array {br}为：

1. b1 <= b2 <= ... <= br
2. 1 <= r <= n, 1 <= bi <= m
3. {br}的所有排列中有t个good array，且 1 <= t <= k

给定n，m，k求{br}的个数

考虑下goodarray有什么性质。首先若{an}good，则{an-a1}good，所以我们可以固定最小元为0。设x=min{an},y=max{an}，那么y-x<=n/2（利用这个可以降低这一维的长度），这是因为假若y太大，就不能构成环了，基于同样的原因，[x,y]之间的每个数在{an}中都必须出现，否则会出现断层。其次n为偶数，这是由于a1-an=(a1-a2)+(a2-a3)+(a(n-1)-an)，即a1-an为n-1个1或-1的和，即a1-an于n-1奇偶性相同，而a1-an为奇数，所以n为偶数，这样dp的时候这个维的长度可以减半，这个在具体推导转移方程的时候也可以看出来。最后考虑y的周围两个数，因为y最大，所以y的两侧只能是y-1，这样可以发现如下规律

0 1 2 1 0 1 0 1 2 1 => 0 (1 2 1) 0 1 0 (1 2 1) => 0 1 0 1 0 1

即可以把(y-1 y y-1)看作y-1，则会构成一个最小值为x最大值为y-1且规模更小的good array，这样就可以适用动态规划了。我们逐个添加元素，需要记录当前处理的元素，当前array大小，当前元素选了多少个，所有排列中有多少great array。如果当前元素i有y个，可见至少需要i-1 x+y个，共有C(x+y-1,x)种选法，然后枚举当前元素选多少个更新就可以了。

Summary

这场由于技术原因最后是unrated，momo作者。正准备写B的时候A被hack了，检查了半天最后发现数组开小了，改完之后就直接睡了，以后要多注意啊。C是一道很好玩的题目，E的dp也很好，最后还是要momo作者。

A. Parity Game

source code

有两个01串a和b，对于a有两种操作，a->a[1..-1]和a->a+parity(a)，问能否通过这两种操作使a变为b。

考察操作中的不变量，可以看到，a中1的个数是确定的，如果a中1的个数为偶数，那么两种操作均不会增加1，如果为奇数，那么1的个数之多智能增加1，对于parity操作0是可以随意添加的，于是只要a中最多能有的1的个数不比b少，那么a均可以变为b。

B. Fish Weight

source code

去掉背景，就是问对于给定的$\sum_{i=1}^{k}b_iw_i$和$\sum_{i=1}^{k}c_iw_i$，$0<w_1\le w_2\le ...\le w_n$，能否有{wi}的一个分配方案使得使第一个式子严格大于第二个。

首先用第一个式子减第二个，令$a_i=b_i-c_i$，得到$X=\sum_{i=1}^{k}a_iw_i$，问X是否可以严格大于0。可以发现，如果an>0，那么使wn趋于无穷大，总可以使X>0，那么当an<0时，我们肯定要使anwn造成的影响最小，那么要使wn最小，根据条件可以知道，wn最小为w[n-1]，于是w[n-1]系数变为a[n]+a[n-1]，规模化为n-1的原问题，如此一直向前，如果存在某个系数>0，那么可知分配方案是存在的，否则无解。

C. Splitting the Uniqueness

source code

有一个数列{si}，对于每个si可以分解为si=ai+bi，于是由{si}可以生成两个数列{ai},{bi}。现在定义almost unique的数列为之多去掉ceil(n/3)项可以使数列项两两不同的数列，问是否存在si的一个分法，使得{ai}{bi}almost unique。其中si,ai,bi>=0，且si两两不同。

不妨设s1<s2<…<sn。假设一个数列{xn}中不同元素的个数为k，于是要使{x}unique，至少要去掉n-k个元素，于是almost unique的数列中不同元素的个数至少为n-ceil[n/3]。如果{si}分布很稀疏的话，比如s[i+1]-s[i]>=2，那么只要让a[i]=i,b[i]=s[i]-i就可以了，因为s[i]各不相等，所以b[i+1]>[i]，于是只要集中精力考虑{si}很密集的情况就可以了，比如{si}={1,2,…,n}。可以有以下的分法：

s: 1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9
a: 1 2 3 0 0 0 4 5 6 	1 0 3 1 4 2 5 3 6
b: 0 0 0 4 5 6 1 2 3	0 2 0 3 1 4 2 5 3

两种分法都是可以的。

D. Color the Carpet

source code

给一个h*w的方格，然后用k种颜色给这个方格染色，给出相邻单元格颜色之间的关系(相同和不相同)，问是否存在一个染色方案使得至少满足3/4的颜色关系。

首先共有T=w(h-1)+h(w-1)个约束关系。假若k=1，那么只有一种染色方案，直接判断就可以了，如果k>1，接下来说明这种方案总是存在的。只需构造出k=2的方案。首先将第一行染色，满足第一行的行关系，然后染第二行，使得满足第二行的行关系，现在比较第一行和第二行之间不满足的列关系个数，记为c，如果c<=w/2，那么继续，否则交换第二行的两种颜色，可知第二行的行关系依然满足，但是列关系不满足的个数变为w-c<=w/2，如此继续直到最后一行。那么不满足的关系至多为S=w/2*(h-1)，如果h>=w，则可知S/T<=1/4，如果h<w，那么先染列就可以了。

E. Mystic Carvings

source code

略去题目背景，最后问题转化为要高效查询一个区间内有多少个完整区间，并且区间是在环上的。

首先考虑一条直线的情形，假设区间集合为{ai,bi}，按bi递增排序，那么当处理到第k个区间[ak,bk]时，前面的所有区间[ai,bi]都会有bi<bk，于是只需查询有多少ai>ak，可以用树状数组或线段树来记录ai，每处理完一个区间后在ai处加1就可以了。

然后考虑环的情况，将整个大区间扩成两倍长即可，于是以前的区间[a,b]可以变为[b,a+n],[a+n,b+n]，可以看到对于两个区间[a,b]和[x,y]，[x,y]只能包含于[a,b]和[b,a+n]中的一个，于是环的情况也解决了。

题目具体的分解转化可以看官方Tutorial。

Summary

A完全考虑错了方向，但是居然过了pretest，pretest也太弱了，B比较顺利，C比较侥幸。这应该是典型的需要”Do More Thinking Than Coding”的比赛，差不多都需要去充分挖掘题目条件给特定问题带来哪些特点和便利，观察啊观察，从反面考虑啊，神奇的构造啊，啊啊啊，弱爆了弱爆了。

A. Greg and Array

source code

一个数组a，有一些系列操作l,r,d，给a[l..r]中的每个数加d，现在有一系列询问x,y，表示执行操作x..y。输出所有询问后的数组。

每个操作l,r,d可以看作a[l]+=d,a[r+1]-=d，于是a[i]的大小即sum[1..i]，询问x,y可以看作操作x,y,1，只不过对应的是操作数组。

B. Greg and Graph

source code

给一个500个点的有向图，现在按给定顺序依此去除一个点，每次去点时输出所有点对最短路的和。

采用Floyd，按照去除点列的逆序一次加一个点。

C. Greg and Friends

source code

过河问题，但是人的重量只有50和100两种，人数为50。现在查询最少需要几步使得所有人到达对岸，在最少的情况下有多少中乘船方案。

记录50的人数a，100的人数b，现在是要过对岸还是返程turn，bfs一遍(a,b,turn)，更新最短路，并且计数。

D. Greg and Caves

source code

nxm的矩形方阵，存在这么一些行[l..r]，每一行只有两个格子是黑色，存在t，对于[l..t]的行，第i行的以黑色块为端点构成的线段包含在i+1行对应的线段内，[t..r]内刚好相反，i+1包含在i内。求所有染色方案数。

如果以t为分界的话，那么上面是一个类似三角的图形，下面是一个倒三角，所以只需计算形成三角形的方案数。设f(i,j)表示三角形第i层长度为j的方案数，那么第i-1层的长度可以有2..j种，i-1层长度为k包含在长度为j的线段上的方案数为j-k+1，于是可以得到递推关系:

$$f(i,j)=\sum_{k=2}^{j}f(i-1,k)*(j-k+1)$$

化简得到：

$$f(i,j)=2f(i,j-1)-f(i,j-2)+f(i-1,j)$$

接下来就可以枚举t，和第t行的长度k。这里t需要做一个确切的定义，取最后一个使[l..t]“递增”的t，即t+1相对于t是严格减小的。于是对应一个(t,k)枚举上三角的高度和下三角的高度就可以了。对于一个高度为h，最后一行长度为k，倒数第二行严格小与最后一行的方案数为f(h,k)-f(h,k-1)。

那么上三角总数为

$$A(t,k)=\sum_{i=0}^{k}f(1,i)$$

下三角总数为

$$B(t,k)=\sum_{i=2}^{n-t+1}(f(i,k)-f(i-1,k))+f(1,k)=f(n-t+1,k)$$

第t行长度为k共有m-k+1排法，于是最后的方案总数为：

$$T(n,m)=\sum_{t=1}^{n}\sum_{k=2}^{m}(A(t,k)*B(t,k)*(m-k+1))$$

E. Yaroslav and Points

source code

有一个数列{xi}，现在有一个操作i,pi,di，表示x[pi]=x[pi]+di，有一系列查询l，r表示查询位于区间[l,r]内的xi的两两差的和，即$\sum_{l\le x_i\le xj\le r}(x_j-x_i)$。

具体做法是线段树，所查询的和可以由两个部分合并，每个区段需要保留三个参数，该区间内数的多少，数的和，和该区间内的两两差的和。

Summary

A比较顺利，B一开始将500看成5000了，想不出来，后来仔细一看发现是500，赶紧按floyd写了一遍，提交wa，后来又wa了两次，在还剩30min的时候过掉，当时没有想清楚就直接写然后交了，以后一定要先想清楚，否则真是得不偿失啊。后来看C，虽然可以做，但是实在没有20min写对的实力，如果B过的快一点，C还是有可能的。很不扎实啊，尤其是B的floyd。啊啊啊，弱爆了弱爆了。

这两天连续碰到单调队列/栈的问题，稍微总结一下。

单调队列/栈即在队列/栈的基础上加上单调。其中每个元素进出各一次，所以复杂度一般是O(n)。单调队列实际上是一个双端队列，队列头删除元素，队列尾添加元素。比较典型的应用是k窗口问题，即一个数列{xi}，用一个长度为k的窗口从左向右扫描，每次都查询当前窗口中的最大元素。

采用单调递减队列，即队列头总是最大元，有新的元素加入时，总是从队尾开始扫描，直到遇到第一个比自己大的，然后插入队尾。窗口每移动一格，从队头开始去除旧元素。可以看出，单调队列里不仅值是单调的，索引也是单调的，即队尾总是最新的。

这个可以用于一类如f[x]=max{g(k)|b[x]<=k<x}+w[x]的问题，其中b[x]不减。如果j<k，并且g(j)<g(k)，那么g(j)就可以被舍弃，因为b[x]单调不减，而g(j)又没有g(k)优，它已经不可能再影响以后的状态了。感觉有些长江后浪推前浪，前浪死在沙滩上的感觉。。比如k窗口问题中k=3，x={3,5,6,2,7}，扫描到6时，比5优，于是便可以舍弃5了，因为以后包含5的窗口肯定会包含6，而5又没有6优。

单调栈感觉就是没有删除操作的单调队列，比较典型的是ZOJ 1985 Largest Rectangle in a Histogram，用于求每个元素两侧第一个比自己大的。

下面是这两天在Codeforces中遇到的一些题目。

Maximum Xor Secondary

source code

有一个数列{xi}到整数的映射f：{xi}中第一大和第二大元素的异或值。现在给定数列{xi}，求max{f(x[L..R])}。

直接求的话，只枚举所有子列就需要n^2，复杂度太高，然而可以发现有很多区间是不用判断的。可以采用单调递增栈，即栈顶总是当前最小的（不是所有元素里最小的），设栈为stack[sz]，那么stack[sz-1]为左边第一个比stack[sz]大的元素，于是只需要计算stack[sz-1]^stack[sz]。当有新的元素x，只需要不断扫描栈，直到遇到第一个比x的元素即可。

Bindian Signalizing

source code

一个圆上有一圈数{xi}，一个合法的数对(i,j)为在至少有一条连接i，j的弧中的所有数都不大于xi和xj，求合法数对的个数。

首先将最大元循环移动放到第一个元素，这样就基本将圈变成了链。单调递增栈，栈里维护了最左端第一个比当前元素大的元素。在更新的时候pop了几次，最后结果就要加几次。比如5 1 4 1 3 6，当前元素为2，首先6找到3，然后比3大的第一个元素为4，比4大的第一个为5，于是(5,6)(4,6)(3,6)都是合法的。具体处理的时候还要注意元素相等的情况和逆向可以到达第一个元素的情况。

Exposition

source code

有一个数列{xi}，设映射f: array x -> y=max{x}-min{x}，求max{L-R|f(x[L..R])<=k}。

类似与k窗口，需要维护一个区段的最大值和最小值，采用两个单调队列，一个维护最大值，一个维护最小值。

A. Polo the Penguin and Strings

source code

有这样一种字符串，它只含有k个不同的字母，长度为n，并且相邻字符不相同。给定n和k，输出字典序最小的那个，不存在的话输出-1。

首先考虑不存在的情况，即不能满足相邻字符不相同，或不够k个字符，即n>&&1k=1和k>n的情况。存在的情况下，由于要求字典序最小所以贪心使用ab的重叠就好了。

B. Polo the Penguin and Houses

source code

有n个房子编号1-n，每个房子有一个门牌号(1-n)，房子x的门牌号记为Px，注意门牌号是可以重复的，当你到房子x时，下一步到Px，然后到P(Px)…，现在已知：

1. 从1-k出发，都会回到1
2. 从k+1-n出发，都不会回到1
3. 从1出发，经过非0步回到1

现在给定n，k，确定有多少种门牌号编排方案。其中k<=8。

由条件知，从1-k出发都不可能到达k+1-n，从k+1-n出发也不可能到1-k。于是由于k的范围很小，可以暴力出1-k的方案数。k+1-n为(n-k)^(n-k)种，然后乘起来就好了。

C. Polo the Penguin and XOR operation

source code

0-n这n+1个数有一个排列{pi}，对于每一个排列对应一个数值p=(0^p0)+(1^p1)+…+(n^pn)，求p的最大值。

采用贪心。对于每个数x，去掉x的二进制最高位后，然后取反得到x’，则x’<x，使得x^x’最大。即对于任何一个x都存在一个x’<x与之对应，并且这种对应是唯一的，即不会有x!=y，而x’=y’，于是从n开始倒序搜索，总可以进行这样的匹配。

D. Polo the Penguin and Trees

source code

给一棵树，查询这样元组(a,b,c,d)的个数，其中a<b,c<d，并且a和b的最短路与c和d的最短路没有公共节点。

从反面考虑，不考虑条件，所有元组的个数为C(n,2)^2，然后去除最短路有公共点的元组。若公共点为x，则最短路经过x的点对有两种：

1. a和b分别在x的两个儿子形成的子树中
2. a在x为根的子树中，b在除x子树的剩余节点中

a和b都在除x子树的剩余节点是不行的，这样最短路肯定不会通过x了。这样的话只需要dfs一遍就可以了。

E. Polo the Penguin and Lucky Numbers

source code

lucky number是十进制位只含有4和7的数，现在给定一个区间[l,r]，其中l和r都是lucky number，位于[l,r]之内的lucky number为{ai}，求a1a2+a2a3+…+a(n-1)an。

采用dp解决，从高位向低位扫描。只需要计算[44..4,l]和[44..4,r]的结果就可了，然后二者相减就得到了结果。比如[444,747]，观察如下图表，每一次的{ai}，对应到下一次为{10ai+4,10ai+7}，只有最后一个an有所区别，有可能没有10an+7。

1-----2------3

       /-- 444
   - 44 -- 447
  /    /-- 474
4 -- 47 -- 477
       /-- 744
7 -- 74 -- 747

看到这样的关系后就可以写转移方程了，设F[n]为题目所求，K[n]为当前数{ai}的多少，比如上图中K[1]=1,K[2]=3,K[3]=6。

$$\begin{align*} & F_{n+1} = \sum_{i=1}^{K_n-1}(10a_i+4)(10a_i+7) + \sum_{i=1}^{K_n-1}(10a_i+7)(10a_{i+1}+4) \\ & F_{n+1} = 100F_n+100\sum_{i=1}^{K_n-1}a_i^2 + 220\sum_{i=1}^{K_n-1}a_i+56(K_n-1)+70(a_{K_n}-a_1) \\ \end{align*}$$

上面是对于当前处理字符为4的情况，7的情况只需要再加上最后一项$(10a_{K_n}+4)(10a_{K_n}+7)$即可，然后可以设

$$S_n = \sum_{i=1}^{K_n-1}a_i, \quad T_n = \sum_{i=1}^{K_n-1}a_i^2$$

求出对应的递推关系，就可以了。

Summary

A，B，C较以往的比赛难度并不算太高，算是比较幸运的在一个小时内1y了前三题，后面一个小时就打酱油了，还是缺乏砍难题的能力啊，啊啊啊，弱爆了弱爆了。

D比赛的时候走偏了，我首先去计算没有公共节点的元组，然后再在这些元组中去去重，始终想不到好的方法，加上自己也确实缺少能够搞定D的信心，后面也就没有再深入去想了。如果开始从更大的角度从反面考虑的话，或许会有一些想法。啊啊，以后做题一定要霸气啊，管他ABCDE，嗯嗯。还有就是要从更多角度去思考问题，但是很多时候真的找不到合适的角度诶，要多做题，多看大牛代码，多看大牛文章。

E花了一天终于搞定了，略兴奋。主要是要发现前后ai之间的关系，然后就只剩下一些计算了。

稍微总结下gentoo下常用的一些软件。

Emerge

emerge是使用portage的一个工具。

• 查询emerge相关选项的含义

  $ man emerge
  

• 更新portage树

  # 使用rsnyc
  $ emerge --sync
  # rsync不能用时，使用gentoo每天的portage快照
  $ emerge-webrsync
  

• 查询软件

  # 搜索所有名字里包含pdf的包
  $ emerge --search pdf
  # 在包描述里查询关键字
  $ emerge --searchdesc pdf
  # 或
  $ emerge -S pdf
  

  当然还有更好更快的方法，这个在后面会提到。

• 安装软件

  # 安装gnumeric
  $ emerge gunmeric
  # 假装安装软件。在你不确定这个软件都要装哪些包时，可以用这个命令
  $ emerge --pretend gnumeric
  # 只下载源码，可在/usr/portage/distfiles目录下找到
  $ emerge --fetchonly gnumeric
  

• 查找已安装包文档

  doc USE决定了包文档是否被安装

  # 以alsa-lib为例
  $ emerge -vp alsa-lib
  [ebuild  N    ] media-libs/alsa-lib-1.0.14_rc1  -debug +doc 698 kB
  

  后面会提到有更好的工具。

• 删除软件

  # 删除gnumeric
  $ emerge -unmerge gnumeric
  

• 更新系统

  # 更新系统
  $ emerge --update --ask world
  # 更新依赖。否则只会更新列在/var/lib/portage/world里的软件
  $ emerge --update --deep world
  # 上面的命令还是没有更新全部包，因为在装某个软件时，只有在编译时依赖，而在编译完后就不再需要了。
  $ emerge --update --deep --with-bdeps=y world # bdeps = build dependencies
  # 如果USE标记有改变
  $ emerge --update --deep --with-bdeps=y --newuse world
  
  # 更新整个系统的话，一般执行以下的命令
  $ emerge --sync
  $ emerge -avuND world
  $ revdep-rebuild # from gentoolkit
  

• 一些标记

  更新系统或装软件时经常会看到一些字母，或者不同的颜色，这些都是有自己特定的意义的

  State flags

  B 被已安装的包拦截（阻挡？block怎么翻译比较好= =）
  b 被已安装的包拦截（但是冲突会自动解决）
  I 交互式包安装（需要用户输入）
  N 新的包，未安装
  S 安装到一个新的slot（怎么翻。。）
  D 降级到一个老版本（downgrade）
  U 升级到一个新版本（upgrage）
  R 重新安装相同的版本，很可能时由于新的USE标记或有标记被移除
  F 下载受限，必须手动下载（比如oracle java诶，要点I agree啊。。）
  f 已经下载过啦（nothing to do，yay）
  r 重新安装（很可能是slot或sub-slot的问题）
  

  USE flags

  未被高亮的USE是不变或启用
  USE（黄绿蓝）前的减号（-）表示该标记被禁用
  USE后的百分号（%）标志着新加入或被移除，和yellow一样
  USE后的星号（*）表示它的意义/域有所改变，和green一样
  USE两侧的括号()表示它当前被屏蔽（可能由于当前的平台不支持此标记）
  

  Color

  red USE被启用或不变
  yellow USE被添加，移除或屏蔽
  green USE自从上次安装后被改变了，和（*）已一样
  blue USE被禁用，和减号（-）一样
  

• 安装软件again

  不能成功安装时请仔细查看emerge输出，添加相应的内容到/etc/portage/的package.keywords,package.license,package.mask,package.unmask,package.use等文件。

Gentoolkit

这是其他发行版不存在的一个工具，可以说它在一定程度上代表了Gentoo，位于app-portage/gentoolkit。看到kit应该就知道了，这其实是一个工具包，而不是一个单一的软件。接下来一个一个介绍。

• 安装

  emerge gentoolkit
  

• equery

  equery用来显示系统上包的信息。可以使用equery --help列出相关选项，更详细的可以man equery

  # 查找一个文件来自哪个包
  $ equery belongs /usr/bin/xmms
  [ Searching for file(s) /usr/bin/xmms in *... ]
  media-sound/xmms-1.2.10-r9 (/usr/bin/xmms)
  # 使用-f，可以使用正则表达式，使用-e可以在找到一个匹配后立刻终止
  	
  # 检查包的完整性
  # 检查md5和时间戳来检查一个可能被冲突，替换或移除的包
  $ equery check gentoolkit
  [ Checking app-portage/gentoolkit-0.2.0 ]
   * 54 out of 54 files good
  # 配置文件改变可能被认为not good
  
  # 依赖
  # equery可以用来查询一个包的直接依赖
  $ equery depends pygtk
  [ Searching for packages depending on pygtk... ]
  app-office/dia-0.93
  dev-python/gnome-python-2.0.0-r1
  gnome-extra/gdesklets-core-0.26.2
  media-gfx/gimp-2.0.4
  x11-libs/vte-0.11.11-r1
  # equery可以查询一个特定包的依赖图
  $ equery depgraph cdrtools
  
  # 查询属于一个ebuild的文件
  $ equery files gentookit
  
  # 查找使用特定USE标记的包
  $ equery hasuse mozilla
  
  # 列出包
  $ equery list gentoolkit
  
  # 计算包大小
  $ equery size openoffice-bin
  
  # 特定包的USE
  $ equery uses ethereal
  
  # 查找ebuild位置
  $ equery which cdrtools
  

• euse

  euse用来列出，启用或禁用USE标记。

  # 获取当前活动的USE标记
  $ euse -a
  
  # 启用USE标记
  $ euse -E 3dfx # /etc/make.conf会被改变，备份为/etc/make.conf.euse_backup
  
  # 禁用USE标记
  $ euse -D 3dfx
  

• glsa-check

  glsa-check主要用来跟踪GLSA’s（Gentoo Linux Security Advisory）。

  # 列出未被应用的GLSAs
  $ glsa-check --list
  
  # 特定GLSAs的信息
  $ glsa-check --dump 200812-20
  
  # 测试特定GLSAs的易碎性
  $ glsa-check --test 200812-20
  
  # 自动应用GLSAs
  $ glsa-check --fix 200901-15
  

• revdep-rebuild

  Gentoo的一个反向依赖重建工具。经常在系统更新完后运行此命令。

  # pretend mode
  $ revdep-rebuild -p
  # normal mode
  $ revdep-rebuild
  

• eread

  显示portage的elog文件。可以在makefile里设置保存的elog文件的相关变量。

  # file location: /etc/make.conf
  PORTAGE_ELOG_GLASSES="log"
  PORTAGE_ELOG_SYSTEM="save"
  

  一旦设置好后，运行eread就可以了。

• eclean

  eclean用来移除陈旧的源码和二进制文件。

Portage-utils

Portage-utils提供了一组快速的工具，但是相对gentoolkit在功能上有所限制，这也是由于追求速度所牺牲的。

• 安装

  emerge portage-utils
  

• 使用

  # qfile找到一个文件属于哪个包
  $ qfile /etc/fonts/fonts.conf
  
  # qcheck检查包的完整性
  $ qcheck portage-utils
  
  # qdepends列出包依赖
  $ qdepends -a pygtk
  
  # qlist列出属于某个ebuild的文件
  $ qlist vim
  
  # quse查找包的USE标记
  $ quse firefox
  
  # qsize查询包大小
  $ qsize vim
  
  # qsearch查找portage树
  $ qsearch terminus
  $ qsearch -H terminus # terminus作者的主页是啥？
  $ qsearch -S "jabber client" # 需要一个jabber clinet？
  
  # qlop查询emerge log信息
  $ qlop -tH perl # 装perl大概要多长时间
  $ qlop -c # 看看emerge现在在干什么^_^
  

Eix

快速查找portage树。我现在基本都用eix来查找。

• 安装

  emerge eix
  

• 更新缓存

  $ eix-update
  $ eix-sync # will run emerge --sync first
  

• 使用

  $ eix --help
  $ eix emer # 查询名字里有emer的包
  $ eix -C app-portage emer # 在给定类型里查找
  $ eix -I -C app-portage porta # 查询已安装的包
  $ eix -S description # 查找包描述
  $ eix -S -c corba # 查找包描述并且打印完整的列表
  $ eix-remote update # 更新overlay缓存
  $ eix-test-obsolete -c -b # 陈旧和遗失包查询
  

Layman

用来管理overlays的工具。

• 安装

  emerge layman
  

• 配置

  (for layman 1.1)
  $ echo "source /usr/portage/local/layman/make.conf" >> /etc/make.conf
  
  (for layman 1.2)
  $ echo "source /usr/local/portage/layman/make.conf" >> /etc/make.conf
  
  (for layman 1.3 and later)
  $ echo "source /var/lib/layman/make.conf" >> /etc/make.conf
  

• 使用

  # 列出可用overlays
  $ layman -L
  
  # 安装一个overlay
  $ layman -a <overlay-name>
  
  # 更新overlay
  $ layman -S
  

References

• A Portage Introduction
• Gentoo Portage Wiki
• Portage Wikipedia
• Gentoolkit
• Portage-Utils
• Eix Homepage
• Gentoo Overlays

A. Lucky Permutation

source code

判定是否存在一个置换使得一个序列经过两次相同的置换达到逆序。

考虑若P(x)=y，则由于P(P(x))=n-x+1，则P(y)=n-x+1，即P(x)=y => P(y)=n-x+1，连续应用此式可以得到

P(x) = y
P(y) = n - x + 1
P(n - x + 1) = n - y + 1
P(n - y + 1) = x

即4个构成一组，于是当n%4=0或1时存在解，否则不存在。

不知道为什么，感觉有点像密码学里的Meet-In-The-Middle

B. Shifting

source code

对于一个序列{pi}，定义操作f(p,k)为将序列按k个分为一组，最后一组若不够分，则含有n%k个元素，然后对于每一个小组循环左移。问f(f(…f(p=[1,2,…,n],2)…,n-1),n)是多少。

对于每一个k，共进行n/k次循环左移，共有n(1/2+1/3+…+1/n)=nln(n)次循环左移，只需要将每次循环左移复杂度降到O(1)就可以了。比如f([1..9], 3)：

1 2 3 4 5 6 7 8 9 =>
2 3 1 5 6 3 8 9 7
将被移动的字符看作*，于是：
* 2 3 * 5 6 * 8 9
  2 3 * 5 6 * 8 9 *
这样就可以将左移变为O(1)了

C. Main Sequence

source code

定义一个正确的括号序列为：

1. 空序列为括号序列
2. 若{a1, a2, ..., al}和{b1, b2, ..., bk}是括号序列，则{a1, a2, ..., al, b1, b2, ..., bk}也是括号序列
3. 若{a1, a2, ..., al}是括号序列，则{v, a1, a2, ..., al, -v}是括号序列，v是一个正整数

现在有一个括号序列{xi}，已知{pi=|xi|}，和{i|xi<0}的一个子集，问是否可以还原{xi}，若存在多解，任意输出一个，否则输出NO。

和正常的括号匹配差不多，因为要求了某些必须取负数，即相当于有括号，所以从右向左压栈，然后正常的匹配就可以了。

D. Tourists

source code

在(-1,0)和(1,0)处有两个人同时沿Oy正方向运动，每秒运动一个单位，现在在某个时刻t会出现(0,a)-(0,b)这样一堵墙，若此时两个人正好位于Oy的[a,b]之间那么这两个人就互相看不见对方，现在给出所有这样的(a,b,t)三元组，还有从q1，q2…时刻出发的人，查询每对人有多长时间是看不到对方的。(a,b,t,qi>=0)

以时间t为自变量，纵坐标为应变量，用x表示，那么对于从时间t出发的人对应的关系为x=t-q（更精确的应该为x=max(0,t-q)，然而因为墙壁不会出现在负轴，所以写成这样对结果没有影响），对于每个墙壁(a,b,t)，关系为x=a,t=t与x=b,t=t之间的带状区域，可以看到被挡到的时间为x=t-q被带状区域所截取的线段的横截距，因为斜率为1，所以也等于纵截距。为了便于判断相交和计算做坐标变换(t,x)=>(t-x,x)，那么人的方程变为t=q，是一条垂直于横轴的直线,带状区域变为左顶角为PI/4的梯形，此时所求即为直线和这个梯形交集的纵截距，也等于q-t（t为梯形最左点的横坐标）可以将梯形看作两个PI/4的角的交，只是在计算的时候下面的角是被减掉的，如果处理出所有这样的角的话，就很容易计算了。比如q和ti(0<=i<k)相交，那么最后所求为sigma(q-ti)=k*q-sigma(ti)，这样只需要处理出ti前缀和，最后二分就可以了。处理角的过程是将所有带状区域的上下边界统一排序，并且维护当前所有线对应的出现时间的最小值，用堆就可以了，当处理到某个区域的下界的时候，这个区域对应的时间t要出堆，依次处理就可以了。

E. Ladies’ Shop

source code

有一些背包，只能够装重量为ai的物品，不能多也不能少，现在有一些物品，但是重量还没有确定，现在让你确定重量1<=p1<p2<…<pk满足下列条件（每个重量的物品有无穷多个）

1. 每个包都会被用到。即对于每一个i都存在一些物品它们的总重量为ai
2. 对于任何不超过m的重量的物品，必须有一个包可以放置它
3. 对于满足1和2的重量分配，使k最小化

题目意思就是说对于物品{pi}它们的任意不大于m的组合都能在{ai}中找到，比较直接的做法就是无限背包作出所有不大于m的重量，然后去和{ai}比较，但是n,m=10^6，这样会超时，首先，所有重量肯定是{ai}的一个子集，否则就会不满足条件2，其次，加入{pi}是一个满足条件的重量分配，对于每一个i，pi,2pi,3pi…tpi<=m都应该有包对应，即总存在某个j使得aj=x*pi，于是要找出所有组合只需要将{ai}中的任意两个相加就可以判断出{pi}的所有组合了，将{ai}看作一个数，它的平方即为任意两个的和，于是可以用FFT做了，采用[Cooley–Tukey FFT algorithm]（这个算法于1965年提出，实际上只是重新发现了Gauss在1805年提出的算法，orz）。假若平方封闭，那么便是可以分配，否则不存在方案，要最小化k，只需要选那些最小的元，即所有其他的重量里没有它的因子。

Summary

弱爆了啊。42min才搞出A，然后一直再搞B，其实应该多看下C的，最后15min看了C，就感觉很可搞，可惜时间不多了，情急之下居然把statck写成queue了，赛后稍微调了一下就过了。这次还是出现了会做的题目在比赛中没有做出来的情况>_<。B还是该早些放弃的，D和E压根就没有读题，以后至少要将每道题目都读一遍，至于会不会做就是另外一回事了。啊啊啊，弱爆了弱爆了。

终于fix了D和E，D首先要用数学的语言去描述题目场景，那个坐标变换太神了。E首先要从题目条件判断出重量是{ai}的子集，然后就要看能不能联想到FFT了。啊啊啊，弱爆了弱爆了。

安装和初始化

• 配置全局用户名和电子邮件地址

  $ git config --global user.name "Your Name"
  $ git config --global user.email "you@example.com"
  

• 为特定的版本库配置用户名和电子邮件地址

  $ cd /path/to/repo
  $ git config user.name "Your name"
  $ git config user.email "you@example.com"
  

• 在命令行中使用不同颜色显示不同内容

  $ git config --global color.ui "auto"
  

• 初始化版本库

  $ mkdir /path/to/repo
  $ cd /path/to/repo
  $ git init
  Initialized empty Git repository in /path/to/repo/.git/
  $
  ... create file(s) for first commit ...
  $ git add .
  $ git commit -m 'initial import'
  Create initial commit bdebe5c: initial import
   1 files changed, 1 insertions(+), 0 deletions(-)
   create mode 100644 <some file>
  

• 克隆版本库

  $ git clone <repository url>
  Initialize repo/.git
  Initialize empty Git repository in /work/<remote repository>/.git/
  

• 将目录中的内容纳入Git版本控制

  $ cd /path/to/existing/directory
  $ git init
  Initialized empty Git repository in /path/to/existing/directory/.git/
  $ git add .
  $ git commit -m "initial import of some project"
  

• 在本地版本库中设置远程版本库的别名

  ... from within the repository directory ...
  $ git remote add <remote repository> <repository url>
  

日常操作

• 添加新文件或暂存已有文件上的改动，然后提交

  $ git add <some file>
  $ git commit -m "<some message>"
  

• 暂存已有文件上的部分修改

  $ git add -p [<some file> [<some file> [and so on]]]
  

• 使用交互方式添加文件

  $ git add -i
  

• 暂存已纳入Git版本控制之下的文件的修改

  $ git add -u [<some path> [<some path>]]
  

• 提交已纳入Git版本控制之下的文件的所有修改

  $ git commit -m "<some message>" -a
  

• 清除工作目录树中的修改

  $ git checkout HEAD <some file> [<some file>]
  

• 取消已暂存但尚未提交的修改的暂存标识

  $ git reset HEAD <some file> [<some file>]
  

• 修复上一次提交中的问题

  改动相关文件，并暂存

  $ git commit -m "<some message>" --amend
  

• 修复上一次提交中的问题，并复用上次的提交注释

  $ git commit -C HEAD --amend
  

分支

• 列出本地分支

  $ git branch
  

• 列出远程分支

  $ git branch -r
  

• 列出所有分支

  $ git branch -a
  

• 基于当前分支（的末梢）创建新分支

  $ git branch <new branch>
  

• 检出另一条分支

  $ git checkout <some branch>
  

• 基于当前分支创建新分支，同时检出该分支

  $ git checkout -b <new branch>
  

• 基于另一个起点，创建新分支

  你可以从版本库中任何一个版本开始创建新分支。这个起始点可以用一条已有的分支名称、一个提交名称，或者一个标签名称来表达。

  $ git branch <new branch> <start point>
  

• 创建同名新分支，覆盖已有分支

  $ git branch -f <some existing branch> [<start point>]
  

• 移动或重命名分支

  只有当<new branch>不存在时

  $ git checkout -m <existing branch name> <new branch name>
  

  如果<new branch>已存在，就覆盖它

  $ git checkout -M <existing branch name> <new branch name>
  

• 把另一条分支合并到当前分支

  $ git merge <some branch>
  

• 合并，但不提交

  $ git merge --no-commit <some branch>
  

• 拣选合并，并且提交

  $ git cherry-pick <commit name>
  

• 拣选合并，但不提交

  $ git cherry-pick -n <commit name>
  

• 把一条分支上的内容压合到另一条分支（上的一个提交）

  $ git merge --squash <some branch>
  

• 删除分支

  仅当欲删除的分支已合并到当前分支时

  $ git branch -d <branch to delete>
  

  不论欲删除的分支是否已合并到当前分支

  $ git branch -D <branch to delete>
  

撤销变更

• 反转某个提交

  $ git revert <commit>
  

• 取消已暂存但尚未提交的变更的暂存标识

  $ git reset HEAD <some file>
  

• 删除工作目录树中的变更

  $ git checkout <some file>
  

  # 警告！此操作本身不可撤销！

• 在版本库中撤销已提交的变更，并在工作目录树中清除

  $ git reset --hard HEAD^
  

  # 警告！此操作本身不可撤销！

历史

• 显示全部历史记录

  $ git log
  

• 显示版本历史，以及版本间的内容差异

  $ git log -p
  

• 只显示最近一个提交

  $ git log -1
  

• 显示最近的20个提交，以及版本间的内容差异

  $ git log -20 -p
  

• 显示最近6小时的提交

  $ git log --since="6 hours"
  

• 显示两天之前的提交

  $ git log --before="2 days"
  

• 显示比HEAD（当前检测出分支的末梢）早3个提交的那个提交

  $ git log -1 HEAD~3
  

  或者

  $ git log -1 HEAD^^^
  

  或者

  $ git log -1 HEAD~1^^
  

• 显示两个版本之间的提交

  *下面命令中的和可以是一个提交名称、分支名称、标签名称，或者它们的混合。*

  $ git log <start point>...<end point>
  

• 显示历史，每个提交显示一行，包括提交注释的第一行

  $ git log --pretty=oneline
  

• 显示改动行数统计

  $ git log --stat
  

• 显示改动文件的名称和状态

  $ git log --name-status
  

• 显示当前工作目录树和暂存区间的差别

  $ git diff
  

• 显示暂存区和版本库间的差别

  $ git diff --cached
  

• 显示工作目录树和版本库间的差别

  $ git diff HEAD
  

• 显示工作目录树与版本库中某次提交版本之间的差别

  $ git diff <start point>
  

• 显示版本库中两个版本之间的差别

  $ git diff <start point> <end point>
  

• 显示差别的相关统计

  $ git diff --stat <start point> [<end point>]
  

• 显示文件中各个部分的修改者及相关提交信息

  $ git blame <some file>
  

  显示文件中各个部分的修改者及相关提交信息，包括在该文件中复制、粘贴和移动内容等方面的情况。

  $ git blame -M <some file>
  

• 显示文件中各部分的修改者及相关提交信息，包括在文件移动内容方面的情况

  $ git blame -C -C <some file>
  

• 显示历史时，显示复制和粘贴信息

  $ git log -C -C -p -1 <some point>
  

远程版本库

• 克隆远程版本库

  $ git clone <some repository>
  

• 克隆远程版本库，但只下载其中最近200个提交的历史记录

  $ git clone --depth 200 <some repository>
  

• 在本地版本库中设置远程版本库的别名

  $ git remote add <remote repository> <repository url>
  

• 显示远程分支

  $ git branch -r
  

• 基于远程分支创建本地分支

  $ git branch <new branch> <remote branch>
  

• 基于远程标签创建本地分支

  $ git branch <new branch> <remote tag>
  

• 从别名“origin”的远程版本库中取来修改变化，但不合并到本地分支

  $ git fetch
  

• 从任意的远程版本库中取来修改变化，但不合并到本地分支

  $ git fetch <remote repository>
  

• 从任意的远程版本库中取来修改变化，并合并到当前检出的本地分支

  $ git pull <remote repository>
  

• 从别名为“origin”的远程版本库中取来修改变化，并合并到当前检出的本地分支

  $ git pull
  

• 把修改变化从本地分支推入远程版本库

  $ git push <remote repository> <local branch>:<remote branch>
  

• 把修改变化从本地分支推入远程版本库中同名分支

  $ git push <remote repository> <local branch>
  

• 把修改变化从本地新建分支推入远程版本库

  $ git push <remote repository> <local branch>
  

• 把修改变化推入别名为“origin”的远程版本库

  *当远程版本库中已有同名分支时，这个命令会推入本地分支到远程版本库对应的分支中。如果远程版本库中尚无同名分支，则须使用 git push *

  $ git push
  

• 在远程版本库中删除分支

  $ git push <remote repository> :<remote branch>
  

• 在本地版本库中删除所有远程版本库中已不存在的分支

  $ git remote prune <remote repository>
  

• 在本地版本库中删除某个远程版本库的简称，以及该远程版本库相关的分支

  $ git remote rm <remote repository>
  

连接Git和SVN

• 克隆SVN版本库的全部内容

  $ git svn clone <svn repository>
  

• 克隆具有标准结构的SVN版本库

  下面命令适用于克隆标准结构的SVN数据库，也就是说，主干命名为trunk，其他分支都存放于branches目录下，标签都存放于tags目录下。

  $ git svn clone -s <svn repository>
  

• 克隆非标准结构的SVN版本库

  $ git svn clone -T <trunk path> -b <branch path> -t <tag path> <svn repository>
  

• 克隆具有标准结构的SVN版本库中的某个版本（比如第2321版）

  $ git svn clone -s -r 2321
  

• 克隆具有标准结构的SVN版本库，并对SVN中的分支添加前缀

  $ git svn clone -s --prefix svn/ <svn repository>
  

• 从上游SVN版本库中获得更新的内容，并依此在本地Git版本库中变基本地分支

  $ git svn rebase
  

• 把修改变化推回上游SVN版本库

  $ git svn dcommit -n
  

• 显示SVN历史记录

  $ git svn log
  

• 显示文件中各个部分的SVN的修改者及相关提交信息

  $ git svn blame <some file>
  

参考资料

• Pragmatic Version Control Using Git（以上都是来自本书）
• Git Doc
• Github Help

A. Cows and Sequence

source code

对于一个数列，有三个操作：

1. 给a个数同时加x
2. 在末尾加入元素k
3. 去掉末尾的元素

对于每一次操作，查询数列的平均值，共有2*10^5次操作。三个操作都可以看作区间操作，[1,a]上同时加x，[sz,sz+1]加x，[sz-1,sz]减去数列末尾sz处的值，于是可以用树状数组来做。

B. Cow Program

source code

初始时给定两个数x=1，y=0，还有一个序列{an}，在这个基础上有一些列操作

1. 某一步后若x<=0或y>n，程序终止
2. x+=ax, y+=ax
3. x-=ax, y+=ax
4. 交替执行步骤2和3，或许有限步后结束，或许永远不会终止

现在给定序列{a[2..n]}，接下来将这个程序跑n-1遍，第i遍执行序列i, a2, …, an，若程序终止，输出y的值，否则输出-1

注意2和3中的ax，其中是以x是变量，是数组下标。比赛时没仔细看直接以为按顺序执行ai，做了很多无用功。略怨念

可以看到共有n*2个状态，2代表当前操作是2还是3，可以直接记忆化搜索。我写的比较麻烦，用了map<int, vector<int> >来表示图，比如mp[a+ax] = x。

C. Coin Troubles

source code

给定n种硬币，面值总共为t，然后有q种限制(bi, ci)，表示类型bi的硬币比ci多，现在要求有多少种方案。其中bi各不相同，ci各不相同。

对于每种限制(bi,ci)，从bi到ci连一条有向边，所谓bi各不相同就是同一个点不能有1条以上出边，ci各不相同即一个点不能有1条以上入边，于是只能够构成一条链，也有可能是圈，然而这是不合法的，直接输出0即可。找到链后，比如是x1,x2,…,xk，于是可以做新的硬币，Si=x1+…+xi，就可以处理，xi一定要比xj多的要求(i>j)，找方案数的话做一遍背包就可以了。其实细节还是挺多的，具体可以看代码。

D. Cows and Cool Sequences

source code

定义cool pair (x,y)是x能够用y个连续整数的和表示，cool sequence{an}是对所有(ai,a{i+1})是cool pair。想在给定一个数列，要求改动最少的数使其是cool sequence。还是直接看官方报告吧，基于一个发现然后n^2dp。

E. Cow Tennis Tournament

source code

数列{sn}表示一些cow的等级，cow_i能够打败cow_j当且仅当s_i>s_j，现在有一些操作[a,b]，等级在在区间[a,b]里的cow的胜负关系会发生改变。最后问查询无序数对(p,q,r)有多少，其中存在一个排列使得cow_p->cow_q->cow_r->cow_p，i->j表是cow_i可以击败cow_j。

首先最后答案为C(m,3)-sigma(C(win_i,2))。用c[n][n]表示胜负关系是否被改变，那么当一次查询[a,b]时，矩形[a,b]x[a,b]里的关系将被反转，用垂直扫描线，线段树就可以解决。具体还是看官方报告吧。

Summary

A，B，C都是可以做的，但是比赛的时候只搞出了A，B和C在赛后很快fix了，很不扎实啊(>_<)。D和E只能通过看官方报告来获取想法，希望能一点一点提高吧。总之这是一套很不错的题目。以上。。