当前位置：网站首页>【学习笔记】AGC044

【学习笔记】AGC044

2022-08-09 04:37:00 【仰望星空的蚂蚁】

Guess the Password

如果 S S S是 T T T的子序列，那么会返回 ∣ T ∣ − ∣ S ∣ |T|-|S| ∣T∣−∣S∣，否则会大于这个值。

那么可以先查询单个字符，选取最小的答案，这个字符一定在 T T T中出现过。这样我们得到了串长。

那么，我们继续询问连续一段相同字符可以得到每个字符的出现次数。

然后用类似归并的过程合并两个字符集不交的子序列，步数为 c n t a + c n t b − 1 cnt_a+cnt_b-1 cnta​+cntb​−1

那么每次找长度最短的两个子序列合并即可。因为 Huffman \text{Huffman} Huffman树的树高不超过 log ⁡ L \log L logL，所以总步数 L log ⁡ L L\log L LlogL。

AC Code

Increasing Numbers

显然要分析答案的结构。。。

一个递增数可以拆成若干串 1 1 1。。。

然后有一个很仙的转化。。。

因为 111 ⋯ 11 ⏟ i = 1 0 i − 1 9 \underbrace{111\cdots 11}_{i}=\frac{10^i-1}{9} i111⋯11​​=910i−1​

所以 N = ∑ i = 1 n + 1 k i ( 1 0 i − 1 ) 9 N=\sum_{i=1}^{n+1}\frac{k_i(10^i-1)}{9} N=∑i=1n+1​9ki​(10i−1)​

设 k k k表示总的 111 ⋯ 11 111\cdots 11 111⋯11的个数，那么 9 N + k = ∑ i = 1 n + 1 k i 1 0 i 9N+k=\sum_{i=1}^{n+1}k_i10^i 9N+k=∑i=1n+1​ki​10i。左边显然是 10 10 10的倍数，那么如果 k k k合法的话 9 N + k 9N+k 9N+k的数位之和应该不超过 k k k，同时我只能把 1 0 i 10^i 10i拆成 10 10 10个 1 0 i − 1 10^{i-1} 10i−1，那么要求 k k k和 ∑ i = 1 n + 1 k i \sum_{i=1}^{n+1}k_i ∑i=1n+1​ki​模 9 9 9同余。等式两边模 9 9 9发现这恒成立。

同时我们观察到 k k k不会超过 10 n 10n 10n，那么我们模拟高精度加法就能做到均摊 O ( 1 ) O(1) O(1)，总复杂度 O ( n ) O(n) O(n)。

Squared Graph

AC Code

Half Reflector

好难的模拟题。。。

从左端飞出去其实只有一种情况，那就是第一个就是 A A A，否则肯定会从右端飞出去。

如果遇到 B B B就直接走过去，如果遇到 A A A就把垫背的反转，然后走过去。

好妙的结论啊。。。

探究一次操作后 i i i的状态。

把 A A A看成 0 0 0， B B B看成 1 1 1。

如果最高位是 0 0 0，那么把最高位反转成 1 1 1。

否则 s s s取反并左移一位。（左移会溢出最高位）

AC Code

原网站

版权声明
本文为[仰望星空的蚂蚁]所创，转载请带上原文链接，感谢
https://blog.csdn.net/cqbzlydd/article/details/126182366

边栏推荐

猜你喜欢

随机推荐