Codeforces Round #303(Div.2)

Codeforces

Contests 链接：Codeforces Round #303(Div.2)
过题数：4
排名：2/16

A. Toy Cars

题意

给出一个二维矩阵，其中第 $i$ 行第 $j$ 列表示第 $i$ 辆车与第 $j$ 辆车相遇后的状态，$-1$ 表示两辆车没有相遇，题目保证 $-1$ 只会出现在对角线上，$0$ 表示两辆车相遇后不回头，$1$ 表示第 $i$ 辆车相遇后回头，$2$ 表示第 $j$ 辆车相遇后回头，$3$ 表示第 $i$ 辆车与第 $j$ 辆车相遇后，两辆车都回头。如果某一辆车在与其他车相遇后从没有回头过，那么这辆车就是一辆“好车”，求好车的数量。

数据范围

$1\leq n\leq100\\-1\leq A_{ij}\leq3$

题解

先假设所有的车都是“好车”，回头一次则这辆车就不是好车，用一个数组来标记状态，最后输出结果即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
#include <io.h>
#include <conio.h>
using namespace std;
#define LL long long
const int maxn = 200;
int n, cnt;
int ans[maxn];
bool bad[maxn];
int num[maxn][maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        memset(bad, 0, sizeof(bad));
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                scanf("%d", &num[i][j]);
                if(num[i][j] == 1) {
                    bad[i] = true;
                } else if(num[i][j] == 2) {
                    bad[j] = true;
                } else if(num[i][j] == 3) {
                    bad[i] = true;
                    bad[j] = true;
                }
            }
        }
        cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(!bad[i]) {
                ans[cnt++] = i;
            }
        }
        printf("%d\n", cnt);
        if(cnt != 0) {
            for(int i = 0; i < cnt; ++i) {
                if(i != 0) {
                    printf(" ");
                }
                printf("%d", ans[i]);
            }
            printf("\n");
        }
    }
    return 0;
}

B. Equidistant String

题意

定义两个字符串的距离为：两个字符串所有不同字符的个数，给定两个字符串 $s$ 和 $t$，输出任意一个到这两个字符串距离相等的字符串 $p$，如果不存在字符串 $p$ 满足上述条件，则输出 "$impossible$".

数据范围

$1\leq len_s,len_t\leq10^5$
所有字符串只有'0','1'两种字符。

题解

先计算两个字符串的距离 $dis$，如果为奇数，则不存在字符串 $p$，否则令 $dis_{ps}=\frac{dis_{st}}{2},dis_{pt}=\frac{dis_{st}}{2}$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
#include <io.h>
#include <conio.h>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int cnt;
char s[maxn], t[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%s%s", s, t) != EOF) {
        cnt = 0;
        for(int i = 0; s[i]; ++i) {
            if(s[i] != t[i]) {
                ++cnt;
            }
        }
        if(cnt % 2 == 1) {
            printf("impossible\n");
            continue;
        }
        int ccnt = cnt / 2;
        for(int i = 0; s[i]; ++i) {
            if(s[i] == t[i]) {
                printf("%c", s[i]);
            } else {
                if(cnt > ccnt) {
                    printf("%c", s[i]);
                    --cnt;
                } else {
                    printf("%c", t[i]);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

C. Woodcutters

题意

最初有 $n$ 棵树排列成一行，每棵树的位置为 $x_i$，高度为 $h_i$，一个伐木工人砍树，每砍一棵树，这棵树就会往左或者往右倾倒，这棵树就占据了 $[x_i-h_i,x_i]$ 或者 $[x_i,x_i+h_i]$ 的区间，且初始每棵树占据区间 $[x_i,x_i]$，要求每棵树被砍倒的时候，在它倒下的范围内没有其他树种植或者在这个区间内。

数据范围

$1\leq n\leq 10^5\\1\leq x_i,h_i\leq10^9$

题解

先在负无穷的位置种第 $0$ 棵树，高度为 $0$，在正无穷的位置种第 $n+1$ 棵树，高度为 $0$，用一个变量 $flag$ 标记第 $i-1$ 树是否向右倒，如果第 $i-1$ 棵树是向右倒的，就判断 $h_{i-1}+h_{i}$ 是否小于 $x_i-x_{i-1}$ ，如果小于，则第 $i$ 棵树向左倒，否则判断 $h_i$ 是否小于 $x_{i+1}-x_i$，如果小于，则这棵树向右倒，否则这棵树就不倒。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
#include <io.h>
#include <conio.h>
using namespace std;
#define LL long long
const LL INF = 1e18;
const int maxn = 100000 + 100;
struct Node {
    LL x, h;
};
int n, ans;
Node node[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        ans = 0;
        bool flag = false;
        node[0].x = -INF;
        node[n + 1].x = INF;
        node[0].h = node[n + 1]. h = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d%I64d", &node[i].x, &node[i].h);
        }
        for(int i = 1; i <= n; ++i) {
            if(flag) {
                if(node[i].x - node[i - 1].x > node[i].h + node[i - 1].h) {
                    ++ans;
                    flag = false;
                } else {
                    if(node[i + 1].x - node[i].x > node[i].h) {
                        flag = true;
                        ++ans;
                    } else {
                        flag = false;
                    }
                }
            } else {
                if(node[i].x - node[i - 1].x > node[i].h) {
                    ++ans;
                    flag = false;
                } else {
                    if(node[i + 1].x - node[i].x > node[i].h) {
                        flag = true;
                        ++ans;
                    } else {
                        flag = false;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Queue

题意

有 $n$ 个人在排队，排在队首的人先被服务，每个人都有一个服务时间 $t_i$，如果某个人的等待时间超过服务时间，这个人就会感到不满，但是可以交换每个人的位置，使得尽可能多的人感到满意，输出最多能够使多少人感到满意。

数据范围

$1\leq n\leq10^5\\1\leq t\leq10^9$

题解

要使每个人的等待时间都最短，就让 $t_i$ 小的人排在前面， $t_i$ 大的人排在后面，$O(n)$ 扫一遍就可以了。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
#include <io.h>
#include <conio.h>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n;
LL num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
        }
        sort(num, num + n);
        LL sum = num[0];
        int ans = 1;
        for(int i = 1; i < n; ++i) {
            if(num[i] >= sum) {
                ++ans;
                sum += num[i];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Paths and Trees

题意

给定一个 $n$ 个节点 $m$ 条边的无向图，和图上的一个点 $u$，找到一棵以 $u$ 点为根的树，这棵树上所有点到 $u$ 点的距离都是图上到 $u$ 点的最短距离，输出这棵树的最小边权和以及被选中的边的编号。

数据范围

$1\leq n\leq3\times10^5\\0\leq m\leq3\times10^5\\1\leq u,v\leq n\\1\leq w_i\leq10^9\\u\neq v$

题解

跑迪杰斯特拉最短路的时候，记录一下每个节点到节点 $u$ 的最短距离的边的下标 $pre_i$，如果 $dis_i>dis_j+dis_{ij}$，则更新 $pre_i$，如果 $dis_i=dis_j+dis_{ij}$，则比较 $pre_i$ 与 $Index_{ij}$，如果 $Index_{ij}$ 的长度更短，则更新。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
#include <sstream>
#include <io.h>
#include <conio.h>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
struct Node {
    int pos;
    LL dis;
    int Index;
    int Next;
    Node() {}
    Node(int p, LL d) {
        pos = p;
        dis = d;
    }
};
bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}
int n, m, u, v, pos, cnt;
LL d, ans;
LL dis[maxn];
int pre[maxn];
LL ddis[maxn];
int IIndex[maxn];
Node node[maxn << 1];
int head[maxn];
priority_queue<Node> que;
bool st[maxn];
void unit(int x, int y, LL d, int I) {
    node[cnt].dis = d;
    node[cnt].Index = I;
    node[cnt].pos = y;
    node[cnt].Next = head[x];
    head[x] = cnt++;
}
void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    que.push(Node(s, 0));
    while(!que.empty()) {
        Node tmp = que.top();
        que.pop();
        for(int i = head[tmp.pos]; i != -1; i = node[i].Next) {
            pos = node[i].pos;
            d = node[i].dis;
            int Index = node[i].Index;
            if(dis[pos] > tmp.dis + d) {
                st[pre[pos]] = false;
                st[Index] = true;
                pre[pos] = Index;
                dis[pos] = tmp.dis + d;
                que.push(Node(pos, dis[pos]));
            } else if(dis[pos] == tmp.dis + d) {
                st[pre[pos]] = false;
                st[Index] = true;
                pre[pos] = Index;
            }
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        cnt = 0;
        memset(head, -1, sizeof(head));
        memset(st, 0, sizeof(st));
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d%I64d", &u, &v, &d);
            ddis[i] = d;
            unit(u, v, d, i);
            unit(v, u, d, i);
        }
        scanf("%d", &pos);
        dij(pos);
        int ccnt = 0;
        for(int i = 1; i <= m; ++i) {
            if(st[i]) {
                ans += ddis[i];
                IIndex[ccnt++] = i;
            }
        }
        printf("%I64d\n", ans);
        for(int i = 0; i < ccnt; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", IIndex[i]);
        }
        printf("\n");
    }
    return 0;
}