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

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

试题编号	试题名称	标签
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	日期计算 | 题解

待做

• [ ] TODO
• [x] Completed
• [ ] 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

1. 获取'='位置，切割等式左右边子串，定义unordered_map，对于左边等式的子串加权为正值，而右边子串加权为负值。（如果配平成功的话，左子串加权+右子串加权为0）

2. 枚举起点，查询最接近起点的'+'，获得子串中每一个化学式

3. 计算化学式中每个原子（总是以大写字母为起点）的出现次数。从左至右遍历：

   • 首先计算化学式开头的系数（注意系数不止一位数；也有可能系数不存在，说明稀系数为1）；

   • 当前字符为大写字母，找到其后的小写字母，得到完整原子的字符串，计算其原子加权次数；

   • 当前字符为'('，（注意含有括号嵌套，内层可能要多个嵌套括号），先获得其对应的')'位置，再递归处理内部的括号嵌套；

   • 当串的长度只有1，又或者是2(eg:$Zn$)，说明分解出最小的原子，此时可以统计入unordered_map。（我们知道化学元素，要么由一个大写字母构成，要么一个大写+一个小写字母构成）

4. 统计unordered_map出现过该原子字符串的key值，如果key不为0，代表左子串无法将右子串完全消掉，进一步说明两边原子出现次数不等即配平错误。

¶学习\温故：

• find_if()函数与map的搭配使用；

• map、string的相应迭代器，成员函数(eg:find()、clear())

• islower()、isupper()、isdigit()。

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

##include <string>
##include <cstring>
##include <cstdio>
##include <iostream>
##include <queue>
##include <map>
##include <vector>
##include <algorithm>
##include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
unordered_map<string, int> 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<string, int>& 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);
}