- 博客(45)
- 收藏
- 关注
RSS订阅原创 LeetCode--阶乘后的零
题目链接解析n!=n∗(n−1)∗(n−2)∗......1n! = n*(n-1)* (n-2)*......1n!=n∗(n−1)∗(n−2)∗......1一个数尾部有多少个0取决于它的因数包含多少个10比如100包含两个10，1000包含3个10，而10 = 2 * 5所以转化为求质因子（2，5）有多少对，5的个数是多于2的n/5n/5n/5表示[1,n][1,n][1,n]中包含一个因子5的数的个数，为什么？比如20=4∗520=4*520=4∗5,那么20前面肯定有3∗5,2∗
2022-03-25 10:59:53
353
原创 LeetCode--字典序的第K小数字
题目链接题解来源于大佬评论–>这位大佬class Solution {public: int getSons(long cur, int n) { int sum = 0; int width = 1; 当前层的宽度 while (1) { if (cur + width - 1 <= n) { //当前层最大值小于等于n sum += width; //总结点数可以加上当
2022-03-23 21:15:57
444
原创 LeetCode周赛--射箭比赛中的最大得分
题目链接这次周赛做的好差，写的太慢这个题回溯，在每个靶子面前有两种选择，得分或不得分class Solution {public: vector<int> ans; int max1 = 0; vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) { vector<int> tmp; dfs
2022-03-20 19:14:31
881
原创 LeetCode--矩阵中的路径
题目链接这道题细节很多，一不小心就超时①引用传递，避免整体赋值②短路或，当值为真时便不会往下进行```class Solution {public: bool vis[210][210]; bool exist(vector<vector<char>>& board, string word) { memset(vis, false, sizeof vis); int n = board.size(), m =
2022-03-20 19:07:33
457
原创 LeetCode--排序序列
题目链接直接用暴力回溯的话会超时所以直接计算每个位置上的数字class Solution {public: string getPermutation(int n, int k) { int num[n + 1], vis[n + 1]; num[n] = 1; for (int i = n; i >= 1; i--) { //首先计算阶乘 num[5] = 24表示位置5上的数不变的话，后面的数有24种排列
2022-03-19 12:46:23
450
原创 洛谷--P1347 排序
题目链接每加入一个条件就要进行一次拓扑排序有以下三种情况：条件不足：多个入度为0、多个出度为0、当前能得出的序列长度小于总字母数量出现环路成功判断测试点14 6C<DC<BB<AC<DD<AA<AInconsistency found after 6 relations.#include <iostream>#include <queue>#include <vector>#includ
2022-03-18 21:59:16
459
原创 浙大上机题--最短路径问题
题目链接堆优化迪杰斯特拉#include <iostream>#include <queue>#include <vector>#include <cstring>using namespace std;typedef pair<int, int> pii;const int N = 1010;struct node { int to, d, m;};vector<vector<node>>
2022-03-18 20:20:02
219
原创 浙大上机题--继续畅通工程
题目链接要先计算连通分支的个数，最终只有一个连通分支即可#include <iostream>#include <algorithm>using namespace std;const int N = 5010;struct node { int wei, x, y, sta; bool operator < (const node& t) const { return wei < t.wei; }}e[
2022-03-18 18:23:09
230
原创 浙大上机题--还是畅通工程
题目链接最小生成树模板题#include <iostream>#include <algorithm>using namespace std;const int N = 5010;struct node { int wei, x, y; bool operator < (const node& t) const { return wei < t.wei; }}e[N];int f[110];int
2022-03-18 18:07:36
221
原创 浙大上机题--畅通工程
简单的并查集，主要复习模板题目链接#include <iostream>using namespace std;const int N = 1010;int f[N];int find(int x) { if (x != f[x]) return f[x] = find(f[x]); return f[x];}void merge(int a, int b) { int ta = find(a); int tb = find(b); .
2022-03-17 21:36:26
411
原创 LeetCode--字符串的排列
思路来源：传送门题目给的字符串是有重复字符的一开始自己做的是最后用vector去重的sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(), vec.end()), vec.end());但是感觉这样的话没什么难度然后看了别人的思路，学到了不少①首先通过在原有字符串上交换元素得到不同的排列，首先固定第一个位置，然后固定第二个位置，以此类推…②怎么做到的去重呢？比如字符串是这样baac，我们把第一个a放到索引0位置上，后面剩.
2022-03-16 18:22:46
784
原创 LeetCode--旋转数组的最小数字
思路来源：传送门关键点： 通过二分判断最小值出现的位置，然后不断缩小范围其中比较麻烦的一种情况就是numbers[mid] == numbers[r]此时可让r = r - 1（操作后仍可保证最小值在[l,r]内）证明：首先整体分为两部分，都是升序的根据 num[mid] >= num[l] >= num[r]和num[mid] == num[r]可得出num[l] == num[r]①若右半部分只有一个元素，则说明num[r]就是最小值，r-1后num[l]就是最小值，仍.
2022-03-16 16:45:47
125
原创 LeetCode--数组中重复的数字
原理：将索引和数组值关联起来，将数组元素放到自己的值对应的索引上，如果有重复的数字，则必会出现一个索引对应多个相同值的情况，即为答案。思路来源https://leetcode-cn.com/u/jyd/class Solution {public: int findRepeatNumber(vector<int>& nums) { int i = 0; while (i < nums.size()) { .
2022-03-15 17:41:01
201
原创 华科上机题--二叉排序树
题目链接#include <iostream>using namespace std;struct node { int val; node *l, *r; node(int x) : val(x), l(nullptr), r(nullptr) {}};int insertTree(node *&root, int x) { if (root == nullptr) { root = new node(x);
2022-03-14 20:37:45
449
原创 华科上机题--二叉树遍历
题目链接#include <iostream>using namespace std;struct node { char c; node *l, *r; node(char x ) : c(x), l(nullptr), r(nullptr) {}};node* buildTree(string pre, string mid, int pl, int pr, int ml, int mr) { if (pl > pr) {
2022-03-14 20:19:49
1443
原创 清华大学上机题-二叉树遍历
题目链接#include <iostream>#include <vector>using namespace std;struct node { char c; node *l; node *r; node(char x) : c(x), l(nullptr), r(nullptr) {}};node* buildTree(int &pos, string str) { if (pos >= str.size()
2022-03-14 19:52:05
2055
原创 LeetCode-得到要求路径的最小带权子图
题目链接这次周赛最后一题没搞出来太久没写dijkstra，模板都忘了深夜补题，收获颇丰，学到了很多新的写法关键点：反向建图如果正常建图的话，求n - 1个点到目的点需要n - 1次djk，而反向建图的话只需要一次，即把目的点作为原点typedef long long ll;typedef pair<int, int> pii;typedef pair<long long, int> pli;class Solution {public: long
2022-03-14 00:14:16
437
原创 DFS-A Knight‘s Journey
题目链接关键点：注意输出时的字母要按字典序，具体就是深搜时的方向排序问题#include <iostream>#include <queue>#include <algorithm>#include <cstring>#include <vector>using namespace std;struct node { int x, y; node(int a, int b) : x(a), y(b){};}
2022-03-12 23:04:44
187
原创 清华大学上机题--玛雅人的密码
清华上机题链接#include <iostream>#include <string>#include <queue>#include <unordered_map>using namespace std;struct node { string s; int cnt; node(string x, int y) : s(x), cnt(y) {};};unordered_map<string, bool>
2022-03-12 21:57:46
177
原创 Catch That Cow--宽度优先搜索
题目链接#include <iostream>#include <climits>#include <queue>using namespace std;const int N = 100010;struct node { int pos, t; node(int x, int y) : pos(x), t(y){}};int ans;bool flag[N];queue<node> q;void bfs(int cu
2022-03-12 20:12:52
346
原创 今年暑假不AC
时隔一年半重写，区间贪心按右端点排序题目链接#include <iostream>#include <vector>#include <algorithm>using namespace std;struct node { int st, ed; bool operator < (const node &t) const { if (ed != t.ed) return ed < t.ed; .
2022-03-09 20:52:45
36
原创 矩阵快速幂
题目-矩阵幂模板#include <iostream>#include <algorithm>#include <string>#include <cstring>using namespace std;const int N = 15;struct Matrix { int v[N][N]; int row, col;};Matrix mutil(Matrix a, Matrix b) { Matrix c;
2022-03-08 22:48:59
90
原创 求约数个数
约数的个数约数定理#include <iostream>using namespace std;const int N = 1e5 + 10;int primes[N];bool st[N];int cnt = 0;void getPrimes() { for (int i = 2; i < N; i++) { if (!st[i]) primes[++cnt] = i; for (int j = 1; i * prime
2022-03-07 19:54:54
100
原创 欧拉筛--质因数的个数
关键点: 每个合数只被最小的质因数筛掉int primes[N];bool st[N];int cnt = 0;void getPrimes() { for (int i = 2; i < N; i++) { if (!st[i]) primes[++cnt] = i; for (int j = 1; i * primes[j] < N; j++) { //i的质因数肯定比primes[j]大，所以就保证了primes.
2022-03-07 15:14:53
284
原创 清华大学上机题--10进制 VS 2进制
10进制 VS 2进制一系列高精度操作#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;//高精度除以低精度（2）void div(string &s) { string ans = ""; int r = 0; for (int i = 0; i < s.leng
2022-03-06 12:32:28
140
原创 清华大学上机题--进制转换
进制转换清华大学上机题十进制转二进制，十进制最多有30位主要用高精度除以低精度#include <iostream>#include <vector>#include <algorithm>using namespace std;void div(vector<int> &v) { vector<int> c; int r = 0; for (int i = 0; i < v.size(
2022-03-05 22:05:23
201
原创 LeetCode-下一个排列
题目整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。例如，arr
2022-02-27 21:59:47
65
原创 LeetCode-完成旅途的最少时间
题目给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟 旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间ps想了半天没想出来二分，做题太少class Solution
2022-02-27 17:38:19
8756
1
原创 Educational Codeforces Round 100 (Rated for Div. 2)补题记录
总结：感觉这个educational场好难啊（蒟蒻视角），又被虐了，唉A. Dungeon每一枪会造成1点伤害对一个单位，但是当开7的倍数枪时会造成3点伤害每7次一个轮回，一个完整的轮回共造成9点伤害，如果最后一起死，那个最小值至少需要承受每个轮回的1点伤害#include <bits/stdc++.h>#define lowbit(x) ((x) & (-x))using namespace std;typedef long long ll;int main(
2020-12-18 22:47:32
249
1
原创 Codeforces Round #689 (Div. 2, based on Zed Code Competition)补题记录
总结：补完题收获还是蛮多的，多多积累，希望量变能形成质变~A - String Generation关键点是回文串的长度不超过k，那就直接设置为1就好了，循环输出“abc”#include <bits/stdc++.h>#define lowbit(x) ((x) & (-x))using namespace std;typedef long long ll;string str = "abc";int main() {#ifndef ONLINE_JUDGE
2020-12-17 19:57:25
114
原创 Codeforces Round #690 (Div. 3)全部题解
总结：这是在cf上打的第二场比赛，做的太慢了，后面几题也没有思路，需要继续刷题A. Favorite Sequence先输出一个头部的元素，然后输出一个尾部的元素如果有奇数个，必然中间会剩余一个，直接输出就好了#include <bits/stdc++.h>#define lowbit(x) ((x) & (-x))using namespace std;typedef long long ll;const int N = 2010;int a[N];int m
2020-12-16 21:05:21
311
原创 多项式除法c++
L2-018 多项式A除以B (25分)（最近重刷PTA天梯赛的题目碰到这个题，还是无从下手，所以写篇博客记录一下）//输入是以指数递减的形式依次输入每一项4 4 1 2 -3 1 -1 0 -13 2 3 1 -2 0 1//输出和输入格式一样，依次输出商和余数3 2 0.3 1 0.2 0 -1.01 1 -3.1样例图解题目代码#include <bits/stdc++.h>using namespace std;typedef long long ll;
2020-11-24 16:25:23
1756
原创 P4588 [TJOI2018]数学计算
题目分析对一个数进行q次操作，每次操作输出结果显然 可以使用线段树（区间乘积），建树时所有节点设为1， 最后输出ans[1]即可我们把每次操作的结果作为一个叶子节点，乘法直接乘m即可，如果是除法，则把pos次位置的值变为1题目代码#include <bits/stdc++.h>using namespace std;typedef long long ll;#define lowbit(x) ((x) & (-x))const int inf = 0x3f3f3f3f
2020-11-21 11:54:22
128
原创 两圆相交求面积c++
题目给定2圆的圆心坐标和半径，计算并输出两圆相交的面积，如果是外切或不相交，则输出0，圆周率取函数值acos(-1)。输入格式:输入6个整数x1 y1 r1 x2 y2 r2，分别表示两圆的圆心(x1,y1),(x2,y2)和半径r1,r2。输出格式:根据圆的位置关系，输出其相交部分的面积（保留2位小数）。输入样例:在这里给出2组输入。例如：0 0 1 2 2 12 0 2 5 2 3输出样例:在这里给出相应的输出。例如：0.003.22//此处PI值为acos(-1)//
2020-11-21 10:45:05
1211
原创 近期所学算法总结（未完待续~~~）
前序最近为了准备天梯赛，刷完PTA的天梯赛题目之后（并没有），又转向了洛谷的官方题单，学到了不少算法和知识点，又到周末了，所以总结一下~
2020-11-20 12:23:08
123
1
原创 P3387 【模板】缩点 (Tarjan + 拓扑 + dp)
题目链接题目分析题目要求出一条路径，保证此路径经过的所有点的权值和最大，并且每个点可以重复走，但是权值只计算一次，因此对于每一个强连通分量可以看作一个缩点，然后求对这些缩点拓扑排序（目的是为了后面的dp，因为在dp的过程中，要依次往后更新值），拓扑完成后进行dp，求出最大值题目代码#include <bits/stdc++.h>using namespace std;const int N = 100010;struct node { int from, to, nx
2020-11-20 11:36:33
153
原创 7-8 整数拆分 (20分)
将一个正整数拆分成若干个正整数的和。输入格式:一个正整数n输出格式:若干行，每行一个等式（每个数或者等号间都有一个空格，第一个数前没有空格，最后一个数后面没有空格，数与数之间要求非降序排列）。最后一行给出解的总个数输入样例:在这里给出一组输入。例如：4输出样例:在这里给出相应的输出。例如：4 = 1 + 1 + 1 + 14 = 1 + 1 + 24 = 1 + 34 = 2 + 24题解：#include <iostream>#
2020-11-01 22:34:24
1140
原创 八皇后问题集合
基础八皇后在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法输入格式:共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；输出格式:共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量输入样例:在这里给出一组输入。例如：185输出样例:在这里给出相应的输出。例如：19210题解：#incl
2020-11-01 22:32:01
359
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人