4987

Jun不见

im0use
LLYY

AcWing2AK

ythyth

exzang_6
solo起来

yxc

6小时前

### 线段树

#include <iostream>

using namespace std;
const int N = 1e5 + 10, INF = 2147483648;
int n, m;
int w[N];
struct node
{
int l, r;
int maxx;
}tr[N * 4];

void pushup(int u)
{
tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}

void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxx;
int mid = tr[u].l + tr[u].r >> 1;
int maxx = -INF;
if (l <= mid) maxx = max(maxx, query(u << 1, l, r));
if (r > mid) maxx = max(maxx, query(u << 1 | 1, l, r));
return maxx;
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);

build(1, 1, n);

while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(1, l, r));
}
return 0;
}


7小时前

#### 线段树

#include <iostream>

using namespace std;
int n, m;
const int N = 1e5 + 10;
int w[N];
struct node
{
int l, r;
int sum;
}tr[N * 4];

void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}

void modify(int u, int x, int v)
{
if (tr[u].l == tr[u].r) tr[u].sum += v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);

build(1, 1, n);
while (m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (!k) printf("%d\n", query(1, x, y));
else modify(1, x, y);
}
return 0;
}


22小时前

### 树状数组 ### 线段树 ### ST表

P3374 【模板】树状数组 1 https://www.luogu.com.cn/problem/P3374
P3368 【模板】树状数组 2 https://www.luogu.com.cn/problem/P3368
1267 清点人数 https://www.acwing.com/problem/content/1269/
1265 数星星 https://www.acwing.com/problem/content/1267/
P1816 忠诚 https://www.luogu.com.cn/problem/P1816
P2880 [USACO07JAN] Balanced Lineup G https://www.luogu.com.cn/problem/P2880
P3865 【模板】ST 表 https://www.luogu.com.cn/problem/P3865
464.数数 http://oj.daimayuan.top/problem/464

### KMP

#### next数组找最小循环节

M - Power Strings https://vjudge.net/contest/502186#problem/M

#### next数组找所有公共前后缀

K - Seek the Name, Seek the Fame https://vjudge.net/contest/502186#problem/K

### 单调栈 单调队列

23小时前
#include <iostream>
#include <set>
using namespace std;

const int N = 15010, M = 32010;
int tree[M];
int n;
int cnt[N];
int lowbit(int x)
{
return x & -x;
}

void add(int x, int k)
{
while (x <= M)
{
tree[x] += k;
x += lowbit(x);
}
}

int sum(int x)
{
int res = 0;
while (x)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d%d", &x, &y);
x ++; y ++;
cnt[sum(x)] ++;
}

for (int i = 0; i < n; i ++ ) printf("%d\n", cnt[i]);
return 0;
}



#include <iostream>
#include <queue>
#include <cstring>
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, pair<int, int>> PIII;
const int N = 1010, M = 20010;
int n, m, S, T, k;
int h[N], sh[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void Dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(d, 0x3f, sizeof d);
q.push({0, T}); d[T] = 0;
while (q.size())
{
auto t = q.top(); q.pop();
int val = t.sd;
if (st[val]) continue;
st[val] = true;
for (int i = sh[val]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] > d[val] + w[i])
{
d[j] = d[val] + w[i];
q.push({d[j], j});
}
}
}
}

int Astar()
{
if (d[S] == 0x3f3f3f3f) return -1;
priority_queue<PIII, vector<PIII>, greater<PIII>> q;
q.push({d[S], {0, S}});
int cnt = 0;
while (q.size())
{
auto t = q.top(); q.pop();
int val = t.sd.sd, dist = t.sd.ft;
if (val == T) cnt ++;
if (cnt == k) return dist;
for (int i = h[val]; i != -1; i = ne[i])
{
int j = e[i];
q.push({dist + w[i] + d[j], {dist + w[i], j}});
}
}
return -1;
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(sh, -1, sizeof sh);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b, c);
add(sh, b, a, c);
}

scanf("%d%d%d", &S, &T, &k);
if (S == T) k ++;

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


#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define ft first
#define sd second
using namespace std;

string s, en = "12345678x";
unordered_map<string, pair<string, char>> pre;
unordered_map<string, char> red;
unordered_map<string, int> d;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char op[4] = {'u', 'r', 'd', 'l'};
struct node
{
string s;
int w;
bool operator< (const node &t) const
{
return w > t.w;
}
};

int get_d(string str)
{
int res = 0;
for (int i = 0; i < 9; i ++ )
for (int j = 0; j < 9; j ++ )
if (str[i] == en[j] && str[i] != 'x')
{res += abs(i / 3 - j / 3) + abs(i % 3 - j % 3); break;}
return res;
}

void bfs()
{
priority_queue<node> q;
q.push({s, get_d(s)});
d[s] = 1;
while (q.size())
{
node t = q.top(); q.pop();
string str = t.s; int w = t.w;
// cout << str << ' ' << w << endl;
if (str == en) break;
for (int i = 0; i < 4; i ++ )
{
string cpy(str);
int j;
for (j = 0; j < 9; j ++ ) if (cpy[j] == 'x') break;
int x = j / 3 + dx[i], y = j % 3 + dy[i];
if (x < 0 || y < 0 || x >= 3 || y >= 3) continue;
swap(cpy[x * 3 + y], cpy[j]);

if (!d.count(cpy) || d[cpy] > d[str] + 1)
{
d[cpy] = d[str] + 1;
q.push({cpy, d[cpy] + get_d(cpy)});
pre[cpy] = {str, op[i]};
}
}
}

string res;
while (en != s)
{
res += pre[en].sd;
en = pre[en].ft;
}
reverse(res.begin(), res.end());
cout << res << endl;
}
int main()
{
char c;
while (cin >> c) s += c;
int x = 0;
for (int i = 0; i < 9; i ++ )
for (int j = i + 1; j < 9; j ++ )
if (s[i] != 'x' && s[j] != 'x' && s[i] > s[j])
x ++;
if (x & 1) cout << "unsolvable" << endl;
else bfs();
return 0;
}


#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
string a, b;
string s1[10];
string s2[10];
unordered_map<string, int> d1;
unordered_map<string, int> d2;
int cnt;
int bfs()
{
if (a == b) return 0;
queue<string> ft, en;
ft.push(a); d1[a] = 1;
en.push(b); d2[b] = 1;
while (ft.size() && en.size())
{
auto t1 = ft.front(); ft.pop();
auto t2 = en.front(); en.pop();
for (int i = 0; i < cnt; i ++ )
{
int lena = t1.size();
int lenb = t2.size();
int len1 = s1[i].size();
int len2 = s2[i].size();
//正向搜
for (int j = 0; j <= lena - len1; j ++ )
{
if (t1.substr(j, len1) == s1[i])
{
string str;
str += t1.substr(0, j);
str += s2[i];
str += t1.substr(j + len1, lena - len1 - j);

if (d1[str]) continue;
d1[str] = d1[t1] + 1, ft.push(str);
if (d2[str]) return d1[str] + d2[str] - 2;
}
}
//反向搜
for (int j = 0; j <= lenb - len2; j ++ )
{
if (t2.substr(j, len2) == s2[i])
{
string str;
str += t2.substr(0, j);
str += s1[i];
str += t2.substr(j + len2, lenb - len2 - j);

if (d2[str]) continue;
d2[str] = d2[t2] + 1, en.push(str);
if (d1[str]) return d1[str] + d2[str] - 2;
}
}
}
}
return 11;
}

int main()
{
cin >> a >> b;
while (cin >> s1[cnt] >> s2[cnt ++ ]); cnt --;
int res = bfs();
if (res <= 10) cout << res << endl;
else cout << "NO ANSWER!" << endl;
return 0;
}


#include <iostream>
#include <deque>
#include <cstring>
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
char g[N][N];
int d[N][N];
bool st[N][N];
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
char s[5] = "\\/\\/";
int n, m;
int bfs()
{
memset(d, 0x3f, sizeof d);
memset(st, false, sizeof st);
deque<PII> q;
q.push_back({0, 0});
d[0][0] = 0;
while (q.size())
{
auto t = q.front();
q.pop_front();
int x = t.ft, y = t.sd;
if (st[x][y]) continue;
st[x][y] = true;
// cout << x << ' ' << y << endl;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || b < 0 || a > n || b > m) continue;

int w = (g[x + ix[i]][y + iy[i]] != s[i]);
int dd = d[x][y] + w;
if (d[a][b] > dd)
{
d[a][b] = dd;
if (w) q.push_back({a, b});
else q.push_front({a, b});
}
if (a == n && b == m)
{
cout << x << ' ' << y << endl;
return d[a][b];
}

}
}
return -1;
}
int main()
{
int Q;
scanf("%d", &Q);
while (Q -- )
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%s", &g[i]);
if (n + m & 1) puts("NO SOLUTION");
else
{
printf("%d\n", bfs());
}
}
}


## bfs

### 2、flood_fill

P1162 填涂颜色 https://www.luogu.com.cn/problem/P1162

### 5、双端队列搜索

175.电路维修 https://www.acwing.com/problem/content/description/177/

### 6、BFS + 优先队列优化

P3956 [NOIP2017 普及组] 棋盘 https://www.luogu.com.cn/problem/P3956

### 7、双向BFS

190.字串变换 https://www.acwing.com/problem/content/192/
*不能每次扩展一个点交替搜索(每次扩展一层)

### 8、A*

/*
A* 应用场景:

A*算法:
while(q.size())
t ← 优先队列的队头  小根堆
当终点第一次出队时 break;
从起点到当前点的真实距离 d_real
从当前点到终点的估计距离 d_estimate
选择一个估计距离最小的点 min(d_estimate)
for j in ne[t]:
将邻边入队

A*算法条件:

d[state] + f[state] = 起点到state的真实距离 + state到终点的估计距离=估计距离
^
d[state] + g[state] = 起点到state的真实距离 + state到终点的真实距离=真实距离

f[u] >= 0

1 假设终点第一次出队列时不是最优
则说明当前队列中存在点u
有 d[估计]< d[真实]
d[u] + f[u] <= d[u] + g[u] = d[队头终点]
即队列中存在比d[终点]小的值,
2 但我们维护的是一个小根堆,没有比d[队头终点]小的d[u],矛盾

证毕

A* 不用判重

A o→o→o
↑   ↓
S o→o→o→o→o→o→o T
B
dist[A] = dist[S]+1 + f[A] = 7
dist[B] = dist[S]+1 + f[B] = 5

B走到T后再从A这条路走到T



## dfs

### 2、IDA*

DNA sequence https://vjudge.net/problem/HDU-1560#author=0

## 一、质数

1、试除法判定质数

2、分解质因数 O(logn ~ sqrt(n))

3、筛质数
1)朴素筛O(nlogn)
2)埃筛O(nlognlogn)
3）线性筛O(n)

Ⅰ、欧拉函数
Ⅱ、莫比乌斯函数

1、试除法求约数

2、870. 约数个数