ChangKe's Blog

写在HAOI2016之后

April 28, 2016

对考试也不想说什么。
只是退役的小伙伴有些可惜。
以后就只有一个人了。空荡荡的机房里，再也没人一起打比赛了。
不过，一个人的命运啊，当然要靠他自己的努力，但是也要考虑到，历史的，这个行程。
事已至此，祝他们高考顺利，而我还有很多的事情。
第一件：膜。
Orz红太阳hs，Orz蓝月亮mzx，Orz被Menci钦点进队的gcx和Fancy，Orz lzz，Orz KZ。
苟利国家生死以，岂因祸福避趋之。
这些人在北京这几天，主要就干了三件事。第一个呢，是参加了CTSC。第二个呢，是参加了APIO。第三个呢，是在群里面说要Au。当然有的真的Au了，不过这都不算什么大事，前面那三件才是最重要的。
你们这些记者，不要见的风，是的雨。我没有说要钦定谁谁谁拿Au，拿Au也要按照基本法，按照选举法，去产生。识得唔识得噶？
I hope to convey my best wishes,through the blog,to the HA teamers.
你问我资瓷不资瓷HA省全都是Au，我是资瓷的，我就明确地告诉你。但是我没有钦定，没有任何这个意思。（我钦定HA省所有人+Menci都是Au）
第二件就比较无聊了。。。因为家里穷没报APIO&CTSC，所以这几天就比较闲。。。就当是颓废了吧。正好老师不知道哪里来的想法，动员高一小朋友刷通USACO，索性一起玩玩。
刷完USACOTraining和USACO今年的所有月赛题，时间不晚于APIO结束。
第三件？浮躁咯~当然还要按着计划推各种题对吧，目前的计划是除了CTSC和IOI的所有题目，一道一道推。
就这样，说不定以后省队会玩胡测什么的，等APIO回来再说。。。

~~（没报CTSC和APIO真是今年下得最烂的一步棋。。。当时确实被周围人硬点退役(@班主任 @家长)，然后就不资瓷了。。。）~~

第八届“玲(ha)珑(wei)杯”某校赛切题报告

April 19, 2016

标题太长了。。。“玲珑杯郑州轻工业学院第八届ACM程序设计大赛暨河南高校邀请赛-正式赛”。。。
进度：1/10

A. 蛤玮学计网

第一题就这么麻烦真是不爽。。。
首先，这个字串里不能出现除数字和'.'外的字符，否则直接不合法；
其次，'.'必须恰好出现3个，否则不合法；
再其次，'.'不能在边界，也不能相邻，否则不合法；
最后就是判断数字的大小了，超过255就不合法。
经过这么多关卡，剩下的都合法。感觉这种题一个人想很容易漏掉一些情况，但三个人一起看会好很多。当然现场AC此题的Satoshi、miku、KZ也是相当厉害的（好像不是1A？）

#include <cstdio>
#include <cctype>
#include <cstring>
char str[100];
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str);
        int len = strlen(str);
        int cnt = 0, i;
        for (i = 0; i < len; i++)
        {
            if (!isdigit(str[i]) && str[i] != '.')
                break;
            if (str[i] == '.')
            {
                if (i && str[i - 1] == '.')
                    break;
                cnt++;
                if (cnt > 3)
                    break;
                if (i == 0 || i == len - 1)
                    break;
            }
        }
        if (i != len || cnt != 3)
        {
            puts("No");
            continue;
        }
        int num = 0;
        for (i = 0; i < len; i++)
        {
            if (isdigit(str[i]))
                num = num * 10 + str[i] - '0';
            if (num > 255)
                break;
            if (str[i] == '.' || i == len - 1)
            {
                if (num > 255)
                    break;
                num = 0;
            }
        }
        if (i != len)
        {
            puts("No");
            continue;
        }
        puts("Yes");
    }
    return 0;
}

J. 蛤玮当上主席

无法直视的题目名称。。。excited
这个idea好古老啊。。。而且，BestCoder Round #80不就有原题？
如果有1，那么无限多个1足够表示了；如果没有1，无论如何也凑不出1，所以就是判断输入有没有1。

#include <cstdio>
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int n, i, j = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            if (x == 1)
                j = 1;
        }
        if (j)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

BestCoder Round #80游记

April 18, 2016

晚上到机房打比赛。。。居然是Div1和Div2一起的？哈哈Rating要涨了！而且出题人好像是个蓝名CreationAugest，感觉题目应该是可做的。。
然后就是等着开始。
先看A题。这题好像和bhi神讲过的一道CF水题类似啊。。。因为每个数都有无穷多个，所以只要有1，就一定可以凑出所有数，而没有1的话，显然是凑不出来1的，直接就是不可能了。然后2min多时交了一发，WA了。
雾草。。。A题都挂。。。pill。。。
然后发现题中说的是自然数，那么还有一个0，如果没有0也要输出NO。应该没问题了吧。。再来一发。
What!PE!仔细检查一下，应该换行了啊，字母也都是大写啊，还有什么问题呢？
上Clarification问问。然后admin告诉我是数据传错了，已经重新上传了。。。。。求心里的阴影面积。。。果断再来一次AC了。
开B题。嗯，连接原点与直线上的所有整点是吧，那么没有被经过的点的坐标肯定满足一些性质，还是数论相关吧。。。然后用画图画了3和5的情况，发现只要是区域内的整点都不会被经过。是巧合吗？题上强调说 $q$ 是质数，一定有什么深意。
好吧就是个SB性质。。。如果 $x+y=q$ ， $q$ 是质数，那么 $x$ 和 $y$ 互质，因为 $\gcd(x,y)=\gcd(x,x+y)=1$ 。所以每条连线都不会经过除原点和直线上的点之外的任何整点，所以最后的答案就是区域内的整点个数之和啦。
我还会等差数列求和呢！于是这题就可以 $O(1)$ 解决。但问题是这数据明显在卡long long，所以找了个写过的快速乘模板交上去，AC了。
看C题。多明显的矩阵递推，两边都取对数，递推是就是 $g(n)=cg(n-1)+g(n-2)+b$ ，其中 $g(1)=0,g(2)=b$ 。然后就可以矩阵快速幂了。嗯，显然不能直接高精度，要取模的。模数应该是。。。反正不是 $p$ 。因为其实我们递推的是指数，而在指数上有著名的欧拉定理 $a^{\varphi(p)}\equiv 1(mod\ p)$ ，所以直接模 $\varphi(p)=p-1$ 即可。。。（这时的大脑已经傻逼到一定境界了不是吗）
然后就是从以前的题里找板子了。。。1遍过pretest。
D题比较有趣，因为出圈顺序已知，所以我们可以运用“重标号法”，得出一些同余方程，关键是怎么解。。。百度了一下非互质的CRT，抄了一遍交上去。什么？WA了？我再改改。。。什么？又WA了？不对吧。。。开始人脑对拍，并没有问题啊。。。然后刷新页面，发现题目中多了一行黑体字，意思是输入的内容和我理解的不一样，但样例太弱所以我没看出来。。。
然后随便改改就A了。骂出题人骂了几遍。E题时间不够了，一看就是线段树+分层图+最短路，就很遗憾的弃掉啦。（如果不弃的话Rank会高很多的）
Hack也很有意思。从下往上点，一堆堆没特判0的，连叉四个，然后就找不出来Hack点了。。。首页某大神Hack21次。。。
结束之后看题解。第一眼看到了C的这句话：
这题有一个小trick，注意 $a\ mod\ p=0$ 的情况.
这题有一个小trick，注意 $a\ mod\ p=0$ 的情况.
这题有一个小trick，注意 $a\ mod\ p=0$ 的情况.
妈蛋。。。要FST了。。。。。。欧拉定理在那个时候怎么会成立。。。。。。
最后果然FST了。。。所幸别人有很多也挂了，因此Rating还是涨了不少的。Menci最后交C题还CE了？Sad story.
好像这种比赛加Rating很容易吧。。。不过令人惊奇的lbn187和TooDifficult事件并没有得到官方回应。。。然后去碎觉啦

SDOI2016Round1游记

April 11, 2016

Day 0

我们坐着大巴来到了省城济南。

Day 1

我在考场上睡了5个小时。

Day 2

我在考场上睡了5个小时。
结果爆0了，连参加Round2的机会都没有。还好我不是山东人。
（以上均为口胡）
真实情况：

Day 0

我在家里看着SD的各位神犇发说说求保佑，见一个膜一个。

Day 1

Menci在中午把题发给我，我吓傻了，一道也不会。后来她还告诉我有人AK，感觉心灵受到了震撼。

Day 2

Menci说她可以去Round2了。我又去看各位神犇的游记，见一个膜一个。

后续

Menci把题放到了COGS上，然后混了个管理员权限。然后我才开始正式刷SDOI2016Round1的6道题。
下面才是正文

储值表

第一题就这么坑让不让人活了，考场上被吓倒的话估计直接三个暴力弃疗……所幸不少人做出了明智的决定——放弃法。
但我就是个SX，我并没有用这个方法。这可是新题，没有题解没有标程，周围的人都不知道怎么搞，真真正正的“开荒”。好的是COGS上可以随便看数据，于是就开始对着数据Debug，虽然不是什么光彩的事情，但没办法了。还是太弱，做不到1A。

算法一

直接大暴力算出来所有的数，然后暴力计算，毫无技巧可言。
时间复杂度 $O(Tnm)$ ，因为数据不卡暴力所以有20分。这应该是考场上出现最多的得分了。

算法二

然而我不知道中间那一堆部分分是干嘛的……所以直接来正解。（似乎标算跟我的截然不同？不过很快就是了）
首先我们打一个 $8\times 8$ 的储值表。很多题都是一打表就看出规律，这次也不例外：

$\begin{matrix} x\ xor\ y & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6\\ 2 & 2 & 3 & 0 & 1 & 6 & 7 & 4 & 5\\ 3 & 3 & 2 & 1 & 0 & 7 & 6 & 5 & 4\\ 4 & 4 & 5 & 6 & 7 & 0 & 1 & 2 & 3\\ 5 & 5 & 4 & 7 & 6 & 1 & 0 & 3 & 2\\ 6 & 6 & 7 & 4 & 5 & 2 & 3 & 0 & 1\\ 7 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0\\ \end{matrix}$

有什么规律吗？当然。
性质1 如果 $x<2^S,y<2^S$ ，那么 $(x + 2^S)\ xor\ (y + 2^S) = x\ xor\ y$ 。
证明显然加上 $2^S$ 之后，两个数的最高位相同，均为1，异或后抵消，所以最后得到的异或值不变。
性质2 对于任意 $y \neq z$ ，有 $x\ xor\ y \neq x\ xor\ z$ 。
证明采用反证法。假设 $x\ xor\ y = x\ xor\ z=a$ ，那么 $y=a\ xor\ x,z=a\ xor\ x$ ，则有 $y=z$ ，与题设矛盾，所以不成立。
性质3 对于 $x<2^S$ ， $0\ xor\ x,1\ xor\ x,\cdots, 2^S-1\ xor\ x$ 必取遍 $0,1,2,\cdots,2^S-1$ 中的所有数。
证明由性质2可知上面这些数都不相同，而这些数字在二进制下都只有不超过 $S$ 位，不可能大于等于 $2^S$ ，也就是说 $2^S-1$ 个数都不超过 $2^S-1$ ，显然会取遍所有数。
性质还有很多，你们可以去探索什么的。现在开始讲这题怎么做，核心就是分情况讨论。
我们记 $calc(n, m, k)$ 表示按照题目要求计算出的结果。为了方便，以下假定 $n \leq m$ 。
情况1
如果 $n=m=2^S$ ，那么根据性质3，这个正方形内每个小于 $2^S$ 的数都出现了 $n$ 次，那么直接返回 $n\times (0+1+2+3+\cdots+(n-k))$ 即可，注意用等差数列求和公式化简就好了。
情况2
我们先计算出 $n,m$ 在二进制下分别有多少位，分别记为 $bit(n)$ 和 $bit(m)$ 。在这种情况下，我们讨论 $bit(n)=bit(m)$ 的情况。
这个时候，整个长方形还算是比较“方”的，没有一边长度大于等于另一边的两倍。那么我们可以通过直线 $x=2^{bit(n)}-1和y=2^{bit(n)}-1$ 把整个矩形分成四部分：
第一部分的四个边界分别是 $x=0,x=2^{bit(n)}-1,y=0,y=2^{bit(n)}-1$ ，对这个区域我们用情况1计算 $calc(2^{bit(n)},2^{bit(n)},k)$ 。第二部分的四个边界是 $x=0,x=2^{bit(n)}-1,y=2^{bit(n)},y=m-1$ ，这个区域可以看做有 $m-2^{bit(n)}$ 行，每行中，每个数都是大于等于 $2^{bit(n)}$ 的，而且如果我们不考虑它们二进制的最前面一位，那么它们仍会取遍 $0,1,2,\cdots,2^{bit(n)}-1$ 中的所有数，也就是每一行的数都取遍 $2^{bit(n)},2^{bit(n)}+1,\cdots,2^{bit(n)}+2^{bit(n)}-1$ 中的所有数，这时还是可以用等差数列求和来求出所有要求的数之和。第三部分的四个边界是 $x=2^{bit(n)},x=n-1,y=0,y=2^{bit(n)}-1$ ，这与第二部分完全一致。第四部分的四个边界是 $x=2^{bit(n)},x=n-1,y=2^{bit(n)},y=m-1$ ，也就是右下角的小矩形，根据性质1，我们完全可以等价地计算 $calc(n-2^{bit(n)},m-2^{bit(n)},k)$ 。
综上，每次递归总会把问题的规模缩小至少一半。而每次的计算显然都只需要常数时间。
情况3
如果 $bit(n)>bit(m)$ ，那么这个图形就会像一个长条一样，我们把它分成两个部分：
第一部分是从左边开始的 $2^{bit(n)}$ 列，根据性质3，每行的这类数取遍了 $0,1,2,\cdots,2^{bit(n)}-1$ 中的所有数，直接计算即可。第二部分就是剩下的部分，因为这些数的最高位显然都是1，因此当 $k>2^{bit(n)}$ 时，我们需要计算 $calc(n-2^{bit(n)},m,k-2^{bit(n)})$ ，否则先计算 $calc(n-2^{bit(n)},m,0)$ ，再加上这一部分数的个数乘以 $2^{bit(n)}$ ，这样才能把最高位都算进来。
综上，每次递归总会把问题的规模缩小至少一半。而每次的计算显然都只需要常数时间。
这三种情况涵盖了所有问题，而递归调用的次数是 $O(\log n)$ 级别的。因此可以很快出解。
时间复杂度 $O(T\max\{n,m\})$ ，期望得分100分。值得注意的是这里很多运算有着爆long long的风险，所以要小心哦~
代码上COGS看吧。

数字配对

这题应该不少人现场AC吧。。。那我直接说正解了。
正解是费用流。
首先，我们惊喜地发现，如果把每种数抽象成一个点，可以配对的脸一条边，那么形成的图是一个二分图！
为什么呢？因为，根据质数的性质，这个图不存在任何形式的环。。。然后自己YY一下就证出来了。
因此，我们可以先进行一遍二分图染色来确定每个点是“左侧”的还是“右侧”的。之后建图，建立源 $S$ 和汇 $T$ ，从 $S$ 到所有左侧结点 $i$ 连一条容量为 $b[i]$ ，费用为0的边，从每个右侧结点 $j$ 到 $T$ 连一条容量为 $b[j]$ ，费用为0的边，而对于每对可以配对的点 $i,j$ ，易知它们必有一个在左侧，一个在右侧，所以从左侧点到右侧点连接一条容量为 $\min{b[i],b[j]}$ ，费用为 $-c[i]*c[j]$ 的边。
然后，站在这个图上按照常规的费用流方法进行增广，当费用超过0或无法增广的时候返回流量即可。因为费用流用的是贪心做法，所以这里可以得到正确结果。但增广时不能以1为增广量，而是保证费用不超过0且不违反流量限制的最大增广量。
然后就去COGS看代码吧。

未完待续

HAOI2013

April 11, 2016

哇，貌似14年及以前的HAOI都是专门照顾弱省选手的套题么……
总体来看，HAOI2013的水题占了很大一部分，但也有很好的，区分度不错的题。经我排过版的题面可以在这里下载：Day1.pdf，Day2.pdf
下面是正文。

跑步训练(t1)

出题人你觉得这也叫省选难度？每一段都必须进行往返，我们直接计算出每段往返用的总时间（注意上下坡），然后从前到后依次加入并判断就好了。
时间复杂度 $O(M)$ ，期望得分100分。当然代码是我几年前写的。

AC code

program P1368;
var
    m,t,u,f,d,i,sum:longint;
    c:char;
    a:array[1..100000] of longint;
begin
    readln(m,t,u,f,d);
    for i:=1 to t do
    begin
        readln(c);
        case c of
        'u','d':a[i]:=u+d;
        'f':a[i]:=2*f;
        end;
    end;
    i:=0;
    sum:=0;
    while  (sum<=m)and(i<=t) do
    begin
        inc(i);
        inc(sum,a[i]);
    end;
    if i=t then writeln(t) else writeln(i-1);
end.

花卉节(t2)

因为这题只要求满意的人数最多，所以只要贪心，尽量优先选取较便宜的花卉即可。注意这题的很多数据接近long long的最大值，所以在中间运算过程中可能会越界，造成WA。我的解决办法是尽量少用乘法、加法，尽量用除法、减法代替，把中间值用实数存，这样就可以AC了。
时间复杂度大概是排序的 $O(N\log N)$ ，期望得分100分。

AC code

#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
struct thing 
{
    ULL p, c;
}; 
inline bool operator <(thing x, thing y)
{
    return x.p < y.p;
}
int n;
ULL b, cost, ans;
thing x[100010];
int main()
{
    scanf("%d%llu", &n, &b);
    for (int i = 0; i < n; i++)
        scanf("%llu%llu", &x[i].p, &x[i].c);
    sort(x, x + n);
    for (int i = 0; i < n; i++)
    {
        ULL ls = (ULL)(1.0 * (b - cost) / x[i].p);
        if (ls <= x[i].c)
        {
            ans +=ls;
            break;
        }
        ans +=x[i].c;
        cost += x[i].p * x[i].c;
    }
    printf("%llu\n", ans);
    return 0;
}

开关控制(t3)

啊出题人居然在抄袭USACO的月赛题，太无耻了！
不过这题还是很有意思的。

算法一

根据题意，任何一盏灯连按两次相当于没按，所以这不可能是最优决策。因此每个灯最多按一次，暴力枚举每个开关是否按，然后判断并取最优解就好了。
时间复杂度 $O(2^N)$ ，期望得分70分（这数据是我从COGS评测记录里发现的）。

算法二

首先，我们用邻接矩阵 $g$ 把图存下来。当然，因为按下一个开关也会改变它自己的状态，所以我们可以把对角线上的元素都设为true。
我们发现对于每个点，灯亮的条件是它本身和与它相连的所有点中，被按过的开关有奇数次。如果我们对每个点都设置一个变量 $x_i$ 表示第 $i$ 是否按过，那么也就是它及它相连的点的 $x$ 值之和为奇数。
看到这里，直觉告诉我们，这正好对应了一种位运算 $xor$ ，因为奇数个1 $xor$ 起来仍然是1，而偶数个1 $xor$ 之后就变成了0。所以，这样子我们就列出了一个异或方程组：

$\begin{cases} g_{1,1}x_1\ xor\ g_{1,2}x_2\ xor\ g_{1,3}x_3\ xor\ \cdots\ xor\ g_{1,n}x_n=1\\ g_{2,1}x_1\ xor\ g_{2,2}x_2\ xor\ g_{2,3}x_3\ xor\ \cdots\ xor\ g_{2,n}x_n=1\\ g_{3,1}x_1\ xor\ g_{3,2}x_2\ xor\ g_{3,3}x_3\ xor\ \cdots\ xor\ g_{3,n}x_n=1\\ \cdots\cdots\\ g_{i,1}x_1\ xor\ g_{i,2}x_2\ xor\ g_{i,3}x_3\ xor\ \cdots\ xor\ g_{i,n}x_n=1\\ \cdots\cdots\\ g_{n,1}x_1\ xor\ g_{n,2}x_2\ xor\ g_{n,3}x_3\ xor\ \cdots\ xor\ g_{n,n}x_n=1\\ \end{cases}$

然后就是解这个方程组。这里要用到高斯消元的方法，把这个方程组消成一个“上三角矩阵”，然后对方程组的所有变元，我们暴力枚举它们的取值，然后推出原方程组的解，计算出有多少个数是1，取最小值即可。
时间复杂度最坏是指数级的，不过可以通过最优性剪枝优化，但我并不会很好的分析。。。就当是 $O(跑得出)$ 好了。期望得分100分。

AC code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct eq
{
    bool c[100], a;
};
eq eqs[100], zero;
int n, m;
bool con[100][100];
int fre[100], cnt;
bool r[100];
int ans, ls;
bool operator <(eq x, eq y)
{
    for (int i = 1; i <= n; i++)
        if (x.c[i] != y.c[i])
            return x.c[i] > y.c[i];
    return false;
}
bool operator ==(eq x, eq y)
{
    return (!(x < y) && !(y < x));
}
void dfs(int now)
{
    if (ls > ans)
        return;
    if (now < cnt)
    {
        r[fre[now]] = 0;
        dfs(now + 1);
        r[fre[now]] = 1;
        ls++;
        dfs(now + 1);
        ls--;
        r[fre[now]] = 0;
    }
    else
    {
        int now = n, l = 0;
        for (int i = n; i >= 1; i--)
        {
            int j;
            for (j = 1; j <= now; j++)
                if (eqs[i].c[j])
                    break;
            if (j > now)
                continue;
            bool ls = 0;
            for (int k = j + 1; k <= n; k++)
                if (eqs[i].c[k])
                    ls ^= r[k];
            r[j] = eqs[i].a ^ ls;
            now = j - 1;
        }
        for (int i = 1; i <= n; i++)
            l += r[i];
        ans = min(ans, l);
    }
}
int main()
{
    freopen("haoi13t3.in", "r", stdin);
    freopen("haoi13t3.out", "w", stdout);
    scanf("%d%d", &n, &m);
    memset(con, 0, sizeof(con));
    for (int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        con[x][y] = con[y][x] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        eqs[i].a = 1;
        for (int j = 1; j <= n; j++)
            if (i == j)
                eqs[i].c[j] = 1;
            else
                eqs[i].c[j] = con[i][j];
    }
    sort(eqs + 1, eqs + n + 1);
    int p = 1;
    for (int i = 1; i <= n; i++)
    {
        bool flag = true;
        for (int j = p; j <= n; j++)
            if (eqs[j].c[i])
            {
                flag = false;
                swap(eqs[p], eqs[j]);
                break;
            }
        if (!flag)
        {
            for (int j = p + 1; j <= n; j++)
            {
                if (eqs[j].c[i])
                {
                    for (int k = i; k <= n; k++)
                        eqs[j].c[k] ^= eqs[p].c[k];
                    eqs[j].a ^= eqs[p].a;
                }
            }
            p++;
        }
        else
        {
            fre[cnt++] = i;
        }
    }        
    ans = n;
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

软件安装(t4)

感觉是比赛里唯一一道有区分度的题目了。当时写了好久，最后WA一大片，后来发现少打了个等号……

算法一

直接暴力枚举所有操作，暴力查询。
时间复杂度 $O(nm)$ ，期望得分我也不知道，就当是40分吧。

算法二

这题都是区间操作，很自然地会想到用线段树。不过想法还是很新奇的。
线段树上的每个线段 $[l,r]$ 除了保存儿子节点的指针之外，还要保存当前区间内最长的连续区间。但只保存这个的话是不能更新状态的对吧，我们还要存储从左边界开始的最长连续区间和到右边界结束的最长连续区间，然后就可以方便的维护了。
其实这维护的思想有些类似于NOI2005的《维修数列》，本身很简单，而这里的难点在于询问。询问的是定长的连续区间最靠左的位置，看似和我们维护的信息无关。但我们进行一些分析的话，问题就好办了。
首先，如果当前区间内的最长连续区间太小，那么直接返回不存在；如果区间长度恰等于询问长度，且区间内均为可行区间，那么返回左边界；如果左儿子区间内的最长连续区间大于等于询问区间，那么递归处理左儿子；如果左儿子区间内的最长连续区间太小，那么从当前区间的中点开始，尽量往左扩展，然后再尽量往右扩展，直到得到长度恰为所要求区间的长度，返回最左边的位置；如果上述操作都不存在可行解，再递归处理右儿子，这时肯定有解，不然最开始就可以返回无解了。
注意以上操作必须严格按照顺序，才能保证返回值最靠前。这样找到可行的区间之后，进行区间覆盖操作，更新线段树即可。
时间复杂度 $O(M\log N)$ ，期望得分100分。
（感觉口胡了好多啊，建议对着代码理解）

AC code

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
int readint()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    x = c - '0';
    c = getchar();
    while (isdigit(c))
    {
    x = x * 10 + c - '0';
    c = getchar();
    }
    return x;
}
struct node
{
    int l, r;
    int m, lm, rm, mp;
    int tag;
    node() : l(0), r(0), m(0), lm(0), rm(0), mp(0), tag(-1) {}
    node(int l, int r, int m, int lm, int rm, int mp, int tag) : l(l), r(r), m(m), lm(lm), rm(rm), mp(mp), tag(tag) {}
};
int n, m;
node sgt[300050];
void build(int p, int l, int r)
{
    if (l == r)
    {
        sgt[p] = node(l, r, 1, 1, 1, l, -1);
        return;
    }
    int mid = (l + r) / 2, len = r - l + 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    sgt[p] = node(l, r, len, len, len, l, -1);
}
void pushdown(int p)
{
    if (sgt[p].tag == 1)
    {
        sgt[p << 1].tag = sgt[p << 1 | 1].tag = 1;
        sgt[p].lm = sgt[p].rm = sgt[p].m = -1;
        sgt[p].mp = -1;
        sgt[p].tag = -1;
    }
    if (sgt[p].tag == 0)
    {
    sgt[p << 1].tag = sgt[p << 1 | 1].tag = 0;
    sgt[p].lm = sgt[p].rm = sgt[p].m = (sgt[p].r - sgt[p].l + 1);
    sgt[p].mp = sgt[p].l;
    sgt[p].tag = -1;
    }
}
void pushup(int p)
{
    pushdown(p);
    pushdown(p << 1);
    pushdown(p << 1 | 1);
    int x1 = sgt[p << 1].m, x2 = sgt[p << 1].rm + sgt[p << 1 | 1].lm, x3 = sgt[p << 1 | 1].m;
    if (x1 >= x2 && x1 >= x3)
    {
        sgt[p].m = x1;
        sgt[p].mp = sgt[p << 1].mp;
    }
    else if (x2 >= x3)
    {
        sgt[p].m = x2;
        sgt[p].mp = sgt[p << 1].r - sgt[p << 1].rm + 1;
    }
    else
    {
        sgt[p].m = x3;
        sgt[p].mp = sgt[p << 1 | 1].mp;
    }
    sgt[p].lm = sgt[p << 1].lm;
    if (sgt[p << 1].lm == (sgt[p << 1].r - sgt[p << 1].l + 1))
        sgt[p].lm = max(sgt[p].lm, sgt[p << 1].lm + sgt[p << 1 | 1].lm);
    sgt[p].rm = sgt[p << 1 | 1].rm;
    if (sgt[p << 1 | 1].rm == (sgt[p << 1 | 1].r - sgt[p << 1 | 1].l + 1))
        sgt[p].rm = max(sgt[p].rm, sgt[p << 1].rm + sgt[p << 1 | 1].rm);
}
inline int query()
{
    pushdown(1);
    return sgt[1].m;
}
int getsmallest(int p, int len)
{
    pushdown(p);
    if (sgt[p].m < len)
        return 0;
    if (sgt[p].lm >= len)
        return sgt[p].l;
    if (sgt[p << 1].m >= len)
        return getsmallest(p << 1, len);
    if (sgt[p << 1].rm >= 0 && sgt[p << 1 | 1].lm >= 0 && sgt[p << 1].rm + sgt[p << 1 | 1].lm >= len)
        return (sgt[p << 1].r - sgt[p << 1].rm + 1);
    return getsmallest(p << 1 | 1, len);
}
void change(int p, int l, int r, int t)
{
    pushdown(p);
    if (l <= sgt[p].l && r >= sgt[p].r)
    {
        sgt[p].tag = t;
        return;
    }
    if (l > sgt[p].r || r < sgt[p].l)
        return;
    change(p << 1, l, r, t);
    change(p << 1 | 1, l, r, t);
    pushup(p);
}
int main()
{
    n = readint();
    m = readint();
    build(1, 1, n);
    for (int i = 0; i < m; i++)
    {
        int type = readint();
        if (type == 1)
        {
            int l = readint();
            if (query() < l)
            {
                printf("0\n");
            }
            else
            {
                int ls = getsmallest(1, l);
                printf("%d\n", ls);
                change(1, ls, ls + l - 1, 1);
            }
        }
        else
        {
            int s = readint();
            int t = readint();
            change(1, s, s + t - 1, 0);
        }
    }
    return 0;
}

遥控器(t5)

小学生都会的最短路。Floyd算法都行。
时间复杂度 $O(102^3)$ ，期望得分100分。你要想写Dijkstra或SPFA也很好啊~

AC code

#include <cstdio>
#define S1 100
#define S2 101
#define INF 10000000
int graph[110][110];
bool ok[13];
const int tr[13] = {1, 2, 3, 10, 4, 5, 6, 11, 7, 8, 9, 12, 0};
int main()
{
    freopen("HAOI2013T5.in", "r", stdin);
    freopen("HAOI2013T5.out", "w", stdout);
    for (int i = 0; i < 13; i++)
    {
        int x;
        scanf("%d", &x);
        ok[tr[i]] = (x == 1);
    }
    int s, t;
    scanf("%d%d", &s, &t);
    for (int i = 0; i < 102; i++)
        for (int j = 0; j < 102; j++)
            graph[i][j] = (i == j) ? 0 : INF;
    for (int i = 0; i < 100; i++)
        graph[i][S1] = 0;
    for (int i = 0; i < 10; i++)
        if (ok[i])
            graph[S1][i] = 1;
    if (ok[10])
    {
        for (int i = 0; i < 99; i++)
            graph[i][i + 1] = 1;
        graph[99][0] = 1;
    }
    if (ok[11])
    {
        for (int i = 1; i < 100; i++)
            graph[i][i - 1] = 1;
        graph[0][99] = 1;
    }
    if (ok[12])
    {
        for (int i = 0; i < 100; i++)
            graph[i][S2] = 1;
        for (int i = 10; i < 100; i++)
            if (ok[i / 10] && ok[i % 10])
                graph[S2][i] = 2;
    }
    for (int k = 0; k < 102; k++)
        for (int i = 0; i < 102; i++)
            for (int j = 0; j < 102; j++)
                if (graph[i][k] + graph[k][j] < graph[i][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
    if (graph[s][t] == INF)
        puts("-1");
    else
        printf("%d\n", graph[s][t]);
    return 0;
}

UOJ Round #13：暴力练习大赛

April 10, 2016

标题已经说明了一切。
今天下午bhi神过来问我，“机房有人吗？”，我说不知道，然后发现居然有人，就跑进去了。
然后直到放学才出来。干了些什么呢？首先艹了一波ZLXSC的题解，居然被出题人赞了，开心owo
然后发现ZLXSC的时间和UR恰好无缝对接，然后连饭都没吃就开始打UR。
先看题。貌似都不可做……暴力大法好。
A暴力 $O(n^2 \log n)$ 二分+贪心，B暴力 $O(n^3)$ DP，C暴力 $O((r-l)\log r)$ 分解质因数。
然后60+20+20=100，Rank50。不过Rating还是涨了，毕竟前面几场都挂了，所以底数很低。
好短啊。。。看来人太傻逼还是写不出来什么有价值的东西吧
附上代码凑字数

A

#include <cstdio>
#define INF 100010
int a[INF];
bool b[INF];
int lsa[INF];
bool lsb[INF];
int n, q;
bool ok(int x)
{
    int lsn = n;
    for (int i = 1; i <= lsn; i++)
    {
        lsa[i] = a[i];
        lsb[i] = b[i];
    }
    while (true)
    {
        int mm = INF, d = 0;
        for (int i = 1; i <= lsn; i++)
            if (!lsb[i] && mm > lsa[i])
                mm = lsa[i], d = i;
        if (!d)
            return true;
        int l = d, r = d;
        while (l >= 2 && lsa[l - 1] > lsa[d])
            l--;
        while (r <= lsn - 1 && lsa[r + 1] > lsa[d])
            r++;
        if (r - l + 1 < x)
            return false;
        else
        {
            lsn--;
            for (int i = d; i <= lsn; i++)
            {
                lsa[i] = lsa[i + 1];
                lsb[i] = lsb[i + 1];
            }
        }
    }
}
int check()
{
    int l = 1, r = n;
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        if (ok(mid))
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    return (ok(r) ? r : l);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char x = getchar();
            while (x < '0' || x > '1')
                x = getchar();
            b[j] = (x == '1');
        }
        printf("%d\n", check());
    }
    return 0;
}

B

#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 500010
#define INF 1000000001
using namespace std;
int a[MAXN], b[MAXN];
int n;
long long ans[MAXN];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", a + i, b + i);
    a[0] = -INF;
    for (int i = 1; i <= n; i++)
    {
        int j = i;
        ans[i] = 1;
        while (abs(a[j] - a[j - 1]) <= b[j] - b[j - 1])
            j--;
        for (int k = j; k < i; k++)
        {
            if (ans[i] < (long long)(i - k + 1) * (i - k + 1))
                ans[i] = (long long)(i - k + 1) * (i - k + 1);
            for (int l = 1; l < k; l++)
                if (abs(a[k] - a[l]) <= b[k] - b[l])
                    if (ans[l] + (long long)(i - k + 1) * (i - k + 1) > ans[i])
                        ans[i] = ans[l] + (long long)(i - k + 1) * (i - k + 1);
        }
        for (int k = 1; k < j; k++)
        {
            if (ans[k] + 1 > ans[i] && abs(a[i] - a[k]) <= b[i] - b[k])
                ans[i] = ans[k] + 1;
        }
    }
    long long o = 0;
    for (int i = 1; i <= n; i++)
        if (ans[i] > o)
            o = ans[i];
    printf("%lld\n", o);
    return 0;
}

C

#include <iostream>
#include <cstdio>
using namespace std;
int prime[10010010], cnt;
bool flag[10010010];
void prepare()
{
    for (int i = 2; i <= 10010000; i++)
    {
        if (!flag[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt; j++)
        {
            if (i * prime[j] > 10010000)
                break;
            flag[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main()
{
    prepare();
    int l, r;
    long long ans = 0;
    scanf("%d%d", &l, &r);
    for (int i = l; i <= r; i++)
    {
        if (!flag[i])
            continue;
        int d1 = 0, d2 = 0, ls = i;
        for (int j = 0; j < cnt; j++)
        {
            if (ls % prime[j] == 0)
            {
                d2 = d1;
                d1 = prime[j];
                while (ls % prime[j] == 0)
                    ls /= prime[j];
            }
            if (!flag[ls])
            {
                d2 = d1;
                break;
            }
        }
        ans = ans + d2;
    }
    printf("%lld", ans);
    return 0;
}

ZLXSCDay2验题报告

April 10, 2016

这次比赛的出题人有ZLX，Austin Bannister，Brian Dean，Nathan Pinsker。
后面几位的出现是因为引用了USACO月赛原题。
我是本次比赛的验题人，因此没有参加比赛，当然你们要吐槽题目也不要怪我啊~（逃
下面是正文，顺序为随机顺序。

4.黑心买卖

比赛开始前我问出题人，说你出这题有什么意义，然后他沉默了。
看这道题之前，请先学习并查集的相关知识，最好AC掉下面这道题：打击犯罪.pdf，目前我只发现在AYYZVijos上可以在线提交，地址http://pingce.ayyz.cn/vijos/Problem_Show.asp?id=1949。

算法一

暴力模拟所有的操作，每进行一次操作后用BFS更新连通性。
时间复杂度 $O(n^2)$ ，期望得分30分。

算法二

这里只有删除操作，我们完全可以把所有操作倒过来，变成只有插入点的操作。而每次插入操作又等价于合并一些连通块，所以我们用并查集进行维护。每插入一个点，我们把所有与之相连的点所在的集合进行合并，并在合并中随时更新最大集合所含的元素个数，如果这个数等于当前插入的点的个数，那么本次输出YES，否则输出NO。
时间复杂度 $O(n\alpha (n))$ ，期望得分100分。

1.梦游仙境

看这道题之前，请先学习2014年国家集训队的这篇论文：根号算法——不止是分块.pdf，作者王悦同。

算法一

很显然直接暴力统计就可以了。
时间复杂度最坏是 $O(nq)$ ，期望得分30分。

算法二

就是那个论文里的例1。文中的标题是“从一道水题说起”。
时间复杂度最坏是 $O(n\log n+\sqrt{n}q)$ ，期望得分100分。

2.撩妹高手

比赛开始前我问出题人，说你出这题有什么意义，然后他BlahBlah说这题不水，然后我发现我想简单了。

算法一

题目的描述很容易使人想到动态规划。我们设 $f[i]$ 表示前 $i$ 个蛋糕所能获得的最大总体积。显然 $f[0]=0$ ，状态转移方程是

$f[i]=\max_{0 \leq j < i,R[j] \geq R[i]}\{f[j]\}+\pi\times R[i]^2 \times H[i]$

按照这个方程直接DP就行了。
时间复杂度 $O(n^2)$ ，期望得分40分。

算法二

上面这个DP方程里，对变量 $j$ 只用到了它所对应的 $f[j]$ ，这启示我们可以用某种数据结构来避免这一层枚举。因为方程中的限制条件是 $0 \leq j < i,R[j] \geq R[i]$ ，而我们是从前往后做的，所以在计算时只有在前面的才可能放进数据结构里，因此暂时不必管 $0 \leq j < i$ 的条件。
而对于另一个条件 $R[j] \geq R[i]$ ，如果我们构造另一个序列，它的下标范围是 $[1,maxR]$ ，每一个位置上存的值，就是半径等于下标的位置对应的 $f$ 值中最大的一个。这样，我们的询问就成了询问这个序列的某一个后缀的最大值，用树状数组或线段树维护就可以了。当然计算出新的 $f$ 值之后，不要忘了更新。
时间复杂度 $O(n\log maxR)$ ，期望得分100分。

3.卡牌游戏

In the simple case where high card always wins one optimal strategy that Bessie can take is to always answer FJ's plays with her lowest card that is still higher than FJ's card (or her lowest card in the case she can't beat FJ). This works because if we can take something we should; otherwise the best that the card we didn't end up using can gain us is 1 trick so there can be no net gain.
This strategy informs the more complicated scenario where we switch from high card wins to low card wins at some point. In this case we should always allocate our highest cards to the section where high card wins and are lowest cards to the latter section. Then this reduces to the simpler case.
To solve this problem where we need to determine the best switch point we can make use a segment tree data structure that will enable us to solve the online version of the simple case. We will be able to insert a card for each player and determine the max score Bessie could achieve. Using this data structure we can determine how many points Bessie will get from the high card wins and low card wins part of each game and output the switch point that yields the highest overall score.
Building this data structure can be done by tracking for each segment in the tree the number of available cards in this segment that Bessie could play over lower cards, the number of coverable cards that FJ has played in this segment that haven't been covered, and the number of points we can score in this segment. Combining two segments is then done by summing the points and awarding points based on the min of coverables on the left and coverers on the right. The other fields are updated similarly (see comb() in my code below). The rest is a standard segment tree implementation.

啊哈，美国人的题解，简单易懂，对吧！我就不解释了~

5.哞哞城堡

This problem suggests a DP approach, and the bounds suggest that $O(n^3)$ is a comfortable target to aim for. There are several ways to approach this problem, but all of these focus on fixing some property of the rectangle, iterating over all possible values of that property, and finding the best rectangle for each iteration. One of the simpler ways is to fix an edge of the rectangle, and calculate the maximum possible rectangle with that edge.
For simplicity, we will fix the left edge of the rectangle. There are $O(n^2 \cdot n) = O(n^3)$ possible left edges, so we will reach our desired runtime if we can compute the best possible rectangle with this edge in $O(1)$ time. Luckily, we can use a sliding window to do so: if we process the left edges in order from left to right, we can note that the right edge of the rectangle must also move to the right over time. This is because a candidate rectangle will never become invalid as we move its left edge more to the right. We can use a simple data structure to query subrectangles of our given array in $O(1)$ time (see the code below if you're not quite sure how).

啊哈，美国人的题解，简单易懂，对吧！我就不解释了~

什么，你想打我？快跑啊……
如果你阅读上述内容有困难，请拿出《牛津高阶英汉词典》。

20160409模拟测试

April 10, 2016

不知道老师从哪里找的题，很水的样子，2hAK，虐标程0.5s。

题1.单词公共子串(pow)

问题描述

有一个单词序列，单词中的字母来自字母表 $['a',\dots,'z']$ 。编程求所有单词中最长的公共部分。

任务

从文本文件pow.in中读入单词序列，计算在每一个单词中都出现的最长子串长度，将结果写入文本文件pow.out中。

输入格式

在输入文件pow.in的第一行有一个整数 $n(1 \leq n \leq 5)$ ，表示单词个数。下面的 $n$ 行，每行有一个由小些英文字符 $['a',\dots,'z']$ 组成的单词。每个单词的长度最少为 $1$ ，最大不超过 $2000$ 。

输出格式

在文本文件pow.out中只有一个整数，为包含在每个单词的公共子串的最大长度。

样例输入

3
abcb
bca
acbc

样例输出

题解

这也要题解？后缀数组裸题啊。详见国家集训队论文《后缀数组——处理字符串的有力工具》，作者罗穗骞。

#include <cstdio>
#include <cstring>
char str[5][3000], s[20000];
int f[5], t[5], cnt[5];
int sa[20000], rank[20000];
int height[20000];
int n, len;
int Wa[20000], Wb[20000];
int Ws[20000], Wv[20000];
bool cmp(int *r,int a, int b, int l)
{
    return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void getsa()
{
    int *x = Wa, *y = Wb;
    int i, j, p, *t;
    int m = 127;
    for (i = 0; i < m; i++)
        Ws[i] = 0;
    for (i = 0; i < len; i++)
        Ws[x[i] = s[i]]++;
    for (i = 1; i < m; i++)
        Ws[i] += Ws[i - 1];
    for (i = len - 1; i >= 0; i--)
        sa[--Ws[x[i]]] = i;
    for (j = 1, p = 1; p < len; j *= 2, m = p)
    {
        for (p = 0,i = len - j; i < len; i++)
            y[p++] = i;
        for (i = 0; i < len; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;
        for (i = 0; i < len; i++)
            Wv[i] = x[y[i]];
        for (i = 0; i < m; i++)
            Ws[i] = 0;
        for (i = 0; i < len; i++)
            Ws[Wv[i]]++;
        for (i = 1; i < m; i++)
            Ws[i] += Ws[i - 1];
        for (i = len - 1; i >= 0; i--)
            sa[--Ws[Wv[i]]] = y[i];
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < len; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
}
void getheight()
{
    int i, j, k = 0;
    for (i = 1; i < len; i++)
        rank[sa[i]] = i;
    for (i = 0; i < len - 1; height[rank[i++]] = k)
        for (k ? k-- : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++);
}
bool check(int d)
{    
    for (int i = 0; i < len; )
    {
        memset(cnt, 0, sizeof(cnt));
        int j = i + 1;
        while (j < len && height[j] >= d)
            j++;
        for (int k = i; k < j; k++)
        {
            int l;
            for (l = 0; l < n; l++)
                if (sa[k] >= f[l] && sa[k] <= t[l])
                    break;
            if (l < n)
                cnt[l]++;
        }
        int l;
        for (l = 0; l < n; l++)
            if (!cnt[l])
                break;
        if (l == n)
            return true;
        else
            i = j;
    }
    return false;
}
int main()
{
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", &str[i]);
        f[i] = strlen(s);
        t[i] = f[i] + strlen(str[i]) - 1;
        strcat(s, str[i]);
        s[strlen(s)] = '$' + i;
    }
    len = strlen(s);
    getsa();
    getheight();
    int l = 0, r = len - 1;
    while (l < r - 1)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    if (check(r))
        printf("%d\n", r);
    else
        printf("%d\n", l);
    return 0;
}

题2.M序列(mseq)

问题描述

有一个非递减的整数序列 $S_1,S_2,S_3,\cdots\cdots,S_{n+1}(S_i \leq S_{i+1})$ 。定义序列 $m_1,m_2,\cdots,m_n$ 为 $S$ 的“ $M$ 序列”，其中 $m_i=\dfrac{S_i+S_{i+1}}{2}$ 。
例如， $S=(1,3,3,5)$ ，则 $m=(2,3,4)$ 。
现在给你序列 $m$ ，要你求有多少个 $S$ 序列的“ $M$ 序列”是序列 $m$ 。

输入格式

第一行一个整数 $n$ ，下接 $n$ 行，每行一个整数 $m_i$ 。

输出格式

一个整数，表示有多少个 $S$ 序列的“ $M$ 序列”是序列 $m$ 。

样例输入

样例输出

样例说明

存在如下四个数列 $S$ 满足要求：
$2,2,8,10$ ；
$1,3,7,11$ ；
$0,4,6,12$ ；
$-1,5,5,13$ 。

数据范围

$50\%$ 的数据 $n \leq 1000,m_i \leq 20000$ ；
$100\%$ 的数据 $2 \leq n \leq 100000,m_i \leq 10^9$ 。

题解

算法一

首先，我们可以发现，如果 $S_1$ 是已知的，那么结合 $M$ 序列，整个数组就确定了。因此，我们可以直接枚举 $S_1$ ，然后计算出整个序列，并判断是否是递增的。
时间复杂度 $O(nm)$ ，期望得分50分。

算法二

枚举太浪费了！我们把智商稍微拉高一点，直接用字母表示数。
比如，我们有了 $S_1$ ，那么 $S_2=2\times m_1 - S_1$ ， $S_3=2\times m_2 - S_2=2(m_2-m_1)+S_1$ ， $\cdots\cdots$
总结一下，

$S_i=2\sum_{j=1}^{i-1}(-1)^{i-j+1}+(-1)^{i-1}S_1$

然后，我们可以根据这些表示，推出数列递增对应的不等式。具体来说，我们用上面的式子表示出来 $S_j \leq S_{j+1}$ ，然后解不等式，取所有不等式解集的交集后，计算里面的整数个数。
事实上，这些不等式的形式都是相当简单的，解集的左右端点也都是整数。因此这题实现并不困难，详见代码。
时间复杂度 $O(n)$ ，期望得分100分。

#include <cstdio>
#include <algorithm>
#define INF 2000000000
using namespace std;
int c[100010];
int n;
int l, r;
int main()
{
    freopen("mseq.in", "r", stdin);
    freopen("mseq.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        c[i + 1] = 2 * x - c[i];
    }
    l = -INF, r = INF;
    for (int i = 1; i <= n; i++)
        if (i & 1)
            r = min(r, (c[i] - c[i - 1]) / 2);
        else
            l = max(l, (c[i - 1] - c[i]) / 2);
    if (r >= l)
        printf("%d\n", r - l + 1);
    else
        printf("0\n");
    return 0;
}

题3.竞技比赛(bnb)

问题描述

第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由 $n$ 名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手 $,$ 二号选手 $,\cdots\cdots,n$ 号选手捉对厮杀，共进行 $n$ 场比赛。每胜一场比赛得 $2$ 分，平一场得 $1$ 分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。
作为河南队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，河南队最终分别能得到多少分。

输入格式

输入文件的第一行为一个整数 $n$ ，表示每支代表队的人数。
接下来 $n$ 行，每行一个整数，描述了 $n$ 位河南队的选手的实力值。
接下来 $n$ 行，每行一个整数，描述了你的对手的 $n$ 位选手的实力值。

输出格式

输出文件中包括两个用空格隔开的整数，分别表示河南队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

样例输入1

样例输出1

2 0

样例说明1

我们分别称 $4$ 位选手为 $A,B,C,D$ 。则可能出现以下 $4$ 种对战方式，最好情况下可得 $2$ 分，最坏情况下得 $0$ 分。

样例输入2

样例输出2

12 12

样例说明2

对手都是认真学习的好孩子，不会打游戏。无论如何排列出场顺序都无法改变被蹂躏的结果。河南队总能取得全胜的结果。

数据范围

$20\%$ 的数据中， $1 \leq n \leq 10$ ；
$40\%$ 的数据中， $1 \leq n \leq 100$ ；
$60\%$ 的数据中， $1 \leq n \leq 1000$ ；
$1000\%$ 的数据中， $1 \leq n \leq 100000$ ，且所有选手的实力值在 $0$ 到 $10000000$ 之间。

题解

算法一

枚举所有排列，然后计算得分。
时间复杂度 $O(n\times n!)$ ，期望得分20分。

算法二

我们可以抽象出二分图的模型。河南的选手作为左侧点，外省选手作为右侧点，如果河南队的某个选手能胜过外省的某个选手，那么在二者之间连接一条权为2的边，如果实力值相同则连权为1的边，同时为了存在完美匹配，在河南选手打不过外省选手时连权值为0的边。之后跑一遍KM求出最大权完美匹配，就是第一问的答案。第二问的话可以把所有边权取成相反数，然后是KM，最后用 $2n$ 加上这时的最大权匹配的值（肯定不是正数）就是答案。
时间复杂度 $O(n^4)$ ，也可以达到 $O(n^3)$ ，但期望得分都是40分。

算法三

我们一个一个分析。对于河南省最弱的人，如果他可以打过外省最弱的人，那么就让他们打，这是最优的；对于河南省最强的人，如果他可以打过外省最强的人，那么就让他们打，这是最优的；如果两个条件都不成立，那么最弱的那个人无论如何都打不到分了，不妨利用“田忌赛马”的策略，让他和目前剩余的外省最强的人打。
不难证明，不存在比上述决策更优的决策，因此第一问可以直接输出结果。第二问的话，原理与算法二类似，将两支队伍交换，求出外省的最大得分 $x$ ， $2n-x$ 就是最终答案。因为每一句无论结果，两方的得分总和都会 $+2$ ，所以总分数一定，对方多，自己就少了。
时间复杂度： $O(nlogn)$ ，期望得分100分。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
int n;
int ha[100010], notha[100010]; 
inline int readint()
{
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    int x = c - '0';
    c = getchar();
    while (isdigit(c))
    {
        x = x * 10 + c -'0';
        c = getchar();
    }
    return x;
}
int main()
{
    freopen("bnb.in", "r", stdin);
    freopen("bnb.out", "w", stdout);
    n = readint();
    for (int i = 0; i < n; i++)
        ha[i] = readint();
    for (int i = 0; i < n; i++)
        notha[i] = readint();
    sort(ha, ha + n);
    sort(notha, notha + n);
    int l1 = 0, l2 = 0, r1 = n - 1, r2 = n - 1;
    int ans = 0;
    while (l1 <= r1)
    {
        if (ha[l1] > notha[l2])
        {
            l1++, l2++;
            ans += 2;
        }
        else if (ha[r1] > notha[r2])
        {
            r1--, r2--;
            ans += 2;
        }
        else
        {
            ans += (ha[l1] == notha[r2]);
            l1++, r2--;
        }
    }
    printf("%d ", ans);
    l1 = 0, l2 = 0, r1 = n - 1, r2 = n - 1;
    ans = 0;
    while (l1 <= r1)
    {
        if (notha[l1] > ha[l2])
        {
            l1++, l2++;
            ans += 2;
        }
        else if (notha[r1] > ha[r2])
        {
            r1--, r2--;
            ans += 2;
        }
        else
        {
            ans += (notha[l1] == ha[r2]);
            l1++, r2--;
        }
    }
    printf("%d\n", 2 * n - ans);
    return 0;
}

Hello World

April 10, 2016

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

Bloging with code snippet:

inline code

Plain Code

puts "Hello World!"

Code with Language

puts "Hello World!"

Code with Title

hello_world.rb

puts "Hello World!"

MathJax Example

Mathjax

$x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

Inline Mathjax

The answser is $a^2 + b^2 = c^2$ .

Table Example

Tables	Are	Cool
col 1	Hello	$1600
col 2	Hello	$12
col 3	Hello	$1