[atcoder abc179]解題報告

好久都没写 atcoder 的题解了

还是先从 abc 开始吧(

比赛链接

A – Plural Form

签到题(

B – Go to Jail

签到题)

C – A x B + C

我写得比较麻烦……

可以把 $C$ 移到右边去,变成 $A\times B = N-C$,然后只需要枚举右边,左边可以用因数个数公式,分解质因数之后求出来即可。

不过好像只需要枚举 $A\times B$ 就行了……

时间复杂度:$\mathcal{O}(N\ln N)$.

D – Leaping Tak

一个很简单的 $dp$.

直接设 $dp(n)$ 表示走到第 $n$ 个格子的方案数,那么就有

$$
dp(i)=\sum\limits_{j\in S}dp(i-j)
$$

初始条件 $dp(1)=1$。然后这个递推式是一段一段的和,所以可以直接维护一个前缀和即可。

时间复杂度 $\mathcal{O}(nk)$.

E – Sequence Sum

注意到 $M\le 10^5$,也就是说循环节的大小也不会超过 $M$。

然后这个循环实际上构成了一棵基环树,跑到环上去了就是 $x$ 开始循环了,所以只需要找到循环节,中间一大段可以直接算,边界再单独处理一下即可。

时间复杂度 $\mathcal{O}(M)$.

F – Simplified Reversi

维护两棵线段树,分别是横着的和竖着的,这一列或者这一行最上 / 最左的白棋的位置。每次查询就先查询这个位置,设为 $pos$,那么黑棋总数就减去 $pos-2$。之后再修改,对行操作就对列进行区间修改(注意修改的时候一定要取最小值),对列操作就对行进行区间修改。

这样,模拟一下这个过程,答案就出来了。

时间复杂度 $\mathcal{O}(Q\log N)$.

 

发表评论