1.完成了P2021 faebdc玩扑克
2.完成了B3603最短树问题
1.P2021
思考:这是一个约瑟夫环的问题,使用双重循环,外层循环遍历1
到n,
表示当前要填入的数字。
内层循环用于找到数组中下一个可以填入的位置。
-
每次内层循环会尝试跳过
2
个位置(j
从1
到2)
。 -
如果跳过2个位置后超出数组范围(
s>n)
,则通过s-=n
将位置回绕到数组开头。 -
如果当前位置已经被赋值(
a[s]!=0
),则继续向后查找,直到找到一个未被赋值的位置。
#include<stdio.h>
int a[1000001]={0};
int n;
int main()
{int s=0;scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=2;j++){s++;if(s>n){s-=n;}while(a[s]!=0){s++;if(s>n){s-=n;}}}a[s]=i;}for(int i=1;i<=n;i++){printf("%d ",a[i]);}return 0;
}
2.B3603
思考:使用并查集的相关知识,查找父节点,使用qsort函数进行比较,使用kruskal算法计算结果并输出。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int n, m, ans;
int f[100001];struct node {int x, y, val;
} a[100001];// 并查集的 find 函数,带路径压缩
int find(int x) {if (f[x] == x) {return x;}return f[x] = find(f[x]); // 路径压缩
}// qsort 的比较函数
int cmp(const void *m, const void *n) {struct node *a = (struct node *)m;struct node *b = (struct node *)n;return a->val - b->val; // 按 val 升序排序
}int main() {// 输入 n 和 mscanf("%d %d", &n, &m);// 初始化并查集for (int i = 1; i <= n; i++) {f[i] = i;}// 输入边的信息for (int i = 1; i <= m; i++) {scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].val);}// 对边按权值升序排序qsort(a + 1, m, sizeof(struct node), cmp);// Kruskal 算法求最小生成树for (int i = 1; i <= m; i++) {int nx = find(a[i].x);int ny = find(a[i].y);if (nx != ny) {f[nx] = ny; // 合并两个集合ans += a[i].val; // 累加边的权值n--; // 减少连通分量数量}if (n == 1) { // 如果只剩一个连通分量,退出循环break;}}// 输出最小生成树的权值和printf("%d", ans);return 0;
}