- 博客(37)
- 收藏
- 关注
RSS订阅原创 线段树基础+例题
一、问题——一定要开四倍空间啊啊啊1）query过程中区间的情况讨论设Tl,TrT_l,T_rTl,Tr为线段树中的区间左右端点，l,rl,rl,r为查询的区间左右端点[l,r]⊃[Tl,Tr][l,r]\supset[T_l,T_r][l,r]⊃[Tl,Tr]，直接返回，不再进行往下搜索——由于这一步的剪枝可以时query操作控制在==O(4∗logN)O(4*logN)O(4∗logN)==的复杂度[l,r]∩[Tl,Tr]≠∅[l,r]\cap[T_l,T_r]\neq\em
2022-05-17 09:03:32
902
3
原创 “统信杯” 第十七届黑龙江省大学生程序设计竞赛 Let‘s Swap
Let’s Swap（思维+hash）4星题意：已知一个长度为n的字符串SSS，可以对字符串进行一种操作：将字符串SSS从下标i(1≤i≤n)i(1\leq i\leq n)i(1≤i≤n)的位置将串分为两个串A、BA、BA、B将字符串SSS变为BABABA反转字符串SSS给你两个数a、ba、ba、b代表可以选取的下标的位置，允许操作任意次（或不操作）问SSS是否可以通过操作变成目标串CCC多组输入1≤T,sum∣S∣≤5∗5101\leq T,sum|S|\leq 5*5^{10}1
2022-05-16 08:16:59
1400
原创 2021 年第十三届四川省 ACM-ICPC 大学生程序设计竞赛
Spicy Restaurant（多元BFS）4星题意：给你一个nnn个点mmm条边的无向图，每个点有一个权值www，qqq次询问问从点aaa出发走到权值小于等于bbb的点的最小距离，不能满足输出-11≤n,m≤1051\leq n,m\leq 10^51≤n,m≤1051≤wi,bi≤1001\leq w_i,b_i\leq 1001≤wi,bi≤1001≤ai≤n1\leq a_i\leq n1≤ai≤n题解：因为权值的范围比较小，所以我们可以按照权值跑BFS记录每种情况每个点到权值
2022-05-14 10:05:07
839
原创 2021 ICPC 江西省大学生程序设计竞赛 Character Distance
Character Distance（思维、模拟）4星题意：给你一个有nnn个元素的序列，要求选择其中任意至少一个数，使对于这个数在序列中的位置间隔恰好为m(1≤i<j,ai=aj=x,m≤j−i)m(1\leq i< j,a_i=a_j=x,m\leq j-i)m(1≤i<j,ai=aj=x,m≤j−i)且要求序列满足字典序最小，若无法满足输出-11≤n,m≤1061\leq n,m\leq 10^61≤n,m≤106题解：只需要找到一个数让他满足上述条件即可当有元素
2022-05-14 10:03:41
369
2
原创 GDCPC广东省大学生程序设计竞赛部分题解
Industrial Nuclear Water（计算几何）3星题意：给你两个点，问这两个点是否在所给三个面的同一侧1000∣x∣=y2+z2,1000∣y∣=x2+z2,1000∣z∣=x2+y21000|x|=y^2+z^2,1000|y|=x^2+z^2,1000|z|=x^2+y^21000∣x∣=y2+z2,1000∣y∣=x2+z2,1000∣z∣=x2+y2题解：判断两点是否在一个面的同一侧，只需将点带入方程看结果是否符号一致#include<bits/stdc++.h>
2022-05-14 10:02:27
1436
原创 2021辽宁省大学生程序设计竞赛
比赛!（差分约束+虚拟源点）4星题意：按照a:bca:bca:bc的形式给你三个队伍的顺序（b>=a>=cb>=a>=cb>=a>=c），输出一种满足所有输入的方案，否则返回No Answer题解：注意可能题目给的队伍不完全联通，需要用虚拟源点连接一定要能从源点出发走到所有点最短路#include<bits/stdc++.h>using namespace std;const int N=510;string s;int n,cnt=0;
2022-05-14 09:54:00
948
原创 DP模板—状压DP
一、状压DP利用二进制表示当前状态二、例题（1）蒙德里安的梦想当我们先尽可能摆放完1∗21*21∗2的方格时，剩下的空格的摆放方式是唯一的——只能用2∗12*12∗1补完或不能构成合法方案所以我们考虑只摆放1∗21*21∗2方格的方案并分析能否构成一个合法方案，状态表示：f[i][j]代表前i−1列已经用1∗2的方格摆放好，且从第i−1列伸出到第i列为状态j的所有方案f[i][j]代表前i-1列已经用1*2的方格摆放好，且从第i-1列伸出到第i列为状态j的所有方案f[i][j]代表前i−1列
2022-05-05 16:22:46
308
原创 DP模板整理—背包、线性、区间、计数类
一、背包问题01背包问题题解：ACM_01背包（恰好装满）解题思路：求01背包恰好装满时得到的最大价值，应该这样初始化：①dp[0]=0，表示背包容量为0时得到的最大价值也为0；②dp[1～W]=-inf，表示背包容量为其他状态下都为非法状态（未装满），因为我们还要求解恰好装满的情况下得到的最大价值。那么在求解过程中，由于动规的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，所以如果子问题状态是非法的(-inf)，则当前问题的状态依然非法，即不存在恰好装满
2022-03-26 12:11:21
1536
原创 AcWing基础课最小生成树模板
Prim算法（O(n2)O(n^2)O(n2)）1）算法流程：设集合S为生成树集合，T为原始集合n次操作：1、找到集合中T中距离距离集合S最近的一个点加入集合S中2、利用该点更新T中其余点距离集合S的距离#include<bits/stdc++.h>using namespace std;const int N=510;int n,m;int g[N][N];int dist[N];bool vis[N];int prim(){ int res=0;//计算
2022-03-23 20:48:52
578
原创 AcWing算法基础课贪心模板题
一、区间问题区间选点、最大不相交区间数量题解：1）如何选点？（1）将每个区间按右端点递增排序、（2）从前往后遍历每个区间，如果当前区间中已经包含点，跳过，否则选取当前区间的右端点PS:此方法选择的点必然是序列中无交集的区间的数量，所以此方法适用于两题2）证明？最优解ansansans：所有合法方案中的最小值，贪心解cntcntcnt：上述选法（1）上述选法必然会使每个区间里至少包含一个点，是一种合法方案，所以ans<=cntans<=cntans<=cnt（2）通过贪心
2022-03-14 20:30:03
859
3
原创 dos、cmd及常用命令、windows快捷键
dosDOS，Disk Operating System（磁盘操作系统），主要是一种面向磁盘的系统软件，就是人给机器下达命令的集合，是存储在操作系统中的命令集合。DOS是早期的计算机操作系统，是单任务单用户的，每次只能执行一个程序，界面是文字交互，所有操作都需要使用命令windows是图形界面操作系统，多任务多用户，可同时执行多个程序cmd（windows操作系统环境）Command Prompt（命令提示符），是windows下的32位命令行程序，是在windows下模拟dos环境的一个程序，可
2021-09-04 11:06:17
428
原创 Web基础知识
**为啥我啥都不知道 **在计算机网络技术中，通常涉及两张网——Network和WebNetwork主要指硬件网络，包括了TCP/IP（Transmission Control Protocol/Internet Protocol）四层网络体系中的三层，即主机—网络层、互联层、传输层，是由实现了这些层级协议的硬件设备，如网线、网卡、中继器、集线器、交换机、路由器、计算机（安装网络操作系统，即实现TCP/IP的操作系统）等组成的。WebWorld Wide Web（全球广域网、万维网），主要指软件网
2021-09-04 10:00:51
1321
原创 acwing数论（痛苦面具非完整版）
质数试除法判断质数（素数）（O(sqrt(n)）质数一定是严格大于一的整数，如果只包含1和本身这两个约数，就成为质数（素数）#include <iostream>#include <algorithm>using namespace std;bool is_prime(int x){ if (x < 2) return false;//注意是质数的条件 for (int i = 2; i <= x / i; i ++ )//注意循环条
2021-08-20 20:20:45
271
原创 在家复健前两天
Multiple of 2019（前缀和+同余）同余的知识以后再补（大概）解题思路：根据同余的思想，每次寻找字符串片段**s[i,s.size()-1]**对2019取余的值，若该值在之前出现过，则说明此片段是2019的倍数所以我们可以每次求字符串的后缀和，用一个数组cnt存储它出现的次数，加入到次数ans中，代码如下#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+
2021-08-17 20:15:46
255
原创 AcWing基础课最短路模板
朴素Dijkstra（稠密图，O(n^2)）集合S为已经确定最短路径的点集。初始化距离 一号结点的距离为零，其他未确定最短路的结点的距离设为无穷大。循环n次，每一次将集合S之外距离源点最短的点X加入到S中去（这里的距离最短指的是距离1号点（源点）最近。点X的路径一定最短，基于贪心）。然后用点X更新X邻接点的距离。寻找路径最短的点：O(n^2)加入集合S：O(n)更新距离：O(m)（实际就是每条边都比较一遍）使用邻接矩阵存储#include<bits/stdc++.h>.
2021-08-12 12:45:58
364
原创 acwing数据结构
单链表#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int e[N],ne[N],head=-1,idx;void add(int k,int x){//插入到下标为k的点的后面（下标从0开始） e[idx]=x; ne[idx]=ne[k]; ne[k]=idx++;}void add_head(int x){//插入在头节点上 e[idx]=x; ne[idx]
2021-08-06 21:04:26
205
原创 中石油补题题板
目录2021-5-14问题 K: 立方问题 L: 排队2021-5-16问题 M: 一箭多雕问题 L: 鸭子唱歌问题 E: Memory Overflow2021-5-14问题 K: 立方今年乐乐开始学编程了，上几天刚刚解决了一个平方数的问题，问题是这样的：随便告诉你一个不超过 1 个亿的正整数，请你算出不超过该数的所有立方数的个数。但是，如果这个超过 1 亿，是一个 18 位正整数，或 28 位的正整数呢？乐乐不会算，你会吗？输入只有一行且只有...
2021-05-16 14:30:58
612
1
原创 中石油补题
2021-5-15问题 L: 排队思路：构造“循环节”#include<bits/stdc++.h>using namespace std;vector<int>v;int n;int ans(vector<int> v){ vector<int>ve(v); sort(ve.begin(),ve.end()); map<int,int>ma; int n=ve.size(),m=0;
2021-05-15 10:04:27
479
原创 cf补题
2021-5-14B. Nice Matrix思维+贪心：构造一个每行每列都是回文结构的矩阵——找出使矩阵的f[i][j],f[n+1-i][m+1-j],f[n+1-i][j]+f[i][m+1-j]四点的值变为同一值的最小改变量 如何找出最小改变量？——找四个数中的任意三个数的中位数证明（数学归纳法）假设四个数为 a=1，b=20，c=80，d=100由此可知当b为中位数时：sum=c-a+d-b（选abc）sum=d-a+c-b（选abd）当c为中位数时
2021-05-15 09:53:47
269
1
原创 朴实无华的总结+题解
2021.4.5Ⅰ.pta-谷歌的招聘素数的遍历条件可以缩减为：（最后一个测试点）for(int i=2;i*i<a;i++)截取字符串中连续子串 substrate()#include<bits/stdc++.h>using namespace std;int main(){ string s="12345789",s1; int k; cin>>k; for(int i=0;i<9-k;i++){ s1=s.substr(i,k
2021-05-15 09:53:15
166
原创 DFS，BFS初步学习
7-2 输出全排列 (20 分)#include<bits/stdc++.h>using namespace std;int vis[11],a[11],n;void dfs(int flag){ if(flag==n+1){ for(int i=1;i<=n;i++) cout<<a[i]; cout<<endl; return ; } for(int i=
2021-05-05 23:34:32
126
原创 五一补题
7-5 田忌赛马·Hard先同easy版对比一下：7-4 田忌赛马·Easy解决方法：对两组进行排序，如果a[n-i-1]>b[k-i-1]，则k++;解题思路：——二分根据题目可知，我们寻找的是从某一天开始a中的????至少获胜k场，那么在这一天之前获胜场数一定是小于k，根据这种性质（类似于单调性）我们可以判断我们设定的第M天是在答案天数的左侧还是右侧，从而可以利用二分解决这个问题。蒟蒻的代码：#include<bits/stdc++.h>us
2021-05-04 11:40:27
116
原创 acwing基础算法
第一章Ⅰ.快速排序void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l], j = l; for (int i = l + 1; i <= r; i ++ ) if (q[i] < x) swap(q[ ++ j], q[i]); swap(q[l], q[j]); quick_sort(q, l, j - 1); qu
2021-05-02 18:08:47
3467
1
原创 二分模板——数的范围
789. 数的范围先用二分求出x的左边界——a[mid] >= x（mid在x的右边，所以右边界变为mid）即：if(a[mid] >= x) r = mid;else l = mid + 1;根据模板得出midmid = l + r >> 1;若得出的左边界值不为x，则满足x不存在与数组中，输出“-1 -1”若等于x，二分求右边界——a[mid] <= x（mid在x的左边，所以左边界变为mid）即：if(a[mid] <= x
2021-05-01 11:03:18
177
原创 Unread Messages
Unread Messages题目描述There is a group of people in an internet email message group. Messages are sent to all members of the group, and no two messages are sent at the same time.Immediately before a person sends a message, they read all their unread messag
2021-04-15 18:26:18
660
原创 STL-set
标准库提供set关联容器分为：1，按关键字有序保存元素：set(关键字即值，即只保存关键字的容器)；multiset(关键字可重复出现的set)；2，无序集合：unordered_set(用哈希函数组织的set)；unordered_multiset(哈希组织的set，关键字可以重复出现)。set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡
2021-03-19 18:58:17
199
原创 STL-map
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值，可类比函数）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。//第一种#include<map>#include<string>#includ
2021-03-18 00:32:14
121
原创 STL-vector
1.STL（Standard Template Library），也被称为标准模板库，包含大量的模板类和模板函数，是C++提供的一个由一些容器、算法和其他一些组件组成的集合。用于完成诸如输入/输出、数学计算等功能。STL被内置到支持C++的编译器中。在C++标准中，STL被组织为13个头文件：<iterator>，<functional>，<vector>，<deque>，<list>，<queue>，<stack>
2021-03-16 20:05:45
283
原创 大一下第一周
Ⅰ.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（不仅数据元素所包含的数据的个数要相同，而且对应数据项的类型要一致）数据的存储结构是指（数据的逻辑结构在计算机中的表示）Ⅱ.Ⅲ.类型起别名——typedef关键字typedef用于为系统固有的或程序员自定义的数据类型定义的一个别名，如：Ⅰtypedef struct student{ char number[5]; char name[11]; int ...
2021-03-11 23:54:35
261
原创 高精度斐波那契
1.为何会有高精度斐波那契一说？ 1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 21 9 3410 5511 8912 14413 23314 37715 61016 98717 159718 258419 418120 676521 1094622 1771123 2865724 4636825 7502526 12139327 19641828 31781129 51422930 83204031 134626932 217
2021-02-23 09:54:38
1957
原创 写了也不看之第一学期c语言总结
一.循环，递归，遍历，迭代1.循环一组被重复执行的语句称之为循环体，能否继续重复，决定循环的终止条件。循环结构是在一定条件下反复执行某段程序的流程结构，被反复执行的程序被称为循环体。c语言中的循环语句第一种for( ; ; ){}第二种while(){}第三种do{}while();2.递归——重复调用自己程序调用自身的编程技巧称为递归递归的缺点：递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为
2020-12-18 19:15:46
599
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人