Loading... ## 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 ### 代码 ```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; } } } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/402.html">https://www.starroad.top/archives/402.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:July 21st, 2019 at 07:47 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat