出题人认为的难度排序：A M F L C / E J K I / G H B D 实际上的通过人数排序：M A F L C / E G D K / H J I B

大体上没什么偏差，偏差比较大的D题可能是因为贵国数据结构太强了，DS经典套路都见过，反倒思维题实际通过更少一点。

A 智乃的博弈游戏

题意

两个人理论取石子，每次可以拿走与当前个数互质的个数，问先手是否有必胜策略。

题解

奇数-奇数=偶数

偶数-奇数=奇数

与偶数互质的数一定是奇数，最终胜利时，胜利状态是奇数。所以无论先手还是后手，轮到自己时如果当前的个数是奇数，最优策略都是只拿走个，而如果轮到自己时是偶数，则说明必败，任何策略都没用。

代码

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n&1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

时间复杂度

B 智乃的质数手串

题意

环形链表，可以删除某个位置加上它的后驱和为质数的节点，特别的，可以直接删除最后一个节点不用判断质数，问全部删除方案是否存在并输出方案。

题解

先不考虑它是一个首位相接的环，考虑在断开后如果是数组怎么做

因为每个数都只用考虑他后面的元素的值，所以从左往右删过去是无后效性的，即第一个元素无论是删还是不删，无论是现在立刻删除还是等等再删的时机，都不会影响第二个元素，因为第二个元素只能和它后面的元素相加删除。

有了这个理论就可以贪心了，形式化的：对于数组中（注意已经把环破开了）的位置，如果则在任何时候删除，都不影响的可删除性，即从左往右删除时，删除操作具有无后效性。

则需要对每一个，只要能找到它后面第一个可配对把它删除的，就立刻把它删掉，否则就等它后面的元素先删，发现这个逻辑和线性判断括号配对算法逻辑是一致的。

所以用一个堆栈模拟，当能弹出栈顶元素时，直接贪心的把它弹出去，最后如果堆栈只剩下一个元素就是合法的，例如一开始数组是2 4 1 2 4 1，堆栈是空的，然后首先输入2，堆栈变为[2]，然后输入4，发现2+4=6不是质数，无法弹出栈顶，所以压入，堆栈变成[2,4]，这个时候1来了，发现栈顶4+1=5是质数，所以4被弹出，然后先不要压入，发现弹出后新的栈顶2+1=3也是质数，继续弹出。这个时候堆栈为空，压入1，然后压入2弹出1，继续压入4，又变为[2,4]，然后压入1，弹出4,2，最后只剩1，说明可以取完。

考虑环形怎么做，显然不能枚举起点，不然是的

这里有个常见的环形处理小技巧，把数组复制一边前后拼接到一起，然后考虑一个长度大小为的滑动窗口从左往右滑过，这样虽然有的元素无法删除，但是一旦离开这个窗口就会失效，这个用法是一个单调队列经典应用，虽然本题不是单调队列，只是用法和代码相同，只需将堆栈变为队列即可。

时间复杂度

代码

#include <bits/stdc++.h>

using namespace std;

void prim_table(int n, vector<int> &table, vector<int> &prime)
{
    prime.clear();
    table.clear();
    table.resize(n + 1);
    table[0] = table[1] = 1;
    for (int i = 2; i < n; ++i)
    {
        if (!table[i])
        {
            prime.emplace_back(i);
        }
        for (auto &j: prime)
        {
            if (i * j > n)
            {
                break;
            }
            table[i * j] = 1;
            if (i % j == 0)
            {
                break;
            }
        }
    }
    for (auto &i: table)
    {
        i ^= 1;
    }
}

using namespace std;

const int MAXN = 200005;

int main()
{
    int n, tail, head, top, posbg;
    bool flag = false;
    auto a = vector<int>(MAXN, 0);
    auto q = vector<pair<int, int>>(MAXN);
    auto stk = vector<pair<int, int>>(MAXN);
    auto pos = vector<int>(MAXN, 0);
    vector<int> table, prim, ans;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
        a[n + i] = a[i];
    }

    prim_table(MAXN, table, prim);
    tail = 0, head = 0;
    for (int i = 0; i < 2 * n; ++i)
    {
        while (tail > head && table[q[tail].first + a[i]])
        {
            --tail;
        }
        while (tail > head && q[head + 1].second <= i - n)++head;
        q[++tail] = make_pair(a[i], i);
        if (i >= n && tail - head == 1)
        {
            flag = true;
            posbg = (i + 1) % n;
            break;
        }
    }

    if (flag)
    {
        printf("Yes\n");
        top = 0;
        for (int i = 0; i < n; ++i)
        {
            while (top > 0 && table[stk[top].first + a[i + posbg]])
            {
                ans.push_back(stk[top].second);
                --top;
            }
            stk[++top] = make_pair(a[i + posbg], i + posbg);
        }
        assert(top == 1);
        ans.push_back(stk[top].second);
        --top;
        for (int i = 0; i < ans.size(); ++i)
        {
            printf("%d%c", ans[i] % n, " \n"[i + 1 == ans.size()]);
        }
    } else
    {
        printf("No\n");
    }
    return 0;
}

C 智乃的Notepad(Easy version)

题意

给个字符串，构造一个字符串的顺序，最小化的值，其中lcp表示最长公共前缀。

题解

，注意到顺序不影响的值，只需要考虑如何令和最小化，这里有一步贪心，一般来讲因为也是的一种选择，两者并不独立，但是因为这里其实顺序相当自由，假定他们的贡献可以独立。

即，单独求出，然后直接输出。

所以答案=(全部字符串的长度和-排序后相邻字符串的lcp)*2-最长字符串长度。

排序就是std::sort，并不需要借助字典树之类的数据结构，代码很简短。

PS：字典树的复杂度不带，但是常数很大，跑的比sort慢

证明

这个证明不太好用文字表述，好在可以用字典树模拟，实际构造出这样的顺序一定存在，所以证明就是字典树的建树过程。

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
string a[MAXN];
int n, m;

int lcp(const string &A, const string &B)
{
    int i = 0;
    while (i < A.size() && i < B.size() && A[i] == B[i])++i;
    return i;
}

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    int mx = 0, sum = 0;
    for (int i = 0; i < n; ++i)
    {
        sum += (int) a[i].size() * 2;
        if (i)sum -= lcp(a[i], a[i - 1]) * 2;
        mx = max(mx, (int) a[i].size());
    }
    cout << sum - mx << endl;
    return 0;
}

D 智乃的Notepad(Hard version)

题意

给个字符串，每次查询之间的字符串，查询对区间[l,r]排序后的，输出

题解

问题：简化版的树上颜色段均摊，核心trick相同

问题：RMQ问题

问题是经典问题，重点讲一下问题，首先可以转化成字典树上边的数目或者节点数目-1

颜色段均摊问题，对[l,r]区间做某种memset操作，暴力维护增加或者删除信息，每次至多在区间边缘产生2条新的信息，则新增信息具有复杂度，删除信息具有均摊复杂度。具体来讲，例如：维护一种数据结构，支持1.将[l,r]区间染色成颜色x，2.查询[l,r]中不同颜色形成的连续段个数。

而树上颜色段均摊问题，是指将上述问题放到树上，区间[l,r]变成节点u到v的树上路径。 不妨先把这个问题放到字典树上面，在字段树中，对于两字符串，所在的

单词节点就是插入字典树时单词节点的，即。这个很好理解，因为在字典树上会合并两个字符串相同的前缀，直到它们产生分叉。那么的另一种数据结构的理解方式就是，将之间的字符串插入一个空的字典树，字典树边的的数目就是的值。

现在有了树，我们引入颜色，考虑这么一个问题，假设对于所有的查询离线分类，每次只处理相同的问题，给一个具体的例子，假设插入的字符串分别为，分别求区间的值。

按照步骤，依次插入，并且定义一个颜色数组[红,黄,蓝,绿]

首先插入，红色

然后插入，黄色，覆盖掉前面已经存在的颜色

然后插入，蓝色，覆盖掉前面已经存在的颜色

然后插入，绿色，覆盖掉前面已经存在的颜色

做完以后，我们统计一个新的数组，叫做颜色个数数组，即[红,黄,蓝,绿]色的节点个数分别是多少，得到

然后发现，查询区间的值就是红+黄+蓝+绿=1+2+2+2=7；

查询区间的值就是黄+蓝+绿=2+2+2=6；

查询区间的值就是蓝+绿=2+2=4；

查询区间的值就是绿=2。

问题转化成颜色个数的区间和，使用树状数组维护颜色的前缀和即可求出的值。

这就为什么说“简化版的树上颜色段均摊”（甚至最核心的均摊部分都没了，只是暴力维护树上数颜色）由于本题是字典树，这表示你可以暴力枚举所有需要推平的颜色段，无需引入其他数据结构。

时间复杂度

当然，如果不是字典树而是更朴素的树的情况下，需要快速找到并改变整个颜色段所在的树链。恰好的模板本身就具备这样的能力，无需再实现额外的代码，所以按照这个思路，只需要在合并分裂树链的时候，多记录一个额外信息表示当前颜色树链的长度，同步维护颜色个数数组，剩下的就和本题完全一致了。

PS：这里离线的RMQ问题直接用个单调栈处理就行，不用再贴一坨RMQ

PS2：莫队会TLE ，写的特别好的莫队可以卡过去，内测有人写了非删莫队偷了个log过去了

PS3：写个真的树上颜色段均摊不知道能不能过，因为完整算法常数还是比较大的，验题没人写这个。

代码

#include <bits/stdc++.h>

using namespace std;


class FenwickTree
{
public:
    FenwickTree(int n) : n(n), bit(n + 1, 0), vis(n + 1, 0)
    {}

    void add(int idx, int value)
    {
        while (idx <= n)
        {
            if (!vis[idx])
            {
                vis[idx] = 1;
                stk.push_back(idx);
            }
            bit[idx] += value;
            idx += idx & -idx;
        }
    }

    int query(int idx)
    {
        int sum = 0;
        while (idx > 0)
        {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    void clear()
    {
        while (!stk.empty())
        {
            int idx = stk.back();
            stk.pop_back();
            bit[idx] = 0;
            vis[idx] = 0;
        }
    }

private:
    int n;
    vector<int> bit;
    vector<int> vis;
    vector<int> stk;
};

const int ALPHA = 26;

struct TrieNode
{
    int child[ALPHA];
    int belong;

    TrieNode()
    {
        memset(child, 0, sizeof(child));
        belong = 0;
    }
};

class Trie
{
public:
    vector<TrieNode> nodes;
    int nodeCount;

    Trie()
    {
        nodes.push_back(TrieNode()); // root node
        nodeCount = 1;
    }

    void clear()
    {
        nodes.clear();
        nodes.push_back(TrieNode()); // root node
        nodeCount = 1;
    }

    void insert(const string &word, int cur, FenwickTree &ft)
    {
        int nodeIndex = 0;
        for (char ch: word)
        {
            int idx = ch - 'a';
            if (!nodes[nodeIndex].child[idx])
            {
                nodes[nodeIndex].child[idx] = nodeCount;
                nodes.push_back(TrieNode());
                nodeCount++;
            }
            nodeIndex = nodes[nodeIndex].child[idx];
            if (nodes[nodeIndex].belong)
            {
                ft.add(nodes[nodeIndex].belong, -1);
            }
            nodes[nodeIndex].belong = cur;
            ft.add(nodes[nodeIndex].belong, 1);
        }
    }

};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<string> words(N + 1);
    vector<vector<pair<int, int>>> Q(N + 1);
    vector<int> ans(M + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> words[i];
    }

    for (int i = 1; i <= M; ++i)
    {
        int l, r;
        cin >> l >> r;
        Q[r].emplace_back(l, i);
    }
    Trie trie;
    vector<pair<int, int>> stk(N + 1);
    int top = 0;
    FenwickTree ft(N);
    for (int i = 1; i <= N; ++i)
    {
        int l = (int) words[i].size();
        while (top && stk[top].second <= l)--top;
        stk[++top] = make_pair(i, l);
        trie.insert(words[i], i, ft);
        for (auto &j: Q[i])
        {
            int mval = lower_bound(stk.data() + 1, stk.data() + 1 + top, make_pair(j.first, 0))->second;
            ans[j.second] = ((int) trie.nodes.size() - 1 - ft.query(j.first - 1)) * 2 - mval;
        }
    }

    for (int i = 1; i <= M; ++i)
    {
        printf("%d\n", ans[i]);
    }

    return 0;
}

E 智乃的小球

题意

个一次函数，求一个最小的使得区间内存在至少个交点

题解

是任意值也能做，这里简化了一下变成

比较无脑的贴板子做法是先按照排序，然后二分，求出后的位置数组，贴一个树状数组求逆序对的板子，则交点数就是逆序对数

这个方法虽然是的，但是好处在于无脑，同时的值可以无其他限制条件

由于，想这么一个问题，假设有三个向左运动的球按照从左到右的顺序分布，两个向右的球也是从左到右的顺序，且全部位于的左侧，假设经过一段时间后，发现与发生碰撞，可以推理出以下两点事实

1. 一定与发生过碰撞
2. 一定与发生过碰撞

这两个事实分别代表两个单调性，只基于1也能写一个双log的二分套二分，两个都用上可以使用双指针技巧优化到线性

时间复杂度

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int INF = 1000000001;

long long count_pairs(long long t, vector<long long> &u, vector<long long> &v)
{
    long long result = 0;
    int p1 = 0, p2 = 0;
    for (auto &i: u)
    {
        while (p2 < v.size() && v[p2] < i)++p2;
        while (p1 < v.size() && v[p1] <= i + t)++p1;
        result += p1 - p2;
    }
    return result;
}

int main()
{
    int n;
    long long k;

    scanf("%d %lld", &n, &k);
    vector<pair<long long, long long>> a(n);//p v
    vector<long long> u, v;
    for (int i = 0; i < n; ++i)
    {
        long long x, y;
        scanf("%lld %lld", &x, &y);
        if (y == 1)
        {
            u.push_back(x);
        } else
        {
            v.push_back(x);
        }
    }

    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    int l = 0, r = INF, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        auto nowk = count_pairs(mid, u, v);
        if (nowk >= k)
        {
            r = mid - 1;
        } else
        {
            ans = mid;
            l = mid + 1;
        }
    }
    if (ans == INF)
    {
        printf("No\n");
        return 0;
    }
    ans++;
    printf("Yes\n%d.%c00000\n", ans / 2, "05"[ans & 1]);
    return 0;
}

F 智乃的捉迷藏

题意

问方程组是否存在非负整数解

题解

（小学数奥题——不等式）

等式左右两边求和得，令，得

解得

题目要求同时为非负整数

则整理后得时，符合条件

时间复杂度

PS：实在不会算可以暴力，大学生擅长使用复杂方法解决简单问题

代码

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

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, a, b, c;
        cin >> n >> a >> b >> c;
        if (n <= a + b + c && a + b + c <= 2 * n)
        {
            cout << "Yes\n";
        } else
        {
            cout << "No\n";
        }
    }
    return 0;
}
 

G 智乃与模数

题意

求中前大数的和

题解

，其中可以使用一种叫做整除分块/数论分块的技巧暴力枚举

形式化的：对于每个整除分块区间,成立

这个结论比较入门，如果不懂的话可以自行百度

则在每一个分块区间可表示为等差数列，其中

二分第大的值，统计等差数列中大于的项

接下来使用等差数列求和公式，统计大于 项的和

时间复杂度

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    int N, K;
    cin >> N >> K;
    int L = 1, R = N;
    int val = 0, vtot = 0;
    while (L <= R)
    {
        int mid = (L + R) / 2;
        int tot = 0;
        for (int l = 1, r; l <= N; l = r + 1)
        {
            r = N / (N / l);
            int a = N - N / l * l;
            int k = (N / l);
            if (a < mid)continue;
            //cout << "a " << a << " " << mid << endl;
            tot += min((a - mid) / k + 1, r - l + 1);
        }
        //cout << "aaa " << mid << " " << tot << endl;
        if (tot >= K)
        {
            L = mid + 1;
        } else
        {
            vtot = tot;
            val = mid;
            R = mid - 1;
        }
    }
    //cout << val << " ** " << vtot << endl;
    ll ans = 1LL * (K - vtot) * (val - 1);
    for (int l = 1, r; l <= N; l = r + 1)
    {
        r = N / (N / l);
        int a = N - N / l * l;
        int k = (N / l);
        if (a < val)continue;
        int len = min((a - val) / k + 1, r - l + 1);
        //cout << "calc " << a << " " << k << " " << len << endl;
        ans += 1LL * (a * 2 - k * (len - 1)) * len / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

H 智乃与黑白树

题意

给定一颗树，定义它的权值为所有从黑色节点出发到到白色节点的简单路径之和，查询独立删除每一条边后形成两颗新树的权值分别是多少

题解

定义三个函数init(x),link(x,y),cut(x,y)

init表示如果树退化成一个单点，如何初始化dp数组的值

link表示当前的根节点为x，从子树y到x的状态转移处理

有了init和link则树形DP的代码可以编写为

void dfs(int x, int fa)
{
    init(x);

    for (auto &i: G[x])
    {
        if (i == fa)continue;
        dfs(i, x);
        link(x, i);
    }
}

cut函数表示前的根节点为x，且已经包含了关于子树y到子树x的转移，还原到不包含子树y转移的处理

对于cut函数，可以使用以下方法构造：

计算机中常用的两种顺序模型：FIFO(First Input First Output)，LIFO(Last Input First Output)，代表性的数据结构分别是队列和堆栈

对于复合型操作序列，假定其原子操作的逆操作为，原子操作的逆操作为，...，原子操作的逆操作为，则操作序列的逆操作序列为原子操作逆操作的LIFO序，即

有了这个理论，不要管操作序列有多复杂，只要写出对应的逆操作，再把顺序反过来写就能从link函数得到cut函数

有了link和cut，可以定义changeRoot(x,y)函数，表示当前的根节点是x,替换为y

核心代码只有两行

cut(x,y);
link(y,x);

这个题因为本来也要断开每一条边，所以换根的时候调用cut函数后顺手记录下答案。

PS：无逆操作（例如max，min）或者无逆元（例如乘以0）需要其他小技巧解决

PS2：如果一个动态规划的状态转移方程是可逆操作，那么它存在带修改的潜力

时间复杂度

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
struct dp_node
{
    long long dpb, dpw, sb, sw, val;
};

dp_node dp[MAXN];

void init_b(int root)
{
    memset(&dp[root], 0, sizeof(dp_node));
    dp[root].sb = 1;
}

void init_w(int root)
{
    memset(&dp[root], 0, sizeof(dp_node));
    dp[root].sw = 1;
}

void link(int root1, int root2)
{
    dp[root1].val += dp[root2].val +
                     dp[root1].dpb * dp[root2].sw +
                     dp[root1].dpw * dp[root2].sb +
                     dp[root1].sw * (dp[root2].dpb + dp[root2].sb) +
                     dp[root1].sb * (dp[root2].dpw + dp[root2].sw);

    dp[root1].dpw += dp[root2].dpw + dp[root2].sw;
    dp[root1].dpb += dp[root2].dpb + dp[root2].sb;

    dp[root1].sb += dp[root2].sb;
    dp[root1].sw += dp[root2].sw;

}

void cut(int root1, int root2)
{
    dp[root1].sw -= dp[root2].sw;
    dp[root1].sb -= dp[root2].sb;

    dp[root1].dpb -= dp[root2].dpb + dp[root2].sb;
    dp[root1].dpw -= dp[root2].dpw + dp[root2].sw;

    dp[root1].val -= dp[root2].val +
                     dp[root1].dpb * dp[root2].sw +
                     dp[root1].dpw * dp[root2].sb +
                     dp[root1].sw * (dp[root2].dpb + dp[root2].sb) +
                     dp[root1].sb * (dp[root2].dpw + dp[root2].sw);
}

vector<int> G[MAXN];
map<pair<int, int>, int> id;
int n;
pair<long long, long long> ans[MAXN];
char s[MAXN];

void dfs(int x, int fa)
{
    if (s[x] == 'b')init_b(x);
    else init_w(x);

    for (auto &i: G[x])
    {
        if (i == fa)continue;
        dfs(i, x);
        link(x, i);
    }
}

void dfs2(int x, int fa)
{
    for (auto &i: G[x])
    {
        if (i == fa)continue;
        cut(x, i);
        if (id.find(make_pair(x, i)) != id.end())
        {
            ans[id[make_pair(x, i)]] = make_pair(dp[x].val, dp[i].val);
        }
        if (id.find(make_pair(i, x)) != id.end())
        {
            ans[id[make_pair(i, x)]] = make_pair(dp[i].val, dp[x].val);
        }
        link(i, x);
        dfs2(i, x);
        cut(i, x);
        link(x, i);
    }
}

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        id[make_pair(u, v)] = i;
    }
    dfs(1, 0);
    dfs2(1, 0);
    for (int i = 1; i < n; ++i)
    {
        printf("%lld %lld\n", ans[i].first, ans[i].second);
    }
    return 0;
}

/*
5
bwbwb
1 2
2 5
4 1
3 1
*/

I 智乃的兔子跳

题意

构造等差数列使得数组中的值尽可能的出现在等差数列当中，要求公差大于

题解

分情况讨论：

如果，那么要么取走所有奇数，要么取走所有偶数。答案一定不小于

如果，首先因为知道的时候答案已经不小于，所以如果，则答案必须严格大于才有意义

则如果真实答案的，随机从中取两个数，成功的概率无限接近1/4，随机10次，找到正确答案的概率仍然有，所以可以随机100次，成功率可达到，失败概率相当于随机一个long long类型的数，它的值是0。

所以每次随机取两个不同的数，假设他们的差是，如果这两个数在正确答案的集合中，则答案一定为的一个质因子（只用统计质数就行，比如统计过2和3，就不用统计6，因为6肯定不如2或者3）

关于是否需要用map统计每一个余数，实际上是不需要的，因为假设，那么正确答案将成为所有余数中的绝对众数，正确答案几乎不可能被这样引入，引入一个的复杂度并不会使得成功率有效提升，换句话说还不如多尝试次随机测试。

时间复杂度，取100比较合适

代码

#include<bits/stdc++.h>

using namespace std;

class RandomNumberGenerator
{
public:
    RandomNumberGenerator() : gen(std::random_device{}())
    {}

    int generate(int l, int r)
    {
        std::uniform_int_distribution<> dis(l, r);
        return dis(gen);
    }

private:
    std::mt19937 gen;
};

int main()
{

    int n;
    scanf("%d", &n);
    vector<int> v(n);
    RandomNumberGenerator rng;

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &v[i]);
    }
    if (n == 1)
    {
        printf("%d 2\n", v[0]);
        return 0;
    }
    int ans = 0, p = v[0], k = 2;
    int T = 100;
    while (T--)
    {
        auto i = rng.generate(0, n - 1);
        auto j = i;
        while (i == j)
        {
            j = rng.generate(0, n - 1);
        }
        auto temp = abs(v[i] - v[j]);
        if (temp == 1)
        {
            continue;
        }
        for (int d = 2; d * d <= temp; ++d)
        {
            if (temp % d == 0)
            {
                while (temp % d == 0)temp /= d;
                int cnt = 0;
                for (const auto &it: v)
                {
                    if ((v[i] - it) % d == 0)++cnt;
                }
                if (cnt > ans)
                {
                    ans = cnt;
                    p = v[i] % d;
                    k = d;
                }
            }
        }
        if(temp != 1)
        {
            int cnt = 0;
            for (const auto &it: v)
            {
                if ((v[i] - it) % temp == 0)++cnt;
            }
            if (cnt > ans)
            {
                ans = cnt;
                p = v[i] % temp;
                k = temp;
            }
        }
    }
    printf("%d %d\n", p, k);
    return 0;
}

/*
6
7 1 501 201 5 301
*/

J 智乃画二叉树

题意

按照给定二叉树结构，画字符画

题解

略

代码

#include <bits/stdc++.h>

using namespace std;

/*
 *                    __
                     /8 \
                     \__/
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
                /            \
               /              \
              /                \
             /                  \
          __/                    \__
         /4 \                    /12\
         \__/                    \__/
         /  \                    /  \
        /    \                  /    \
       /      \                /      \
    __/        \__          __/        \__
   /2 \        /6 \        /10\        /14\
   \__/        \__/        \__/        \__/
 __/  \__    __/  \__    __/  \__    __/  \__
/1 \  /3 \  /5 \  /7 \  /9 \  /11\  /13\  /15\
\__/  \__/  \__/  \__/  \__/  \__/  \__/  \__/
*/
const int INF = 1 << 30;
const int MAXN = 200005;
const int MAXM = 5005;
int n, ch[MAXN][2], fx[MAXN], fy[MAXN], l2[MAXN], dch[MAXN][2], mp_tree[MAXN];
bool vis[MAXN], is_root[MAXN];
char s[MAXM][MAXM];

int lowbit(int x) {
    return x & -x;
}

void dfs(int root1, int root2) {
    assert(root1!=0&&root2!=0);
    mp_tree[root1] = root2;
    vis[root1] = true;
    for (int i = 0; i <= 1; ++i) {
        if (ch[root2][i] != -1) {
            dfs(dch[root1][i], ch[root2][i]);
        }
    }
}

int cal_deep(int root) {
    int ret = 0;
    for (int i = 0; i <= 1; ++i) {
        if (ch[root][i] != -1) {
            ret = max(ret, cal_deep(ch[root][i]) + 1);
        }
    }
    return ret;
}

void draw_node(int id, int x) {
    sprintf(s[fx[l2[lowbit(id)]]] + fy[id], "%d", x);
    if (x < 10) {
        s[fx[l2[lowbit(id)]]][fy[id] + 1] = ' ';
    }
    s[fx[l2[lowbit(id)]] - 1][fy[id]] = '_';
    s[fx[l2[lowbit(id)]] - 1][fy[id] + 1] = '_';
    s[fx[l2[lowbit(id)]]][fy[id] - 1] = '/';
    s[fx[l2[lowbit(id)]]][fy[id] + 2] = '\\';
    s[fx[l2[lowbit(id)]] + 1][fy[id] - 1] = '\\';
    s[fx[l2[lowbit(id)]] + 1][fy[id]] = '_';
    s[fx[l2[lowbit(id)]] + 1][fy[id] + 1] = '_';
    s[fx[l2[lowbit(id)]] + 1][fy[id] + 2] = '/';
}

void draw_left_line(int id) {
    int x = fx[l2[lowbit(id)]] + 2;
    int y = fy[id] - 1;
    while (s[x][y] == '\0') {
        s[x][y] = '/';
        x++, y--;
    }
}

void draw_right_line(int id) {
    int x = fx[l2[lowbit(id)]] + 2;
    int y = fy[id] + 2;
    while (s[x][y] == '\0') {
        s[x][y] = '\\';
        x++, y++;
    }
}
/*
6
6 5
-1 -1
-1 2
1 3
-1 -1
-1 -1
*/
//1 7 13 19 25
int main() {
    fx[1] = fy[1] = l2[1] = 1;
    for (int i = 2; i <= 180; ++i) {
        fx[i] = fx[i - 1] * 2 + 2;
        fy[i] = fy[i - 1] + 3;
        l2[i] = l2[i / 2] + 1;
    }
    for (int i = 1; i <= 180; ++i) {
        fx[i] = 200 - fx[i];
        if (lowbit(i) != 1) {
            dch[i][0] = i - lowbit(i >> 1);
            dch[i][1] = i + lowbit(i >> 1);
        }
    }
    scanf("%d %*d", &n);
    for (int i = 1; i <= n; ++i) {
        is_root[i] = true;
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &ch[i][0], &ch[i][1]);
        is_root[ch[i][0]] = is_root[ch[i][1]] = false;
    }

    int root;
    for (int i = 1; i <= n; ++i) {
        if (is_root[i]) {
            root = i;
        }
    }

    int froot = 1 << cal_deep(root);

    dfs(froot, root);
    for (int i = 1; i < 180; ++i) {
        if (vis[i]) {
            draw_node(i, mp_tree[i]);
        }
    }

    for (int i = 1; i < 180; ++i) {
        if (vis[i] && ch[mp_tree[i]][0] != -1) {
            draw_left_line(i);
        }
        if (vis[i] && ch[mp_tree[i]][1] != -1) {
            draw_right_line(i);
        }
    }

    int lx = INF, rx = -INF, ly = INF, ry = -INF;

    for (int i = 0; i <= 200; ++i) {
        for (int j = 0; j <= 2000; ++j) {
            if (s[i][j]) {
                lx = min(lx, i);
                rx = max(rx, i);
                ly = min(ly, j);
                ry = max(ry, j);
            }
        }
    }
    for (int i = lx - 1; i <= rx + 1; ++i) {
        for (int j = ly - 1; j <= ry + 1; ++j) {
            if (i == lx - 1 || i == rx + 1 || j == ly - 1 || j == ry + 1) {
                printf("*");
            } else {
                printf("%c", s[i][j] ? s[i][j] : ' ');
            }
        }
        printf("\n");
    }
    return 0;
}

K 智乃的逆序数

题意

构造一个序列包含若干个值域互不相交子序列，且逆序对恰好为对

题解

逆序对的其中一个重要性质是，逆序对的值等于其在冒泡排序的过程中，相邻元素的交换次数，且排序过程中每次交换相邻元素后逆序对的数目减少1。

因为值域互不相交，所以直接按照值域区间从大到小排序时逆序对最多，反过来逆序对最少。

假设按照从大到小排序，记逆序对为，如果则无解，直接输出，否则跑一个真正的冒泡排序，但是加一个特判：阻止来自相同序列的元素互相交换，每次交换令，直到时停止并输出，特别的，如果跑完了仍然还多，则说明无解。

时间复杂度

顺带一提，理论上存在的解法，构造方法类似逆康拓展开，不过预计代码比较繁琐，感兴趣可以自行了解。

代码

#include <bits/stdc++.h>

using namespace std;
int n, k;
vector<pair<int, int>> a;
vector<vector<int>> v;

int calc()
{
    int ret = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        for (int j = i + 1; j < a.size(); ++j)
        {
            if (a[i] > a[j])++ret;
        }
    }
    return ret;
}

void bsort()
{
    for (int i = 0; i < a.size(); ++i)
    {
        for (int j = 0; j + 1 < a.size(); ++j)
        {
            if (a[j].first == a[j + 1].first)continue;
            if (k > 0 && a[j].second < a[j + 1].second)
            {
                swap(a[j], a[j + 1]);
                --k;
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    v.resize(n);
    for (int i = 0; i < n; ++i)
    {
        int l;
        scanf("%d", &l);
        for (int j = 0; j < l; ++j)
        {
            int x;
            scanf("%d", &x);
            v[i].push_back(x);
        }
    }
    sort(v.begin(), v.end(), [](const vector<int> &A, const vector<int> &B)
    {
        return A[0] < B[0];
    });
    for (int i = 0; i < n; ++i)
    {
        for (auto &j: v[i])
        {
            a.emplace_back(i, j);
        }
    }
    k -= calc();
    if (k < 0)
    {
        printf("No");
        return 0;
    }
    bsort();
    if (k > 0)
    {
        printf("No");
        return 0;
    }
    printf("Yes\n");
    for (int i = 0; i < a.size(); ++i)
    {
        printf("%d%c", a[i].second, " \n"[i + 1 == a.size()]);
    }
    return 0;
}

L 智乃的三角遍历

题意

一笔画出层正三角形组成的图形

题解

Solution1

反正，自己在纸上把所有情况都画出来然后直接输出答案

Solution2

Solution3

可以写个真的dfs求欧拉回路

时间复杂度

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> G[MAXN];//to,id
bool vis[MAXN];
int n, b[MAXN], tot;
vector<int> ans;

void add_edge(int u, int v)
{
    G[u].emplace_back(v, tot);
    G[v].emplace_back(u, tot++);
}

void dfs(int x)
{
    for (auto &i: G[x])
    {
        if (vis[i.second])continue;
        vis[i.second] = true;
        dfs(i.first);
    }
    ans.push_back(x);
}

int main()
{
    scanf("%d", &n);
    b[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        b[i] = b[i - 1] + i;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            int p1 = b[i] + j, p2 = b[i + 1] + j, p3 = b[i + 1] + j + 1;
            add_edge(p1, p2);
            add_edge(p2, p3);
            add_edge(p3, p1);
        }
    }
    dfs(1);
    printf("Yes\n");
    for (int i = 0; i < ans.size(); ++i)
    {
        printf("%d%c", ans[i], " \n"[i + 1 == ans.size()]);
    }
    return 0;
}

M 智乃的牛题

题意

问输入的字符串是不是能组成单词nowcoder

题解

可以用std::map统计下字母出现的次数是不是符合，也可以用std::sort判断排序后的内容是否为cdenoorw

代码

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

int main() {
    string a;
    cin>>a;
    sort(a.begin(), a.end());
    if(a=="cdenoorw")
    {
        cout<<"happy new year"<<endl;
    }else{
        cout<<"I AK IOI"<<endl;
    }
}

PS：在群里喊一句I AK IOI会被人截图截下来

时间复杂度