sb题

ARC

090

F

Solution

分类讨论

  1. f(l)7f(l) \le 7:暴力

  2. f(l)8f(l) \ge 8:显然f(r)f(l)1f(r) - f(l) \le 1,且区间长度一定会S8\le \lfloor \frac{S}{8}\rfloor ,于是考虑枚举区间长度lenlen

    • f(r)f(l)=0f(r) - f(l) = 0:方案数为10Slen10Slen1len+110^{\frac{S}{len}} - 10^{\frac{S}{len} - 1}- len + 1

    • f(r)f(l)=1f(r) - f(l) = 1:

      设有xx个数长度为f(l)f(l)yy个数长度为f(r)f(r),那么有

      于是对于每个lenlen,都能解出唯一确定的解

      需要注意当f(l)Sf(l) | S时答案在前一种情况中计算过了

Code

Summary

  • 小范围暴力,缩紧条件以方便计数

091

E

猜了个结论,贪心构造方案,没想到就A了

根据Dilworth定理:最小链覆盖等于最长反链,即最长下降子序列的长度等于极长上升子序列的个数

那么可以类似这样去构造:(7,8,9,10),(5,6),(3,4),(2),(1)(7, 8, 9 , 10), (5, 6), (3, 4), (2), (1)

这个例子中,LIS=4,LCS=5LIS = 4,LCS = 5

092

E

为什么sb题又做不出

可能一定程度上是被这数据范围误导了吧,明明是线性做法

首先观察到对答案有贡献的位置的奇偶性是相同的

那么答案要么是所有奇数位上大于零的数之和,要么是所有偶数位上大于零的数之和

选一个较大的即可

F

考虑一条边(a,b)(a, b)

  • a,ba, b在同一个强连通分量中:

    那么bb能到达aa

    aa能只通过这条边到bb,则反向后答案改变,否则不改变

  • a,ba,b不在同一个强连通分量中:

    那么bb不能到达aa

    aa还有另一条路径能到达bb,则答案改变,否则不改变

考虑如何判断是否存在另外一条路径能到达bb

枚举aa,考虑aa的所有出边指向的节点

的顺序dfs一次

假设从bib_i开始dfs,访问到某个节点的时候,如果它没有标记,则标记上ii,否则退出

再按同样的方法 的顺序dfs一次

这样就能对每个点求出,经过它所需的编号最小的出边,以及编号最大的出边了

若二者相等,则只有这一条出边能到达这个点

复杂度是O(nm)O(nm)的,能跑过

AGC

028

A

答案要么是1-1,要么是lcm(n,m)\mathrm{lcm}(n, m)

B

连个B都做不出来。。。

先把答案转化为总方案数乘每个数贡献的期望

对于第ii个数,它产生贡献的概率是j=1n1ij+1\sum_{j=1}^{n}\frac{1}{|i - j| + 1}

这个概率的套路和这道题)几乎一模一样。。。

处理下逆元的前缀和即可

Summary

  • 对整体算所有情况的答案时可以转化为求概率期望

C

其实大体自己都想到了。一个小细节上想歪了,一直卡在那个细节那里就去看了题解。看了题解之后发现我是sb

发现一个合法方案中总共可能有这四类点:00, 01, 10, 11 (左边为AiA_i,右边BiB_i11表示答案中有这个权值)

通过手玩发现,合法方案中00的个数与11的个数相等。并且只要满足num00=num11>0num_{00} = num_{11} > 0,方案就一定合法

可以通过画图的方法来证明,并构造出方案

19-7-31-1

其中红色边为AiA_i,蓝色边为BiB_i

显然,红蓝两色分界处对应00和11,只要它们数量相等,那么其他类型的点分配在每条相同颜色边构成的链上即可

到这里其实都想到了。。。

当时感觉这样构造出来的方案有可能不可行,不过没关系,如果不可行那答案一定会比它更优

这样做只要能保证答案的情况能被算进来就行了


接下来就很简单了,把Ai,BiA_i, B_i混在一起排序,枚举00类的点是哪个(至少要一个),剩下的贪心选即可

记得考虑全是01或者全是10的情况

D

转化一下

数轴上有一些点,已经存在的KK条线段把数轴分成了一些部分

可以求出如果在任意两个部分之间连一条边,答案会增加多少

狗屎

看错题了,题目联通是指两个点通过某些线段联通,我以为把圆分成了多少个部分。。。

好难的计数题。。。

题解看了好久才懂

考虑最终状态,一定是某些编号连续的(不一定是联通块)构成的

19-8-11-1

注:如图中的蓝色部分,它不是一个联通块,但这并不影响

考虑枚举所有这样的块,设dp[i][j]dp[i][j]表示这样的块编号最小的点为ii,最大的点为jj,那么答案就是所有dp[i][j]dp[i][j]乘上剩下点随便连的方案数

这样的块本质上就是满足iijj联通,且iijj之间的点只在内部互相配对

g[i]g[i]表示ii个点随便连边的方案数,若ii为奇数,则g[i]=0g[i] = 0;否则g[i]=(i1)×(i3)××1g[i] = (i-1) \times (i-3) \times \cdots \times 1

如何计算dp[i][j]dp[i][j]呢?

直接算并不好算,因为有图中蓝色块的情况,于是考虑简单容斥(补集转化),用所有方案减去iijj不联通的方案(枚举断点位置,相当于区间dp)

dp[i][j]=g[cnti,j]k=ij1dp[i][k]×g[cntk+1,j] dp[i][j] = g[cnt_{i, j}] - \sum_{k=i}^{j-1}dp[i][k]\times g[cnt_{k+1, j}]

其中cnti,jcnt_{i, j}表示iijj中没被钦定的点的个数

答案就是

i,jdp[i][j]×g[cnt1,i1+cnti+1,n] \sum_{i, j} dp[i][j]\times g[cnt_{1, i-1} + cnt_{i + 1, n}]

029

A

显然答案就是每个WW前面BB的个数

B

贪心题。。。

不会做。。。

没脑子。。。

从大到小考虑,对于一个数xx,找到它在剩下的数中能与它配对的数yy,那么yy是唯一确定的

yy是最小的满足x+y=2kx + y = 2^k的数,那么显然找不到一个z>yz > y,满足 x+z=2kx + z = 2^{k'}

因为剩下的数中没有比xx大的数,而这里的zz肯定要比xx

于是可以直接将x,yx, y配对

C

二分答案,判断的时候若ai>ai1a_i > a_{i - 1}就填0,否则把大于aia_i位的部分删掉,再+1,用map暴力维护这个过程即可