2019-07-12发表2020-11-21更新OI / 题解

「USACO 2011 Jan. Gold」道路和航线

题目概述

LOJ #10081. 「一本通 3.2 练习 7」道路和航线 原题来自：USACO 2011 Jan. Gold

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T$ 个城镇，编号为 $1$ 到 $T$ 。这些城镇之间通过 $R$ 条道路（编号为 $1$ 到 $R$ ）和 $P$ 条航线（编号为 $1$ 到 $P$ ）连接。每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ 到 $B_i$ ，花费为 $C_i$ 。

对于道路， $0 \le C_i \le 10^4$ ，然而航线的花费很神奇，花费 $C_i$ 可能是负数。道路是双向的，可以从 $A_i$ 到 $B_i$ ，也可以从 $B_i$ 到 $A_i$ ，花费都是 $C_i$ 。然而航线与之不同，只可以从 $A_i$ 到 $B_i$ 。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从 $A_i$ 到 $B_i$ ，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$ 。由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 $S$ 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

如果去掉航线可以发现原图变成了许多连通块

若把一个连通块看成一个节点,则发现连通块和航线组成 DAG

考虑 Topo sort 结合 Dijkstra

称连通块和航线组成的图为 $G$ ，连通块 $A$ 内部节点和道路的图为 $g_A$

假设 $s$ 所在的连通块为 $S$ ，对所有在 $G$ 中可从 $S$ 到达的连通块进行拓扑排序（否则算 deg 的时候会算多），一边拓扑一边 Dijkstra

大致是这个样子

q <- Topo_Queue;
while(q not empty):
    clr = q.front(); q.pop();
    
    heap <- Dijkstra_Priority_Queue;
    for (u 为 clr 节点)
        if (dis[u] != INF) heap.push(dis[u], u);
    
    while(heap not empty):
        u = heap.top(); heap.pop();
        for 从 u 出发道路:
            // 普通 Dijkstra 写法，略
        for 从 u 出发的航线(u, v, w):
            A 为 v 所在的连通块;
            if (A 不可从 S 出发到达) continue;
            deg[A]--;
            if (deg[A] == 0) q.push(A);
            dis[v] = min(dis[v], dis[u] + w)

2019-07-12发表2020-11-21更新OI / 题解

「NOIP 2009」最优贸易

题目概述

LOJ #2590. 「NOIP2009」最优贸易 C 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。

C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 $n$ 个城市的标号从 $1\sim n$ ，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 $n$ 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 C 国有 $5$ 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设 $1$ ~ $n$ 号城市的水晶球价格分别为 $4,3,5,6,1$ 。

阿龙可以选择如下一条线路： $1\to 2\to 3\to 5$ ，并在 $2$ 号城市以 $3$ 的价格买入水晶球，在 $3$ 号城市以 $5$ 的价格卖出水晶球，赚取的旅费数为 $2$ 。

阿龙也可以选择如下一条线路 $1\to 4\to 5\to 4\to 5$ ，并在第 $1$ 次到达 $5$ 号城市时以 $1$ 的价格买入水晶球，在第 $2$ 次到达 $4$ 号城市时以 $6$ 的价格卖出水晶球，赚取的旅费数为 $5$ 。

现在给出 $n$ 个城市的水晶球价格， $m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

¶ 解法一

Tarjan 缩点，重构图 + 判可达性（某一个强连通分量能否到达终点，若不能，则不能更新 ans ） + 跑 DAG 上的 DP

用了一个结论：Tarjan 逆序即为拓扑序

具体看代码吧

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int N = 100005;

std::vector<int> g[N], ng[N], fg[N];
int price[N];

int min[N], max[N], dfn[N], ins[N], low[N], color[N], dp[N];
std::stack<int> s;
int cnt = 0;
int T = 0;

void tarjan(int u) {
    dfn[u] = low[u] = ++T, ins[u] = 1;
    s.push(u);
    for (auto v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (ins[v]) {
            low[u] = std::min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u]) {
        int x;
        cnt++;
        // cerr << "cnt" << cnt << ":\n";
        do {
            x = s.top();
            s.pop();
            // cerr << x << ' ';
            color[x] = cnt, ins[x] = 0;
            min[cnt] = std::min(min[cnt], price[x]);
            max[cnt] = std::max(max[cnt], price[x]);
        } while (x != u);
        // cerr << endl;
    }
}

int coutable[N];

void dfs(int u) {
    if (coutable[u]) return;
    coutable[u] = 1;
    for (auto v : fg[u]) dfs(v);
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::memset(min, 0x3f, sizeof(min));
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    rep(i, 1, n) cin >> price[i];
    rep(i, 1, m) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(y);
        if (z - 1) g[y].push_back(x);
    }

    // tarjan
    tarjan(1);

    // rebuild
    rep(u, 1, n) {
        for (auto v : g[u])
            if (color[u] != color[v]) ng[color[u]].push_back(color[v]);
    }

    // connectable
    rep(u, 1, cnt) for (auto v : ng[u]) fg[v].push_back(u);
    dfs(color[n]);

    // topo + dp
    int ans = 0;
    std::memset(dp, 0x3f, sizeof(dp));
    per(u, cnt, 1) {
        dp[u] = std::min(dp[u], min[u]);
        if (coutable[u]) ans = std::max(ans, max[u] - dp[u]);
        for (auto v : ng[u]) {
            dp[v] = std::min(dp[v], dp[u]);
        }
    }

    cout << ans;
    return 0;
}

¶ 解法二

正图反图跑 SPFA转移方程定义为

d_{v} = \min\Big(\min_{u\rightarrow v}\{d_u\}, price_v\Big)

最后减一下

¶ 解法三

引用一下

构造分层图，具体看上面

2019-05-11发表2020-11-21更新OI / 题解

「一本通 1.1 练习 4」家庭作业题解

题目概述

LOJ #10008. 「一本通 1.1 练习 4」家庭作业

老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 $10$ ，要求在 $6$ 天内交，那么要想拿到这 $10$ 学分，就必须在第 $6$ 天结束前交。

每个作业的完成时间都是只有一天。例如，假设有 7 次作业的学分和完成时间如下：

作业号	期限	学分
$1$	$1$	$6$
$2$	$1$	$7$
$3$	$3$	$2$
$4$	$3$	$1$
$5$	$2$	$4$
$6$	$2$	$5$
$7$	$6$	$1$

最多可以获得 $15$ 学分，其中一个完成作业的次序为 $2,6,3,1,7,5,4$ ，注意可能还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

显然的贪心，先按学分 $s$ 从大到小，再按期限 $d$ 从后到前

考虑要安排一个作业，显然是越晚越好，故用一个二分区间，用一个数据结构查询、修改

这里选择二分套树状数组

2019-04-06发表2020-11-21更新OI / 题解

「Codeforces 1140E」Palindrome-less Arrays

题意

当一个数组 $b$ 至少有一个长度为奇数的连续回文子串时，称 $b$ 是坏的，否则称 $b$ 是好的。

给你长度为 $n$ 的数组 $a$ ，其中 $−1$ 可替换为任意从 $1$ 到 $k$ 的整数。

求好数组的个数，对 998244353 取模。

2019-02-09发表2020-11-21更新OI / 题解

「SCOI 2007」降雨量

~~我写这一题是因为 BZOJ 的讨论~~

线段树（动态开点）裸题，讨论有点烦

2019-02-06发表2020-11-21更新OI / 题解

「Codeforces 1111C」Creative Snap

题目链接

题目非常简单，只要实现不带修改的区间个数查询就可以了（还有适当剪枝

2019-02-04发表2020-11-21更新OI / 题解

「Codeforces 1111B」Average Superhero Gang Power

题目链接

首先观察求平均数的公式

avg=\frac{sum}{n}

所以我们要么改变 $sum$ 要么改变 $n$

如果忽略 $k$ 这个条件，我们有以下解法

我们先删数，数量记为为 $q$ ，剩余数的和记为 $s'$

avg = \frac{s'+m-q}{n-q}

对于一个数，我们要么舍弃，要么保留，显然的我们需要先删小的数（可以用 Exchange Argument 证明

2018-06-12发表2020-11-21更新OI / 题解

「NOIP 2008」传纸条

题目链接

为了方便，坐标先行后列。

设 $A = (1, 1),B = (m, n)$

不考虑不能传相同同学

从 A 到 B 再从 B 到 A $\sim$ 从 A 同时考虑两条路到 B

设 $i$ 为 A 到 B 线路 1 的行号， $j$ 为 A 到 B 线路 2 的行号， $k$ 为当前行列之和

对于线路1， $(i, k-i)$ 可从 $(i-1, k-i)$ 和 $(i, k-i-1)$ 推得

对于线路2， $(j, k-j)$ 可从 $(j-1, k-j)$ 和 $(j, k-j-1)$ 推得

故对于 $dp(i, j, k)$ 有四种情况。

\begin{aligned} dp(i, j, k) = a[i][k-i] + a[j][k -j] + \max\{ & dp(i, j, k-1), \\ & dp(i-1,j-1,k-1), \\ & dp(i-1,j,k-1), \\ & dp(i-1,j-1,k-1)\} \\ \end{aligned}

2017-11-04发表2020-11-21更新OI / 题解

奶牛玩杂技

非常棒的贪心题，我是完全没有想到解法。看了一波题解，证明如下：

若现在要处理两头牛 $a$ , $b$ 记 $w$ , $s$ 分别为 $w_a$ $s_a$ $w_b$ $s_b$

2017-10-29发表2020-11-21更新OI / 题解

「NOIP 2004」合唱队形

记忆化搜索

定义一个 solve(x, lim, dir)

x 表示处理完的层数，所有x == n是就return

lim 是限制条件

dir 表示方向，true为向上，false向下

当 dir == true 时，显然有以下情况

若 height[x+1] > lim
选 solve(x+1, height[x+1], true)
不选 solve(x+1, lim, true)
若 height[x+1] < lim
不选 solve(x+1, lim, true)
选，并改方向 solve(x+1, lim, false)
若 height[x+1] == lim
只能跳 solve(x+1, lim, false)

当 dir == false时，不能再换方向，显然有以下情况

若 height[x+1] > lim
不选 solve(x+1, lim, false)
若 height[x+1] < lim
选 solve(x+1, height[x+1], false)

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
int t[101], dp[101][231][2], n, ans=200;
int solve(int x, int max,bool dir){
    if (x == n){
        return 0;
    }
    if (dp[x][max][dir]!=-1) return dp[x][max][dir];
    int& ans = dp[x][max][dir];
    if (dir){
        if (t[x+1] < max) return ans = std::min(solve(x+1,max,true)+1,solve(x+1,t[x+1],false));
        if (t[x+1] > max) return ans = std::min(std::min(solve(x+1,t[x+1],true),solve(x+1,max,true)+1), solve(x+1,t[x+1],false));
        return ans = solve(x+1,max,true)+1;
    }else{
        if (t[x+1] < max) return ans = std::min(solve(x+1,t[x+1],false),solve(x+1,max,false)+1);
        if (t[x+1] >= max) return ans = solve(x+1,max,false)+1;
    }
}
int main(){
    std::memset(dp, -1, sizeof(dp));
    int i;
    cin >> n;
    for (i=1;i<=n;++i)
        cin >> t[i];
    cout << solve(0,0,true);
    return 0;
}

「USACO 2011 Jan. Gold」道路和航线

「NOIP 2009」最优贸易

¶ 解法一

¶ 解法二

¶ 解法三

「一本通 1.1 练习 4」家庭作业题解

「Codeforces 1140E」Palindrome-less Arrays

题意

「SCOI 2007」降雨量

「Codeforces 1111C」Creative Snap

「Codeforces 1111B」Average Superhero Gang Power

「NOIP 2008」传纸条

奶牛玩杂技

「NOIP 2004」合唱队形

分类

标签

作业号	期限	学分
$1$	$1$	$6$
$2$	$1$	$7$
$3$	$3$	$2$
$4$	$3$	$1$
$5$	$2$	$4$
$6$	$2$	$5$
$7$	$6$	$1$

作业号	期限	学分
$1$	$1$	$6$
$2$	$1$	$7$
$3$	$3$	$2$
$4$	$3$	$1$
$5$	$2$	$4$
$6$	$2$	$5$
$7$	$6$	$1$

作业号	期限	学分
$1$	$1$	$6$
$2$	$1$	$7$
$3$	$3$	$2$
$4$	$3$	$1$
$5$	$2$	$4$
$6$	$2$	$5$
$7$	$6$	$1$