题意

给定一棵树，给出m个查询，要求判断每个查询给出的a,b之间的最短路顶点权值是否回文？

题意：

给定一个字符串，求包含ACCEPT但不包含WA且长度大于k的子串数量。

题解：

子序列自动机，一个我较少写的算法（ps:可能是用到了没意识到），mark。。。

子序列自动机的基本概念是用二维数组保存对于i位置 j字符第一次出现的位置为nxt[i][j]，通过这种方式来维护字串ACCEPT和子串WA的子序列位置。

这是一个很容易理解，很多人没有给它命名的算法。该题的答案就是对于每个以i结尾的字符串i，计算后一个“WA"，“A”与后一个“ACCEPT”中的“A”的上一位合法字符串长度累和。

题意

题意：给一个数字字符串，要求按相对序构建不带前导零的偶数，求这些数字的多重集的大小

题解

题解：维护两个值，cnt，ans，cnt表示当前能构造出的不带前导零的数字的多重集size，ans表示偶数多重集size。处理前导零的思维是，cnt所代表的多重集中不含0这个数字，也就保证了cnt在计算过程中的不含前导零，具象到代码中则是在s[i]=='0'时，将cnt-1，而ans保持相同计算。cnt->ans，cnt在每一位上的计算非常简单不再赘述，即ans=(ans+cnt+1)%MOD,cnt=(cnt*2+1)%MOD。

题意：

给你一个数组[𝑝1,𝑝2,…,𝑝𝑛] ，其中所有元素都是不同的。

你可以对它执行几个(可能是零)操作。在一个操作中，你可以从 p 中选择一个连续的子段，然后从该子段中删除所有元素，除该子段中最小的元素。例如，如果选择p = [3, 1, 4, 7, 5, 2, 6]，并选择从，并选择从3元素到−𝑟𝑑元素到6元素的子段，那么得到的数组就是−𝑡ℎ元素的子段，那么得到的数组就是[3, 1, 2, 6]。

如果数组 a可以从可以从p中通过上述几种也许是零种操作得到，那么这个数组中通过上述几种(也许是零种)操作得到，那么这个数组a 就叫做可达数组。计算可达数组的个数，并打印出它的模数 998244353。

题解：

根据题目答案数据范围，很容易想到通过区间修改暴力答案是不可行的。于是转向dp想法，一个简单的构型是，对于每个i结尾的结果数组计算贡献值。思考状态转移，需要计算如何在保留 𝑎𝑖 的情况下的贡献值。

考虑操作对于保留最小值的设定，该操作具有结合律，可以想到， 𝑎𝑖 是后缀操作区间（如进行[n-1,n],[n-3.n-2]的操作等同于操作后缀[n-3,n]）最小值一定成立。则状态转移为其中dp(i)+=dp(j)(其中a[j]<a[i])另外一种情况则是，不对i进行操作。考虑上一个比a[i]小的数为\(l*{a_i}\)下标为，则小于且大于下标为j，则小于j且大于l{aj}的下标的下标均无法转移至，显然的下标k的下标idx均无法转移至i，显然l{ai}是无法通过操作区间中比它大的数移除的，这是可以推广的，即对任意下标小于的下标如果其不等于是无法通过操作区间中比它大的数移除的，这是可以推广的，即对任意下标小于j的下标x如果其不等于\(l*{a_x}\)则无法转移到i。

总结状态转移为\(f*i = \sum*{k={l*{a_i}+1}}^{i-1} f_k + \sum*{k=l^x(l*{a_i})}^{k>0}f*{k}\)

前缀和处理即可。

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

	void slove(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    s[top] = {-1,-1};
    for(int i = 1;i <= n;i++) {
        while(top && s[top].x > a[i]) top--;
        l[i] = s[top].y;
        s[++top] = {a[i],i};
    }

    // for(int i=1;i<=n;i++) cout<<l[i]<<' ';
    // cout<<endl;

    for(int i=0;i<=n;i++) pre1[i] = pre2[i] = 0;

    f[0] = 1;
    pre1[0] = 1;
    for(int i=1;i<=n;i++) {
        if(l[i]!=-1) pre2[i] = pre2[l[i]] + f[l[i]] % MOD;
        int t = l[i] == -1 ? 0: pre1[l[i]];
        f[i] = (pre1[i-1] - t) % MOD ;
        // cout<<(pre1[i-1] - t)<<' ';
        f[i] += pre2[i];

        pre1[i] = pre1[i-1] + f[i] % MOD;
        // cout<<i<<' '<<pre1[i]<<' '<<pre2[i]<<' '<<f[i]<<nline;
    }

    int mi = 1e18,ans = 0;
    for(int i=n; i>=1; i--) {
        mi = min(mi,a[i]);
        if(mi==a[i]) {
            ans = (ans + f[i]) % MOD;
        }
    }
    cout<<ans<<endl;
}

题意：

给你一个整数数组 1, 2,…, ，它的所有元素都是不同的。

首先，要求你在数组中再插入一个整数 an+1 。 an +1 不应等于 a1, a2,…, an中的任何一个。

然后，你必须使数组中的所有元素相等。一开始，你选择一个正整数 x。在一次操作中，你将 x 恰好加到数组的一个元素上。注意， x 在所有操作中都是一样的。

选择 +1 和 x 后，使所有元素相等的最小操作次数是多少？

题解：

容易误解的点在于——对一个新增的数x，能否找到 ∑𝑖=1𝑖=𝑛𝑥−𝑎𝑖(𝑥−𝑎𝑖) 小于 ∑𝑖=1𝑖=𝑛𝑚𝑥−𝑎𝑖(𝑚𝑥−𝑎𝑖) （mx表示数组中的最大值）由于笔者太拉昆了，暂时先不证明了。。。

可以凭直觉猜出一个解法，最大的数不变𝑎𝑛𝑠=∑𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖])(𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖]))+𝑎𝑑𝑑𝑡𝑖𝑜𝑛其中addtion为以最大公倍数为步减的最大值(𝑚𝑥−𝑎𝑛+1)/(𝑑𝑖𝑓(𝑚𝑥,𝑎[𝑖]))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void slove(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    int mx = -INF;
    for(int i=1;i<=n;i++) {
        mx = max(mx,a[i]);
    }

    for(int i=1;i<=n;i++) d[i] = mx - a[i];

    int gd = 0;
    for(int i=1;i<=n;i++) gd = __gcd(d[i],gd);

    if(!gd) {cout<<1<<endl;return ;}

    ll sum = 0;
    set<int> S;
    for(int i=1;i<=n;i++) sum += (mx - a[i]) / gd,S.insert((mx - a[i]) / gd);
    int t = 1;
    while(1) if(S.count(t)) t++;else break;
    cout<<sum + t<<endl;
}

题意：

对一个数组的所有非空子区间，计算这个公式\[w = \sum_{i=l}^{i=r} \sum_{j=l}^{j=r}a_i \oplus a_j \]的和。

三种操作系统简单模拟使用手册

可运行程序图标

https://1drv.ms/u/s!Ap-enY7ckLANgpBTVvNJXGKi-3tRZw

Typora

​ Typora是我一直在使用的markdown编辑器，对比起其他的markdown编辑器来说，==Obsidian==虽然有更加具有逻辑性的文档之间的双向链接和git式的设定，==Vscode==，==Sublime==则是Markdown插件构成的markdown编辑器，Typora更加纯粹和统一。具体表现在，它的使用逻辑非常简洁，仅仅只是文档编辑器，除了markdown的即时渲染之外，并没有过多独特的特性，在编辑上的极致优化使得它受众广泛。