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)$。
代码
#include
#include
#include
#include
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原题。
题面
有一棵点数为$N$的树，树边有边权。给你正整数$K \in [0,N]$，你要在这棵树中选择$K$个点，将其染成黑色，并将其他的点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。
题解
$f_{i,j}$表示以$i$为根的子树中选了$j$个黑点的最大获益。考虑由子树转移到根，连接子树和根的路径的贡献为子树中所有黑（白）点和子树外所有黑（白）点的配对个数乘以边权。
代码
#include
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
代码
#include
#include
#include
#include
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;
}
}
}
此处评论已关闭