CCF-CSP认证 C++题解目录

阅读原文时间：2021年12月23日阅读：1

持续更新中，记录刷题过程并分享一下小小的心得总结。

试题编号

试题名称

标签

202006-1

线性分类器 | 题解

线性规划

202006-2

稀疏向量| 题解

归并排序思想

202006-3

化学方程式 | 题解 ️

大模拟、常用STL

201912-1

报数| 题解

201912-2

回收站选址| 题解

常用STL

201909-1

小明种苹果| 题解

201909-2

小明种苹果(续)| 题解

模拟

201903-1

小中大| 题解

201903-2

二十四点|题解

队列、四则表达式

201812-1

小明上学 | 题解

201812-2

小明放学 | 题解 ️

模拟、周期变化

201812-4

数据中心

最小生成树

201809-1

卖菜 | 题解

201809-2

买菜 | 题解 ️

区间重叠、暴力枚举

201803-2

碰撞的小球 | 题解 ️

模拟、哈希表

201712-2

游戏 | 题解

模拟

201709-1

打酱油 | 题解

201709-4

通信网络 | 题解

深搜

201703-4

地铁修建 | 题解

最小生成树

201609-4

交通规划 | 题解

单源最短路径

201604-4

游戏 | 题解 ️

广搜

201512-4

送货 | 题解 ️

欧拉通路

201509-2

日期计算 | 题解

待做

[ ] 201912-4 区块链（常用STL、大模拟）
[ ] 201903-3 损坏的RAID5 （进制转换、字符串读取）
[ ] 201812-3 CIDR合并（list）
[ ] 201809-3 元素选择器（复杂模拟）
[ ] 201803-3 URL映射（正则表达式）
[ ] 201709-2 公共钥匙盒（STL）
[ ] 201709-3 JSON查询（复杂模拟、正则表达式、字符串处理）
[ ] 201509-4 高速公路（强连通分支）
[ ] 201503-4 网络延时（树的最长路径）

202006-1 线性分类器

题目看似很复杂很长。简化而言，就是给定两组顶点集及其横纵坐标，给定直线方程\(ax+by+c=0\)的参数\(a,b,c\)。现要你判断该直线是否能将两组顶点集完全分割开。（也就说直线上方是一组顶点集，下方是另一组顶点集）

首先观察数据范围只有\(1e3\)，直接\(O(nm)\)算法，即对于每一条直线，都将每个顶点遍历一次，判断每个点是否属于某一集合。

判断的问题，实际上就是高中数学的线性规划，如果两个点对直线方程的参数得到的符号是同号（同为\(>\)号或者同为\(<\)号），说明两点均在直线的同一侧（同为上方或者同为下方）首先对第一个输入的点，并将其结果作为一个相对的标准，自定义以后的点在上方是类型A还是类型B。

注意，题目中“完全”意味着任何顶点都不允许在直线上。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n, m;
struct Point{
    int x, y; char type;
} p[MAXN];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d %d %c", &p[i].x, &p[i].y, &p[i].type);
    for(int i = 1, a, b, c; i <= m; i++){
        scanf("%d%d%d", &a, &b, &c);
        char t = '#';
        bool flag = true;
        for(int j = 1; j <= n; j++){
            int res = b * p[j].x + c * p[j].y;
            if(res == -a){ //说明该点在直线上
                printf("No\n");
                flag = false;
                break;
            }
            else if(j == 1){ //设一相对基准，'>'与"type == t"相关
                if ((res > -a && p[j].type == 'A') || (res < -a && p[j].type == 'B'))
                    t = 'A';
                else if ((res < -a && p[j].type == 'A') || (res > -a && p[j].type == 'B'))
                    t = 'B';
            }
            else {
                if ((res > -a && p[j].type == t) || (res < -a && p[j].type != t))
                    continue; //说明该点被直线完全分割
                else {
                    printf("No\n");
                    flag = false;
                    break;
                }
            }
        }
        if (flag) printf("Yes\n");
    }
    return 0;
}

202006-2 稀疏向量

稀疏向量，是\(n\)维向量中每个维度都存有值，但大部分维度上的值为\(0\)，少量维度取值不为\(0\)。我们可通过\((index, value)\)对来表示一个向量在\(index\)维度上取值为\(value\)。比如，\(v=(0,0,0,5,0,0,-3,0,0,1)\)，可表示为\([(4,5),(7,-3),(10,1)]\)。现给定两个稀疏向量\(u,v\)，要求出两稀疏向量的点积（或称内积）\(u\cdot v\)。

点积过程其实就是运用归并排序的思想，将稀疏矩阵\(u,v\)看做两子数组，接下来就是对两子数组进行合并排序了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 5e5+5;
typedef long long ll;
struct Node{
    int idx, val;
} u[MAXN], v[MAXN];
int n, a, b;
int main(){
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i <= a; i++)
        scanf("%d%d", &u[i].idx, &u[i].val);
    for (int i = 1; i <= b; i++)
        scanf("%d%d", &v[i].idx, &v[i].val);
    int le = 1, ri = 1;
    ll ans = 0;
    while(le <= a && ri <= b){
        if(u[le].idx < v[ri].idx) le++;
        else if(u[le].idx > v[ri].idx) ri++;
        else {
            ans += (1ll * (ll)u[le].val * (ll)v[ri].val);
            le++; ri++; //同时增加
        }
    }
    printf("%lld\n", ans);
    return 0;
}

201912-3 化学方程式

检查诸如\(4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH\)的化学方程式，是否配平。

十分感谢@日沉云起的代码，十分清晰，同时利用相应库函数或STL，简洁地处理一些细节问题，把我的思路打开了orz….

我将他的代码思路及我的体会总结一下qaq

获取'='位置，切割等式左右边子串，定义unordered_map，对于左边等式的子串加权为正值，而右边子串加权为负值。（如果配平成功的话，左子串加权+右子串加权为0）
枚举起点，查询最接近起点的'+'，获得子串中每一个化学式
计算化学式中每个原子（总是以大写字母为起点）的出现次数。从左至右遍历：
- 首先计算化学式开头的系数（注意系数不止一位数；也有可能系数不存在，说明稀系数为1）；
- 当前字符为大写字母，找到其后的小写字母，得到完整原子的字符串，计算其原子加权次数；
- 当前字符为'('，（注意含有括号嵌套，内层可能要多个嵌套括号），先获得其对应的')'位置，再递归处理内部的括号嵌套；
- 当串的长度只有1，又或者是2(eg:\(Zn\))，说明分解出最小的原子，此时可以统计入unordered_map。（我们知道化学元素，要么由一个大写字母构成，要么一个大写+一个小写字母构成）
统计unordered_map出现过该原子字符串的key值，如果key不为0，代表左子串无法将右子串完全消掉，进一步说明两边原子出现次数不等即配平错误。

find_if()函数与map的搭配使用；
map、string的相应迭代器，成员函数(eg:find()、clear())
islower()、isupper()、isdigit()。

我最初认为有些数据结构或者函数，自己手写也行，但是遇到大模拟题时，代码可能要上到百行以上时，通过STL，能够减少冗余的代码（真香）。

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 1005;
unordered_map mymap;
string str;
int getDigit(int& lo, int hi) { //这里lo的引用十分妙，返回时无需再重新调整lo的起点
int res = 0;
while (lo <= hi && isdigit(str[lo])) //找到数字就走人 res = res * 10 + (str[lo++] - '0'); return res == 0 ? 1 : res;//注意，化学式前面有可能无系数! } void Compute(int lo, int hi, int val) { //递归处理化学式，得到原子 if (lo == hi || (hi - lo == 1 && islower(str[hi]))) { //得到完整的原子 mymap[str.substr(lo, hi - lo + 1)] += val; return; } val *= getDigit(lo, hi); //求出该化学式前面的系数 for (int i = lo, j = i + 1; i <= hi; i = j, j++) { if (isupper(str[i])) { if (j <= hi && islower(str[j])) j++; //j指向该原子的后面一位 int tmp = j; //用个临时变量存j，避免getDigit()对j的引用进行修改 Compute(i, j - 1, val * getDigit(tmp, hi)); //比如CO2 } else if (str[i] == '(') { //处理括号嵌套 for (int cnt = 1; cnt != 0; j++) { //移动的是j，为了确定括号的右端点范围 if (str[j] == '(') cnt++; else if (str[j] == ')') cnt--; } int tmp = j; Compute(i + 1, j - 1, val * getDigit(tmp, hi)); } } } void getFormula(int lo, int hi, int val) { //通过'+'分离出化学式 for (int i = lo, j = lo; i <= hi; i = j + 1) { j = str.find('+', i); if (j > hi || j == (int)string::npos) //说明后面再无'+'号
j = hi + 1;
Compute(i, j - 1, val);
}
}
int main() {
int n; scanf("%d", &n);
while (n--) {
mymap.clear();
cin >> str;
int mid = str.find('=');
getFormula(0, mid - 1, 1);
getFormula(mid + 1, str.length() - 1, -1);
auto i = find_if(mymap.begin(), mymap.end(),
[](const pair& p) { return p.second != 0; });
//遍历map每个元素（即每个原子），一旦发现某个原子在等式两边不平衡，说明等式不配平
printf("%c\n", (i == mymap.end()) ? 'Y' : 'N');
}
return 0;
}

201912-1 报数

四个人从\(1\)开始轮流，进行报数，但如果需要报出的数为\(7\)的倍数或含有数字\(7\)则直接跳过。总共需要报出\(n\)个数（不计入被跳过的数）方能结束游戏。现要统计每个人各自跳过几次。

这题容易审错题，它还需要检查当前报的数字为，敲的时候注意细节然后模拟即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 5e5+5;
typedef long long ll;
int n, cnt = 0;
int peo[5];
int num = 0, i = 0;
bool Judge(int x){
    if(x % 7 == 0) return true;
    while(x){
        int cur = x % 10;
        if(cur == 7) return true;
        x /= 10;
    }
    return false;
}
int main(){
    scanf("%d", &n);
    while(num < n){
        i++; cnt++; if(cnt > 4) cnt = 1;
        if(Judge(i)) peo[cnt]++;
        else num++;
    }
    for (int i = 1; i <= 4; i++) printf("%d\n", peo[i]);
    return 0;
}

201912-2 回收站选址

\(n\)处待清理垃圾位置，第\(i\)处坐标为\((x_i,y_i)\)。现要在垃圾集中的地方，对于位置\((x_i, y_i)\)是否适合建立回收站，需满足以下几点：

\((x, y)\)必须是整数坐标，该处存在垃圾；
上下左右四个邻居位置全部存在垃圾；

我们会对上述两个条件的选址进行评分，分数为不大于4的自然数，表示在四个对角位置有多少处存在垃圾。

现你要统一，每种得分(\(0~4\))的选址个数。

该题的横纵坐标达到了\(\pm1e9\)，数组无法模拟。先用\(STL\)中的\(pair\)存储坐标，再将\(pair\)存到\(map\)中，用于检查该坐标是否已经存在。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n;
struct Point{
    int x, y;
} p[MAXN];
map<pair<int, int>, int> mymap;
int cnt[5];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d%d", &p[i].x, &p[i].y);
        mymap[{p[i].x, p[i].y}] = 1;
    }
    for (int i = 1; i <= n; i++){
        int x = p[i].x, y = p[i].y;
        if(mymap[{x-1, y}] && mymap[{x+1, y}]
        && mymap[{x, y-1}] && mymap[{x, y+1}]){
            int tmp = mymap[{x + 1, y + 1}] + mymap[{x - 1, y - 1}]
                    + mymap[{x + 1, y - 1}] + mymap[{x - 1, y + 1}];
            cnt[tmp]++;
        }
    }
    for (int i = 0; i <= 4; i++)
        printf("%d\n", cnt[i]);
}

201909-1 小明种苹果

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n, m;
int tree[MAXN];
int main(){
    scanf("%d%d", &n, &m);
    int mymax = -1, sum = 0, pos = 0;
    for (int i = 1, a0; i <= n; i++){
        scanf("%d", &a0);
        int del = 0;
        for (int j = 1, tmp; j <= m; j++){
            scanf("%d", &tmp);
            del += tmp;
        }
        del *= -1;
        if(mymax < del){
            mymax = del;
            pos = i;
        }
        sum += (a0 - del);
    }
    printf("%d %d %d\n", sum, pos, mymax);
}

201909-2 小明种苹果(续)

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n, sum = 0, cnt = 0;
bool isDrop[MAXN];
int main(){
    scanf("%d", &n);
    for(int i = 1, m, last = 0; i <= n; i++){
        scanf("%d", &m);
        for(int j = 1, tmp; j <= m; j++){
            scanf("%d", &tmp);
            if(tmp > 0){
                if(last > tmp){
                    if(isDrop[i] == 0) cnt++;
                    isDrop[i] = 1;
                }
                last = tmp;
            }
            else
                last += tmp;
        }
        sum += last;
    }

    int E = 0;
    for(int i = 1; i <= n; i++){
        int cur = i, pre = cur - 1, succ = cur + 1;
        if(pre <= 0) pre = n;
        if(succ > n) succ = 1;
        E += (isDrop[pre] && isDrop[cur] && isDrop[succ]);
    }
    printf("%d %d %d\n", sum, cnt, E);
    return 0;
}

201903-1 小中大

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int main(){
    int n; scanf("%d", &n);
    int mymin = 0x3f3f3f3f, mymax = -0x3f3f3f3f;
    int sum = 0;
    int mid1 = 0; double mid2 = 0;
    for(int i = 1, tmp; i <= n; i++){
        scanf("%d", &tmp);
        if(i == 1)
            mymin = tmp;
        else if(i == n)
            mymax = tmp;
        if(n % 2 != 0 && i == (n + 1) >> 1){
            mid1 = tmp;
        }
        else if(n % 2 == 0 && ((i == n >> 1) || (i == (n >> 1) + 1))){
            sum += tmp;
        }
    }
    if(mymin > mymax) swap(mymin, mymax);
    if(n % 2 != 0){
        printf("%d %d %d\n", mymax, mid1, mymin);
    }
    else {
        mid2 = sum * 1.0 / 2;
        if(mid2 > (sum / 2))
            printf("%d %.1f %d", mymax, mid2, mymin);
        else
            printf("%d %.0f %d", mymax, mid2, mymin);
    }
    return 0;
}

201903-2 二十四点

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
deque<int> num;
deque<char> opt;
int main(){
    int n, sum = 0; cin >> n;
    char lastopt = '#';
    for(int i =1; i <= n; i++){
        string str; cin >> str;
        for (int j = 0; j < str.length(); j++){
            char tmp = str[j];
            if(lastopt != '#'){
                if(lastopt == 'x'){
                    int a = num.back(); num.pop_back();
                    int b = tmp - '0';
                    num.push_back(a * b);
                    lastopt = '#';
                }
                else if(lastopt == '/'){
                    int a = num.back(); num.pop_back();
                    int b = tmp - '0';
                    num.push_back(a / b);
                    lastopt = '#';
                }
            }
            else if('0' <= tmp && tmp <= '9')
                num.push_back(tmp - '0');
            else if(tmp == 'x' || tmp == '/')
                lastopt = tmp;
            else if(tmp == '+' || tmp == '-')
                opt.push_back(tmp);

        }
        while(!opt.empty()){
            char curopt = opt.front(); opt.pop_front();
            int a = num.front(); num.pop_front();
            int b = num.front(); num.pop_front();
            if(curopt == '+') num.push_front(a + b);
            else if(curopt == '-') num.push_front(a - b);
        }
        if(num.front() != 24) printf("No\n");
        else printf("Yes\n");
        num.pop_front();
    }
    return 0;
}

201812-2 小明上学

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
int r, y, g, n, sum = 0;
int main(){
    scanf("%d%d%d", &r, &y, &g);
    //lamp[1] = r; lamp[2] = y; lamp[3] = g;
    scanf("%d", &n);
    //k=0，直接走；k=1，红灯；k=2，黄灯；k=3,绿灯
    //先红灯，再绿灯，后黄灯
    for(int i = 1, k, t; i <= n; i++){
        scanf("%d%d", &k, &t);
        if(k == 0) sum += t;
        else if(k == 3) continue;
        else if(k == 1) sum += t;
        else if(k == 2) sum += (t + r);
    }
    printf("%d\n", sum);
    return 0;
}

201812-2 小明放学

红、绿、黄灯各自有其亮灯的时间，且其变化顺序为红->绿->黄。

小明在出门的时候将所有红绿灯当前状态，及亮灯的剩余时间，记录下来。同时也知道了某一段路（无红绿灯）所需要的时间，现要计算小明放学回家所用时间。

原题干有点难读懂，我稍微对样例画个图吧qaq

要注意，亮灯时长数据有点大，需用\(long long\)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
ll lamp[4];
int n;
int main(){
    scanf("%lld%lld%lld", &lamp[0], &lamp[2], &lamp[1]); //红、黄、绿
    scanf("%d", &n);
    ll period = lamp[0] + lamp[2] + lamp[1]; //红绿灯一轮变换的时长
    ll cur = 0;
    for(int i = 1, k, t; i <= n; i++){
        scanf("%d%d", &k, &t);
        if(k == 0){
            cur += (ll)t;
            continue;
        }
        if(k == 1) k = 0; //映射红灯
        //else if(k == 2) k = 2; //映射黄灯
        else if(k == 3) k = 1; //映射绿灯
        int last = (lamp[k] - (ll)t + cur) % period; //截取最后一个变化周期
        while(last > lamp[k]){ //当前灯的时间无法满足last
            last -= lamp[k];
            k = (k + 1) % 3; //灯变化
        }
        if(k == 1) continue; //当前灯为绿灯，无需等待
        else if(k == 0) cur += (ll)(lamp[0] - last);
        else if(k == 2) cur += (ll)(lamp[2] - last + lamp[0]); //若当前灯为黄灯，需要等黄灯和红灯
    }
    printf("%lld\n", cur);
}

201812-4 数据中心

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 5;
const int MAXM = 2e5 + 5;
int n, m, rt;
int parent[MAXN];
struct Edge {
    int u, v;
    int w;
} E[MAXM];
bool cmp(const struct Edge& a, const struct Edge& b) {
    return a.w < b.w;
}
int findSet(int x) {
    if (x != parent[x])
        parent[x] = findSet(parent[x]);
    return parent[x];
}
bool Union(int x, int y) {
    int px = findSet(x), py = findSet(y);
    if (px == py) return false;
    else {
        parent[py] = px;
        return true;
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &rt);
    m <<= 1;
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    for (int i = 1; i <= m; i += 2) {
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
        E[i + 1].u = E[i].v;
        E[i + 1].v = E[i].u;
        E[i + 1].w = E[i].w;
    }
    sort(E + 1, E + 1 + m, cmp);
    int ans = -1;
    for (int i = 1; i <= m; i++) {
        if (Union(E[i].u, E[i].v))
            ans = max(ans, E[i].w);
    }
    printf("%d\n", ans);
    return 0;
}

201809-1 卖菜

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n, a[MAXN], cost[MAXN];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        if(i == 1) {
            int tmpsum = a[i] + a[i+1];
            cost[i] = tmpsum / 2;
        }
        else if(i == n){
            int tmpsum = a[i-1] + a[i];
            cost[i] = tmpsum / 2;
        }
        else {
            int tmpsum = a[i - 1] + a[i] + a[i + 1];
            cost[i] = tmpsum / 3;
        }
    }
    for(int i = 1; i <= n; i++) printf("%d ", cost[i]);
    return 0;
}

201809-2 买菜

小H有\(n\)个不相交的工作时间段，小W也有\(n\)个不相交的工作时间段。现求他们两个人工作时间段之间的交集长度。

知道两区间各自左右端点，即区间[\(a,b\)]、[\(c,d\)]，如何判断两区间是否重叠呢？显然是\(a\leq d\)且\(c\leq b\)会发生重叠。

题目中\(n\)数据不大，直接暴力枚举（如果数据较大，可能需要线段树去处理），也就说对于新加入的H区间，我们枚举所有已存好的W区间并判断是否与H新加入区间重叠，若重叠则计入其长度。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 2005;
int a[MAXN], b[MAXN], n, sum = 0;
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
    for (int i = 1, le, ri; i <= n; i++){
        scanf("%d%d", &le, &ri);
        for (int j = 1; j <= n; j++){
            if(a[j] <= ri && le <= b[j])
                sum += (min(b[j], ri) - max(a[j], le));
        }
    }
    printf("%d\n", sum);
    return 0;
}

201803-2 碰撞的小球

数轴上有长为\(L\)的线段，有\(n\)个球在该线段相应位置上，速度方向向右，速度大小为1单位长度每秒。当小球到达线段的端点（左端点为\(0\)或右端点\(L\)）的时候，会立即向相反的方向移动，速度大小仍然为原来大小；当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。

现在要你计算t秒之后，各个小球的位置。

数据\(L,n\)及每个球位置均为偶数，保证不会有三个小球同时相撞

定义一数组vis，其中vis[pos]表示当前时刻，线段pos位置上球的数量。定义结构体ball存储每个球的基本信息

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 105;
struct Node{
    int x, d, id;
} ball[MAXN];
bool cmp(const struct Node& a, const struct Node& b){
    return a.id < b.id;
} //用于答案输出
int n, L, t;
int vis[1005];
int main(){
    scanf("%d%d%d", &n, &L, &t);
    for(int i = 1; i <= n; i++){
        scanf("%d", &ball[i].x);
        ball[i].d = 1; ball[i].id = i;
        vis[ball[i].x]++;
    }
    for(int i = 1; i <= t; i++){
        for (int j = 1; j <= n; j++){
            vis[ball[j].x]--; //清除j球在当前的位置
            ball[j].x += ball[j].d;
            if(ball[j].x == L || ball[j].x == 0) //到达端点
                ball[j].d *= (-1); //转向
            vis[ball[j].x]++; //标记新位置
        }
        for (int j = 1; j <= n; j++){
            if(vis[ball[j].x] >= 2) //同一位置出现两个球，说明发生碰撞
                ball[j].d *= (-1);
        }
    }
    sort(ball + 1, ball + 1 + n, cmp); //对球的编号进行排序，用于答案输出
    for (int i = 1; i <= n; i++) printf("%d ", ball[i].x);
    return 0;
}

201712-2 游戏

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int n, k, cnt, peo, last;
bool vis[MAXN];
bool Judge(int x){
    if(x % k == 0 || x % 10 == k) return true;
    else return false;
}
int main(){
    scanf("%d%d", &n, &k);
    last = n;
    while(last > 1){
        cnt++;
        while(vis[peo] == true) peo = (peo + 1) % n;
        if(Judge(cnt)){
            vis[peo] = true;
            last--;
        }
        peo = (peo + 1) % n;
    }
    while(vis[peo] == true) peo = (peo + 1) % n;
    printf("%d\n", peo + 1);
    return 0;
}

201709-1 打酱油

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
int main(){
    int n; scanf("%d", &n);
    ans = n / 10 + 2 * (n / 50) + 1 * (n % 50 / 30);
    printf("%d\n", ans);
    return 0;
}

201709-4 通信网络

考虑到\(n\leq1e3\)，从每个点出发搜索可到达的点，并用相应的二位数组isKnow标记，说明两点之间产生过信息传递。别忘了，在搜索的过程中要用vis数组去判断当前的顶点是否已在此轮搜索中已访问过，避免遍历过程中产生回环。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
const int MAXM = 20005;
struct Edge{
    int to, nextNbr;
} E[MAXM];
int H[MAXN], tot = 0, n, m;
void addEdge(int u, int v){
    tot++;
    E[tot].to = v;
    E[tot].nextNbr = H[u];
    H[u] = tot;
}
bool isKnown[MAXN][MAXN], vis[MAXN];
void dfs(int start, int u){
    for(int i = H[u]; i >= 0; i = E[i].nextNbr){
        int v = E[i].to;
        if(vis[v]) continue;
        vis[v] = true;
        isKnown[start][v] = isKnown[v][start] = true;
        dfs(start, v);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) H[i] = -1;
    for (int i = 1, u, v; i <= m; i++){
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) vis[j] = false;
        vis[i] = isKnown[i][i] = true;
        dfs(i, i);
    } //一定要将所有起点都DFS过，才能统计
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if(isKnown[i][j]) cnt++;
        }
        if(cnt == n)
            ans++;
    }
    printf("%d\n", ans);
}

201703-4 地铁修建

题目实际上要求的是，当顶点1与顶点n连通时，所连接的边越短越好，要求其中最大边能有多长（不是路径！）。“两点连通问题”，我们可以联想到并查集与\(Kruskal\)算法。我们不需要将建立完整的最小生成树，执行算法过程中，更新最长边的同时合并点，只要顶点1与顶点n连通即可将算法终止。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXM = 400005;
struct Edge{
    int u, v, w;
}E[MAXM];
int n, m;
bool cmp(const struct Edge& a, const struct Edge& b){
    return a.w < b.w;
}
int fa[MAXN];
int findSet(int x){
    if(x != fa[x]) fa[x] = findSet(fa[x]);
    return fa[x];
}
int main(){
    scanf("%d%d", &n, &m); m <<= 1;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, u, v, w; i <= m; i+=2){ //双向边
        scanf("%d%d%d", &u, &v, &w);
        E[i].u = E[i + 1].v = u;
        E[i].v = E[i + 1].u = v;
        E[i].w = E[i + 1].w = w;
    }
    sort(E+1, E+1+m, cmp);
    int mymax = -1;
    for(int i = 1; i <= m; i++){
        int pu = findSet(E[i].u), pv = findSet(E[i].v);
        if(pu != pv){
            fa[pu] = pv;
            mymax = max(mymax, E[i].w);
        }
        int p1 = findSet(1), pn = findSet(n);
        if(p1 == pn) //说明顶点1与顶点n连通，满足题目要求
            break;
    }
    printf("%d\n", mymax);
}

201609-4 交通规划

注意，直接使用STL中的pair，会超时。

题目要求的是，修最短的边之和，也就说它只累加边的长度，而不是累加一条条路径。对于题目的样例，我们可以计算出1-2-4及1-3-4属于同样长度的最短路径，为了到达顶点2与3，1-2及1-3的边必须要修。那么如何选择修一条连接到顶点4的边（选2-4还是3-4），使得代价没有那么低？显然是修3-4的边（代价为2）。因而在松弛边的过程中别忘了(dis[u] + E[i].w == dis[v] && cost[v] > E[i].w)这一条判断条件。

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
const int MAXM = 200005;
struct Edge{
    int to, nextNbr = -1, w;
}E[MAXM];
typedef struct qnode{
    int data, v;
    bool operator < (const qnode& r) const {
        return data > r.data;
    }
}qnode;
int H[MAXN], tot = 0, dis[MAXN], cost[MAXN];
int n, m;
void addEdge(int u, int v, int w){
    tot++;
    E[tot].to = v;
    E[tot].w = w;
    E[tot].nextNbr = H[u];
    H[u] = tot;
}
void Init(){
    for(int i = 1; i <= n; i++){
        dis[i] = 0x3f3f3f3f;
        H[i] = -1;
    }
    dis[1] = 0;
}
void dijkstra(int start){
    priority_queue< qnode > myque;
    myque.push({dis[start], start});
    while(!myque.empty()){
        qnode cur = myque.top();
        int len = cur.data, u = cur.v;
        myque.pop();
        if(len != dis[u]) continue;
        for(int i = H[u]; i >= 0; i = E[i].nextNbr){
            int v = E[i].to;
            if(dis[u] + E[i].w < dis[v]
            || (dis[u] + E[i].w == dis[v] && cost[v] > E[i].w)){
                cost[v] = E[i].w;
                dis[v] = dis[u] + E[i].w;
                myque.push({dis[v], v});
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    Init();
    for(int i = 1, u, v, w; i <= m; i++){
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dijkstra(1);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans += cost[i];
    printf("%d", ans);
    return 0;
}

201604-4 游戏

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, t;
typedef struct Node{
    int x, y, curt;
}node;
bool limited[105][105][105+105+100];
//记录每个顶点的危险时间点
int di[] = {0, 1, 0, -1, 0};
int dj[] = {0, 0, -1, 0, 1};
queue<Node> myque;
void BFS(){
    myque.push({1, 1, 0});
    while(!myque.empty()){
        node cur = myque.front(); myque.pop();
        if(cur.x == n && cur.y == m){
            printf("%d\n", cur.curt);
            break;
        }
        for(int d = 1; d <= 4; d++){
            int x = cur.x + di[d], y = cur.y + dj[d];
            int newt = cur.curt + 1;
            if(0 >= x || x > n || 0 >= y || y > m || limited[x][y][newt]) continue;
            limited[x][y][newt] = true; //在该newt时刻下标记访问过
            myque.push({x, y, newt});
        } //同一顶点在同一时刻显然只能访问一次！！！
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &t);
    for(int i = 1, r, c, a, b; i <= t; i++){
        scanf("%d%d%d%d", &r, &c, &a, &b);
        for(int j = a; j <= b; j++) limited[r][c][j] = true;
    }
    BFS();
    return 0;
}

201512-4 送货

题目要求的是欧拉通路(每条边经过一次且仅为一次)。一个无向图是欧拉通路，充要条件为，该无向图为连通图，且度数为奇数的的点可以有2个或者0个，若有2个，则其中一个为起点另外一个为终点。

此题还需要我们求出欧拉序列，一般来说直接DFS即可，每遇到一条未访问过的边，就对其打上标记，并将相应顶点存到数组即可（由于递归的顺序，需要倒序输出）(70分)。然而，本题数据会让你DFS爆栈，因而需要用到一个栈去模拟(90分)。注意，判断完是否会欧拉通路后，对于求出的欧拉序列，你必须要判断欧拉序列中顶点的个数是否等于\(m + 1\)（保证图的连通性！！）

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
const int MAXM = 200005;
bool vis[MAXN][MAXN];
vector<int> G[MAXN], path;
int n, m;
void DFS(int u){ //求欧拉序列法一（会爆栈）
    for (int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(vis[u][v]  && vis[v][u])
            continue;
        else {
            vis[u][v] = vis[v][u] = true;
            DFS(v);
        }
    }
    path.push_back(u);
}
void solve(int start){ //求欧拉序列法二
    stack<int> mystack;
    mystack.push(start);
    while(!mystack.empty()){
        int u = mystack.top(), i;
        for(i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            if(vis[u][v] && vis[v][u]) continue;
            else{
                mystack.push(v);
                vis[u][v] = vis[v][u] = true;
                break;
            }
        }
        if(i == G[u].size()){ //说明已将u的所有邻接点遍历完
            mystack.pop(); //让u出栈
            path.push_back(u);
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i <= m; i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        sort(G[i].begin(), G[i].end());
        if((int)G[i].size() & 1) cnt++;
    }
    if(cnt == 0 || (cnt == 2 && ((int)G[1].size() & 1))){
        //DFS(1);
        solve(1);
        if(path.size() != m + 1)
            printf("-1\n");
        else{
            for (int i = path.size() - 1; i >= 0; i--)
                printf("%d ", path[i]);
            printf("\n");
        }
    }
    else
        printf("-1\n");
    return 0;
}

201509-2 日期计算

#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
bool Judge(int y){
    if(y % 4 == 0 && y % 100 != 0)
        return true;
    else if(y % 400 == 0)
        return true;
    else
        return false;
}
int main(){
    int y, d;
    scanf("%d%d", &y, &d);
    int mon_day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (Judge(y)) mon_day[2]++;
    int sum = 0, i, j;
    for (i = 1; i <= 12; i++){
        sum += mon_day[i];
        if(sum >= d) break;
    }
    sum -= mon_day[i];
    printf("%d %d\n", i, d - sum);
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

01-C语言基础语法

【题解】AtCoder Beginner Contest 318（D - Ex）

C++算法之旅、05 基础篇 | 第二章数据结构