2019-2020 ACM-ICPC Pacific Northwest Regional Contest
A. Radio Prize
思路：预处理出三个值：各子树的大小，各子树点权之和，各个节点到1号节点的距离。子树划分是以树根作为划分的依据。那么，距离可以这么推。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int maxn
= 100010, maxm
= maxn
* 2;
typedef long long ll
;
typedef pair
<ll
, ll
> P
;
int h
[maxn
], e
[maxm
], ne
[maxm
], idx
;
int N
;
ll wv
[maxn
], we
[maxm
];
ll sz
[maxn
], sum_wv
[maxn
], d
[maxn
], A
[maxn
], B
[maxn
], W
;
void add(int a
, int b
, int c
){
e
[idx
] = b
, ne
[idx
] = h
[a
], we
[idx
] = c
, h
[a
] = idx
++;
}
P
dfs1(int u
, int fa
){
P p
= {1, wv
[u
]};
for(int i
= h
[u
]; i
!= -1; i
= ne
[i
]){
int v
= e
[i
];
if(v
== fa
) continue;
d
[v
] = d
[u
] + we
[i
];
P son
= dfs1(v
, u
);
p
.first
+= son
.first
, p
.second
+= son
.second
;
}
sz
[u
] = p
.first
, sum_wv
[u
] = p
.second
;
return p
;
}
void dfs2(int u
, int fa
){
for(int i
= h
[u
]; i
!= -1; i
= ne
[i
]){
int v
= e
[i
];
if(v
== fa
) continue;
A
[v
] = A
[u
] + (N
- 2 * sz
[v
]) * we
[i
];
B
[v
] = B
[u
] + (W
- 2 * sum_wv
[v
]) * we
[i
];
dfs2(v
, u
);
}
}
int main(){
memset(h
, -1, sizeof h
);
scanf("%d", &N
);
for(int i
= 1; i
<= N
; i
++){
scanf("%d", &wv
[i
]);
W
+= wv
[i
];
}
for(int i
= 1; i
< N
; i
++){
int a
, b
, c
;
scanf("%d%d%d", &a
, &b
, &c
);
add(a
, b
, c
), add(b
, a
, c
);
}
dfs1(1, -1);
for(int i
= 1; i
<= N
; i
++){
A
[1] += d
[i
];
B
[1] += wv
[i
] * d
[i
];
}
dfs2(1, -1);
for(int i
= 1; i
<= N
; i
++){
printf("%lld\n", wv
[i
] * A
[i
] + B
[i
]);
}
return 0;
}
B. Perfect Flush
题意：给出n个数
∈
[
1
,
k
]
\in [ 1 , k ]
∈[1,k]，找出它的子序列中，字典序最小的 1~k 的全排列。用单调栈去解题（单调增大）。首先统计每个数最后出现的一个位置。然后遍历这个序列，我们称现在遍历到的这个序列的数为
x
i
x_i
xi，做一下操作
如果
x
i
x_i
xi还未出现在答案序列，并且答案序列不为空，就比较
x
i
x_i
xi 和答案序列中最后一个数的大小。如果大于原序列中的最后一个数，直接放到答案序列就行，如果小于，就看后面还是否会出现当前答案序列的最后一个数，如果后面不会再出现了，也直接加到答案序列。如果
x
i
x_i
xi 已经出现在答案序列，跳过。
#include<cstdio>
#include<algorithm>
using namespace std
;
const int maxn
= 200010;
int a
[maxn
], stk
[maxn
], p
[maxn
], N
, K
;
bool vis
[maxn
];
int main() {
scanf("%d%d", &N
, &K
);
for (int i
= 1; i
<= N
; i
++) {
scanf("%d", &a
[i
]);
p
[a
[i
]] = i
;
}
int top
= 0;
for (int i
= 1; i
<= N
; i
++) {
if (vis
[a
[i
]]) continue;
while (top
&& a
[i
] < stk
[top
] && p
[stk
[top
]] > i
) {
vis
[stk
[top
]] = false;
--top
;
}
stk
[++top
] = a
[i
];
vis
[a
[i
]] = true;
}
for (int i
= 1; i
<= K
; i
++) printf("%d%c", stk
[i
], i
== K
? '\n' : ' ');
return 0;
}
E. Rainbow Strings
统计每个字母出现的次数
c
n
t
1
,
c
n
t
2
,
.
.
.
,
c
n
t
n
cnt_1, cnt_2, ... , cnt_n
cnt1,cnt2,...,cntn. 然后答案就是
c
n
t
1
∗
c
n
t
2
∗
.
.
.
∗
c
n
t
n
cnt_1*cnt_2*...*cnt_n
cnt1∗cnt2∗...∗cntn.原因很简单，对于一个字母 a：不选、选第一个位置、选第二个位置……有 cnt + 1 种选择的方法。代码略。
I. Error Correction
由于每交换一次就改变了一次排列逆序对的奇偶性，因此这个图没有奇数环，是个二分图。二分图建边一定要注意，之前都学错了。是二分图两个部分，一个部分全部向另一个部分建单向边，这样才能保证匈牙利算法是正确的。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std
;
const int maxn
= 510, maxm
= 125000;
int h
[maxn
], e
[maxm
], ne
[maxm
], idx
;
unordered_map
<string
, int> id
;
int N
, match
[maxn
];
bool vis
[maxn
];
void add(int a
, int b
) {
e
[idx
] = b
, ne
[idx
] = h
[a
], h
[a
] = idx
++;
}
int rev(string
& s
) {
int len
= s
.size();
int res
= 0;
for (int i
= 0; i
< len
; i
++) {
for (int j
= 0; j
< i
; j
++) {
if (s
[i
] < s
[j
]) res
++;
}
}
return res
;
}
bool find(int u
) {
for (int i
= h
[u
]; i
!= -1; i
= ne
[i
]) {
int v
= e
[i
];
if (vis
[v
]) continue;
vis
[v
] = true;
if (match
[v
] == 0 || find(match
[v
])) {
match
[v
] = u
;
return true;
}
}
return false;
}
int main() {
memset(h
, -1, sizeof h
);
scanf("%d", &N
);
for (int i
= 1; i
<= N
; i
++) {
string s
;
cin
>> s
;
id
[s
] = i
;
}
for (auto p
: id
) {
string s
= p
.first
;
int len
= s
.size();
for (int i
= 0; i
< len
; i
++) {
for (int j
= 0; j
< i
; j
++) {
swap(s
[i
], s
[j
]);
if (id
.count(s
) && (rev(s
) & 1)) add(id
[p
.first
], id
[s
]);
swap(s
[i
], s
[j
]);
}
}
}
int ans
= 0;
for (int i
= 1; i
<= N
; i
++) {
memset(vis
, false, sizeof vis
);
if (find(i
)) {
ans
++;
}
}
printf("%d\n", N
- ans
);
return 0;
}
Maze Connect
题意：求删掉多少边使得没有封闭图形，而只要存在封闭图形，总能通过删一条边，使得封闭图形的数量减少1。因此本质上还是求封闭图形的数量。思路：其实这个题就是求连通块的个数，难点在于建图，原图没法用，需要建立一个点图，对于原图的每一个字符，将其变为一个2*2的矩阵，’'是从左上到右下的赋值为1，‘/’是从右上到左下的赋值为1，‘.’不变化就是初始值为0.然后遍历这个新图的连通块的个数。注意，所有原本就能走到方格之外的点，会和最外面那一圈0形成一个连通块儿，因此最终答案数就是：连通块儿的数目 - 1.
#include<iostream>
#include<algorithm>
using namespace std
;
const int maxn
= 2010;
int field
[maxn
][maxn
];
int N
, M
;
int dx
[] = { 0, 0, 1, -1 }, dy
[] = { 1, -1, 0, 0 };
void dfs(int x
, int y
) {
field
[x
][y
] = 1;
for (int i
= 0; i
< 4; i
++) {
int nx
= x
+ dx
[i
], ny
= y
+ dy
[i
];
if (nx
< 0 || nx
> N
+ 1 || ny
< 0 || ny
> M
+ 1 || field
[nx
][ny
]) continue;
dfs(nx
, ny
);
}
}
int main() {
scanf("%d%d", &N
, &M
);
char c
;
for (int i
= 1; i
<= N
; i
++) {
for (int j
= 1; j
<= M
; j
++) {
cin
>> c
;
if (c
== '\\') field
[2 * i
- 1][2 * j
- 1] = field
[2 * i
][2 * j
] = 1;
else if (c
== '/') field
[2 * i
- 1][2 * j
] = field
[2 * i
][2 * j
- 1] = 1;
}
}
N
*= 2, M
*= 2;
int ans
= 0;
for (int i
= 1; i
<= N
; i
++) {
for (int j
= 1; j
<= M
; j
++) {
if (field
[i
][j
] == 0) dfs(i
, j
), ans
++;
}
}
cout
<< ans
- 1 << endl
;
return 0;
}
