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+组

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