Hzao's Blog

CSP – S 2019游记

这是一篇流水账式游记。

主要写第二轮。

Day -1

今天巨佬搬过来和我坐了。

打了一些板子。

然后中途写题。

一道题都不会写。

wtcl。

Day 0

上午打了一点板子。学了一下单调队列优化多重背包。到现在也还没学斜率优化，如果像去年那样考个板子就很尴尬。

下午一点就出发了。

路上听了一些以前下的歌。把一直没听清楚的歌词看了一遍。忽然好喜欢你戳。

大概三点钟的时候到了神大对面的宾馆。简单收拾了东西之后写了一道博弈论的题。然而什么都没搞懂。

房间临水，水声听起来很舒服。

五点多和其他小朋友们出去吃饭。忽然想起去年的Day 0也是这个点去吃饭的呢。（我在走到图中同样的位置时截下了这张图。比去年早了8分钟）

晚饭吃的还算好，人均43.75。

拍这张图是想拿来让偷偷跑走的另外四位神犇犇嘴馋的。一时间觉得发了也没多大意思，就没发给他们了。

虽然其实写这个游记也没多大意思…

中午没睡觉，于是晚上吃饭的时候很晕很恶心，一度感觉自己不在状态。可能我需要一瓶脉动？

不在状态的时候居然被几对情侣虐了。于是在旁边的超市买了几块巧克力。

回到房间看了B站上一个关于Vae的互动视频。

于是就到现在了。现在（20:53）在补这篇游记从到达酒店开始的部分。

教练讲了一些注意事项。

希望明早的T1不要太难吧。就当成是参加了两天的面包矿泉水自助餐了。

希望明早起来就不头晕恶心了。

希望不要考我任务列表的最后这几点未完成任务。

然后用小凶凶的微博安慰一下自己。

放平静。

Day 1

晚上醒了几次，不过也还算好。有些时候晚上睡太饱会导致第二天频繁走神。

七点钟准时起了床，在宾馆旁边的店里吃了早饭。

在某谷打了卡。居然是中吉。kkk不是说一定会大吉的么？

看来特别设定的大吉都对我无效了。

wtcl。

爆零必不可免了。

忽然收到我妈微信发来的红包。原来今天是自己的农历生日呢。

半点和大佬们一起过天桥到对面的神大。不过已经来过两次了，没有很紧张。感受也和之前差不多。真的没有很紧张。

唯一的不同是，去年NOIP和今年省选不是禁止坐电梯上楼么，现在电梯居然被人占满了。

不过我依然走的楼梯。

考场在五楼。怕到时候人多，所以先在四楼上了个厕所。心里想着就算一道题都不会做也要多嫖一点考场的面包和矿泉水。怎料刚上楼面包和矿泉水就没了。

坐到位置上忽然觉得有点奇怪：这显示器为啥是正方形的？镇定一下才想起前两次来用的显示器都是正方形的。

旁边坐了一位很小很小的妹妹，应该是小学来的吧。最开始她都不知道怎么从FTP上下载试题。

我想起去年拿到压缩包的时候，我怎么输密码都解压不了。当时用普通话问了一下旁边的选手（还没到开考时间），可惜他似乎不太想理我。可能他在担心这是一种作弊行为？

这个时候我也有点犹豫，如果我就告诉她怎么下载会不会也被判为作弊？不过旁边的一位选手咳了几声，在自己的电脑上演示了一次。可惜小妹妹还是不懂。

折腾一会之后监考老师请还没看到题的选手举手。小妹妹手太短了。我跟监考老师对视了一眼，指了一下旁边的小妹妹。

那么就仁至义尽了。

这个时候我已经打开虚拟机，然后看了几眼题。

开考时间已到，监考老师开始传草稿纸。我坐在最左边，不幸的是传到最左边的草稿纸多了一张。我拿到了两张。可能是被CCF的禁赛警告搞自闭了，这个时候我心里想的全是“多拿草稿纸会不会被当成作弊然后被禁赛啊”之类的。

可惜监考老师跑后面传纸了。一直等到检查准考证我才给他说了这事。

“你拿着就是了。”

…

然后来说说做题。

先照例打了快读的和最值更新的函数。

读T1。题面有些长，没读完的时候以为要让我生成格雷码，瞬间有些慌：T1都这么难么？

不过还是和神奇的幻方一样，题目给出了生成方法。

第一感觉是，递归下去，每次n的规模减小1不就行了。

注意到题目范围给到了 $2^{64}-1$ 。嗯，不就是unsigned long long 吗，没关系。

在NOI Linux下用测评软件测试了一下自己的程序，99，OK，不用管了。

插播一下有关T1的后续：下午没事，听说牛客网可以测测。于是靠记忆敲了一次。用yms大佬给的数据才发现一个问题：我的算法用到了 $(1<<64)-1$ 这个运算。虽然结果在ull内，可惜中间结果溢出了。 $n =64$ 就必炸。交上去果然只有95分。

幸好原题也只有一个点满足 $n==64$ 。

说回考场。做完并且测完T1已经是8:55了。

然后做T2。看前两行，有点一道很经典的动态规划题（UVA1626，洛谷 P1241 ）的味道。可惜我很久没看过这道经典题了，第一次交的时候似乎也只是半懂。

不过这道题的区别在于，空串不能算作一个合法的括号串。

暂时没想到什么思路，只是隐约觉得一个位置能从前面的位置继承过来。看到有链的分，在想能不能推一个适用于链的转移方程。又想起前两天听到“大神经验分享”里，“大神”们要求无论如何都先把暴力打出来，然后再搞正解。

一时间几种选择摆在面前，还是有点慌的。但淡定了一下，决定再看看T3。然后又淡定地在虚拟机里把后面两道题的数据都配置在了Arbiter里。

这时候忽然脑海里有一个声音：这是D1啊，想想去年，应该T2是能做的吧。

于是开始专心做T2。先推了链上的情况，想到用栈来维护能和当前位置匹配的位置。既然要继承，第 $i$ 个位置的答案应该用之前的答案，加上以第 $i$ 个位置结尾的字串的答案。于是考虑用 $f[i]$ 表示以 $i$ 位置结尾能扩展多少个。然后乱糊了一通，期间前缀和乱入了，后来发现状态转移不需要前缀和，只是统计答案需要。

然后一想，既然是树形，深度优先遍历再加上回溯，不就可以让刚刚链上的方法适用了吗？

然后测了一下在Arbiter里测了一下T2，看样子应该是过了。

看了下时间，大概是10:11。

总觉得哪里不对，又反复测了一下T1和T2，然后检查文件名和输入输出。

然后就开始干T3了。

开始以为菊花图上的答案就是 $1,2,3, ..., n$ ，只需要不断把当前中心的那个数字 $x$ 放到编号 $x$ 相同的结点上就行了。不过似乎如果 $x$ 本身就在 $x$ 号结点上就不行了。

于是瞎搞链，乱贪心。

最后11:49才把样例的链过了。可惜第一阶梯的数据还没打暴力。

不过也懒得打了。

又在Arbiter里测了一下程序。又检查了几次文件名。差不多就颓到12:00了。

咦，我好像还没嫖到面包和矿泉水呢。

所以Day 1预估：95+100+(0~25)。也就195～210吧。

下午和几位巨佬玩了两个小时的4399大富翁。程序写的很精致，可惜设计有些问题。因为一个人死都不能破产。这个游戏似乎可以永远进行下去。

然后和lch julao玩了十几分钟森林冰火人。这个时候教练忽然来访……

教练走后在宾馆瞎逛，又遇到教练，被教练牵桥邀请和辰星凌巨佬散步。可惜辰星凌巨佬不想。

lch julao也不想。

再然后本来约了跟几位他校julao面基，后来julao不来了。我也就自己在神大里逛了逛。

天呐，好多情侣啊，我为什么要找虐。

还在神大里再次偶遇教练了woc。

lch julao等我回房间一起点外卖。于是我就掉头回了。再不回也受不了这些恶臭的情侣们了。

路上看Q群消息，同校的其他julao们出去吃饭了。

lch julao和我点了一些外卖。等外卖的时候我和他校另外两位julao在宾馆外谈笑风生。可惜他们只知道装弱。我实在无法和他们沟通了。

忽然发现这个游记的流水账太流水了。还有些细节就不谈了吧。

22:12。今天就写到这里。

Day 2

昨晚睡觉前居然流了鼻血。

看来我必然会爆零了。

大吉。

很惊喜的是外面起了很大的雾。

昨天的题把比我强一些的大佬们的分卡到和我差不多的样子了。但今天心里还是有点忐忑。

很高兴成功嫖到了场地提供的两个小面包。

和昨天完全相反。今天草稿纸传到我这里就没了。主动向监考老师要了一张。

周围没什么键盘声。我想敲，恐禁三。

于是就只是默默开了虚拟机，改了一下IDE的配色。

奶了一口今天的密码： 9Zi%Xi*DuTi! ，可惜是抓紧时间。

非常失望。于是开始干题。

通读整个题面，T2和T3题意似乎很好懂。

但想的是T1应该能拿满吧，于是开始干T1。很可惜的是DP方程推不出来，暴力搜索打不出去。一直搞到9:40左右。开始慌了。

这个时候感觉马上要做出来了，但就是做不出来。心跳忽然加速，有一种绝望的感觉。我D2不会就这么爆零了吧。

尝试深呼吸，一度引来右边小妹妹迷惑的目光。

然并卵。

遂决定出考场走走。向老师请假上了个厕所。

回来的时候心跳差不多平静了。决定先放弃第一题。

看了下T2，打了一个 $n^3$ 的暴力。在Arbiter里测试了一下，应该可以拿到 $\frac{9}{25}$ 的分数。

此时大概十点多吧。

被刚刚的T1整怕了，不敢回头去做。所以开始做第三题了。

嗯，我一定不要先想正解。我一定要先打暴力。否则又会像T1那么惨不忍睹。

于是打了一下暴力。忘了打完是几点了。好像还挺早的。

又在Arbiter里测试了一下。暴力分应该稳了。

打完两道题的暴力，心情稍微好了一点。又看了一下几个特殊点，发现T3链上的情况可以 $O(n)$ 做。又花了点时间打链上的分。Arbiter里测试通过。

这个时候大概是11:30。嗯，把目标定小一点就很空闲了。

这个时候心情差不多更好了，所以回头去看了第一题。最开始迟迟没把第一做出来，就是因为自己非要想把暴力优化一下。这么一想，我决定开始打纯暴力。时间复杂度大概是 $O(m^n)$ 吧。过了前两个样例，开心。

可惜没过第三个小样例。

这个时候，乱检查了一下，加了一个 $a[i][j]=0$ 的判断，过了。但是我想，我的这个算法加不加判断都无所谓啊。

忽然发现其实是一个地方数组只开了3的大小。虽然这个复杂度只能过 $m=3$ 的数据，但是后来我把整个数组下标右移了。

然后再次测了一下。T3有 $\frac{11}{20}$ 的分吧。此时大概是11:55？真险。

反复在Arbiter里测试了一下三道题，非常担心这个垃圾软件因为刷新不及时迷惑我的眼睛。手动刷新了几次，应该可以确认无误了。

今天的预估分数就是：32+36+55=123.（所以应该倒序开题！）

两天一共：95+100+(0~25)+32+36+55=(318~343)=AFO。

好了。中午吃了碗兰州拉面，回房间收拾东西，坐了一会之后就上车回学校了。

下午放假。打了支疫苗。回家。

那就等分数出来了再更。（我打赌今年CCF又会在出初评成绩的时候咕咕咕几下。）

Day 3

今天教练来文化课班里说程序已经公开了，要给我们发程序。

晚上回家发现他忘了。没发。

在几个OI群里问程序，没人有。

聪明的我想到，如果有人拿到了SC源程序，应该会在洛谷的讨论区里发吧。所以就一页一页地往前翻今天的讨论，果然看到了SC的源码。

重新下回来电报，然后在笔记本里解压。等等，为什么我的D1T1代码是空的？有文件没有代码这种。注意这里面的code是0字节。

我解压又删除了整整三次，都是一样的结果。

他说我刚刚修改过，但是我解压完就是这样子。真的没有修改过啊。而且只有00153和00154的代码是这样的。

我差点被吓死了。

然后非常淡定地打开台式电脑的Windows 10，传包，解压。

太好了，发现自己的代码还在。

在洛谷交了一发，居然有350分。我自己都不信。

在nowcoder交了一发，318，刚好是我自己估分的下限。（看上文，我估的分数是318～343，这25分的差距来自于D1T3链上的情况）

现在也就坐等官方数据公开了。

早睡身体好。

~~to be continued~~..

2019 12 04，下午第三节课到机房收拾东西顺便更新：

1号晚上就查了分了，一直没更新这篇游记。318。果然AFO了。

这大概是最后一次所有人都坐满机房了吧。

大佬们还是和以前一样颓游戏，颓知乎，虐题库。

还是挺感慨的。

OI生涯总算告一段落了。

不过结束就是新的起点吧。

想起初中毕业那天上线并且在毕业晚会上放过的歌：

等到记忆只剩精华等到笑容不掺伪装我们相约老地方

等到人已不再奔忙等到心也不再轻狂我们相约老地方

THE END

题解 UVA11361 【Investigating Div-Sum Property】

数位DP，对于每一个询问，回答为 $ask(B)-ask(A-1).$

我主要想分享一下一些实现上的细节。但还是先说一下思路，这里借鉴了《算法竞赛入门经典:训练指南》的讲解。

设 $f(w,m_1,m_2)$ 表示有 $w$ 位数（可以有前导 $0$ ）需要确定，需要让各位数字之和除以 $K$ 的余数为 $m_1$ ，需要让这 $w$ 位数组成的数字除以 $K$ 的余数为 $m_2$ 需要的方案数。然后我们一步一步确定前面几位数，加起来得到答案。

显然，我们可以从 $0$ 到 $9$ 枚举最高位上的数字 $head$ ，从而有:

$f(w,m_1,m_2)=\sum f(w-1,(m_1 - head)mod \, K,(m_2 - 10^{w-1}head)mod \,K).$

边界: $f(0,0,0)=1$ ， $f(0,m_1 ≠0,m_2≠ 0)=0.$

理解：要让 $w$ 位数各个位之和 $mod \, K$ 为 $m_1$ ，且第一位为 $head$ ，那么肯定需要没有 $head$ 的时候 $mod \, K$ 的值为为 $(m_1-head)mod \, K$ 。第三个参数亦然。

几个细节：

$1.$ 记忆化搜索，那么时间复杂度为 $O(ws* K^2).$ 可是 $K$ 这么大怎么办？

如果 $ask(val)$ 中 $val$ 有 $ws$ 位数，但是 $K > 9* ws$ ，显然没有合法的数字。因为所有位加起来都没有 $K$ 那么大，肯定加起来之后不能整除 $K$ .

所以题中数据范围给那么大是没用的…..

于是可以用数组来记搜，数字最多十位数，所以 $K>9 * 10 =90$ 时肯定是无解的。数组可以开得下。

$2.$ $val=0$ 时答案为 $1$ 不为 $0$ 。

$3.$ 可以先让 $val=val+1$ ，然后紧贴 $val$ 求解答案，需要同时记录已经有的各位数字之和和总的数字之和。

还有一些细节见代码：

#include<cmath>
#include<cstdio>
#include<cstring>
template<typename T>
inline bool read(T &x){
    x=0;char c;T  f=1;
    do{c=getchar();if(c=='-')f=-1;else if(c==EOF)return false;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    return x*=f,true;
}
long long A,B,K;
long long tp[20];//tp[i]表示10 的i次方
long long Div[20];
long long d[20][200][200];

#define res1 (d[w][m1][m2])
long long f(int w,int m1,int m2){
    if(w==0){
        return m1==0&&m2==0;
    }
    if(~d[w][m1][m2])return d[w][m1][m2];
    res1=0;
    for(register int  i=0;i<=9;++i){
        //i即为前所述的head 即最高位的数字
        res1+=f(w-1,(m1-i%K+K)%K,(m2-(1ll*tp[w-1]*i%K)+K)%K);
        //必须保证mod K之前为非负数 所以加上一个K 
    }
    return res1;
}
long long Getws(long long val){//分割这个数，并且返回它的位数

    if(!val){//其实这步可以不要。毕竟在GetAns()的入口处特判了0的情况
        return Div[0]=(Div[1]=0)+1;
    }
    Div[0]=0;
    while(val){
        Div[++Div[0]]=val%10;
        val/=10;
    }
    return  Div[0];
}
long long GetAns(long long val){
    if(!val)return 1ll;
    long long res=0;
    ++val;
    //紧贴val来计算答案，如果不加1会漏掉val这个数
    //当然也可以不加1，最后特判val这个数
    long long ws=Getws(val);
    if(ws*9<K)return 1ll;
    long long presum=0,presum2=0;
    //presum：当前累计的各位数字之和 如322的presum=3+2+2=7
    //presum2：当前已确定数字组成的数：如32***的presum2=32000.
    for(register int  i=ws;i>=1;--i){
        for(register int  j=0;j<Div[i];++j){
            if(j)presum+=1;presum%=K;
            if(j)presum2+=tp[i-1];presum2%=K;
            //presum,presum2每步取模更方便
            res+=f(i-1,(K-presum+K)%K,(K-presum2+K)%K);
            //此处有减法，必须保证它是非负数
        }
        //紧贴val来取值，则最高一位没有被讨论到
        //例如，如果val=32565
        //如果已经枚举到第二位
        //那么实际上我们暂时只会先考虑30***和31***的情况
        //但在后面的讨论中，应保证第二位为2
        //所以还要把2的贡献累加进去
        if(Div[i]){
            ++presum;
            presum2+=tp[i-1];
        }
    }
    return res;
}
void  work(){
    // GetAdd();
    long long ans=GetAns(B)-GetAns(A-1);
    printf("%lld\n",ans);
}
int main(){
    //freopen("testin.txt","r",stdin);
    //freopen("testout.txt","w",stdout);
    tp[0]=1;
    for(register int  i=1;i<=15;++i){
        tp[i]=10ll*tp[i-1];
    }
    long long T;
    read(T);
    while(T--){
        read(A);
        read(B);
        read(K);
        memset(d,-1,sizeof(d));
        work();
    }

    return 0;
}

题解 UVA1073 【Glenbow Museum】

如果有一个点能看到各个顶点，那么这个点的上下左右一定要对应四个 $RR$ 。

如果有 $OO$ ，那么这两个 $270$ °的角延伸出去的角的可视范围没有交集，即它们不能被同时被看到（点 $A$ 能看到点 $B$ ，那么点 $B$ 也能看到点 $A$ 。反之 $B$ 一定不能看到点 $A$ ），如下图所示：（延伸出去的角可能是 $R$ 也可能是 $O$ ，这里以 $R$ 为例）

所以一定不能有 $OO$ 。

如果没有 $OO$ ，但是有 $OR$ 。那么 $OR$ 前面一个字符一定是 $R$ 。（否则就有 $OO$ 了）。这 $O,R$ 两个角的可视范围是有交集的。如下图所示：

同样地，相邻的 $RR$ 两角的可视范围也是有交集的。至少它们两个角是可以被同时看到的。

如果一个点能看到所有内角，那么它的正对的上下左右一定都是 $RR$ 。因为如果某个方向是 $RR$ ，显然成立。如果某个方向上的角度序列有 $OR$ ，那么这个方向的角度序列只能是 $OROROR…ORR$ 。即只能以 $RR$ 结尾。（如果一直不结尾，那就不构成多边形。如果以 $OO$ 结尾，那么不合法）。

既然以 $RR$ 结尾，那么能同时看到这个 $RR$ 的点一定在如图所示的灰色区域。

反过来说，一个点的正对的上下左右四个方向一定是 $RR$ 。

稍加思考可以发现，只要满足上下左右四个方法有 $RR$ ，且整个序列没有 $OO$ ，那么一定满足条件。(没有 $OO$ 意味着不会往外拐)

$L$ 个内角代表 $L$ 条边，根据多边形内角和公式：
$90R+270O=(L-2)* 180.$

又因为 $R+O=L.$

所以有 $R=(L+4)/2,O=(L-4)/2.$

所以我们要求的就是 $(L+4)/2$ 个 $R$ 和 $(L-4)/2$ 个 $R$ 的字符串中，有至少四个 $RR$ 且没有 $OO$ 的个数。注意 $L<4$ 或者 $L$ 为奇数时无解。（为奇数时的内角和不为 $180$ °的整数倍）

前两个实现方法参考《算法竞赛入门经典：训练指南》:

方法一：

用 $f(i,j,b,e)$ 表示有 $i$ 个 $R$ ， $j$ 个 $O$ ，开头为 $b$ （ $0$ 表示 $R$ ， $1$ 表示 $O$ ），结尾为 $e$ 。

则 $f(x,0,0,0)=f(0,1,1,1)=1,x > 0.$

且 $f(i,j,b,0)=f(i-1,j,b,1)+f(i-1,j,b,0).$

$f(i,j,b,1)=f(i,j-1,b,0).$ （不能出现 $OO$ ）

答案就很显然了（把几个 $f(i,j,b,e)$ 加起来），你可以自行推一推或者见代码。

递归加上记忆化即可 $O(n)$ 解决。（直接递推则需 $O(n^2)$ ）

代码：

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2][2];
long long f(int i,int j,int b,int e){
    if(~d[i][j][b][e]){
        return d[i][j][b][e];
    }
    if(!j){
        return i&&!b&&!e;
    }
    if(!i){
        return j==1&&b==1&&e==1;
    }
    if(e){
        return d[i][j][b][e]=f(i,j-1,b,0);
    }
    else{
        return d[i][j][b][e]=f(i-1,j,b,0)+f(i-1,j,b,1);
    }
}
int main(){
    memset(d,-1,sizeof(d));
    long long ans;
    while(~scanf("%d",&L)&&L){
        ans=0;
        if(!(L&1||L<4)){
            ans+=f((L+4)/2,(L-4)/2,0,0);
            ans+=f((L+4)/2,(L-4)/2,1,0);
            ans+=f((L+4)/2,(L-4)/2,0,1);
        }
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}

方法二：

$d(i,j,k)$ 表示以 $k$ 开头，有 $i$ 个 $R$ ，有 $j$ 对相邻的 $R$ （ $RRR$ 算两对， $ROR$ 算 $0$ 对），且以 $R$ 结尾的方案数。

则 $d(1,0,0)=d(1,0,1)=1.$

其余 $d(i,j,k)=d(i-1,j,k)+d(i-1,j-1,k)$ .表示当前字符串可由某个 $R$ 结尾的字符加上 $OR$ 或 $R$ 来得到。

设 $A=(L+4)/2$ 。

答案是 $d(A,4,1)+d(A,3,0)+d(A,4,0).$

第一项表示 $O$ 开头 $R$ 结尾。

第二项表示 $R$ 开头 $R$ 结尾。求的是字符串中只有 $3$ 对 $RR$ 。但是把开头和结尾这一对算上就有 $4$ 对了。

第三项很难理解，它表示 $R$ 开头 $O$ 结尾。每一个 $R$ 开头 $O$ 结尾的合法字符串都对应一个把最后一个 $O$ 去掉之后的， $R$ 开头 $R$ 结尾的字符串。因为最后一个字符是 $O$ ，不能和前面的 $R$ 接在一起，所以需要保证前面就有 $4$ 个 $R$ 。

也就是说把 $4$ 个 $RR$ 对的 $R$ 开头 $R$ 结尾的字符串后面加上一个 $O$ 就可以得到 $4$ 个 $RR$ 对的 $R$ 开头 $O$ 结尾的字符串。

代码：

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2];
long long f(int i,int j,int k){
    if(i==1){
        return !j;
    }
    if(~d[i][j][k])return d[i][j][k];
    return d[i][j][k]=f(i-1,j,k)+f(i-1,j-1,k);
}
int main(){
    memset(d,-1,sizeof(d));
    while(~scanf("%d",&L)&&L){
        if(L&1||L<4){
            printf("Case %d: 0\n",++kase);
            continue;
        }
        printf("Case %d: %lld\n",++kase,
            f((L+4)/2,3,0)+//R...R
            f((L+4)/2,4,1)+//O...R
            f((L+4)/2,4,0)  //R...O
        );
    }
    return 0;
}

方法三：（参考了KobeDuu的博客）

组合计数。

其实可以发现，只要有 $A=(L+4)/2$ 个 $R$ ， $B=(L-4)/2$ 个 $O$ (其实 $B=A-4$ )，并且 $OO$ 不相连，那么一定可以保证有4个 $RR$ 对。

可以这样想：把 $A \ge 4$ 个 $R$ 连成一个环，那么有 $A$ 个 $RR$ 对。

再把 $B=A-4$ 个 $O$ 插入，每插入一个 $O$ ，就会少一个 $RR$ 对。

所以最后剩下 $A-B=4$ 个 $RR$ 对。刚好满足条件。

所以可以这样利用组合数算,把所有 $RR$ 排成一行之后：

$1.$ 在开头放 $O$

那么，最后一个位置不能放 $O$ 。剩下 $A-1$ 个位置可以放，要放下 $B-1$ 个 $O$ 。

计数 $C_{A-1}^{B-1}$

$2.$ 不在开头放 $O$

那么剩下 $A$ 个位置可以放 $B$ 个 $O$ 。
计数 $C_{A}^{B}.$

所以答案为 $C_{A-1}^{B-1}+C_{A}^{B}.$

代码太简单就略了吧。

祝AC。

题解 UVA11806 【Cheerleaders】

以下内容中 $C_{n}^{m}$ 表示组合数。

考虑四角上四个点的情况:

$1.$ 四个角都不放人。

显然需要枚举最外圈（第一行、最后一行、第一列、最后一列的并集）除开四个角之外的放置方案。

设第一列、最后一列、第一行、最后一行中除开第一个位置和最后一个位置分别放置 $j_1,j_2,k_1,k_2$ 个人，那么它们分别有： $C_{n-2} ^{j_1},C_{n-2}^{j_2}, C_{m-2}^{k_1},C_{m-2}^{k_2}$ 种放置方法。(需要保证 $1 \leq j_1,j_2,k_1,k_2 <k$ 且 $j_1+j_2+k_1+k_2 \leq k$ )

除开最外圈，里面还剩下 $left=k-(j_1+j_2+k_1+k_2)$ 个人，需要把他们放置在中间共 $(m-2) (n-2)$ 个位置上。有 $C_{(m-2) (n-2)}^{left}$ 种方法。

所以一共有 $( \sum C_{n-2}^{j_1} C_{n-2}^{j_2} C_{m-2}^{k_1} C_{m-2}^{k_2}) C_{(m-2) (n-2)}^{left}$ 种方案。

(也就是说要枚举 $j_1,j_2,k_1,k_2$ )

$2.$ 仅一个角放人。 那么又有四种情况:左上、左下、右上、右下。显然这四种是等价的，求一种之后乘以 $4$ 即为答案。

为了方便讲述，假设选择了左上的那一个角。

那么第一行、第一列都不需要找了。为了使方案合法，我们需要一种方案，使得最后一行、最后一列都有人。

因为左下、右上、右下都不放人，所以最后一列 $n-2$ 个位置中至少要选择一个人，最后一行 $m-2$ 个位置中要选择至少一个人。

假设最后一列放 $j_1$ 个人，最后一行放 $k_1$ 个人，那么方案数为 $C_{n-2}^{j_1} C_{m-2}^{k_1}$ .

除去左上角一个点、最后一整列、最后一整行，还剩下 $(m-1) (n-1)-1$ 个点可以放人，还剩下 $k-j_1-k_1-1$ 个人需要放。

于是放这剩下的 $k-j_1-k_1-1$ 个人就有 $C_{(m-1) (n-1)-1}^{k-j_1-k_1-1}$ 种方法。

于是这种情况下有 $(\sum C_{n-2}^{j_1} C_{m-2}^{k_1}) C_{(m-1) (n-1)-1} ^ { k-j_1-k_1-1}$ 种方法。

3.有且只有两个角放人。

假设这两个人不在同一对角线上 ：

那么只有在 $n>2$ 时才能在左上左下、右上右下放置。只有在 $m>2$ 时才能在左上右上、左下右下放置。(否则若要满足情况，则不止要放 $2$ 个角)。

假设 $n>2$ 且在左上左下(或者右上右下)放置，那么只有最后一列(或者第一列)没有被覆盖了。我们需要在最后一列(或者第一列)的 $n-2$ 个位置上选出至少一个人来参与。设选择 $j$ 人，那么方案数为 $C_{n-2}^{j}$ 。

还剩下 $left=k-2-j$ 个人，放置在 $nm-2-n$ 个位置。

方案数为 $(\sum C_{n-2}^{j}) C_{n m-2-n}^{left}$ 。
由于可以选左上左下或者右上右下，所以需要把这个玩意乘以 $2$ 。

同理，如果 $m>2$ 且选择左上右上（或者左下右下)，给最后一行（或者第一行）放置 $j$ 个人，那么方案数共为： $(\sum C_{m-2}^{j}) C_{n m-2-m}^{left}$ 。同样需要计数时乘以 $2$ 。

假设在同一对角线上：

除了四个角，每个位置都可以放置，方案数为 $C_{n m-4}^{k-2}$ 。在对角线上有两种情况（左上右下，左下右上），所以这个数也要乘以 $2$ 。

4.有且只有三个角放人。

那么无论怎么放，都是满足条件的。
$4$ 个点中选出 $3$ 个有 $C_{4}^{3}$ 种方法，除开四角有 $C_{n m - 4}^{k-3}$ 种方法。

所以计数： $C_{4}^{3}C_{nm-4}^{k-3}$ 。

5.所有角都放人。

那么所有角都放人有一种方法，除开这四个角共有 $C_{n m -4}^{k-4}$ 种方法，所以计数 $C_{nm-4}^{k-4}$ 。

当然要记得每步取模。

代码:

#include<cstdio>
#include<cstring>
// #define LOC

const long long mod=1000007;
long long C[505][505];
long long n,m,k;
long long ans;
long long T;
int kase;
void init(){
    C[0][0]=1;
    for(register int i=1;i<=500;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
            // printf("C[%d][%d]=%lld\n",i,j,C[i][j]);
        }
    }
}

void work(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ans=0;
    if(m*n>=k){
        {//四个角都不放人
            for(register int j1=1;j1<=n-2;++j1){
                if(j1>=k)continue;
                for(register int j2=1;j2<=n-2;++j2){
                    if(j1+j2>=k)continue;
                    for(register int k1=1;k1<=m-2;++k1){
                        if(j1+j2+k1>=k)continue;
                        for(register int k2=1;k2<=m-2;++k2){
                            if(j1+j2+k1+k2>k)continue;
                            ans+=C[n-2][j1]*C[n-2][j2]%mod*C[m-2][k1]%mod*C[m-2][k2]%mod*C[(m-2)*(n-2)][k-(j1+j2+k1+k2)]%mod;
                            ans%=mod;
                        }
                    }
                }
            }
            ans%=mod;
        }

        {// 一个角上放人
            for(register int j1=1;j1<=n-2&&j1<k;++j1){
                for(register int k1=1;k1<=m-2;++k1){
                    if(j1+k1+1>k)continue;
                    ans+=C[n-2][j1]*C[m-2][k1]%mod*C[(m-1)*(n-1)-1][k-1-j1-k1]%mod*4%mod;
                    ans%=mod;
                }
            }
            ans%=mod;
        }

        {//左上左下或者右上右下放置
            for(register int j=1;j<=n-2&&j<=k-2;++j){
                ans+=C[n-2][j]*C[m*n-n-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }

        {//左上右上或者左下右下放置
            for(register int j=1;j<=m-2&&j<=k-2;++j){
                ans+=C[m-2][j]*C[m*n-m-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }


        if(k>=2){//对角线上放置
            ans+=2*C[m*n-4][k-2];
            ans%=mod;
        }

        if(k>=3){//三个角都放
            ans+=C[4][3]*C[m*n-4][k-3]%mod;
            ans%=mod;
        }

        if(k>=4){//四个角都放
            ans+=C[m*n-4][k-4];
            ans%=mod;
        }
    }
    printf("Case %d: %lld\n",++kase,ans);
}
int main(){
    scanf("%lld",&T);
    init();
    while(T--){
        work();
    }
    return 0;
}

早睡身体好

去年今天我第一次来3-2机房。

回翻手机相册发现自己记下好多没用的东西。

/*******/

好多惊喜统统镇定

删掉一半应用把复杂消融成简单

早睡身体好

几道水题的题解

这篇文章包含了这几道简单题的题解：

逆序排列

给出 $2$ 个数 $n$ 和 $k$ ，求 $1~n$ 的全排列中，逆序数为 $k$ 的排列有多少种。每个测试点包含 $T$ 组数据。
$1 \leq T \leq 10000, 2 \leq n \leq 1000, 0 \leq k \leq 20000$

$1$ 到 $n$ 的全排列有 $n!$ 个，每个测试点的数据组数很多。考虑动态规划。

和1296 有限制的排列一样，假如以“当前考虑到 $1$ 到 $N$ 的全排列的第 $i$ 位，且逆序对数为 $j$ 的排列个数”来定义状态 $d[i][j]$ ，必然会困于如何去重。即使找到去除重复数字的方法，也会导致时间复杂度偏高。

因此我们这样简化状态：定义 $d[i][j]$ 为 $1$ 到 $i$ 的全排列中，逆序对数为 $j$ 的排列数。可以发现 $d[n][j]$ 仍然包含了所需要的状态。

如何由 $1$ 到 $(i-1)$ 的全排列转移到 $1$ 到 $i$ 的全排列？怎么保证没有重复的数字？假如新排列第 $i$ 位是 $j$ ，这些新排列和 $1$ 到 $(i-1)$ 的全排列的关系是什么？

借鉴 1296 有限制的排列的思想（这两道题的在思想上很相像），我们可以把每一个 $1$ 到 $(i-1)$ 的全排列通过以下方式变成一个长度为 $i$ ，且最后一位为 $j$ 的全排列：

将原排列中，大于等于 $j$ 的数加上1；
在最后添上 $j$ 。

可以发现每个 $1$ 到 $(i-1)$ 的全排列都可以转化为各不相同的长度为 $i$ ，且最后一位为 $j$ 的全排列。（从数学上理解，最后一位确定，前 $i-1$ 位的排列数为 $(i-1)!$ ，也就是 $1$ 到 $(i-1)$ 的全排列个数。）

在理解上述内容的基础上，我们可以得到状态转移方程:

$d[i][j]=\sum_{k=1}^i d[i-1][j-(i-1-k+1)] = \sum_{k=1}^i d[i-1][j-(i-k)]$

在给第 $i$ 位填上 $k$ 后，前面大于 $k$ 的 $i-k$ 个数就会和 $k$ 构成逆序对。因此需要满足在转移之前有 $j-(i-k)$ 个逆序对。注意，这里计算的大于 $k$ 的个数，是指新排列中大于 $k$ 的个数。即在长度为 $i-1$ 的原排列中大于等于 $k$ 的个数。

由于频繁求区间和，可以考虑维护前缀和。长度为 $i$ 的全排列的状态只与长度为 $i-1$ 的全排列的状态有关，所以考虑滚动数组。

时间复杂度 $O(nk+TlogT)$

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const long long maxn=1000,mod=1e9 + 7;
long long n,k,done=1;
long long ans[10*maxn+5];
long long sum[2][20005];
struct qst{
    long long n,k,id;
}Q[maxn*10+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{
        c=getchar();if(c=='-')f=-1;
    }
    while(c>'9'||c<'0');
    do{
        x=x*10+c-'0';c=getchar();
    }
    while(c>='0'&&c<='9');
    x*=f;
}
inline long long max(long long a,long long b){
    return a>b?a:b;
}
long long d[2][20005];
void work(){
    d[0][0]=1;
    sum[0][0]=1;
    for(register int i=1;i<=k;++i){
        sum[0][i]=1;
    }
    for(register long long i=1;i<=n;++i){
        for(register long long nk=0;nk<=k;++nk){
            d[i&1][nk]=0;
            d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod;
            if(i==Q[done].n&&nk==Q[done].k){
                ans[Q[done++].id]=d[i&1][nk];
            }
            sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod;
        }
    }
}
inline bool cmp(qst a,qst b){
    if(a.n!=b.n)return a.n<b.n;
    return a.k<b.k;
}
int main(){
    long long T;
    read(T);
    for(register long long i=1;i<=T;++i){
        read(Q[i].n);
        read(Q[i].k);
        n=max(n,Q[i].n);
        k=max(k,Q[i].k);
        Q[i].id=i;
    }
    sort(Q+1,Q+1+T,cmp);
    work();
    for(register long long i=1;i<=T;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

最长递增路径

一个无向图，可能有自环，有重边，每条边有一个边权。你可以从任何点出发，任何点结束，可以经过同一个点任意次。但是不能经过同一条边2次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。
$1 \leq N \leq 50000, 0 \leq M \leq 50000, 0 \leq W \leq 10^9$

有点像最长上升子序列，只不过是在图上。

考虑将每条无向边拆成两条有向边，按照边的大小排序，由于一条路径走过后不能再走，所以没有后效性。

每次从边 $a$ 转移到边 $b$ ，需要满足两个条件：

$a$ 的终点是 $b$ 的起点。
$a$ 的长度必须严格小于 $b$ 的。

考虑用数组 $maxb[]$ 保存每个节点作为终点的，已经走过的最长的边数。那么通过某条边从一个点 $u$ 走向另一个点 $v$ 时，可以用 $maxb[u]+1$ 来更新 $maxb[v]$ 。为了满足第二点，我们可以以边长为标准分段，将某几条长度相同的边处理完之后，再一起更新这些边更新过的 $maxb[]$ 。

时间复杂度 $O(mlogm)$

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int maxn=5e4;
struct line{
    int u,v,w;
}l[maxn*2+5];
int ans;
int d[maxn*2+5],maxb[maxn+5];
inline void read(int &x){
    x=0;char c;int f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
inline bool cmp(line a,line b){
    return a.w<b.w;
}
int n,m;

int main(){
    read(n);read(m);
    for(register int i=1;i<=m;++i){
        read(l[i].u);read(l[i].v);read(l[i].w);
        l[i+m].w=l[i].w;
        l[i+m].u=l[i].v;
        l[i+m].v=l[i].u;
    }
    sort(l+1,l+1+2*m,cmp);
    int lst=1;
    for(register int i=1;i<=2*m;++i){
        if(l[i].w!=l[lst].w){
            for(register int j=lst;j<i;++j){
                maxb[l[j].v]=std::max(maxb[l[j].v],d[j]);
            }
            lst=i;
        }
        d[i]=maxb[l[i].u]+1;
        if(d[i]>ans)ans=d[i];
    }
    printf("%d\n",ans);
    return 0;
}

选数字

当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。每个测试点包含不超过20组数据， $1 \leq n \leq1000,2 \leq K \leq 100000000$

很显然是一道动态规划题。

读入一个数字，就可以用它与前面的数字能构成的数来构成新的数（或者给已有的数增加方案数）。这算是最普通的做法。

给出一种优化：

读入 $a[i]$ 时，假如 $k \bmod a[i]\ne0$ ，则直接忽略，读入下一个数字。
用 $a[i]$ 与之前已经生成的某个数 $x$ 构成新的数时，若 $k \bmod (x*a[i])\ne0$ 则跳过。

这样我们就可以保证，所有存入的数都是尽可能对答案有帮助的。因为假如一个数不能整除 $k$ ，必然不可能对答案造成影响。

在 $a[i]$ 与已有的数来更新新的数时，应该将所有的修改都保存起来，等到更新完了之后再应用更新。什么意思呢？假如读入了一个数 $3$ ，之前已经有了 ${2,6,18}$ 这三个数，且构成这三个数的方案数分别为 ${1,2,3}$ 。由我们的推算可知，加入 $3$ 后，可以由 $2*3$ 来使构成 $6$ 的方案数加 $1$ ，由 $6*3$ 使构成 $18$ 的方案数加 $1$ ，由 $18*3$ 使构成 $54$ 的方案数加 $1$ 。加上 $3$ 本身，处理之后的已有数字和方案数分别为： ${2,3,6,18,54}$ 和 ${1,1,3,4,1}$ 。但是如果我们边处理边更新，会导致同一个 $3$ 被重复计算。给 $6$ 的方案数加1后，新增的这个已经用过 $3$ 的方案，又与 $3$ 一起更新了 $18$ 的答案。所以应该把每次要修改的操作保存起来，把所有的待更新数更新完毕后，再应用修改到方案数组中。

由于 $k$ 较大，可能出现的数字不定，所以可以通过 $STL map$ 来作为数组。

时间复杂度大概是 $O(n log k)$ 。

#include<cstdio>
#include<map>
using std::map;
const long long maxn=1e3;
const long long mod=1000000007;
long long n,k;
long long a[maxn+5];
map<long long,long long>d;
map<long long,bool> ment;
long long mentd[maxn+5];
struct addo{
    long long to,val;
    addo(long long to=0,long long val=0):to(to),val(val){}
}add[maxn+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
void work(){
    for(register long long i=1;i<=n;++i){
        read(a[i]);
        if(k%a[i]!=0)continue;
        long long lmentd=mentd[0],tadd=0;
        for(register long long j=1,y;j<=lmentd;++j){
            if(k%(y=a[i]*mentd[j])!=0)continue;
            add[++tadd]=addo(y,d[mentd[j]]);
            if(!ment[y]){
                mentd[++mentd[0]]=y;
                ment[y]=true;
            }
        }
        for(register long long j=1;j<=tadd;++j){
            d[add[j].to]+=add[j].val;
            d[add[j].to]%=mod;
        }
        d[a[i]]++;
        d[a[i]]%=mod;
        if(!ment[a[i]]){
            mentd[++mentd[0]]=a[i];
            ment[a[i]]=true;
        }
    }
    printf("%lld\n",d[k]);
}
int main(){
    long long T;
    read(T);
    while(T--){
        read(n);read(k);
        work();
        if(T){
           ment.clear();
           mentd[0]=0;
        }
    }
    return 0;
}

整数划分

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。
$1 \leq N \leq 50000$

当成一个0/1背包问题， $1$ 到 $N$ 每个数是一件物品，背包的容积为 $N$ 。把普通背包（求最大价值）改为求价值之和即可。

但是这种做法的时间复杂度为 $O(N^2)$ ，很显然过不了此题的数据范围。

考虑用 $g[i][j]$ 表示考虑用 $i$ 个数构成 $j$ 的方案数。要求用的数各不相同，所以应该保证构造的数不出现重复。

用 $g[i][j]$ 表示用 $j$ 个数构成i的方案数，由于每个数各不相同，最多的数的个数 $m$ 满足 $(1+2+...+m=n)$ 。计算得知 $m_{max}=316$ 。

用 $i$ 个数字来组成 $j$ ，假如不选择数字 $1$ ，那么方案数为 $g[i][j-i]$ ，也就是把构成 $j-i$ 的 $i$ 个数每个都加上 $1$ ；假如要选择数字 $1$ ，为了保证前面没有数字 $1$ （题目要求所有数不相同），我们需要把前面 $i-1$ 个数加上1，再给最后一位放一个 $1$ 。方案数就是 $g[i-1][j-i]$ （前 $i-1$ 位构成 $j-i$ ）。

选择 $1$ 和不选择 $1$ ，包含了所有的情况。

于是我们得到状态转移方程：

$g[i][j]=g[i-1][j-i]+g[i][j-i].$

答案就是 $\sum_{i=1}^{316} g[i][n].$

代码：

#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
    scanf("%lld",&n);
    g[0][0]=1;
    for(register int i=1;i<=319;++i){
        for(register int j=i;j<=n;++j){
            g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
        }
    }
    for(register int i=1;i<=319;++i){
        ans+=g[i][n];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Everyone will be famous for fifteen minutes.

求解差分约束系统

差分约束系统是一个N元一次不等式组，由多组形如 $x_i-x_j \leqslant c_k$ 的不等式组成。一个差分约束系统要么无解，要么有无数组解。

Part 1 前置技能

在了解如何判断一个差分约束系统是否有解，或者求出它的一组解之前，我们需要先掌握它的前置技能。

图论基本概念
求单源最短/长路的方法

讲解图论的算法书籍都会讲解单源最短路的求法。在边权非负时，我们通常使用 Dijkstra 算法或 Bellman-Ford算法（以及它们的堆/队列优化算法）。Dijkstra算法不能处理负权存在时的情况，也不能求出单源最长路。Bellman-Ford算法及其队列优化的SPFA算法可以处理边带负权的情况，于是可以通过将边权取相反数的方法求出单源最长路。（见这里）Bellman-Ford算法及其队列优化的SPFA算法都可以判断图中是否存在负环，并且会在 $d[x]>d[y]+w(y,x)$ 时用 $y$ 点更新 $d[x]$ 。

在单源最短路算法结束后，假如图 $G(V,E)$ 中没有负环，那么必有：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

在你搞清楚上面两种SSSP问题求解的算法之后，我们就可以通过以下方式判断负环：

对于Bellman-Ford算法：

每次操作后，总会有一个点收敛。如果没有负环，经过 $n-1$ 轮迭代后必然不会再有点的路径长度被更新。如果迭代 $n-1$ 轮后仍然有点的距离可以被更新，那么说明一定有负环。

对于SPFA算法：

假如在用算法进行处理时，一个点的最短路径经过的边数已经大于 $n-1$ （即必然重复走了很多边和点），那么说明一定有些点可被重复走过，且重复经过这些点之后可以使距离更小。也就是说，图里有负环。使用一个数组 $cnt[]$ 记录每个点当前所求最短路经过了多少边就可以解决这个问题。方法是在用 $x$ 更新 $y$ 时，令 $cnt[y]=cnt[x]+1$ ，并判断是否 $cnt[y] > n-1$ 。

Part 2 求解差分约束系统

在理解Part 1的内容后，我们就可以用它来求解差分约束系统了。

如前所述，差分约束系统中的不等式形式是：

$x_i-x_j \leqslant c_k$

(例如 $x_2 - x_1 \leqslant 6$ )

而一个没有负环的图在跑完单源最短路算法后，满足：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

那么我们能否利用这个形式上的共同性来将求解差分约束系统的问题转化为图上的问题，然后利用图论算法求解？

当然可以。设有图 $G(V,E)$ ，对于差分约束系统中的每组关系 $x_i-x_j \leqslant c_k(i,j \in V)$ ，我们从 $j$ 点向 $i$ 点连接一条权值为 $c_k$ 的有向边。

假如从这个图的某点出发的单源最短路径为 $d[i](i \in V)$ ，满足 $\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$ ，那么这个差分约束系统必然是有解的， $d[i]$ 就是其中一组解。如果有一组解 $\{ x_1,x_2,...,x_n \}$ ，那么 $\{ x_1+k,x_2+k,...,x_n+k \} (k \in \mathbb{R} )$ 也必然是一组解。即它有无数组解。