- 博客(100)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 【拿去教女朋友】Python入门第一课
当下载好VSCode后，在扩展中搜索Chinese，Python拓展包安装，重新启动编辑器后生效。当安装好Python包后，此时不需要额外安装编译器，即可在VSCode中编译执行python代码。
2023-07-17 23:37:08
107
原创 【蓝桥杯国赛】游园安排
最长上升子序列 LIS 优化 二分与贪心 单调队列数据范围 1e6，如果用普通的LIS会超时。现在介绍优化版本：在单调队列中，保证所有字符串按照字典序单增。首先对题目进行字符串处理，按照顺序依次入队。入队满足两个条件：当前元素比队尾元素大，直接入队；当前元素比队尾元素小，二分找到第一个大于等于该元素的元素，替换它。最终的队列长度一定是该序列的最长子序列长度。(结论1)在每一次入队操作时，同时更新len序列(表示以第i个元素结尾的序列的最长子序列的长度)：当前元素比队尾元素大，长度为队列
2022-05-14 14:32:40
351
2
原创 ACM算法与竞赛协会第二次培训-图论-代码与题目汇总
目录前言洛谷题目编号DFSBFS拓扑排序链式前向星DijkstraDijkstra(堆优化)FloydPrimKruskal前言目录里面包含了所有上课提到的内容，这肯定不是一天能理解吸收的。我只有代码模板，但是不包含讲解，想深入了解的同学可以去各个平台搜对应的名字学习与补全自己的知识面。刷模板题可以去洛谷。洛谷题目编号dfs/bfsP1219 八皇后P2392 kkksc03考前临时抱佛脚P1443 马的遍历P1135 奇怪的电梯P2895 Meteor Shower SP1036
2022-05-06 16:58:15
255
原创 计数dp cf1426f Number of Subsequences
题目题意很简单，输入n(字符串长度),s(字符串)，字符串只包含a b c ? 四种字符。如果遇到? 字符串序列会分裂成三个，? 位置分别由a,b,c代替。问全部字符串序列中，abc子序列的数量。dp[i][0] 表示 到i位为至，a的数量dp[i][1] 表示 到i位为至，ab的数量dp[i][2] 表示 到i位为至，abc的数量数量转移有dp[i][j]=dp[i-1][j]+dp[i-1][j-1] j>=1dp[i][j]=dp[i-1][j]+1 j=0对于?产生的分裂，可以
2022-04-14 18:39:12
202
原创 计数dp cf404d
蓝桥杯两道我愿称为全是计数dp，昨天找了一道d，不敢练f。计数dp就是找规律，把情况找全进行转移即可。题目题意见题目。一开始设的情况不够用，后面补充全了。dp[i][0] 到第i位结尾，当前位为0dp[i][1] 到第i位结尾，当前位为1，且s[i-1]是一个雷dp[i][2] 到第i位结尾，当前位为1，且s[i-1]不是一个雷dp[i][3] 到第i位结尾，当前位为2dp[i][4] 到第i位结尾，当前位为雷如果是?就把?可以替代的情况都填一遍。#include<bits/
2022-04-14 14:38:52
131
原创 第十三届蓝桥杯省赛b组 两道dp补题
画积木推导见上图因为画布为2*n，只有两行，所以可以考虑每一种占满两行的方式，对每种方式做一个状态转移，得到的就是总方案数。#include<bits/stdc++.h>using namespace std;const int N=1e7+100;const int mod=1e9+7;typedef long long ll;ll f[N],sum[N];ll n;int main(){ cin>>n; f[0]=1;f[1]=1;f[2]=
2022-04-12 22:04:45
169
原创 KMP模板
先导概念s[ ] 模式串p[ ] 匹配串非平凡前缀 指除了最后一个字符以外，一个字符串的全部头部组合（前面连续的部分）非平凡后缀 指除了第一个字符以外，一个字符串的全部尾部组合部分匹配值 非平凡前缀和非平凡后缀的最大相似长度next[ ] 第i个元素的，前i个元素的字符串，的部分匹配值。与模式串匹配 若在下标i处匹配失败，若模式串与匹配串有一个以s[i]结尾的相似子串，那个就可以跳过这段匹配，把匹配串直接移动到下一个需要匹配的位置（匹配串的当前下标移动到len+1处，len为相似子串的长度）。
2022-04-02 16:37:32
812
2
原创 codeforce#edu125d 补题
现在是每日一题。最近争取能想出来个d。【题意】总共金币为 CCC ，士兵种类为 nnn 。每个士兵有三个属性 h 生命 d 攻击 c 购买费用有 mmm 次查询，每次查询：给出一个野怪的 H 生命 D 攻击需要满足：{h[i]∗d[i]∗cnt>H∗Dcnt∗c[i]≤C \left\{ \begin{array}{ll} h[i]*d[i]*cnt>H*D \\ cnt*c[i] \leq C \
2022-03-24 02:06:02
1147
原创 codeforce#dp专项
1 https://codeforces.com/problemset/problem/467/C【题意】给定一个长度为n的序列，找到k个长度为m的子串（不是子序列），求能得到的每个子串相加后的最大值。特别，子串下标不能重复且不能交叉 。iii 表示下标jjj 表示子串个数不新增子串，那最大值与上一次的状态相同；新增子串，那最大值为以当前下标 iii 结尾的 [i−m+1,i][i-m+1,i][i−m+1,i] 长度的子串，自然dp[i−m][j−1]dp[i-m][j-1]dp[i−m][j−
2022-03-13 00:11:46
422
原创 【桂林信息科技学院第一届程序设计大赛】完整题解 C++
目录A.Hello 小明B.博学多识的小明C.小明爱偶数D.小明爱打单词E.小明打篮球F.小明爱数学G.小明与张三H.小明拿宝藏I.小明的考试成绩J.小明与鲜花K.小明与小红的增删图游戏后记A.Hello 小明本题作为本场最简单的签到题，改编于hello world，想考察大家的字符串输入输出能力。#include<bits/stdc++.h>using namespace std;int main(){ string s; cin>>s; cout
2021-12-05 17:00:00
1066
原创 VMware中Ubuntu18.04连不上网
使用，共享主机IP地址模式状态，网络未连接，右上方无网络连接图标第二步仅第一次需要修改此方法虽然可以联网，但下次开机后仍会找不到网络，每次开机做一次一三步即可。所用命令在终端输入。第一步 删除NetworkManager缓存文件service NetworkManager stopsudo rm /var/lib/NetworkManager/NetworkManager.stateservice NetworkManager start第二步 修改/etc/NetworkManager/
2021-12-02 19:26:59
820
原创 【二分模板】
两场cf两个二分。今天压线过了c，心情有点激动。二分差点没把我心态搞崩。check()函数是判断是要选择哪个区间。求尽可能小二分区间 [l,mid],[mid+1,r][l,mid],[mid+1,r][l,mid],[mid+1,r]int l=1,r=n;while(l<r){ int mid=(l+r)>>1; if(check(mid)){ r=mid; }else{ l=mid+1; }}cout&l
2021-11-24 01:35:59
196
原创 线段树【模板】全面
导航栏点/区间线段树求和点/区间线段树求最大值更新(非替换)及查询最大值变型 2020 CCPC MianYang J点/区间线段树求和线段树，顾名思义，是把给定的n个元素组成的序列比作线段，以树的方式重建，进而达到更新，询问的时间复杂度都达到log2n\log_2nlog2n的级别。pushup建树过程中或者更新过程中，会先递归到叶子节点（不一定到叶子节点），然后再回溯，就是下一次回到他们两个的子树根节点，该点要记录两个子节点的和，所以pushup.当然再向上回溯同理，也是当前根等于他两个子节点
2021-11-06 00:50:19
119
原创 2021CCPC网络赛重赛-题解
(自己可能真的是个废物，理不出逻辑，错在小细节，不敢开新题，新题更没把握)难过周末。1006题意就是：前缀为nunhehheh，后缀为若干个a(不包括0个)，给定一个字符串，问有多少个满足条件的子序列。分析：先倒序维护一个在当前位置a有多少个的数组。再动态维护出一个dp[i][j]dp[i][j]dp[i][j]，表示在第i位以第j个操作数 结尾的子序列个数。opp="@nunhehheh"opp="@nunhehheh"opp="@nunhehheh"，第一位空出，防止i=0i=0i=0
2021-10-12 10:43:29
710
1
原创 在Ubuntu18.0中配置Vscode
补充一些配置过程中的坑。。如果想看完整教程网上搜。。网上也没有特别完整，只有相对完整。准备工作VMwareUbuntu开始在配置虚拟机设置的时候要注意，把网络适配器改成NAT。一开始用的本机，结果IP一直对不上。然后就可以愉快的上网了。如果不确定可以在Linux的终端上输入ping www.baidu.com看看能不能ping到。下一步，网络配好了，开始下载ubuntu-makesudo add-apt-repository ppa:ubuntu-desktop/ubuntu-m
2021-10-02 19:05:22
215
原创 《自己动手写操作系统》之 10分钟完成最小的操作系统
准备工作nasm 汇编编译器Floppywriter (File to image) 转换器VMware 虚拟机步骤先创建一个boot.asm的文件，我是用VsCode写的，记事本也可以。（还一直以为nasm是编辑器，结果是编译器，搜了半天教程。。 org 07c00h ; 告诉编译器程序加载到7c00处 mov ax, cs mov ds, ax mov es, ax call DispStr ; 调用显示字符串例程 jmp $ ; 无限循环DispStr: mo
2021-10-01 23:13:20
1371
2
原创 【Acwing Linux基础课笔记】shell语法
概论shell是我们通过命令行与操作系统沟通的语言。shell脚本可以直接在命令行执行，也可以将一套逻辑组织成一个文件，方便复用。Linux中常见的shell脚本有很多种：Bourne Shell (/usr/bin/shor/bin/sh)Bourne Again Shell (/bin/bash)…Linux系统中一般默认适用bash，接下来均为bash中的语法。文件开头需要写#! /bin/bash，指明bash为脚本解释器。脚本演示新建一个test.sh文件，内容如下：#!
2021-09-20 14:18:22
651
2
原创 【离线】可持久化数据结构（主席树）
权值线段树，又称主席树。权值线段树，每个叶子节点代表一个权值。每个节点都有权值，表示在当前区间内的数字个数。以该题为例，数据为1 5 2 6 3 7 4表示要查询的数组a[]。离散化离散化就是用键值对把所有数据的相隔距离变为1。例如1008 9 2 2 3数据集，可以通过编号:map[1]=2;map[2]=3;map[3]=9;map[4]=1008前提是需要对原数组排序并去重。//如果我的数据集存在<vector>中sort(d.begin(),d.end());//排
2021-09-06 19:08:23
110
原创 时间序列预测的七种方法-python复现
前提：数据集为JetRail高铁的乘客数量，网上搜一下可以找到。数据集共18288行有效数据，第一列对应 ID ；第二列为Datatime，格式为日-月-年+时间，时间间隔为一小时；第三列为Count，表示该时段内乘客数量。目录测试数据是否正确读入数据可视化（一）朴素法（二）简单平均法（三）移动平均法（四）简单指数平滑法(SES)（五）霍尔特(Holt)线性趋势法（六）Holt-Winters季节性预测模型（七）自回归移动平均模型（ARIMA）总结测试数据是否正确读入import pandas as
2021-09-05 21:10:02
4637
1
原创 高精度整合-vector写法-C++
高精度加法#include<bits/stdc++.h>using namespace std;const int maxn=100010;vector<int> x,y;vector<int> add(vector<int>& a,vector<int>& b){ if(a.size()<b.size()) return add(b,a); vector<int> c; int
2021-08-10 00:23:53
194
原创 链式前向星(C++)
因为在图论中总会遇到存图的情况，如果用邻接矩阵进行存储，相当于需要开辟 点 的平方的空间，但采用邻接表，有多少条边开辟多少空间，更节省空间。两种表达方式：用 top=0top=0top=0 存第一条边，边的个数范围为 [0,m−1][0,m-1][0,m−1]此时需要把头数组初始化为-1，memset(head,-1,sizeof(head)且在对某一点进行枚举边时(看该点与哪些点相连)，应该写成for(int j=head[i];~j;j=edge[i].next代表若下一条边的头是-1退出，
2021-08-02 18:32:19
815
2
原创 背包九讲 整理
该篇文章为了自己回顾基础，也为了下学期为社团讲解做个铺垫，本来想做ppt但是公式真是太折磨人了。主要是自己太菜了，想一直刷题，发现到后面想不出来，看题解也要看半天，仔细回想觉得是因为经典问题不牢固的原因。所有解题思路学习来源于acwing。01背包问题问题叙述： 有 nnn 件物品和一个容量为 vvv 的背包，每件物品只能选择一次。  
2021-07-30 22:09:14
196
原创 非精写版-51nod基础训练（终）
稳定婚姻参考文章首先介绍强连通分量：在有向图中，能形成回路的环。红色部分为强连通分量。在题目中，若夫妻离婚，男方要去找另一个女伴，然后迫使另一个女伴的夫妻双方离婚…过程描述为：男1->女2----男2->女3----男3->女4…男x->女1。一定是兜兜转转一圈之后最后有一个离婚的男选了最初离婚的女1，这样大家都配好了对，又重新组合成了n对夫妻，那么就说婚姻不是稳定的关系。（若有一部分人重新配对，但是有一部分人未拆散，保持原状，也称为重新组合成了n对夫妻）根据描述我们构
2021-06-15 00:36:33
116
原创 非精写版-51nod基础训练（4）
四点共面已知四个点，判断是否共面。可以求出三条向量，利用向量积求立方体体积，若体积是0，则四点共面。求出的三个向量：d1=(x1,y1,z1)d_1=(x_1,y_1,z_1)d1=(x1,y1,z1)d2=(x2,y2,z2)d_2=(x_2,y_2,z_2)d2=(x2,y2,z2)d3=(x3,y3,z3)d_3=(x_3,y_3,z_3)d3=(x3,y3,z3)V=d1∗d2∗d3V=d_1*d_2*d_3V=d1∗d2∗d3V=(x1y2z3+x2y3z1+x3
2021-06-11 14:20:29
123
1
原创 非精写版-51nod基础训练（3）
第一部分地址第二部分地址目录无向图最小生成树威佐夫游戏V2无向图最小生成树Kruskal算法，基于边选择的方法，适合稠密图。模板：#include<bits/stdc++.h>using namespace std;const int maxn=50050;struct node{ int fr,to,w;}e[maxn];bool cmp(const node &a,const node &b){ return a.w<b.w;}i
2021-06-08 22:37:13
120
1
原创 蓝桥杯国赛CB组 DP 总结
本质上升子序列题意： 给定一个长度为200的字符串，问当中有多少个本质不同的上升子序列。本质不同：子序列的字符串唯一。上升：字典序升序。tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtnip
2021-06-02 16:21:31
199
原创 非精写版-51nod基础训练（2）
衔接上篇点击跳转因为长度问题，一直发不出去，所以拆开来完成。目录中国剩余定理子段求和背包问题中国剩余定理看了好几个博客，推导的式子都是错误的，额，越看越难受。最后在b站找到了一个讲解视频，之前就看到过，后来又忘记怎么算了，写下来记录一下。栗子： 三三数余二，五五数余三，七七数余二，问数为多少。翻译：k%3=2k\%3=2k%3=2k%5=3k\%5=3k%5=3k%7=2k\%7=2k%7=2问k最小为多少。套用中国剩余定理的公式：x≡1(mod 3)x \equiv 1
2021-05-29 20:08:11
220
原创 非精写版-51nod基础训练（持续更新）
题目就不赘述了，来源51nod网站。最长公共子序列LCS这道题是一道非常好想的二维dp问题，可以在不选当前行，不选当前列的情况下（dp[i+1][j+1]=dp[i][j]+1)，若两个字符串中的字符相等，则有在原来的子序列基础上又增加一个字符；若两个字符串中的字符不相等，则寻找到此为止的最大的子序列的长度是多少，把值赋给它。dp[i][j]：表示第一个字符串取(0,i-1)，第二个字符串为(0,j-1)，最长的公共子序列是多长。最后在记录长度的同时，记录这个子序列的长度是怎么加过来的，记录完毕后从
2021-05-25 10:13:18
1239
2
原创 十一届蓝桥杯国赛 CB组（持续更新）
自己放松了几天，今天开始找状态，先从简单题入手。试题A答案：563#include<bits/stdc++.h>using namespace std;int main(){ int res=0; for(int i=1;i<=2020;i++){ int n=i; while(n){ int t=n%10; if(t==2){ res++;
2021-05-19 16:57:15
332
1
原创 蓝桥杯赛前一天——STL类库+各种函数调用+熟悉板子 总结
质数筛板子（埃氏筛）#include<bits/stdc++.h>using namespace std;const int maxn=1e5+100;int prime[maxn];int vis[maxn];int Prim(int n){ int p=0; memset(vis,0,sizeof(vis)); vis[0]=vis[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ prime[p++]=i; for
2021-05-08 18:00:11
349
2
原创 蓝桥杯真题训练 五一 5/5
A8位二进制=1字节1024字节=1KB1024KB=1MB25610241024*8/32=67108864B#include<bits/stdc++.h>using namespace std;int a[10];int main(){ for(int i=1;i<=100000000;i++){ for(int j=0;j<=9;j++){ if(a[j]>=2021){ cout<<i-1<<endl;
2021-05-05 18:13:02
124
原创 蓝桥杯真题训练 五一 4/5
1217 垒骰子矩阵快速幂op[i]表示的是与i的对面的数。如果有面互斥，就在矩阵中标记为零，否则标记为4，代表顶和底确定的时候可以有四种情况。（矩阵乘法）就是快速幂里面的乘法变成了矩阵乘法。#include<bits/stdc++.h>using namespace std;const int mod=1e9+7;typedef long long ll;const int maxn=6;ll n,m;int a,b;int vis[7][7];int op[]={3
2021-05-04 22:39:59
154
原创 蓝桥杯真题训练 五一 3/5
1215 小朋友排队题目被喂了一下，知道是求逆序对的题目，一开始也想到了排序，看题解有人用归并排序做。树状数组以前学过，忘记了，看了一手代码，又会了。二进制表示下最低位1及其后面的0构成的数值：lowbit(x) —> x & -x —> x & (~x+1) 取反加一。有些地方都写在注释里了。那再说一下思路：为什么做两遍树状数组，因为一个数的逆序对数，就是在它之前比它大的数，加上在它之后比它小的数。有了这个关系我们可以知道，一遍是为了求比在i之前，比当前（第i个）数大的
2021-05-03 12:49:31
70
原创 蓝桥杯真题训练 五一 2/5
1212 地宫取宝可真是醉了。这是记忆化搜索的题目，为了弄懂，又花了不少时间。记忆化搜索=深搜+动态规划题目要求的只能向下或者向右，所有只用了两个坐标。其实取模每次都应该取的，但是居然只在结果取模没爆，就没改。解题步骤：题目要求取k个物品，且每次取都不能比之前取过的所有物品的最大值小，可以在路径上选择取或者不取。设方程：dp[x][y][num][val] =n — 表示(x,y)位置下取了num个物品，当前最大物品的价值为val的情况下，共有n种情况。（1）考虑到不取也是一种情况，相当于
2021-05-02 22:10:23
86
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人