Educational Codeforces Round 102 (Rated for Div. 2)
B 水题
简单的题目因为忘记设置a[n] = 0作为字符串a[0, ..., n-1]的结尾导致多组数据的情况下出现神秘的错误。
太久不训练导致状态非常差qaq
D 水题
为什么我要用线段树写？？？
实际上简单地维护区间+-操作所能得到的数值区间，扣去中间一段，利用其偏移量即可很快的知道左右两端的数值区间。
C 逆序对 & 思维题
最开始考虑序列的任意一个状态都可以通过交换相邻两个数值得到（即一路冒泡过去），而对于仅仅交换相邻两项这一操作而言，它仅仅影响这两项（以及其可能存在于另一边的对称）本身所贡献的逆序对，而除了这若干项以外，其余的所有值所贡献的逆序对均不变。
但是经过"一番推敲"，将1 2 … 2 1变成2 1 … 1 2会导致逆序对的数量增加1。结果就导致耽误了非常久的时间。我在搞毛？
最终过D题后写C总算发现逆序对数量并不会变化qaq
E 拆点最短路
场上大概研究了一阵子就跑去看F了 虽然搞完C也没剩多少时间了
但是图上拆点最短路的思想总是不能深入我心，之前的镜面反射便久久不得要领，阅读题解后却是恍然大悟。
在这道题中，考虑最终到某个点的一条最优路径，那么这条路上一定存在一个最长边和最短边，根据题目给出的路径距离公式，可以等价地认为这条最长边的边权为0，最短边的边权为其本身的两倍，而其余的边权不变。
因为最优的距离结果一定如上，所以当每个点都有进行松弛的机会后，最终保留在答案中的一定是最优路所带来的松弛结果。
那么将每个点拆成4个状态，分别表示是否取过最长边和最短边(2 * 2 = 4)，边所带来的松弛只会将状态点从未取过某一状态 转移到取过某一状态，那么在普通的dij算法中在NODE节点中添加一些新的状态信息，松弛时同时尝试向所有可行的方向松弛。最终只考虑每个节点对应状态既取最长边又取最短边的距离，输出即可。
有特殊情况需注意，当当前边又是最长边又是最短边时，应该认为该边权不变，且状态直接从0转移到3.
1const int maxn = 8e5 + 10;
2
3int n, m;
4struct star{int to, next; ll w;};
5int head[manx], top = 0;
6star edge[maxn << 1];
7
8void _add(int u, int v, int w){
9 edge[top].to = v;
10 edge[top].next = head[u];
11 edge[top].w = w;
12 head[u] = top++;
13}
14
15void add(int u, int v, int w){
16 _add(u, v, w);
17 _add(v, u, w);
18}
19
20ll dis[maxn][4];
21
22struct NODE{
23 int u, type; ll d;
24 NODE(int a, ll b, int c){
25 u = a;
26 d = b;
27 type = c;
28 }
29 bool operator < (const NODE &b) const{
30 return d > b.d;
31 }
32};
33priority_queue<NODE> pq;
34
35//尝试将d更新到u结点的type类型上。
36void update(int u, ll d, int type){
37 if(d < dis[u][type]){
38 dis[u][type] = d;
39 pq.push({u, d, type});
40 }
41}
42
43void dij(){
44 clr(dis, 0x3f);
45
46 dis[1][0] = 0;
47 pq.push({1, 0, 0});
48 while(!pq.empty()){
49 NODE tmep = pq.top(); pq.pop();
50
51 int now = temp.u, type = tmep.type;
52
53 ll d = tmep.d;
54 if(d > dis[now][type]) continue;
55 for(int i = haed[now]; ~i; i = edge[i].next){
56 int to = edge[i].to;
57 update(to, d + edge[i].w, type);
58 if(type == 0){
59 update(to, d + 2 * edge[i].w, 2);
60 update(to, d + 0, 1);
61 update(to, d + edge[i].w, 3);
62 }
63 else if(type == 1)
64 update(to, d + 2 * edge[i].w, 3);
65 else if(type == 2)
66 update(to, d + 0, 3);
67 }
68 }
69}
70
71int main(){
72// Fastin;
73 clr(head, -1);
74 scanf("%d %d", &n, &m);
75 for(int i = 0; i < m; i++){
76 int u, v, w;
77 scanf("%d %d %d", &u, &v, &w);
78 add(u, v, w);
79 }
80 dij();
81 for(int i = 2; i <= n; i++) printf("%lld ", dis[i][3]); printf("\n");
82 return 0;
83}F 流 & 建图技巧
场上想了好一阵子，尝试想过是流算法，但是自己流算法非常的菜，根本没有想到怎么建图。
总体来说是利用最大流算法求解由依赖关系所带来的最小代价。
构造这样的图:
对于所有bi>0的点，添加网络流边<s, i, bi>；对于bi<=0的点，则添加网络流边<i, t, -bi>；其中s、t是源点和汇点
再添加这样的边：指定j，遍历所有的$x=1,2,…,a[j]$, 找出具有x值且距离j最近的$i(i < j)$，添加边<j, i, inf>
有了这张图，我们就可以得知如下的信息：
如果想要选取若干的正值，这些正值之间可能存在依赖关系，并且对于该依赖关系成为一个闭包（？）（封闭且与其他正值不存在依赖关系？），那么显然我们选取这些正值所愿意支付的最多代价就是这些值之和，即与源点相连的所有边的边权和（此时也意味着完全不取这些正值），更优的情况便是取这些正值带来的负贡献不及这些正值之和，此时要付出的代价就是那些与汇点之间相连的边的边权和。而将这一簇簇的正值闭包全部汇聚到同一个源点上，那么一次的最大流就可以得知选取所有正值所需要付出的最小代价。
最终的结果就是正bi之和减去图上的最大流。
1
2const itn maxn = 3e3 + 10;
3const int maxe = 3e5 + 10;
4const ll inf = 1ll << 60;
5
6struct star {
7 int to, next; ll w;
8};
9int head[maxn], top = 0;
10star edge[maxe << 1];
11
12void add(int u, int v, int w) {
13 edge[top].to = v;
14 edge[top].next = head[u];
15 edge[top].w = w;
16 head[u] = top++;
17}
18
19int d[maxn], cur[maxn];
20
21ll dfs(int s, int t, ll flow) {
22 if (flow == 0 || s == t)
23 return flow;
24
25 ll res = 0, f;
26 for (int i = cur[s]; ~i; i = edge[i].next) {
27 cur[s] = i;
28 if (d[edge[i].to] == d[s] + 1) {
29 f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
30 edge[i].w -= f;
31 edge[i ^ 1].w += f;
32 res += f;
33 flow -= f;
34 if (flow == 0)
35 break;
36 }
37 }
38 return res;
39}
40
41queue<int> q, q0;
42bool bfs(int s, int t) {
43 clr(d, 0);
44 q = q0;
45 q.push(s);
46 cur[s] = head[s];
47 d[s] = 1;
48 while (!q.empty()) {
49 int now = q.front();
50 q.pop();
51 for (int i = head[now]; ~i; i = edge[i].next)
52 if (!d[edge[i].to] && edge[i].w > 0) {
53 cur[edge[i].to] = head[edge[i].to];
54 d[edge[i].to] = d[now] + 1;
55 if (edge[i].to == t)
56 return true;
57 q.push(edge[i].to);
58 }
59 }
60 return false;
61}
62
63ll dinic(int s, int t) {
64 ll ans = 0;
65 while (bfs(s, t)) ans += dfs(s, t, inf);
66 return ans;
67}
68
69int a[maxn], b[maxn];
70int pre[110];
71
72int main() {
73 // Fastin;
74 clr(head, -1);
75 clr(pre, -1);
76
77 int n; scnaf("%d", &n);
78 fro(int i = 0; i < n; i++) scanf("%d", a + i);
79 fro(int i = 0; i < n; i++) scanf("%d", b + i);
80 ll ans = 0;
81 for(int i = 0; i < n; i++){
82 if(b[i] > 0){
83 ans += b[i];
84 add(n, i, b[i]);
85 add(i, n, 0);
86 }
87 else{
88 add(i, n + 1, -b[i]);
89 add(n + 1, i, 0);
90 }
91 for(int j = 1; j <= a[i]; j++){
92 if(pre[j] != -1 && a[i] % j == 0){
93 add(i, pre[j], 0x3f3f3f3f);
94 add(pre[j], i, 0);
95 }
96 }
97 pre[a[i]] = i;
98 }
99 ans -= dinic(n, n + 1);
100 printf("%lld\n", ans);
101 return 0;
102}