「NOI2019」题解小结

杂题 / noi
Word count: 211   |   Reading time≈ 1 min

A 接 W 接外圈刮吮干缪撒，跟我搞这个东西

顺序由个人认为的难度排序

回家路线

Description

巧克力回家

#3156. 「NOI2019」回家路线

Solution

最暴力的一个想法就是建 $nt$ 个点，点 $(i,j)$ 表示现在在点 $i$ ，时刻是 $j$ ，然后跑一个不是那么简单的最短路。

仔细思考后发现两次等待必须由乘坐一般车连接，考虑到转移的方便程度和状态的数量，我们只留下出发状态（恰好能乘上车）和到达状态（刚下车），这样一来状态数就变成 $O(m)$ 了，暴力最短路 $O(m^2)$ 。

考虑到最短路本质是一个 DP ，我们不妨从 DP 的角度来看待这个问题，我们发现有转移

拆开平方后就是个斜率优化，实际上写动态开点李超树也是可行的，这也是我的做法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
ll n, m, val[5], ans = linf;

struct edge
{
    ll x, y, p, q;
    friend bool operator < (edge a, edge b)
    {
        return a.p < b.p;
    }
}
e[maxn];

vector <edge> s[maxn];

struct node
{
    ll ls, rs;
    ll a, b;
}
tr[maxn << 5];

ll rt[maxn], cnt;

ll calc(ll x, ll a, ll b)
{
    return a * x + b;
}

void modify(ll &tot, ll l, ll r, ll a, ll b)
{
    if(!tot) assert(cnt + 1 < maxn), tot = ++ cnt, tr[tot].b = linf;
    if(calc(l, tr[tot].a, tr[tot].b) > calc(l, a, b)) swap(tr[tot].a, a), swap(tr[tot].b, b);
    if(calc(r, tr[tot].a, tr[tot].b) <= calc(r, a, b)) return;
    if(l == r) return;
    ll mid = (l + r) >> 1;
    if(calc(mid, tr[tot].a, tr[tot].b) <= calc(mid, a, b)) modify(tr[tot].rs, mid + 1, r, a, b);
    else swap(tr[tot].a, a), swap(tr[tot].b, b), modify(tr[tot].ls, l, mid, a, b);
}

ll query(ll tot, ll l, ll r, ll x)
{
    if(!tot) return linf;
    ll mid = (l + r) >> 1;
    ll ret = calc(x, tr[tot].a, tr[tot].b);
    if(x <= mid) chmin(ret, query(tr[tot].ls, l, mid, x));
    else chmin(ret, query(tr[tot].rs, mid + 1, r, x));
    return ret;
}

ll f[maxn];

signed main()
{
    file("route");
    n = read(), m = read(), val[2] = read(), val[1] = read(), val[0] = read();
    rep(i, 1, m) e[i].x = read(), e[i].y = read(), e[i].p = read(), e[i].q = read();
    sort(e + 1, e + m + 1);
    f[0] = 0;
    modify(rt[1], 0, 1000, 0, 0);
    ll pos = 0;

    rep(i, 1, m)
    {
        while(pos <= e[i].p && pos <= 1000)
        {
            for(auto now : s[pos]) modify(rt[now.x], 0, 1000, now.y, now.q);
            pos ++;
        }
        f[i] = query(rt[e[i].x], 0, 1000, e[i].p) + val[2] * e[i].p * e[i].p + val[1] * e[i].p + val[0];
        if(e[i].y == n) chmin(ans, f[i] + e[i].q);
        else s[e[i].q].pb((edge){e[i].y, -2 * val[2] * e[i].q, e[i].q, f[i] + val[2] * e[i].q * e[i].q - val[1] * e[i].q});
    }
    printf("%lld\n", ans);
    return 0;
}

弹跳

Description

郭思博帝国

#3159. 「NOI2019」弹跳

Solution

这个题有两档暴力，直接最短路 52pts，一维的情况线段树优化建图一共 72pts。

正解还是考虑如何用数据结构优化建图。这个题有一个很重要的技巧，就是我们发现我们跑 dijkstra 的时候每次会拿出当前最小的点来进行松弛操作，并且松弛的时候，从一个点出发走到一个矩阵，用来松弛的值都是 $dist_i+t_j$ ，然后把这个点标记为以松弛。于是我们原本是把这个矩阵里的每一个点都松弛一遍，然后判断是否入队，现在我们不妨直接在松弛的时候把每条边转移出去的整个矩阵当做一个整体，扔进优先队列里。松弛的时候直接把队首的一整个矩阵拿出来，考虑里面哪些点是真正要进行松弛操作的点，显然是那些未被标记为已松弛的点。虽然听起来很像废话，但是我还是解释一个，因为如果一个点已经被标记为以松弛，那么他一定已经出队过了，他的权值一定小于当前权值。否则这个点还没有出队，那么他的权值一定大于等于队内权值最小值，在当前这次操作刚好取到最小值，于是就可以进行松弛操作后出队。不考虑如何找到一个矩阵内未松弛的点，最短路的复杂度是 $O(m\log m)$ ，瓶颈就是入队次数是 $O(m)$ 的。

剩下的问题就是如何找到一个矩阵里未松弛的点有哪些了。因为一个点松弛一次后就没有贡献了，所以我们可以直接用线段树套set简单维护，这部分时间复杂度 $O(n\log^2n)$ 。

空间稍微注意一下应该就没什么问题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
int n, m, w, h;

pii p[maxn];

struct catapult
{
    int val, l, r, d, u;
    friend bool operator < (catapult a, catapult b)
    {
        return a.val < b.val;
    }
}
;

vector <catapult> edge[maxn];

struct node
{
    int l, r;
    set <pii> s;
}
tr[maxn << 3];

#define ls (tot << 1)
#define rs (ls | 1)
#define mid ((tr[tot].l + tr[tot].r) >> 1)

void build(int tot, int l, int r)
{
    tr[tot].l = l, tr[tot].r = r;
    if(l == r) return;
    build(ls, l, mid), build(rs, mid + 1, r);
}

void add(int tot, int x, int pos)
{
    tr[tot].s.insert(mp(p[pos].se, pos));
    if(tr[tot].l == tr[tot].r) return ;
    if(x <= mid) add(ls, x, pos);
    else add(rs, x, pos);
}

void del(int tot, int x, int pos)
{
    tr[tot].s.erase(tr[tot].s.find(mp(p[pos].se, pos)));
    if(tr[tot].l == tr[tot].r) return ;
    if(x <= mid) del(ls, x, pos);
    else del(rs, x, pos);
}

pqueue <pair <int, catapult>> q;

int dist[maxn];

vi pos;

void find(int tot, catapult x, int val)
{
    if(tr[tot].l >= x.l && tr[tot].r <= x. r)
    {
        auto it = tr[tot].s.lb(mp(x.d, 0));
        while(it != tr[tot].s.end())
        {
            if(it -> fi > x.u) break;
            dist[it -> se] = val, pos.pb(it -> se);
            ++ it;
        }
        return;
    }
    if(x.l <= mid) find(ls, x, val);
    if(x.r > mid) find(rs, x, val);
}

void solve()
{
    while(!q.empty())
    {
        auto now = q.top();
        q.pop();
        find(1, now.se, -now.fi);
        for(int now : pos)
        {
            for(auto to : edge[now]) q.push(mp(-to.val - dist[now], to));
            del(1, p[now].fi, now);
        }
        vi().swap(pos);
    }
}

signed main()
{
    file("jump");
    n = read(), m = read(), w = read(), h = read();
    rep(i, 1, n) p[i].fi = read(), p[i].se = read();
    rep(i, 1, m)
    {
        int p = read(), val = read(), l = read(), r = read(), d = read(), u = read();
        edge[p].pb((catapult){val, l, r, d, u});
    }
    build(1, 1, w);
    rep(i, 1, n) add(1, p[i].fi, i);
    rep(i, 2, n) dist[i] = iinf;
    for(auto to : edge[1]) q.push(mp(-to.val, to));
    solve();
    rep(i, 2, n) printf("%d\n", dist[i]);
    return 0;
}

序列

Description

没有任何资产

#3158. 「NOI2019」序列

Solution

主流做法有两种：模拟费用流 和 反悔贪心

模拟费用流

网络流一般不擅长解决至少的限制，于是我们把至少 $L$ 对数的限制对偶成至多 $K-L$ 对不同的限制，可以建出这样的费用流流模型。

from s_r_f的博客

直接跑费用流有 64pts，但是这个图肉眼可见的十分简单，我们考虑用模拟的方法优化掉每次跑 spfa 增广的过程，这就是所谓的的模拟费用流的概念。

至于如何找到最短路，首先发现边权非零的边只有 $S$ 出发的边和 $T$ 结束的边，换句话说每一条合法的最短路一定是原图上的一对匹配。我们只需要考虑若干种本质不同的匹配的最小值以及他们对 $C \to D$ 流量的影响，然后每次选出最小的可行路径然后把图上流量进行修改即可，具体细节可以参考 s_r_f的博客。

反悔贪心

本质和模拟费用流什么大的区别，但是做法上会有一些出入。如果没有 L 的限制，我们一定会贪心地选出 $a$ 中最大的 $k$ 个和 $b$ 中最大的 $k$ 个，但是一般情况下这样随意的选择都不会满足 L 的限制（指除了样例的情况），于是我们通过贪心的策略进行一些反悔，逐步满足 L 的限制，这个就是反悔贪心的做法。

考虑怎样的操作可以在不改变 K 的情况下使 $L + 1$ ，本质不同的方法只有下面四种

下北沢の迫真画作

图中的 o 表示方案中选的数，x 表示方案中不选的数，红线则是修改的变化。

  1. case 1

    case 1 其实是两种对称的策略，我把他们放在一起了。具体来说就是把一个选了 $a_i$ 却没有选 $b_i$ 的 $a_i$ 改成 $a_j$，使其配对另一个 $b_j$ ，代价为 $a_j-a_i$ 。最优的策略一定是选一个最大的合法的 $a_i$ ，改成一个最大的合法的 $a_j$ ，用两个堆不怎么简单维护一下。对称的情况类似，一共用四个堆不简单维护。

  2. case 2

    case 2 就是拆开一对原有的配对，使他们配对剩下的两对，代价为 $-(a_i+b_i)+a_j+b_k$ ，我们在 case 1 里已经维护过最大合法 $a_j$ 和 $b_k$ 了，所以只需要再加一个堆维护最大合法的 $-(a_i+b_i)$ 即可。

  3. case 3

    case 2 倒过来而已，代价是 $a_i+b_i-a_j-b_k$ ，后面两项在 case 1 里维护了，第一项重新维护一下就好了。

六个堆不简单维护即可。

Code

反悔贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

ll t, n, k, l, ans;

ll a[maxn], b[maxn], vis[2][maxn];

pii c[maxn], d[maxn];

pqueue <pii> p[14];

void upd(ll &a, ll &b, ll x, ll y)
{
    if(y > b) b = y, a = x;
}

signed main()
{
    file("sequence");
    t = read();
    while(t --)
    {
        n = read(), k = read(), l = read();
        rep(i, 1, n) a[i] = read(), c[i] = mp(a[i], i), vis[0][i] = 0;
        rep(i, 1, n) b[i] = read(), d[i] = mp(b[i], i), vis[1][i] = 0;
        sort(c + 1, c + n + 1), sort(d + 1, d + n + 1), reverse(c + 1, c + n + 1), reverse(d + 1, d + n + 1);
        rep(i, 1, k) ans += c[i].fi + d[i].fi, vis[0][c[i].se] = vis[1][d[i].se] = 1;
        rep(i, 1, n)
        {
            if(vis[0][i] && vis[1][i])
            {
                p[0].push(mp(-a[i] - b[i], i));
                l --;
            }
            if(!vis[0][i] && vis[1][i])
            {
                p[1].push(mp(a[i], i));
                p[2].push(mp(-b[i], i));
            }
            if(vis[0][i] && !vis[1][i])
            {
                p[3].push(mp(b[i], i));
                p[4].push(mp(-a[i], i));
            }
            if(!vis[0][i] && !vis[1][i])
            {
                p[5].push(mp(a[i] + b[i], i));
            }
        }
        // printf("%lld\n", ans);
        while(l --> 0)
        {
            while(!p[0].empty() && (!vis[0][p[0].top().se] || !vis[1][p[0].top().se])) p[0].pop();
            while(!p[1].empty() && (vis[0][p[1].top().se] || !vis[1][p[1].top().se])) p[1].pop();
            while(!p[2].empty() && (vis[0][p[2].top().se] || !vis[1][p[2].top().se])) p[2].pop();
            while(!p[3].empty() && (!vis[0][p[3].top().se] || vis[1][p[3].top().se])) p[3].pop();
            while(!p[4].empty() && (!vis[0][p[4].top().se] || vis[1][p[4].top().se])) p[4].pop();
            while(!p[5].empty() && (vis[0][p[5].top().se] || vis[1][p[5].top().se])) p[5].pop();
            ll typ = -1, val = -linf;
            if(!p[0].empty() && !p[1].empty() && !p[3].empty()) upd(typ, val, 0, p[0].top().fi + p[1].top().fi + p[3].top().fi);
            if(!p[1].empty() && !p[4].empty()) upd(typ, val, 1, p[1].top().fi + p[4].top().fi);
            if(!p[2].empty() && !p[3].empty()) upd(typ, val, 2, p[2].top().fi + p[3].top().fi);
            if(!p[5].empty() && !p[2].empty() && !p[4].empty()) upd(typ, val, 5, p[5].top().fi + p[2].top().fi + p[4].top().fi);
            ans += val;
            // printf("choose : %lld %lld\n", typ, val);
            if(typ == 0)
            {
                ll p1 = p[1].top().se, p2 = p[3].top().se, p3 = p[0].top().se;
                vis[0][p3] = vis[1][p3] = 0;
                p[5].push(mp(a[p3] + b[p3], p3)); 
                vis[0][p1] = 1;
                vis[1][p2] = 1;
                p[0].push(mp(-a[p1] - b[p1], p1));
                p[0].push(mp(-a[p2] - b[p2], p2));
            }
            if(typ == 1)
            {
                ll p1 = p[1].top().se, p2 = p[4].top().se; 
                vis[0][p1] = 1;
                vis[0][p2] = 0;
                p[0].push(mp(-a[p1] - b[p1], p1));
                p[5].push(mp(a[p2] + b[p2], p2));
            }
            if(typ == 2)
            {
                ll p1 = p[2].top().se, p2 = p[3].top().se; 
                vis[1][p1] = 0;
                vis[1][p2] = 1;
                p[5].push(mp(a[p1] + b[p1], p1));
                p[0].push(mp(-a[p2] - b[p2], p2));
            }
            if(typ == 5)
            {
                ll p1 = p[2].top().se, p2 = p[4].top().se, p3 = p[5].top().se;
                // printf("%lld %lld %lld\n", p1, p2, p3);
                vis[0][p3] = vis[1][p3] = 1;
                p[0].push(mp(-a[p3] - b[p3], p3));
                vis[1][p1] = 0;
                vis[0][p2] = 0;
                p[5].push(mp(a[p1] + b[p1], p1));
                p[5].push(mp(a[p2] + b[p2], p2));
            }
        }
        printf("%lld\n", ans);
        ans = 0;
        rep(i, 0, 5) while(!p[i].empty()) p[i].pop();
    }
    return 0;
}

斗主地

Description

澳门线上

#3160. 「NOI2019」斗主地

Solution

只能毛估估讲一下怎么做。

首先我们发现一次洗牌过后，每一种牌出现的概率都一样，证明就考虑一种牌的出现概率就是每一步概率乘起来，既然分子乘起来都一样，分母乘起来也都一样，那么概率一定也是一样的。

然后因为初始的时候每个点的概率都是一个关于 $i$ 的低于二次的函数，洗牌操作又是把两个序列不改变顺序的情况下均匀的混在一起，那么毛估估一下期望应该还是一个关于 $i$ 的多项式，且次数不会变多。

于是我们只需要算出每一次操作之后前三张牌的期望，然后把多项式系数叉出来即可，又由于牌堆的前三张一定由第一堆的前三张和第二堆的前三张组合而成，所以我们只要每次通过已经差出的系数算出第二堆牌的排顶三张牌的期望，然后暴力 $2^3$ 枚举他们如何组合，算出新牌堆的前三张期望即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
ll n, m, typ, q;

ll a[maxn];

ll coef[3], val[5][5];

ll calc(ll x)
{
    return (x * x % mod * coef[2] % mod + x * coef[1] % mod + coef[0]) % mod;
}

ll fac[10000005], inv[10000005];

ll power(ll a, ll b)
{
    ll ret = 1;
    for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod;
    return ret;
}

void init()
{
    fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    inv[n] = power(fac[n], mod - 2);
    per(i, n, 1) inv[i - 1] = inv[i] * i % mod;
}

ll binom(ll n, ll m)
{
    return n < m ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod;
}

ll bit[maxn];

signed main()
{
    file("landlords");
    n = read(), m = read(), typ = read();
    init();
    coef[typ] ++;
    rep(i, 1, 7) bit[i] = bit[i - lowbit(i)] + 1;
    while(m --)
    {
        ll a = read();
        rep(i, 1, 3) val[0][i] = calc(i), val[1][i] = calc(a + i), val[2][i] = 0;
        ll inv = power(binom(n, a), mod - 2);
        rep(i, 0, 7)
        {
            if(bit[i] > a || 3 - bit[i] > n - a) continue;
            ll p0 = 0, p1 = 0, p = binom(n - 3, a - bit[i]) * inv % mod;
            rep(j, 1, 3)
            {
                if(i >> j - 1 & 1) red(val[2][j] += p * val[0][++ p0] % mod);
                else red(val[2][j] += p * val[1][++ p1] % mod);
            }
        }
        coef[2] = (val[2][3] + 2 * (mod - val[2][2]) + val[2][1]) * (mod + 1) / 2 % mod;
        coef[1] = (val[2][2] + mod - val[2][1] + 3 * (mod - coef[2])) % mod;
        coef[0] = (val[2][1] + mod - coef[2] + mod - coef[1]) % mod;
    }

    // query
    q = read();
    while(q --)
    {
        ll x = read();
        printf("%lld\n", calc(x));
    }
    return 0;
}

机器人 & I君的探险

感觉题不是很能写，题解去网上找找8.。

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信