分类目录归档：搜索

洛谷 封锁阳光大学

发表评论

题号：1330
这个属于搜索中的染色问题，之前不会，以后要多多学习。

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
#include<iostream>
#include<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
    if (x == 1)return 2;
    else return 1;
}
int BFS(int i){
    int cnter1 = 0, cnter2 = 0;
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, 1));
    while (!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        if (point[cur.first] != 0){
            if (point[cur.first] != cur.second)return -1;
            continue;
        }
        point[cur.first] = cur.second;
        if (cur.second == 1)cnter1++;
        if (cur.second == 2)cnter2++;
        for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
            q.push(pair<int, int>((*iter), color(cur.second)));
        }
    }
    return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (point[i] == 0){
            int t=BFS(i);
            if (t == -1){
                cout << "Impossible";
                return 0;
            }
            else
                sum += t;
        }
    }
    cout << sum;
}

20180806：基本上自己做出来了！！哈哈！有个小细节忽略了：是每个互不联通子图分别找出最小值加起来，不是整图统计。

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<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
vector<int> edges[10005];
int color[10005];
inline int getOppoColor(int x) {
    if (x == 1)return 2;
    else return 1;
}
int BFS(int s) {
    int color1 = 0, color2 = 0;
    queue<int> q;
    color[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int node = q.front();
        if (color[node] == 1)color1++;
        else color2++;
        q.pop();
        for (int i = 0; i < edges[node].size(); i++) {
            if (color[edges[node][i]] == 0) {
                color[edges[node][i]] = getOppoColor(color[node]);
                q.push(edges[node][i]);
            }
            else if (color[edges[node][i]] == color[node]) {
                return 0;
            }
        }
    }
    return min(color1, color2);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && edges[i].size() != 0) {
            int cur = BFS(i);
            if (cur == 0) {
                cout << "Impossible";
                return 0;
            }
            cnter += cur;
        }
    }

    cout << cnter;
}

洛谷 八皇后

发表评论

题号1219

感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦！

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int cnt;//情况计数器
bool line[14],row[14],left_diagonal[26],right_diagonal[26];
//占用情况数组：行；列；左上-右下对角线；右上-左下对角线
int pos[14];
//记录每一行的棋子放在哪一列
inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上
    return x+y-1;
}
inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上
    return (n+1-x)+y-1;
}
void search(int level){//dfs搜索：行
    if(level==n+1){//递归基
        cnt++;
        if(cnt>3)return;
        for(int i=1;i<=n;i++){//输出结果
            cout<<pos[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){//遍历列
        if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求
            pos[level]=i;
            line[i]=true;row[i]=true;
            left_diagonal[calculate_left_dia(level,i)]=true;
            right_diagonal[calculate_right_dia(level,i)]=true;
            search(level+1);//继续深搜
            line[i]=false;row[i]=false;//回溯
            left_diagonal[calculate_left_dia(level,i)]=false;
            right_diagonal[calculate_right_dia(level,i)]=false;
        }
    }
}
int main(){
    cin>>n;
    search(1);
    cout<<cnt;
}

洛谷 滑雪（重要！）

发表评论

题号:P1434
这道题需要留着细细品味……
这道题也挺恶心，用尽各种优化方法……
需要写一下注释，省得我以后看不懂自己写的代码……

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int array[105][105];
int memory[105][105];
bool check[105][105];
struct s{
    int x,y,n;
    bool operator < (s& s2){
        return this->n>s2.n;
    }
}ss[11025];
int r,c;
int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down
int safe_array(int x,int y){
    if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y];
    else return -1;
}//保证数组不越界
int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的
    if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0;
    if(memory[x][y]!=-1)return memory[x][y];
    check[x][y]=true;
    int max_=-1;
    for(int i=1;i<=4;i++){
        int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]);
        if(t>max_)max_=t;
    }
    check[x][y]=false;
    return memory[x][y]=max_+1;
}
int main(){
    memset(memory,-1,sizeof(memory));
    cin>>r>>c;
    int ptr=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>array[i][j];
            ss[ptr].x=i;
            ss[ptr].y=j;
            ss[ptr].n=array[i][j];
            ptr++;
        }
    }
    int max_=-1;
    sort(ss,ss+ptr);//先排序，由坡高到坡低去进行dfs，这样坡低的在刚一开始就会因为记忆化搜索直接return
    for(int i=0;i<ptr;i++){
        int t=dfs(ss[i].x,ss[i].y,ss[i].n+1);
        if(t>max_)max_=t;//收集最长路径
    }
    cout<<max_;
}

20180730更新：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int r,c;
int arr[105][105];
int f[105][105];
struct node{
    int x,y;
    int v;
    bool operator < (const node& n2){
        return v<n2.v;
    }
}narr[10005];
int narrptr=0;
int main() {
    ios::sync_with_stdio(false);
    memset(arr,0x7f,sizeof(arr));
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>arr[i][j];
            narr[++narrptr].v=arr[i][j];
            narr[narrptr].x=i;
            narr[narrptr].y=j;
        }
    }
    sort(narr+1,narr+r*c+1);
    for(int i=1;i<=narrptr;i++){
        if(narr[i].v>arr[narr[i].x-1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x-1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x+1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x+1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y-1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y-1]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y+1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y+1]+1);
    }
    int mmax=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            mmax=max(mmax,f[i][j]);
        }
    }
    cout<<mmax+1;
}

洛谷 [USACO06FEB]数字三角形Backward Digit Su…

发表评论

题号：P1118

必须用杨辉三角/组合数的方法做，同时要剪枝……这样才能A。不用这个只能60，剩下的全部TLE。

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,sum;
bool check[13];
int current[13];
int current_temp[13];
int yanghui[13];
int calculate(int k){
    int sum=0;
    for(int i=0;i<k;i++){
        sum+=yanghui[i]*current[i];
    }
    return sum;
}
void search(int level){
    if(level==n&&calculate(n)==sum){
        for(int i=0;i<n;i++){
            cout<<current[i]<<" ";
        }
        exit(0);
    }
    for(int i=1;i<=n;i++){
        if(!check[i]){
            check[i]=true;
            current[level]=i;
            if(calculate(level)<sum)search(level+1);
            check[i]=false;
        }
    }
}
int main(){
    memset(check,false,sizeof(check));
    cin>>n>>sum;
    //calculate yanghui
    yanghui[0]=1;
    for(int i=1;i<n;i++){
        yanghui[i]=(n-i)*yanghui[i-1]/i;
    }
    //end calculate
    search(0);
}

20180730更新：都忘了杨辉三角了……

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
#include<iostream>
using namespace std;
int n,sum;
bool visited[15];
int ansarr[15];
int triangle[15][15];
void triangle_init(){
    for(int i=0;i<15;i++){
        triangle[i][0]=1;
        triangle[i][i]=1;  
    }
    for(int i=2;i<15;i++){
        for(int j=1;j<i;j++){
            triangle[i][j]=triangle[i-1][j]+triangle[i-1][j-1];
        }
    }
}
bool dfs(int pos,int s){
    if(pos==n+1)return s==sum;
    if(s>sum)return false;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        visited[i]=true;
        ansarr[pos]=i;
        if(dfs(pos+1,s+i*triangle[n-1][pos-1]))return true;
        visited[i]=false;
    }
    return false;
}
int main() {
    triangle_init();
    cin>>n>>sum;
    if(dfs(1,0))for(int i=1;i<=n;i++)cout<<ansarr[i]<<" ";
}

Openjudge Sudoku 题解

发表评论

2982:Sudoku

总时间限制:
2000ms
内存限制:
65536kB
描述
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
输入
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
输出
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
样例输入
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
样例输出
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
来源
Southeastern Europe 2005

继续阅读 →

洛谷 P1141 01迷宫 题解

发表评论

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式：

输入的第1行为两个正整数n，m。

下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。

接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式：

输出包括m行，对于每个询问输出相应答案。

输入输出样例

输入样例#1：

2 2

01

10

1 1

2 2

输出样例#1：

4

4

说明

所有格子互相可达。

对于20%的数据，n≤10；

对于40%的数据，n≤50；

对于50%的数据，m≤5；

对于60%的数据，n≤100，m≤100；

对于100%的数据，n≤1000，m≤100000。

继续阅读 →

数据结构 邓俊辉 PA#3 无线广播(Broadcast) 题解

发表评论

无线广播(Broadcast)

描述

某广播公司要在一个地区架设无线广播发射装置。该地区共有n个小镇，每个小镇都要安装一台发射机并播放各自的节目。

不过，该公司只获得了FM104.2和FM98.6两个波段的授权，而使用同一波段的发射机会互相干扰。已知每台发射机的信号覆盖范围是以它为圆心，20km为半径的圆形区域，因此，如果距离小于20km的两个小镇使用同样的波段，那么它们就会由于波段干扰而无法正常收听节目。现在给出这些距离小于20km的小镇列表，试判断该公司能否使得整个地区的居民正常听到广播节目。

输入

第一行为两个整数n，m，分别为小镇的个数以及接下来小于20km的小镇对的数目。 接下来的m行，每行2个整数，表示两个小镇的距离小于20km（编号从1开始）。

输出

如果能够满足要求，输出1，否则输出-1。

输入样例

4 3
1 2
1 3
2 4

输出样例

1

限制

1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

不需要考虑给定的20km小镇列表的空间特性，比如是否满足三角不等式，是否利用传递性可以推出更多的信息等等。

时间：2 sec

空间：256MB

提示

BFS

继续阅读 →

Openjudge Pots

发表评论

Pots

总时间限制:
1000ms
内存限制:
65536kB
描述
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

输入
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
输出
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
样例输入
3 5 4
样例输出
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

本来我是不会做的，看了这篇题解 http://blog.csdn.net/kindlucy/article/details/5827794 之后明白的……
继续阅读 →

Openjudge 迷宫问题

发表评论

迷宫问题

总时间限制:
1000ms
内存限制:
65536kB
描述
定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

继续阅读 →

Openjudge 鸣人和佐助

发表评论

鸣人和佐助

总时间限制: 1000ms 内存限制: 65536kB
描述
佐助被大蛇丸诱骗走了，鸣人在多少时间内能追上他呢？

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
输入
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10 后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。 输出 输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。 样例输入 样例输入1 4 4 1 #@## **## ###+ **** 样例输入2 4 4 2 #@## **## ###+ **** 样例输出 样例输出1 6 样例输出2 4 继续阅读 →