题目涉及算法:
计数问题: 枚举;
表达式求值: 栈;
小朋友的数字: 动态规划;
车站分级: 最长路.
计数问题
题目链接: https://www.luogu.org/problem/P1980
因为数据量不大, 所以直接枚举一下每个数, 然后统计一下 x 出现的次数就可以了.
实现代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- int n, x, cnt;
- int main() {
- cin>> n>> x;
- for (int i = 1; i <= n; i ++) {
- int j = i;
- while (j> 0) {
- if (j % 10 == x) cnt ++;
- j /= 10;
- }
- }
- cout <<cnt << endl;
- return 0;
- }
表达式求值
题目链接: https://www.luogu.org/problem/P1981
涉及栈前缀表达式转后缀表达式.
题解地址:
小朋友的数字
题目链接: https://www.luogu.org/problem/P1982
首先表示一下这道题目的题目意思真的好难看懂啊.
因为这句话:
"第一个小朋友的分数是他的特征值, 其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人), 小朋友分数加上其特征值的最大值."
到底这个 "其特征值" 是这个小朋友还是排在他前面的所有小朋友. 一直没搞清楚啊~.
然后这是一道动态规划的题目.
首先需要求状态 \(f[i]\) , 它表示以 \(a[i]\) 结尾 (且不需包含 \(a[i]\)) 的最大字段和, 状态转移方程为:
\(f[i] = max(f[i-1],0) + a[i]\)
这一步操作我觉得是没有问题的.
但是题目没有看懂, 所以我决定暂时先不错了~. 嗯, 就是这么任性.
车站分级
题目链接: https://www.luogu.org/problem/P1983
这道题目只需要建图 + 求最长路就可以了.
对于每一趟车, 我们假设它的区间范围为 \([L,R]\) , 然后我们假设 \([L,R]\) 范围内的数分为两个集合:
停靠的站对应的数的集合 \(S1\);
没有停靠的站对应的数的集合 \(S2\);
我们知道没有停靠的站的优先级比停靠的站的肯定要低, 所以对于每一趟车来说, 我们从 \(S2\) 集合中的所有点向 \(S1\) 集合中的所有点连一条权值为 \(1\) 的边.
然后我们设一个起点 \(start\) , 对于所有入度为 0 的点, 我们从起点连一条权值为 \(1\) 的点到这些点.
并且这个图是保证不存在环的.
然后我们直接套 SPFA 求一下最长路即可.
实现代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1010;
- vector<int> g[maxn];
- bool bg[maxn][maxn], d[maxn], vis[maxn];
- int n, m, cnt, a[maxn], dist[maxn], ans;
- queue<int> que;
- void test() {
- puts("[test]");
- for (int i = 1; i <= n; i ++)
- printf("\tdist[-] = M\n", i, dist[i]);
- }
- int main() {
- scanf("%d%d", &n, &m);
- while (m --) {
- scanf("%d", &cnt);
- for (int i = 0; i < cnt; i ++) scanf("%d", &a[i]);
- for (int i = a[0], j = 0; i <= a[cnt-1]; i ++) {
- if (a[j] == i) j ++;
- else {
- for (int k = 0; k < cnt; k ++)
- bg[i][ a[k] ] = true;
- }
- }
- }
- for (int i = 1; i <= n; i ++) {
- for (int j = 1; j <= n; j ++) {
- if (bg[i][j]) {
- g[i].push_back(j);
- d[j] = true;
- }
- }
- }
- for (int i = 1; i <= n; i ++) {
- if (!d[i]) {
- dist[i] = 1;
- que.push(i);
- }
- else dist[i] = -1;
- }
- while (!que.empty()) {
- int u = que.front(); que.pop();
- vis[u] = false;
- int sz = g[u].size();
- for (int i = 0; i < sz; i ++) {
- int v = g[u][i];
- if (dist[v] == -1 || dist[v] < dist[u] + 1) {
- dist[v] = dist[u] + 1;
- if (!vis[v]) {
- vis[v] = true;
- que.push(v);
- }
- }
- }
- }
- for (int i = 1; i <= n; i ++) ans = max(ans, dist[i]);
- printf("%d\n", ans);
- return 0;
- }
作者: zifeiy
来源: http://www.bubuko.com/infodetail-3259746.html