2020-team11-C07

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team11 返回]

== 概述 ==

solved: 6/11  dirt: 55%

rank: 11


==  ==

== 总结 ==

今天的大多数题目都是签到题。但是由于I被double卡到自闭，C、H写得较晚。

Qza写完ABG后开了H，发现就是个讨论。而写H时思路却非常混沌，于是Qza决定去做I。他发现I是个虚假的计算几何，解方程求出一个线段，判一下与第三条线段有无公共点即可。但当时状态不太好，写完之后WA了，修掉几个明显的错误后还是WA。遂自闭。

后来无奈去开H，把H的分类讨论写完，测过样例后交了一发WA，自己看了代码后发现是一对儿分类讨论写反了。改正后遂AC。此时距离做出上一道题已104min。

又WA了一会儿I，cjb过来给予了安慰并建议扔掉I去开C。Qza遂在手玩、乱搞中找出了C的解法，交了一发TLE（缺少a=0特判）和一发WA（没取模）后，A掉了这道题。

之后开了D和J，D有些思路便开始研究。

此时ljm过来准备造数据叉I，但是并没有叉掉。（

之后建议剩下的时间冲J而扔掉D。于是Qza去做J，看到大家基本都一发过，便猜测这题有简单结论，结合样例后猜测答案就在l和r之间取。感觉有一些道理便开始莽。调通（并查集忘记路径压缩+搜索时只在本节点上疯狂递归而并没有往父亲上跳）了之后便交了一发TLE（数组开小），改了之后便AC掉了。

成功在最后5min内绝杀一题，拿下了rank倒数第一。

总的来说，状态还是比较糟糕。卡题之后思路一度停滞。

在考场上想出D有点困难。当时确实想过把I的long long改成double，但是总觉得long long没问题遂错失良机。

== 题解 ==

A: 按题意模拟。

B: 按题意模拟，找8或者找1均可。找8可以利用8里有三叉点这个性质。

C：首先，0-1序列差的绝对值就是异或操作。随便模拟几组数据就会发现，最终剩下的数由原序列中若干个数的异或值决定。进一步考虑哪些数可以留在最后，哪些数不会留在最后。由异或性质易知，在答案中具有奇数次贡献的数会留到最后。由组合数知识可知，第i个数在答案中的贡献次数为C(n-1,i-1)，于是只有((n-1)&(i-1))=(i-1)的i会出现在答案里。所以对需要填写的问号进行分类讨论。当问号所在位置不在答案中时，问号带来2的贡献。如果问号在答案中，则记问号数量为a。考虑除问号外剩余数的异或值，该值为0则意味着我们的问号需要异或出1；否则需要异或出0。所以问题转化为在a个问号中选1，3，5，7，...或2，4，6，8，...个位置填1，其余填0的方案数，易知这两个方案数相同，均为2^a-1^。a=0时特判即可。这道题就做完了。

D：把a+b和b+a两个串写出来比较一下即可发现，b必然由若干段a和一段c组成，其中c满足a+c=c+a，于是整个过程就类似求两个串的gcd。当且仅当两串的最小循环节相等，两串能产生贡献。我们可以直接对字符串的最小循环节进行统计，使用一遍kmp可以求出一个串的最小循环节，之后丢到unordered_map里查询，可以O(n)出。（用tire好像也能O(n)出？）

E：还没想清楚为什么是相等+等差。

F：多项式不会。

G：考虑到最后是判断奇偶，差的绝对值就相当于异或运算，于是矩阵变为了0-1矩阵。又考虑到我们要做的是判断两行异或值的和的奇偶性，所以我们只需要把两行中的所有元素（0或者1）都异或起来即可。进一步考虑到异或的交换律，我们可以将每一行分别异或起来得到一个值。当两行的这个值相等时，则这两行差的绝对值之和为偶数。于是简单n^2^扫过去即可。其实还可以进一步想到，当n>=3时，一定存在两行相等（因为取值只有0和1），所以实际复杂度为常数级别，故最后复杂度与输入同阶。

H：分类讨论。首先当两个矩形处处不交时，答案就是a*(a+1)*b*(b+1)/4加上固定矩形的面积乘ab。当二者相交时，考虑上式在矩阵内部、矩阵上部、矩阵右部、矩阵右上部产生的重复贡献，将它们减掉即可。

I：计算几何。考虑下两条直线能在第三条线的纵坐标上扫到的点集合是一个区间，故计算出区间的左右端点即可。其左右端点可以由下两条直线的端点交叉相连得到。需注意的是，这题要开double，long long会WA。

J：根据样例，可以猜答案一定在l或者r处取到。感性理解一下就是：考虑t从l到r连续变化，到某个时刻某条边将另一条边换掉了，那么它一定比原来那条边的斜率更小。那么继续往后走或者往前走一定比当前状态更优秀。但这个解释其实是错的。正解是由答案考虑过程，考虑最后的答案为树T，则树T的权值为Σa+xΣb，该值关于x单调。所以答案一定在l或者r处取到。

K：不会。

[/wiki/2020-team11 返回]

概述

solved: 6/11 dirt: 55%

rank: 11

总结

今天的大多数题目都是签到题。但是由于I被double卡到自闭，C、H写得较晚。

Qza写完ABG后开了H，发现就是个讨论。而写H时思路却非常混沌，于是Qza决定去做I。他发现I是个虚假的计算几何，解方程求出一个线段，判一下与第三条线段有无公共点即可。但当时状态不太好，写完之后WA了，修掉几个明显的错误后还是WA。遂自闭。

后来无奈去开H，把H的分类讨论写完，测过样例后交了一发WA，自己看了代码后发现是一对儿分类讨论写反了。改正后遂AC。此时距离做出上一道题已104min。

又WA了一会儿I，cjb过来给予了安慰并建议扔掉I去开C。Qza遂在手玩、乱搞中找出了C的解法，交了一发TLE（缺少a=0特判）和一发WA（没取模）后，A掉了这道题。

之后开了D和J，D有些思路便开始研究。

此时ljm过来准备造数据叉I，但是并没有叉掉。（

之后建议剩下的时间冲J而扔掉D。于是Qza去做J，看到大家基本都一发过，便猜测这题有简单结论，结合样例后猜测答案就在l和r之间取。感觉有一些道理便开始莽。调通（并查集忘记路径压缩+搜索时只在本节点上疯狂递归而并没有往父亲上跳）了之后便交了一发TLE（数组开小），改了之后便AC掉了。

成功在最后5min内绝杀一题，拿下了rank倒数第一。

总的来说，状态还是比较糟糕。卡题之后思路一度停滞。

在考场上想出D有点困难。当时确实想过把I的long long改成double，但是总觉得long long没问题遂错失良机。

题解

A: 按题意模拟。

B: 按题意模拟，找8或者找1均可。找8可以利用8里有三叉点这个性质。

C：首先，0-1序列差的绝对值就是异或操作。随便模拟几组数据就会发现，最终剩下的数由原序列中若干个数的异或值决定。进一步考虑哪些数可以留在最后，哪些数不会留在最后。由异或性质易知，在答案中具有奇数次贡献的数会留到最后。由组合数知识可知，第i个数在答案中的贡献次数为C(n-1,i-1)，于是只有((n-1)&(i-1))=(i-1)的i会出现在答案里。所以对需要填写的问号进行分类讨论。当问号所在位置不在答案中时，问号带来2的贡献。如果问号在答案中，则记问号数量为a。考虑除问号外剩余数的异或值，该值为0则意味着我们的问号需要异或出1；否则需要异或出0。所以问题转化为在a个问号中选1，3，5，7，...或2，4，6，8，...个位置填1，其余填0的方案数，易知这两个方案数相同，均为2^a-1。a=0时特判即可。这道题就做完了。

D：把a+b和b+a两个串写出来比较一下即可发现，b必然由若干段a和一段c组成，其中c满足a+c=c+a，于是整个过程就类似求两个串的gcd。当且仅当两串的最小循环节相等，两串能产生贡献。我们可以直接对字符串的最小循环节进行统计，使用一遍kmp可以求出一个串的最小循环节，之后丢到unordered_map里查询，可以O(n)出。（用tire好像也能O(n)出？）

E：还没想清楚为什么是相等+等差。

F：多项式不会。

G：考虑到最后是判断奇偶，差的绝对值就相当于异或运算，于是矩阵变为了0-1矩阵。又考虑到我们要做的是判断两行异或值的和的奇偶性，所以我们只需要把两行中的所有元素（0或者1）都异或起来即可。进一步考虑到异或的交换律，我们可以将每一行分别异或起来得到一个值。当两行的这个值相等时，则这两行差的绝对值之和为偶数。于是简单n²扫过去即可。其实还可以进一步想到，当n>=3时，一定存在两行相等（因为取值只有0和1），所以实际复杂度为常数级别，故最后复杂度与输入同阶。

H：分类讨论。首先当两个矩形处处不交时，答案就是a*(a+1)*b*(b+1)/4加上固定矩形的面积乘ab。当二者相交时，考虑上式在矩阵内部、矩阵上部、矩阵右部、矩阵右上部产生的重复贡献，将它们减掉即可。

I：计算几何。考虑下两条直线能在第三条线的纵坐标上扫到的点集合是一个区间，故计算出区间的左右端点即可。其左右端点可以由下两条直线的端点交叉相连得到。需注意的是，这题要开double，long long会WA。

J：根据样例，可以猜答案一定在l或者r处取到。感性理解一下就是：考虑t从l到r连续变化，到某个时刻某条边将另一条边换掉了，那么它一定比原来那条边的斜率更小。那么继续往后走或者往前走一定比当前状态更优秀。但这个解释其实是错的。正解是由答案考虑过程，考虑最后的答案为树T，则树T的权值为Σa+xΣb，该值关于x单调。所以答案一定在l或者r处取到。

K：不会。