KMP(字符串匹配)

KMP算法是一种高效的字符串匹配算法。通常,在求两个字符串是否匹配是,都是枚举一个字符串的开头与另一个字符串匹配, 假如 A 串长度为 n , B 串长度为 m , 那么这种方法的复杂度是 O(nm)的。而KMP能在O(n)的时间内完成。

【KMP思想】

如图,假设有A,B两个字符串要求匹配,当匹配到A[i]、B[j]时,A[1..i-1]与B[1..j-1]完全匹配,但A[i]!=B[j]。通常,遇到这种情况,都是再枚举开头,重新进行匹配,但是这会浪费很多时间。仔细观察,发现B串的a部分与b部分完全相同,那么可以适当减少j的值(相当于把B串往后移动),那么匹配便可以继续进行。如下图。

显而易见,j减少的多少与A无关,只与B有关。 我们完全可以预处理出这样一个数组 next[j], 表示当匹配到 B 数组的第 j 个字母而第 j +1个字母不能匹配了时, 新的 j 最大是多少。 next[j] 应该是所有满足 B[1..k]= B[ j- k+1... j]的k (k < j) 的最大值。

于是容易得出KMP的代码:


1
2
3
4
5
6
7
8
9
void KMP()  {
    int j = 0;
    for (int i = 1;i <= m; i++)  {
        while (j && b[i] != a[j + 1]) j = next[j];
        if (b[i] == a[j + 1]) ++j;
        if (j == n)
            j = next[j];
    }
}

最后的 j=next[j]是为了让程序继续做下去, 因为我们有可能找到多处匹配。

那么next数组要怎么求呢?

假设我们现在已经求得next[1]、next[2]、……next[i],分别表示长度为1到i的字符串的前缀和后缀最大公共长度,现在要求next[i+1]。

  1. 如果位置i+1和位置next[i+1]处的两个字符相同(下标从零开始),则next[i+1]等于next[i]加1。
  2. 如果两个位置的字符不相同,我们可以将长度为next[i]的字符串继续分割,获得其最大公共长度next[next[i]],然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造,如果位置next[next[i]]和位置i的字符相同,则next[i+1]就等于next[next[i]]加1。如果不相等,就可以继续分割长度为next[next[i]]的字符串,直到字符串长度为0为止。

怎么这个预处理过程跟前面的 KMP 主程序这么像呢? 其实, KMP 的预处理本身就是一
个 B 串“自我匹配” 的过程。


1
2
3
4
5
6
7
8
9
void Find_next()  {
    int j = 0;
    next[1] = 0;
    for (int i = 2;i <= n; i++)  {
        while (j && a[j + 1] != a[i]) j = next[j];
        if (a[j + 1] == a[i]) j++;
        next[i] = j;
    }
}

最后为什么KMP的代码会是O(n)的呢?

我们从上述程序的 j 值入手。 每一次执行 while 循环都会使 j减小( 但不能减成负的) , 而另外的改变 j 值的地方只有一处。 每次执行了这一处, j 都只能加 1; 因此, 整个过程中 j 最多加了 n 个 1。 于是, j 最多只有 n 次减小的机会(j 值减小的次数当然不能超过 n , 因为 j 永远是非负整数) 。 这告诉我们, while 循环总共最多执行了 n 次。 按照摊还分析的说法, 平摊到每次 for 循环中后, 一次 for 循环的复杂度为O(n)
整个过程显然是O(n) 的。 这样的分析对于后面next数组预处理的过程同样有效, 同样可以得到预处理过程的复杂度为 O(n)。
完整代码如下: 继续阅读KMP(字符串匹配)

splay(平衡树)

【引入】

先来看一道题:营业额统计

显然,对于每一天的营业额只要找出已有的营业额与其差值最小的就行了。那么便可以用二叉搜索树来实现这样的查找。

如果一棵二叉树如同下图,为一条链,那么每次查找的时间复杂度就和暴力没有什么差了。

我们可以发现,下图的二叉树与上图的二叉树是等价的,但下图的深度比上图的深度少了2,这样查找的时间复杂度也就减少了,那如何将上图的二叉树转化成下图的呢?splay便可以实现。

【思想】

【rotate】

这是原来的树。为了减小深度,我们把B结点旋转到根结点,那么A结点就成了B结点的儿子。由二叉树的性质我们可以知道B<E<A<C,那么可以得到如下的一棵新树。

rotate代码如下:


1
2
3
4
5
6
7
8
9
10
11
void Rotate(int x)
{
    int fa = tree[x].fat, s = (x == tree[fa].son[1]), s1 = (fa == tree[tree[fa].fat].son[1]);
    tree[tree[x].son[s^1]].fat = fa;
    tree[fa].son[s] = tree[x].son[s^1];
    if (tree[fa].fat)
        tree[tree[fa].fat].son[s1] = x;
    tree[x].fat = tree[fa].fat;
    tree[x].son[s^1] = fa;
    tree[fa].fat = x;
}

【splay】

splay则是rotate的拓展,因为对于一个点,只进行一次rotate显然并不会有多少优化,只有将其旋转至根结点才方便之后的操作。

splay的过程中需要分类讨论,如果是三点一线的话(x,x的父亲,x的祖父)需要先rotate x的父亲,否则需要先rotate x本身(否则会形成单旋使平衡树失衡)。


1
2
3
4
5
6
7
8
9
10
void splay(int x)
{
    for (int y; (y = tree[x].fat) > 0;)
    {
        if (tree[y].fat)
            Rotate((tree[tree[y].fat].son[1] == y)^(tree[y].son[1] == x) ? y : x);
        Rotate(x);
    }
    root = x;
}

【insert/find/delete】

插入、查找、删除的操作于普通平衡树一样。只是在最后要将操作的点旋转到根结点。

插入:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ins(int va)
{
    int x = root;
    if (!tree[x].val)
    {
        tree[++tot].val = va;
        tree[tot].tot = tot;
        root = tot;
        return ;
    }
    for (;tree[x].son[va > tree[x].val] && tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    if (tree[x].val == va)
    {
        tree[x].cnt++;
        return ;
    }
    tree[++tot].val = va;
    tree[tot].fat = x;
    tree[x].son[va > tree[x].val] = tot;
    splay(tot);
}

查找:


1
2
3
4
5
6
void Find(int va)
{
    int x = root;
    for (;tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    splay(x);
}

查找前驱/后继:


1
2
3
4
5
6
7
int Find_max(int x)
{
    int y = tree[x].son[0];
    for (;tree[y].son[1]; y = tree[y].son[1]);
        splay(y)
    return y;
}

删除:

删除的操作相对麻烦。如果其只有一个儿子,那么将它的儿子当作根结点就可以。否则,要先找出当前结点的前驱/后继,将其旋转到根结点。那么要操作的结点一定是根的一个儿子,并且它只有一个儿子,于是只要将根的儿子指向要操作的结点的儿子即可。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void del(int x)
{
    if (tree[x].cnt > 1)
    {
        tree[x].cnt--;
        return ;
    }
    int l = (tree[x].son[0] != 0), r = (tree[x].son[1] != 0);
    if (!l && !r)
    {
        root = 0;
        return;
    }
    if (!l)
    {
        tree[tree[x].son[1]].fat = 0;
        root = tree[x].son[1];
        return ;
    }
    splay(Find_max(x));
    tree[root].son[1] = tree[x].son[1];
    if (r) tree[tree[x].son[1]].fat = root;
}

【总结】

splay是一种优化二叉查找的方法,所有的操作一定都满足二叉搜索树的性质。

完整代码:

继续阅读splay(平衡树)

【NOIP2011】观光公交 题解

题目传送门:!点我传送!

每个人在车上的时间 等于 车到达目的站的时间 减去 这个人到达起始站的时间
由于人到达起始站的时间题目给出不会变化
所以求解一个最优的车到达目的站的时间即可

假设到达第i+1站的时间是time[i]
从前往后逐个求解到站时间
可以得出time[i] = max{time[i-1], last[i]} + d[i]
其中last[i]为从第i站上车的旅客中最后到达的一个到达的时间 可以用O(n+m)的时间预处理得出
d[i]为从i走到i+1所用的时间
很明显的 我们可以利用这个递推关系式用O(n)的时间求解time[i]

当我们令d[i]减少1时
time[1..i-1]不会变化
time[i]会减少1
考虑time[i+1]
由前面的式子得出time[i+1] = max{time[i], last[i+1]} + d[i+1]
若我们令d[i]减少之前 存在time[i] > last[i+1]则time[i+1]会减少1 否则time[i+1]就会不变
若time[i+1]减少了1 我们可以用同样的方法判断time[i+2]直到最后是否变化
若time[i+1]不变 则time[i+2]及之后的time值都不会变化
**所以 当我们令某个d[i]减少1时 从time[i]开始会有一段区间的time值均减少1

这个区间的左端为i 我们令右端为range[i]
对于j属于从i+1到range[i] 均存在time[j-1] > last[j] 且对于range[i]+1不存在time[j-1] > last[j]

说到这里 大家应该发现求解range[i]的方法了
若range[i+1] = t 则对于从i+2到t前不等式均成立且对于t+1不成立
所以我们求解range[i]只需判断对于i+1前不等式是否成立即可
若成立则 range[i] = range[i+1] 不成立则 range[i] = i

若我们修改每个值所减少的时间为reduce[i] 则reduce[i] = v[i] + v[i+1] + ... +v[range[i]]
v[i]表示到达第i+1个车站的人的数量
很明显的 reduce[i] = v[i] + reduce[i+1] 或 v[i]

现在 我们可以用O(n)的时间求解reduce了
然后每次选择一个令reduce[i]最大的i 令d[i]减少即可

注意每次修改d[i]之后 要重新计算新的time[i]

时间复杂度O(kn)

继续阅读【NOIP2011】观光公交 题解

【NOIP2010】引水入城 题解(Probably)

题目传送门:!点我传送!

知识点:广度优先搜索+区间最小覆盖

题目大意就是给我们一张图,我们只能从第一行的任意位置出发,走一条高度递减的路径到最后一行,要求我们达到最后一行的每一个位置。问我们最少要走几条路,若无法达到最后一行的全部位置则要求输出有几个位置我们无法到达。

首先我们先对题目进行分析,因为流水路径是连续的,所以对于在可以到达最后一行每个位置的情况下,第一行某个位置作为起点,则其能到达最后一行的位置势必是连续的,不理解的可以自己画图举反例看看。对于每个起点所到最后一行我们可以看做是一个范围是[L,R]的区间,那接着我们只要求出哪几个区间能将总区间覆盖并使使用的区间最少,这就是区间最小覆盖问题。

  • 对于找第一行所对应很明显我们只要用广度优先搜索找出其对应的区间即可。但在这要注意要进行剪枝,不然讲道理是会被卡一个点的。因为每个点所能流到位置是固定的,所以如果X点能到达Y点,那X点也能到达Y所能到达的点。所以对于第一行我们只要对凸出来的最高点进行广搜。
    
    
    1
    2
    3
    4
    5
        for (i = 1; i <= m; i++)
        {
            if (map[1][i]<map[1][i+1]||map[1][i]<map[1][i-1]) continue;//判断是否有其他点可以流到该点
            ji[++ji[0]] = i; //将凸出的点记录到数组中
        }
  • 在已知第一行的范围后,我们只要跑一遍区间最小覆盖问题即可。
  • 用一个数组f[i]记录以i为左端点的区间能覆盖的最大距离,再用一个数组Ans记录能覆盖这个点的且向右距离最大的区间的右端点。最后再根据Ans让每个取得查询尽量靠右,统计取得区间个数即为最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    Ans[1] = f[1];
    for(i = 2; i <= m; i++)
    {  
        if(Ans[i-1]>f[i])  
        {  
            Ans[i] = Ans[i-1];  
        }  
        else  
        {  
            Ans[i]=f[i];  
        }  
    }  
   
    i = 1;
    int sum = 0;
    while (i<=m)
    {
        i = Ans[i]+1;
        sum++;
    }

以下为完整代码:

继续阅读【NOIP2010】引水入城 题解(Probably)

【NOIP2011】 Mayan游戏(gtmd搜索)

传送门:!点我传送!

话不多说,先贴代码


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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int map[6][8];

int ans[4][10];

void fall()
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 7; j++)
        {
            int x=i,y=j;
            while (map[x][y]!=0&&map[x][y-1]==0&&y>1)
            {
                map[x][y-1]=map[x][y];
                map[x][y]=0; y--;
            }
        }
    }
}

void check()
{
    int k = 1;
    while (k)
    {
        int map_D[6][8];
        memset(map_D,0,sizeof(map_D));
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 7; j++)
            {
                if (map[i][j] == 0) break;
               
                if (j>=3&&map[i][j] == map[i][j-1]&&map[i][j-1] == map[i][j-2])
                    map_D[i][j]=map_D[i][j-1]=map_D[i][j-2]=1;
                   
                if (i>=3&&map[i][j] == map[i-1][j]&&map[i-1][j] == map[i-2][j])
                    map_D[i][j]=map_D[i-1][j]=map_D[i-2][j]=1;
            }
        }
       
        k=0;
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 7; j++)
            {
                if (map_D[i][j] == 1)
                {
                    k = 1;
                    map[i][j] = 0;
                    map[i][0]--;
                }
            }
        }
        if (k) fall();
    }
}

void exchange(int x, int y, int k)
{
    if (map[x+k][y] != 0)
    {
        int ex=map[x+k][y];
        map[x+k][y] = map[x][y];
        map[x][y] = ex;
        check();
    } else
    {
        int ex=map[x+k][y];
        map[x+k][y] = map[x][y];
        map[x][y] = ex;
        map[x][0]--; map[x+k][0]++;
        fall();
        check();
    }
}

int boom = 0,n;
void dfs(int x)
{
    int sum = 0;
   
    int col[12];
    memset(col,0,sizeof(col));
    for (int i = 1; i <= 5; i++)
    {
        sum+=map[i][0];
        for (int j = 1; j <= map[i][0]; j++)
            col[map[i][j]]++;
    }
    for(int i = 1; i <= 10; i++)  
        if(col[i] != 0&&col[i] < 3) return;
         
    if(sum==0&&x<n) return;
    if(x==n)
    {
        if (sum==0)
            boom = 1;
        return;
    }
   
    int map1[6][8];
    memcpy(map1,map,sizeof map1);

    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= map[i][0]; j++)
        {
            for (int k = 1; k >= -1; k=k-2)
            {
                if (i == 5 && k == 1) continue;
                if (i == 1 && k == -1) continue;
                if (map[i][j] == map[i+k][j]) continue;
                if (k == -1 && map[i-1][j]!=0) continue;
                exchange(i, j, k);
                dfs(x+1);
                if (boom)
                {
                    ans[1][x] = i-1;
                    ans[2][x] = j-1;
                    ans[3][x] = k;
                    return;
                }
                memcpy(map,map1,sizeof map);
            }
        }
    }
   
}

int main(void)
{
    int i;
    scanf("%d", &n);
    for (i = 1; i <= 5; i++)
    {
        int x_;
        map[i][0] = 0;
        while (1)
        {
            scanf("%d", &x_);
            if (!x_) break;
            map[i][++map[i][0]] = x_;
        }
    }
    dfs(0);
    if(boom)
      for (i=0;i<n;i++)
        printf("%d %d %d\n",ans[1][i],ans[2][i],ans[3][i]);
    else printf("-1");
    return 0;
}

写得我心神憔悴,讲道理这题不难,所以难度就只有代码的构建。

对于这种脑残模拟,代码长度成了它报复社会的唯一方法。这题也就照着题目意思分成下面几个步骤

  1. 深搜:每次对每一个方块进行搜索,分别列举出其向右移和向左移的情况,找出符合题目要求情况即可。
  2. 下落:对于下落的判断只要是图中一个方块其底下有空,那其就得不断下落,直到接触方块为止,对于下落方块上方的方块也应进行下落。至于执行下落的时间就是在交换后或在去除方块后要执行下落的步骤。
  3. 去除方块:去除方块就是连续3个相同颜色要进行删除,在此要注意删除是在要搜索完整个图再进行删除,若是搜索到一个可删的三个方块就直接删除的话就无法判断类似“丁”字图形删除的了。同样这个步骤要在交换和下落后进行。
  4. 注意:去除方块后要执行下落,下落后要执行去除方块。。。直到没有方块去除为止

对于一些剪枝

在每次搜索过程中我们若发现某一颜色少于三种,那这种颜色就永远无法消去,直接return就好了。


1
2
3
4
5
6
7
8
    int col[12];
    memset(col,0,sizeof(col));
    for (int i = 1; i <= 5; i++)
    {
        sum+=map[i][0];
        for (int j = 1; j <= map[i][0]; j++)
            col[map[i][j]]++;
    }

因为题目要求答案按字典序输出,所以如果只是交换的话,和右边的方块交换是没有意义的(因为可看做右边的方块与左边的交换),同样,和相同方块交换也是没有意义的。


1
2
    if (map[i][j] == map[i+k][j]) continue;
    if (k == -1 && map[i-1][j]!=0) continue;

	

【NOIP2010】关押罪犯 题解(大概→_→)

题目传送门:!点我传送!

刚开始做的时候看到最小值这几个字,我们就应想到用贪心的想法,我们应该尽量的把先影响力高的两的犯人关到不同的监狱,直到发现有两个犯人已经被分配到相同的监狱,这两个犯人之间的影响力就是这题的答案。

二分法

二分法大家肯定都不陌生,这题只要对影响力进行二分,对于在二分出来的影响力X,只要是犯人之间的影响力小于X就判断在可容忍范围内,可将其关到同一监狱内,反之则必须分到不同监狱。时间最多应是O(log1,000,000,000),应还在时间范围内。

以下代码来自http://blog.csdn.net/cynthia_wjyi/article/details/47125015


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
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
struct Node{  
    int y,z,next;  
}e[200020];  
int tot,item,n,m;  
int head[20005],b[20005],a[100005];  
bool pd;  
int cmp(int a,int b){return a<b;}  
void insert(int x,int y,int z)  
{  
    e[++tot].y=y;  
    e[tot].z=z;  
    e[tot].next=head[x];  
    head[x]=tot;  
}  
void dfs(int x,int data)  
{  
    if(pd==false)return;  
    b[x]=data;  
    for(int i=head[x];i!=0;i=e[i].next)  
    {  
        if(e[i].z>item)  
        {  
            if(b[e[i].y]==-1)dfs(e[i].y,1-data);  
            else  
            if(b[e[i].y]==data){pd=false;return;}  
        }  
    }  
}  
bool work(int midd)  
{  
    memset(b,-1,sizeof(b));  
    pd=true;  
    item=a[midd];  
    for(int i=1;i<=n;i++)  
    if(b[i]==-1)dfs(i,0);  
    return pd;  
}  
int main()  
{  
    scanf("%d%d",&n,&m);  
    memset(head,0,sizeof(head));  
    int x,y,z;  
    tot=0;  
    for(int i=1;i<=m;i++)  
    {  
        scanf("%d%d%d",&x,&y,&z);  
        insert(x,y,z);  
        insert(y,x,z);  
        a[i+1]=z;  
    }  
//  for(int i=1;i<=tot;i++)cout<<e[i].y<<' '<<e[i].z<<' '<<e[i].next<<endl;  
    a[1]=0;  
    sort(a+1,a+1+m,cmp);  
//  for(int i=1;i<=m+1;i++)cout<<a[i]<<' ';  
//  cout<<endl;  
    int l=1,r=m+1,mid;  
    while(l<r)  
    {  
        mid=(l+r)/2;  
//      cout<<l<<' '<<r<<' '<<mid<<endl;  
        if(work(mid)==true)r=mid;  
        else l=mid+1;  
    }  
    printf("%d\n",a[l]);  
}

并查集

这题我乍一看以为是二分图,其实用并查集的思想就可以做。

  1. 对于并查集的判断顺序,通过贪心的思想得出是要从大到小,保证答案最小。所以要先对于影响力对每一对犯人进行排序。
  2. 对于每个犯人我们可以创造一个他的镜像,比如犯人X和犯人Y,我们需加入犯人Px和犯人Py。
  3. 在操作过程中我们只需不断将X、Py并入一个集合,同样将Y、Px也并入一个集合。在发现X,Y已处于同一集合时就说明他们已经被分配到相同的监狱,这时他们之间的影响力即是答案。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

struct sd
{
    int x,y,z;
}hate[100100];

int father[50000];

bool com (sd a, sd b)
{
    return a.z > b.z;
}

void start(int n)
{
    for (int i = 1;i <= n; i++) father[i]=i;
}

int xfind(int x)
{
    return father[x] == x ? x : xfind(father[x]);
}

void un(int a, int b)
{
    father[xfind(a)] = xfind(b);
}

int main(void)
{
    int i,n,m;
   
    scanf("%d%d", &n, &m);
    start(n*2);
   
    int po=m;
    while (m--) scanf("%d%d%d",&hate[m].x,&hate[m].y,&hate[m].z);
   
    sort(hate+1,hate+po+1,com);
   
    int ans=0;
    for (i=1;i<=po;i++)
    {
        if (xfind(hate[i].x)==xfind(hate[i].y))
        {
            ans=hate[i].z;
            break;
        }
       
        un(hate[i].x,hate[i].y+n);
        un(hate[i].y,hate[i].x+n);
    }
   
    printf("%d", ans);
    return 0;
}

【[NOIP2009】靶形数独 题解(大概)

题目传送门:!点我传送!

题目再怎么看也就只是简单的数独(sudoku)而已,其实没比基本的数独难到哪去。

先从最基本的数独开始讲,在程序中做数独最经常还是用深搜(Depth First Search),在进行剪枝后再对种种可能进行一一搜索。对于剪枝的方法还是要从数独的规则入手:满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。在此我们可以用数组通过统计每一行、每一列、每一个粗线宫中存在的数字在讨论剩余空格中数字的可能。个人在在每次dfs时会先找出可能的数字最少的点优先进行搜索,这样可以减少不少时间(也算是个不小的优化吧)。

在此题中我们用上述做法找到所以可能并把最大的ANS找出进行输出即是答案。

 



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
110
111
112
113
114
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int L[10][10],H[10][10],A[10][10]; //列 行 area
int map[10][10],ANS=0;
 
int Area(int x,int y)  
{  
    return  (x-1)/3*3+(y+2)/3;  
}

int Abs(int x)  
{  
    return x > 0 ? x : -x;  
}
 
int Score(int x,int y)  
{  
     return 10-max(Abs(x-5),Abs(y-5));  
}

int boom = 0;
void start()
{
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        int k = Area(i, j);
                        if (map[i][j])
                        {
                                if (!H[i][map[i][j]]&&!L[j][map[i][j]]&&!A[k][map[i][j]])
                                {
                                        H[i][map[i][j]]=L[j][map[i][j]]=A[k][map[i][j]]=1;
                                }else
                                {
                                        boom = 1; return;
                                }
                        }
                }
        }
}


void dfs(int now)
{
        int g_max=0, minn=10, px, py;
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        if (map[i][j]) continue;
                        int num = 0, sd=0;
                        for (int k = 1; k <= 9; k++)
                        {
                                if (H[i][k] || L[j][k] || A[Area(i, j)][k]) continue;
                                num++; sd=k;
                        }
                        if (num == 0) return;
                        if (num < minn)
                        {
                                minn = num;
                                px=i; py =j;
                        }
                        g_max += sd*Score(i,j);
                }
        }
       
        if(g_max+now <= ANS)  return ;  
    if(g_max == 0)  
    {  
        boom=1;  
        ANS = max(ANS,now);  
        return ;  
    }  
       
        for (int k = 1; k <= 9; k++)
        {
                if (H[px][k] || L[py][k] || A[Area(px, py)][k]) continue;
               
                H[px][k] = L[py][k] = A[Area(px, py)][k] =1;
                map[px][py] = k;
               
                dfs(now+k*Score(px, py));
               
                map[px][py] = 0;
                H[px][k] = L[py][k] = A[Area(px, py)][k] =0;
        }
        return;
}

int main(void)
{
       
        for (int i = 1; i <= 9; i++)
          for (int j = 1; j <= 9; j++)
          {
                scanf("%d", &map[i][j]);
                ANS+=map[i][j]*Score(i,j);
          }
        start();
        if (boom)
        {
                printf("-1");
                return 0;
        }
        dfs(ANS);
        if (boom) printf("%d", ANS);
        else printf("-1");
}


	

【NOIP】2008 提高组 双栈排序

题目传送门:!点我传送!

主要思想:二分图染色


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
#include<cstdio>
#include<iostream>
 
using namespace std;
 
int Stack_A[1010], Stack_B[1010];
int IN[1010], MIN[1010];
char ANS[10100];
 
int dui[10100], fa[10100], start[1010];
int col[1010];
 
void line(int i, int j)
{
    dui[++dui[0]] = j; fa[dui[0]] = start[i]; start[i] = dui[0];
    dui[++dui[0]] = i; fa[dui[0]] = start[j]; start[j] = dui[0];
}
 
int boom = 0;
 
void draw(int x, int c)
{
    if (!col[x]) col[x] = c;
        else if (col[x] != c) {boom = 1; return;}
            else return;
    for (int i = start[x]; i != 0; i = fa[i]) draw(dui[i], 3-c);
}
 
int main(void)
{
    int n, i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &IN[i]);
   
    int num = 1; i = 1;
    int head_A = 0, head_B = 0;
    int sum = 0;
    Stack_A[0] = Stack_B[0] = 2000000000;
   
    MIN[n] = IN[n];
    for (i = n-1; i >= 1; i--)
        MIN[i] = MIN[i+1] < IN[i] ? MIN[i+1] : IN[i];
       
    for (i = 1; i <= n-2; i++)
        for (j = i+1; j <= n-1; j++)
            if  (IN[i]<IN[j]&&MIN[j+1]<IN[i])
                line(i,j);
   
    for (i = 1; i <= n; i++)
    {
        if(!col[i]) draw(i,1);
        if (boom)
        {
            printf("0");
            return 0;
        }
    }
   
    i = 1;
    while (num <= n)
    {
        if (num == Stack_A[head_A])
        {
            num++; ANS[sum++]='b';
            ANS[sum++]=' ';
            head_A--; continue;
        }
        if (num == Stack_B[head_B])
        {
            num++; ANS[sum++]='d';
            ANS[sum++]=' ';
            head_B--; continue;
        }
        if (IN[i] < Stack_A[head_A]&&col[i] == 1)
        {
            Stack_A[++head_A] = IN[i++];
            ANS[sum++]='a'; ANS[sum++]=' ';
        }
        else
        if (IN[i] < Stack_B[head_B]&&col[i] == 2)
        {
            Stack_B[++head_B] = IN[i++];
            ANS[sum++]='c'; ANS[sum++]=' ';
        }
        else
        {
            printf("0");
            return 0;
        }
    }
    printf("%s", ANS);
    return 0;
}

【noip2005】篝火晚会 题解报告(→_→)

传送门:!点我传送!

首先,毫无疑问,即使是在毫无思路的情况下,我们也应先把期待的序列求出,个人想法只是一个遍历加一些奇怪的判断,在此过程中,我们可以十分轻易的拿到“-1”答案的分值。在求出期待序列后,我们再对其分析。

明显地 ,当一个人到达了他想在的位置后,就永远不需要再挪动了,而且每个人到达它想在的位置的代价必定为1(最赖皮情况就是每次两两交换),因此,当目标序列确定时,不在位人数即为这种情况下的解

当然由于题目是绕着篝火以圆的方式排列,所以并无所谓的起始点。意思就是我们要把每个点当做起始点,再依次与期待序列进行比较,找出最少不在位人数(answer)。

30%

暴力解法就是直接暴搜所有情况,找出最小答案输出,时间复杂度应是起始点个数*队列长度O(n^2),期待得30%的点。

100%

以下要说的方法是我在一篇博文中看到的。30%的方法中,我把每种情况都枚举,这是没必要的。在目标环中,如果一些元素的相对位置与原环中的相同,我就可以让两个环中的这些元素对齐,此时若这些元素的个数为k,则代价m=N-k。明显地,找出最长的一组就可以让代价最小。

要找最长的相对位置相同的串,也就是找最长的递增且权值之差等于序号之差的序列,DP可行,加入优化可以到O(nlogn)。

当然还有一种简单的方法,如果a和b的相对位置与序号的相对位置和c和d的相对位置与序号的相对位置相同,并无法确定a、b、c、d相对位置是否都与序号的相对位置相同。但是我如果知道a与其序号位置、b与其序号位置、c与其序号位置、d与其序号位置的差值都相等,就一定有a、b、c、d与序号的相对位置相等。因此用f[i]存储目标环中权值与序号差值为i的数的个数,最后找出最大值maxx,N-maxx即为解。同样要反向做一次。时空复杂度皆为O(N)。注意:所考虑的1,2,3,4,5,6,7,8和1,8,7,6,5,4,3,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
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
110
111
112
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int MAX = 50000;

int f[200000];
int a[50100];

int num[2][50100];
int w[50100], ji[50100], n;

int main(void)
{

    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        a[i] = n-i+2;
        scanf("%d%d", &num[0][i], &num[1][i]);
    }
    a[1] = 1;
    w[1] = 1; i = 1; ji[1] = 1;
    int k = num[0][1], fa = 1;
    while (i<n)
    {
       
        if (i == n-1)
        {
            int sd = 1;
            for (j = 0; j <= 1; j++)
            {
                if (num[j][k] != fa) continue;
                if (ji[num[1-j][k]] != 1) continue;
                sd = 0;
                w[++i] = k;
                ji[k] = 1;
            }
            if (sd)
            {
                printf("-1\n");
                return 0;
            }
            continue;
        }
       
        int mas = 1;
       
        for (j = 0; j <= 1; j++)
        {
            if (num[j][k] != fa) continue;
            if (ji[num[1-j][k]]) break;
            mas = 0;
            w[++i] = k;
            fa = k;
            k = num[1-j][k];
            ji[w[i]] = 1;
        }
        if (mas)
        {
            printf("-1\n");
            return 0;
        }
    }
   
    int maxx = -1;
    for (i = 1; i <= n; i++)
    {
        int forward, back;
        if (w[i] >= i)
        {
            forward = w[i]-i;
            back = (i-w[i]+n)%n;
        } else
        {
            back = i-w[i];
            forward = (w[i]-i+n)%n;
        }
        f[MAX+forward]++;
        f[back]++;
        maxx = maxx < f[MAX+forward] ? f[MAX+forward] :maxx;
        maxx = maxx < f[back] ? f[back] :maxx;
       
    }
   
    memset(f,0,sizeof(f));
    for (j = 1; j <= n; j++)
    {
        int forward, back;
        i = a[j];
        if (w[j] >= i)
        {
            forward = w[j]-i;
            back = (i-w[j]+n)%n;
        } else
        {
            back = i-w[j];
            forward = (w[j]-i+n)%n;
        }
        f[MAX+forward]++;
        f[back]++;
        maxx = maxx < f[MAX+forward] ? f[MAX+forward] :maxx;
        maxx = maxx < f[back] ? f[back] :maxx;
       
    }
    printf("%d", n-maxx);

    return 0;
}

 

题解报告Problem [NOIP2016] D2T1

题目传送门 :!点我传送!

惯例NOIP签到题

方法:杨辉三角+矩阵和(大概)

杨辉三角我话就不多说了,这题只要把其化成在杨辉三角的前n行m列中有多少个数符合题意,在这个过程中可以用递推的方法去进行优化。

好,下面直接贴代码。


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
#include<cstdio>
#include<iostream>
 
using namespace std;
 
long long f[2110][2110], num[2110][2110];
 
int Mod, Nx = 2005;
 
void WORK()
{
    f[1][1]=1;
   
    int i, j;
   
    for (i = 2; i <= Nx; i++)
    {
        for (j = 1; j <= i; j++)
        {
            int Pi = 1;
           
            f[i][j] = (f[i-1][j] + f[i-1][j-1]) % Mod;
            if (f[i][j]%Mod) Pi = 0;
           
            if (i!=j) num[i][j] = num[i][j-1] + num[i-1][j] - num[i-1][j-1] +Pi;
            else num[i][j] = num[i][j-1] + Pi;
        }
    }
}
 
int main(void)
{
    int t;
    cin >> t >> Mod;
   
    WORK();
   
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        m = m > n? n : m;
        m++; n++;
       
        cout << num[n][m] << endl;
    }
    return 0;
}