- 博客(83)
- 收藏
- 关注
RSS订阅
原创 软光栅算法和分型几何的实现
第一部分软光栅(1)绘制线段1 思路如上图所示，当画一条线时，首先计算增量dx，dy。如果dy<dx，则x方向增长快，每次必加1，而y看判别式。取dx所在线（x轴平行线）和画的线所成角的角平分线，若新的y落在该平分线上面，则y递增，否则y不变。而角平分线方程为：dy=12dxdy=\frac{1}{2}dxdy=21dx，即平分斜率。即dy−12dx>0⟹2dy−dx>0dy-\frac{1}{2}dx>0 \Longrightarrow 2dy-dx>0dy−21
2020-11-15 21:41:43
368
2
原创 学习笔记——KMP字符串匹配算法
简介KMP算法是一种字符串匹配算法，它利用了模式串（被匹配串）自身的相关信息来减少匹配次数。本文假设文本串（待匹配串）为T，模式串（被匹配串）为P。而T，P的长度分别为TLen，PLen。记Ti为T的前i个字符构成的子串，T-i为T后i个字符构成的子串，P同理。求辅助数组在实现这个算法前，我们需要先求一个特殊的数组，暂且记为Pre[PLen+1]。这个数组的含义为Pre[i]=max(j),...
2019-05-04 01:13:42
381
原创 学习笔记——并查集（下）带权并查集
简介带权并查集是一种带有某种信息的并查集，即每个子节点都储存其自身与跟节点的关系，如路径长度等。定义一个带权并查集数组：struct{ int p;//父节点编号 int data;//与根节点的关系}f[MAX];这里关键的问题时带权并查集在合并和路径压缩时怎么做到状态更新呢？合并首先合并，除了普通的合并，只要加一条信息更新就行了（更新最终根节点）void merge(int ...
2019-02-21 21:36:30
748
原创 学习笔记——并查集（上）模板和种类并查集
简介并查集是用于处理点集之间关系的一种方法，支持合并和查询两种操作，即将两个集合合并和查询两个点是否位于同一集合内，是一种树形数据结构，一般采用数组实现。首先定义一个数组ppp，对于点iii，p[i]p[i]p[i]存储着i的父节点的下标，通过递归查找找到其根节点。而合并点i，j时，首先找到i，j的父节点pi，pj，然后让p[pi]=pj或p[pj]=pi即可，也就是让i，j所在的集合的根节点...
2019-02-20 02:51:25
781
原创 学习笔记——最小生成树
简介规定点的数量为V，边为E生成树是指在连通图中包含所有节点的一棵树，即该树包含所有节点的同时每个节点的入度出度均为1。而一幅图的生成树有很多种，其中最小生成树指的是带权图的生成树中边权和最小的树。并且若图中的边权都不相同，则最小生成树唯一（每两个节点都只有一条边相连，每次选最小的），反之，就不一定了。最小生成树一般有两个通用的算法，一个是Prim算法，一个是Kruskal算法。Prime...
2019-02-19 00:51:50
895
原创 Linux添加Qt库的方法
阿里云服务器上添加Qt库的方法（会自动根据当前已安装的版本下载对应版本）：sudo apt-get install libqt5websockets5-dev会安装libqt5websockets5.so
2020-05-15 10:08:25
1182
原创 Numbers（模拟）
ZOJ - 3987DreamGrid has a nonnegative integer n. He would like to divide n into m nonnegative integers a1,a2,…,ama_1, a_2, \dots, a_ma1,a2,…,am and minimizes their bitwise or (i.e. n=a1+a2+⋯+amn...
2020-03-05 01:16:41
258
原创 Safest Buildings（思维模拟）
ZOJ - 3993PUBG is a multiplayer online battle royale video game. In the game, up to one hundred players parachute onto an island and scavenge for weapons and equipment to kill others while avoiding ...
2020-03-05 00:54:08
330
原创 Crusaders Quest（模拟）
ZOJ - 3983Crusaders Quest is an interesting mobile game. A mysterious witch has brought great darkness to the game world, and the only hope for your kingdom is to save the Goddesses so that they can...
2020-03-05 00:49:10
407
原创 String of CCPC（模拟）
ZOJ - 3985BaoBao has just found a string (s) of length (n) consisting of ‘C’ and ‘P’ in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substring (s_is_{i+1}s_{...
2020-03-05 00:39:27
283
原创 A Research Problem（欧拉函数，DFS）
UVA10837#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <cstdio>#include <cstring>#include <queue>#include <strin...
2020-03-04 09:10:24
236
原创 Yet Another Multiple Problem（同余方程+BFS）
SP12810There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”.I...
2020-03-03 17:50:19
195
原创 Sum of Consecutive Prime Numbers（前缀和，素数筛）
UVA1210筛出素数，处理成前缀和，O(n2)O(n^2)O(n2)枚举每一种和的可能。#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <cstdio>#include <cstring>usi...
2020-03-03 11:48:11
283
原创 Almost Prime Numbers（素数筛）
UVA10539枚举2到high\sqrt{high}high，分别看i2,i3⋯ini^2,i^3\cdots i^ni2,i3⋯in，是否在[left,right][left,right][left,right]中，统计多少个这样的次方方在范围中即可。#include <iostream>#include <algorithm>#include <cm...
2020-03-03 11:30:35
174
原创 Perfect Pth Powers（唯一分解定理）
UVA10622由唯一分解定理，将nnn分解后求每个素数项对应的指数的最小公约数即可。虽然nnn在int范围内，但仍要long long，因为int的负数的绝对值比整数大1。#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include ...
2020-03-03 10:38:42
1531
原创 Divisors（约数的数目）
UVA294题目要求指定范围内约数数目最多的数以及对应的约数数量。根据唯一分解定理，对于任意正整数2≤N2\leq N2≤N，有：N=∑i=1npiai，p为素数N=\sum\limits_{i=1}^{n}p_i^{a_i}，p为素数N=i=1∑npiai，p为素数那么根据乘法原理，约数的总数目为：f(N)=∏i=1n(1+ai)f(N)=\prod\limits_{i=1}^...
2020-03-03 08:57:59
576
原创 Semi-prime H-numbers
UVA11105线性筛即可。#include <iostream>#include <algorithm>#include <cmath>#include <vector>using namespace std;const int MAXN = 1000001;bool IsNotHPrimer[MAXN + 1];bool...
2020-03-02 23:36:01
164
原创 Trees in a Wood.
UVA10214思路：对于坐标为(x,y)(x,y)(x,y)的树，需要满足gcd(x,y)=1gcd(x,y)=1gcd(x,y)=1这棵树才不会被阻挡。（同一条直线上的树从第二颗起会被遮挡）。根据对称性，设第一象限的答案为KKK，则四个象限的答案为4∗K4*K4∗K，再加上，每个坐标轴上能看见一棵树，答案为4∗K+44*K+44∗K+4。由于列比较小，考虑枚举列，对于列x，1≤y≤x1...
2020-03-02 22:27:15
158
原创 Send a Table（欧拉函数埃式筛）
UVA10375显然，题目要求有多少二元组(x,y)(x,y)(x,y)满足1≤x,y≤n且x,y互素1\leq x,y\leq n且x,y互素1≤x,y≤n且x,y互素。根据欧拉函数ϕ\phiϕ的定义，ϕ(n)\phi (n)ϕ(n)为小于n且与n互素的整数个数。定义f(n)=∑i=2nϕ(i)f(n)=\sum\limits_{i=2}^{n}\phi(i)f(n)=i=2∑nϕ(i...
2020-03-02 21:33:54
213
原创 Choose and divide
Voj#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <string.h>using namespace std;const int MAXN = 10000;//素数表vector<int>...
2020-03-02 20:25:20
110
原创 Minimum Sum LCM
UVA10791思路：由N=lcm(a,b)=abgcd(a,b)N=lcm(a,b)=\frac{ab}{gcd(a,b)}N=lcm(a,b)=gcd(a,b)ab可知，当且仅当gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1时，a+ba+ba+b的值最小。因为若gcd(a,b)>1gcd(a,b)>1gcd(a,b)>1，则有:lcm(a,b)=abg...
2020-03-02 19:38:29
219
原创 Pairs of integers
HDOJ 1554You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The firs...
2020-03-02 17:40:43
343
原创 Nature Reserve（三分）
CodeForces - 1059D题目大意：平面上有n个点，现在需要找这么一个圆，它与y=0相切，且这n个点都在圆上或圆内，求这个圆的最小半径Input输入n，1 <= n <= 10^5接下来n行，每行表示一个点的坐标，依次是x,y，坐标都是整数且绝对值不超过107，同时不存在y=0的点Output这样的圆如果不存在，输出-1，存在则输出其最小半径，误差小于10-6视为正确...
2020-03-02 12:51:12
288
原创 Forgery
CodeForces - 1059B time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputStudent Andrey has been skipping physical education lessons for the whole ter...
2020-03-02 10:15:14
179
转载 Tournament(转载）
ZOJ - 4063DreamGrid, the king of Gridland, is making a knight tournament. There are nnn knights, numbered from 1 to nnn, participating in the tournament. The rules of the tournament are listed as fo...
2020-03-02 10:02:58
323
原创 Plants vs. Zombies
ZOJ - 4062BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao’s zombies.(Image from pixiv. ID: 21790160; Artist: s...
2020-03-02 09:55:01
826
原创 Books
ZOJ - 4067DreamGrid went to the bookshop yesterday. There are nnn books in the bookshop in total. Because DreamGrid is very rich, he bought the books according to the strategy below:Check the nnn b...
2020-03-02 09:36:20
182
原创 除法表达式
Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByteTotal Submit: 279 Accepted: 68Description给出如下除法表达式E：X1/X2/X3/…/Xk其中Xi是正整数并且Xi<=2 000 000 000(1<=i<=k,k<=1...
2020-03-02 09:20:06
640
原创 Flippy Sequence
ZOJDreamGrid has just found two binary sequences s1,s2,…,sns_1, s_2, \dots, s_ns1,s2,…,sn and t1,t2,…,tnt_1, t_2, \dots, t_nt1,t2,…,tn (si,ti∈{0,1}s_i, t_i \in \{0, 1\}si,ti∈{0,1} for all 1≤...
2020-03-01 13:18:32
308
1
原创 git的基本使用方法（Qt）
首先下载一个git，然后配置好。在Qt中创建一个项目来到项目所在的文件夹，右键/git bash here（Windows系统打开git的方法）在git bash中，输入git init，创建一个本地仓库。执行git remote add origin <仓库链接地址>。这样，origin就是仓库地址了。一般是https或ssh。执行git branch 分支名，在本地仓库...
2020-02-08 23:00:31
1143
原创 基于QTest的TDD开发模式应用实例。
TDD（Test Driven Development），即测试驱动开发。是指在具体开发之前先编写测试样例。这样做的好处有：一开始就从被使用的角度考虑，能避免开发半天发现方向错误甚至开发用不到的功能。先编写出测试，方便接口各方达成共识（交叉评审），并在开发中相互协同测试，避免各方开发方向出现偏差。基于QTest开发的测试代码能在开发后一键测试，并且在代码进行修改时（功能变更或出现联调Bug...
2020-02-08 22:32:24
535
原创 数的表达式解析，正则定义以及DFA
文章目录目标构造正则定义基本正则定义数的正则定义正则定义转NFA（非确定的有穷自动机）无符号浮点数(unsigned float)(Spaces)(ID)(Equal)(UnsignedFloat)IDunsigned floatEqualUnsignedFloatDigitsFractionExponentSigned有符号浮点数(float)(Spaces)(ID)(Equal)(Float)...
2020-02-08 17:43:32
616
原创 整数以及浮点数的正则定义
文章目录定义无符号整数(UnsignedInt)(UnsignedInt)(UnsignedInt)有符号整数(SignedInt)(SignedInt)(SignedInt)无符号浮点数(UnsignedFloat)(UnsignedFloat)(UnsignedFloat)有符号浮点数(SignedFloat)(SignedFloat)(SignedFloat)定义Digit=0∣1∣2∣...
2020-02-06 00:36:55
1189
原创 Coding Wiki文档的应用
基本操作首先，可以新建一个页面选中新建的页面，点击右上角的编辑。右边有个模板，可以选择项目模板/Wiki模板，然后确定。然后最可以往下写markdown格式的文档了。markdown语法编辑界面右边有个问好图标HashTag只要打一个#号就会出现上图的HashTag，可以直接关联到其他文档，上传到文件网盘的文件以及需求等等。历史对比点击图中的共xx个版本可以看到和历...
2020-02-05 00:36:55
1599
原创 coding关联QT项目（Git）
下载git设置环境变量。在coding上创建分支Branch绑定QtCreator点击文件/新建文件或项目/Import Project/Git CloneRepository：https://e.coding.net/luoxiao23333/ChrtScript.git（仓库链接）Branch：Branch，即当前要同步的分支名Path：自己本地仓库要放在电脑哪里Dictor...
2020-02-04 21:41:43
323
原创 自己的个人博客（hexo+coding+gittalk）
自己用hexo框架+coding搭建了一个个人博客，所有文章在两个博客都会同步上传。不得不说，butterfly主题真的好看，吹爆！博客链接chrome食用更佳用的coding的临时域名，所以没有https，有空了再申请一个域名弄到个人上服务器。吹爆butterfly！给作者打赏去了。...
2020-02-02 10:37:44
467
原创 K-th occurrence （后缀自动机上合并权值线段树+树上倍增）
AC代码：#include<iostream>#include<cstring>#include<vector>using namespace std;const int MAXN = 1e5 + 5;int N, L, R, K, Q;char S[MAXN];int u[MAXN];//1...rint EndPosToTree[2 *...
2020-01-30 18:17:09
309
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人