首页 笔记 思维题

小思维题做题记录

(经过一天的小清新题的洗礼，感觉整个人的都可以入土了) 小清新题给人的第一感觉，哇！这题干好短啊，也没太多的要维护的东西，这题肯定很简单吧。理解完题意后发现，什么抽象题，根本没思路，(使用跳题 dp)。虽然写完了 zzz 学长上课讲的那些题，感觉做小清新题的时候还是有思路但不多，正好今天写不下去题了，就来稍微整理一下。

# 例题一：

# Number of Components

# 题面翻译

有一条n(1≤n≤105)n(1 \leq n \leq 10^5) 个节点的链，编号相邻节点有边，每个点一个权值ai(1≤ai≤n)a_i(1 \leq a_i \leq n)，f(l,r)f(l,r) 定义为权值在[l,r][l,r] 的点中的连通块数量求∑l=1n∑r=lnf(l,r)\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)

# 分析：

首先对于这个题，我们第一眼就有一个非常暴力的做法，那就是直接暴力美剧每个权值区间，然后在暴力查一遍所有的连通块，这显然是过不去的。我们考虑怎么去优化，首先有一个学过图论的人都知道一个公式，那就是点数 −- 边数 == 联通块的数量，那么我们现在就转换成了如何快速求点数和边数，我们可以先单独考虑每个点的贡献，对于每一个点，他的贡献显然是 a[i]×(n−a[i]+1)a[i] \times (n-a[i] + 1)，只有 L≥a[i]L \geq a[i] 并且 R≤(n−a[i]+1)R \leq (n - a[i] + 1) 中，这个点才会被选中。我们再接着来看边的情况，对于一条边，他的左右端点为 uu 和 vv，那么根据点的关系，我们可以推出边的贡献为 min⁡(a[u],a[v])×(n−max⁡(a[u],a[v])+1)\min(a[u], a[v]) \times (n - \max(a[u], a[v]) + 1)，因为我们要保证区间的左端点是小于等于最小的那个值，右端点要在最大的值的右边，既然我们都算出了点和边的贡献，我们也就可以把这道题给切了。(我记得是得开 long long ，要不然会爆掉)

#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
            while (ch >= '0' && ch <= '9')
                x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    const int N = 1e6 + 10;
    int n;
    int a[N], sum1, sum2;
    void solve()
    {
        read(n);
        for(int i = 1 ; i <= n ; ++ i)
            read(a[i]);
        for(int i = 1 ; i <= n ; ++ i)
        { 
            sum1 += a[i] * (n - a[i] + 1);   // 计算所有的点的贡献
            if(i == n)
                continue;
            sum2 += min(a[i], a[i + 1]) * (n - max(a[i], a[i + 1]) + 1);  // 计算所有的边的贡献
        }
        write(sum1 - sum2);
    }
}
signed main()
{
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    Solve::solve();
    return 0;
}
# 例题二：
# 赛车游戏
# 题目描述
R 君和小伙伴打算一起玩赛车。但他们被老司机 mocania 骗去了秋名山。
秋名山上有 nn 个点和 mm 条边，R 君和他的小伙伴要从点 11 出发开往点 nn，每条边都有一个初始的方向。老司机 mocania 拿到了秋名山的地图但却不知道每条路有多长。显然，为了赛车游戏的公平，每条 11 到 nn 的路径应当是等长的。mocania 想，我就随便给边标上一个 1...91...9 的长度，反正傻傻的 R 君也看不出来。
可 mocania 的数学不大好，不知道怎么给边标长度，只能跑来请教你这个 OI 高手了。
# 输入格式
第一行两个整数 n,mn,m。
接下来 mm 行，每行两个整数 u,vu,v，表示一条从 uu 到 vv 的有向边。
# 输出格式
如果无解或者不存在 11 到 nn 的路径直接输出一个 −1-1。
如果有解第一行输出两个数 n,mn,m，和输入文件中给出的相同。
借下来 mm 行，每行三个整数 u,v,wu,v,w，表示把从 uu 到 vv 的路径的长度设置为 ww，其中 ww 是一个 1∼91\sim 9 的整数。要求所有边的出现顺序和题目中给出的相同。
# 分析：
首先，题干说的是要求 11 到 nn 的所有路径都是相同长度的，那么对于路径外的边我们随便设即可，同时我们观察到题干中对于边的长度给出了限制，长度都在 11 到 99 之间，我们设 dis[i]dis[i] 为 11 到 ii 的距离，然后我们会发现，对于一条边连接 uu 和 vv，都必须要满足 1≤dis[u]−dis[v]≤91 \leq dis[u] - dis[v] \leq 9，然后我们移一下项之后会发现这就是个差分约束系统，那么我们直接跑 spfaspfa 判断一下有没有负环，最后在输出一下合法边权就行了。有一个小细节就是直接跑 spfaspfa 好像跑不过去，那么我们可以正着跑一次，反着跑一次，处理出来在路径上的边，然后建个新图，在新图上跑 spfaspfa。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
            while (ch >= '0' && ch <= '9')
                x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    const int N = 1e6 + 10, INF = 0x3f3f3f3f;
    int n, m, times[N], dis[N];
    int post[N], rev[N], h[N], cnt, idx;
    bool st1[N], st2[N], st[N], vis[N];
    struct Edge
    {
        int ne, v, w;
        int rev_ne, rev_v;
    } e[N];
    struct Line
    {
        int x, y;
    } line[N];
    void add(int u, int v)
    {
        e[++ cnt].v = v, e[cnt].ne = post[u], post[u] = cnt;
        e[cnt].rev_ne = rev[v], e[cnt].rev_v = u, rev[v] = cnt;
    }
    void add(int u, int v, int w)
    {
        e[++ idx].v = v, e[idx].w = w, e[idx].ne = h[u], h[u] = idx;
    }
    inline void dfs1(int x)   // 正着跑
    {
        st1[x] = true;
        for(int i = post[x] ; i ; i = e[i].ne)
        {
            int v = e[i].v;
            if(!st1[v])
                dfs1(v);
        }
    }
    inline void dfs2(int x)   // 反着跑
    {
        st2[x] = true;
        for(int i = rev[x] ; i ; i = e[i].rev_ne)
        {
            int v = e[i].rev_v;
            if(!st2[v])
                dfs2(v);
        }
    }
    void spfa()
    {
        std::queue<int> q;
        //memset(dis, INF, sizeof(dis));
        q.push(1), vis[1] = true, dis[1] = 0, times[1] = 1;
        while(!q.empty())
        {
            int t = q.front();
            q.pop(), vis[t] = false;
            for(int i = h[t] ; i ; i = e[i].ne)
            {
                int v = e[i].v;
                if(dis[v] > dis[t] + e[i].w)
                {
                    dis[v] = dis[t] + e[i].w;
                    if(!vis[v])
                    {
                        if(times[v] == n)
                        {
                            puts("-1");
                            exit(0);
                        }
                        
                        q.push(v), vis[v] = true;
                        ++ times[v];
                    }
                }
            }
        }
        if(dis[n] == INF)
        {
            puts("-1");
            exit(0);
        }
    }
    void solve()
    {
        read(n), read(m);
        for(int i = 1 ; i <= m ; ++ i)
        {
            int x, y;
            read(x), read(y);
            add(x, y);
            line[i] = {x, y};
        }
        dfs1(1), dfs2(n);
        for(int i = 1 ; i <= n ; ++ i)
            st[i] = st1[i] & st2[i], dis[i] = INF;
        idx = 0;
        for(int i = 1 ; i <= m ; ++ i)
        {
            if(st[line[i].x] && st[line[i].y])
                add(line[i].x, line[i].y, 9), add(line[i].y, line[i].x, -1);
        }
        spfa();
        write(n), putchar(' '), write(m), puts("");
        for(int i = 1 ; i <= m ; ++ i)
        {
            write(line[i].x), putchar(' '), write(line[i].y), putchar(' ');
            if(!st[line[i].x] || !st[line[i].y])
                write(1);
            else 
                write(dis[line[i].y] - dis[line[i].x]);
            puts("");
        }
    }
}
int main()
{
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    Solve::solve();
    return 0;
}
# 例题三
# Kay and Snowflake
# 题面翻译
输入一棵树，判断每一棵子树的重心是哪一个节点.
# 分析：
首先对于每次询问我们都暴力的求一遍，复杂度是非常高的，然后我们得考虑一些更快速的求子树的重心的方法，我们都知道重心的定义，然后我们结合定义就可以差不多有一个猜想，就是假如当前我们从一个节点推他子树的重心，那么重心应该是在这个点到他的重儿子的路径上，为什么因为如果当前节点不是重心，你往轻儿子走只会让答案变的更劣，一直往重儿子走才行，那么这道题想到这里也就差不多切了。
#include <cstring>
#include <iostream>
#include <algorithm>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
            while (ch >= '0' && ch <= '9')
                x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    const int N = 1e6 + 10;
    int n, m;
    int h[N], siz[N], idx;
    int fa[N], max_siz[N], ans[N];
    struct Edge
    {
        int ne, v;
    } e[N];
    void add(int u, int v)
    {
        e[++ idx].v = v, e[idx].ne = h[u], h[u] = idx;
    }
    void dfs(int u, int fath)
    {
        int mx = 0, id = 0;
        siz[u] = 1, fa[u] = fath;
        for(int i = h[u] ; i ; i = e[i].ne)
        {
            int v = e[i].v;
            if(v == fath)
                continue;
            dfs(v, u);
            siz[u] += siz[v];
            if(siz[v] > mx)
                mx = siz[v], id = v;
        }
        max_siz[u] = mx;
        if(max_siz[u] * 2 < siz[u])
            ans[u] = u;
        else 
        {
            int pos = ans[id];
            while(fa[pos] && max(max_siz[pos], siz[u] - siz[pos]) > max(max_siz[fa[pos]], siz[u] - siz[fa[pos]]))
                pos = fa[pos];
            ans[u] = pos;
        }
    }
    void solve()
    {
        read(n), read(m);
        for(int i = 2 ; i <= n ; ++ i)
        {
            int x;
            read(x);
            add(x, i);
        }
        dfs(1, 0);
        while(m --)
        {
            int x;
            read(x);
            write(ans[x]), puts("");
        }
    }
}
int main()
{
    Solve::solve();
    return 0;
}
# 例题四
# Complicated Computations
# 题面翻译
求一个数列的所有连续子数列的 mex 值的 mex（mex：对于一个序列，这个序列中没出现的最小的正整数）
# 分析
我们手模一下第二个样例，（因为第一个样例实在是太弱了！！！）我们如果当前点的值为 a[i]a[i]，那么 a[i]a[i] 能成为 mexmex 的位置就只有所有值为 a[i]a[i] 的位置，然后我们就依次递推，枚举 mexmex 要是没有有个位置没有，那么我们就直接输出这个 mexmex 即可，对于给位置上加数，我们可以整个主席树来维护。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
            while (ch >= '0' && ch <= '9')
                x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    const int N = 1e6 + 10;
    int n, m, cnt;
    int a[N], rt[N], idx;
    std::vector<int> col[N];
    bool st[N];
    struct Question
    {
        int l, r, val;
        bool operator < (const Question&a) const {return r < a.r;}
    } q[N];
    void New(int l, int r, int w)
    {
        if(l > r)
            return ;
        q[++ idx].l = l, q[idx].r = r, q[idx].val = w;
    }
    struct Tree
    {
        int l, r, val;
    } tr[N << 1];
    void pushup(int u)
    {
        tr[u].val = min(tr[tr[u].l].val, tr[tr[u].r].val);
    }
    void insert(int &u, int last, int l, int r, int p, int k)
    {
        u = ++ cnt;
        tr[u] = tr[last];
        if(l == r)
        {
            tr[u].val = k;
            return ;
        }
        int mid = l + r >> 1;
        if(p <= mid)
            insert(tr[u].l, tr[last].l, l, mid, p, k);
        else 
            insert(tr[u].r, tr[last].r, mid + 1, r, p, k);
        pushup(u);
    }
    int query(int u, int l, int r, int k)
    {
        if(l == r)
            return l;
        int mid = l + r >> 1;
        if(tr[tr[u].l].val < k)
            return query(tr[u].l, l, mid, k);
        else 
            return query(tr[u].r, mid + 1, r, k);
    }
    void solve()
    {
        read(n);
        for(int i = 1 ; i <= n ; ++ i)
            read(a[i]), col[a[i]].push_back(i);
        for(int i = 1 ; i <= n ; ++ i)
        {
            for(int j = 0 ; j < col[i].size() ; ++ j)
            {
                if(j == 0)
                    New(1, col[i][j] - 1, i);
                else 
                    New(col[i][j - 1] + 1, col[i][j] - 1, i);
            }
            if(col[i].size())
                New(col[i][col[i].size() - 1] + 1, n, i);
        }
        for(int i = 1 ; i <= n ; ++ i)
            insert(rt[i], rt[i - 1], 1, n + 1, a[i], i);
        rt[n + 1] = rt[n];
        for(int i = 1 ; i <= idx ; ++ i)
        {
            int l = q[i].l, r = q[i].r, v = q[i].val;
            if(query(rt[r], 1, n + 1, l) == v)
                st[v] = true;
        }
    
        for(int i = 1 ; i <= n + 2 ; ++ i)
        {
            if(query(rt[n + 1], 1, n + 1, 1) == i)
                st[i] = true;
        }
        for(int i = 1 ; i <= n + 2 ; ++ i)
            if(!st[i])
                write(i), exit(0);
    }
}
int main()
{
    Solve::solve();
    return 0;
}
# 例题五
# [国家集训队] 阿狸和桃子的游戏
# 题目描述
阿狸和桃子正在玩一个游戏，游戏是在一个带权图 G=(V, E) 上进行的，设节点权值为 w (v)，边权为 c (e)。游戏规则是这样的：
  1. 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
  2. 为了保证公平性，节点的个数 N 为偶数。
  3. 经过 N/2 轮游戏之后，两人都得到了一个顶点集合。对于顶点集合 S，得分计算方式为
∑v∈Sw(v)+∑e=(u,v)∈E∧u,v∈Sc(e)\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)
由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。
# 分析:
对于这道题我们会发现计算点权非常好计算，但是有了边权就显得非常难计算，这时，充分发挥自己的智慧，会想到之前我们做树剖题维护边权的时候都会把边权给转换成点权，然后我们想一想这道题能不能也把边权拆成点权呢？显然是可以的，为什么呢？
我们考虑将边权一分为二扔到两个端点上，由于我们最终求的是差值，所以，对于一条边，如果一个人只拿了一半，那么让最后做差时，其实会相互抵消，也就不会在最终的答案中产生这个贡献，所以这个拆边权的策略的正确性是能保证的，然后我们就拆完之后直接 sortsort 一下不就能直接计算答案了吗。还有要注意排序的方向性，因为每个人是优先选择大的。
#include <cstring>
#include <iostream>
#include <algorithm>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
            while (ch >= '0' && ch <= '9')
                x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    const int N = 1e6 + 10;
    int n, m;
    double w[N], sum1, sum2;
    bool cmp(double a, double b)
    {
        return a > b;
    }
    void solve()
    {
        read(n), read(m);
        for(int i = 1 ; i <= n ; ++ i)
            read(w[i]);
        for(int i = 1 ; i <= m ; ++ i)
        {
            int a, b, v;
            read(a), read(b), read(v);
            w[a] += (double) v / 2 * 1.0;
            w[b] += (double) v / 2 * 1.0;
        }
        std::sort(w + 1, w + n + 1, cmp);
        for(int i =  1 ; i <= n ; ++ i)
        {
            if(i & 1)
                sum1 += w[i];
            else 
                sum2 += w[i];   
        }
        write(int(sum1 - sum2));
    }
}
int main()
{
    Solve::solve();
    return 0;
}
# 例题六
# Happy New Year
# 题面翻译
做圣诞老人是一件很难的事。有时你不得不面对困难的情况。
今天圣诞老人在度假的时候，有 mm 个孩子排在他面前。我们把他们从 11 到 mm 编上号。圣诞老人知道 nn 个咒语。每个咒语给编号从 LiL_i 到 RiR_i 的每个孩子一颗糖果。题目保证如果将全部的咒语都用一次，每个孩子至多收到 k 颗糖果
如果一个孩子得到的糖果量是偶数（可能为零），那么他（或她）会很伤心。不过，其他孩子（收到奇数个糖果的孩子）会很高兴。
请问圣诞老人最多能使多少个孩子快乐。
# 分析
首先我们看这个题，如果读题意就会当成若干次区间覆盖，每次加 11 然后就是查询 11 到 nn 中有多少位置是奇数，到但是我们再读一读题发现是从这些区间中任意选部分区间然后进行区间加，使得为奇数的位置尽可能多，同时我们从题意中还发现一个位置最多不会被超过 88 个区间给覆盖，那么我们可以直接对每一个点都进行状压来表示当前点被覆盖的状态，由于是区间，我们不太好处理，于是我们可以使用扫描线的思想，将其拆为两个点，扫到了直接处理对应的贡献即可。
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    #define int long long
    const int N = 1e6 + 10, INF = 0x7f7f7f7f;
    int n, m, k;
    int f[N], vis[N];
    std :: pair<int, int> line[N];
    int lowbit(int x) { return x & -x; }
    int count(int x)
    {
        int cnt = 0;
        while(x)
        {
            x -= lowbit(x);
            ++ cnt;
        }
        return cnt & 1;
    }
    void solve()
    {
        read(n), read(m), read(k);
        for(int i = 1 ; i <= n ; ++ i)
        {
            int l, r;
            read(l), read(r);
            line[i] = std :: make_pair(l, i);
            line[i + n] = std :: make_pair(r + 1, -i);
        }
        std :: sort(line + 1, line + (n << 1) + 1);
        for(int i = 1 ; i <= 256 ;++ i)
            f[i] = -INF;
        for(int i = 1 ; i <= (n << 1) ; ++ i)
        {
            int t = line[i].second, k;
            int len = (i == (n << 1) ? 0 : line[i + 1].first - line[i].first);
            if(t > 0)
            {
                for(int j = 0 ; j < 8 ; ++ j)
                {
                    if(!vis[j])
                    {
                        vis[j] = t, k = j;
                        break;
                    }
                }
                for(int j = 255 ; j ; -- j)
                {
                    if((j >> k) & 1)
                        f[j] = f[j - (1 << k)] + len * count(j);
                    else 
                        f[j] += len * count(j);
                }
            }
            else 
            {
                for(int j = 0 ; j < 8 ; ++ j)
                {
                    if(vis[j] == -t)
                    {
                        vis[j] = 0, k = j;
                        break;
                    }
                }
                for(int j = 0 ; j < 256 ; ++ j)
                {
                    if((j >> k) & 1)
                        f[j] = -INF;
                    else 
                        f[j] = max(f[j], f[j + (1 << k)]) + len * count(j);
                }
            }
        }
        write(f[0]);
    }
}
signed main()
{
    Solve :: solve();
    return 0;
}
# 例题七
# SCOI2015 小凸玩密室
# 题目描述
小凸和小方相约玩密室逃脱，这个密室是一棵有 nn 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 aia_i，每条边也有个权值 bib_i。点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 vv 的花费，等于上一个被点亮的灯泡 uu 到这个点 vv 的距离 Du,vD_{u,v}，乘以这个点的权值 ava_v。在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。
# 分析
这个状态设计起来还是比较新颖的对于我来说，我们考虑他只有两个子树，那么我们肯定是从一个子树到另一个子树，那么我们需要枚举是从哪转移过去的，那么我们就可以设 f[i][j][0/1]f[i][j][0/1] 为 ii 子树内已经处理完，下一个要处理的点为 ii 的 jj 级祖先（0）还是那个祖先的儿子（1）。
若当前点 xx 有做儿子没有右儿子，只有左儿子就不用讨论左右儿子谁更优了。
f[x][i][0]=f[ls(x)][i+1][0]+dis[ls(x)][1]∗a[ls(x)]f[x][i][0] = f[ls(x)][i + 1][0] + dis[ls(x)][1] * a[ls(x)]
f[x][i][1]=f[ls(x)][i+1][1]+dis[ls(x)][1]∗a[ls(x)]f[x][i][1] = f[ls(x)][i + 1][1] + dis[ls(x)][1] * a[ls(x)]
若当前点左右儿子都有
f[x][i][0]=min⁡(f[ls(x)][1][1]+f[rs(x)][i+1][0]+dis[ls(x)][1]∗a[ls(x)],f[rs(x)][1][1]+f[ls(x)][i+1][0]+dis[rs(x)][1]∗a[rs(x)])f[x][i][0] = \min(f[ls(x)][1][1] + f[rs(x)][i + 1][0] + dis[ls(x)][1] * a[ls(x)], f[rs(x)][1][1] + f[ls(x)][i + 1][0] + dis[rs(x)][1] * a[rs(x)])
f[x][i][1]=min⁡(f[ls(x)][1][1]+f[rs(x)][i+1][1]+dis[ls(x)][1]∗a[ls(x)],f[rs(x)][1][1]+f[ls(x)][i+1][1]+dis[rs(x)][1]∗a[rs(x)])f[x][i][1] = \min(f[ls(x)][1][1] + f[rs(x)][i + 1][1] + dis[ls(x)][1] * a[ls(x)], f[rs(x)][1][1] + f[ls(x)][i + 1][1] + dis[rs(x)][1] * a[rs(x)])
# 例题八
# HEOI2013 SAO
# 题目描述
Welcome to SAO (Strange and Abnormal Online)。这是一个 VR MMORPG， 含有 n 个关卡。但是，挑战不同关卡的顺序是一个很大的问题。
某款游戏有 n−1n-1 个对于挑战关卡的限制，诸如第 ii 个关卡必须在第 jj 个关卡前挑战，或者完成了第 kk 个关卡才能挑战第 ll 个关卡。并且，如果不考虑限制的方向性，那么在这 n−1n-1 个限制的情况下，任何两个关卡都存在某种程度的关联性。即，我们不能把所有关卡分成两个非空且不相交的子集，使得这两个子集之间没有任何限制。
# 分析
我们很容易就会有一个想法就是我们要先跑一个拓扑排序，然后一个比较 naivenaive 的想法就是跑出若干个部分然后每个块之间互相插入，但是我们会发现这样好像不是特别好处理，所以要转变一下思路，这若干个块一定是一棵树，然后我们可以对这棵树上的点进行标号（即为顺序），我们设 f[i][j]f[i][j] 为 ii 在他的子树中排名为 jj 的方案数，我们设当前点为 yy ，他的父亲为 xx ，那么我们考虑怎么讲 yy 转移到父亲那里，那么我我们设转移之后 xx 的方案数为 p3p3 ，转移前的排名为 p1p1 ，yy 的排名为 p2p2 ，那么左边的方案数量即为 Cp3−1p1−1C_{p3-1} ^ {p1-1} ，那么右边即为 Csizx+sizy−p3sizx−p1C_{siz_x+siz_y-p3} ^ {siz_x - p1} ，那么总的转移方程即为
f[x][p3]+=Cp3−1p1−1∗Csizx+sizy−p3sizx−p1∗f[x][p1]∗f[y][p2]f[x][p3] += C_{p3-1} ^ {p1-1} * C_{siz_x+siz_y-p3} ^ {siz_x - p1} * f[x][p1]*f[y][p2]
但是这复杂度是 O(n3)O(n^3) 的，我们还是过不去，但是我们发现可以处理一下 f[y][p2]f[y][p2] 的前缀，因为这个是只出现了一次且不会影响其他项，那么最后优化完之后掉一维，复杂度即为 O(n2)O(n^2) 是能过的。
#include <cstring>
#include <iostream>
#include <algorithm>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    #define int long long 
    const int N = 2e3 + 10, mod = 1e9 + 7;
    int t, n;
    int f[N][N], ans;
    int suf[N][N], pre[N][N];
    int temp[N], siz[N], h[N], idx;
    int infac[N], fac[N];
    struct Edge
    {
        int v, ne, w;
    } e[N];
    void add(int u, int v, int w)
    {
        e[++ idx].v = v, e[idx].w = w, e[idx].ne = h[u], h[u] = idx;
    }
    int qmi(int a, int k)
    {
        int res = 1;
        while(k)
        {
            if(k & 1)
                res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
        }
        return res;
    }
    void init()
    {
        fac[0] = infac[0] = 1;
        for(int i = 1 ; i <= 2e3 ; ++ i)
        {
            fac[i] = fac[i - 1] * i % mod;
            infac[i] = infac[i - 1] * qmi(i, mod - 2) % mod;
        }
    }
    int C(int n, int m)
    {
        if(n < m || m < 0 || n < 0)
            return 0;
        return fac[n] * infac[m] % mod * infac[n - m] % mod;
    }
    void dfs(int u, int fa)
    {
        siz[u] = f[u][1] = 1;
        for(int i = h[u] ; i ; i = e[i].ne)
        {
            int v = e[i].v;
            if(v == fa)
                continue;
            dfs(v, u);
            if(e[i].w == 1)
            {
                for(int p = siz[u] ; p >= 1 ; -- p)
                    for(int q = siz[v] ; q >= 1 ; -- q)
                        temp[p + q] = (temp[p + q] + f[u][p] * C(p + q - 1, p - 1) % mod * C(siz[u] + siz[v] - p - q, siz[u] - p) % mod * pre[v][q] % mod) % mod;
            }
            else 
            {
                for(int p = siz[u] ; p >= 1 ; -- p)
                    for(int q = siz[v] ; q >= 0 ; -- q)
                        temp[p + q] = (temp[p + q] + f[u][p] * C(p + q - 1, p - 1) % mod * C(siz[u] + siz[v] - p - q, siz[u] - p) % mod * suf[v][q + 1] % mod) % mod;
            }
            siz[u] += siz[v];
            for(int x = 1 ; x <= siz[u] ; ++ x)
                f[u][x] = temp[x], temp[x] = 0;
        }
        pre[u][0] = f[u][0];
        for(int x = 1 ; x <= siz[u] ; ++ x)
            pre[u][x] = (pre[u][x - 1] + f[u][x] % mod) % mod;
        suf[u][siz[u] + 1] = 0;
        for(int x = siz[u] ; x >= 1 ; -- x)
            suf[u][x] = (suf[u][x + 1] + f[u][x] % mod) % mod;
    }
    void solve()
    {
        read(t);
        init();
        while(t -- )
        {
            read(n);    
            memset(h, 0, sizeof(h)), idx = ans = 0;
            memset(f, 0, sizeof(f));
            for(int i = 1 ; i < n ; ++ i)
            {
                int a, b;
                char op;
                read(a), scanf("%c", &op), read(b);
                ++ a, ++ b;
                if(op == '>')
                    add(a, b, 1), add(b, a, 0);
                else 
                    add(a, b, 0), add(b, a, 1);
            }
            dfs(1, 0);
            for(int i = 1 ; i <= n ; ++ i)
                ans = ans + f[1][i] % mod;
            write(ans % mod), puts("");
        }
    }
}
signed main()
{
    Solve :: solve();
    return 0;
}
# 例题九
# The Child and Toy
# 题面翻译
n 个带权点，m 条无向边，删除一个点就要付出所有与之有联系且没有被删除的点的点权之和的代价。
求删除所有点的最小代价。
# 分析
这题一开始感觉是个贪心，但是我想的贪心策略是一个点的贡献是点权乘上度数，然后优先删除贡献最多的，但是会发现连样例都过不了，然后发现这删点其实就等价于给一条边定了一个全职，因为我们实际上是要删掉所有的边的，我们删去点的顺序实际上是在给这个边定值，那么我们对于每条边直接删去小的点即可，因为大小关系是不会有环的，所以这样的正确性是能保证的。（这道题也没有必要挂代码
# 例题十
# ABC164E Two Currencies
# 题目描述
有 nn 个城市，它们由 mm 条双向道路连接，保证它们能够彼此到达。第 ii 条道路连接 ui,viu_i,v_i，需要花费 xix_i 个银币，耗费 tit_i 秒的时间。每个城市处都有兑换银币处，第 ii 个城市中你可以用 11 个金币兑换 cic_i 个银币，可以兑换无限次，不过兑换 11 次需要花费 did_i 秒的时间。你一开始在 11 号城市，有 ss 个银币和无限多的金币，求到其它城市需要耗费的最小时间。
1≤n≤501 \leq n \leq 50，n−1≤m≤100n - 1 \le m \le 100，1≤xi≤501 \leq x_i \leq 50，1≤ti,di≤1091 \leq t_i,d_i \leq 10^9，1≤s,ci≤1091 \leq s,c_i \leq 10^9
# 分析
首先这个题一开始想到是 dpdp 但是是想的按每一个点去 dpdp 然后就想着是枚举一个点的所有出点，然后枚举当前点的状态，但是感觉兑换银币的那个操作不太好处理，然后知道了一种很优秀的思路。首先我们可以对于在每个点时有的金币数当成一个状态，那么接下来就是这若干个二元组之间的转移，然后我们考虑就 5050 个点，每次最多花费 5050 个银币，那么实际上就是最多 24502450 个就够了，那么我们最终状态数量就是 n3n^3 的，那么我们对于状态之间可以进行连边，那么对于起点跑个 dijkstradijkstra ，对于每个点的所有状态取个最小值即可。
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace read_write
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char ch = getchar();
        while (ch > '9' || ch < '0')
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        return;
    }
    template <typename T, typename... Args>
    inline void read(T &first, Args &...args)
    {
        read(first);
        read(args...);
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
        {
            x = -x;
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T>
    T max(T x, T y)
    {
        return x > y ? x : y;
    }
    template <typename T>
    T min(T x, T y)
    {
        return x > y ? y : x;
    }
    template <typename T>
    void swap(T &a, T &b)
    {
        T tem = b;
        b = a;
        a = tem;
    }
}
namespace Solve
{
    using namespace read_write;
    #define int long long
    const int N = 2e6 + 1206;
    const int INF = 0x7f7f7f7f7f7f;
    int n, m, s, tot; 
    int h[N], idx;
    int dis[N];
    bool st[N];
    struct Edge
    {
        int v, ne, w;
    } e[N];
    struct Mypair
    {
        int w, id;
        bool operator < (const Mypair &a) const { return w > a.w; }
    } ;
    std :: priority_queue<Mypair> q;
    void add(int u, int v, int w)
    {
        e[++ idx].v = v, e[idx].ne = h[u], e[idx].w = w, h[u] = idx;
    }
    int get_id(int x, int y)
    {
        return x * (tot + 1) + y;
    }
    void dijkstra(int x)
    {
        std :: fill(dis, dis + N, INF);
        dis[x] = 0, q.push({0, x});
        while(!q.empty())
        {
            auto u = q.top();
            q.pop();
            if(st[u.id])
                continue;
            st[u.id] = true;
            for(int i = h[u.id] ; i ; i = e[i].ne)
            {
                int v = e[i].v;
                if(dis[v] > dis[u.id] + e[i].w)
                {
                    dis[v] = dis[u.id] + e[i].w;
                    if(!st[v])
                        q.push({dis[v], v});
                }
            }
        }
    }
    void solve()
    {
        tot = 2500;
        read(n, m, s);
        for(int i = 1 ; i <= m ; ++ i)
        {
            int u, v, x, t;
            read(u, v, x, t);
            
            for(int j = x ; j <= tot ; ++ j)
            {
                add(get_id(u, j), get_id(v, j - x), t);
                add(get_id(v, j), get_id(u, j - x), t);
            }    
        }
        for(int i = 1 ; i <= n ; ++ i)
        {
            int x, y;
            read(x, y);
            for(int j = x ; j <= tot ; ++ j)
                add(get_id(i, j - x), get_id(i, j), y);
        }
        dijkstra(get_id(1, min(s, tot)));
        for(int i = 2 ; i <= n ; ++ i)
        {
            int ans = INF;
            for(int j = 0 ; j <= tot ; ++ j)
                ans = min(ans, dis[get_id(i, j)]);
            write(ans), puts("");
        }
    }
}
signed main()
{
    Solve :: solve();
    return 0;
}
 
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
Tokai Teio 微信支付
微信支付
Tokai Teio 支付宝
支付宝
Tokai Teio 贝宝
贝宝