标签：Right 赛时 int Sum 11.20 rm CW dp Left

看题

前言: 花了 $10 \rm{min}$ 把昨天的题调了一下, 神经

$\rm{T1}$

艹, 再一次缺失大样例

神秘博弈放 $\rm{T1}$ , 大抵可做 (主要原因是 $\rm{lhs}$ 键盘敲得框框响)

手玩几组数据大概能做, 后面再认真看

$\rm{T2}$

看到树直接小命不保

喵了个咪的, 这我打鸡毛啊

又开始想树形 $\rm{dp}$ ?

好的方面是, $50\%$ 还能打

$\rm{T3}$

坏了, 今天是神秘 $\rm{dp}$ 专题, 寄

$\rm{T4}$

没啥思路, 多半最后也只有时间过来打个暴力

正序开题

$\rm{T1}$

最多想 $40 \rm{min}$ , 不能再多了

以下将 dogenya 称为 A , dogwang 称为 B

注意到 A 每次必定是从序列中删除掉一个数, 使得序列中元素和最大的连续区间元素和最小, 而 B 只能将元素和最大的连续区间选完

关于 B 选择的原因:
如果 B 留一段, 后面一定不优, 一定不如直接选完

也就是说, 这个博弈问题只与 A 有关, 我们每次枚举最小分割点, 前缀和优化查询, 这是 $\mathcal{O}(n)$ 的, 最多分割 $n$ 次, 时间复杂度 $\mathcal{O} (n ^ 2)$ , 没的说

先在这里造数据

in:
10
11 32 14 56 12 37 41 47 24 53

out:
215

就这样

希望别假, 还是先去打 $\rm{T2}$

$\rm{T2}$

如果 $\rm{T1}$ 正解真的这么简单的话, 区分度应该在 $\rm{T2}$ , 看能不能冲一发

现在只过去了 $33 \rm{min}$ , 优势在我

首先观察到, 对于链的情况是一个简单贪心

对于小数据, 我们显然可以 $\rm{dfs}$ 处理

部分分还是非常宽松的, 爽

注意到时间其实就是询问最小的武力值

令 $f_{i, j}$ 表示根节点为 $i$ , 最大武力值为 $j$ , 可能获得的最大货物储备之和

答案二分可得

状态转移方程, 显然的

\[f_{i, j} = \sum_{u \in \rm{Son} (i), w \leq j} f_{u, j} \]

看起来这并不像一道树形 $\rm{dp}$ , 倒是像一道二分答案

既然收货不需要时间, 那么我们显然可以在外层二分武力值 , 内层循环中, 能走的全部走即可, 直接用 $f_i$ 表示以 $i$ 为根子树中有多少货物能够被收集, 每次 $\rm{check}$ 是 $\mathcal{O}(n)$ 的

易得外层 $\mathcal{O}(\log W)$ 数量级是 $30$ 上下

那么正解就出来了, 时间复杂度 $\mathcal{O}(n \log W)$

这下只过去了 $1 \rm{h}$

$\rm{T3}$

直接不打代码冲 $\rm{T3}$ , 无论如何, 会战兵力是 $200 \rm{pts}$ 打 $100 \rm{pts}$ , 优势在我(毕竟 $200 \rm{pts}$ 应该大家都有, 要么就是我想简单了, 反正没有好结局)

先转化题意

每个物品重量 $w$ , 将其分成若干个不同的组, 使得组中物品编号连续
对于第 $i$ 个组, 其花费为 $i \times w_{sum} + w_{max} - w_{min}$
询问怎样分组, 费用最少

也许是一种很典的 $\rm{dp}$ , 但是我没见过, $\rm{lhs}$ 这次真的要 $\rm{AK}$ 了

转移过程中记录最后一组的 $w_{min}$ , $w_{max}$ , $w_{sum}$

每次对于一个物品无非两种选择

新开一组
跟上上一组

但是这样不好设计状态, 只能打 $10\%$ 的小数据, 肯定不够

感觉很冷, 要趋势力

想到 $1 \rm{h} 30 \rm{min}$ 就跳过, 不能死磕

令 $dp_i$ 表示前 $i$ 个物品最优情况下, 花费最小, 其中必须以第 $i$ 个物品结束一组, 并且记录当前有多少组

显然有 $dp_0 = \{0, 0\}, dp_1 = \{1, 1\}$, 答案即为 $dp_n$

有,

\[dp_i = \min_{j \in [0, i)}(dp_{j} + Cost_{i + 1, j} ) \]

这是 $ \mathcal{O}(n ^ 2)$ 的, 考虑优化, 但是不优化也有 $60\%$ 的分, 差不多够了

$Cost$ 需要前缀和预处理和 $\rm{ST}$ 表预处理, 这个太冒险只能最后打, 基本上可以确定是假的

$\rm{T4}$

把暴力当正解想, 这场就结束了

这个题的目标就是把 $30\%$ 打出来

最多想到 $1 \rm{h} 45 \rm{min}$

差不多就这样

代码

$\rm{T1}$

先打保险一点的 $\rm{T1}$ , 毕竟比较好打

#include <bits/stdc++.h>
#define int long long
const int MAXN = 520; // 641

int n;
int Sum[MAXN];

void solve()
{
    int Ans = 0;
    int Left = 1, Right = n;
    while (Left <= Right)
    {
        int CutPoint = -1;
        int type = -1; // 0 左, 1 右
        int Min_Sum = 0x3f3f3f3f;
        for (int i = Left; i <= Right; i++) {
            if (Min_Sum > std::max(Sum[i - 1] - Sum[Left - 1], Sum[Right] - Sum[i])) {
                Min_Sum = std::max(Sum[i - 1] - Sum[Left - 1], Sum[Right] - Sum[i]);
                if (Sum[i - 1] - Sum[Left - 1] > Sum[Right] - Sum[i]) type = 0;
                else type = 1;
                CutPoint = i;
            }
        }
        Ans += Min_Sum;
        if (type == 0) Left = CutPoint + 1;
        else Right = CutPoint - 1;
    }

    printf("%lld", Ans);
}

signed main()
{
#ifdef FILE_IO
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
#endif

    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &Sum[i]);
        Sum[i] += Sum[i - 1];
    }

    solve();

    return 0;
}

应该不会有太大问题

$\rm{T2}$

顺下去打, 看看有没有实现上的问题?

#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e6 + 20;

int n, W;
int MaxW = 0;

class Tree_Class
{
private:

public:
    struct node
    {
        int to, w;
        int next;
    } Edge[MAXN];
    int Edge_Cnt = 0;
    int head[MAXN];
    int Val[MAXN];
    void head_init() { for (int i = 0; i <= n + 1; i++) head[i] = -1; }

    void addedge(int u, int v, int w) {
        Edge[++Edge_Cnt].to = v, Edge[Edge_Cnt].w = w;
        Edge[Edge_Cnt].next = head[u];
        head[u] = Edge_Cnt;
    }

    /*建树*/
    void solve()
    {
        for (int i = 2; i <= n; i++)
            scanf("%lld", &Val[i]);

        for (int i = 1; i <= n - 1; i++) {
            int u, v, w;
            scanf("%lld %lld %lld", &u, &v, &w);
            MaxW = std::max(MaxW, w);
            addedge(u, v, w);
        }
    }
} Tree;

class Sol_Class
{
private:
    int f[MAXN];

    void dfs(int Now, int fa, int x)
    {
        f[Now] = Tree.Val[Now];
        for (int i = Tree.head[Now]; ~i; i = Tree.Edge[i].next)
        {
            int NowTo = Tree.Edge[i].to, NowW = Tree.Edge[i].w;
            if(NowW > x || NowTo == fa) continue;
            dfs(NowTo, Now, x);
            f[Now] += f[NowTo];
        }
    }

    bool check(int x) {
        memset(f, 0, sizeof(f));
        dfs(1, -1, x);

        return f[1] >= W;
    }

public:
    /*二分答案*/
    void bin_search()
    {
        int Left = 0, Right = MaxW + 1;
        int Ans;
        while (Left < Right) {
            int Mid = Left + ((Right - Left) >> 1);

            if (check(Mid)) {
                Right = Mid;
                Ans = Mid;
            }else {
                Left = Mid + 1;
            }
        }

        printf("%lld", Ans);
    }
} Sol;

signed main()
{
#ifdef FILE_IO
    freopen("collect.in", "r", stdin);
    freopen("collect.out", "w", stdout);
#endif

    scanf("%lld %lld", &n, &W);
    Tree.head_init();
    Tree.solve();

    Sol.bin_search();

    return 0;
}

应该是对的, 希望别挂

$\rm{T3}$

这个题需要先捋一捋, 还剩下约 $1\rm{h}$

冲冲冲

#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e5 + 20;

int n, W;
int Val[MAXN];
int Sum[MAXN];

class ST_Class
{
private:
    int LOG2[MAXN];
    int ST_max[MAXN][30], ST_min[MAXN][30];

public:
    /*建立 ST 表*/
    void solve()
    {
        LOG2[0] = -1;
        for (int i = 1; i <= 1e5; i++) {
            LOG2[i] = LOG2[i >> 1] + 1;
        }

        for (int i = 1; i <= n; i++) {
            ST_max[i][0] = ST_min[i][0] = Val[i];
        }

        int p = log2(n);
        for (int k = 1; k <= p; k++) {
            for (int s = 1; s + (1 << k) <= n + 1; s++) {
                ST_max[s][k] = std::max(ST_max[s][k - 1], ST_max[s + (1 << (k - 1))][k - 1]);
                ST_min[s][k] = std::min(ST_min[s][k - 1], ST_min[s + (1 << (k - 1))][k - 1]);
            }
        }
    }

    int query_max(int Left, int Right) {
        int k = LOG2[Right - Left + 1];
        return std::max(ST_max[Left][k], ST_max[Right - (1 << k) + 1][k]);
    }
    int query_min(int Left, int Right) {
        int k = LOG2[Right - Left + 1];
        return std::min(ST_min[Left][k], ST_min[Right - (1 << k) + 1][k]);
    }
} ST;

struct node
{
    int Val;
    int Num;
} dp[MAXN];

int Cost(int Left, int Right, int num) {
    if (Sum[Right] - Sum[Left - 1] > W) return 0x3f3f3f3f;
    return num * (Sum[Right] - Sum[Left - 1]) + ST.query_max(Left, Right) - ST.query_min(Left, Right);
}

/*dp 计算*/
void solve()
{
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j].Val + Cost(j + 1, i, dp[j].Num + 1) < dp[i].Val) {
                dp[i].Val = dp[j].Val + Cost(j + 1, i, dp[j].Num + 1), dp[i].Num = dp[j].Num + 1;
            }
        }
    }

    printf("%lld", dp[n].Val);
}

signed main()
{
#ifdef FILE_IO
    freopen("grouping.in", "r", stdin);
    freopen("grouping.out", "w", stdout);
#endif

    scanf("%lld %lld", &n, &W);
    for (int i = 1; i <= n; i++) 
        scanf("%lld", &Val[i]), Sum[i] = Sum[i - 1] + Val[i];

    ST.solve();

    solve();

    return 0;
}

方程有可能会挂

$\rm{T4}$

这个暴力看手速了

最后也没写完, 太难搞了

baidu 搜索: dfs 计算四元环的个数

标签：Right,赛时,int,Sum,11.20,rm,CW,dp,Left
From： https://www.cnblogs.com/YzaCsp/p/18558698

11.20 CW 模拟赛赛时记录

看题

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

代码

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

相关文章

赞助商

阅读排行

11.20 CW 模拟赛 赛时记录

看题

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

代码

\(\rm{T1}\)

\(\rm{T2}\)

\(\rm{T3}\)

\(\rm{T4}\)

相关文章

赞助商

阅读排行

11.20 CW 模拟赛赛时记录