2019-10-25测试总结
Eqvpkbz's Site

2019-10-25测试总结

$chess$

$Dove$ 喜爱下跳棋,在传统的跳棋基础之上,$Dove$ 又延伸出了许多别的玩法。$Dove$以一个一维数轴为棋盘下跳棋,总共会移动棋子$n − 1$次。因为讨厌没有规律,所以$Dove$每次只会恰好把棋子向右移动$k$个格子。$Cicada$送给了$Dove$一个长度为 $n$ 的数列 $\{ a \}$,为了表示感谢,$Dove$ 打算以 $Cicada$ 送给他的序列 $\{ a \}$ 为基础下跳棋。具体的,$Dove$ 将会把棋子从编号为 $a_1$ 的格子出发,在第 $i$次移动后,把棋子移动到编号为 $a_{i+1}$ 的格子。显然 $Cicada$ 送给他的 $\{ a \}$ 有可能不满足$Dove$ 要求的条件,$Dove$ 想知道,最少需要修改多少个 $a_i$ 的值,才能使得这个数列 $\{ a \}$ 是满足 $Dove$ 需要的移动棋子的要求的

首先因为序列$\{ a \}$是从$a_1$开始的一个公差为$k$的等差数列,所以令每个数字$a_i$$a_i = k(i - 1) + b$,然后就可以得到$b = a_i - k(i - 1)$,然后把$a_1$作为出现次数最多的$b$值来开始构造等差数列即可做到

然后考场上的时候没有开long long20分没了

然后用的是数组下标而不是map,又因为$b$可以是负数,所以全部运行时错误了

要是这是CSP-S的考场上犯的错误,可能就再也没有能力走下去了吧

正确代码:

 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
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)
#define MAXN 1000005
#define int long long
map<int,int> vis;
int n,k,a[MAXN],b[MAXN],cnt = 0;
signed main()
{
    file("chess");
    scanf("%lld%lld",&n,&k);
    int MAX = 0;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&a[i]),a[i] -= k * (i - 1);
        vis[a[i]] ++;
        MAX = max(MAX,vis[a[i]]);
    }
    printf("%lld",n - MAX);
    file_close;
    return 0;
}

$substring$

作为一个熟练的算法竞赛选手,$Cicada$喜爱研究字符串问题。特别的,他尤其喜爱研究字符串中的子串问题。某日,$Cicada$在研究这样一道题目。首先对于一个字符串$S$,我们定义其第$l$个字符到第$r$个字符构成的子串为$S_{l,r}$ 。同时我们定义函数$f(S, l, r)$表示将字符串 $S$ 的第 $l$ 到第 $r$个字符删去后构成的字符串,$g(S, m, t)$表示将 $t$ 插入 $s$ 的第 $m$ 个字符之后构成的字符串。$Cicada$ 想知道,对于一个给定的长度为 $n$ 的字符串 $s$,有多少个三元组 $(l, r, m)$,满足$S = g(f(S, l, r), m, S_{l,r} )$

考场上想的是$KMP$的部分操作

然后不知道为什么脑子抽了,计算全部重复的结果的时候用的$O(n)$的算法

但是可以是$O(1)$的平方和式子的

于是就只有第$14,15$两个测试点的分

最后不知道怎么去重,所以不会

对于子串$(l, r)$,我们找出他的最短完整循环节$t$,即$S_{l,r} = $t^m$ ,即$S_{l,r}$可以表示为$m$个$t$前后拼接。

那么所有可以选取的$r_1$就是循环节的分界点。我们只需要对于每个子串确定他的循环
节即可。

这个问题是经典问题,可以选择哈希或者$KMP$来解决。
时间复杂度 $O(n^2)$,期望得分100pts

$permutation$

作为一个熟练的算法竞赛选手,$Dove$ 尤其喜爱研究排列问题。特别的,他尤其喜爱研究排列的标号问题。我们定义一个长度为 $n$ 的排列 $\{ a \}$ 的标号为把所有长度为 $n$ 的排列按字典序递增排序后这个排列的下标。一天,$Cicada$ 送给了 $Dove$ 一个长度为 $n$ 的排列,但是这个排列有一些位置的具体数字丢失了。特别的,对于第 $i$ 个位置,我们用 $a_i = 0$ 来表示这个位置的数值受到了丢失,否则表示这个位置的数值没有丢失。如果一个排列满足抹去若干数值后(即把一些位置的值置为 $0$)和给定的排列相同,那么我们称这个排列是合法的。$Dove$ 非常好奇,所有合法的排列的标号和是多少,因为还要学高考,所以 $Dove$ 只关心答案对 $10^9 + 7$ 取模的结果

不会正解,直接康托展开

 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
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)
#define MAXN 300005
#define ull unsigned long long
#define Mod 1000000007
int n,a[MAXN],b[MAXN], c[MAXN];
ull ANS = 0;
int cnt = 0,q[MAXN],pos[MAXN];
bool vis[MAXN];
inline int calc()
{
    int fac = 1,ans = 1;
    for(int i = 1;i <= n;i ++)
    {
        int s = 0;
        for(int j = b[n - i + 1];j > 0;j -= j & -j ) 
            s += c[j];
        ans = ( ans + 1ll * fac * s ) % Mod, fac = 1ll * fac * i % Mod;
        for(int j = b[n - i + 1];j <= n;j += j & -j ) ++ c[j];
    } 
    memset(c,0,sizeof(c));
    return ans;
}
void dfs(int now)
{
    if(now == cnt){ANS += calc();return ;}
    for(int i = 0;i < cnt;i ++)
        if(!vis[q[i]])
        {
            b[pos[now]] = q[i],vis[q[i]] = 1;
            dfs(now + 1);
            vis[q[i]] = 0,b[pos[now]] = 0;
        }
    return ;
}
int main()
{
    file("permutation");
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&b[i]),vis[b[i]] = 1;
        if(!b[i]) pos[cnt ++] = i;
    }
    cnt = 0;
    for(int i = 1;i <= n;i ++) if(!vis[i]) q[cnt ++] = i;
    dfs(0);
    printf("%llu",ANS);
    file_close;
    return 0;
}

然后此题的本质是:


$$\sum\limits_{s \in S}\sum\limits_{i = 0}^{n - 1}(s_i - \sum\limits_{j = 0}^{i - 1}[s_j < s_i]) * (n - i - 1)!$$

枚举 $i$,利用 $BIT$ 来维护 $j$ 即可。

时间复杂度 $O(n log n)$,期望得分100pts