Chaosliang

Chaosliang
17小时前

## 注意：

### 2.unordered_map不太会用

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

char g[2][4];

unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;

string move0(string state)
{
string t = state;
for(int i = 0; i < 4; ++ i)
t[i] = state[i+4];
for(int i = 4; i < 8; ++ i)
t[i] = state[i-4];
return t;
}

string move1(string state)
{
string t = state;
for(int i = 1; i < 4; ++ i)
{
t[i] = state[i-1];
t[i + 4] = state[i-1 + 4];
}
t[0] = state[3];
t[4] = state[7];
return t;
}

string move2(string state)
{
string t = state;
int tp = t[1];
t[1] = t[5];
t[5] = t[6];
t[6] = t[2];
t[2] = tp;
return t;
}

int bfs(string start, string end)
{
if(start == end)    return 0;
queue<string> q;
q.push(start);
dist[start] = 0;

while(!q.empty())
{
string t = q.front();
q.pop();
string m[3];
m[0] = move0(t);
m[1] = move1(t);
m[2] = move2(t);

for(int i = 0; i < 3; ++ i)
{
if(!dist.count(m[i]))
{
dist[m[i]] = dist[t] + 1;
pre[m[i]] = {'A'+i, t};
q.push(m[i]);
if(m[i] == end) return dist[end];
}
}
}
return -1;
}

int main()
{
// string t = "12348765";
// cout << move0(t) << endl;
// cout << move1(t) << endl;
// cout << move2(t) << endl;
// cout << t << endl;
string start, end;
for(int i = 0; i < 8; ++ i)
{
int x;
cin >> x;
end += char(x + '0');
}
// cout << end << endl;
swap(end[4], end[7]), swap(end[5], end[6]);
start = "12348765";
int step = bfs(start, end);
cout << step << endl;
string res;
while(end != start)
{
res += pre[end].first;
end = pre[end].second;
}
reverse(res.begin(), res.end());
if(step > 0)    cout << res << endl;
}


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1005, M = N*N;

char g[N][N];

int dist[N][N];
PII q[M];

int n, m;

int hh = 0, tt = -1;

int main()
{
memset(dist, -1, sizeof(dist));
cin >> n >> m;
for(int i = 0; i < n; ++ i)
cin >> g[i];
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
if(g[i][j] == '1')
{
dist[i][j] = 0;
q[++ tt] = {i, j};
}
}
while(hh <= tt)
{
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
PII t = q[hh ++];
for(int i = 0; i < 4; ++ i)
{
int qx = t.x + dx[i], qy = t.y + dy[i];
if(qx < 0 || qx > n-1 || qy < 0 || qy > m-1)    continue;
if(dist[qx][qy] != -1)  continue;
dist[qx][qy] = dist[t.x][t.y] + 1;
q[++ tt] = {qx, qy};
}
}
for(int i = 0; i < n; ++ i)
{
for(int j = 0; j < m; ++ j)
{
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}


# 注意

### 这题主要注意上界

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5+5; // v*2-2 <=> (v-1)*2

int n, k;
int dis[N];
int q[N];

int dfs()
{
memset(dis, -1, sizeof(dis));
int hh = 0, tt = -1;
dis[n] = 0;
q[++ tt] = n;
while(hh <= tt)
{
int t = q[hh++]; //注意++位置
if(t == k)  return dis[t];
if(dis[t+1] == -1 && t+1 < N)
{
dis[t+1] = dis[t] + 1;
q[++tt] = t+1;
}
if(dis[t-1] == -1 && t-1>0)
{
dis[t-1] = dis[t] + 1;
q[++tt] = t-1;
}
if(dis[t*2] == -1 && t*2 < N)
{
dis[t*2] = dis[t] + 1;
q[++tt] = t*2;
}
}
return -1;
}

int main()
{
cin >> n >> k;
cout << dfs() << endl;
}


# 注意

### 注意输入是先列后行

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 155, M = N*N;

int n, m;

char g[N][N];
int sx=-1, sy=-1;
PII q[M];
int dist[N][N];

int bfs()
{
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int hh = 0, tt = -1;
memset(dist, -1, sizeof(dist));
dist[sx][sy] = 0;
q[++ tt] = {sx, sy};
while(hh <= tt)
{
PII tp = q[hh ++];//注意++位置
for(int i = 0; i < 8; ++ i)
{
int a = tp.x + dx[i], b = tp.y + dy[i];
if(a < 0 || a > n-1 || b < 0 || b > m-1)    continue;
if(dist[a][b] != -1)    continue;
if(g[a][b] == '*')  continue;
if(g[a][b] == 'H')
{
return dist[a][b] = dist[tp.x][tp.y] + 1;
}
dist[a][b] = dist[tp.x][tp.y] + 1;
q[++ tt] = {a, b};
}
}
return -1;
}

int main()
{
cin >> m >> n; //注意
for(int i = 0; i < n; ++ i)
{
cin >> g[i];
for(int j = 0; j < m; ++ j)
if(g[i][j] == 'K')
{
sx = i, sy = j;
}
}
cout << bfs() << endl;
return 0;
}


# 注意

### 3. pre数组起到了st数组的作用

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

const int N = 1005, M = N*N;
typedef pair<int, int>  PII;

int n;

int g[N][N];
PII q[M];
PII pre[N][N];

void bfs(int sx, int sy)
{
memset(pre, -1, sizeof(pre));
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int hh = 0, tt = -1;
pre[sx][sy] = {0, 0}; //随便写
q[++ tt] = {sx, sy};
while(hh <= tt)
{
PII t = q[hh ++];
for(int i = 0; i < 4; ++ i)
{
int nx = t.x + dx[i], ny = t.y + dy[i];
if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1)    continue;
if(pre[nx][ny].x != -1)   continue;
if(g[nx][ny] == 1)  continue;
pre[nx][ny] = t;
q[++ tt] = {nx, ny};
}
}
}

int main()
{
cin >> n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
{
cin >> g[i][j];
}
bfs(n-1, n-1);
PII point(0, 0); //打印路线
while(true)
{
cout << point.x << " " << point.y << endl;
if(point.x == n-1 && point.y == n-1)   break;
point = pre[point.x][point.y];
}
return 0;
}


## 注意平原即是山顶，也是山谷

#include <iostream>
#include <cstdio>
#include <algorithm>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1005, M = N*N;
int n;

int g[N][N];
PII q[M];
bool st[N][N];
bool has_higher, has_lower;

void bfs(int sx, int sy)
{
int hh = 0, tt = -1;
st[sx][sy] = true;
q[++tt] = {sx, sy};

while(hh <= tt)
{
int qx = q[hh].x, qy = q[hh].y;
++ hh;
for(int i = qx-1; i <= qx+1; ++ i)
for(int j = qy-1; j <= qy+1; ++ j)
{
if(i < 0 || i > n-1 || j < 0 || j > n-1)    continue;
if(i == qx && j == qy)  continue;
if(g[i][j] != g[qx][qy])
{
if(g[i][j] > g[qx][qy]) has_higher = true;
else    has_lower = true;
continue;
}
if(!st[i][j])
{
st[i][j] = true;
q[++tt] = {i, j};
}
}
}
}

int main()
{
cin >> n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
{
cin >> g[i][j];
}
int num_high = 0, num_low = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
{

if(!st[i][j])
{
has_higher = false, has_lower = false;
bfs(i, j);
if(!has_higher)     ++ num_high;
if(!has_lower)      ++ num_low;
}
}
cout << num_high << " " << num_low << endl;
return 0;
}


## 知识点：BFS + 简单二进制

#include <iostream>
#include <algorithm>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N*N;

PII q[M];
int g[N][N];
bool st[N][N];
int n, m;

int bfs(int sx, int sy)
{
int hh = 0, tt = -1;
st[sx][sy] = true;
q[++ tt] = {sx, sy};
int area = 1;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

while(hh <= tt)
{
int qx = q[hh].x, qy = q[hh].y;
++ hh;
for(int i = 0; i < 4; ++ i)
{
if(g[qx][qy] >> i & 1)  continue;
int a = qx + dx[i], b = qy + dy[i];
if(a < 0 || a > n-1 || b < 0 || b > m-1)    continue;
if(st[a][b])    continue;
st[a][b] = true;
++ area;
q[++ tt] = {a, b};
}
}
return area;
}

int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
cin >> g[i][j];
}
int cnt = 0, area = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
if(!st[i][j])
{
area = max(area, bfs(i, j));
++ cnt;
}
}
cout << cnt << endl;
cout << area << endl;
return 0;
}


# 注意

## 判定map是否走过的st数组可以省略，直接把map的’W’改为’.’

#include <iostream>
#include <algorithm>
#include <cstdio>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1005, M = N*N;

int n, m;
char g[N][N];
PII q[M];

void bfs(int sx, int sy)
{
int hh = 0, tt = -1;
q[++tt] = {sx, sy};
g[sx][sy] = '.';
while(hh <= tt)//队列不空
{
int qx = q[hh].x, qy = q[hh].y;
++ hh;
for(int i = qx-1; i <= qx+1; ++ i)
for(int j = qy-1; j <= qy+1; ++ j)
{
if(qx == i && qy == j)    continue; //可省略
if(i < 0 || i > n-1 || j < 0 || j > m-1)    continue;
if(g[i][j] == '.')  continue;
q[++tt] = {i, j};
g[i][j] = '.';
}
}
}

int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++ i)
cin >> g[i];
int cnt = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
if(g[i][j] == 'W')
{
bfs(i, j);
++ cnt;
}
}
cout << cnt << endl;
return 0;
}


### 状态真的很难，f数组的初始化不会

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1505, M = 2*N, INF = 0x3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;

int n;

//f[i, j]三大状态
//j = 0: i节点没放守卫，被父节点的守卫看到
//j = 1: i节点放了守卫，被自己的守卫看到
//j = 2: i节点没放守卫，被子节点中至少有一个守卫看到（有很多子节点）
int f[N][3];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int father)
{
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == father) continue;
dfs(j ,u);
f[u][0] += min(f[j][1], f[j][2]);
f[u][1] += min(min(f[j][0], f[j][1]), f[j][2]);
}
f[u][2] = INF;//思考一下，初始化了所有的叶子结点
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == father) continue;
f[u][2] = min(f[u][2], f[j][1]+f[u][0]-min(f[j][1], f[j][2]));//理解很数学
}
}

int main()
{
//初始化1
memset(h, -1, sizeof(h));

//输入
cin >> n;
for(int i = 1; i <= n; ++ i)
{
int a, k, m;
cin >> a >> k >> m;
w[a] = k;
while(m --)
{
int b;
cin >> b;
}
}
//初始化2
int root = 1;//假定为根节点
for(int i = 1; i <= n; ++ i)
{
f[i][1] = w[i];
}

dfs(root, -1);//对于无向树可以随便一个点当做根节点
cout << min(f[root][1], f[root][2]) << endl;
return 0;
}


# 注意点：

### 4.st数组用来寻找根节点

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1505;

int h[N], e[N], ne[N], idx; //每条边只出现一次

{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

bool st[N]; //非根节点

int n;

int f[N][2];

void dfs(int u)
{
int sum0=0, sum1=0;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
sum0 += f[j][1];
sum1 += min(f[j][0], f[j][1]);//看到min记住初始化最大
}
f[u][0] = sum0;
f[u][1] = sum1 + 1;
}

int main()
{
while(scanf("%d", &n) != -1)//多组数据记得初始化
{
memset(h, -1, sizeof(h));
memset(st, 0, sizeof(st));
memset(f, 0x3f,sizeof(f)); //最大
idx = 0;
for(int i = 0; i < n; ++ i)
{
int a, num;
scanf("%d:(%d)", &a, &num);
while(num --)
{
int b;
cin >> b;