- 博客(203)
- 收藏
- 关注
RSS订阅原创 【160】相交链表
先找到较长的链表，并计算两个链表的长度之差dist，使长链表先进行遍历，走完这个长度之差dist，使得两个链表对齐。由于两个指针走的路程相同，所以若两链表相交，则p1，p2一定会在第一个交点处相遇。当p1遍历完headA或p2遍历完headB，我们让该指针去遍历另一个链表。使用两个指针p1，p2分别遍历headA和headB。若两链表相交，则p1，p2一定会在第一个交点处相遇。若两个链表不相交则p1，p2会同时指向空。若两个链表不相交则p1，p2会同时指向空。而后，令短链表和长链表同步开始遍历。
2023-10-14 16:59:12
145
原创 SMT求解器Q3B——在WSL上的Docker配置
其中，q3b为容器名称，v2为target。进入Q3B的安装目录，执行如下命令。下载完后，将如下文件更换为。
2023-10-07 20:38:52
840
原创 【ACwing算法基础课】第一讲
1. 快排模板1.1 快速排序算法思路：确定枢轴元素x（通常取：q[l]，q[r]，q[(l+r)/2]，随机）调整区间，使得x左侧元素皆小于等于x，右侧元素皆大于等于x递归处理左右两侧// 快速排序算法模板void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l]; while (i < j) {
2022-02-25 14:58:22
317
原创 SDUTOJ 整数变换问题
#include<bits/stdc++.h>using namespace std;#define maxn 105// n初始给定的数// m为目标值// minval最小操作步数// res数组，记录每一步操作int m, n, minval;char res[maxn];int dfs(int step, int num){ // 如果当前操作步数，大于最少操作步数 // 则该操作序列不可能为最少操作序列 // 剪枝 if (st
2021-11-29 15:11:53
582
原创 SDUT 1776 - 工作分配问题
#include<bits/stdc++.h>using namespace std;#define maxn 25int inf = 0x3f3f3f3f;// s数组记录工人和工作搭配的花费// visited数组记录工人是否已分配工作// sum记录当前累加的费用// n为输入数据大小// minval为最小费用int s[maxn][maxn], visited[maxn], sum, n, minval;void dfs(int i){ // 分配
2021-11-29 14:53:06
118
原创 SDUTOJ 1767 - 运动员匹配问题
#include<bits/stdc++.h>using namespace std;#define maxn 25// n输入的数据大小// maxval寻找最大竞争优势// sum累加当前竞赛优势int n, maxval, sum;// p为男方搭配优势// q为女方搭配优势// f标记当前女方队员是否已经搭配// res记录两个远动员搭配时的竞赛优势int p[maxn][maxn], q[maxn][maxn], visited[maxn], res[max
2021-11-29 14:39:56
192
原创 SDUTOJ 1764 - 子集和问题
#include<bits/stdc++.h>using namespace std;int a[10005]; // 存放集合s的数据int n, c, sum;int flag = 0; // 有解时flag=1int ans[10005] = {0};// 递归求解// 从pos处向后查找，sum记录此时的加和，top作为ans数组的游标void getRes(int pos, int sum, int top){ // 相加和大于c时，无解 // f
2021-11-28 22:56:38
239
原创 SDUTOJ 1751 - 区间覆盖问题
#include<bits/stdc++.h>using namespace std;int main(){ int a[10005]; // n个点，固定区间长度为k，count_num记录所用区间数 int n, k, count_num; while(cin>>n>>k){ for (int i = 0; i < n; i++){ cin>>a[i];
2021-11-28 16:43:21
145
原创 SDUTOJ 1743 - 最优合并问题
#include<bits/stdc++.h>using namespace std;bool cmp(int a, int b){ return a>b;}int main(){ int k; int a[1010], b[1010]; int minval = 0, maxval = 0; cin>>k; for (int i = 0; i < k; i++){ cin>>a[
2021-11-28 16:28:04
290
原创 SDUTOJ 1298 - 活动选择
#include<bits/stdc++.h>using namespace std;struct Active{ int start; // 活动开始时间 int finish; // 活动结束时间 int num; // 活动编号，从1开始}actives[110];int main(){ int n; cin>>n; for (int i = 0; i < n; i++){ cin>&g
2021-11-28 16:05:01
507
原创 SDUTOJ 2052 - 装船问题
#include<bits/stdc++.h>using namespace std;struct good{ int w; // 重量 int p; // 价值 int val; // 价值与重量之比}goods[15], tmp;// 冒泡排序，将货物按val值从大到小排列void my_sort(){ for (int i = 0; i < 9; i++){ for (int j = 0; j < 9-i; j+
2021-11-28 15:43:15
146
原创 SDUTOJ 1760 - 多元Huffman编码问题
#include<bits/stdc++.h>using namespace std;int main(){ int n, k, x; priority_queue<int, vector<int>, greater<int>> q1; // 从小到大排列的优先级队列 priority_queue<int> q2; // 从从大到小排列的优先级队列 cin>>n>>k; fo
2021-11-28 15:16:55
385
原创 SDUTOJ 1750 - 汽车加油问题
#include<bits/stdc++.h>using namespace std;int main(){ int n, k, dist[1005]; cin>>n>>k; int temp = n; int count_num = 0; // dist数组记录从上一站到第i站的距离 for (int i = 1; i <= k+1; i++){ cin>>dist[i];
2021-11-28 14:59:10
323
原创 SDUTOJ 2080 - 最长公共子序列问题
#include<bits/stdc++.h>using namespace std;int main(){ char s1[501], s2[501]; while (cin>>s1>>s2){ int n = strlen(s1); int m = strlen(s2); // dp[i][j]表示长度为i和长度为j时，两个序列的最长公共子序列长度 int dp[n+1][m+1]
2021-11-27 16:24:04
120
原创 SDUTOJ 1729 - 石子合并问题
#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3fint main(){ int n, k, a[202]; int dp_max[202][202], dp_min[202][202]; cin>>n; memset(dp_max, 0, sizeof(dp_max)); memset(dp_min, 0, sizeof(dp_min)); f
2021-11-27 15:54:13
186
原创 SDUTOJ 1730 - 数字三角形问题
#include<bits/stdc++.h>using namespace std;int main(){ // dp[i][j]存储当前位置到底部的最大和 int n, dp[101][101], a[101][101]; cin>>n; for (int i = 1; i <= n; i++){ for (int j = 1; j <= i; j++){ cin>>a[i][
2021-11-27 15:27:45
200
原创 SDUTOJ 1725 - 最少硬币问题
#include<bits/stdc++.h>using namespace std;#define INF 9999struct Coins{ int val; int count_num;}coins[15];int main(){ // dp[i]记录找i元所用最少的硬币量 int n, dp[20100], m; cin>>n; for (int i = 1; i <= n; i++){
2021-11-27 15:04:34
300
原创 SDUTOJ 3358 - 高数Umaru系列（9）——哈士奇
#include<bits/stdc++.h>using namespace std;int main(){ // n为狗数，x为钱数，p为每只狗的价格，m为每只狗的萌值 int n, x, p, m; while(cin>>n>>x){ int dp[110][1010] = {0}; // 当第i条狗被考虑在内时的最优解 for (int i = 1; i <= n; i++){
2021-11-27 14:34:26
142
原创 SDUTOJ 1722 - 整数因子分解问题
#include<bits/stdc++.h>using namespace std;// 数组a[i]记录i有多少种分解方式int a[500000];// 求解x有多少种分解方式long long func(int x){ // 默认一种，即x = x long long sum = 1; // 若x在50万以内，且已统计完分解方式，则直接返回 if ((x<500000) && a[x] != 0){ r
2021-11-26 16:23:53
139
原创 SDUTOJ 1018 - 骨牌铺方格
#include<bits/stdc++.h>using namespace std;// 类似斐波那契数列// a1 = 1, a2 = 2// a[i] = a[i-1] + a[i-2]int main(){ long long a[60] = {0}; a[1] = 1; a[2] = 2; for (int i = 3; i <= 50; i++){ a[i] = a[i-1] + a[i-2]; }
2021-11-26 15:52:02
201
原创 SDUTOJ 3664 - 顺序表应用7：最大子段和之分治递归法
#include<bits/stdc++.h>using namespace std;int a[50010] = {0};int count_num = 0; // 记录递归次数int sum = 0;int maxSub(int l, int r){ count_num++; // 统计递归次数 if (l == r){ // 递归出口 if (a[l] > 0){ sum = a[l]; }
2021-11-26 15:34:43
189
原创 SDUTOJ 1710 - 众数问题
#include<bits/stdc++.h>using namespace std;// 定义mode记录众数值，mul记录众数重数int mode = 0, mul = 0, n;// 该函数递归维护众数mode及重数mulvoid mode_func(int a[], int l, int r){ int mid = (l+r)/2; int count_num = 1; // 默认a[mid]的重数为1 int i, j; // 向左侧统计
2021-11-26 14:46:51
335
原创 788. 逆序对的数量
原题链接#include<cstdio>#include<iostream>#include<algorithm>using namespace std;/*note:在归并排序中逆序对(x, y)有三种情况 <1>x, y 属于 [l, mid] <2>x, y 属于 [mid+1, r] <3>x, y 分别属于 [l, mid] 和 [mid+1, r]对于前两种情况不必特殊处理，在递归过程
2021-03-25 11:41:30
76
原创 1231. 航班时间
原题链接#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;/*飞行时间的计算：设起飞时间是S，到达时间是E，单程飞行时间是X，时差是T。从A到B：S1+X+T=E1从B到A：S1+X-T=E2整理两式得：2X=(E1-S1) + (E2-S1)，答案就是X。可见，并不需要计算时差T，因为一去一回，互相抵消了
2021-03-25 10:52:25
105
原创 1245. 特别数的和
原题链接#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int main(){ int n; scanf("%d", &n); int res = 0; // 记变量i遍历[1, n]每个数，将i的每一位拆出来与2、0、1、9比对，含有其中一个则累加至res for (
2021-03-25 10:10:46
63
原创 787. 归并排序
原题链接#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int maxn = 100010;int n;int a[maxn], tmp[maxn];void merger_sort(int l, int r){ // 递归边界，即递归到单独一个数 if (l >= r){
2021-03-23 11:54:03
43
原创 466. 回文日期
原题链接#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check_valid(int date){ int year = date / 10000; int
2021-03-23 11:31:09
46
原创 895. 最长上升子序列
原题链接#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int maxn = 1010;int n, res = 0;int a[maxn], f[maxn];// f[]数组：以第i个数结尾的最长上升子序列的长度int main(){ cin >> n; for (
2021-03-23 10:35:51
48
原创 795. 前缀和
原题链接#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int maxn = 100005;int a[maxn], sum[maxn] = {0};// 前缀和计算思路：// 计算每一项的前缀项和// 令res = sum[r] - sum[l-1]计算区间[l, r]的和int ma
2021-03-11 11:38:46
49
原创 790. 数的三次方根
原题链接法一使用二分法确定浮点数的三次方根#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;int main(){ double n, mid; scanf("%lf", &n); double l = -10000; double
2021-03-11 11:05:09
135
原创 789. 数的范围
原题链接二分详解#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int nums[100005];// 二分查找，返回第一个大于等于k值的元素的位置int lowerBoundL(int l, int r, int k){ int mid; while (l < r){
2021-03-10 16:24:34
48
原创 整数二分详解
模板一在升序、无重复元素的数组中，查找值为k的元素的数组下标#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int n = 10;// 在给定数组中查找k值所在位置，若不存在则返回-1// l为二分下界，r为二分上界int binarySearch(int a[], int l, int r, int k){ int mid; /
2021-03-10 16:16:07
485
原创 1208. 翻硬币
原题链接#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn = 110;int n;char state[maxn]; // 用于存储题目给出的初始状态char target[maxn]; // 用于存储题目给出的目标状态// 翻转单枚硬币void turn(int i){
2021-03-10 13:35:15
46
原创 116. 飞行员兄弟
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef pair<int, int> pii;const int maxn = 5;char state[maxn][maxn]; // 存储题目给出的矩阵vector<pii> ans
2021-03-10 13:34:14
53
原创 1209. 带分数
#include<cstdio>#include<cstring>#include<algorithm>#include<cstring>using namespace std;const int maxn = 10;int target; // 题目给出的数int nums[maxn]; // 保存1~9，九个数的全排列结果int visited[maxn] = {0}; // 标记1~9，某个数是否被访问过int cnt; // 记录
2021-03-10 13:33:37
77
原创 93. 递归实现组合型枚举
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn = 30;int n, m;int position[maxn];// pos标识m个空中的当前位置，index标识在n个数中遍历的起始位置void dfs(int pos, int index){ // 若将剩余的n-i
2021-03-10 13:32:58
129
原创 95. 费解的开关
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int maxn = 6;char state[maxn][maxn]; // 存储游戏状态的矩阵，使用char类型方便一次输入一行char backup[maxn][maxn]; // 用于备份游戏状态int dx[5] = {-1, 0, 1, 0
2021-03-10 13:32:28
61
原创 717. 简单斐波那契
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int maxn = 50;int n;int nums[maxn]; // 存储数列int main(){ cin>>n; nums[1] = 0; // 将前两项的值直接赋予 nums[2] = 1;
2021-03-10 13:31:53
49
原创 94. 递归实现排列型枚举
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int maxn = 10;int n;int position[maxn]; // 数组position记录当前位置存放的数int visited[maxn]; // 数组visited标识当前数是否被访问过，0为未访问状态，1为已被访问// i
2021-03-10 13:31:18
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人