这次的CSP是十分伤心的，考试的状态不好，导致分数不理想。

睡了一觉后我重做了一下这四道题，觉得还是蛮简单的，于是便有了这篇题解。

T1

统计1的数量，字符串模拟即可

#include <bits/stdc++.h>

using namespace std;

char buf[233];

signed main() {
    fgets(buf, 233, stdin);
    int res = 0;
    for (int i = 0; i < 8; ++i)
        res += (buf[i] == '1');
    printf("%d", res);
}

T2

这道题是最亏的，STL是个好东西，但容易遗忘一些细节。比如erase后没有减掉下标。

模拟即可，用一个数组或vector存储优惠票，每次坐地铁的时候扫描一下。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

vector < pair < int , int > > vec;
const int MAXN = 1e5 + 5;
struct NODE {
    int ID;
    int Pri;
    int Tim;
} a[MAXN];
int n;
int ans;

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[i] = NODE{x, y, z};
        if (!a[i].ID) {
            ans += a[i].Pri;
            vec.push_back(make_pair(a[i].Pri, a[i].Tim));
            continue;
        }
        int Flag = false;
        for (int j = 0; j < vec.size(); ++j) {
            if (abs(a[i].Tim - vec[j].second) <= 45 && vec[j].first >= a[i].Pri) {
                vec.erase(vec.begin() + j);
                --j;
                Flag = true;
                break;
            }
            if (abs(a[i].Tim - vec[j].second) > 45)
                vec.erase(vec.begin() + j), --j;
        }
        if (!Flag) ans += a[i].Pri;
    }
    printf("%d\n", ans);
}

T3

完全背包的题

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <utility>
#define _ 0

using namespace std;

inline int read() {
    int a = 0, f = 1; char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
    while (isdigit(ch)) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = getchar();
    return a * f;
}

template<typename _T>
inline void write(_T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x /10);
    putchar(x % 10 + '0');
}

const int MAXN = 233333 + 5;
int T = read();
int n = read();
int m = read();
int o233[105][105];
int dp[MAXN];

signed main() {
    for (int i = 1; i <= T; ++i)
        for (int j = 1; j <= n; ++j)
            o233[i][j] = read();

    int ans = m;
    for (int i = 1; i <= T; ++i) {
        memset(dp, ~~(0^_^0), sizeof dp);
        dp[ans] = ans;
        for (int j = 1; j <= n; ++j)
            for (int k = ans; k >= o233[i][j]; --k)
                dp[k - o233[i][j]] = max(dp[k - o233[i][j]], dp[k] + o233[i + 1][j] - o233[i][j]);

        int maxNum = -2333333;
        for (int ljs = ~~(0^_^0); ljs <= ans; ++ljs)
            maxNum = max(maxNum, dp[ljs]);
        ans = maxNum;
    }
    write(ans);
    return 0;
}

T4

这道题还没有T3难

对这个图跑一遍Dijkstra或SPFA，（这次的数据不知道有没有卡SPFA）处理出所有点到原点的奇数最短路和偶数最短路。

因为边权一直为1，所以只需要用当前的奇数最短路更新偶数最短路，用当前的偶数最短路更新奇数最短路就行了。

有一个坑点在于，若源点是独立的，也就是说若1号结点没有出入度，那么这种情况是一直输出No

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <utility>

using namespace std;

inline int read() {
    int a = 0, f = 1; char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
    while (isdigit(ch)) a = (a << 3) + (a << 1) + (ch ^ '0'), ch = getchar();
    return a * f;
}

template<typename _T>
inline void write(_T x) {
    if (x < 0) putchar('-'), x = -x;
    if (9 < x) write(x / 10);
    putchar(x % 10 + '0');
}

const int MAXN = 1e5 + 5;
struct UndirectedGraph {
    long long OddDis;
    long long EvenDis;
} dis[MAXN];
int head[MAXN << 1], _next[MAXN << 1];
int ver[MAXN << 1], edge[MAXN << 1];
int tot;
int n = read();
int m = read();
int q = read();

inline void addEdge(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z;
    _next[tot] = head[x], head[x] = tot;
}

inline void SPFA() {
    for (int i = 1; i <= n; ++i)
        dis[i].EvenDis = dis[i].OddDis = 0x7fffffff;
    queue<int> Q;
    Q.push(1);
    dis[1].EvenDis = 0;
    while (Q.size()) {
        int x = Q.front(); Q.pop();
        for (int i = head[x]; i; i = _next[i]) {
            int y = ver[i];
            int z = edge[i];
            int OddDis = dis[y].OddDis;
            int EvenDis = dis[y].EvenDis;
            dis[y].OddDis = min(dis[y].OddDis, dis[x].EvenDis + z);
            dis[y].EvenDis = min(dis[y].EvenDis, dis[x].OddDis + z);
            if (dis[y].EvenDis ^ EvenDis || dis[y].OddDis ^ OddDis)
                Q.push(y);
        }
    }
}

signed main() {
    bool flag = false;
    for (int i = 1; i <= m; ++i) {
        int from = read();
        int to = read();
        addEdge(from, to, 1);
        addEdge(to, from, 1);
        if (from == true || to == true) flag = 1;
    }
    SPFA();
    for (int i = 1; i <= q; ++i) {
        int ID = read();
        int wanted = read();
        if (ID == 1 && !flag) {
            puts("No");
            continue;
        }
        if (dis[ID].OddDis == 0x7fffffff && dis[ID].EvenDis == 0x7fffffff) {
            puts("No");
            continue;
        }
        if (((wanted & 1) && dis[ID].OddDis <= wanted) || ((~wanted & 1) && dis[ID].EvenDis <= wanted)) puts("Yes");
        else puts("No");
    }
    #define _ 0
    return ~~(0^_^0);
}