Welcome to BeckoninGshy's Bolg

POJ-1416-Shreddin-Company

POJ-1416

描述：

You have just been put in charge of developing a new shredder for the Shredding Company Although a “normal” shredder would just shred sheets of paper into little pieces so that the contents would become unreadable, this new shredder needs to have the following unusual basic characteristics.

  • 1.The shredder takes as input a target number and a sheet of paper with a number written on it.

  • 2.It shreds (or cuts) the sheet into pieces each of which has one or more digits on it.

  • 3.The sum of the numbers written on each piece is the closest possible number to the target number, without going over it.

For example, suppose that the target number is 50, and the sheet of paper has the number 12346. The shredder would cut the sheet into four pieces, where one piece has 1, another has 2, the third has 34, and the fourth has 6. This is because their sum 43 (= 1 + 2 + 34 + 6) is closest to the target number 50 of all possible combinations without going over 50. For example, a combination where the pieces are 1, 23, 4, and 6 is not valid, because the sum of this combination 34 (= 1 + 23 + 4 + 6) is less than the above combination’s 43. The combination of 12, 34, and 6 is not valid either, because the sum 52 (= 12 + 34 + 6) is greater than the target number of 50.

Figure 1. Shredding a sheet of paper having the number 12346 when the target number is 50

There are also three special rules :

  • 1.If the target number is the same as the number on the sheet of paper, then the paper is not cut.

For example, if the target number is 100 and the number on the sheet of paper is also 100, then the paper is not cut.

  • 2.If it is not possible to make any combination whose sum is less than or equal to the target number, then error is printed on a display. For example, if the target number is 1 and the number on the sheet of paper is 123, it is not possible to make any valid combination, as the combination with the smallest possible sum is 1, 2, 3. The sum for this combination is 6, which is greater than the target number, and thus error is printed.

  • 3.If there is more than one possible combination where the sum is closest to the target number without going over it, then rejected is printed on a display. For example, if the target number is 15, and the number on the sheet of paper is 111, then there are two possible combinations with the highest possible sum of 12: (a) 1 and 11 and (b) 11 and 1; thus rejected is printed. In order to develop such a shredder, you have decided to first make a simple program that would simulate the above characteristics and rules. Given two numbers, where the first is the target number and the second is the number on the sheet of paper to be shredded, you need to figure out how the shredder should “cut up” the second number.

输入：

The input consists of several test cases, each on one line, as follows :

1
2
3
4
5
tl num1
t2 num2
...
tn numn
0 0

Each test case consists of the following two positive integers, which are separated by one space : (1) the first integer (ti above) is the target number, (2) the second integer (numi above) is the number that is on the paper to be shredded.

Neither integers may have a 0 as the first digit, e.g., 123 is allowed but 0123 is not. You may assume that both integers are at most 6 digits in length. A line consisting of two zeros signals the end of the input.

输出：

For each test case in the input, the corresponding output takes one of the following three types :

1
2
3
sum part1 part2 ...
rejected
error

In the first type, partj and sum have the following meaning :

1.Each partj is a number on one piece of shredded paper. The order of partj corresponds to the order of the original digits on the sheet of paper.

2.sum is the sum of the numbers after being shredded, i.e., sum = part1 + part2 +…

Each number should be separated by one space.
The message error is printed if it is not possible to make any combination, and rejected if there is
more than one possible combination.
No extra characters including spaces are allowed at the beginning of each line, nor at the end of each line.

输入示例：

1
2
3
4
5
6
7
8
9
10
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0

输出示例：

1
2
3
4
5
6
7
8
9
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected

题目大意：

给你一个有n个数的纸条，一个目标值，你可以任意剪纸条，要找出剪出的数的和最接近并且小于目标数的分解方式。

如果该数可以由多个分解方式组成，则输出error；如果无论如何分解都比目标值大，则输出rejected。如果分解值和目标数相同，则直接输出。

思路：

首先对于剪纸条，无论如何剪，相邻数的位置关系并不会发生变化，只是选择元素的个数会发生变化，则可以dfs枚举所有的可能————对于某一过程，可以选择从该数开始到纸条结尾，每次都选择增加一个数，然后进行下一层的dfs，即可取得所有的分解组合。

接下来要保留选择数的路径，我们使用一个数的每一位来记录当前选择了几个数（N最大为6位，所以一位足够表示）。

然后，对于大于目标数的情况，只有当最小分解方式（每一位都被分解）之和都比目标值大，则可以直接输出rejected。该步可在dfs之前判断。

对于error的情况，只要在每次更新当前值的时候，也更新其相同的次数，如果大于1，则符合该情况。

可以小小的剪枝下：当过程中的取值比目标值大的话，就可以直接剪掉。

最后就是编码的时刻了！

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
vector<vector<int> > ans;
int num; //目标数
int npath; //最优路径
int curNum; //当前数，dfs中间值
int cntNum; //当前数的出现次数。

/*
将结果数组中的各值相加
*/
int getNum(vector<vector<int> > t, int n){
    int ans = 0;
    int cont = 0;
    for(int j = 0; j < t.size(); j++){
        int c = 0;
        cont += t[j].size();
        for(int k = 0; k < t[j].size(); k++){
            c = c*10 + t[j][k];
        }    
        ans +=c;
    }
    return ans;
}
/*
i:当前位置
n：总长度
path：记录每次分割长度
s：总数据
t：结果数组。
*/
void dfs(int i,int n,int path,char s[],vector<vector<int> > t){
    int tt = getNum(t,n);
    //如果过程中已经比当前数大了，直接剪掉
    if(tt > num) return;
    
    if(i == n){
        //在当前一轮结束时更新离目标数最近并小于目标数的值、次数与路径。
        if(curNum < tt){
            cntNum = 1;
            curNum = tt;
            npath = path;
        }else if(curNum == tt){
            cntNum++;
        }
        return;
    }
    /*
    dfs核心：
    输入：1234
    生成下列排列
    1 2 3 4 
    1 2 34 
    1 23 4 
    1 234 
    12 3 4 
    12 34 
    123 4 
    1234
    */
    vector<int> a;
    for(int j = i; j < n; j++){
        a.push_back(s[j]-'0');
        t.push_back(a);
        dfs(j+1,n,path*10+j-i+1,s,t);
        t.pop_back();
    }
    
}

//根据path输出各个数。
void show(char s[],int path){
    vector<int> a;
    while(path){
        a.push_back(path%10);
        path/=10;
    }
    reverse(a.begin(),a.end());
    int j = 0;
    for(int i = 0; i < a.size(); i++){
        printf(" ");
        for(int k = 0; k < a[i]; k++){
            printf("%c",s[j++]);
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int a;
    char s[1000];
    while(scanf("%d%s",&a,s) && a){
        vector<vector<int> > t;
        num = a;
        curNum = 0;
        cntNum = 0;

        int sum = 0;
        for(int i = 0; i < strlen(s); i++){
            sum += s[i]-'0';
        }
        //给定数的每一位相加都比目标数大
        if(sum > a){
            printf("error\\n");
        }else{
            dfs(0,strlen(s),0,s,t);
            if(cntNum > 1){
                printf("rejected\\n");
            }else{
                printf("%d",curNum);
                show(s,npath);
                printf("\\n");
            }
        } 
    }
    return 0;
}
阅读更多
POJ-3083-Childre-o-th-Cand-Corn

POJ-3083

描述：

The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through the maze facing zombies, chainsaw-wielding psychopaths, hippies, and other terrors on their quest to find the exit.

One popular maze-walking strategy guarantees that the visitor will eventually find the exit. Simply choose either the right or left wall, and follow it. Of course, there’s no guarantee which strategy (left or right) will be better, and the path taken is seldom the most efficient. (It also doesn’t work on mazes with exits that are not on the edge; those types of mazes are not represented in this problem.)

As the proprieter of a cornfield that is about to be converted into a maze, you’d like to have a computer program that can determine the left and right-hand paths along with the shortest path so that you can figure out which layout has the best chance of confounding visitors.

输入：

Input to this problem will begin with a line containing a single integer n indicating the number of mazes. Each maze will consist of one line with a width, w, and height, h (3 <= w, h <= 40), followed by h lines of w characters each that represent the maze layout. Walls are represented by hash marks (‘#’), empty space by periods (‘.’), the start by an ‘S’ and the exit by an ‘E’.

Exactly one ‘S’ and one ‘E’ will be present in the maze, and they will always be located along one of the maze edges and never in a corner. The maze will be fully enclosed by walls (‘#’), with the only openings being the ‘S’ and ‘E’. The ‘S’ and ‘E’ will also be separated by at least one wall (‘#’).

You may assume that the maze exit is always reachable from the start point.

输出：

For each maze in the input, output on a single line the number of (not necessarily unique) squares that a person would visit (including the ‘S’ and ‘E’) for (in order) the left, right, and shortest paths, separated by a single space each. Movement from one square to another is only allowed in the horizontal or vertical direction; movement along the diagonals is not allowed.

输入示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########

输出示例：

1
2
37 5 5
17 17 9

题目大意：

有一张地图，# 是墙壁，. 是路，S是点，E是终点。（S和E在地图边缘且不在四个对角）

问：优先选择左边到达终点的路径长度（目前朝向的左边为优先选边，顺时针），优先选择右边到达终点的路径长度（目前朝向的右边为优先选边，逆时针），和最短的路径长度。

思路：

该题使用dfs（前两问）加bfs（后一问）来解答，由于有一个优先选择当前方向的左边或者右边位置，所以需要处理一个当前的朝向问题。比普通的dfs要复杂一点。但是根据定义的方向数组，只要知道了向左转就是当前的朝向减一个单位，右转为当前的朝向加一个单位，以此为起始探测方向，并且处理好顺逆时针关系就可以化解该题。

Solution：

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

const int MAXN = 50;
char m[MAXN][MAXN];

int N,M;
int sx,sy,ex,ey;
int ans;
int flag;
struct node{
    int x,y,d;
    node(){}
    node(int _x,int _y, int _d):x(_x),y(_y),d(_d){}
};

//从左顺时针
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};


void dfs(int x, int y, int pos,int t,int s){
    // printf("%d %d %d\\n",x,y,d);
    if(flag) return;
    if(x == ex && y == ey){
        flag = 1;
        ans = max(ans,s);
        return;
    }
    //t = -1 表示顺时针，t = 1 表示逆时针
    //pp : 当前的方向
    //如果是左优先，就将当前方向-1开始顺时针，
    //如果是右优先，就将当前方向+1开始逆时针。
    for(int i = 1,pp = (pos+t+4)%4; i <= 4; i++,pp = (pp-t+4)%4){
        int nx = dx[pp] + x;
        int ny = dy[pp] + y;
        if(nx >= 0 && nx < N && ny >= 0 && ny < M && m[nx][ny] == '.'){
            dfs(nx,ny,pp,t,s+1);
            if(flag) return;
        }
    }

}


void bfs(int x,int y){
    queue<node> q;
    q.push(node(x,y,1));
    m[x][y] = '#';
    node temp;
    while(q.size()){
        temp = q.front();q.pop();
        if(temp.x == ex && temp.y == ey){
            ans = temp.d;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = dx[i] + temp.x;
            int ny = dy[i] + temp.y;
            if(nx >= 0 && nx < N && ny >= 0 && ny < M && m[nx][ny] == '.'){
                m[nx][ny] = '#';
                q.push(node(nx,ny,temp.d+1));
            }
        }
    }
}

int main(){
    int T;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&T);
    while(T--){
        int pos = 0;
        scanf("%d%d",&M,&N);
        // memset(m,0,sizeof(m));
        for(int i = 0; i < N; i++){
            scanf("%s",m[i]);
            for(int j = 0; j < M; j++){
                if(m[i][j] == 'S'){
                    sx = i,sy = j; m[i][j] = '.';
                }else if(m[i][j] == 'E'){
                    ex = i,ey = j; m[i][j] = '.';
                }
            }
        }
        // for(int i = 0; i < N; i++){
        //     for(int j = 0; j < M; j++){
        //         printf("%c",m[i][j]);
        //     }
        //     printf("\\n");
        // }
        /*
        pos = 0 表示向上为初始方向
        pos = 1 表示向右为初始方向
        pos = 2 表示向下为初始方向
        pos = 3 表示向左为初始方向
        */
        if(sx == 0) pos = 2;
        if(sx == N-1) pos = 0;
        if(sy == 0) pos = 1;
        if(sy == M-1) pos = 3;
        ans = 0;
        flag = 0;
        dfs(sx,sy,pos,-1,1);
        printf("%d",ans);
        ans = 0;
        flag = 0;
        dfs(sx,sy,pos,1,1);
        printf(" %d",ans);
        ans = 0;
        bfs(sx,sy);
        printf(" %d\\n",ans);
    }
    return 0;
}
阅读更多
LeetCode-473-火柴拼正方形

473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

1
2
输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

1
2
输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

注意:

给定的火柴长度和在 0 到 10^9之间。火柴数组的长度不超过15。

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
class Solution {
public:
    int part;
    vector<bool> vis;
    bool f = true;
    bool makesquare(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];
        if(!sum || sum%4) return false;
        part = sum / 4;
        vis = vector<bool>(nums.size());
        //从大到小枚举所有边
        sort(nums.begin(),nums.end(),greater<int>());
        return dfs(nums,0,0,part);
    }
    //u:当前选了几个数，sum：当前的和，k:选到了第几层
    bool dfs(vector<int> &nums,int u,int cur,int length){
        if(cur == length) u+=1,cur=0;
        if(u == 4) return true;
        for(int i = 0; i < nums.size(); i++){
            //
            if(!vis[i] && cur+nums[i] <= length){
                vis[i] = true;
                if(dfs(nums,u,cur+nums[i],length)) return true;
                vis[i] = false;
                //如果当前木棒拼接失败，并且是第一个，则剪掉。
                if(cur == 0) return false;
                //如果当前木棒拼接失败，并且是最后一个，则剪掉。
                if(cur + nums[i] == length) return false;
                //如果当前木棒拼接失败，跳过所有相同长度的木棒。
                while(i+1 < nums.size() && nums[i] == nums[i+1]) i++;
                
            }
        }
        return false;
    }
};

思路：

剪枝策略：

  • 从小到大枚举所有边
  • 每条边内部的木棒长度规定为从大到小
  • 如果当前木棒拼接失败，则跳过接下来所有长度相同的木棒。
  • 如果当前木棒拼接失败，且是当前边的第一个，则直接剪掉当前分支。
  • 如果当前木棒拼接失败，且是当前边的最后一个，则直接剪掉当前分支。
阅读更多
LeetCode-216-组合总-III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。

  • 解集不能包含重复的组合。

示例 1:
1
2
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
1
2
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

Solution：

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(0,1,0,k,n);
        return ans;
    }
    //u:当前选择数的个数，a：当前可以枚举的位置，sum:当前组合数的和。
    void dfs(int u,int a,int sum,int k,int n){
        if(u == k && sum == n){
            ans.push_back(tmp);
            return;
        }
        if(a == 10){
            return;
        }
        if(sum > n) return;
        for(int i = a; i < 10; i++){
            tmp.push_back(i);
            dfs(u+1,i+1,sum+i,k,n);
            tmp.pop_back();
        }
        
    }
};
阅读更多
LeetCode-47-全排-II

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: 

1
[1,1,2]

输出:

1
2
3
4
5
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution1(set去重)：

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<bool> bt;
    int n;
    set<vector<int>> s;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        bt = vector<bool>(n);
        sort(nums.begin(),nums.end());
        dfs(0,0,nums);
        return ans;
    }
    void dfs(int u,int start,vector<int> &nums){
        if(u == n){
            if(!s.count(tmp)){
            ans.push_back(tmp);
                s.insert(tmp);
            }
            return;
        }
        for(int i = 0; i < n; i++){
            if(!bt[i]){
                bt[i] = true;
                tmp.push_back(nums[i]);
                dfs(u+1,start,nums);
                tmp.pop_back();
                bt[i] = false;
            }
        }
    }
};

思路：

去重问题，首先想到set，比较简单粗暴的都放到set容器里，有重复就不往答案里面去。

Solution2（排序去重）：

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
class Solution {
    
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<bool> bt;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        bt = vector<bool>(n);
        sort(nums.begin(),nums.end());
        dfs(0,0,nums);
        return ans;
    }
    bool judge(int i,vector<int> nums){
        for(int j = 0; j < i; j++){
            if(nums[i] == nums[j]){
                if(!bt[j]) return false;
            }
        }
        return true;
    }
    
    void dfs(int u,int start,vector<int> &nums){
        if(u == n){
            ans.push_back(tmp);
            return;
        }
        for(int i = 0; i < n; i++){
            //如果所选是重复数，并且前面都选过了，才能选择当前的。
            if(!bt[i] && (i == 0 ? 1 : nums[i-1] == nums[i] ? bt[i-1] : 1)){
                bt[i] = true;
                tmp.push_back(nums[i]);
                dfs(u+1,start,nums);
                tmp.pop_back();
                bt[i] = false;
            }
            
        }
    }
};

思路：

选择不重复元素的全排列我们已经解决过了，现在我们研究如何去重的问题。

首先我们发现去重的原因是两个位置不同的相同的数在交换之后，整体排列不变，这样就会产生重复，为了达到去重的目的，我们人为规定，当前元素必须在所有在它之前的元素都已经被选了以后，它才能选。这样，相同元素的相对位置就固定下来，不会发生交换重复问题。所以为了方便，我们把相同的元素排在一起，这时需要先排序。

阅读更多
费解的开关

费解的开关

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

1
2
3
4
5
10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

1
2
3
4
5
01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

1
2
3
4
5
01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式

第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
输出格式

一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围：0<n≤500

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

1
2
3
3
2
-1

Solution1（TLE）：

我们可以枚举每个开关的状态，然后查看是否全亮，每个开关两个状态（开和关），一共有25个开关，所以复杂度为O(2^25) = 33554432次。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int m;
int ans = 26;
void flip(int k){
    int i = k / 5,j = k % 5;
    m ^= 1 << k;
    if(j-1 >= 0) m ^= (1 << (i * 5 + (j-1)));
    if(j+1 < 5) m ^= (1 << (i *5 + (j+1)));
    if(i-1 >= 0) m ^= (1 << ((i-1) *5 + j));
    if(i+1 < 5) m ^= (1 << ((i+1) *5 + j));
}

void dfs(int k,int d){
    if(m == (1<<25)-1){
        ans = min(ans,d);
        return;
    }
    if(k >= 26) return;
    dfs(k+1,d);
    flip(k);
    dfs(k+1,d+1);
    flip(k);
}

int main(){
    freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    getchar();
    while(T--){
        char c[10];
        m = 0;
        ans = 26;
        for(int i = 0; i < 5; i++){
            scanf("%s",c);
            for(int j = 0; j < 5; j++){
                if(c[j] == '1') m |= (1 << (i*5+j));
            }
            printf("%s\\n",c);
            getchar();
        }
        printf("%#x\\n",m);
        dfs(0,0);
        if(ans > 6) ans = -1;
        printf("%d\\n",ans);
    }
    
    return 0;
}

Solution2：

我们可以从行的角度来看：
如果当前行确定了，我们要让所有的开关打开，就要选把当前行中关闭的灯的下面位置的切换状态。
归纳到一般情况，当第一行的状态确定了，我们为了使所有的开关打开，去下一行改变状态，使得当前行的所有灯打开。如此4次后，由于到达了最后一行，这时，我们检查最后一行的灯是否全部亮，（前面4行已经全部亮了）。如果全亮，则当前的选择为一个可选方案，这时更新翻转的次数。

复杂度为O(n * 2^5)。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;

char m[10][10];
int ans = INF;
int dx[5] = {0,-1,0,1,0};
int dy[5] = {0,0,1,0,-1};
void flip(int x,int y){
    for(int i = 0; i <5; i++){
        int xi = x + dx[i];
        int yi = y + dy[i];
        if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5){
            m[xi][yi] ^= 1;
        }
    }
}

void solve(){
    char backup[10][10];
    int res = 0;
    memcpy(backup,m,sizeof(m));
    for(int i = 0; i < 1 << 5; i++){
        res = 0;
        for(int j = 0; j < 5; j++){
            if(i >> j & 1){
                res++;
                flip(0,j);
            }
        }
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 5; k++){
                if(m[j][k] == '0'){
                    flip(j+1,k);
                    res++;
                }
            }
        }
        bool flag = true;
        for(int j = 0; j < 5; j++){
            if(m[4][j] == '0'){
                flag = false;
                break;
            }
        }
        if(flag) ans = min(ans,res);
        memcpy(m,backup,sizeof(backup));    
    }

}

int main(){
    // freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    getchar();
    while(T--){
        ans = INF;
        for(int i = 0; i < 5; i++){
            scanf("%s",m[i]);
            // printf("%s\\n",m[i]);
        }
        solve();
        if(ans > 6) ans = -1;
        printf("%d\\n",ans);
    }

    return 0;
}
阅读更多
POJ-1062-昂贵的聘礼

POJ-1062

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。

为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的”优惠”Vi。如果两人地位等级差距超过了M，就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和”优惠价格”。

输出最少需要的金币数。

输入示例：

1
2
3
4
5
6
7
8
9
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

输出示例：

1
5250

题目大意：

一开始需要n金币，每个物品都有自己的价值，你可以用其他物品来抵消一部分金币（优惠价格），而用来抵消的物品也可以由其他物品来抵消该物品的一部分，如此往复。并且主人是分等级的，要确保交换物品过程中任何两个人的等级差距都不能超过M。
问最少需要的金币数量。

思路：

把每个物品看成结点，B物品可以抵消A物品的一部分,表示A有一条边指向B,边权是替代品的优惠价格，点权为该物品的价值。

可以求第一个物品到其他物品的最短路，松弛操作为：

1
dis[v] > dis[u] + u到v的边权

这样求得的dis为每个顶点到起点的优惠价格，而到当前点的总花费为：

1
dis[i] + coin[i] //优惠价格+当前物品的价格

而题目还有一层约束条件为物品交换不能超过等级差距。
我们就需要检查每个点到起点的等级差了。
例如起点的等级为5，等级差距为3，则要枚举的区间为 3 ~ 5、4 ~ 6、5 ~ 7 ，在每个区间中，求符合等级差距的点，并求起点到该点的最短路（这里比较绕，建议多思考下）。最后答案取一个最小值即可。

Solution：

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to,cost;
    Edge(){};
    Edge(int _to,int _cost){
        to = _to;
        cost = _cost;
    };
};

struct qnode{
    int v,cost;
    qnode(int _v, int _cost){
        v = _v;
        cost = _cost;
    }
    qnode(){}
    bool operator <(const qnode &b)const{
        return cost > b.cost;
    }
};
vector<Edge> G[MAXN];

int coin[MAXN]; //价值多少金币 
int dis[MAXN];	//最少优惠 
int vis[MAXN];	
int pos[MAXN];  //等级 
int M,N;
int ans;
 void Dijkstra(int S,int N){
 	for(int i = 1; i <= N; i++){
 		dis[i] = S== i ? 0 : INF;
	 }
     priority_queue<qnode> pq;
     pq.push(qnode(S,dis[S]));
     qnode temp;
     while(pq.size()){
         temp = pq.top();pq.pop();
         int u = temp.v;
         if(vis[u])continue;
         vis[u] = 1;
         for(int i = 0; i < G[u].size(); i++){
             int v = G[u][i].to;
             int vc = G[u][i].cost;
             if(!vis[v] && dis[v] > dis[u] + vc){
                dis[v] = dis[u] + vc;	
                //更新答案 
                ans = min(ans,dis[v] + coin[v]);
                pq.push(qnode(v,dis[v]));
             }
         }
     }
//     for(int i = 1; i <= N; i++){
//     	ans = min(ans,dis[i] + coin[i]);		
//	 } 
 }

void init(int N){
	for(int i = 0; i <= N; i++){
		G[i].clear();
	}
} 

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d %d",&M,&N);
    init(N);
    for(int i = 1; i <= N; i++){
        int c,r,n;
        scanf("%d%d%d",&c,&r,&n);
        coin[i] = c;
        pos[i] = r;

        for(int j = 1; j <= n; j++){
            int t,cost;
            scanf("%d%d",&t,&cost);
            G[i].push_back(Edge(t,cost));
        }
    }
    //设最大值为起始值 
    ans = coin[1];
    for(int i = 0; i <= M; i++){
    	//更新每个点是否在当前区间内 
    	for(int j = 1; j <= N; j++){
    		if(pos[j] >= pos[1]-M+i && pos[j] <= pos[1]+i) vis[j] = 0;
    		else vis[j] = 1;
		}
		//求一下当前区间的最短路。 
		Dijkstra(1,N);
	}
    printf("%d",ans);
    return 0;
}
阅读更多
POJ-2965-Th-Pilot-Brothers-refrigerator

POJ-2965

题目大意：

有一个4X4的冰箱阵列，当你改变一个冰箱门的状态（开或关），同行同列的冰箱门也会发生改变，给定一个序列，问从全部的冰箱门打开（“-”为开、“+”为关）到给定序列需要几步，以及具体的打开方式。

输入示例：
1
2
3
4
-+--
----
----
-+--
输出示例：
1
2
3
4
5
6
7
6
1 1
1 3
1 4
4 1
4 3
4 4

Solution1（枚举）:

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

int m[4][4];
int dx[16],dy[16],ans[16][2];
int ansn = 40;
bool isComplete(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(m[i][j] == 1) return false;
        }
    }
    return true;
}

void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        m[k][j] = !m[k][j];
        m[i][k] = !m[i][k];
    }
    //m[i][j]被翻转了两次，再翻转抵消一次。
    m[i][j] = !m[i][j];
}

//d:翻转的次数，s:要翻转的序号
void dfs(int d, int s){
    if(isComplete()){
        ansn = min(ansn,d);
        for(int i = 0; i < ansn; i++){
            ans[i][0] = dx[i];
            ans[i][1] = dy[i];
        }
    }
    if(s >= 16) return;
    dfs(d,s+1);
    flip(s/4,s%4);
    dx[d] = s/4;
    dy[d] = s%4;
    dfs(d+1,s+1);
    flip(s/4,s%4);
    dx[d] = 0;
    dy[d] = 0;
}
int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            m[i][j] = c == '+' ? 1 : 0;
        }
        getchar();
    }
    dfs(0,0);
    printf("%d\\n",ansn);
    for(int i = 0; i < ansn; i++){
        printf("%d %d\\n",ans[i][0]+1,ans[i][1]+1);
    }
    return 0;
}

思路：

直接枚举所有的状态，每个冰箱门都有转换和不转换两种状态，一共有16个冰箱门，所以有2的16次方种状态。
在所有的序列中取一个步数最小的即可。

Solution2（位运算压缩）：

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

int dx[16],ans[16];
int ansn = 40;
int state;


void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        state = state ^ (1<< (i*4+k));
        state = state ^ (1 << (k*4+j));
    }
    state = state ^ (1 << (i*4+j));
}

//d:翻转的次数，s:要翻转的序号
void dfs(int d, int s){
    if(!state){
        //更新结果
        ansn = min(ansn,d);
        for(int i = 0; i < ansn; i++){
            ans[i] = dx[i];
        }
    }
    if(s >= 16) return;
    dfs(d,s+1);
    //翻转
    flip(s/4,s%4);
    //保留翻转的位置
    dx[d] = 1 << s;
    dfs(d+1,s+1);
    //回溯
    flip(s/4,s%4);
    dx[d] = 0;
}
int Pos(int a){
    int ans = 0;
    while(a){
        ans++;
        a >>= 1;
    }
    return ans;
}
int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            // m[i][j] = c == '+' ? 1 : 0;
            if(c == '+')
                state = state | (1 << (i*4+j));
        }
        getchar();
    }
    dfs(0,0);
    printf("%d\\n",ansn);
    for(int i = 0; i < ansn; i++){
        int a  = Pos(ans[i])-1;
        printf("%d %d\\n",a/4+1,a%4+1);
    }
    return 0;
}

思路：

在上一题解的基础上，我们发现没有必要用二维数组来存储状态，可以使用一个16位的整数来存储，第几位二进制位表示第几个冰箱的状态。

记录改变冰箱的位置也同样可以使用一个16位的整数来存储。1表示该冰箱门改变了状态，所有的改变不会超过16个，使用16个整数就可以表示全部的移动的过程。

然后更新结果，并提取出来每一位即可。

Solution3（找规律）：

通过找规律我们发现：

  • 一个冰箱门状态改变两次等于不变。

  • 在上一条的基础上，如果以某一冰箱门为基准，将该冰箱门所在的行列上所有的冰箱门都翻转一次，该冰箱门改变，其他冰箱门都不变。

所以我们只要从结果反向推，将每个关闭的冰箱门所在的行列的冰箱门都翻转，更新每个冰箱门的改变的次数，结果状态就为当所有的关闭的冰箱门都被打开后的状态。当次数为奇数说明我们需要改变，偶数则忽略。最后遍历一遍结果数组，取出次数为奇数的冰箱门的坐标即可。

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

int record[16][16];

void flip(int i, int j){
    for(int k = 0; k < 4; k++){
        record[i][k]++;
        record[k][j]++;
    }
    record[i][j]--;
}


int main(){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            char c;
            scanf("%c",&c);
            if(c == '+') flip(i,j);
        }
        getchar();
    }
    
    int cnt = 0;
    for(int i = 0; i <4; i++){
        for(int j = 0; j < 4; j++){
            if(record[i][j]&1) cnt++;
        }
    }
    printf("%d\\n",cnt);
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(record[i][j]&1){
                printf("%d %d\\n",i+1,j+1);
            }
        }
    }
    return 0;
}
阅读更多
LeetCode-785-判断二分图

785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:

1
2
3
4
5
6
7
8
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2

我们不能将节点分割成两个独立的子集。

注意:

  • graph 的长度范围为 [1, 100]。

  • graph[i] 中的元素的范围为 [0, graph.length - 1]。

  • graph[i] 不会包含 i 或者有重复的值。

  • 图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

一个裸二分图染色题。

Solution1（DFS）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int vis[graph.size()] = {false};
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i].size(); j++){
                if(vis[graph[i][j]] == 0 && !dfs(graph,vis,graph[i][j],1)) return false;
            }
        }
        return true;
    }
    bool dfs(vector<vector<int>>& G,int vis[],int j, int c){
        vis[j] = c;
        for(int i = 0; i < G[j].size(); i++){
            if(vis[G[j][i]] == c) return false;
            if(vis[G[j][i]] == 0 && !dfs(G,vis,G[j][i],-c)) return false;
        }
        return true;
    }
};

思路：

二分染色题。
重点在dfs函数的编写，到达当前结点，先染色，再判断与之相连的结点的颜色是否被染过，如果没有染过，则染与当前结点不同的颜色，如果染过色且与当前结点颜色相同则表示不符合要求，颜色不同则可以直接忽略。

Solution2（BFS）:

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
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int vis[graph.size()] = {0};
        queue<int> q;
        int curr = -1;
        while(1){
            if(q.size() == 0){
                int k;
                for(k = 0; k < graph.size(); k++){
                    if(vis[k] == 0){
                        q.push(k);
                        break;
                    }
                }
                if(k == graph.size()) break;
            }
            curr *= -1;
            int len = q.size();
            for(int j = 0; j < len; j++){
                int f = q.front(); q.pop();
                vis[f] = curr;
                for(int i = 0; i < graph[f].size(); i++){
                    if(vis[graph[f][i]] == curr) return false;
                    if(vis[graph[f][i]] == 0){
                        q.push(graph[f][i]);
                    }
                }
            }
        }
        return true;
    }
};

思路：

与DFS思路相同，只不过改写为BFS版。

注意：给定的图有可能为多棵树组成的森林。所以每个树都要考虑到。

阅读更多
LeetCode-207-课程表

207. 课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]

输出: true

解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]

输出: false

解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

Solution1（DFS）:

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(numCourses <= 0) return true;
        vector<int> G[numCourses];
        int vis[numCourses] = {0};
        for(int i = 0; i < numCourses; i++) G[i].clear();
        for(int i = 0; i < prerequisites.size(); i++){
            G[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        for(int i = 0; i < numCourses; i++){
            if(!vis[i]){
                if(!dfs(G,vis,i)) return false;
            }
        }
        return true;
    }
    bool dfs(vector<int> G[], int vis[],int j){
        vis[j] = 2;
        for(int i = 0; i < G[j].size(); i++){
            if(vis[G[j][i]] == 2) return false;
            if(!vis[G[j][i]]){
                if(!dfs(G,vis,G[j][i])) return false;
            }
            
        }
        vis[j] = 1;
        return true;
    }
   
};
思路:

把该题看做判断一个有向图是否有环的问题。
进而可以看做一个染色问题：

  • 如果该节点没有被访问过，则是白色（用0表示）。

  • 如果该节点正在访问，但是没有访问结束，则是灰色（用2表示）。

  • 如果该节点已经访问，则是黑色（用1表示）。

只有在DFS中维护颜色数组（我这里为vis数组）即可。

Solution2（拓扑排序）：

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int inDegree[numCourses] = {0};
        vector<int> G[numCourses];
        for(int i = 0; i < prerequisites.size(); i++){
            G[prerequisites[i][1]].push_back(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        queue<int> q;
        int inqnum = 0;
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        while(q.size()){
            inqnum++;
            int f = q.front();q.pop();
            for(int i = 0; i < G[f].size(); i++){
                inDegree[G[f][i]]--;
                if(inDegree[G[f][i]] == 0){
                    q.push(G[f][i]);
                }
            }
        }
        return inqnum == numCourses;
    }
};
思路：

利用拓扑排序，每次将节点入度为零所在的边删去并更新边的另一端节点的入度信息，如果在多轮“删边”之后还有结点，说明有环。

阅读更多
首页 归档 标签 关于 搜索