第十二次CCF-CSP认证
最小差值
满分题解
遇到的问题
虽然没啥好说的，就是遍历一下数组找到最小差值（最小为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;//最后一段小路的长度y
if(f[i]){// 小路
y += w[i]; //小路长度更新
if(y <= 1000){ // 小路长度不会超过1000
if(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;
}