${\color{purple}{\href{https://www.acwing.com/blog/content/26305/}{「算法主页」}}}$

3.4万

Libert
taozhiming
shengshu_
alan69359

lsz_

M_137
XZ916

14124
Serendipity_04

Firefly2000
fwyize

straySheep.

04辽宁大丑

6小时前

# 前置知识

## 复数

### 运算

$\ \ \ \ \ \ \ \ \ \ \$代数意义：$(a+bi)(c+di) = (ac-bd)+(ad+bc)i$

### 共轭复数

$|Z|=|Z’|\ \ \ \ \ \ \ \ Z\cdot Z’ = a^2+b^2$

### 复数除法

$z_1=a_1+b_1i,z_2=a_2+b_2i$

$$\frac{z_1z_2’}{a_2^2 + b_2^2}$$

## 单位根 $\omega$

$\omega_n^k$ 表示为将圆分成 $n$ 份，从 $x$ 正半轴逆时针取 $k$ 份下的复数。

• $\omega_n^k = \omega _{n}^{k-1} \cdot \omega _n^1$

• $\omega_n^0 = \omega_n^n=1$

• $\omega_{2n}^{2k} = \omega_n^k$

• $\omega_n^{k+\frac{n}{2}} = - \omega_n^k$

# 快速傅里叶变换

$$A(x) = \sum_{i=0}^{n-1} a_i * x^i$$

$$A_1(x) = a_0 + a_2 \cdot x + a_4 \cdot x^2 + \cdots + a_{n-2} x^{\frac{n}{2}-1}$$

$$A_2(x) = a_1 + a_3 \cdot x + a_5 \cdot x^2 + \cdots + a_{n-1} x^{\frac{n}{2}-1}$$

$$A(x) = A_1(x^2) + xA_2(x^2)$$

$$A(\omega_n^k) = A_1(\omega_{\frac{n}{2}}^{k}) + \omega_n^k A_2(\omega_{\frac{n}{2}}^{k})$$

$$A(\omega_n^{\frac{n}{2}+k}) = A_1(\omega_{\frac{n}{2}}^{k}) - \omega_n^k A_2(\omega_{\frac{n}{2}}^{k})$$

# 快速傅里叶逆变换

$C(x)$ 经过 $n$ 个点，$(b_0, y_0) \dots (b_{n - 1}, y_{n - 1})$

### 引理1

$$S(x) = 1 + x + x^2 + \cdots + x^{n-1}$$

$$S(\omega_n^k) = \omega_n^0 + \omega_n^k + \omega_n^{2k} + \cdots + \omega_n^{(n-1)k}$$

$$\omega_n^k S(\omega_n^k) = \omega_n^k + \omega_n^{2k} + \cdots + \omega_n^{(n-1)k} + \omega_n^{nk}$$

#### 若 $k\not= 0$

$$S(\omega_n^k) = \frac{0}{1 - \omega_n^k} = 0$$

#### 若 $k=0$

$$S(\omega_n^k) = n$$

### 引理2

$$nc_k = \sum_{i=0}^{n-1} y_i (w_n^{-k})^i$$

#### 证明

$$\sum_{i=0}^{n-1} y_i (w_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(w_n^i)}^{j}) (w_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(w_n^j)}^{i}) (w_n^{-k})^i$$

$$=\sum_{i=0}^{n-1} (\sum_{j=0}^{n-1} c_j {(w_n^{j - k})}^{i})$$

$$=\sum_{j=0}^{n-1} c_j \sum_{i=0}^{n-1} (w_n^{j-k})^{i}$$

$$=\sum_{j=0}^{n-1} c_j S(w_n^{j-k})$$

$$=nc_k$$

$$D(x) = \sum_{i=0}^{n-1} y_i x^i$$

$$c_k = \frac{D(w_n^{-k})}{n}$$

# $实现$

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

const int N = 400010;
const double PI = acos(-1);
int n, m, tot;
int rev[N];

struct Complex
{
double x, y;
Complex operator+ (const Complex& t) const
{
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const
{
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const
{
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
} a[N], b[N];

void fft(Complex a[], int inv)
{
for (int i = 0; i < tot; i ++ )
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int mid = 1; mid < tot; mid <<= 1)
{
Complex w1 = {cos(PI / mid), inv * sin(PI / mid)};
for (int i = 0; i < tot; i += mid * 2)
{
Complex wk = {1, 0};
for (int j = 0; j < mid; j ++ , wk = wk * w1)
{
Complex x = a[i + j], y = wk * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i ++ ) scanf("%lf", &a[i].x);
for (int i = 0; i <= m; i ++ ) scanf("%lf", &b[i].x);

int bit = 0;
while ((1 << bit) <= n + m) bit ++ ;
tot = 1 << bit;

for (int i = 0; i < tot; i ++ )
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (bit - 1));

fft(a, 1), fft(b, 1);
for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];

fft(a, -1);
for (int i = 0; i <= n + m; i ++ )
printf("%d ", (int)(a[i].x / tot + 0.5));
return 0;
}


$\Huge 单调栈$

## $过程$

• 若栈顶元素 $a_{top} \leq a_i$ 则在之后的答案中不可能出现 $a_{top}$ ，将栈顶元素弹出。
• 反复执行步骤1 ，最后栈中元素单调递减。
• 答案一定为栈中某个元素， $a_{top}$ 为第一个大于 $a_i$ 的数，第一个大于它的数是 $a_{top}$ 。
• 加入元素 $a_i$ 。

## $实现$

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

const int N = 100010;
int n;
int w[N], q[N];

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

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

w[0] = -1;
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && w[q[tt]] >= w[i])tt -- ;
printf("%d ", w[q[tt]]);
q[++ tt] = i;
}

return 0;
}


$\Huge 单调队列$

## $过程$

• 若 $i - hh + 1\ge k$ ，则弹出队头元素。
• 若 $a_{tt} \leq a_i$ ，则在之后的询问中不可能出现 $a_{tt}$ ，弹出队尾元素（循环此步骤多次）。
• 加入元素 $a_i$ ，队列保持单调递减。
• $hh$ 位置上的元素在队列中最大，以 $i$ 结尾的最大值为 $a_{hh}$

## $实现$

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

const int N = 1e6 + 10;
int a[N], q[N];

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

int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
{
if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
while (hh <= tt && a[q[tt]] > a[i]) tt -- ;
q[ ++ tt] = i;
if(i >= k) printf("%d ", a[q[hh]]);
}
puts("");

hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
{
if (hh <= tt && i - q[hh] + 1 > k) hh ++ ;
while (hh <= tt && a[q[tt]] < a[i]) tt -- ;
q[ ++ tt] = i;
if (i - k >= 0) printf("%d ", a[q[hh]]);
}

return 0;
}


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

int a[10];

bool check(int x)
{
memset(a, 0, sizeof a);
while (x)
{
a[x % 10] ++ ;
if (a[x % 10] > 1) return false;
x /= 10;
}
return true;
}

int main()
{
int a;
scanf("%d", &a);
for (int i = a + 1; ; i ++ )
{
if (check(i))
{
printf("%d", i);
return 0;
}
}
}


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

const int N = 30;
int n, m, tot;
int L[N], C[N];
bool st[N][N];

void dfs(int x, int y)
{
if (st[x][y]) return;
tot ++ , st[x][y] = true;
if (L[x] && y > 1) dfs(x, y - 1);
if (!L[x] && y < m) dfs(x, y + 1);
if (C[y] && x > 1) dfs(x - 1, y);
if (!C[y] && x < n) dfs(x + 1, y);
}

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

for (int i = 1; i <= n; i ++ )
{
char c;
cin >> c;
if (c == '<') L[i] = 1;
}

for (int i = 1; i <= m; i ++ )
{
char c;
cin >> c;
if (c == '^') C[i] = 1;
}

bool flag = true;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
memset(st, 0, sizeof st);
tot = 0;
dfs(i, j);
if (tot != n * m) flag = false;
}

puts(flag ? "YES" : "NO");

return 0;
}


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

const int N = 110;
int a[N], f[N][3];

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

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

memset(f, 0x3f, sizeof f);

f[0][2] = 0;
for (int i = 1; i <= n; i ++ )
{
if (a[i - 1] == 2 || a[i - 1] == 3)
{
f[i][1] = min(f[i][1], f[i - 1][0]);
f[i][2] = min(f[i][2], f[i - 1][0] + 1);
}
if (a[i - 1] == 1 || a[i - 1] == 3)
{
f[i][0] = min(f[i][0], f[i - 1][1]);
f[i][2] = min(f[i][2], f[i - 1][1] + 1);
}
f[i][0] = min(f[i][0], f[i - 1][2]);
f[i][1] = min(f[i][1], f[i - 1][2]);
f[i][2] = min(f[i][2], f[i - 1][2] + 1);
}

int res = f[n][2];
if (a[n] == 1) res = min(res, f[n][1]);
if (a[n] == 2) res = min(res, f[n][0]);
if (a[n] == 3) res = min(res, min(f[n][0], f[n][1]));

printf("%d", res);

return 0;
}


## $\large \color{RGB(240, 120 , 40)}{列表}$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 2010, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
int n;
int cnt;

PII check(int x, int y)
{
int res = 0;
for(int u = 0; u < 4; ++ u)
{
int ux = x + dx[u], uy = y + dy[u];
if(st[ux][uy])
res ++;
}
if(res == 3)
{
for(int u = 0; u < 4; ++ u)
{
int ux = x + dx[u], uy = y + dy[u];
if(!st[ux][uy])
return {ux, uy};
}
}
return {INF, INF};
}

void dfs(int x, int y)
{
PII ck = check(x, y);
if(ck.x != INF)
{
cnt ++;
st[ck.x][ck.y] = true;
dfs(ck.x, ck.y);
}
for(int u = 0; u < 4; ++ u)
{
int ux = x + dx[u], uy = y + dy[u];
if(st[ux][uy])
{
PII r = check(ux, uy);
if(r.x != INF)
{
st[r.x][r.y] = true;
cnt ++;
dfs(r.x, r.y);
}
}
}
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
{
int x, y;
scanf("%d%d", &x, &y);
x += 500, y += 500;
if(st[x][y]) cnt --;
else
{
st[x][y] = true;
dfs(x, y);
}
printf("%d\n", cnt);
}

return 0;
}


code

## B

x, y 一定被 $gcd(x,y)$ 整除。

x + y 也一定整除 $gcd(x,y)$ 。

code

## D

• 对于第 i 位，减去 $2^i ，ans加上 2^i$
• 若减去后位数增加或不变，则该位原来为0，现在为1，预计位数加1，ans加上$2^i$
• 若现位数等于预计位数，则说明位前面没有1，返回ans
• 否则说明前面有1，回到步骤1

code

General announcement
----------

Unfortunately, the round will be unranted. We apologize, we made a mistake in problem C and it cannot be solved within the given constraints.

## $A$

$$ans = n - \lfloor \frac{cnt}{2} \rfloor$$

code

code

## $C$

$$1, 2, 3, … , n$$

1. 若序列已按最终顺序排好，则返回 $0$
2. 否则则最后一次一定使用了序列最小值和序列最大值。
3. 去掉最小值和最大值 ，回到步骤一。

code

code