Aigrl

8431

1000减7是

chaser.

lchlchlch123
lyktes
shaoxuan

cdm

acwing_9052

Aigrl
8天前

Aigrl
9天前

Aigrl
15天前

Aigrl
15天前

# 第二章 DFS 题目的状态空间与转换

## $2.1$ DFS 在地图类问题的转换

### * DFS 维护连通块

int dfs(int x, int y)
{
int cnt = 1;

st[x][y] = true;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];

if (a < 0 || a >= h || b < 0 || b >= w) continue;

if (g[a][b] != '.') continue;
if (st[a][b]) continue;

cnt +=  dfs(a, b);  // 相加
}

return cnt;
}


### * DFS 有约束的跑图问题

0. 向左转移

LL Left(int x, int y)
{
int a, b;
LL ans = -INF;
a = x - 1;
b = y;
if (check(a, b) && !st[a][b])
{
LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 2) + g[x][y]);
ans = max(ans, res);
}
return ans;
}


1. 向上转移

LL Up(int x, int y)
{
int a, b;
LL ans = -INF;
a = x;
b = y - 1;
if (check(a, b) && !st[a][b])
{
LL res = max(max(dfs(a, b, 0) + g[x][y], dfs(a, b, 2) + g[x][y]), dfs(a, b, 1) + g[x][y]);
ans = max(ans, res);
}
return ans;
}


2. 向右转移

LL Right(int x, int y)
{
int a, b;
LL ans = -INF;
a = x + 1;
b = y;
if (check(a, b) && !st[a][b])
{
LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 0) + g[x][y]);
ans = max(ans, res);
}
return ans;
}


inline bool check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
inline LL dfs(int x, int y, int k)
{
LL &ans = f[x][y][k];
if (ans != -INF)
{
return ans;
}

st[x][y] = true;

if (k == 0) ans = max(ans, Right(x, y));
if (k == 1) ans = max(ans, Up(x, y));
if (k == 2) ans = max(ans, Left(x, y));

st[x][y] = false;
return ans;
}


### * DFS 解决棋盘类问题

Aigrl
15天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 100010;

int n, m;
int S, T, K;
int f[N], h[N], e[M], ne[M], w[M], idx;

int dist[N], cnt[N];
bool st[N];

struct Ver
{
int x, dist;
bool operator < (const Ver &t) const
{
return dist > t.dist;
}
};

struct Aver
{
int x, dist, Af;
bool operator < (const Aver &t) const
{
return Af > t.Af;
}
};

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void fadd(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = f[a], f[a] = idx ++;
}

void init(int Start)    // 反向边预处理
{
memset(dist, 0x3f, sizeof dist);
priority_queue<Ver> heap;
heap.push({Start, dist[Start]});
dist[Start] = 0;

while (heap.size())
{
Ver t = heap.top();
heap.pop();

int ver = t.x;

if (st[ver]) continue;
st[ver] = true;

for (int i = f[ver]; i != -1; i = ne[i])
{
int j = e[i];

if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({j, dist[j]});
}
}
}
}

int Astar(int start)    // A*版 Dijkstra
{
priority_queue<Aver> heap;
heap.push({start, 0, dist[start]}); // 点的编号, 到源点的距离, 全程估计距离 = 实际距离 + 估价距离

while (heap.size())
{
Aver t = heap.top();
heap.pop();

int ver = t.x;
cnt[ver] ++;    // 经过次数 ++
if (cnt[T] == K) return t.dist; // 此时经过 K 次终点, 直接返回到源点的距离

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
/*
如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,
说明从j出发找不到第k短路(让终点出队k次)，
即继续让j入队的话依然无解，
那么就没必要让j继续入队了
*/
if (cnt[j] < K) // 出队次数小于 K
{
heap.push({j, t.dist + w[i], t.dist + w[i] + dist[j]});
}
}
}
return -1;
}

int main()
{
memset(h, -1, sizeof h);
memset(f, -1, sizeof f);

scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int a, b, L;
scanf("%d %d %d", &a, &b, &L);
}

scanf("%d %d %d", &S, &T, &K);
if (S == T) K ++;   // 源点等于汇点

init(T);
int ans = Astar(S);
printf("%d", ans);

return 0;
}


Aigrl
21天前

### 数据范围

$1≤T≤50$,
$1≤N≤10^5$

### 输入样例：

2
3
1 8 2
4
10 7 6 14


### 输出样例：

8
24


### 算法1

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N];
int ans;

int dfs(int u)
{
if (u <= 0) return 0;
if (f[u] != 0) return f[u]; // 计搜灵魂

return f[u] = max(dfs(u - 1), dfs(u - 2) + a[u]);
}

int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

printf("%d\n",dfs(n));
}
return 0;
}


### 算法2

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N][2];

int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++ )
{
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + a[i];
}
printf("%d\n", max(f[n][0], f[n][1]));
}
return 0;
}


### 算法3

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N];

int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

f[1] = a[1];
for (int i = 2; i <= n; i ++ )
{
f[i] = max(f[i - 1], f[i - 2] + a[i]);
}
printf("%d\n",f[n]);
}
return 0;
}


### 算法4

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N][2];

int dfs(int u, int state)
{
if (u <= 0) return 0;
if (f[u][state]) return f[u][state];

if (!state) return f[u][0] = max(dfs(u - 1, 0), dfs(u - 1, 1));
else return f[u][1] = dfs(u - 1, 0) + a[u];
}

int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

memset(f, 0, sizeof f);
int x = dfs(n, 0);
memset(f, 0, sizeof f);
int y = dfs(n, 1);

printf("%d\n", max(x, y));
}
return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[2][2];

void solve()
{
memset(f, -0x3f, sizeof f);
f[0][0] = 0;

cin >> n;
for (int i = 1; i <= n; ++ i) cin >> w[i];
for (int i = 1; i <= n; ++ i)
{
f[i & 1][0] = max(f[(i - 1) & 1][1], f[(i - 1) & 1][0]);
f[i & 1][1] = f[(i - 1) & 1][0] + w[i];
}
cout << max(f[n & 1][0], f[n & 1][1]) << endl;
}
int main()
{
int T = 1;
cin >> T;
while (T -- ) solve();
return 0;
}



Aigrl
22天前

### 算法1

#### C++ 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200010;

int n, m;

int p[N];
int a, b;
int c;

vector<int> mp[4];
unordered_map<int, bool> pth;

signed main()
{
cin >> n;

for (int i = 0; i < n; i ++ )
{
cin >>p[i];
pth[p[i]] = true;
}

for (int i = 0; i < n; i ++ )
{
cin >> a;
mp[a].push_back(p[i]);
}
for (int i = 0; i < n; i ++ )
{
cin >> b;
mp[b].push_back(p[i]);
}

for (int i = 1; i <= 3; i ++ )
{
sort(mp[i].begin(), mp[i].end());
reverse(mp[i].begin(), mp[i].end());
}

cin >> m;
for (int i = 0; i < m; i ++ )
{
cin >> c;
while (mp[c].size() && pth[mp[c].back()] == false) mp[c].pop_back();
if (mp[c].size())
{
printf("%lld ", mp[c].back());
pth[mp[c].back()] = false;
mp[c].pop_back();
}
else printf("-1 ");
}

}


Aigrl
22天前

【第一周】

1个多小时就调完了qwq

【第二周】

Aigrl
22天前
#include <bits/stdc++.h>
using namespace std;

const int N = 260000, INF = 1e9;

typedef pair<int, int> PII;

int n;
char str[N];
map<char, PII> mp;

struct Edge
{
int x, y;
int num;
}R[N];

int S, E, ans = INF;
char st;

bool C1(Edge a, Edge b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
bool C2(Edge a, Edge b) {return a.y < b.y || (a.y == b.y && a.x < b.x);}

bool check(int d, int l, int r)
{
if (d == ans && S == l) return E < r;
return d == ans ? S > l : d < ans;
}

void work1()
{
int f, l;
for (int i = 1; i < n; i ++ )
{
if (R[i].x == R[i + 1].x)
{
int dist = R[i + 1].y - R[i].y;
int a = R[i].num, b = R[i + 1].num;
char std = a > b ? 'S' : 'N';
if (a > b) swap(a, b);
f = a, l = b;

if (f + 1 == l) continue;
if (check(dist, f, l)) {ans = dist, S = f, E = l; st = std;}
}
}
}

void work2()
{
int f, l;
for (int i = 1; i < n; i ++ )
{
if (R[i].y == R[i + 1].y)
{
int dist = R[i + 1].x - R[i].x;
int a = R[i].num, b = R[i + 1].num;
char std = a > b ? 'W' : 'E';
if (a > b) swap(a, b);

f = a, l = b;

if (f + 1 == l) continue;
if (check(dist, f, l)) {ans = dist, S = f, E = l; st = std;}
}
}
}

int main()
{
scanf("%d\n%s", &n, str + 1);

mp['N'] = {0, 1}, mp['S'] = {0, -1}, mp['W'] = {-1, 0}, mp['E'] = {1, 0};
for (int i = 1; i <= n; i ++ )
{
R[i] = R[i - 1], R[i].num = i;
R[i].x += mp[str[i]].first;
R[i].y += mp[str[i]].second;
}
sort(R + 1, R + n + 1, C1); work1();
sort(R + 1, R + n + 1, C2); work2();

printf("%d %d %d %c", ans, S, E, st);
return 0;
}


Aigrl
22天前

# 第一章 引言

## $1.1$ DFS 的定义

### * DFS 的基层实现原理

$DFS$ 即 深度优先搜索，在程序中是以 栈的形式 实现，符合 的先进先出的原理，当栈不为空时，就会一直弹出栈顶元素

### * DFS 的实现场景

$DFS$ 是一种用递归实现的算法，但本质上完全可以借助栈来解决。

### * DFS 的实现方式

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
if 问题边界                 // 必备的, 只有有限的空间才可以搜索
{
维护答案;
return;
}

往不同方向搜索延伸          // 搜索分支
{
dfs(参数发生不同的变化);   // 往下搜索
}
}


### * 回溯法的原理

"从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。"


1. 【组合问题】：N个数里面按一定规则找出k个数的集合

2. 【排列问题】：N个数按一定规则全排列，有几种排列方式

3. 【切割问题】：一个字符串按一定规则有几种切割方式

4. 【子集问题】：一个N个数的集合里有多少符合条件的子集

5. 【棋盘问题】：N皇后，解数独等等

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
if 问题边界                 // 必备的, 只有有限的空间才可以搜索
{
维护答案;
return;
}

往不同方向搜索延伸          // 搜索分支
{
处理此节点信息
dfs(参数发生不同的变化);    // 往下搜索
复原此节点信息, 才可以进行对分支的正确搜索。    // 回溯
}
}


## $1.2$ DFS 的可传递信息

### *DFS 自底向上的信息维护

$【sum$ 值的维护】 ：

【树的最小字典序维护】 ：

【树的重心】 ：

## $1.3$ DFS 的铺垫知识

### *变换步骤（递归）

1. 【自身调用自身】

2. 【回溯时还原现场（搜索失败）】

3. 【扩展（搜索成功）】

### *DFS 的三种枚举方式

【指数型枚举】 ：

void dfs(int u){
if (u == n + 1)
{
for (int i = 0; i < ch.size(); i ++ )
printf("%d ", ch[i]);
puts("");
return;
}

dfs(u + 1);
ch.push_back(u);

dfs(u + 1);
ch.pop_back();
}


【组合型枚举】 ：

void dfs(int u){
if (ch.size() > m || ch.size() + (n - u + 1) < m) return;
if (u == n + 1)
{
for (int i = 0; i < ch.size(); i ++ )
printf("%d ", ch[i]);
puts("");
return;
}

dfs(u + 1);
ch.push_back(u);

dfs(u + 1);
ch.pop_back();
}


【排列型枚举】 ：

int st[N];//存储方案
bool used[N];//标记数字是否被用过，true表示被用过，false表示没被用过
int n;

void dfs(int u) {   //当前枚举第u位
if (u > n) {
for (int i = 1; i <= n; i ++ )
printf("%d ", st[i]);   //打印方案
puts("");
return ;
}

for (int i = 1; i <= n; i ++ ) {    //依次枚举每个数
if (!used[i]) {                 //当前数可用
st[u] = i;
used[i] = true;
dfs(u + 1);

//恢复现场
st[u] = 0;      //可省略
used[i] = false;//不可省
}
}
}

int main() {
scanf("%d", &n);

dfs(1);

return 0;
}


## $1.4$ 记忆化搜索初步

### 3、记忆化搜索的核心实现

$a.$ 首先，要通过一个表 记录已经存储下的搜索结果，一般用 哈希表 实现

$b.$ 状态表示，由于是要用 哈希表 实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个 $p$ 进制数字，然后把这个数字对应的十进制数字作为状态

$c.$ 在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯

$d.$ 如果没有，则按正常方法搜索