第十二次CCF-CSP认证
- 最小差值
- 满分题解
- 遇到的问题
- 游戏
- 满分题解
- solution 1
- solution 2
- 行车路线
- 样例图示
- 满分题解（yxc）
最小差值
题目链接
满分题解
遇到的问题
虽然没啥好说的，就是遍历一下数组找到最小差值（最小为0），但是需要注意相等的情况，我一开始没排序，出现了错误，原因就在于，我们的for循环帮助我们的是找到相邻数之间的最小差值，每次更新res保证最小，但是这个数列是无序的，
举个例子：
5 2 4 1 4 6
当我们最小情况出现也就是为差值为0的时候，我们显然能看出来，但是我之前程序输出的是相邻数之间最小也就是2，所以需要sort一下，然后多加一个if，这样就算出现差值最小，也能通过我们的for循环判断出来，这是我一开始写 没考虑到的地方
#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int s[N];
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>s[i];}//读入一下int res=10000;sort(s,s+n);for(int i=1;i<n;i++){if(s[i]==s[i-1]){res=0;}else{res=abs(s[i]-s[i-1])<res?abs(s[i]-s[i-1]):res;}}cout<<res;
}
游戏
题目链接
满分题解
这题我一看不对啊，这不是简化版的约瑟夫环吗，也就是猴子选大王问题，可以去看我前面的文章——约瑟夫环问题（多解法）
看完这篇 思路立马就来了。
solution 1
#include <bits/stdc++.h>
using namespace std;
int main()
{int n,k;cin>>n>>k;queue<int> q;for(int i=1;i<=n;i++){q.push(i);//用队列来表示时钟型排列}int j=1;while(q.size()>1){int tmp=q.front();q.pop();if(j%k!=0 && j%10!=k){q.push(tmp);}j++;}cout<<q.front()<<endl;
}
solution 2
一开始尝试用数组来模拟队列，交了一发答案没问题
但是显示 Segmentation Fault 哈哈我cnm 用vector吧，其实不需要管那些乱七八糟的，只需要知道vector是能够动态调整大小就够了
原因：
数组大小固定：代码里定义了一个固定大小的数组 arr[1000]，要是 n 超出了这个大小，就会出现数组越界的情况。
未对数组空间进行有效管理：在模拟队列的过程中，若不断将元素重新添加到数组末尾，而没有对数组空间进行合理管理，也可能引发数组越界。
#include <iostream>
#include <vector>
using namespace std;int main() {int n, k;cin >> n >> k;vector<int> arr;for (int i = 1; i <= n; i++) {arr.push_back(i); // 初始化数组，模拟队列元素}int j = 1;int index = 0;while (arr.size() > 1) {int tmp = arr[index];arr.erase(arr.begin() + index);if (j % k != 0 && j % 10 != k) {arr.push_back(tmp);} else {index = index % arr.size();}j++;}cout << arr[0] << endl;return 0;
}
行车路线
题目链接
样例图示
一开始我还疑惑呢 不是最佳路线吗，我如果全部走小路的话不就是25+36+1=62
小于样例给的76啊，不可能是样例给错了吧，后来想了半天
奥！原来是如果从1走到3是大路的话，那从3到5确实是6*6=36的疲劳，但是如果全是小路的话，就触发了疲劳值快速增长的条件，从1到5应该是（3+2+6）的平方 112，并不是简单的相加关系了
满分题解（yxc）
其实这个问题我觉得抽象成网图，疲劳值就是权值，我觉得如果学过图论的同学是比较好写的，比第三题的大模拟好拿分的多，而且这前50%的样例都没有小道全是大路 其实考试拿个一半还是可以的
我没有学dijkstra算法所以有些思路 但又不太能写出来，下面是Y总课上的代码，供大家参考：
这是对于Y总的代码做了解析：博客链接
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 200010;
const int INF = 1e6;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int f[M];// 边的类型，大路还是小路
bool st[N][1010];
int dist[N][1010];//第二维为拆点struct Node{// 点，最后一条小路的长度，距离int x, y, v;// 小根堆（距离从小到大）bool operator<(const Node& t)const{return v > t.v;}
};void add(int t, int a, int b, int c){e[idx] =b ,w[idx] = c, f[idx] = t,ne[idx] = h[a], h[a] = idx ++;
}void dijkstra(){memset(dist, 0x3f, sizeof dist);priority_queue<Node> heap;heap.push({1, 0, 0});dist[1][0] = 0;while(heap.size()){auto t = heap.top();heap.pop();if(st[t.x][t.y]) continue;st[t.x][t.y] = true;for(int i = h[t.x]; ~i; i= ne[i]){int x = e[i], y = t.y;//最后一段小路的长度yif(f[i]){// 小路y += w[i]; //小路长度更新if(y <= 1000){ // 小路长度不会超过1000if(dist[x][y] > t.v - t.y * t.y + y * y){// 更新1到x点的最短路dist[x][y] = t.v - t.y * t.y + y * y; if(dist[x][y] <= INF){// 加入堆heap.push({x, y, dist[x][y]});}}}}else{ // 大路if(dist[x][0] > t.v + w[i]){dist[x][0] = t.v + w[i];//权值累加if(dist[x][0] <= INF)heap.push({x,0, dist[x][0]});}}}}
}int main(){cin >> n >> m;memset(h, -1, sizeof h);while(m --){int t, a, b, c;cin >> t >> a >> b >> c;add(t, a, b, c), add(t, b, a, c);}dijkstra();int res = INF;// dist[n][i] 表示最后一段小路的长度为i的前提下，1到n的最短路// 我们通过dijkstra算法求得了合法的、最后一段是小路、但是小路长度不同的所有情况// 取min即可for(int i = 0; i <= 1000; i ++) res = min(res, dist[n][i]);cout << res << endl;
}
