# A

# 题目原文

Kostya has a text $s$ consisting of $n$ words made up of Latin alphabet letters. He also has two strips on which he must write the text. The first strip can hold $m$ characters, while the second can hold as many as needed.

Kostya must choose a number $x$ and write the first $x$ words from $s$ on the first strip, while all the remaining words are written on the second strip. To save space, the words are written without gaps, but each word must be entirely on one strip.

Since space on the second strip is very valuable, Kostya asks you to choose the maximum possible number $x$ such that all words $s_1, s_2, \dots, s_x$ fit on the first strip of length $m$ .

# 题目大意

给定 $n$ 个长度确定的字符串 $s_i$ ，要将其放置于两个磁带中，第一个磁带可以放置 $m$ 个字符，第二个磁带无限长。已知每两个字符串之间不需要空格，若一个字符串不可以被分割成两部分放入两个磁带中，请问第一个磁带最多可以放置几个字符串。（并且，字符串还得是按顺序放置）

# 题解

找前 $x$ 个字符串，使得 $x$ 最大的情况下， $\sum\limits_{i=1}^x s[i].size() \le m$

# 注意，不能这样写

int cnt = 0, i = 1;

    while (true) {
        m -= s[i].size();
        
        if (m < 0)
            break;

        cnt++, i++;
    }

会 $RE$ ，因为可能所有字符串都能放在第一个磁带中

# 正确写法

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> s[i];

    int cnt = 0, i = 1;

    for (int i = 1; i <= n; i++) {
        m -= s[i].size();

        if (m < 0)  break;
            
        cnt++;
    }
    
    cout << cnt << endl;
}

# B

# 题目大意

对于一个序列 $A=(a_1,a_2,...,a_n)$ ，你可以从 i = 2 $\to$ i = n - 1 中，任选一个 $i$ ，进行两种操作

a[i - 1] += 1, a[i + 1] -= 1
a[i - 1] -= 1, a[i + 1] += 1

问，是否可以经过若干次操作后，使得 $a_i = (\sum\limits_{j = 1}^n a_j) / n$

# 题解

很奇怪的是，题目内有一句是：After each operation, all the values must be non-negative. Can you make all the elements equal after any number of operations?
但是加上特判反倒 $WA$ 没有特判 $AC$ 了

int n, a[N], avg = 0;
void solve () {
    avg = 0;

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], avg += a[i];
    
    if (avg % n != 0) {
        cout << "NO" << endl;
        return;
    }

    avg /= n;

    for (int i = 2; i <= n - 1; i++) {
        a[i + 1] += a[i - 1] - avg, a[i - 1] = avg;

        // if (a[i + 1] < 0) {
        //     cout << "NO" << endl;
        //     return;
        // }
    }

    if (a[n - 1] != avg || a[n] != avg)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

# C

# 题目大意

给定一个长度不超过 $10^5$ 的字符串，你可以对任意一个数字进行平方并且替换（前提是平方后的数字还是一位数）
问：有没有可能，经过若干次操作后（可以为 $0$ ），操作后的数是 $9$ 的倍数？

# 错误解法

一开始看错了题，以为是数值不超过 $10^5$ ，想当然的用了搜索，然后光荣 $WA$

bool flag;

int len;
string s;

void dfs(int u, int num) {
    if (flag)
        return;

    if (u == len + 1) {
        flag = (num % 9 == 0);
        return;
    }

    int t = s[u] - '0';

    if (t <= 1)
        dfs(u + 1, num * 10 + t);
    else {
        while (t < 10) {
            dfs(u + 1, num * 10 + t);
            t *= t;
        }
    }
}

void solve () {
    flag = false;

    cin >> s;
    len = s.size(), s = " " + s;

    dfs(1, 0);

    cout << (flag ? "YES" : "NO") << endl;
}

# 正解

首先，能被 $9$ 整除的数有这样一个性质： 其各位数的和是 9 的倍数
再者，题目说的是进行平方替换操作（前提是平方后的数字还是一位数），只有 $1,2,3$ 可以进行这个操作，而 $1$ 平方后不会影响原数，只有 $2$ 和 $3$ 平方会改变和，所以只需考虑 $2$ 和 $3$ 分别改变 $i$ 和 $j$ 个即可

void solve () {
    cin >> s;

    int cnt2 = 0, cnt3 = 0, sum = 0;
    
    for (char x : s) {
        sum += x - '0';

        if (x == '2')
            cnt2++;
        if (x == '3')
            cnt3++;
    }

    for (int i = 0; i <= cnt2; i++)
        for (int j = 0; j <= cnt3; j++)
            if ((2 * i + 6 * j + sum) % 9 == 0) {
                cout << "YES" << endl;
                return;
            }

    cout << "NO" << endl;
}

# D

# 题目大意

给定一个字符串 $s$ （是一个数字），你可以进行一种操作：选择任意一个非 $0$ 的、不是最左边的数字的，使其减一并且与左边一个对调位置，你可以进行任意次操作。
问：可以构成的最大数字是多少？

一共有 $t~(1 \le t \le 10^4)$ 个数，每个数长度为 $1 \le len \le 2\cdot 10^5$

# 题解

大水题啊，暴力搜就好，用一个 maxN 存每一位的数，对于当前遍历到的 t = a[i] 不断往前找，只要 t - 1 > 前一个数 ，那么就继续往前，复杂度较可观，一个数最多往前 $8$ 次，复杂度是 $O(8 \cdot t \cdot len)$

void solve() {
    memset(maxN, 0, sizeof maxN);

    cin >> (a + 1), n = strlen(a + 1);

    for (int i = 1; i <= n; i++)    maxN[i] = a[i] - '0';

    for (int i = 2; i <= n; i++)
        if (maxN[i] > 1) {
            int t = maxN[i], j = i - 1;

            while (j >= 1 && t - 1 > maxN[j])
                maxN[j + 1] = maxN[j], maxN[j] = t - 1, t--, j--;
        }
    
    for (int i = 1; i <= n; i++)    cout << maxN[i];

    cout << endl;
}

# E

# 题目大意

给定三个字符串 $a,b,c$

假想一个字符串 $d$ ， $d$ 的是这样构成的，每次任从 $a~or~b$ 中选择一个字符串，将这个字符串的第一个字符挪到 $d$ 的末尾并从选中字符串中删除最前面的字符。

问：在若干种可能构成的 $d$ 字符串中，与 $c$ 字符串相比较，最小不同字符数是多少？

$t~(1 \le t \le 10^3)$ 组数据。
每组数据中， $a,b$ 字符串的长度都满足 $1 \le len \le 10^3$

# 题解

还是无法战胜噩梦 $dp$ 吗

设 $dp_{ij}$ 为字符串 $a$ 的前 $i$ 个字符和字符串 $b$ 的前 $j$ 个字符组成字符串 $c$ 的前 $i+j$ 个字符的最小替换次数

如果当前字符来源 $a$ $a$
- 如果当前字符是目标字符， dp[i][j] = dp[i - 1][j]
- 如果不是， dp[i][j] = dp[i - 1][j] + 1
如果当前字符来源 $b$ $b$
- 如果当前字符是目标字符， dp[i][j] = dp[i][j - 1]
- 如果不是， dp[i][j] = dp[i][j - 1] + 1
对于以上两种情况取 $min$ 即可

string a, b, c;
int dp[N][N];

void solve(){
    memset(dp, 0x3f, sizeof dp);

    cin >> a >> b >> c;
    int la = a.size(), lb = b.size(), lc = c.size();
    a = " " + a, b = " " + b, c = " " + c;

    dp[0][0] = 0;

    for (int i = 1; i <= la; i++)
        dp[i][0] = dp[i - 1][0] + (a[i] != c[i]);
    for (int i = 1; i <= lb; i++)
        dp[0][i] = dp[0][i - 1] + (b[i] != c[i]);
    
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
            dp[i][j] = min(dp[i - 1][j] + (a[i] != c[i + j]), dp[i][j - 1] + (b[j] != c[i + j]));

    cout << dp[la][lb] << endl;
}

# F

# 题意

给定一个 $n$ 个数的序列 $A(a_1,a_2,...,a_n)$ ，和 $q$ 个查询，每次查询给定一个范围 $l,r$

问，对于 $a_l \to a_r$ ，请你确定一个 $m$ ，使得对于 $\forall~i\in[l,r]$ 满足 $a_i~\%~m = k$ ， $k$ 是一个固定整数。如果当 $m \rightarrow +\infty$ 时，则输出 $0$

一共 $t,~(1 \le t \le 10^4)$ 组数据， $1 \le n,q \le 2 \cdot 10^5$ ， $1 \le l,r \le n$ ， $1 \le a_i \le 10^9$

# 题解

还是无法战胜噩梦数学题吗？

你需要知道：若 a > b，则 a 和 b 对 a - b 同余。

设 $p=a-b,~a=kp+q$
那么 $b=a-(a-b)=a-p=(k-1)p+q$
$a,b,p$ 模 $p$ 都是 $q$ ，即 $a,b$ 对 $a-b$ 同余（都是 $q$ ）

你还需要知道：若 a > b，则 a 和 b 对 a - b 的所有因数同余

设 $p=a-b,a=kp+q,b=(k-1)p+q$
设 $p$ 的因数为 $p_0$ ，因为 $kp$ 和 $(k-1)p$ 可以被 $p$ 整除，则这两个数都同余于 $p_0$
并且 $q$ 和 $q$ 同余于 $p_0$
所以 $a,b$ 的两部分都同余于 $p_0$
综上， $a,b$ 同余于 $p_0$

因此， $a_l$ 到 $a_r$ 同余可以拆分成：

限制	结论
$a_l,a_{l+1}同余$	$m$ 是 $\vert{a_l-a_{l+1}}\vert 的因数$
$a_{l+1},a_{l+2}同余$	$m$ 是 $\vert{a_{l+1}-a_{l+2}}\vert 的因数$
...	...
$a_{r-2},a_{r-1}同余$	$m$ 是 $\vert{a_{r-2}-a_{r-1}}\vert 的因数$
$a_{r-1},a_{r}同余$	$m$ 是 $\vert{a_{r-1}-a_{r}}\vert 的因数$

得出结论， $m = gcd(\vert{a_{l}-a_{l+1}}\vert,\vert{a_{l+1}-a_{l+2}}\vert,...,\vert{a_{r-2}-a_{r-1}}\vert,\vert{a_{r-1}-a_{r}}\vert)$ ，需要特判，区间长度为 $1$

# 暴力写法

暴力对每一个 $l,r$ 求解 __gcd ，显然时间复杂度爆了： $O(T\cdot Q\cdot N\cdot \log{a_i})$

void solve(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    while (q--) {
        cin >> l >> r;

        if (l == r)
            cout << "0 ";
        else {
            int g = abs(a[l] - a[l + 1]);

            for (int i = l + 1; i <= r - 1; i++)
                g = __gcd(g, abs(a[i] - a[i + 1]));

            cout << g << " ";
        }
    }
    
    cout << endl;
}

# 正解

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

// n：数组 a 的长度；
// q：查询次数；
// a：存储输入的数列；
// s：存储相邻元素差值的绝对值，即 s[i] = |a[i+1] - a[i]|；
int n, q, a[200005], s[200005];

// 变量 l, r 用于表示每次查询的左右区间；
// Log 数组用于预处理每个数字对应的二进制对数（下取整），用于稀疏表查询
int l, r, Log[200005];

// 定义一个结构体 ST_map，用于构造和维护稀疏表（Sparse Table）
struct ST_map {
    // Gcd[i][j] 表示从位置 i 开始、长度为 2^j 的区间内的最大公约数（GCD）
    int Gcd[200005][21];

    // 初始化稀疏表的函数
    void Init() {
        // 初始化第一列，区间长度为1的情况，即直接将 s 数组的值赋给 Gcd[i][0]
        for (int i = 1; i <= n - 1; i++)
            Gcd[i][0] = s[i];
        
        // 通过动态规划构造稀疏表，i 表示区间的 2^i 长度
        for (int i = 1; i <= 20; i++)
            // 对于每个起点 j (注意 j 的上界为 n-1，因为 s 数组只有 n-1 个元素)
            for (int j = 1; j <= n - 1; j++)
                // Gcd[j][i] = gcd(从 j 开始长度为 2^(i-1) 的区间的 GCD, 从 j+2^(i-1) 开始长度为 2^(i-1) 的区间的 GCD)
                // min(j + (1 << (i - 1)), n) 用于确保索引不会越界（取最大值不超过 n）
                Gcd[j][i] = __gcd(Gcd[j][i - 1], Gcd[min(j + (1 << (i - 1)), n)][i - 1]);
    }

    // 查询函数，查询差值数组 s 中区间 [l, r] 的最大公约数
    int Query(int l, int r) {
        // 根据区间长度 (r-l+1) 从预处理的 Log 数组中取得对应的对数值
        int logx = Log[r - l + 1];
        // 利用稀疏表进行区间查询：
        // 将区间 [l, r] 分成两个长度为 2^logx 的重叠区间，
        // 分别为 [l, l+2^logx-1] 和 [r-2^logx+1, r]，然后取两者的 GCD
        return __gcd(Gcd[l][logx], Gcd[r - (1 << logx) + 1][logx]);
    }
} ST;  // 定义一个全局的 ST_map 对象，名称为 ST

void Main() {
    scanf("%d%d", &n, &q);
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    // 计算相邻元素的差值的绝对值，存入数组 s 中
    for (int i = 1; i < n; i++)
        s[i] = abs(a[i + 1] - a[i]);

    // 初始化稀疏表，构造 Gcd[][] 数组
    ST.Init();

    while (q--) {
        scanf("%d%d", &l, &r);
        
        if (l == r) // 如果查询区间只有一个元素，则没有相邻差值，直接输出 0
            printf("0 ");
        else // 否则，通过稀疏表查询区间 [l, r-1] 内的最大公约数，并输出结果
            printf("%d ", ST.Query(l, r - 1));
    }
    
    puts("");
}

signed main() {
    int cnt = 0, last = 2; // 初始化 cnt 用于记录对数值，last 表示当前 2 的幂的临界值，初始值为 2
    
    // 预处理 Log 数组：对每个整数 i (2 <= i <= 200000)
    // 如果 i 达到了 2 的某个幂值，则 cnt 自增，并更新 last 为下一个 2 的幂值
    for (int i = 2; i <= 200000; i++) {
        if (i == last)
            cnt++, last *= 2;
        // 将当前 cnt 值存入 Log[i]，即 Log[i] = floor(log2(i))
        Log[i] = cnt;
    }

    int T;
    scanf("%d", &T);

    while (T--)
        Main();

    return 0;
}

DFS 模拟小学数学 DP Div3 RMQ问题 ST表

# A

# 题目原文

# 题目大意

# 题解

# 注意，不能这样写

# 正确写法

# B

# 题目大意

# 题解

# C

# 题目大意

# 错误解法

# 正解

# D

# 题目大意

# 题解

# E

# 题目大意

# 题解

# F

# 题意

# 题解

# 暴力写法

# 正解

运输问题

三角积分表