日记 - 伊埃斯的博客站

想说点什么但是说不出来。

Transforming Pairs S↗

也是切上绿题了。

看到这玩意很像 $\gcd$ 的求法，我们看看能不能往 $\gcd$ 上面想。

口胡了一个做法：我们钦定 $c < d$ 。首先我们对 $d$ 进行操作。将 $d$ 减去 $\lfloor \frac{d - b}{c} \rfloor \times c$ 。这样可以保证 $d \ge b$ 。对 $c$ 进行同样的操作，减去 $\lfloor \frac{c - a}{d} \rfloor$ ，同样为了保证 $c \ge a$ 。

继续口胡的证明：感性理解，我们为了让 $c$ 和 $d$ 尽快的减成 $a$ 和 $b$ ，每次减的肯定要尽可能多。于是我们每次进行辗转相减，减到再减一次就会爆炸的程度，每次减得就尽可能多了。

Moo Decomposition G↗

Java 的常数还是太优秀了。

我们发现 $L \le 1 \times 10^{18}$ ，直接把整个序列拎出来做肯定是不现实的。但是我们发现一个性质：每段的方案数相互独立。那么我们就可以把每段的方案数单独求出来然后快速幂了。

考虑如何求每段的方案数：从后往前枚举每个字符，我们设 $cnt$ 表示当前遇到的 $\texttt{O}$ 的个数。

遇到了个 $\texttt{O}$
显然是 $cnt \leftarrow cnt + 1$ 。
遇到了个 $\texttt{M}$
这个 $\texttt{M}$ 可以从前面的 $cnt$ 个 $\texttt{O}$ 里面任意取 $k$ 个，方案数乘上 $\binom{cnt}{k}$ 。然后因为用掉了 $k$ 个 $\texttt{O}$ ，我们需要把 $cnt$ 减去 $k$ 。

Bessie’s Function G↗

一道基环树板子题硬控我一下午。

我也并非人类。

我们发现这玩意可以套一个典中典的模型：对于每个 $i$ ，连一条 $i \to a_i$ 的边。因为总共有 $n$ 条边，所以一定是一个基环树森林。

我们发现如果要修改 $a_i$ ，一定是要把 $a_i$ 修改成 $i$ ，因为这样不仅可以使得 $i$ 变得满足条件，还能使出边连接到 $i$ 的点满足条件。但是为了方便 dfs，不可能建内向的基环树，肯定是建外向的基环树，就变成了让 $a_i = i$ 可以使得 $i$ 的儿子们也满足条件，我们就可以把题意转化一下：

对于每个点 $u$ ，都可以花费代价 $c_u$ 进行一次操作。操作必须要满足以下条件：如果你不操作那你的所有前驱就必须操作（在树上“前驱”表示儿子，在环上表示上一个节点。），反之你的前驱爱咋咋地。求最小代价。

我们这个题意都把方程给你写出来了。设 $dp_{u,0/1}$ 表示 $u$ 操作或者不操作。在树上就是：

\begin{aligned} dp_{u,0} & = \sum_{v \in son_u}dp_{v,1} \\ dp_{u,1} & = \sum_{v \in son_u}\min\{dp_{v,0},dp_{v,1} \} \end{aligned}

在环上也类似。如何处理环上 dp 呢？我们考虑钦定 $cir_0$ 的状态。比如我们钦定 $cir_0$ 选，那么 $dp_{cir_0,1}$ 就设成 $\inf$ ，最后统计答案最后一个点 $u$ 就爱选不选， $tmp = \min\{dp_{u,0},dp_{u,1}\}$ 。反之就是 $dp_{cir_0,0} = \inf$ ， $tmp = dp_{u,1}$ 。最后 $ans$ 加上两个 $tmp$ 的最小值就是了。

以后有向图找环还是老老实实 dfs 吧。

Shorten the Array↗

都想到了 $85\%$ 了为啥不再想一会呢？

1
#include<bits/extc++.h>
2
#define inf 0x3f3f3f3f
3
using namespace std;
4
const int maxn = 2e5 + 5;
5
int n,k,cnt;
6
int ch[maxn * 30][2],pos[maxn * 30];
7
void ins(int x,int id)// 字典树插入
8
{
9
    int rt = 1;
10
    for (int i = 30; i >= 0; i--)
11
    {
12
        bool dig = (x >> i) & 1;
13
        if (!ch[rt][dig])
14
            ch[rt][dig] = ++cnt;
15
        rt = ch[rt][dig];
16
        pos[rt] = max(pos[rt],id);// 维护这个这个子树内的最大 id
17
    }
18
}
19
int que(int x)
20
{
21
    int sum = 0,res = 0,rt = 1;
22
    for (int i = 30; i >= 0; i--)
23
    {
24
        bool dig = (x >> i) & 1;
25
        if (ch[rt][dig ^ 1])
26
        {
27
            if ((sum ^ (1 << i)) >= k)
28
            {
29
                res = max(res,pos[ch[rt][dig ^ 1]]);
30
                rt = ch[rt][dig];
31
                // 如果可以 >= k 就记录答案，然后往另一个子树走，看看能不能更大。
32
            }
33
            else
34
            {
35
                // 否则肯定要异或。
36
                sum ^= (1 << i);
37
                rt = ch[rt][dig ^ 1];
38
            }
39
        }
40
        else if (ch[rt][dig])
41
            rt = ch[rt][dig];
42
        else
43
            break;
44
    }
45
    return res;
46
}
47
void solve()
48
{
49
    for (int i = 1; i <= cnt; i++)
50
        ch[i][0] = ch[i][1] = pos[i] = 0;
51
    cnt = 1;
52
    scanf("%d%d",&n,&k);
53
    int ans = inf;
54
    for (int i = 1,x; i <= n; i++)
55
    {
56
        scanf("%d",&x);
57
        ins(x,i);
58
        if (int tmp = que(x); tmp)
59
            ans = min(ans,i - tmp + 1);
60
    }
61
    if (k == 0)
62
        return (void)puts("1");
63
    if (ans == inf)
64
        puts("-1");
65
    else
66
        printf("%d\n",ans);
67
}
68
signed main()
69
{
70
    int t;
71
    scanf("%d",&t);
72
    while (t--)
73
        solve();
74
    return 0;
75
}

后日谈

今天也是终于把 Java 的传参搞懂了。

Thanks for reading!

日记

周一 4月 14 2025

1131 字 · 6 分钟

life 日记