伊埃斯的小站
日记

日记

Mon Apr 14 2025
7 分钟
life 日记
1207 字

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

Transforming Pairs S Link to

也是切上绿题了。

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

口胡了一个做法：我们钦定 c<dc < d。首先我们对 dd 进行操作。将 dd 减去 ⌊d−bc⌋×c\lfloor \frac{d - b}{c} \rfloor \times c。这样可以保证 d≥bd \ge b。对 cc 进行同样的操作，减去 ⌊c−ad⌋\lfloor \frac{c - a}{d} \rfloor，同样为了保证 c≥ac \ge a。

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

Moo Decomposition G Link to

Java 的常数还是太优秀了。

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

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

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

Bessie’s Function G Link to

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

我也并非人类。

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

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

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

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

dpu,0=∑v∈sonudpv,1dpu,1=∑v∈sonumin⁡{dpv,0,dpv,1}\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 呢？我们考虑钦定 cir0cir_0 的状态。比如我们钦定 cir0cir_0 选，那么 dpcir0,1dp_{cir_0,1} 就设成 inf⁡\inf，最后统计答案最后一个点 uu 就爱选不选，tmp=min⁡{dpu,0,dpu,1}tmp = \min\{dp_{u,0},dp_{u,1}\}。反之就是 dpcir0,0=inf⁡dp_{cir_0,0} = \inf，tmp=dpu,1tmp = dp_{u,1}。最后 ansans 加上两个 tmptmp 的最小值就是了。

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

Shorten the Array Link to

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

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

后日谈 Link to 后日谈

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


Telegram
Douban
Reddit
Pocket