- 博客(90)
- 收藏
- 关注
RSS订阅原创 蓝桥杯 超级胶水（动态规划）
小明有n颗石子，按顺序摆成一排。他准备用胶水将这些石子粘在一起。每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。测试样例输入33 4 5输出..
2020-10-13 19:55:11
745
1
原创 蓝桥杯 REPEAT程序（DFS）
问题描述附件 prog.txt 中是一个用某种语言写的程序。其中 REPEAT k 表示一个次数为 k 的循环。循环控制的范围由缩进表达，从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。例如如下片段：该片段中从 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的循环两次中。REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循环中。A = A + 5 实际总共的循环次数是 2 × 5 × 6 = 60 次。
2020-10-02 19:08:35
525
原创 关于jQuery源码中一段正则表达式的问题
<script> var text1="#div"; var text2="<div>3"; var pattern=/^(\s*(<[\w\W]+>)[^>]*|#([\w-]+))$/; var matches1=pattern.exec(text1); var matches2=pattern.exec(text2);...
2020-09-17 00:52:07
268
原创 C++虚析构函数
为防止内存泄露，定义一个基类的指针p，在delete p时，如果基类的析构函数是虚函数，这时会看指针p所指向的对象是什么类型的，如调用构造函数时，先调用基类构造函数，再调用派生类构造函数，调用析构函数时，先调用派生类再调用基类析构函数。这种需要等到编译器运行时才能确定对象的类型叫动态联编，若基类中没有声明虚析构函数，则将根据p的指针类型调用，而不是p所指向的对象...
2020-07-16 10:02:57
126
1
原创 C++复制构造函数
什么是复制构造函数？复制构造函数形如：假设类为StringBad，其相应的构造函数为StringBad(const StringBad &);当使用一个对象初始化另一个对象的时候，编译器将自动生成上述函数每当程序生成对象副本时，编译器都将使用复制构造函数如一个函数为call（StringBad sb）sb为其副本，创建sb时就调用了该函数，这也就会造成如果某个类型中有字符串时候，其副本因为浅拷贝的问题会指向与原类相同的地址，造成析构时，重复释放该地址内存。假设m.
2020-07-12 21:54:43
68
原创 javascript中基本类型和引用类型
区别： 基本类型创建在栈中，引用类型的值同时保存在栈和堆中基本类型包括 Underfined ,Null, Boolean,Number,String其中Boolean,Number,String还可以是特殊的引用类型用new操作符创建的引用类型的实例在执行流离开当前作用域前一直保存在内存中，而自动创建的基本包装类型的对象，则只存在于一行代码的执行瞬间基本包装类型的对象如：var s1="some text";var s2=s1.substring(2);本来s1不用调用s.
2020-07-10 23:38:04
92
原创 前端杂记
标签<a>中的target属性 ：_blank 浏览器总在一个新打开、未命名的窗口中载入目标地址_self 这是默认目标，在当前窗口中加载目标地址_parent 在父框架集中打开被链接文档_top 在整个窗口中打开被链接文档父目录表示方法 ../根目录表示方法 /...
2020-07-04 15:04:32
79
原创 LA 2797 怪物陷阱（平面直线PSLG）
题目：https://vjudge.net/problem/UVALive-2797把直线的每两个端点点处理一遍，因为只有贴着端点才能过。若遇到直线端点相交情况，把每条线段稍微延长一点，通过判断是否相交即可判断是否可以通过#include<bits/stdc++.h>using namespace std;struct Point{ double x,y; Point(double x=0,double y=0) :x(x),y(y){}}; int n;typed
2020-05-25 01:03:01
134
原创 LA 3890 离海最远的点（半平面交）
题目：https://vjudge.net/problem/UVALive-3890二分法，通过收缩凸边型，直到半平面交为空集。#include<bits/stdc++.h>using namespace std;#include<bits/stdc++.h>using namespace std;struct Point{ double x,y; Point(double x=0,double y=0) :x(x),y(y){}};typedef P
2020-05-22 21:12:25
113
原创 UVA 10652 Board Wrapping（凸包）
#include<bits/stdc++.h>using namespace std;struct Point{ double x,y; Point(double x=0,double y=0) :x(x),y(y){}};typedef Point Vector;Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator -(Vector A,Vector B){.
2020-05-21 15:05:50
90
原创 UVA 12304 2D Geometry 110 in 1！（与圆有关二维几何问题）
关于InscribedCircle：O是ABC内心的充要条件是：aOA+bOB+cOC=0 （均表示向量）设ABC的坐标为：A(x1,y1),B(x2,y2),C(x3,y3) BC=a,CA=b,AB=c内心为O(x,y)则有aOA+bOB+cOC=0（三个向量）MA=(x1-x,y1-y)MB=(x2-x,y2-y)MC=(x3-x,y3-y)则：a(x1-x)+b(x2-x)+c(x3-x)=0,a(y1-y)+b(y2-y)+c(y3-y)=0∴x=(ax1+bx2+cx3)...
2020-05-21 00:14:47
137
原创 UVA 11178 Morley定理(几何入门）
#include<bits/stdc++.h>using namespace std;struct Point{ double x,y; Point(double x=0,double y=0) :x(x),y(y){}};typedef Point Vector;Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator -(Vector A,Vector B){.
2020-05-15 23:23:04
111
原创 UVA 11107 生命的形式（后缀数组+LCP）
把所有输入的字符串拼起来，二分答案，每次判断是否有一个长度为p的串在超过一半的串中连续出现，判断方法是扫描height数组，因为height数组中，相同串长度都聚集在一起。#include<bits/stdc++.h>using namespace std;const int maxn=100005;char s[maxn];int sa[maxn],t[maxn]...
2020-05-07 21:49:16
113
原创 蓝桥校内模拟赛摆动数列（动态规划）
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。 小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。输入格式 输入一行包含两个整数 m，n。输出格式 输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。样例输入3 4...
2020-04-19 00:21:10
268
原创 LA 3704 Cellular Automaton(矩阵快速幂）
题目https://vjudge.net/problem/UVALive-3704构造出来矩阵后，发现这是一个循环矩阵，从第二行开始每一行都是上一行向右，所以只需要保留第一行数据，使时间复杂度边为（O^2log k）#include<bits/stdc++.h>using namespace std;typedef long long ll;const int max...
2020-04-13 21:19:34
100
原创 UVA 10870 Recurrences （矩阵快速幂）
由于n太大，不能直接递推，需要用矩阵快速幂来解决，时间复杂度为O(d^3logn)举例，d=5的矩阵关系式为：|a1 a2 a3 a4 a5| | f[n-1] | | f[n]| |1 | | ...
2020-04-12 23:40:54
110
原创 蓝桥杯 油漆面积（线段树区间修改+离散+扫描线）
10.标题：油漆面积X星球的一批考古机器人正在一片废墟上考古。该区域的地面坚硬如石、平整如镜。管理人员为方便，建立了标准的直角坐标系。每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。矩形的表示格式为(x1,y1,x2,y2)，代表矩形的两个对角点坐标。为了醒目，总部要求对所有机器人选中的矩形区域...
2020-03-17 21:40:23
304
原创 2017 蓝桥杯 迷宫（dfs）
X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：L表示走到左边的房间，R表示走到右边的房间，U表示走到上坡方向的房间，D表示走到下坡方向的房间。X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！开始的时候，直升机把100名玩家放入一个个小房间...
2020-03-15 14:48:58
210
原创 UVA 10214 Trees in a Wood(欧拉函数)
枚举每列，只要找到g(x,y)=1中的所有y即可。因为1~x中，与x互质的假如有i个，那么[1+x,2x]中也有i个，因为相当于那互质的i个每个加了x，公因数还是11≤y≤x 有phi(x)个x+1≤y≤x 也有phi(x)个2x+1≤y≤x 也有phi（x）个.....kx+1≤y≤b ....直接统计#include<bits...
2020-03-14 22:42:54
124
原创 UVA 11440 Help Mr.Tomisu(欧拉公式）
题目：https://vjudge.net/problem/UVA-11440所有素因子都大于M等价于和M！互素，因为和M！互素的数中不包含M中的任何因子。在kn中与n互质的个数如何求：在1~n中与n互质的个数为phi[n],再[n+1,2n]....中的个数与1~n中的个数一样。最后用递推先预处理一遍Phi根据欧拉函数若n是素数 phi(n)=phi(n-1)*(n-1)...
2020-03-12 11:28:54
86
原创 蓝桥杯 2019 糖果（01背包问题的状态压缩）
采用了滚动数组的方法。状态转移：把第i，i+1，i+2的糖果装到 j的背包后，现有背包的糖果为j|a[i]。#include<bits/stdc++.h>using namespace std;int n,m,k,temp;int a[25],d[1<<21];const int inf=0x3f3f3f3f;int main(){ int ...
2020-03-10 17:19:54
280
原创 UVA 10859 放置街灯（树形DP）
把无向图转化成有根树。两个优化的量v1，v2，把二者组合成一个量Mv1+v2，让M是一个比“v2的最大理论值和v2的最小理论值之差”还要大的数，就可以先决定v1，再决定v2。取M=2000，ans表示该节点放灯的情况，sum表示该节点不放灯的情况#include<bits/stdc++.h>using namespace std;vector<int>...
2020-03-08 22:01:20
195
原创 UVA 10891 Sum游戏 (DP)
题目：https://vjudge.net/problem/UVA-10891第一种方法：记忆化搜索状态有O（n^2）,每个状态有O(n)个转移，所以时间复杂度为O（n^3）#include<bits/stdc++.h>#include<algorithm> using namespace std;const int maxn=100+10;int S...
2020-03-07 19:47:18
99
原创 UVA 10635 王子和公主（LCS转LIS）
题目：https://vjudge.net/problem/UVA-10635传统LCS问题时间复杂度为O（p*q），但是此题p*q高达250*250=62500，有些太慢所以把问题转化为LIS，时间复杂度变为（n*logn）先把A串的每个字符的位置记录一下，然后把B串的元素转换成A串的位置，相当于求LIS。#include<bits/stdc++.h>usin...
2020-03-05 21:34:18
128
原创 LA 3882 约瑟夫环变形(递推）
假设有n个人，每次从0数，删除第k个人。此时编号k 0k+1 1k+2 2.....倒着推会发现每一轮的胜利者编号都少了个K，然后利用递推复原回去。f[n]=(f[n-1]+k)%n直到最后一轮，最后的胜利者编号为0f[1]=0,又由于本题是从编号为m，所以找到距m为k的位置即（m-k）,所以答案为(f[n]+1+m-k)由于m-k可...
2020-03-05 09:51:23
98
原创 UVA 11922 排列变换（Splay）
给节点增加一个flip标记，用来表示以本节点为根的子树有没有旋转过。合并过程中的细节：先把left中的最大元素伸展到根节点，此时的最大元素一定无右子树。分裂时，就直接把第k小元素伸展到根，然后断开根与右子树的链接关系。#include<cstdio>#include<algorithm>#include<vector>using names...
2020-03-03 00:15:17
89
原创 LA 5031 图询问（Treap）
熟悉了Treap树的常用操作.#include<cstdlib>struct Node{ Node *ch[2]; int r; //随机优先值 int v; //值 int s; //结点总数 Node(int v):v(v){ch[0]=ch[1]=NULL; r=rand(); s=1;} bo...
2020-03-01 22:54:30
96
原创 LA 3942 背单词 (trie)
递推加字典树,令d(i)为从字符i开始的字符串，d(i)=sum{d(i+len(x)}#include<bits/stdc++.h>using namespace std;const int maxn=300000+10;const int maxs=100+10;const int maxnode=4000*105;const int signa_size=26...
2020-02-10 15:30:11
92
原创 UVA 11992 快速矩阵操作（线段树区间修改）
对于set操作要清除结点上的addv标记maintain函数中，先考虑setv再考虑addvquery函数中，综合考虑setv和addv.#include<bits/stdc++.h>const int maxn=4e5+10;const int inf=1000000000;using namespace std;int r,c,m,qr,ql;int _su...
2020-02-09 21:15:55
134
原创 LA 3938 动态的最大连续和（线段树）
第一次学习线段树#include<bits/stdc++.h>#define lson l,m,i<<1#define rson m+1,r,i<<1|1typedef long long ll;using namespace std;const ll inf=1223372036854775807;struct node{ ll v,l...
2020-01-28 23:56:16
121
原创 UVA 10561 Treblecross游戏（Nim博弈）
题目：https://vjudge.net/problem/UVA-10561由于禁区内谁放谁输，所以禁区之外的一段一段分成了很多子游戏。子游戏g(0)=0,g(1)=g(2)=g(3)=1，超过3以后就可以分成子游戏了，比如连续4个格子的，若在最左边放一个。那么该格子可以影响最左边的3个格子，只有最右边的一个格子不受影响，所以g(4)=mex{g(x-3),g(x-4)}=2...依...
2020-01-21 20:54:43
1400
原创 中国剩余定理
假若有方程组x=a[i](mod mi) i=0,1,2,... 求出x另M为所有mi的乘积，wi=M/mi，此时，wi是除了mi之外所有m0..mi-1,..mi+1,..mn的乘积，也就是他们的公倍数。另gcd(wi,mi)=1,求出ei=wi*pi.此时的ei是除mi余1的数，所以最后要乘a[i].把所有这样的mi加起来，就可以得到解。如：一个数除3余2，除5余3...
2020-01-16 10:37:38
131
原创 乘法逆(扩展欧几里得、欧拉定理）
用扩展欧几里得求解的乘法逆原理：ax=1 mod (n)ax+ny=1如7=1mod(15)7*13-(15*6)=1.13为7的逆元。求解出的x就是a的逆元。实现：#include<bits/stdc++.h>using namespace std;typedef long long ll;void gcd(int a,int b,int &...
2020-01-16 09:59:36
934
原创 蓝桥杯 2019 RSA加密 （快速幂 快速乘 欧拉定理 乘法逆）
RSA 是一种经典的加密算法。它的基本加密过程如下。首先生成两个质数 p,q 令 n=p⋅q 设 d 与(p-1) * (q-1) 互质，则可 找到 e 使得 d⋅e 除 (p−1)⋅(q−1) 的余数为 1.n,d,e 组成了私钥，n,d 组成了公钥。当使用公钥加密一个整数 X 时（小于 n ），计算 C=X^d mod n ,则 C 是加 密后的密文.当收到密文 C 时...
2020-01-14 21:59:58
2058
2
原创 LA 3905 流星（扫描法）
题目：https://vjudge.net/problem/UVALive-3905把进入的流星看成一个个时间的事件，当扫描线和最多的开区间相交时，维护答案。应注意细节，事件的左端和事件的右端重合时，应先处理事件右端。#include<bits/stdc++.h>#include<algorithm>using namespace std;const i...
2020-01-10 14:11:11
128
原创 UVA 11549 计算器谜题（floyd判圈）
题目：https://vjudge.net/problem/UVA-11549可以想成两个小孩，一个小孩去追另一个小孩，这个小孩是那个小孩的几倍速度都没有关系，若跑着跑着突然出现了一个循环圈，那么快的小孩一定可以套慢的小孩的圈，直到某一刻追上。此方法可以省去stl中的set，使得空间开销变小。#include<bits/stdc++.h>using namespace ...
2020-01-09 23:13:03
179
1
原创 UVA 11462 年龄排序（桶排序）
考虑到该题对内存要求限制比较严格，不能把所有数据保存，所以考虑用桶排。#include<cstring>#include<cstdio>int c[101],n;int main(){ while(scanf("%d",&n) && n){ int a; memset(c,0,sizeof(c)); for(int i...
2020-01-09 20:15:38
124
原创 LA 4329 乒乓比赛（树状数组+计数原理）
#include<bits/stdc++.h>#define maxn 100005using namespace std;int num[maxn],n,a[maxn],c[maxn],d[maxn];int lowbit(int x){ return x&(-x);}int sum(int x){ int ret=0; while(x>0){...
2020-01-08 22:06:20
116
原创 UVA 10795 新汉诺塔问题（递归）
题目：https://vjudge.net/problem/UVA-10795新汉诺塔问题往旧汉诺塔问题上转换，所以先来看旧汉诺塔问题。旧汉诺塔：汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在...
2019-12-30 19:51:45
286
原创 LA 3401 彩色的立方体（暴力+打表）
题目：https://vjudge.net/problem/UVALive-3401学习了如何用机器人中的术语“姿态”，来解决这个问题。一个正方体6个面，当为每个面标上号的时候，这个正方体就有了24种姿态，即每个面作为顶面，每个面作为顶面的时候有4种不同的情况。这样颜色在不同姿态上的正方体的情况可以看做是互不相同的了。这道题的实现比较复杂，而且用到了很多技巧。此外，一定要搞...
2019-12-29 20:35:55
291
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人