搜索与回溯算法与训练心得

搜索与回溯算法即为了求得问题的解,先选择某一种可能的情况向前搜索,一旦发现原来的选择是错误的,就应退回一步重新选择,继续向前搜索,如此反复进行,直至得到解或证明正解。
奉上算法框架:
int search(int k)
{
if(到目的地)
输出解
else
for(int i=1;i<=算符种数;i++)
if(满足条件)
{
保存结果;
search(k+1);
恢复,保存结果之前的状态(回溯)
}
心得:学习每一种算法,应先去理解算法的各个方面,并且熟练每一种算法,能够解决有关题目,且应细致认真,坚持不懈。

Day3

【作文】
题意:求一个字符串的子串,使其在字符串中至少出现三次,分别是前缀、后缀、以及非前、后缀。
字符串匹配,考虑KMP,分别将字符串删去前一个字符和后一个字符,将这两个串进行匹配,求出前缀、后缀的可行长度。对原串求next数组,在可行前后缀的位置求答案。
正解是二分,哈希暴力求出前后缀的可行长度,二分这些长度暴力判断。
【智能机器人】
题意:用多个机器人遍历一棵树,使消耗的代接最小。
首先,一个明显的结论,如果从某个节点往下走去了多于1个机器人,那么它们绝对不会再回头.如果它们有一个回头,则令这个机器人处于该节点的父节点不动,令另外一个机器人先走这个机器人走的路线然后在走自己的路线,就会更优!
令f[x][i]表示i个机器人走完x子树的最优值。g[x]表示只用一个机器人走x子树(即机器人要回到x点)。可得:
f[x][i] = min(f[x][i - j] + f[y][j] + w * j)。
f[x][i] = min(g[x] + f[y][i] + w * i)。
f[x][i] = min(f[x][i] + g[y] + w * 2)。
g[x] = g[x] + g[y] + w * 2。
【大都市】
题意:给定一棵树,从1结点出发,每次修改一条边,求到某个点的路径上经过的未修改路径树。
可以发现,如果修改一条边,则这条边所连接的子树答案都会改变(-1)。联想到DFS序,在DFS序中,一个点的子树是一段连续的区间,那么,可以使用数据结构来维护修改,如树状数组,线段树。

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

【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;

	

【[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");
}


	

[FJWC2016] 树上三角形

树上三角形

不妨设三条线段的长度分别a, b, c,且满足abc,由几何知识可知,若a + b > c这三条线段即可构成一个三角形。那么若要使得若干线段无法构成三角形,令a + b = c即可使线段总数最大。由于点权范围满足,那么当线段长度分别为1, 1, 2, 3, 5, 8, 13······时,线段总数最大。显然这个数列为斐波那契数列。由计算可知,斐波那契数列的第47项>,那么当u和v的简单路径上有大于46个点权时,必定存在以其中三个权值为边长构成的三角形。

预处理出每个节点的子节点来计算深度。

对于修改操作,直接修改即可。

对于查询操作,暴力枚举u,v的路径,若总数大于46即可输出Y,否则排序后判断。注意两边权相加后可能会溢出int/longint。

时间复杂度为

继续阅读[FJWC2016] 树上三角形