日常训练17-10-14

题目链接：here

Emptying the Baltic

题意：问给定位置的抽水机需要排多少水（水从高往低流）。

类似最短路～

 1 /*************************************************************************
 2     > File Name: temp.cpp
 3     > Author: yijiull 
 4     > Mail: 1147161372@qq.com 
 5     > Created Time: 2017年10月15日 星期日 09时56分36秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include <bits/stdc++.h>
10 
11 using namespace std;
12 const int maxn = 510;
13 int p[maxn][maxn], vis[maxn][maxn];
14 long long ans;
15 
16 struct Node{
17     int x, y;
18     int dep;
19     Node(int x,  int y, int dep): x(x), y(y), dep(dep){}
20     bool operator < (const Node &a)const {
21         return dep > a.dep;
22     }
23 };
24 int n, m;
25 int sx, sy;
26 
27 int d[8][2]={0, 1, 0, -1, 1, 0, 1, 1, 1, -1, -1, 0, -1, 1, -1, -1};
28 
29 int ck(int x, int y){
30     return x>=0&&x<n && y>=0&&y<m && !vis[x][y] && p[x][y] < 0;
31 }
32 
33 void bfs(){
34     priority_queue<Node> q;
35     memset(vis, 0, sizeof(vis));
36     ans = -p[sx][sy];
37     q.push(Node(sx, sy, p[sx][sy]));
38     vis[sx][sy] = 1;
39     while(!q.empty()){
40         Node now = q.top();
41         q.pop();
42         int x = now.x, y = now.y, dep = now.dep;
43         for(int i = 0; i < 8; i++){
44             int dx = x + d[i][0];
45             int dy = y + d[i][1];
46             if(ck(dx, dy)){
47                 vis[dx][dy] = 1;
48                 ans -= max(dep, p[dx][dy]);
49                 q.push(Node(dx, dy, max(p[dx][dy], dep)));
50             }
51         }
52     }
53 }
54 
55 int main(){
56     scanf("%d %d", &n, &m);
57     for(int i = 0; i < n; i++){
58         for(int j = 0; j < m; j++){
59             scanf("%d", &p[i][j]);
60         }
61     }
62     scanf("%d %d", &sx, &sy);
63     sx--; sy--;
64     bfs();
65     printf("%lld
", ans);
66 }

View Code

Distinctive Character

Kattis - distinctivecharacter

题意：给ｎ个长度为ｋ的０１串，　让求一个长度为ｋ的０１串，使得该串和给出的ｎ个串相似度最大值最小．

转换成不相似度最小值最大（？）　　－－　　异或？

然后ｂｆｓ～

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1<<21;
 4 const int inf = 0x3f3f3f3f;
 5 int d[maxn];
 6 int n, k;
 7 char s[25];
 8 int main(){
 9     queue<int> q;
10     memset(d, inf, sizeof(d));
11     scanf("%d %d", &n, &k);
12     for(int i = 0; i < n; i++){
13         scanf("%s", s);
14         int x = 0;
15         for(int j = 0; j < k; j++){
16             x |= (s[j]-'0')<<(k-1-j);
17         }
18         q.push(x);
19         d[x] = 0;
20     }
21     int ans = -inf;
22     int id;
23     while(!q.empty()){
24         int u = q.front();
25         q.pop();
26         for(int i = 0; i < k; i++){
27             int v = u^(1<<i);
28             if(d[v] != inf) continue;
29             d[v] = d[u] + 1;
30             q.push(v);
31             if(d[v] > ans) {
32                 ans = d[v];
33                 id = v;
34             }
35         }
36     
37     }
38     int cnt = k-1;
39     for(int i = 0; i < k; i++){
40         s[cnt--] = (id&1) + '0';
41         id>>=1;
42     }
43     puts(s);
44 }

View Code