https://atcoder.jp/contests/abc351

G - Hash on Tree

给定n点树有根数

值数组a[n]

f(u) = a[u] , 如果u是叶子

f(u) = a[u] + prod f(child of u)如果u非叶子

q次操作,每次 修改 a[pos]=val,每次修改后输出 f(1)

n,q 2e5

4s

1024mb

我的思路

首先这个是收到深度控制的,如果暴力的更新的话

那么一个想法是能否flat掉这个行为

[a,b,c]x[x,y,1] = [0,a*1+b*y,1]

leaf = [0,ai,1]

非叶子 = [ai,1,0]

然而没找到 矩阵方法或者满足“结合率”的东西

如果能有 矩阵或者结合律满足,就是个线段树维护,就好了

其中 上面的乘还可以拆成左右的包裹,总之如果有办法就好了

但是在尝试中发现要得到 a1+by 这种总是伴随秩的下降,没啥办法


第二个想的是上生成方程, 也没有弄出东西


那么最后就是 能否树的结构通过 轻重链 来完成快速计算(q log n)? 也没想到具体维护方法

閱讀全文 »

https://codeforces.com/contest/1951

G Clacking Balls(2s,256mb)

1~m篮子 顺时针 环

n个球,第i个在 篮子ai中,每个篮子至多1个球

alice 可以进行1s操作

  • [1,n]等概率 选i
  • 如果 球已经不存在,则跳过(依然耗时)
  • 如果 球存在,则沿着把球顺时针移动一个篮子,(如果目标篮子有球,把目标篮子中原来的球抛弃)

直到只剩下一个球停止,求操作时间的期望值 mod 1e9+7

n 3e5

n,m 1e9

我的思路

不能说没有想法,只能说一点想法也没有

如果一个球消失,那么说明有前面的球超过了它,换个角度 如果 球i移动 导致球j消失,也就是i走到j的位置,那么换成i消失是等价的后续,不影响概率

所以转换了题意的第三条(谁移动谁消失)以后

如果说 最后剩下的是 第i个球,那么这个球没有触碰下一个球,而前面的所有球触碰了后一个球

所以是个min/max 容斥+期望 吗?

计算每个球的 消失(触碰后面球)的期望次数,再min-max 容斥掉?

感觉也不对

再换个角度, 如果i留下

1
[i-1 ................i] .....

没啥想法,总的来说,显然直接状态描述肯定不行的,不论是点坐标还是距离

那么要么就是孤立每个 间隔的期望什么的,要么就是孤立的什么点期望,总之需要一个办法把其中 关联的东西拆掉,

而且不只如此,还有环


然后就是考虑简化的问题, 同样是环,但是只有两个点

那么 Exp(state) = Exp(点的距离)

然而转化构成了 一个转化矩阵

$A\lambda=\lambda$的形式,已知$A$要求$\lambda$


另一个是展开环到无限的数轴,指定目标点,那么得到每个点的移动方案数?

閱讀全文 »

https://codeforces.com/contest/1942

E. Farm Game(2s,256mb)

在 区间[1,l]整数点上 放 ABABAB…或者BABABA… 一共n组AB或BA, 坐标不一定相邻

  • 玩家X可以选择任意多个X(和玩家ID相同),和一个方向(左或右),把所有选中的A沿着这个方向移动
  • A先B后
  • 移动过程中字母不能重叠 不能出[1,l]范围,如果无法移动则输掉

问 给定$l,n$ 有多少个初始状态 玩家A获胜

我的思路

很像nim的游戏之类的

那么考虑 每个AB之间的空位的和,如果空位和为奇数,那么总可以移动那个位置让AB之间的空位和减1,而对于空位和是偶数,不一定能增大,也不一定能减少,但只要是能操作则结果也是奇数,

如果一轮操作后 空位和不变(否则变小),那么对应位置整体向同一个方向移动了两个字母

所以 获胜状态 = 所有AB间隔 空隙和=奇数

那么 l个位置 去掉 2n个占用位置,实际是切割成2n+1个 >=0 的段

也就是 l-2n长度线段切割成 2n+1个 >=0整数段 且 偶数index的段的长度和=奇数

考虑所有段+1

(l-2n)+(2n+1) 段 切割成 2n+1个 >=1 整数段,且偶数index的段的长度和 = 奇数+n

考虑 做顺序的置换,把所有偶数index段直接移动到最前,则方案还是一一对应

(l-2n)+(2n+1) 段 切割成 2n+1个 >=1 整数段,且前n段的长度和 = 奇数+n

1
2
3
4
5
6
for 前n段的长度和 = i:
if i % 2 == (n+1) % 2:
ans += (i 切割 n)段 * (l+1-i 切割成 n+1) 段, 每个切割段 >=1

长度 x 切割成y个>=1整数段,相当于 x-1个切割点中选择y-1个切割点
cut(x,y) = binom(x-1,y-1)

最后答案 AB和BA反向需要乘上2

然而 pretest1都没过 https://codeforces.com/contest/1942/submission/256178349


然后我发现读错题了,是 一次可以移动任意多个同方向,而不是一次一个

那么思路也完全一样,就是 去挤压另一个

所以 如果 存在 > 0 个奇数空位,则A 总能 把这些 奇数空位全变偶数(0个奇数空位)

如果 存在 0 个奇数空位,则全为偶数空位,则操作不确定,且操作后至少一个奇数空位

所以 方案 = 所有方案 - 全偶数空位方案

一样的

l-2n个位置切割2n+1个>=0整段,其中偶数index的长度全偶数

(l-2n)+(2n+1)=l+1个位置切割2n+1个>=1整段,其中偶数index的长度全奇数

l+1个位置切割2n+1个>=1整段,其中前n段的长度全奇数

1
2
3
4
5
6
7
for 前n段长度和为i, i % 2 = n * 1 % 2:
把 前n段每个长度+1, 则 前半
i+n长度 切割成 n 个 >= 2的偶数段 (那么每2个看成一个)
(i+n)/2 长度 切割成 n 个 >= 1的整数段
也就是 cut((i+n)/2,n)
cnt += cut((i+n)/2,n)*cut(l+1-i,n+1)

ans = (binom(l,2n)-cnt)*2

https://codeforces.com/contest/1942/submission/256179100

閱讀全文 »

https://atcoder.jp/contests/abc347

G - Grid Coloring 2

n * n

a[i][j] \in [0,5]

可以把0改为 1~5

所有操作后

代价=4临的差的平方和

求 最小代价的具体方案

n 20

2s

1024mb

我的思路

一个是插头dp 但是边界状态是 $5^n$

不知道怎么利用15,因为只关心差,可以变换成 `-22`但没感觉有什么帮助

有想网络流,但是不知道怎么表示 选与代价的关系。

$(x-y)^2=x^2-2xy+y^2$ 感觉就是这个2xy不知道怎么处理

閱讀全文 »

https://codeforces.com/contest/1943

D1,D2 Counting Is Fun

如果数组 每次可以 选择连续长度大于1的区间 同时减去1,操作多次以后 所有值变为0,则该数组是好(good)数组

对于 长度n,值范围[0,k]的 $(1+k)^n$个数组有多少个是好数组 $\mod p$

n D1(400),D2(3000)

$\sum n^2$, D1(2e5),D2(1e7)

$k \le n$

$p\in[10^8,10^9]$ 是质数

3s

1024mb

我的思路

good的充要条件?

首先 两端 不大于a1

如果出现连续3个$a < b > c$

要$b-a\le c$ (b,c同时下降 直到b变为a)或$b-c\le a$ (a,b同时下降 直到b变为c)

都是$b\le a+c$

所以 如果good 一定满足 上面的 两端 和 单峰的条件


那么如果满足 两端 和 单峰条件

对于单峰从左到右, 下降,每个前面的不影响后面的,

因此 这个条件是充要


就dp吧

dp[i][x][y]=i-1个位置合法,第i-1个位置是x,后一个是y的方案数

从第二项开始

然后 ans = sum dp[n][>=x][x]

对于$x\le y$

dp[i+1][x][y] = sum dp[i][...][x]

对于$x > y$

dp[i+1][x][y] = (sum dp[i][t][x], x <= t+y )=sum dp[i][>=x-y][x]

所以

dp[i+1][x][y] = sum dp[i][>=x-y][x], 其中 dp[i][<0][x]=0

用 后缀和可以 均摊 O(1) 计算每个x,y

所以有一个 $n n^2$的方法,感觉能过D1, 然后D2 明显TLE


感觉就是需要再次优化效率,然而上面的似乎并不能nxn的矩阵的矩阵乘法

然而 并没有成功优化

閱讀全文 »
0%