前言
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接
题目大意：n个点在一维坐标轴上，坐标x[i]从小到大。
每个点会选择Left或者Right的方向前进，速度v=1，求首次相遇的时间，如果所有点都不会相遇则输出-1。
样例数据：
input
4
RLRL
2 4 6 10
output
1
input
3
LLR
40 50 60
output
-1
数据范围 (1 ≤ n ≤ 200 000) ， (0 ≤ x[i] ≤ 109)
代码实现：
int right = -1;
for (int i = 0; i < n; ++i) {
if (str[i] == 'R') {
right = i;
}
else {
if (right != -1 && a[i] != a[right]) {
if (ret == -1) {
ret = (a[i] - a[right]) / 2;
}
else {
ret = min(ret, (a[i] - a[right]) / 2);
}
}
}
}
题目解析：
对于点i，有两种碰撞情况：
1、方向是L，遇到左边的点方向是R；
2、方向是R，遇到右边的店方向是L；
假设点i和点j是碰撞的点，那么点i的情况1就是点j的情况2；
那么对于点i只考虑左边的点即可；
题目变成：对于每个点，求左边最近的方向为R 的点。
B
题目链接
题目大意：n*m的棋盘上有若干点，找一个点横竖能覆盖所有点。
输入数据中的*表示点。
n and m (1 ≤ n, m ≤ 1000)
Examples
input
3 4
.*..
....
.*..
output
YES
1 2
方法1：
代码实现：
// 假设符合的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
Node tmp;
tmp.x = i;
tmp.y = j;
nodes.insert(tmp);
}
}
// 检查假设的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
if (str[i][j] == '*') {
set<Node>::iterator it = nodes.begin();
while (it != nodes.end()) {
if (it->x == i || it->y == j) {
++it;
}
else {
nodes.erase(it++);
}
}
if (nodes.size() == 0) {
OK = 0;
}
}
}
}
题目解析：
假设所有点符合，用set来存放所有的点，每遇到一个点，把不符合的去掉；
时间复杂度为O(NM*LogN)，复杂度的关键在于set的构建。
方法2：
代码实现：
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>c[i][j];
if(c[i][j]=='*'){
k++;
a[i]++;
b[j]++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++) {
s=a[i]+b[j];
if(c[i][j]=='*'){
s--;
}
if(s==k) {
cout<<"YES"<<endl<<i+1<<" "<<j+1;
return 0;
}
}
}
题目解析：
假设某一点符合，求这一个点覆盖的点数是否包括其他所有需要覆盖的点；
事先统计每行每列对应的点数，求点覆盖点数时通过每行每列的值可以较快计算出来。
时间复杂度为O(NM)。
C
题目链接
题目大意：
小明放了n天暑假，他非常喜欢去图书馆学习和去体育馆锻炼。
暑假里每天有4种情况：
- 0、体育馆关门，图书馆关门；
- 1、体育馆关门，图书馆开门；
- 2、体育馆开门，图书馆关门；
- 3、体育馆开门，图书馆开门；
但小明不希望连续两天学习或者连续两天锻炼，如果不锻炼也不学习那么小明会在家颓废。
现在已知n天暑假里每天的图书馆、体育馆开关门情况，问小明最少会在家颓废几天。
样例
input
7
1 3 3 2 1 2 3
output
0
样例解释：小明可以在第1、3、5、7天选择学习，2、4、6选择运动，故而小明最少会在家颓废0天。
n (1 ≤ n ≤ 100)
代码实现：
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
d[i][0] = min(min(d[i - 1][0] + 1, d[i - 1][1] + 1), d[i - 1][2] + 1);
if (k == 0) {
d[i][1] = d[i][2] = N;
}
if (k == 1) { // can to contest
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = N;
}
if (k == 2) { // can to gym
d[i][1] = N;
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
if (k == 3) {
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
}
cout << min(min(d[n][0], d[n][1]), d[n][2]) << endl;
题目解析：
典型的动态规划。
d[i][j]表示第i天，状态为j时的最小休息天数。
j = 0表示都不去；
j = 1表示去contest；
j = 2表示去gym；
这样j = 0可以由前面三种状态转换过来；
j = 1只能由0和2转换；
j = 2只能由1和2转换；
然后动态规划一遍得最优解。
D
题目链接
题目大意：有n个点。
有n个数字a[i]，表示第i个点的parent节点。
问使其变成一棵树，最少需要修改多少条边，并且把所有值输出。
n (2 ≤ n ≤ 200 000)
Examples
input
4
2 3 3 4
output
1
2 3 4 4
代码实现：
lld find(lld x) {
lld ret = f[x];
if (ret != x) {
ret = find(ret);
}
return f[x] = ret;
}
int main() {
for (int i = 1; i <= n; ++i) {
if (i != root) {
lld x = find(i);
lld y = find(a[i]);
if (x == y) {
++ans;
if (!root) {
root = x;
}
a[i] = root;
}
else {
f[x] = f[y];
}
}
}
}
题目解析：
n个点，n条边。如果是树必然是一条边指向自己，其余n-1条边没有环。（有且仅有一个环）
那么假设有一个根节点root，当出现环的时候，直接将环某个点指向root即可；
需要修改的数量=环的数量 - 1。
总结
两个关键词：动态规划（C题）、并查集（D题）。
网友评论