题目涉及算法：
- 数字游戏：字符串入门题；
- 公交换乘：模拟；
- 纪念品：完全背包；
- 数字游戏：广搜/最短路。
数字游戏
题目链接：https://www.luogu.com.cn/problem/P5660
题目大意：求一个长度为8的字符串中有多少个字符0。
题解：
首先开一个变量用于计数（我称此变量为“计数器”，初始时计数器的值为0）。
然后输入字符串，然后从0到7遍历字符串的前8个字符，每当遇到一个字符‘1’就将计数器加一，最后输出计数器对应的值即可。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
char s[10];
int cnt;
int main() {
cin >> s;
for (int i = 0; i < 8; i ++)
if (s[i] == '1')
cnt ++;
cout << cnt << endl;
return 0;
}
公交换乘
题目链接：https://www.luogu.com.cn/problem/P5661
题目大意：
有公交和地铁，做地铁会得到一张票，凭此票可以在45分钟内免费坐一班票价小于等于地铁票的公交车，
默认按照最早的一张符合要求的地铁车票开始使用。问按照这种操作，小轩出行的总花费。
题解：
因为条件是限定死的，即给了我乘车的记录，答案是固定的。所以不管我使用什么方法，只要能解决这样一个过程就可以了。
本题如果将条件中的时间间隔从 45 分钟修改为 n 分钟，那么是可以使用线段树+二分做的。
然而题目给我们的时间间隔是固定的 45 分钟，所以我们可以采取更暴力的手段来解决这个问题。
我们只需要从前往后遍历每一张车票，
- 如果这张车票是地铁票，则我们的总花费直接加上地铁票的价格；
- 如果这张查票是公交车票，则我们从它的45分钟之前开始找是否有满足要求的地铁票可以使用的，如果有，则使用该地铁票并且置本次公交车免费；否则，总价格需要加上公交车的车费。
因为题目限定了时间从早到晚，并且每班车的开始时间都不一样，所以对于第 i 班车，我们只需要从第 max(1, i-45) 班车开始遍历到第 i-1 班车就可以了。
所以总的时间复杂度是 O(45n) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, // 乘车记录的数量
type[maxn], // 交通工具类型
price[maxn], // 乘车的票价
t[maxn], // 开始乘车时间
tot; // 总花费
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> type[i] >> price[i] >> t[i];
for (int i = 1; i <= n; i ++) {
if (type[i] == 0) tot += price[i];
else {
bool flag = false;
for (int j = max(1, i-45); j < i; j ++) {
if (type[j] == 0 && t[i]-t[j] <= 45 && price[j] >= price[i]) {
type[j] = 1;
flag = true;
break;
}
}
if (!flag) tot += price[i];
}
}
cout << tot << endl;
return 0;
}
纪念品
题目链接：https://www.luogu.com.cn/problem/P5662
题目大意：
有 n 件物品，它们每一天都有一个价格，然后现在有T天，每一天你都可以选择卖出你手头上有的任意物品任意件，也可以选择以当天的价格买入任意物品任意件。
题解：
完全背包变形题。
我们枚举任意两天 i 和 j（i小于j），那么在已知第i天我能够获得的总价值是 Vi 的情况下，我们可以进行一次完全背包：
背包的容量为 Vi，同时我们令 Fi 表示容量为i的背包的最大价值，那么第i天能够扩充第j天背包的最大容量应该是 max(Fk + Vi-k) ，然后我们再选该候选项和当前 Vj 的最大值作为 Vj 的选项即可。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int n, T, a[101][101], V[101], f[maxn];
void solve(int day1, int day2) {
memset(f, 0 ,sizeof(int)*(V[day1]+1));
for (int i = 1; i <= n; i ++) {
int c = a[day1][i], w = a[day2][i];
for (int j = c; j <= V[day1]; j ++) {
f[j] = max(f[j], f[j-c] + w);
}
}
int tmp = 0;
for (int i = 0; i <= V[day1]; i ++) tmp = max(tmp, f[i] + V[day1]-i);
V[day2] = max(V[day2], tmp);
}
int main() {
cin >> T >> n >> V[0];
for (int i = 1; i <= T; i ++) for (int j = 1; j <= n; j ++) cin >> a[i][j];
for (int i = 1; i <= T; i ++) {
V[i] = max(V[i], V[i-1]);
for (int j = i+1; j <= T; j ++) {
solve(i, j);
}
}
cout << V[T] << endl;
return 0;
}
加工零件
题目链接：https://www.luogu.com.cn/problem/P5663
题目大意：
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 n 位工人，工人们从 1∼n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 x 号工人想生产一个被加工到第 L(L>1) 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L−1 阶段的零件（但 x 号工人自己无需生产第 L−1 阶段的零件）。
如果 x 号工人想生产一个被加工到第 1 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要为 x 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 q 张工单，第 i 张工单表示编号为 a_i的工人想生产一个第 L_i 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
题解：
将每个点拆分成奇点和偶点，从1号偶点求到每个点的最短路。
然后对于每次询问的距离L和点u，如果L是偶数并且到点u偶点的距离小于等于L，或者L是奇数并且到点u奇点的距离小于等于L，那么就能够走通。
但是还有一组特例，就是如果点1的度数为0（即没有连向点1的边）并且询问的点也是1，那也没有办法走到，因为起点没有边，需要特殊判断这个条件。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int dis[maxn][2], n, m, q;
vector<int> g[maxn];
struct Node {
int u, s;
Node (int _u, int _s) { u = _u; s = _s; }
};
queue<Node> que;
bool inq[maxn][2];
void spfa() {
memset(inq, 0, sizeof(inq));
memset(dis, -1, sizeof(dis));
dis[1][0] = 0;
que.push(Node(1, 0));
while (!que.empty()) {
Node nd = que.front();
que.pop();
int u = nd.u, s = nd.s;
inq[u][s] = false;
int sz = g[u].size();
for (int i = 0; i < sz; i ++) {
int v = g[u][i];
if (dis[v][s^1] == -1 || dis[v][s^1] > dis[u][s] + 1) {
dis[v][s^1] = dis[u][s] + 1;
if (!inq[v][s^1]) {
inq[v][s^1] = true;
que.push(Node(v, s^1));
}
}
}
}
}
int main() {
cin >> n >> m >> q;
while (m --) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
spfa();
if (g[1].size() == 0) {
while (q --) puts("No");
}
else {
while (q --) {
int a, L;
cin >> a >> L;
puts( dis[a][L%2] != -1 && dis[a][L%2] <= L ? "Yes" : "No" );
}
}
return 0;
}