头像

清风qwq

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




离线:5小时前


最近来访(1192)
用户头像
Libert
用户头像
taozhiming
用户头像
shengshu_
用户头像
alan69359
用户头像
还有898天
用户头像
续写
用户头像
lsz_
用户头像
肥仔_7
用户头像
M_137
用户头像
XZ916
用户头像
织葉
用户头像
14124
用户头像
Serendipity_04
用户头像
君の名は_43
用户头像
Firefly2000
用户头像
fwyize
用户头像
北海没有WA
用户头像
straySheep.
用户头像
自宅警备员
用户头像
04辽宁大丑


清风qwq
6小时前

前言

宣传: 算法主页

更好的阅读体验


前置知识

多项式

一个多项式表示为 $A(x) = a_0 + a_1 x + a_2 x^2 + … a_n x^n$

系数表示法: $A(x) = \sum _{i=0}^{n} a_i x^i$

点值表示法:用 $n$ 个不同的点 $(x, A(x))$ 唯一表示多项式 $A(x)$

复数

前置知识:向量、三角函数

定义

设 $i^2 = -1$ ,则一个复数表示为 $a + bi (a,b\in R)$

其中 $bi$ 为虚部, $a$ 为实部

复平面上,从 $(0,0)$ 到 $(a,b)$ 的向量表示 $a+bi$

棱长: $|Z| = \sqrt{a^2+b^2}$

幅角:为从 $x$ 正半轴逆时针旋转的角度

运算

加法: $(a+bi)+(c+di) = (a+c)+(b+d)i$

乘法: 几何意义:复数相乘,模长相乘,幅角相加

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

共轭复数

复数 $Z = a+bi$ 的共轭复数$Z’$为 $a-bi$

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

复数除法

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

设 $z_0=\frac{z_1}{z_2}$

上下同乘 $z_2$ 的共轭复数 $z_2’$

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

单位根 $\omega $

为在复平面上以原点为圆心作半径为 $1$ 的圆。

$\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$


算法流程

1101696-20180211213536607-322408834.png


快速傅里叶变换

快速傅里叶变换($\texttt{Fast Fourier Transform , FFT}$)

使用 $\omega_n^k (0\leq k < n)$ 这 $n$ 个不同的数来当作点值表示法中的 $n$ 个 $x$

已知

$$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)$$

将 $\omega_n^k (0\leq k < n)$ 代入 $A(x)$ 中

$$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})$$

两个式子 $A_1()$ ,$A_2()$ 相同。

当计算 $[0,\frac{n}{2})$ 时,$[\frac{n}{2},n)$ 可以直接计算。

每次计算量减小一半,时间复杂度 $O(n\log n)$

快速傅里叶逆变换

快速傅里叶逆变换 $(\texttt{Inverse Fast Fourier Transform , IFFT})$

设 $C(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_{n - 1} x^{n-1}$

设 $b_i = \omega_n^i, y_i = C(b_i)$

$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 单调栈$

$问题描述$

给定长度为 $n$ 的序列 $a$ 。

对于每一个 $a_i$ ,求在它前面第一个大于它的数。

$过程$

从左往右扫描序列 $a$ ,对于每一个 $a_i$ :

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

时间复杂度为 $O(n)$

$实现$

#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 单调队列$

$题目描述$

有一个长为 $n$ 的序列 $a$,以及一个大小为 $k$ 的窗口。

现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

$过程$

以最大值为例。

队列开头为 $hh$ ,结尾为 $tt$ ,对于每一个 $a_i$ :

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

时间复杂度 $O(n)$

$实现$

#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(100, 020 ,220)}{前言}$

本贴记录了打过的 $codeforces$ 比赛题解。

通常打 $div.2$ 和 $edu$, 偶尔打 $div.3$ 和 $div.1 + div.2$。

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

  1. Codeforces Round #842 (Div. 2)
  2. Educational Codeforces Round 141 (Rated for Div. 2)
  3. Codeforces Round #843 (Div. 2) A-D
  4. Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)
  5. Educational Codeforces Round 142(Rated for Div. 2) A~D
  6. Codeforces Round #846 (Div. 2)


活动打卡代码 AcWing 3367. 舒适的奶牛

#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;
}



A

code

B

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

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

所以尽量多加一定使答案更优。

题目要求 $k > 1$ ,

那么考虑所有将序列分成两半的方案,取最大值即可。

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$

设 $cnt$ 为 1 的个数

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

code

$B$

先用 a , 再同时用 b 和 c , 再用剩余的 b 或 c , 最后用 d 。

code

$C$

最后结果为

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

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

code

$D$

逆向思考,序列 $q$ 对那些序列 $p$ 有贡献。

具体看代码。

code