Dylan's Blog
0%

Posted on Edited on In

结束位置集与状态

结束位置集：

对于 $S$ 的一个子串 $t$，我们将 $S$ 中 $t$ 的所有结束位置叫做一个结束位置集，记为 $endpos(t)$。

状态：

我们将 $ S$ 的子串按照 $endpos$ 几何被分为若干个等价类，每一个等价类就对应于后缀自动机的一个状态。

性质：

我们设 $len(t_1)<=len(t_2)$，那么 $t_1$ 是 $t_2$ 的后缀当且仅当 $endpos(t_2) \subseteq endpos(t_1)$，$t_1$ 不是 $t_2$ 的后缀当且仅当 $endpos(t_1)\bigcap endpos(t_2)=\emptyset$。

一个状态所对应的所有子串，其中短的子串一定是长的子串的一个后缀，且子串的长度是连续的。也就是说，一个状态对应的所有子串，都是其中最长子串的一系列连续后缀。

后缀链接

定义：

我们考虑 $S$ 的一个前缀 $S[1,2,…,i]$，它会有 $i$ 个连续的后缀，这组连续的后缀可能会在中间若干个地方「断掉」并分为若干段，其中每一段的连续后缀都对应一个状态。我们可以用一个叫后缀链接的东西把这若干段链接起来。

后缀链接不属于DFA（有限状态自动机）的一部分，由于它奇妙的性质和强大的功能，构造 SAM 时会需要后缀链接。

性质：

所有后缀链接构成一棵根节点为 $t_0$（初始状态）的树。后缀链接构成的树本质上是 $endpos$ 集合构成的一棵树，树的边表示 $endpos$ 集合的包含关系。

构造算法

我们先用一个结构体来储存一个状态内的信息。其中 $len$ 该为对应子串的最长长度，$fa$ 为该状态的后缀链接，$next$ 为该状态的转移。

1
struct State {int len, fa, next[26]...;} st[MAXN*2];

假设我们构造好了 $S[1,2,..,i]$ 的SAM，并向其中添加字符 $s[i+1]$，那么我们就要对 $S[1,2,..,i]$ 所有后缀所对应的状态增加相应的转移，并且可以发现所有这些状态都被一条后缀链接构成的路径连接到初始状态上。我们只需要新建一个状态 $cur$，并对这条路径上的状态增加相应的转移就好。这个转移一共有三种情况：

1
int cur=++tot; st[cur].len=st[last].len+1;

先考虑最简单的情况，就是路径上的所有状态都没有 $s[i+1]$ 的转移。在这种情况下只要简单地把路径上的状态增加一个 $s[i+1]$ 的转移并指向状态 $cur$，再将 $cur$ 的后缀链接连向初始状态。

1
2
for(; p && !st[p].next[c]; p=st[p].fa) st[p].next[c]=cur;
if(!p) st[cur].fa=1;

再考虑第二种情况，路径上有一个状态 $p$ 有 $s[i+1]$ 的转移，设这个转移指向状态 $q$，且 $q$ 的 $len$ 等于 $p$ 的 $len+1$，也就是说 $q$ 对应的最长子串是 $p$ 对应的最长子串加 $s[i+1]$。这样我们只要把 $p$ 之前的状态增加一个 $s[i+1]$ 的转移并指向状态 $cur$，再将 $cur$ 的后缀链接连向 $q$。

1
2
int q=st[p].next[c];
if(st[p].len+1==st[q].len) st[cur].fa=q;

最后考虑最复杂的一种情况，路径上有一个状态 $p$ 有 $s[i+1]$ 的转移，设这个转移指向状态 $q$，但 $q$ 的 $len$ 不等于 $p$ 的 $len+1$，也就是说 $q$ 对应的最长子串不是 $p$ 对应的最长子串加 $s[i+1]$。这里我们要将状态 $q$ 分裂开，新建一份 $q$ 的拷贝 $t$，令 $t$ 状态对应的最长子串为 $p$ 对应的最长子串加 $s[i+1]$ 且令 $p$ 之后的状态的 $s[i+1]$ 转移指向的状态由 $q$ 变为 $t$，最后，将状态 $q$ 和 $cur$ 的后缀链接指向 $t$。

1
2
3
4
5
6
int t=++tot;
st[t].len=st[p].len+1;
memcpy(st[t].next, st[q].next, sizeof(st[q].next));
st[t].fa=st[q].fa;
for(; p && st[p].next[c]==q; p=st[p].fa) st[p].next[c]=t;
st[q].fa=st[cur].fa=t;

最终代码

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
int len, tot=1, last=1;
char s[MAXN];

struct State {int len, fa, next[26];} st[MAXN*2];

void insert(int c)
{
    int cur=++tot, p=last;
    st[cur].len=st[last].len+1;
    for(; p && !st[p].next[c]; p=st[p].fa) st[p].next[c]=cur;
    if(!p) st[cur].fa=1;
    else
    {
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len) st[cur].fa=q;
        else
        {
            int t=++tot;
            st[t].len=st[p].len+1;
            memcpy(st[t].next, st[q].next, sizeof(st[q].next));
            st[t].fa=st[q].fa;
            for(; p && st[p].next[c]==q; p=st[p].fa) st[p].next[c]=t;
            st[q].fa=st[cur].fa=t;
        }
    }
    last=cur;
}

int main()
{
    scanf("%s", s+1);
    len=strlen(s+1);
    for(rint i=1; i<=len; ++i) insert(s[i]-'a');
    /*
    进行操作
    */
    return 0;
}

例题

1.hihocoder1445 重复旋律5

代码链接

2.hihocoder1457 重复旋律7

代码链接

3.BZOJ3998 弦论

代码链接

4.hihocoder1465 重复旋律8

代码链接

5.BZOJ4566 找相同字符

代码链接

6.hihocoder1449 重复旋律6

代码链接

7.BZOJ2882 工艺

代码链接

8.hihocoder1449 重复旋律9

代码链接

Posted on Edited on In

离散傅里叶变换

定义：

是将 $\omega_n^1,\omega_n^2,…,\omega_n^n$ 带入多项式所得到的一种特殊的多项式点值表示

性质：

考虑将 $A(x)$ 的每一项按下标的奇偶分成两个多项式之和：

$A(x) = (a_0 + a_2x^2 + … + a_{n - 2}x^{n - 2}) + (a_1x + a_3x^3 + … + a_{n-1}x^{n-1})$

如果设：

$A_1(x) = a_0 + a_2x + … + a_{n - 2}x^{\frac{n}{2} - 1}$

$A_2(x) = a_1 + a_3x + … + a_{n - 1}x^{\frac{n}{2} - 1}$

那么：

$A(x) = A_1(x^2) + xA_2(x^2)$

于是我们把 $x = \omega_n^k$ 带入$A(x)$：

当 $k\subseteq \lbrace 0,1,2,… ,\frac{n}{2}-1\rbrace $ 时：

$A(\omega_{n}^{k})=A_1(\omega_{\frac{n}{2}}^{k}) + \omega_n^kA_2(\omega_{\frac{n}{2}}^{k})$

$A(\omega_{n}^{k+\frac{n}{2}})=A_1(\omega_{\frac{n}{2}}^{k}) - \omega_n^kA_2(\omega_{\frac{n}{2}}^{k})$

这样如果我们知道了 $A_1(x),A_2(x)$ 的离散傅里叶变换表示就可以 $O(n)$ 地求出 $A(x)$ 的离散傅里叶变换。

快速傅里叶变换

根据上面所提的离散傅里叶变换的性质，我们就可以递归地在 $O(nlogn)$的时间内将多项式的系数表示转换为点值表示。下面就介绍一下优化和实现上的细节：

蝴蝶操作：

有一个很神奇的性质：将一个多项式按下标的奇偶分为两部分，并将奇数部分放在偶数部分之后，然后不断递归下去。那么多项式下标为 $i$ 的数在这个操作之后的下标就变成了「将 $i$ 二进制翻转所得的数」。

1
for(rint i=0; i<lim; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(l-1));

根据这个性质，我们可以先预处理出多项式中每个数操作之后的位置，并将它放到这个位置。然后类似于递归时回溯的操作，不断向上还原求出点值表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(rint i=0; i<lim; ++i)
    if(i<pos[i]) swap(a[i], a[pos[i]]);
for(rint i=1; i<lim; i<<=1)
{
    Complex del(cos(PI/i), sin(PI/i));
    for(rint j=0; j<lim; j+=(i<<1))
    {
        Complex t(1, 0);
        for(rint k=0; k<i; ++k, t=t*del)
        {
            Complex x=a[j+k], y=t*a[j+k+i];
            a[j+k]=x+y; a[j+k+i]=x-y;
        }
    }
}

傅里叶逆变换

按照上述方法我们在 $O(nlogn)$ 内将多项式的系数表示转换成了点值表示，然后我们在 $O(n)$ 的时间内将两个多项式的点值表示相乘，得到了乘积的点值表示。利用傅里叶逆变换就可以同样在 $O(nlogn)$ 内将点值表示转换成系数表示。

离散傅里叶变换的另一个性质：把多项式 $A(x)$ 的离散傅里叶变换作为另一个多项式 $B(x)$ 的系数，并将 $\omega_{n}^{0}, \omega_{n}^{-1}, \omega_{n}^{-2}, …, \omega_{n}^{-(n - 1)}$ 代入多项式 $B(x)$ ，得到的每个数除 $n$，这样的 $n$ 个数就恰好是多项式 $A(x)$ 的系数。

根据上面的性质，我们在求离散傅里叶变换的代码上稍作修改，就能在 $O(nlogn)$ 内将点值表示转换成系数表示。

最终代码

下面是用 FFT 优化的高精度乘法代码（BZOJ2179）

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
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

const double PI=acos(-1);

int n, m, len, pos[MAXN], ans[MAXN];
char sa[MAXN], sb[MAXN];

struct CP
{
    double x, y;
    CP(double a=0, double b=0)
    {
        x=a; y=b;
    }
    friend CP operator * (CP a, CP b)
    {
        return CP(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
    }
    friend CP operator + (CP a, CP b)
    {
        return CP(a.x+b.x, a.y+b.y);
    }
    friend CP operator - (CP a, CP b)
    {
        return CP(a.x-b.x, a.y-b.y);
    }
} a[MAXN], b[MAXN];

void fft(CP a[], int op)
{
    for(rint i=0; i<n; ++i)
        if(i<pos[i]) swap(a[i], a[pos[i]]);
    for(rint i=1; i<n; i<<=1)
    {
        CP omg(cos(PI/i), op*sin(PI/i));
        for(rint j=0; j<n; j+=(i<<1))
        {
            CP t(1, 0);
            for(rint k=0; k<i; ++k, t=t*omg)
            {
                CP x=a[j+k], y=t*a[j+k+i];
                a[j+k]=x+y; a[j+k+i]=x-y;
            }
        }
    }
}

int main()
{
    scanf("%d", &len);
    scanf("%s%s", sa, sb);
    for(rint i=0; i<len; ++i)
    {
        a[i].x=sa[len-1-i]-'0';
        b[i].x=sb[len-1-i]-'0';
    }
    for(n=1; n<(len*2); ) n<<=1, m++;
    for(rint i=0; i<=n; ++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(m-1));
    fft(a, 1);
    fft(b, 1);
    for(rint i=0; i<n; ++i) a[i]=a[i]*b[i];
    fft(a, -1);
    for(rint i=0; i<n; ++i)
    {
        ans[i]+=(int)(a[i].x/n+0.5);
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    len=len*2-1;
    while(!ans[len] && len>=1) len--;
    for(rint i=len; i>=0; i--) printf("%d", ans[i]);
    return 0;
}

例题

1.BZOJ3771 Triple 2.BZOJ4259 残缺的字符串 3.AGC005F Many Easy Problems

Posted on Edited on In

刚接触一点计算几何，就把一些知识点记录在这里，后面会不断补充。

一、点 向量

这两个东西都可以用一对 double 来表示且运算基本相同，于是就放在一起。

0.储存

1
2
3
4
5
struct Vector
{
    int x, y;
    Vector(int _x, int _y) {x=_x, y=_y;}
};

1.加

1
2
3
4
Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

2.减

1
2
3
4
Vector add(Vector a, Vector b)
{
    return Vector(a.x+b.x, a.y+b.y);
}

3.点积

1
2
3
4
double dot(Vector a, Vector b)
{
    return a.x*b.x+a.y*b.y;
}

4.叉积

1
2
3
4
double cross(Vector a, Vector b)
{
    return a.x*b.y-a.y*b.x;
}

二、线段

0.储存

1
2
3
4
5
struct Line
{
    int k, b;
    int cal(int x) {return k * x + b;}
};

1.跨立实验

2.李超线段树 算法：用线段树标记永久化维护平面内线段覆盖情况

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
//维护线段的下凸壳
void insert(int &root, int l, int r, Line x) //插入线段
{
    if (!root) {t[root = ++tot] = x; return;}
    int lx=x.cal(l), rx=x.cal(r), ly=t[root].cal(l), ry=t[root].cal(r);
    if(lx<=ly && rx<=ry) {t[root]=x; return;}
    if(lx>ly && rx>ry) return;
    double p = 1.0 * (t[root].b - x.b) / (x.k - t[root].k);
    if(lx<ly)
    {
        if(p<=mid) insert(ls[root], l, mid, x);
        else insert(rs[root], mid+1, r, t[root]), t[root]=x;
    }
    else
    {
        if(p<=mid) insert(ls[root], l, mid, t[root]), t[root]=x;
        else insert(rs[root], mid+1, r, x);
    }
}

int query(int root, int l, int r, int x) //询问下凸壳纵坐标
{
    int temp = INF;
    if (root) temp = t[root].cal(x);
    if (l == r) return temp;
    if (x <= mid) temp = min(temp, query(ls[root], l, mid, x));
    else temp = min(temp, query(rs[root], mid + 1, r, x));
    return temp;
}

三、多边形

1.多边形面积 算法：取一点进行三角形剖分，然后用叉积求出三角形面积

1
2
3
4
5
6
double area()
{
    double ans=0;
    for(rint i=2; i<=n; ++i) ans+=cross(con[i-1], con[i])/2;
    return ans;
}

2.凸包 性质：所有邻边的叉积符号相同 算法：Graham扫描法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Graham()
{
    sta[++top]=con[1];
    for(rint i=2; i<=n; ++i)
    {
        while(top>1 && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
    int lim=top;
    for(rint i=n; i>=1; --i)
    {
        while(top>lim && cross(sub(con[i], sta[top]), sub(sta[top-1], sta[top]))<=0) top--;
        sta[++top]=con[i];
    }
}

Posted on Edited on In

11月15日 Educational Codeforces Round 56 题目链接：https://codeforces.com/contest/1093

D - Beautiful Graph

思路： 一个简单的计数题。

首先根据题意可以得知，一条边两端的奇偶性一定要是不同的，因此只有二分图是存在可行方案的。考虑计数，先二分图染色（假设染成黑白两色），那么对于每一个连通块可行的方案就是 $2^{白色点数}+2^{黑色点数}$，然后总方案就是每个连通块方案的乘积。

代码：

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
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 300005
#define p 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int T, n, m, ans, num, tot, cnt, head[MAXN], col[MAXN], Pow[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int ksm(int x, int y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=1LL*sum*x%p;
        x=1LL*x*x%p; y>>=1;
    }
    return sum;
}

bool dfs(int x, int color)
{
    col[x]=color; tot++;
    if(color==0) num++;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(col[to]==-1)
        {
            if(!dfs(to, 1-color)) return false;
        }
        else if(col[to]==col[x]) return false;
    }
    return true;
}

void solve()
{
    cnt=0; ans=1;
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; i++) head[i]=0, col[i]=-1;
    for(rint i=1; i<=m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for(rint i=1; i<=n; ++i)
    {
        if(col[i]>=0) continue;
        tot=num=0;
        if(dfs(i, 0)) ans=1LL*ans*(Pow[num]+Pow[tot-num])%p;
        else {printf("0\n"); return ;}
    }
    printf("%d\n", ans);
}

int main()
{
    scanf("%d", &T);
    Pow[0]=1;
    for(rint i=1; i<=300000; ++i) Pow[i]=Pow[i-1]*2%p;
    while(T--) solve();
    return 0;
}

E -Intersection of Permutations

思路： E 题就是个这么毒瘤的数据结构。。正解似乎是树套树，但是 CDQ 显然能做。

先可以将问题转化一下，处理出数组 $b$ 中的数字在数组 $a$ 中的位置记为数组 $c$，那么询问操作就是询问 $c[lb~rb]$ 中有多少个数的值在 $la~ra$ 内。这是一个二维数点问题，可以使用树状数组维护，由于有修改操作，那么就用 CDQ 基于时间一维进行分治就好了。时间复杂度也是 $O((n+m)log^2n)$。

代码：

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define MAXM
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, cnt, a[MAXN], b[MAXN], pos[MAXN], t[MAXN], ans[MAXN];

struct Act
{
    int id, x, y, val;
    Act(int a=0, int b=0, int c=0, int d=0)
    {
        id=a; x=b; y=c; val=d;
    }
} act[MAXN*5], temp[MAXN*5];

bool CMP(Act x, Act y)
{
    return x.x<y.x;
}

void add(int x, int y)
{
    for(; x<=200001; x+=(x&-x)) t[x]+=y;
}

int ask(int x)
{
    int sum=0;
    for(; x; x-=(x&-x)) sum+=t[x];
    return sum;
}

void cdq(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l, mid); cdq(mid+1, r);
    int L=l, R=mid+1;
    for(; R<=r; ++R)
    {
        if(!act[R].id) continue;
        while(act[L].x<=act[R].x && L<=mid)
        {
            if(!act[L].id) add(act[L].y, act[L].val);
            L++;
        }
        ans[act[R].id]+=act[R].val*ask(act[R].y);
    }
    for(int i=l; i<L; i++)
        if(!act[i].id) add(act[i].y, -act[i].val);
    merge(act+l, act+mid+1, act+mid+1, act+r+1, temp+l, CMP);
    for(int i=l; i<=r; i++) act[i]=temp[i];
}


int main()
{
    memset(ans, -1, sizeof(ans));
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        pos[a[i]]=i;
    }
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &b[i]);
        act[++cnt]=Act(0, i+1, pos[b[i]]+1, 1);
    }
    for(rint i=1; i<=m; ++i)
    {
        int op, la, ra, lb, rb, x, y;
        scanf("%d", &op);
        if(op==1)
        {
            ans[i]=0;
            scanf("%d%d%d%d", &la, &ra, &lb, &rb);
            act[++cnt]=Act(i, lb, la, 1);
            act[++cnt]=Act(i, lb, ra+1, -1);
            act[++cnt]=Act(i, rb+1, la, -1);
            act[++cnt]=Act(i, rb+1, ra+1, 1);
        }
        else
        {
            scanf("%d%d", &x, &y);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, -1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, -1);
            swap(b[x], b[y]);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, 1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, 1);
        }
    }
    cdq(1, cnt);
    for(int i=1; i<=m; i++)
        if(ans[i]!=-1) printf("%d\n", ans[i]);
}

F - Vasya and Array

思路： 是一个很有趣的 DP。

如果不考虑限制可以得到转移：$f[i][j]=\sum_{x=1}^{k} f[i-1][x]$，其中如果 $a[i]=-1$ 那么 $j$ 可以取 $1~k$ 所有数，否则 $j$ 只能取 j。接下来就是要把不合法的状态减去，我们记录一个数组 $pre[i]$ 表示从下标 $pre[i]$ 开始全可以取数字 $i$，由此我们就可以判断一个状态是否合法。如果数字 $j$ 在位置 $i$ 上不合法，那么我们就应该减去 $\sum_{x!=j} f[i-len][x]$。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define p 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, len, ans, a[MAXN], f[MAXN][105], pre[105], sum[MAXN];

void add(int &x, int y)
{
    x=(x+y>=p)?x+y-p:x+y;
}

int main()
{
    scanf("%d%d%d", &n, &k, &len);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(pre, -1, sizeof(pre));
    sum[0]=1;
    for(rint i=1; i<=n; ++i)
    {
        if(a[i]!=-1)
        {
            f[i][a[i]]=(i==1)?1:sum[i-1];
            for(rint j=1; j<=k; ++j)
            {
                if(j!=a[i]) pre[j]=-1;
                else if(pre[j]==-1) pre[j]=i;
            }
            if(pre[a[i]]!=-1 && i-pre[a[i]]+1>=len)
                add(f[i][a[i]], p-sum[i-len]), add(f[i][a[i]], f[i-len][a[i]]);
                //f[i][a[i]]=(f[i][a[i]]-sum[i-len]+f[i-len][a[i]]+p)%p;
        }
        else
        {
            for(rint j=1; j<=k; ++j)
            {
                if(pre[j]==-1) pre[j]=i;
                f[i][j]=(i==1)?1:sum[i-1];
            }

            for(rint j=1; j<=k; ++j)
                if(i-pre[j]+1>=len) add(f[i][j], p-sum[i-len]), add(f[i][j], f[i-len][j]);
                    //f[i][j]=(f[i][j]-sum[i-len]+f[i-len][j]+p)%p;
        }
        for(rint j=1; j<=k; j++) add(sum[i], f[i][j]);
            //sum[i]=(sum[i]+f[i][j])%p;
    }
    printf("%d\n", sum[n]);
}

G - Multidimensional Queries

思路： G 题与 E 题比反而是一个比较简单的数据结构题。

考虑 $k$ 比较小，于是我们可以对一个点枚举在每一维上对答案的贡献情况，即在公式 $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$ 去掉绝对值时的符号。对于我们枚举的每一种情况，由于去掉了绝对值，答案便是求一个区间内最大值与最小值之差，这个可以很简单的用线段树去维护。

为了减小码量，对于每一棵线段树可以只维护最小值。而最大值与最小值之差就是当前状态下的最小值与相反状态下最小值的和。

代码：

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
Copy
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, q, w[6], sum[32];

struct Segtree
{
    int val[MAXN*4], num[MAXN];

    void up(int root)
    {
        val[root]=min(val[ls], val[rs]);
    }

    void build(int root, int l, int r)
    {
        if(l==r)
        {
            val[root]=num[l];
            return;
        }
        build(ls, l, mid);
        build(rs, mid+1, r);
        up(root);
    }

    void update(int root, int l, int r, int x, int k)
    {
        if(l>x || r<x) return;
        if(l==r)
        {
            val[root]=k;
            return;
        }
        update(ls, l, mid, x, k);
        update(rs, mid+1, r, x, k);
        up(root);
    }

    int query(int root, int l, int r, int x, int y)
    {
        if(l>y || r<x) return INF;
        if(l>=x && r<=y) return val[root];
        return min(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
    }
} t[32];


int main()
{
    scanf("%d%d", &n, &k);
    for(rint i=1; i<=n; ++i)
    {
        for(rint j=0; j<k; ++j) scanf("%d", &w[j]);
        for(rint sta=0; sta<(1<<k); ++sta)
            for(rint j=0; j<k; ++j)
            {
                if((sta>>j)&1) t[sta].num[i]+=w[j];
                else t[sta].num[i]-=w[j];
            }
    }
    for(rint sta=0; sta<(1<<k); ++sta) t[sta].build(1, 1, n);
    scanf("%d", &q);
    while(q--)
    {
        int op, x, y, ans=0;
        scanf("%d", &op);
        if(op==2)
        {
            scanf("%d%d", &x, &y);
            for(rint sta=0; sta<(1<<k); ++sta)
                sum[sta]=t[sta].query(1, 1, n, x, y);
            for(rint sta=0; sta<(1<<k); ++sta)
                ans=max(ans, -(sum[sta]+sum[(1<<k)-1-sta]));
            printf("%d\n", ans);
        }
        else
        {
            scanf("%d", &x);
            for(rint i=0; i<k; ++i) scanf("%d", &w[i]);
            for(rint sta=0; sta<(1<<k); ++sta)
            {
                int temp=0;
                for(rint i=0; i<k; ++i)
                {
                    if((sta>>i)&1) temp+=w[i];
                    else temp-=w[i];
                }
                t[sta].update(1, 1, n, x, temp);
            }
        }
    }
}

Posted on Edited on In

问题描述

windy 定义了一种 windy 数。不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道在 A 和 B 之间（包括 A 和 B）总共有多少个 windy 数？

输入

包含两个整数，A B。

输出

一个整数，同题目要求

思路

一个比较简单的数位DP吧，直接按照套路来就好了。$f[i][j]$ 表示在第 $i$ 位上为 $j$ 的可能情况数，利用 $f$ 数组记忆化。然后需要注意的是，处理前导零时也不能够记忆化（仅针对我这种写法）。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int l, r, dig[12], f[10][10];

int dp(int x, int lim, int tag, int num)
{
    if(x==0) return tag;
    if(!lim && tag && f[x][num]!=-1) return f[x][num];
    int temp=0;
    if(!tag)
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(i==0) temp+=dp(x-1, lim&&i==dig[x], 0, 0);
            else temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    else
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(abs(num-i)<2) continue;
            temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    if(!lim && tag) f[x][num]=temp;
    return temp;
}

int solve(int x)
{
    int cnt=0;
    memset(f, -1, sizeof(f));
    while(x) dig[++cnt]=x%10, x/=10;
    return dp(cnt, 1, 0, 0);
}

int main()
{
    scanf("%d%d%", &l, &r);
    //printf("%d %d!!!\n", solve(r), solve(l-1));
    printf("%d\n", solve(r)-solve(l-1));
}