CWOI 2019 NOIP 暑假测试四

Author：薇薇安
发布时间：July 21, 2019
227views
No comments
2111 words
Categories： OI

## Problem A 序列

### 题面

给定一个长度为 n 的数列$a_1,a_2,\cdots,a_n$，每次可以选择一个区间$[l,r]$，使这个区间内的数都加$1$或者都减$1$。请问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

### 题解

把原序列差分，考虑所有的$a_i−a_{i−1}(1 \leq i \leq n+1)$，当$i \neq 1$且$i \neq n+1$时都需要等于$0$。因此统计一下需要加多少次、减多少次。由于要求操作次数最少，因此其中的加减需要抵消。即如果有$s_1$次减操作、$s_2$次加操作，那么需要有 $min(s1,s2)$次操作选出其中的两个抵消。由于是差分数组，对应到原序列中就是区间$+1$或$-1$。剩下的操作可以选择用$a_1−a_0$ 或者 $a_{n+1}−a_n$。选择$a_1−a_0$的话相当于序列的值改变，否则不改变。因此序列改变的范围是$[0,|s1−s2|]$，取值的范围再$+1$即可。因此只需要统计出每一个数与前一个数差了多少即可。时间复杂度$O(n)$。

### 代码

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 3200010;
const int inf = 0x3f3f3f3f;
typedef pair< int, int > pi;
int ans[maxn];
int tot, head[maxn];
int M, N;
int dis[2][maxn];
int T;
struct node {
    int v, next;
    int w;
} e[maxn];
inline void addedge( int u, int v, int w ) {
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].next = head[u];
    head[u] = tot;
}
inline void dijkstra( int st, int num ) {
    memset( dis[num], 0x3f3f3f3f, sizeof( dis[num] ) );
    priority_queue< pi, vector< pi >, greater< pi > > q;
    dis[num][st] = 0;
    q.push( make_pair( dis[num][st], st ) );
    while ( !q.empty() ) {
        int u = q.top().second;
        q.pop();
        for ( int i = head[u]; i; i = e[i].next ) {
            int v = e[i].v;
            if ( dis[num][v] > dis[num][u] + e[i].w ) {
                dis[num][v] = dis[num][u] + e[i].w;
                q.push( make_pair( dis[num][v], v ) );
            }
        }
    }
    return;
}
int main() {
    int u;
    int w;
    cin >> T;
    int Cas = 0;
    while ( T-- ) {
        tot = 0;
        memset( head, 0, sizeof( head ) );
        cin >> N >> M;
        int pos = N + 1;
        int num;
        for ( int i = 1; i <= M; i++ ) {
            cin >> w >> num;
            for ( int j = 1; j <= num; j++ ) {
                cin >> u;
                addedge( pos, u, w );
                addedge( u, pos, w );
            }
            pos++;
        }
        dijkstra( 1, 0 );
        dijkstra( N, 1 );
        int mindis = inf;
        int tot2 = 0;
        for ( int i = 1; i <= N; i++ ) {
            mindis = min( mindis, max( dis[0][i], dis[1][i] ) );
        }
        if ( mindis == inf )
            cout << "Case #" << ++Cas << ": Evil Wkr" << endl;
        else {
            cout << "Case #" << ++Cas << ": " << mindis / 2 << endl;
            for ( int i = 1; i <= N; i++ ) {
                if ( max( dis[0][i], dis[1][i] ) == mindis ) {
                    ans[++tot2] = i;
                }
            }
            for ( int i = 1; i <= tot2 - 1; i++ ) {
                cout << ans[i] << " ";
            }
            cout << ans[tot2] << endl;
        }
    }
}
```

## Problem B [HAOI2015]树上染色

该题目为[洛谷P3177](https://www.luogu.org/problemnew/show/P3177)原题。

### 题面

有一棵点数为$N$的树，树边有边权。给你正整数$K \in [0,N]$，你要在这棵树中选择$K$个点，将其染成黑色，并将其他的点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

### 题解

$f_{i,j}$表示以$i$为根的子树中选了$j$个黑点的最大获益。考虑由子树转移到根，连接子树和根的路径的贡献为子树中所有黑（白）点和子树外所有黑（白）点的配对个数乘以边权。

### 代码

```cpp
#include <iostream>
using namespace std;
const int MAXN = 100020;
int main() {
    ios::sync_with_stdio( false );
    long long a[MAXN] = { 0 }, b[MAXN] = { 0 };
    long long sum = 0;
    int n;
    long long ans1 = 0, ans2 = 0;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    for ( int i = 2; i <= n; i++ ) {
        if ( b[i] > 0 )
            ans1 += b[i];
        if ( b[i] < 0 )
            ans2 -= b[i];
    }
    sum = a[n] - a[1];
    if ( sum >= 0 )
        cout << sum + ans2 << endl << abs( sum ) + 1 << endl;
    else
        cout << -sum + ans1 << endl << abs( sum ) + 1 << endl;
    return 0;
}
```

## Problem C 看电影

### 题面

一天`wkr`想和`zjk`一起去看电影，然而他们相隔太远，他们需要选择一个集合点，然后再去看电影。假设我们将`wkr`和`zjk`之间的街道划分为$n$区，`wkr`在$1$区，`zjk`在$n$区，给出$m$种传送阵，同一种传送阵的区可以相互传送，传送时间为$t_i$。问`wkr`和`zjk`最少花费多少时间长能见面，他们已经迫不及待的想去看电影了！

### 题解

这道题难点在于建图。每个集合外虚建一个点$A_i$，然后，$i$集合里面的点到达$A$的距离为$t/2$。
这样$1\rightarrow2$也是$4$，很巧妙的减少了边。考虑有浮点数误差，所以各点到`A`以$t$计算。最后结果除以$2$。建图之后就是一道比较裸的最短路问题，用`dijkstra`分别求出$1$为起点和$n$为起点到各点的时间。第$i$点的时间为，$time[i]=max(dist[0][i],dist[1][i])$。求出最小的$time$即可。

!>要用 long long 存 t 和 dist

### 代码

Last modification：July 21st, 2019 at 07:47 pm

如果您觉得我的文章有用，给颗糖糖吧~