gym101572补题

组队赛补题

水坑问题

从起始点出发进行BFS,不断的维护最深的水坑。
问最多能流多少的水

AC code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
int n, m, x, y;
int a[505][505];
int vis[505][505],h[505][505];
int dir[8][2] = { {1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1} };
struct node
{
int x, y, h;
bool operator<(const node &a)const
{
return h > a.h;
}
}pre, nt;
int main()
{
while (~scanf("%d%d", &n, &m))
{
priority_queue<node>q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
scanf("%d%d", &x, &y);
memset(vis, 0, sizeof vis);
pre = { x,y,a[x][y] };
q.push(pre);
vis[x][y] = 1;
h[x][y] = a[x][y];
while (!q.empty())
{
pre = q.top();
q.pop();
for (int i = 0; i < 8; i++)
{
int xx = pre.x + dir[i][0];
int yy = pre.y + dir[i][1];
if (xx<1 || yy<1 || xx>n || yy>m|| a[xx][yy] >= 0||vis[xx][yy]) continue;
int tmp = max(pre.h, a[xx][yy]);
h[xx][yy] = tmp;
vis[xx][yy] = 1;
nt = { xx,yy,tmp };
q.push(nt);
}
}
LL ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout<<h[i][j]<<" ";
}
cout<<endl;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += -1LL * h[i][j];
printf("%lld\n", ans);
}
return 0;
}
/*
3 3
1 1 1
1 -1 1
1 1 1
*/

水坑问题2

问题博客
可以看到相似的处理方法,但是一开始维护的高度为最外面的高低

01串的相似度的最大值最小

题解博客
先所有的串压入队列,求最远的串的距离就行了

ac code

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
#include <bits/stdc++.h>
using namespace std;
char a[25];
int dist[(1<<20)+10];
queue<int>que;
int main()
{
memset(dist,-1,sizeof(dist));
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%s",a);
int now=0;
for(int j=0;j<k;j++)
if(a[j]=='1')
now|=(1<<j);
que.push(now);
dist[now]=0;
}
int ans,ma=0;
while(!que.empty())
{
int K=que.front();
que.pop();
for(int i=0;i<k;i++)
{
int to=K^(1<<i);
if(dist[to]!=-1)continue;
dist[to]=dist[K]+1;
que.push(to);
if(ma>dist[to]) continue;
{
ma=dist[to];
ans=to;
}
}
}
for(int i=0;i<k;i++)
printf("%d",ans%2),ans/=2;
printf("\n");
}

ICPC排名计算

维护序号为1前面的序列就行了,注意set怎么访问struct

ac code

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
#include <bits/stdc++.h>
using namespace std;
struct Node{
int u;
int number;
int fa;
Node(int _u=0, int _number = 0, int _fa = 0):u(_u), number(_number), fa(_fa){}
Node(){}
bool operator < (const Node & a) const {
if(number != a.number) return number>a.number;
else return fa < a.fa;
}
};
int main(){
Node node1 = Node(1, 2, 100);
Node node2 = Node(2, 2, 101);
Node node3 = Node(3, 1, 90);
set<Node> s;
s.clear();
s.insert(node1);
s.insert(node2);
s.insert(node3);
for(set<Node>::iterator it = s.begin(); it!=s.end(); it++){
cout<<(it)->u<<" "<<(it)->number<<" "<<(it)->fa<<endl;
}
return 0;
}

未解决的问题

文章目录
  1. 1. 水坑问题
    1. 1.1. AC code
  2. 2. 水坑问题2
  3. 3. 01串的相似度的最大值最小
    1. 3.1. ac code
  4. 4. ICPC排名计算
    1. 4.1. ac code
  5. 5. 未解决的问题
{{ live2d() }}