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


	

01 背包问题——遗传算法

一种仿生(?)的模拟优化算法。

Reference:

https://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

http://blog.csdn.net/v_july_v/article/details/6132775

遗传算法的0-1背包问题(c语言).doc

具体内容参考资料已经讲得很详细了,我就不再赘述了。

注意遗传算法是一种随机算法,需要适当地选择参数与迭代次数才能尽可能地保证答案准确性。

代码实现(较长):

继续阅读01 背包问题——遗传算法

NOIP2016普及组T1买铅笔

水题,直接模拟。

代码块示例:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;

int work(int a, int b, int c)
{
  int ans = (c / a) * b;
  if (c % a) ans += b;
  return ans;
}

int main(void)
{
  int n;
  cin << n;
  int x, y, ans = 100000000;
  for (int i = 1;i &lt;= 3; i++) {
  cin >> x >> y;
  ans = min(ans, work(x, y, n));
  }
  cout << ans;
  return 0;
}