2024TJUACM暑期集训（三）2024.7.22-2024.7.28

ICPC-CCPC
字数统计: 14.1k   |   阅读时长≈ 68 分钟

第三周

SW-3-1 鸡爪

题目信息

图例

定义上述结构图形为一个鸡爪，规定其中心点以及三条边属于该鸡爪，另外三个点不属于。

给定条边以及任意个点，要求其能够构造出最多的鸡爪，并且输出所有可能的构造中，边集顶点行优先遍历字典序最小的一个。

题目解析

明眼易得最多构造只鸡爪，但是要输出一个字典序尽可能小的，这就要求连边尽可能往点编号小的点连边构造，不难想到鸡爪的中心点为~。

那么就可以让每个鸡爪的中心点和连边，作为第鸡爪的一部分组成边。

那么对于号中心点而言，其不能和剩下的任何属于的顶点之间的边构造鸡爪，其需要额外的三个点进行构造。

所以对其和顶点进行连边，组成第一个鸡爪。

此时编号为的鸡爪就不需要再额外加点了，其和之间的边可以构成一只鸡爪。

编号为的可以和编号构成。

剩下的，和编号，，构成即可。

分类讨论即可，特殊处理鸡爪数量小于等于的。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'//交互题就删
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,p;
void solve(){
    cin>>n;p=n/3;
    if(n==1)cout<<1<<" "<<2<<endl;
    else if(n==2) {
        cout<<1<<" "<<2<<endl;
        cout<<1<<" "<<3<<endl;
    }
    else{
    for(int i=2;i<=p;i++)cout<<1<<" "<<i<<endl;
    cout<<1<<" "<<p+1<<endl;
    cout<<1<<" "<<p+2<<endl;
    cout<<1<<" "<<p+3<<endl;
    for(int i=3*p+1;i<=n;i++)cout<<1<<" "<<p+3+(i-3*p)<<endl;
    for(int i=3;i<=p;i++)cout<<2<<" "<<i<<endl;
    if(p>=2){
        cout<<2<<" "<<p+1<<endl;
        cout<<2<<" "<<p+2<<endl;
    }
    for(int i=4;i<=p;i++)cout<<3<<" "<<i<<endl;
    if(p>=3)cout<<3<<" "<<p+1<<endl;}
    //cout<<endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){solve();}
}

SW-3-2 绝对不模拟的简单魔方

题目信息

给定一个三阶魔方，保证只扭侧面不超过三次。扭的时候掉了同一个角的两篇贴纸，贴纸现在被胡乱的贴了回去。给出现在模仿状态的展开图，问贴对了贴纸没。

题目解析

赛时觉得是硬暴力，码了五百多行（只能说还诶看情况听话）

旋转魔方的时候，魔方的八个角的贴纸一定遵循原先的拓补序，也就是说，无论怎么转，其侧面贴纸颜色的顺序一定不会发生改变，其指定视角下贴纸顺序固定。

所以，我们只需要暴力判断八个角的现行贴纸顺序对不对就行了。

有一个细节在于旋转之后可能发生循环位移（即原顺时针视角为123，现在顺时针视角为312），需要归一化。（上层归1，下层归6）

#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define db double
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define i128 __int128
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define endl '\n'
using namespace std;
// #define int long long
// 原始魔方八个角，顺时针
struct cor
{
    int a, b, c;
    cor(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
    bool operator==(cor t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
    void srt()
    { // 按大小排序
        if (a > b)
            swap(a, b);
        if (b > c)
            swap(b, c);
        if (a > b)
            swap(a, b);
    }
    void mkstd()
    { // 把三元组化为以1或6开头的形式
        int t;
        while (a != 1 && a != 6)
        {
            t = a;
            a = b;
            b = c;
            c = t;
        }
    }
};
vector<cor> std_cor = <!--swig0-->; // 还原状态的8个角（逆时针）
void solve()
{
    vector<string> mf(9);
    for (auto &s : mf)
        cin >> s;          // 注意加&
    vector<cor> corners = {// 给定魔方的八个角，逆时针
                           {mf[0][3] - '0', mf[3][11] - '0', mf[3][0] - '0'},
                           {mf[8][3] - '0', mf[5][0] - '0', mf[5][11] - '0'},
                           {mf[3][8] - '0', mf[3][9] - '0', mf[0][5] - '0'},
                           {mf[5][8] - '0', mf[8][5] - '0', mf[5][9] - '0'},
                           {mf[6][3] - '0', mf[5][3] - '0', mf[5][2] - '0'},
                           {mf[3][3] - '0', mf[2][3] - '0', mf[3][2] - '0'},
                           {mf[6][5] - '0', mf[5][6] - '0', mf[5][5] - '0'},
                           {mf[3][6] - '0', mf[2][5] - '0', mf[3][5] - '0'}};
    for (auto &cor : corners)
        cor.mkstd();
    for (auto &cor : corners)
    {
        int fl = 0;
        for (auto &st : std_cor)
            if (st == cor)
            {
                fl = 1;
                break;
            }
        if (fl)
            continue;
        cor.srt();
        cout << cor.a << ' ' << cor.b << ' ' << cor.c << endl;
        return;
    }
    cout << "No problem" << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

SW-3-3 图计算

题目信息

给定一张图，将其复制次。每次维护一个操作，表示将第张图的连边。每次操作后询问有多少个点对在所有图中均处于联通状态。

题目解析

并查集维护多图联通状态，关键是如何维护计数。

将每个点在每张图中的祖先组成一个序列串，对序列字符串进行来判断两个点是否在所有图中均有相同祖先（值不变）。

考虑计数变化，如果对于第张图的之间连边，则的祖先会由之前的变为现在的祖先，所有和处于同一联通块的都会发生变化。这个操作的维护可以通过多减多补的方式来实现，即暴力联通分块内的所有点，每一个点都先断掉和剩下的点的所有联系，然后父亲变化，变化，和新​的所有点建立联系。这样可以保证同连通分量的点都正确的维护了状态的变化（一减一加抵消了，维护了同变化点的连通性未变）

// 1012 图计数（d张图，每次在某个图加入一条边，并询问有多少个无序点对在每张图上都连通）做法：哈希+启发式合并
// 维护d个并查集，这样每个点在每张图上的祖先组成了一个d长的序列，我们对序列哈希，如果两个序列相同就代表在每张图上都连通
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10, mod = 998244353;
int d, n, m, k, ans;
int w[201][50005], fa[201][50005];
int weight[50005];
unordered_map<int, int> b;
vector<int> v[201][50001];
int find(int k, int x)
{
    if (fa[k][x] != x)
    {
        fa[k][x] = find(k, fa[k][x]);
        return fa[k][x];
    }
    else
        return x;
}
inline void read(int &x)
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = (s * 10) + ch - '0';
        ch = getchar();
    }
    x = s * w;
}
void add(int x, int y, int k, int c)
{ // 启发式合并
    int fx = find(k, x), fy = find(k, y);
    if (fx == fy)
    {
        if (c == 1)
            cout << ans << "\n";
        return;
    }
    if (v[k][fx].size() > v[k][fy].size())
        swap(fx, fy);
    fa[k][fx] = fy;
    for (int i : v[k][fx])
    {
        b[weight[i]]--;
        ans -= b[weight[i]];
        weight[i] -= w[k][fx];
        weight[i] += w[k][fy];
        ans += b[weight[i]];
        b[weight[i]]++;
        v[k][fy].push_back(i);
    }
    v[k][fx].clear();
    if (c == 1)
        cout << ans << "\n";
}
void solve()
{
    ans = 0;
    mt19937 myrand(time(0));
    read(n);
    read(m);
    read(d);
    read(k);
    d++;
    for (int j = 1; j <= n; j++)
        weight[j] = 0;
    for (int i = 1; i <= d; i++)
        for (int j = 1; j <= n; j++)
            v[i][j].clear();
    for (int i = 1; i <= d; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            w[i][j] = (long long)myrand() * (long long)myrand() % 1000000001339; // 每层图的每个点都赋一个随机点权
            weight[j] += w[i][j];                                                // 一个点的权重就是各层的相加
            v[i][j].push_back(j);                                                // 存以i、j为父亲的所有点
            fa[i][j] = j;                                                        // 记录父亲
        }
    }
    b.clear();
    for (int i = 1; i <= n; i++)
        b[weight[i]]++; // 赋初值
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        read(x);
        read(y);
        for (int j = 1; j <= d; j++)
        {
            add(x, y, j, 0);
        }
    }
    for (int i = 1; i <= k; i++)
    {
        int x, y, w;
        read(x);
        read(y);
        read(w);
        add(x, y, w, 1);
    }
}
signed main()
{
    int T;
    read(T);
    while (T--)
        solve();
    return 0;
}

SW-3-4 在A里面找有C的B

题目解析

给定一个初始字符串和,询问次，每次询问两个字符串、，判断是否在中且是否在中。

题目解析

板子题，但是不知道为何会，算的复杂度是真的。

前面离线模式串后自动机判定，后面预处理模式串后在线比较，时间复杂度.

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200010;
#define maxn 200010
char s[maxn], T[maxn];
int n, cnt, vis[200051], ans, in[maxn], Map[maxn];
struct kkk
{
    int son[26], fail, flag, ans;
    void clear() { memset(son, 0, sizeof(son)), fail = flag = ans = 0; }
} trie[maxn];
queue<int> q;
void insert(char *s, int num)
{
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; i++)
    {
        int v = s[i] - 'a';
        if (!trie[u].son[v])
            trie[u].son[v] = ++cnt;
        u = trie[u].son[v];
    }
    if (!trie[u].flag)
        trie[u].flag = num;
    Map[num] = trie[u].flag;
}
void getFail()
{
    for (int i = 0; i < 26; i++)
        trie[0].son[i] = 1;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        int Fail = trie[u].fail;
        for (int i = 0; i < 26; i++)
        {
            int v = trie[u].son[i];
            if (!v)
            {
                trie[u].son[i] = trie[Fail].son[i];
                continue;
            }
            trie[v].fail = trie[Fail].son[i];
            in[trie[v].fail]++;
            q.push(v);
        }
    }
}
void topu()
{
    for (int i = 1; i <= cnt; i++)
        if (in[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[trie[u].flag] = trie[u].ans;
        int v = trie[u].fail;
        in[v]--;
        trie[v].ans += trie[u].ans;
        if (in[v] == 0)
            q.push(v);
    }
}
void query(char *s)
{
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; i++)
        u = trie[u].son[s[i] - 'a'], trie[u].ans++;
}
bool check[maxn];
char b[MAX_N], a[MAX_N];
int P[MAX_N]; // next数组，next[i]表示1-i的最长前缀后缀的那个长度
int nt, mt;
void KMP_start()
{
    mt = strlen(b + 1);
    P[1] = 0;
    for (int i = 2, j = 0; i <= mt; i++)
    {
        while (j > 0 && b[i] != b[j + 1])
            j = P[j]; // p就是next数组，j在循环中最初表示的是next[i-1],这步是重复跳next
        if (b[j + 1] == b[i])
            j++;  // 如果相等则next进步
        P[i] = j; // 赋值next数组
    }
}
bool KMP_judge()
{
    nt = strlen(a + 1);
    for (int i = 1, j = 0; i <= nt; i++)
    {
        while (j > 0 && a[i] != b[j + 1])
            j = P[j];
        if (b[j + 1] == a[i])
            j++;
        if (j == mt)
        {
            return true;
        }
    }
    return false;
}
char str[MAX_N + 10];
char ss[MAX_N + 10];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        cnt = 1;
        scanf("%s", str);   // A
        scanf("%s", b + 1); // 1-n存储C
        KMP_start();
        for (int i = 1; i <= n; i++)
        {
            bool flag = 1;
            scanf("%s", ss);
            scanf("%s", a + 1);
            check[i] = KMP_judge();
            insert(ss, i);
        }
        getFail();
        query(str);
        topu();
        for (int i = 1; i <= n; i++)
        {
            if (check[i])
            {
                if (vis[Map[i]] > 0)
                {
                    printf("%d", i);
                    if (i != n)
                        printf(" ");
                }
            }
        }
        printf("\n");
        for (int i = 1; i <= cnt; i++)
            trie[i].clear();
    }
    //fflush(stdout);
    // system("pause");
    return 0;
}

SW-3-5 成长、生命、幸福

题目信息

给一棵树，这棵树会不断的成长。对于一个节点的成长，先将这个节点变为边型（为这个点的度数），然后将原本与这个点相连的边随机匹配多边形上的点，再随机删除由这个点变化成的多边形上的一条边。

特别的，对于一个度数为0或1的点，进行成长将不会发生变化。

对于一棵树的成长，定义为树上所有的节点进行一次成长。求在这棵树进行次成长后，直径的长度最大可能是多少。

这里定义树的直径的长度为直径上的点数。

答案对取模。

题目解析

不难返现度数为和的点成长价值最大。

对于初始树的每一个节点，让其成长到、的度数后开始倍增就可以了，由于接边的随意性，任何一条原树上的路径都可以接到这个点生长结果的最大值上，所以点权就可以修改为该点能长出来的最大直径。最后树的直径跑树形，注意一点是系数很大但是维护时不能取模，当很大的时候直接按照比例缩放估算就可以了。

// 1008 图生长
// 注意到度数为i的点数成长m轮的贡献是确定的，2^(m-1)*结点为2的数量，2^m-1结点为3的数量。m太大时可以用1：2来估计
// 所以我们就以这个贡献跑树的直径即可，树形dp思想以每个点为根求最长路和次长路即可
// 但是m太大时我们计算不了每个点的贡献，就按照上面那个来计算，所以最后ans要存结点为2的数量和3的数量，最后再用具体的A、B来计算最终答案
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, m, A, B;
vector<int> e[N];
struct node
{
    int x, y;
    friend inline node operator+(const node &A, const node &B)
    {
        return (node){A.x + B.x, A.y + B.y};
    }
} ans, f[N];
int sum(node a)
{
    return 1LL * A * a.x + 1LL * B * a.y;
}
long long ksm(int x, int y)
{
    if (y == 0)
        return 1;
    long long temp = ksm(x, y / 2) % mod;
    if (y % 2 == 0)
        return temp * temp % mod;
    else
        return (temp * temp % mod) * x % mod;
}
void dfs(int u, int fa)
{
    if (e[u].size() >= 2)
        f[u] = (node){2, e[u].size() - 2}; // 每个点生长一次有几个2度点、3度点
    else
        f[u] = (node){0, 0};
    node mx = (node){0, 0}, mmx = (node){0, 0};
    for (auto i : e[u])
    {
        if (i == fa)
            continue;
        dfs(i, u);
        if (sum(f[i]) > sum(mx))
        {
            mmx = mx, mx = f[i];
        }
        else if (sum(f[i]) > sum(mmx))
            mmx = f[i];
    } // 找最大和次大的两个点往下走（类似树形dp）
    if (sum(f[u]) + sum(mx) + sum(mmx) > sum(ans))
        ans = f[u] + mx + mmx;
    f[u] = f[u] + mx;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    if (m <= 20)
        A = 1 << m - 1, B = (1 << m) - 1;
    else
        A = 1, B = 2; // 跑dfs时作为一个点的贡献的系数
    ans.x = 0;
    ans.y = 0; // ans记录了最后有几个2度节点和3度节点
    dfs(1, 0);
    A = ksm(2, m - 1);
    B = (ksm(2, m) - 1 + mod) % mod;
    cout << ((ans.x * A % mod + ans.y * B % mod) + 2) % mod << endl;
    ; // 放大，正常输出答案
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

SW-3-6 深度自同构

题目信息

定义一个有根树森林是深度自同构的，当且仅当其任意两个深度相同的结点都拥有一致的度数。

给定，查询使用的节点个数最多可以构造出多少个满足要求的有根树森林

保证​

题目解析

赛时数的时候丢了一种情况导致推错公式，浪费了一个多钟头。

不难发现其必然是一个对称的结构，考虑因数枚举。

设，则可以将个点分成个连通分量，其中每个连通分量为单个节点悬挂一个的树（之于为什么这么算，因为手动模拟很快便会发现你多算了很多次个连通分量，每个分量只有单个节点的森林）。

设结果为，不难发现有以下公式： 主要谈一下时间复杂度的问题，枚举因数的时候使用类似埃氏筛法的调和枚举，复杂度是的，级别的数据可以做到伪线性()解决。

void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        f[i] += (f[i - 1] + 1);
        for (int j = (2 * i); j <= n; j += i)
        {
            f[j] += f[i - 1];
        }
    }
}

所以可以轻松通过时间限制。

#include <bits/stdc++.h>
using namespace std;
template <int MOD> // 模板参数
struct modint
{
    int val;
    static int norm(const int &x) { return x < 0 ? x + MOD : x; }
    static constexpr int get_mod() { return MOD; }
    modint inv() const
    {
        assert(val);
        int a = val, b = MOD, u = 1, v = 0, t;
        while (b > 0)
            t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
        assert(b == 0);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int &m) : val(norm(m)) {}
    modint(const long long &m) : val(norm(m % MOD)) {}
    modint operator-() const { return modint(norm(-val)); }
    bool operator==(const modint &o) { return val == o.val; }
    bool operator<(const modint &o) { return val < o.val; }
    modint &operator+=(const modint &o) { return val = (1ll * val + o.val) % MOD, *this; }
    modint &operator-=(const modint &o) { return val = norm(1ll * val - o.val), *this; }
    modint &operator*=(const modint &o) { return val = static_cast<int>(1ll * val * o.val % MOD), *this; }
    modint &operator/=(const modint &o) { return *this *= o.inv(); }
    modint &operator^=(const modint &o) { return val ^= o.val, *this; }
    modint &operator>>=(const modint &o) { return val >>= o.val, *this; }
    modint &operator<<=(const modint &o) { return val <<= o.val, *this; }
    modint operator-(const modint &o) const { return modint(*this) -= o; }
    modint operator+(const modint &o) const { return modint(*this) += o; }
    modint operator*(const modint &o) const { return modint(*this) *= o; }
    modint operator/(const modint &o) const { return modint(*this) /= o; }
    modint operator^(const modint &o) const { return modint(*this) ^= o; }
    modint operator>>(const modint &o) const { return modint(*this) >>= o; }
    modint operator<<(const modint &o) const { return modint(*this) <<= o; }
    friend std::istream &operator>>(std::istream &is, modint &a)
    {
        long long v;
        return is >> v, a.val = norm(v % MOD), is;
    }
    friend std::ostream &operator<<(std::ostream &os, const modint &a) { return os << a.val; }
    friend std::string tostring(const modint &a) { return std::to_string(a.val); }
    friend modint quickpow(const modint &a, const int &b)
    {
        assert(b >= 0);
        modint x = a, res = 1;
        for (int p = b; p; x *= x, p >>= 1LL)
            if (p & 1)
                res *= x;
        return res;
    }
};
using M107 = modint<1000000007>;
using M998 = modint<998244353>;

using Mint = M998;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
vector<int> pri;
const int N = 1e6 + 10;
bool isnp[N]; // is not prime: 不是素数设为1，是素数设为0
Mint f[N];
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        f[i] += (f[i - 1] + 1);//每个数都有1和自己作为因数，暴力转移
        for (int j = (2 * i); j <= n; j += i)
        {
            f[j] += f[i - 1];
        }
    }
}
signed main()
{
    IOS;
    int n;
    cin >> n;
    f[0] = f[1] = 1;
    init(n);
    for (int i = 1; i <= n; i++)
    {
        cout << f[i] << " ";
    }
}

SW-3-7 比特跳跃

题目信息

给定一张节点条边的无向图，第条边边权为；每两个点之间可直接幻影移形到达，从幻影移形到的代价为，求从开始单源最短路。保证

题目解析

除了正常跑最短路之外要考虑幻影移形的问题。

首先不可否定的是，如果选择从两个奇数点幻影移形的代价一定不低于从​向目的地幻影移形的代价。

如果从偶数点向奇数点幻影移形的代价同样一定会劣于从偶数点向幻影移形的代价。

但是，如果从偶数点向偶数点幻影移形的代价，不一定会劣于向偶数点的代价。如果，则其代价为，优于从开始的.

考虑只特判偶数到偶数的幻影移形，将和其他节点多连接一条边表示幻影移形路径参与跑最短路。还有要注意的是，如果当前节点的最短距离比要大了，就不用加边了，因为其一定劣于直接从到的直接幻影移形

枚举当前点的超集多取一个松弛操作就可以了。注意不要存边，否则会.

（论赛后把队友赛时的代码给了有多离谱，赛时过度紧张超集枚举的不全。还有，多组数据一定要记得清空，不然白吃好几发罚时）

#include <bits/stdc++.h>
#define int long long
// #define DEBUG 1
using namespace std;
typedef pair<int, int> P;
const int inf = 1e18;
const int N = 1e6 + 10;
int n, m, k, len;
int dis[N], vis[N];
struct node
{
    int to, val;
};
vector<node> edge[N];
void add(int x)
{
#ifdef DEBUG
    bitset<9> b(x);
    cout << "now adding edges at x = " << x << endl;
    cout << "bindary shows : " << b << endl;
    cout << "len = " << len << endl;
#endif
    vector<int> e;
    for (int i = 1; i < len; i++)
    {
        if (((x >> i) & 1) == 0)
        {
            e.push_back(1 << i);
        }
    }
    int s = e.size();
#ifdef DEBUG
    cout << "s = " << s << endl;
#endif
    for (int i = 1; i < (1 << s); i++)
    {
        int sum = x;
        for (int j = 0; j < s; j++)
        {
            if (((i >> j) & 1))
            {
                sum += e[j];
            }
        }
#ifdef DEBUG
        cout << "sum = " << sum << endl;
        cout << "bindary shows : " << bitset<9>(sum) << endl;
#endif
        if (sum <= n)
            // edge[x].push_back({sum, (sum)*k});
            dis[sum] = min(dis[sum], dis[x] + sum * k);
    }
}
void dijkstra()
{
    dis[1] = 0;
    priority_queue<P, vector<P>, greater<P>> q;
    q.push({0, 1});
    while (!q.empty())
    {
        P u = q.top();
        q.pop();
        if (vis[u.second])
            continue;
        vis[u.second] = 1;
        for (auto j : edge[u.second])
        {
            if (dis[j.to] > dis[u.second] + j.val)
            {
                dis[j.to] = dis[u.second] + j.val;
                q.push({dis[j.to], j.to});
                if ((j.to) % 2 == 0 && dis[j.to] < k)
                { // 加边
                    add(j.to);
                }
            }
        }
    }
}
void solve()
{
    cin >> n >> m >> k;
    int t = n;
    len = 0;
    while (t)
    {
        t >>= 1;
        len++;
    }
    for (int i = 1; i <= n; i++)
        edge[i].clear(), vis[i] = 0, dis[i] = inf;
    for (int i = 1, u, v, sum; i <= m; i++)
    {
        cin >> u >> v >> sum;
        edge[u].push_back({v, sum});
        edge[v].push_back({u, sum});
    }
    for (int i = 1; i <= n; i++)
        edge[1].push_back({i, k * (1 | i)}); // 1连到i的边
    dijkstra();
    for (int i = 2; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
    cout << endl;
}
signed main()
{
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

SW-3-8 单峰数列

题目信息

维护一个数据结构，判断以下内容

对于一个整数数列，如果其先严格递增，然后在某一点后严格递减，我们称这个数列为单峰数列（严格递增和严格递减的部分均要是非空）。

给定长度为 的整数数列，请你支持 次操作：

  1. 1 l r x：将 的每个数加 。
  2. 2 l r：判断 的元素是否全都相同。
  3. 3 l r：判断 的元素是否严格升序排序。当 时，认为符合严格升序排序。
  4. 4 l r：判断 的元素是否严格降序排序。当 时，认为符合严格降序排序。
  5. 5 l r：判断 的元素是否为单峰数列。保证 ​

题目信息

最唐氏的一集，直接开三个树状数组维护差分数组第位是正数、负数还是就可以了。

赛时单线段树就是维护不过来，思考区间、​和，这个玩意儿是不支持修改的！

第五个操作维护二分就行了。

#include <bits/stdc++.h>
// #define DEBUG 1
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
struct BIT
{
    vector<int> c;
    int ns;
    void init(int n)
    {
        c.resize(n + 1, 0);
        ns = n;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void add(int x, int y)
    {
        for (int i = x; i <= ns; i += lowbit(i))
            c[i] += y;
    }
    int query(int x)
    {
        int ans = 0;
        for (int i = x; i; i -= lowbit(i))
            ans += c[i];
        return ans;
    }
};
BIT bit[3];
int a[maxn];
int b[maxn];
int n;
void modifybit(int i, int x)
{
    if (b[i] > 0)
        bit[1].add(i, x);
    if (b[i] < 0)
        bit[2].add(i, x);
    if (b[i] == 0)
        bit[0].add(i, x);
}
void modify(int l, int r, int x)
{
    modifybit(l, -1);
    modifybit(r + 1, -1);
    b[l] += x;
    b[r + 1] -= x;
    modifybit(l, 1);
    modifybit(r + 1, 1);
}
bool checkeuqal(int l, int r)
{
    return bit[0].query(r) - bit[0].query(l) == r - l;
}
bool checkraise(int l, int r)
{
    return bit[1].query(r) - bit[1].query(l) == r - l;
}
bool checkfall(int l, int r)
{
    return bit[2].query(r) - bit[2].query(l) == r - l;
}
bool checkup_down(int l, int r)
{
    int cl = l, cr = r + 1;
    while (cr - cl > 1)
    {
#ifdef DEBUG
        cout << "cl=" << cl << " cr=" << cr << endl;
#endif
        int mid = (cl + cr) >> 1LL;
        if (checkraise(l, mid))
        {
#ifdef DEBUG
            cout << "checkraise at " << l << " to " << mid << endl;
#endif
            cl = mid;
        }
        else
        {
#ifdef DEBUG
            cout << "not checkraise at " << l << " to " << mid << endl;
#endif
            cr = mid;
        }
    }
    if (cl == l)
        return false;
    if (checkfall(cl, r))
        return true;
    return false;
}
void solve()
{
    cin >> n;
    bit[0].init(n);
    bit[1].init(n);
    bit[2].init(n);
#ifdef DEBUG
    cout << "n=" << n << endl;
    cout << "successfully create bit" << endl;
#endif
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
        modifybit(i, 1);
    }
#ifdef DEBUG
    cout << "successfully init bit" << endl;
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << bit[0].query(i) - bit[0].query(i - 1) << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << bit[1].query(i) - bit[1].query(i - 1) << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << bit[2].query(i) - bit[2].query(i - 1) << " ";
    cout << endl;
#endif
    int q;
    cin >> q;
    while (q--)
    {
        int op, l, r, x;
        cin >> op >> l >> r;
        switch (op)
        {
        case 1:
            cin >> x;
            modify(l, r, x);
            break;
        case 2:
            cout << checkeuqal(l, r) << endl;
            break;
        case 3:
            cout << checkraise(l, r) << endl;
            break;
        case 4:
            cout << checkfall(l, r) << endl;
            break;
        case 5:
            cout << checkup_down(l, r) << endl;
        }
    }
}
signed main()
{
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    IOS;
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        solve();
    return 0;
}

SW3-9 抓拍

题目信息

给定个同学的坐标以及指定不变的移动方向，所有人每秒都只移动一个单位。求最小的矩阵周长，使得该矩阵能够在某正整数时刻将所有人框起来。

题目解析

模拟，标答是三分，不会（）

感觉也没必要三分，赛时唐在模拟的过于复杂，想记录的东西太多，不是打表题记那么多状态干什么？

思想很简单，因为每条最外框边界线的移动一定是一个一次函数，而且其状态只有四种：一直不变、先缩后扩、先平后扩、一直外扩。

换言之，单条边状态改变点至多只有小常数个（算上初始时刻），且分段函数必然是线性一次函数。

所以只记录突变时间点就可以了，因为时间点很少，所有同学在该点的状态直接暴力枚举计算出当前外框坐标值就行了，别tm一直搁哪惦记着怎么维护当前时间具体是哪位同学在外面来​转移了，有那个必要吗？？？

在考虑突变计算点的计算问题，初始时并不知道最靠外的坐标的人的移动方向具体是什么，也就是初始边状态不确定，这个不好维护那就换一个啊

那就直接从同移动方向的人群的最值入手维护就行了，这个总能知道向某个方向移动的人的最值吧？

以向东走的为例。

向东走的只有三种状态改变可能：一直向东走没有遇到任何人、遇到一个南北走的​坐标最大的、迎面遇到一个东西向走的人。

其他同理，把所有的全算了，取最小值，以时间成本换代码成本，下班。

#include <cstdio>
#include <iostream>
#include <set>
#define int long long
#define RI register int
#define CI const int &
using namespace std;
const int N = 200005, INF = 1e18;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};
int n, x[N], y[N], mnx[4], mxx[4], mny[4], mxy[4]; // 0向东，1向西，2向南，3向北
char s[10], ch[N];
signed main()
{
    RI i;
    for (scanf("%lld", &n), i = 1; i <= n; ++i)
        scanf("%lld%lld%s", &x[i], &y[i], s), ch[i] = s[0];
    auto trs = [&](const char &ch)
    {
        switch (ch)
        {
        case 'E':
            return 0;
        case 'W':
            return 1;
        case 'S':
            return 2;
        case 'N':
            return 3;
        default:
            return -1;
        }
    };
    for (i = 0; i < 4; ++i)
        mnx[i] = mny[i] = INF, mxx[i] = mxy[i] = -INF;
    for (i = 1; i <= n; ++i)
    {
        int tp = trs(ch[i]);
        // 向tp方向走的最值
        mnx[tp] = min(mnx[tp], x[i]);
        mxx[tp] = max(mxx[tp], x[i]);
        mny[tp] = min(mny[tp], y[i]);
        mxy[tp] = max(mxy[tp], y[i]);
    }
    set<int> key;
    key.insert(0);
    if (mxx[0] != -INF)//有向东走的人
    {
        int mx = max(mxx[2], mxx[3]);//南北向在x轴的最大定值
        if (mxx[0] < mx)//向东走的人在x轴的最大定值小于南北向在x轴的最大定值，可能超越其成为最大值
            key.insert(mx - mxx[0]);//记录时间点
        mx = mxx[1];//向西走的人在x轴最大定值
        if (mxx[0] < mx)//东西向相向而行直到遇见后导致函数分段时间
            key.insert((mx - mxx[0]) / 2), key.insert((mx - mxx[0] + 1) / 2);//防止小数，多算两个
    }
    if (mnx[1] != INF)
    {
        int mn = min(mnx[2], mnx[3]);
        if (mnx[1] > mn)
            key.insert(mnx[1] - mn);
        mn = mnx[0];
        if (mnx[1] > mn)
            key.insert((mnx[1] - mn) / 2), key.insert((mnx[1] - mn + 1) / 2);
    }
    if (mny[2] != INF)
    {
        int mn = min(mny[0], mny[1]);
        if (mny[2] > mn)
            key.insert(mny[2] - mn);
        mn = mny[3];
        if (mny[2] > mn)
            key.insert((mny[2] - mn) / 2), key.insert((mny[2] - mn + 1) / 2);
    }
    if (mxy[3] != INF)
    {
        int mx = max(mxy[0], mxy[1]);
        if (mxy[3] < mx)
            key.insert(mx - mxy[3]);
        mx = mxy[2];
        if (mxy[3] < mx)
            key.insert((mx - mxy[3]) / 2), key.insert((mx - mxy[3] + 1) / 2);
    }
    int ans = INF;
    for (auto t : key)
    {
        int res = 0, xl = INF, xr = -INF, yl = INF, yr = -INF;
        for (i = 1; i <= n; ++i)
        {
            int tp = trs(ch[i]), nx = x[i] + t * dx[tp], ny = y[i] + t * dy[tp];
            xl = min(xl, nx);
            xr = max(xr, nx);
            yl = min(yl, ny);
            yr = max(yr, ny);
        }
        ans = min(ans, (xr - xl) + (yr - yl));
    }
    return printf("%lld", 2LL * ans), 0;
}

SW-3-10 Bridging the Gap 2

题目信息

个人要过河，每个人初始体力为，只有一条船，每次开船最少要个人，最多限乘个人。每次乘船，船上所有人都会掉一点体力值。询问能否把所有人都载过去。

题目解析

显然摆渡船的过河次数是固定的，考虑最后一发不归之途必定能载过去个人，故进考虑前次摆渡船。

这些次摆渡船必须需要次体力值，且最后回到对岸时这些负责划船的人体力值均不得低于.

考虑枚举所有体力值大于等于的人，如果人数不够，则需要考虑凑人数问题。显然，如果来贡献体力的人是奇数点体力，其可以贡献点体力用于划船，如果是偶数点，其最多贡献点体力值。

枚举人数拼凑，能凑够就能过去。

#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define db double
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define i128 __int128
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define endl '\n'
using namespace std;
//#define int long long
const int maxn=5e5+10;
int h[maxn],a[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,L,R;
    cin>>n>>L>>R;
    int k=(n-R+(R-L-1))/(R-L); //需要从河的右侧往回运送的趟数最小值，注意向上取整
    int ans=0;
    rep(i,1,n){
        cin>>h[i];
        a[i]=(h[i]-1)/2; //每个人最多来回的趟数（最后还得过去）
        ans+=min(a[i],k);
    }
    if(ans>=k*L) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

SW-3-11 Crash Test/Yet Another Origami Problem

两道辗转相减

Case 1. Crash Test

题目信息

一辆车做碰撞试验，一共有种推进器，每种推进器有无限个，第种推进器可以推动车辆移动距离。初始时车距墙距离，如果推进器力量大于当前车到墙的距离，则会发生弹性碰撞，反向移动的距离。给定推进器参数，询问车辆最近离墙多远。

题目解析

取个就行了，谈一谈为什么。

考虑使用和都能生成一些什么东西。

不难发现其一定可以变成一个辗转相减的过程，也就是说，其单位间隙必然是群体

秒了。

Case 2. Yet Another Origami Problem

题目信息

给定一个长度为 的数组 ，你可以执行以下任意次数（可能为零）的操作：

选择一个索引 ，然后执行以下两种操作之一：

  1. 对于所有，如，让。

  2. 对于所有，如，设为。

例如，如果原始数组为 ，选择 并执行操作 1，数组将变为 。

现在，你想通过这些操作最小化数组的范围。回想一下，数组的范围是数组中最大元素和最小元素之差。

题目解析

显然最优的是折中翻。翻两次就会发现辗转相减的过程，然后就又变成了。

不同的是，这个是间隙的。

SW-3-11 Sort4

题目信息

给定一个长度为的排列。在一次操作中，你可以从排列中选择最多4个元素，并任意交换它们的位置。按升序排列该排列所需的最少操作次数是多少？

题目解析

又是高等代数题。

排列可拆成不相交循环的乘积。

显然，如果某个不相交循环是一个对换，那么可以将两个对换组合起来。

如果是一个大小为、的不相交循环，其直接使用​次交换就可以了。

如果不相交循环大小大于等于就有一点问题了。手动模拟发现每次从中选择出来个元素，最多只能归位个。那就计数其需要几次个。如果剩余元素为个（形成对换），参与对换组合计数。如果剩余元素为个，不好意思，这一个会自动归位（相当于拆成了一个大小为4的不相交循环）

SW-3-12 Good Tree

题目信息

构造一个满足以下要求的树最少需要多少个节点？ 其中

题目解析

显然构造一颗蒲公英菊花图（一个菊花图，中心点再接一条直链）是最优的，不难算出主链个节点，附带个菊花节点的最大为。二分加均值不等式求出最小节点数。

这里要注意一个特殊判定，如果为奇数，那么有可能是奇数，而每拔插一个节点至少变化，可能到不了。这时候需要在主链上配平一个节点在，总结点数要加.

SW-S-1 梦中的地牢战斗

题目信息

一个的方格地图，有个怪兽分别位于个方格之中。第个怪兽位于，具有金币价值，其攻击距离为，单次伤害。初始时位于，每次可以向所在行或列强制位移到距自己不超过的距离的没有怪兽的方格，并斩杀路径上所有怪兽，获得对应怪兽的全部金币。不可以选择落脚在路径斩杀前有怪兽的方格，强制位移期间无敌。位移到目标点后，如果在第个怪兽的曼哈顿攻击距离之内，会受到一次伤害。初始时不受伤害。每受一点伤害，都要花费​金币疗伤。问最多能获得多少金币。

保证

题目解析

分层图最长路，和骑士游戏逻辑很像。

因为很小，将其状态压缩表示怪兽的击败状态，那么每一次位移时选择的方式就是。

对于每一个点，尝试十字架形态移动，如果路径有击败怪兽，就转向下一张状态图；否则在本层图中拓补，容易发现对于分层图之间必然是正边（击败怪兽必然有奖励），分层图之间必然只有负边和负权环（没奖励还可能被倒扣金币），且没有高层图像底层图的边（击败了的怪兽不可能再复活）

对于可能的环所造成的后效性拓补，采用最短路思想即可。注意，此处我们寻找的是最长路，无需考虑负权环的影响，直接寻找最长路即可。

时间复杂度：​

#include <bits/stdc++.h>
using namespace std;
//#define DEBUG 1
#define cout std::cout
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m, k, sx, sy;
struct monster
{
    int x, y, a, b, c;
} mon[15];
int maxd;
int graph[35][35];
const int INF = 0x3f3f3f3f;
int dp[35][35][(1 << 10) + 5];
int cost[35][35][(1 << 10) + 5];
int B;
int dist(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}
int ans = 0;
int dir[4][2] = <!--swig1-->;
void Dijkstra_like_dp(int b)
{
#ifdef DEBUG
    cout << "now dp at level " << b << endl;
#endif
    priority_queue<tuple<int, int, int>> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (dp[i][j][b] > -INF)
            {
                q.push({dp[i][j][b], i, j});
            }
        }
    vector<vector<bool>> vis(n + 1, vector<bool>(m + 1, false));
#ifdef DEBUG
    cout << "q size is " << q.size() << endl;
#endif
    while (!q.empty())
    {
        auto [dps, x, y] = q.top();
#ifdef DEBUG
        cout << "now at " << x << " " << y << " with dps " << dps << endl;
#endif
        q.pop();
        if (vis[x][y])
            continue;
        vis[x][y] = true;
        ans = max(ans, dps);
        for (int p = 0; p < 4; p++)
        {
            int status = 0, val = 0;
            for (int d = 1; d <= maxd; d++)
            {
                int nowx = x + dir[p][0] * d, nowy = y + dir[p][1] * d;
                if (nowx < 1 || nowx > n || nowy < 1 || nowy > m)
                    break;
#ifdef DEBUG
                cout << "now at " << nowx << " " << nowy << " with d " << d << endl;
#endif
                if (graph[nowx][nowy] < k && !((b >> graph[nowx][nowy]) & 1)) // 路径上有怪兽并且未消灭
                {
#ifdef DEBUG
                    cout << "kill monster " << graph[nowx][nowy] << endl;
#endif
                    status |= (1 << graph[nowx][nowy]);
                    val += mon[graph[nowx][nowy]].a;
#ifdef DEBUG
                    cout << "status afterkill " << bitset<10>(status) << endl;
                    cout << "val now " << val << endl;
                    cout << "nowpos used to have a monster,cannot stop" << endl;
#endif
                }
                else if (status == 0) // 路径上没怪兽，图层间最长路dp
                {
#ifdef DEBUG
                    cout << "up to now meets no monsters" << endl;
#endif
                    if (dp[nowx][nowy][b] < dps - cost[nowx][nowy][b])
                    {
                        dp[nowx][nowy][b] = dps - cost[nowx][nowy][b];
                        q.push({dp[nowx][nowy][b], nowx, nowy});
#ifdef DEBUG
                        cout << "have good choices,update dp" << endl;
                        cout << "dp[" << nowx << "][" << nowy << "][" << (bitset<10>(b)) << "]=" << dp[nowx][nowy][b] << endl;
#endif
                    }
                }
                else // 路径上已经击杀目标，向下一层转移
                {
#ifdef DEBUG
                    cout << "nowpos don't to have a monster,can stop" << endl;
                    cout << "have killed monsters" << endl;
#endif
                    if (dp[nowx][nowy][b | status] < dps - cost[nowx][nowy][b | status] + val)
                    {
                        dp[nowx][nowy][b | status] = dps - cost[nowx][nowy][b | status] + val;
#ifdef DEBUG
                        cout << "dp[" << nowx << "][" << nowy << "][" << (bitset<10>(b | status)) << "]=" << dp[nowx][nowy][b | status] << endl;
#endif
                    }
                }
            }
        }
    }
    return;
}
void solve()
{
    cin >> n >> m >> k;
    B = (1 << k);
    cin >> maxd;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            graph[i][j] = k + 1;
        }
    for (int i = 0; i < k; i++)
        cin >> mon[i].x >> mon[i].y >> mon[i].a >> mon[i].b >> mon[i].c, graph[mon[i].x][mon[i].y] = i;
#ifdef DEBUG
    cout << "graph init" << endl;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
#endif
    for (int i = 0; i < B; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int w = 1; w <= m; w++)
            {
                dp[j][w][i] = -INF;
                cost[j][w][i] = 0;
                for (int t = 0; t < k; t++)
                {
                    if (((i >> t) & 1) == 0) // 未击杀
                    {
#ifdef DEBUG
                        cout << "monster " << t << " not killed" << endl;
                        cout << "dist=" << dist(j, w, mon[t].x, mon[t].y) << endl;
#endif
                        if (dist(j, w, mon[t].x, mon[t].y) <= mon[t].c)
                        {
#ifdef DEBUG
                            //cout << "monster " << t << " add" << endl;
#endif
                            cost[j][w][i] += mon[t].b;
                            //cout << "now cost[" << j << "][" << w << "][" << (bitset<10>(i)) << "]=" << cost[j][w][i] << endl;
                        }
                    }
                }
#ifdef DEBUG
                cout << "cost[" << j << "][" << w << "][" << (bitset<10>(i)) << "]=" << cost[j][w][i] << endl;
#endif
            }
        }
    }
    cin >> sx >> sy;
    dp[sx][sy][0] = 0;
#ifdef DEBUG
    cout << "dp init" << endl;
    cout << "pos is " << sx << " " << sy << endl;
#endif
    ans = 0;
    for (int i = 0; i < B; i++)
    {
        Dijkstra_like_dp(i);
    }
    cout << ans << endl;
}
signed main()
{
    //freopen("10021.in", "r", stdin);
    //freopen("10021.out", "w", stdout);
    IOS;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

SW-S-2 Linear Kingdom Races/Pillars/Subsequences/旅行

数据结构优化学习

Case 1. Linear Kingdom Races

题目信息

有条损坏的道路，第条的修复费用为，有组织期望在此处举办场比赛，第场比赛需要使用连续的的道路，只有这些道路都修复好了后道路才能举办比赛，并收入.请问你可以获得的最大利润。请注意，你可以选择不修缮任何道路，然后获得利润。

题目解析

考虑一个的做法，枚举表示只修缮中的若干条道路所能获得的最大利润，则有以下转移方程 这里表示修缮区间所有道路的花费，表示在这段道路区间举办比赛的收益。

做法显然是一个的，对这个题的数据范围并不友善。

注意到范围取，考虑使用线段树优化。

如果考虑到，那么先对前面所有的值进行一次区间修改，表示要修缮本条道路。

然后遍历以为终点的比赛，设某个比赛区间为，则所有的均需叠加一次本次举办比赛的利润，因为已经成功的修复了区间所有道路。

最后和取，更新​。

涉及单点修改和区间查询，把所有的直接扔到线段树里面维护起来就行了。

// 线段树优化dp方程转移
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
const int maxn = 3e5 + 9;
struct node
{
    int l, r;
    int max = 0;
    int lazy = 0;
};
node tree[maxn << 2LL];
int n, m;
int costs[maxn];
vector<pair<int, int>> mp[maxn];
int f[maxn];
void pushup(int p)
{
    tree[p].max = max(tree[p << 1LL].max, tree[p << 1LL | 1].max);
}
void pushdown(int p)
{
    if (tree[p].lazy)
    {
        tree[p << 1LL].max += tree[p].lazy;
        tree[p << 1LL].lazy += tree[p].lazy;
        tree[p << 1LL | 1].max += tree[p].lazy;
        tree[p << 1LL | 1].lazy += tree[p].lazy;
        tree[p].lazy = 0;
    }
}
void modify(int l, int r, int d, int p = 1, int cl = 0, int cr = n)
{
    if (cl > cr || r < cl || cr < l)
        return;
    if (cl >= l && cr <= r)
    {
        tree[p].max += d;
        tree[p].lazy += d;
        return;
    }
    pushdown(p);
    int mid = (cl + cr) >> 1LL;
    modify(l, r, d, p << 1LL, cl, mid);
    modify(l, r, d, p << 1LL | 1, mid + 1, cr);
    pushup(p);
}
int query(int l, int r, int p = 1, int cl = 0, int cr = n)
{
    if (cl > cr || r < cl || cr < l)
        return 0;
    if (cl >= l && cr <= r)
        return tree[p].max;
    pushdown(p);
    int mid = (cl + cr) >> 1LL;
    return max(query(l, r, p << 1LL, cl, mid), query(l, r, p << 1LL | 1, mid + 1, cr));
}
signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> costs[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int l, r, w;
        cin >> l >> r >> w;
        mp[r].push_back({l, w});
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1];
        modify(0, i - 1, -costs[i]);
        for (auto [l, w] : mp[i])
        {
            modify(0, l - 1, w);
        }
        f[i] = max(f[i], query(0, i - 1));
        modify(i, i, f[i]);
    }
    cout << f[n] << endl;
    return 0;
}

Case 2. Pillars

题目信息

土拨鼠发现了一排有根石柱。第 根柱子的高度为 米。从一根柱子 开始，旱獭想要跳到柱子 、、、上。( ).从柱子 出发跳跃到，当且仅当有和 .

找出一个最大长度的跳跃序列并打印出来。

题目解析

有点像的思路，考虑的思想。

则显然有 暴力又是一个的，难以接受。

注意到又是在维护区间的,考虑线段树维护。那就显而易见的可以发现将作为线段树的下标，每次查询两个解集区间的最大值然后赋给，然后再插入线段树。这样可以自动维护的过程。

对离散化后上普通线段树模板就行了。这个题有一个细节就是不用线段树建树初始化，因为出发的第一跳一定是从高度为的号桩子跳来。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
int n, d;
const int maxn = 1e5 + 9;
const int INF = 1e18;
int h[maxn], a[maxn], rankh[maxn], dp[maxn], pre[maxn];
struct node
{
    int l, r, maxx, maxpos;
} trees[maxn << 2LL];
void pushup(int rt)
{
    trees[rt].maxx = max(trees[rt << 1LL].maxx, trees[rt << 1LL | 1LL].maxx);
    trees[rt].maxpos = trees[rt << 1LL].maxx > trees[rt << 1LL | 1LL].maxx ? trees[rt << 1LL].maxpos : trees[rt << 1LL | 1LL].maxpos;
}
void modifypoints(int pos, int maxposs, int x, int rt = 1, int cl = 1, int cr = n)
{
    if (cl == cr)
    {
        trees[rt].maxx = x;
        trees[rt].maxpos = maxposs;
        return;
    }
    int mid = (cl + cr) >> 1LL;
    if (pos <= mid)
        modifypoints(pos, maxposs, x, rt << 1LL, cl, mid);
    else
        modifypoints(pos, maxposs, x, rt << 1LL | 1LL, mid + 1, cr);
    pushup(rt);
}
pair<int, int> querymax(int l, int r, int p = 1, int cl = 1, int cr = n)
{
    if (l > r)
        return {-INF, -INF};
    if (cl > cr || l > cr || r < cl)
        return {-INF, -INF};
    if (l <= cl && cr <= r)
        return {trees[p].maxx, trees[p].maxpos};
    int mid = (cl + cr) >> 1LL;
    pair<int, int> ans1 = querymax(l, r, p << 1LL, cl, mid);
    pair<int, int> ans2 = querymax(l, r, p << 1LL | 1LL, mid + 1, cr);
    return ans1.first > ans2.first ? ans1 : ans2;
}
signed main()
{
    IOS;
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
        cin >> h[i], a[i] = h[i];
    sort(a + 1, a + 1 + n);
    int len = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n; i++)
        rankh[i] = lower_bound(a + 1, a + 1 + len, h[i]) - a;
    for (int i = 1; i <= n; i++)
    {
        int l = upper_bound(a + 1, a + 1 + len, h[i] - d) - a - 1;
        int r = lower_bound(a + 1, a + 1 + len, h[i] + d) - a;
        pair<int, int> ans1 = querymax(1, l);
        pair<int, int> ans2 = querymax(r, len);
        if (ans1.first > ans2.first)
            dp[i] = ans1.first + 1, pre[i] = ans1.second;
        else
            dp[i] = ans2.first + 1, pre[i] = ans2.second;
        modifypoints(rankh[i], i, dp[i]);
    }
    int pos = max_element(dp + 1, dp + 1 + n) - dp;
    cout << dp[pos] << endl;
    vector<int> ans;
    while (pos)
        ans.push_back(pos), pos = pre[pos];
    reverse(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

Case 3. Subsequences

题目信息

对于给定的具有 个不同元素的序列，求具有 个元素的递增子序列的个数。保证答案不大于

题目解析

和上一题类似，也是很像的一道题。

显然有转移方程 区间和的过程维护，线段树操作即可。

对于的维护，一样选择将其作为线段树的下标。

这个题需要开多个线段树，并且因为要维护，必须所有线段树同时建树，并且对于每一个点同时操作完多个线段树。

话说回来，动态开点线段树在这方面真是过于外挂了，简介、码量小，并且内存利用率极高。

#include <bits/stdc++.h>
using namespace std;
//#define DEBUG 1
#define int long long
struct node
{
    int sum, l, r, lazys;
};
const int maxn = 4e5+10;
node tree[maxn << 3];
int cnt = 0;
int roots[15];
int a[maxn], dp[maxn], test[maxn];
int n, k;
void build(int &p, int cl, int cr, int *a)
{
    if (!p)
        p = ++cnt;
    if (cl == cr)
    {
        tree[p].sum = a[cl];
        return;
    }
    int mid = (cl + cr) >> 1LL;
    build(tree[p].l, cl, mid, a);
    build(tree[p].r, mid + 1, cr, a);
    tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum;
}
void modify(int &p, int l, int r, int d, int cl, int cr)
{
    if (l > r)
        return;
    if (cl > cr || r < cl || cr < l)
        return;
    if (!p)
        p = ++cnt;
    tree[p].sum += d * (min(r, cr) - max(l, cl) + 1);
    if (cl >= l && cr <= r)
    {
        tree[p].lazys += d;
        return;
    }
    int mid = (cl + cr) >> 1LL;
    modify(tree[p].l, l, r, d, cl, mid);
    modify(tree[p].r, l, r, d, mid + 1, cr);
    return;
}
void modifypoints(int &p, int pos, int d, int cl, int cr)
{
    if (!p)
        p = ++cnt;
    tree[p].sum += d;
    if (cl == cr)
        return;
    int mid = (cl + cr) >> 1LL;
    if (pos <= mid)
        modifypoints(tree[p].l, pos, d, cl, mid);
    else
        modifypoints(tree[p].r, pos, d, mid + 1, cr);
}
int query(int p, int l, int r, int cl, int cr, int lazy)
{
    if (l > r)
        return 0;
    if (cl > cr || r < cl || cr < l)
        return 0;
    if (!p)
        return 0;
    if (cl >= l && cr <= r)
        return tree[p].sum + lazy * (cr - cl + 1);
    int mid = (cl + cr) >> 1LL;
    return query(tree[p].l, l, r, cl, mid, lazy + tree[p].lazys) + query(tree[p].r, l, r, mid + 1, cr, lazy + tree[p].lazys);
}
signed main()
{
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i], test[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        modifypoints(roots[1], a[i], 1, 1, n);
        for (int j = 2; j <= min(k + 1, i); j++)
        {
            dp[i] = query(roots[j - 1], 1, a[i] - 1, 1, n, 0);
            modifypoints(roots[j], a[i], dp[i], 1, n);
        }
    }
    cout << query(roots[k + 1], 1, n, 1, n, 0) << endl;
    //system("pause");
    return 0;
}

Case 4. 旅行

题目信息

有一棵个结点，种节点类型的无根树，每个结点都有对应的类型和权重，你需要在这棵树上规划若干次旅行。

对于一次旅行，你将从一个树上的一个结点出发，沿着树上的边进行旅行，最终到达另一个和起点类型相同的结点。

你会进行很多次旅行，但你希望对于每个结点，在所有旅行路线中最多只会经过一次。

一次旅行的价值是起始点和终止点的权重和，你需要规划旅行的方案使得旅行的总权重和最大。

题目解析

赛时就有想到开树上转移，但是不会实现。

考虑子树问题。如果存在一个子树，那么如果子树的根未参与到任何的路径权值计算当中去，则当前子树下最大的权重就是子节点的所有权重和。而如果子树的根参与到路径之中，就需要计算儿子群体所提供的具有上传路径效果的权重和。

记某个节点的表示该节点为根的子树内部不提供不完整路径的最大权值和，为该节点内部子树提供了一条经过的不完整路径，且该路径的起点为颜色的最大权重和。

则显然有以下方程 而对于的更新，显然也有

考虑如何维护。显然的维护交给线段树合并就可以了，以颜色为下标，动态开点的合并线段树并不难实现。

对于总方程，记，则不难发现有​

依旧是线段树合并的时候顺手就可以维护了这一个操作。

#include <bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
int head[N], tot, c[N], v[N];
int L[N * 32], R[N * 32];
ll tr[N * 32], la[N * 32];
int top, n, T[N];
ll dp[N], sm;
int vi[N];
struct edge
{
    int n, to;
} e[N << 1];
inline void add(int u, int v)
{
    e[++tot].n = head[u];
    e[tot].to = v;
    head[u] = tot;
}
void pushd(int u)
{
    if (L[u])
        tr[L[u]] += la[u], la[L[u]] += la[u];
    if (R[u])
        tr[R[u]] += la[u], la[R[u]] += la[u];
    la[u] = 0;
}
int merge(int u, int v, int l, int r, ll &ans)
{
    if (!u || !v)
        return u + v;
    if (l == r)
        ans = max(ans, tr[u] + tr[v] + sm);
    pushd(u);
    pushd(v);
    int mid = (l + r) >> 1;
    tr[u] = max(tr[u], tr[v]);
    L[u] = merge(L[u], L[v], l, mid, ans);
    R[u] = merge(R[u], R[v], mid + 1, r, ans);
    return u;
}
void upd(int &u, int l, int r, int x, ll y)
{
    if (!u)
        u = ++top;
    tr[u] = y;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (x <= mid)
        upd(L[u], l, mid, x, y);
    else
        upd(R[u], mid + 1, r, x, y);
}
void dfs(int u, int fa)
{
    ll sum = 0;
    vi[u] = 1;
    for (int i = head[u]; i; i = e[i].n)
        if (e[i].to != fa)
        {
            int v = e[i].to;
            dfs(v, u);
            sum += dp[v];
        }
    dp[u] = sum;
    sm = sum;
    upd(T[u], 1, n, c[u], v[u]);
    for (int i = head[u]; i; i = e[i].n)
        if (e[i].to != fa)
        {
            int v = e[i].to;
            tr[T[v]] -= dp[v];
            la[T[v]] -= dp[v];
            T[u] = merge(T[u], T[v], 1, n, dp[u]);
        }
    tr[T[u]] += sm;
    la[T[u]] += sm;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TT;
    cin >> TT;
    while (TT--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> c[i];
        }
        for (int i = 1; i <= n; ++i)
        {
            cin >> v[i];
        }
        int u, v;
        for (int i = 1; i < n; ++i)
        {
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }

        dfs(1, 0);
        cout << dp[1] << endl;
        for (int i = 0; i <= top; ++i)
        {
            L[i] = R[i] = tr[i] = la[i] = 0;
        }
        tot = top = 0;
        for (int i = 0; i <= n; ++i)
        {
            head[i] = T[i] = dp[i] = 0;
        }
    }
    return 0;
}

SW-S-3 Zero/Decode/Malfunctioning Typewriter

把三个挺有意思的放到一起来看

Case 1.Zero

题目信息

给定一个长度为的只包含的字符串，下标从开始。可以等概率的被视作或。定义随机变量的值为，否则为。

求整个字符串的期望

题目解析

考虑枚举结尾点。

设表示以为结尾的字符串期望值。则有 考虑递推关系。如果，那么意味着这一点必然不连续有，故有

如果，那么则必然有

表示以为结尾的后缀连续字符串的长度

故 记，对其二项式展开有 此处先只讨论​的递推情形。

记，则 此时发现所有概率项均被消去，可以实现递推。问题只会在时引发，但也非常好解决，如果对应位置是，则所有公式全部乘即可。

#include<bits/stdc++.h>
typedef long long ll;
const ll mod = 998244353, inv = (mod+1) / 2;
const int N = 1e5+999;
ll f[N], g[N], C[55][55], len[N][33];
int n, k;
char s[N];
void init(){
    C[0][0] = 1;
    for(int i = 1; i <= 30; i++){
        C[i][0] = 1;
        for(int j = 1; j <= 30; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
    }
}
int main(){
    init();
    scanf("%d %d", &n, &k);
    scanf("%s", s+1);
    len[0][0] = 1;
    for(int i = 1; i <= n; i++){
        ll p;
        if(s[i] == '0') p = 0;
        else if(s[i] == '1') p = 1;
        else p = inv;
        for(int j = 0; j <= k; j++)
            for(int t = 0; t <= j; t++)
                len[i][j] = (len[i][j] + C[j][t] * len[i-1][t]) % mod;
        g[i] = g[i-1] + len[i][k];
        g[i] = g[i] * p % mod;        
        for(int j = 1; j <= k; j++)
            len[i][j] = len[i][j] * p % mod;
        f[i] = (f[i-1] + g[i]) % mod;       
    }
    printf("%lld\n", f[n]);
}

Case 2.Decode

题目信息

给定一个二进制串，长度，定义，此处的表示为的子串，即子串中的数量等于的数量。

求

题目解析

注意到只需枚举决定意义的串，将贡献分成两块计算。（因为一个串的贡献为)

设表示以为结尾的位置形成的符合要求的串的前半贡献，则有

，​

逐项递推就行，因为这样可以把所有符合要求的字符串按照前缀压缩到后缀的方式前缀和起来，这样就可以统一计算了。

Case 3.Malfunctioning Typewriter

题目信息

给定个长度为的字符串，现在要将其打印到纸上。有一台故障的打印机，其能正确打印你想要的字符的概率为，求最优条件下你能正确打印出这些诗句的最大概率。

题目解析

挺有意思的一道题。关键在于转移方程怎么想。

想要最大可能的概率打印出诗句，就要尽可能的混着打印。显然因为打印的目标不同，概率也会变化。而且，拥有相同前缀的字符要尽可能的放到一起打印。

考虑到逐字符列打印，则一次考虑要打印个，个.

显然有转移方程 这里有一个点，必须把想打字符但打错了也算上，因为可能之前的概率高。

关于维护相同前缀的一起打印，建个就可以了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6+10;
const int maxnn = 2e3+10;
int cnt = 0, trie[maxn][2], sizes[maxn];
int n, m;
double dp[maxnn][maxnn];
double P;
void insert(string t)
{
    int p = 0;
    for (int i = 0; i < t.size(); i++)
    {
        int c = t[i] - '0';
        if (!trie[p][c])
        {
            trie[p][c] = ++cnt;
            trie[cnt][0] = trie[cnt][1] = 0;
            sizes[cnt] = 0;
        }
        p = trie[p][c];
        sizes[p]++;
    }
    return;
}
void initdp()
{
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0] * (P);
        dp[0][i] = dp[0][i - 1] * (P);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = max(dp[i - 1][j] * P + dp[i][j - 1] * (1 - P), dp[i][j - 1] * P + dp[i - 1][j] * (1 - P));
        }
    return;
}
double ans = 1.0;
double calcall(int pos)
{
    double res = dp[sizes[trie[pos][0]]][sizes[trie[pos][1]]];
    if (trie[pos][0])
        res *= calcall(trie[pos][0]);
    if (trie[pos][1])
        res *= calcall(trie[pos][1]);
    return res;
}
void solve()
{
    cin >> n >> m >> P;
    trie[0][0] = trie[0][1] = 0;
    sizes[0] = 0;
    cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        string t;
        cin >> t;
        insert(t);
    }
    initdp();
    ans = calcall(0);
    cout << fixed << setprecision(12) << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

SW-S-4 游戏

多项式相关，下周再看

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 栾博越
  • 访问人数: | 浏览次数:

      请我喝杯咖啡吧~

      支付宝
      微信