- 博客(57)
- 收藏
- 关注
RSS订阅原创 LL 代码库-打印沙漏
while(sum<=n){//sum 是num行的沙漏能有多少星星 星星超过n就结束循环。int pd(int kk){//kk 判断kk个符号 能产生几行沙漏。i-=2){//都是奇数。}//结束时星星是超的，所以要回退一步。return num;//输出ans行的沙漏。//记录输出几个空格。
2023-07-17 15:58:11
61
原创 USE方法——初步学习总结
USE方法对于所有的资源 查看他的Utilization 使用率、Saturation饱和率、errors错误。资源：服务器物理器件：CPU，总线 。某些软件资源。使用率：在规定时间内用于工作时间的百分比。部分资源也可表示为使用的容量占总量的比。饱和度：资源繁忙时等待队列的长度。错误：报错的个数。列举出系统资源，USE 方法会将分析引导到一定数量的关键指标上，这样可以尽快地核实所有的系统资源。建立一张尽可能完整的资源表，可能包括（CPU，内存，网络接口，存储设备，控制器，互联）USE
2023-04-11 20:45:40
126
原创 线性回归实验-SDUT
'''Author: your nameDate: 2021-11-16 19:52:20LastEditTime: 2021-11-16 21:53:58LastEditors: Please set LastEditorsDescription: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AEFilePath: \workspace\python\py1
2021-11-16 22:27:04
97
原创 2021 ICPC Jinan C Optimal Strategy
题意：题意很明确，n个值，两个人轮流取，问有多少种可能，然后取模。这个题意看看样例应该很好理解分析首先统计一下每个数的个数，然后顺序排好，就没有问题了。我推出的第一条性质是如果存在一个奇数个的大数，那么它一定会比这个数下面的数先被取走，偶数个数的大数，乃至偶数个的任何数都没有这个性质。由此再考虑偶数个的数字，我们发现偶数取的规律十分随意，但是呢，有一个很抽象的性质，对于后手来说，先手如果取了一个偶数个数的数，那么我作为后手一定会去选择一个比你大或者等于你的偶数的数，这里的前提是没有个数的数了，.
2021-11-16 13:02:23
717
原创 第二类斯特林数
概要：第二类斯特林数表示将n个不同的元素分成m个集合的方案数。代码s[i][j]实现代码：const int mod=1e9+7;//取模LL s[N][N];//存放要求的第一类Stirling数void init(){ memset(s,0,sizeof(s)); s[1][1]=1; for(int i=2;i<=N-1;i++){ for(int j=1;j<=i;j++){ s[i][j]=s[i-1][j-1
2021-08-23 21:03:10
2340
原创 2021-08-17
线段树1#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N =200010;int n,m,p;struct node{ int l,r; int v;}tr[4*N];void pushup(int u){ tr[u].v=max(tr[u<<1
2021-08-17 11:05:02
52
原创 杭电 1005 ( Median
题目链接Median问能否构成复合题意的分配，考虑到a(i) a(i+1)这个序列的中位数和a(i)是相同的，所以对于所有中位数可以先单独做一个分组，然后取最大连续不是中位数的数的长度，减掉这个序列之前的中位数个数前缀和，然后比较一下即可。#include <bits/stdc++.h>#define ll long long#define mem(a, b) memset(a, b, sizeof a)#define ull unsigned long long#define
2021-08-06 09:39:39
106
原创 数论题目打卡
acwing197 阶乘分解#include <bits/stdc++.h>#define ll long long#define mem(a, b) memset(a, b, sizeof a)#define ull unsigned long long#define INF 0x3f3f3f3f3f3f3f3f#define inf 0x3f3f3f3f#define rep(i, a, b) for (auto i = a; i <= b; ++i)#define
2021-08-05 21:45:57
117
原创 杭电5 1007
#include <bits/stdc++.h>#include <algorithm>#include <iostream>#define ll long long#define mem(a, b) memset(a, b, sizeof a)#define ull unsigned long long#define INF 0x3f3f3f3f3f3f3f3f#define inf 0x3f3f3f3f#define rep(i, a, b) for
2021-08-03 21:28:39
56
转载 二分求区间连续子串平均值最大，斜率求区间连续字串平均值最大
二分模板#include<iostream>#include<cstdio>#define fo(i,j,n) for(register int i=j; i<=n; ++i)#define ll long longusing namespace std;const int maxn = 1e5;int n,F;double a[maxn+5],b[maxn+5],sum[maxn+5];// b数组为a数组减去平均数mid，所以只要某一段和非负即说明平均数大
2021-07-27 10:10:09
218
原创 二分答案dp
给定一个序列，有n+2个数，选择一个数i能获得一个ai，至少获得w的前提下，选的数的最小间隔是多少，考虑用二分答案解决，用二分选择答案，然后进行check即可，然后对于可以的答案取mid和右边，不可以的考虑取左边和mid。对于check用dp进行，dp【i】代表从i到最后的n+1点通过最小x间隔能选出的最大值，对于第i个，我们知道要么选要么不选，若不选则dp【i】=dp【i+1】，选的话是dp【i+x+1】然后取max即可。代码如下/* * @Author: tunan * @Date: 2021
2021-06-29 21:26:27
115
原创 dp去重复补题Gym - 247727E Removal
给出一个n个数的序列，要求求出删除m个数字后能够产生的序列个数模1e9+7的结果。传送门显然是一个dp，考虑定义dp[i][j]为前i项删除j位后的种类数，显然j应当小于i求转移方程为：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]，可以理解为对于第i个数字，有选或者不选两种，选的话dp[i][j]是前i-1个删j个，否则的话是前i-1个删j-1个。但是会有许多重复的序列，考虑如何去重，考虑到只会在删除当前第i个以及前面的与第i个相同的之间的所有序列时，会产生重复，则减去删除这些后
2021-06-28 13:46:44
90
原创 2021-06-11
A#include<bits/stdc++.h>using namespace std;#define ll long long#define Test int T;cin>>T;while(T--)#define PI acos(-1)#define endl "\n"#define fx(x) fixed<<setprecision(x)#define sz(s) (int)s.size()#define all(v) (v).begin(),(v)
2021-06-11 21:22:37
84
原创 2021-06-09个人赛题解
B - Das Blinkenlights 签到题，求一下最小公倍数即可；#include <bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int n,m,t; cin>>n>>m>>t; int u=n*m/__gcd(n,m); if(u>t)cout<<"no"<<endl; else
2021-06-09 20:40:04
76
原创 A - CRC Test
传送门题意：给出两个数，k位数P，一个十六进制数，给定一种计算方法，如上图，分析之后发现每次计算前k位与p的异或，然后往后遍历。最后算出一个k-1位的余数即为答案。处理思路，用string把十六进制数处理成二进制，然后在该数末尾添加k-1个0，然后进行异或到位数等于k-1即可。#include <bits/stdc++.h>using namespace std;const int N=100050;string s,t,b,k;int p;bool a[40];void s
2021-05-26 10:16:30
394
原创 I - Inspecting Illumination 赛后题解
I - Inspecting Illumination题目传送门题意tips：本题是个交互题目，用cin，cout输入输出的话，不用考虑输入输出问题，正常做就行。本题的意思很简单，给你一个权限，
2021-05-17 20:38:35
130
2
原创 A - Abstract Painting 赛后题解
传送门A - Abstract Painting题意本题主要是定义一种格式，1X1正方体的四条边有两个不同颜色组成，每个颜色两条边，问nXm的矩形有多少种情况（共有三种颜色）。、推理一下规律，对于1X1的小正方形，共有四条边，选择两种颜色是C（2，3），放到对应位置是有三种情况，上左，上右，上下 颜色相同，是三种排法，然后选出的两种颜色各有两种排法，最后答案是3X3X2=18；那么对于1x2的小正方形，在一格小正方形已经确定了18种情况的基础上，只需要确定剩下的那个小正方形有多少情况，相乘即可，则
2021-05-17 20:10:45
86
原创 环形dp Patches
题目链接题意： 自行车轮被钉子扎了，有n个钉子，轮胎周长m，有两种补丁，长度a，b，补丁不能剪短，求覆盖所有的钉子需要多长的补丁（tips:在2 5 处有两个钉子，补丁长度为5，则只需要一个补丁即可）。算法： 考虑环形dp，首先需要考虑这是一个圈，并不是直线型的，所以一般考虑把前n个再接到后面去，求任意一个长度为n 的序列的答案，这个过程需要枚举起点操作。通过数组a来存储钉子的位置，存完n个以后，用a[n+i]=a[i]+m在后面再次储存n个位置，既可完成顺延操作。然后进行dp，枚举一个起点，用f[
2021-04-01 15:47:10
123
原创 操作数位的小tips
空集 0只有第i位为1 1<<in位全是1 (i<<n)-1判断第i位是不是1 if(S>>i&1)第i位 置1 S|(1<<i)第i位 置0 S&~(1<<i)nm取交 n&mnm取并 n|m...
2021-03-24 21:10:50
50
原创 字符串哈希
字符串哈希算法：取一个固定值P，把字符串看作p进制数，并分配一个大于0的数值，代表每种字符，一般来说，我们分配的数值都有远小于p。一般来说p取131或13331，此时hash的冲突率极低，只要hash值相同，我们就认为原字符串是相等的。实战演练：对于一串字符串：asdfasdjgjkhasd选取p为131我们用1代表a，2代表b，以此类推，那么我们对于每一个位都用p进制表示出来，比如；第一位是a，也就是1，这样1就可以表示a这个一个字符的字符串，那么如果字符串是as怎么表示呢，与数学的进制相同
2021-03-22 21:20:33
98
原创 开关问题 反转poj 3276
Face the right way题意分析：首先我们来看看对于一个特定的K如何求出让所有的牛面朝前方的最小操作次数。如果把牛的方向作为状态进行搜索的话，由于状态数有2的n次方个，是无法在时限内找出答案的。那么不搜索的话要怎么办呢？首先交换区间反转的顺序对结果是没有影响的。此外，可以知道对同一个区间进行两次以上的反转是多余的。由此，问题就转化成了求需要被反转的区间的集合。于是我们考虑一下最左端的牛，包含这头牛的区间只有一个，因此如果这头牛面朝前方，我们就能知道这个区间不需要反转。反之，如果这头牛面朝
2021-03-19 16:51:18
124
2
原创 尺取法.2 poj 3320
采用了map和set来协助尺取法的完成#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <map>#include <set>#include <algorithm>#include <vector>
2021-03-17 20:54:34
44
原创 尺取法poj3061
poj3061两个指针，l,r取sum[i]-sum[l-1] >=s 时记录长度不断l++ ；开始循环，直至边界。#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <map>#include <algorithm>
2021-03-17 20:31:15
111
原创 POJ NO.1064 Cable master
有N条绳子，它们长度分别为Li,如果从它们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留到小数点后2位。tips{N:1-10000 K：1-10000 Li 1-100000}这个问题通过二分搜索可以快速的找到答案，套用二分搜索的模型 试着解决这个问题。令：条件C（x）：=可以得到K条长度为x的绳子则问题变成了求满足C（x）的最大x，在区间初始化时，只需使用充分大的数INF（>MAX）作为上届即可：lb=0，hb=INF；代码如下：#include <
2021-03-14 17:20:49
78
原创 kingswalk——动态规划
kingswalk这题是一个简单的动态规划题:规则：给出n×n 的表格，国王可以向八个方向走，给出起点（x1,y1）终点(x2,y2);请输出最短路径的条数解：考虑最短路径的算法，可以对于x1,y1 x2,y2 分析后可以知道若二者x差距较大则每一步都要橫移，反之则竖移，以橫移为例：一共会有abs（x1-x2）次选择，对于每次选择，都有斜上下，或者橫移可选则将问题转化为：有p次操作，每次可以选择+1,-1，不变，从 x1 到x2有多少种变化方式。则考虑动态规划解决。将f[i][j]表示为第i
2021-03-07 17:57:54
60
原创 dp.3 最长公共子序列
## 最长公共子序列依旧是ｄｐ的入门题目，考虑用f[i][j]表示第一行的ｉ个字母与第二行的ｊ个字母能构成的最长解是多少，然后用当前阶段推下一阶段。对与dp[i][j],若arr[i]==brr[j]则f[i][j]取f[i-1][j-1]+1即可，若不等的话，则转移到f[i][j-1],或者f[i-1][j]即可，即不匹配后放弃第一行的ｉ或者放弃第二行的ｊ,取max即可。#include <iostream>#include <stdio.h>#include <a
2021-03-06 12:06:37
46
原创 dp.2 最长上升子序列
最长上升子序列解： 同样是动态规划入门的题目，我们用一个数组f[i]来表示在序列中，第ｉ位以前最长的上升子序列，用这个部分解来推算全部的解。对于第i个数时，我们考虑前i-1个数中的末尾小于arr[i]的最长子序列 ，取max即可, 详情见代码。#include <iostream>#include <stdio.h>using namespace std;const int N = 1200;int main(){ ios::sync_with_stdio(
2021-03-06 11:25:30
42
原创 dp.1数字三角形
### 数字三角形入门dp，倒着用数组把数累加起来即可#include <iostream>#include <stdio.h>using namespace std;const int N = 600;int main(){ ios::sync_with_stdio(0); int n,m; int arr[N][N]; cin>>n; for(int i=0;i<n;i++){ for(in
2021-03-06 11:09:50
50
原创 2021-02-22
题目链接题意：翻牌游戏，给出前面别人玩的游戏记录，输出你能推出的最大的答案数。tips：n张牌，若有n-2被成对确认后，答案是都能确认，若每对牌都有一张被掀开过，便可以推算对全部的牌。思路：标记已经被别人完成的牌。然后找出都出现过的一队的牌没被确认的牌。这里是ans然后求特殊情况：即能全推出来的情况。#include <iostream>#include <cstring>#include <cstdio>#include <queue&g
2021-02-22 12:40:53
85
原创 dp.2.5 最长上升子序列优化版 O(n)（请先弄懂dp的）
目标：是求一个序列中的最长的上升子序列现提出一个性质即：对于长度为n的上升子序列，我们只需要考虑序列末尾最小的数即可，比如存在一个2 3 4 和一个2 5 6我们只需要知道2 3 4这个序列，若后面还有别的数可以加在当前序列后面，比如来了一个7 可以把234 更新成2347 也可以把2 5 6更新成2 5 6 7，我们当然只需要一个就够了，所以贪心的思想，保存2 3 4 这个序列，我们现在把不同长度的子序列的末尾存起来，存在a数组中，即a[1]存长度为一的子序列的末尾，a[5]即存长度为5的子序列的末尾，
2021-02-19 15:57:45
152
原创 开春第一赛题解
B - Super Mancunian题目链接一个最小生成树板子题，最后需要求有多少可行路，即加入n-2条边后孤立的点的度即可；#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <map>#include <algorithm&g
2021-02-17 12:55:45
106
原创 树状数组入门
关于lowbit运算lowbit是找到数字x的二进制的最后一个一代表的数字， 例如lowbit(4)=lowbit((2)100)=100=4;lowbit(6)=lowbit((2)110)=10=2;lowbit(7)=lowbit((2)111)=1=1; while(x>0){ printf("[%d,%d]\n", }ss
2021-01-29 22:01:04
109
原创 最短路，迪杰斯特拉优先队列优化
#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <map>#include <algorithm>#include <vector>#include <cstring>using namespace
2021-01-24 22:28:28
128
原创 平方矩阵
题目输入整数N，输出一个N阶的二维数组。数组的形式参照样例。输入格式输入包含多行，每行包含一个整数N。当输入行为N=0时，表示输入结束，且该行无需作任何处理。输出格式对于每个输入整数N，输出一个满足要求的N阶二维数组。每个数组占N行，每行包含N个用空格隔开的整数。每个数组输出完毕后，输出一个空行。数据范围0≤N≤100输入样例：123450输出样例：11 22 11 2 32 1 23 2 11 2 3 42 1 2 33 2 1 24 3 2 1
2021-01-21 10:17:40
530
原创 八数码问题
八数码问题用bfs可以解决，但是需要解决一个问题，就是如何判重。判重的方法有一个是康托展开的方法，康托展开是特殊的哈希函数，可以计算出一个排列是所有排列按照字典序排序后的下标。具体计算函数如下；例如对于2143这个序列：对于第一位，查找后面的数字小于当前数字的个数，乘上后面位数的阶乘即可，得到的数即是哈希出的结果。然后用bfs不断swap即可#include <stdlib.h>#include <stdio.h>#include <iostream>#
2021-01-19 10:50:33
59
原创 结构体 共用体 枚举
1.结构体1.1结构体的定义与声明//1先声明后定义struct 结构体名{ 成员列表}；//最后的分号不可丢struct 结构体名 变量名;//2声明与定义同时进行struct student{ int num; char name[20]; int age; char sex; float score;}stu1,stu2;//3直接定义变量struct{ int num; char name[20];
2021-01-17 20:31:41
380
原创 2020-12-08
#include <bits/stdc++.h>using namespace std;int trie[1000000][26];int num[1000010];int pos=1;void Insert(char str[]){//在字典树中插入字符串，int p=0;//从根节点开始int len=strlen(str);for(int i=0;i<len;i++){//遍历每个字符if(str[i]>‘z’||str[i]<‘a’) return;/
2020-12-08 08:27:08
62
原创 Hash简单理解
简单哈希当我们对若干复杂信息进行统计时，可以用Hash函数把这些复杂的信息映射到一个容易维护的值域内，因为值域变得简单和范围变小， 会造成两个不同的原始信息被Hash函数映射成同一个值，所以我们要处理这种情况。有一种叫“开散列”解决方案是建立一个邻接表结构，以Hash函数的值域作为表头数组head，映射后的值相同的原始信息被分到同一个表头的链表中的不同部位，链表的节点可以存一些原始信息和数据。Hash主要有两个操作，一个是计算哈希后的值，第二个是定位到对应链表上依次遍历比较。建立一个大小等于值域的数组
2020-10-18 15:59:48
171
原创 T9-POJ 1415 模拟输入法＋字典树
字典树+模拟题意加算法代码解析题意加算法题意加算法这题要求我们模拟一下九键输入法输入数字推荐单词的算法，根据题意原题传送我们可以利用字典树来维护频率最高的前缀，来实现推荐，而那些频率不比其他同系列内单词高的前缀实际是没有意义的，例如abe 5abf 6因为在223这个数字输入情况下，这两个长度为三且属于223，即为同一模块的，但是abe频率低，所以理论上它永远也没有用了（针对本题意），所以我们只需要维护每个数字对应的最常出现的字符即可，在存字符串数量的时候要注意，因为是排好序的，所以我们只
2020-10-14 20:27:57
312
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人