- 博客(534)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 DFS序详解
树通常有多种类型，但其终归是非线性结构，操作起来有时总是那么费时。例如：POJ 3321 给你一棵树，树上每个节点都有1个苹果，然后你对一个节点操作，如果有苹果就拿走，没苹果就放上，然后询问你以x为根的子树上共有多少个苹果。 每次更新都要遍历一遍，查询也要遍历一遍，时间复杂度很高。如果能转化成线性结构就可以了，就可以用线段树或者树状数组等其他方法对树高效更新和查询。DFS序就是将树
2018-02-02 10:50:37
2101
原创 浅谈线段树+模板
推荐两篇线段树博文： 线段树之一； 线段树之二；小结： 线段树是一种二叉树，也可以说成是区间树，操作有：建树build，更新updata(单点+区间)，查询query(单点+区间)。单点操作时把区间不断二分，用root指向数组下标；区间更新操作时，标记lazy，先对子树的根节点做更新，当用到的这个子树的时候，再把标记下推，同时递归时向上统计，更新区间；区间查询时，会有遍历的一个操作遇到l...
2018-01-31 15:40:23
422
原创 leetcode 1882. 使用服务器处理任务【优先队列】
原题链接给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n 和 m 。servers[i] 是第 i 台服务器的 权重 ，而 tasks[j] 是处理第 j 项任务 所需要的时间（单位：秒）。你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台
2021-06-06 16:45:46
515
原创 Berlekamp-Massey算法实现
BM算法的C++实现：#include <bits/stdc++.h>using namespace std;// a数组存储序列，MAXN定义为a的长度；更改这两处，即可将程序运行；const int MAXN = 20;int a[MAXN] = {1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0};int d[MAXN + 1], L[MAXN + 1];vector<int> f[MAXN
2020-11-29 09:58:37
687
原创 centos 修改/etc/passwd的root信息出错 && 重置root密码
1，进入虚拟机时按上下键（如图中下方提示），打断3秒进入系统的步骤；2，按下e，进入编辑模式。按住下键，将光标停在图中黄色位置处（不移动时，可能看不全字母），将黄色框中的信息写入，注意空格和字母。然后，按下ctrl+x保存并进入下一步；3，输入命令：mount -o remount, rw /4，（若仅为了重置root密码，跳过此步骤，直接进入第五步）将误修改的root信息，修改过来（我是误在root前添加了数字1），这里只建议修改root的名称；输入命令：vim /etc/passwd5
2020-07-06 22:08:25
1856
原创 虚拟机远程连接宿主机数据库
一、宿主机：1，关闭防火墙：控制面板 -> 系统和安全 -> windows defender 防火墙 -> 启用或关闭防火墙2，查看本机的VMware Network Adapter VMnet1 的ipv4：3，宿主机启动mysql服务(一直保持启动态)，登录mysql数据库，查看mysql使用端口号。输入：show global variables like ...
2020-04-27 16:16:12
2347
原创 MySQL更改Auto_Increment自增值
创建表时设置了ID字段是Auto_Increment，因种种原因导致Auto_Increment值错误，现需要对其进行更改。 1，打开MySQL控制台，通过常用命令选中需要更改Auto_Increment的那张表，输入命令：ALTER TABLE <table_name> auto_increment=<num>;table_name：需要更改Auto_I...
2020-04-13 19:53:16
2261
原创 Cesium-经纬度转换笛卡尔坐标系
CZML(百度查阅)字段里的position里坐标系仅支持cartesian（笛卡尔坐标系），一般的地理位置经纬度较为普遍。Cesium提供了转换接口，并且CZML里position字段支持填入常量（详情翻阅API）。var position = Cesium.Cartesian3.fromDegrees(116.3912822800,39.9074647400);var czml = [{...
2020-03-25 17:45:48
6931
原创 Cesium-Sandcastle（基本流程）
上一篇博文操作结束，就可以有运行环境，本篇介绍主要是方便之后写代码。学习每一项技术，每次都特别讨厌开始，因为环境+写代码+运行代码流程不熟悉。本篇博文+上一篇就能解决这些问题，我也是刚开始学习，书写不周，欢迎讨论。1，下载cesiumjs（https://cesium.com/cesiumjs/）；2，打开官方沙盒（http://mars3d.cn/forcesium/Apps/Sandcas...
2020-03-24 21:33:50
7877
4
原创 Nodejs环境搭建+cnpm安装使用
Nodejs环境搭建：1，到Nodejs官网（https://nodejs.org/en/download/）下载个对应操作系统的.msi文件。2，按照提示，一直next，正常安装。3，打开cmd/powershell，输入：node -v，若显示版本号则安装成功； 否则失败，找篇博客安装一下，这个不麻烦。nodejs安装成功后，不建议使用npm，下面介绍cnpm的安装：cnpm...
2020-03-24 20:08:44
860
原创 学成在线教育平台
HTML：<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>学成在线&...
2020-03-22 17:50:31
1009
原创 指针学习
一 概念前言：指针变量就是变量，指针就是地址。首先考虑四个问题：指针变量的类型，指针所指向的类型，指针的值或是指针所指的地址，指针本身所占据的内存区。Int *p；1， 指针类型： Int *p；//指针p的类型即为 int *2， 指针所指向的类型： Int *p；//指针p指向的类型为int，也就是指针指向的内存区的类型3， 指针的值（= 指针所指向的内存地址）：指针指向的变量的...
2020-01-10 17:05:06
119
原创 win10下安装虚拟机，出现错误“此主机支持 Intel VT-x，但 Intel VT-x 处于禁用状态”的问题
考研结束了，打开虚拟机玩一玩，更新一下版本，发现不能用了，出现错误“此主机支持 Intel VT-x，但 Intel VT-x 处于禁用状态”的问题。【如下图】Solutions：**一：**进入bios界面（我用的联想，开机时“Fn+F2”同时不断按下），修改Virtual Technology为Enabled。**二：**若已完成上述操作，仍没有解决error，那就可能是硬件的缘故...
2019-12-30 16:26:25
1704
2
原创 JAVA大数+常用函数
推荐：java中的BigIntegertest 1题目描述：输入两个非常大的实数A和B，判断A是否等于B；import java.math.BigDecimal;import java.util.Scanner;public class Main { public static void main(String[] args) { BigDecimal a, b...
2018-11-07 12:14:14
251
原创 Educational Codeforces Round 53 (Rated for Div. 2)
C. Vasya and Robot 【二分】暴力左端点，二分右端点。在[L,R]区间内任意填方向，根据区间外的方向值和终点(x,y)计算出此区间需要能否填成。判断式：r - l >= abs(res1) + abs(res2) && (r - l - abs(res1) - abs(res2)) % 2 == 0.#include <bits/stdc++.h&...
2018-11-02 12:02:05
185
1
原创 简单记忆化搜索
以前极少写记忆化，大多都是直接推递推方程，推。不。动。。。所谓记忆化，就是一种优雅的暴力，最近在写数位DP，总感觉好强大的暴力。。。POJ 1579 Function Run Fun分析：按照题意记忆化，每一步都记忆化一下；#include <cstdio>#include <cmath>#include <cstring>#include &l...
2018-10-24 22:35:32
442
原创 P3413 SAC#1 - 萌数【数位DP+回文数】
题目描述只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说，101是萌的，因为101本身就是一个回文数；110是萌的，因为包含回文子串11；但是102不是萌的，1201也不是萌的。现在SOL想知道从l到r的所有整数中有多少个萌数。由于答案可能很大，所以只需要输出答案对1000000007（10^9+7）的余数。输入格式：输入包含仅1行，包含两个整数：l、r。输出格式：输出仅...
2018-10-24 21:16:24
350
原创 P2602 [ZJOI2010]数字计数【数位DP】
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。输入格式：输入文件中仅包含一行两个整数a、b，含义如上所述。输出格式：输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。输入样例#1：1 99输出样例#1：9 20 20 20 20 20 20 20 20 20分析：类似于写的这个题；这个题要除去前导0，其他就是把之...
2018-10-23 10:59:55
363
原创 ZOJ 3962 Seven Segment Display【数位DP*好题】
ZOJ 3962 Seven Segment DisplaySample Input35 89ABCDEF3 FFFFFFFF7 00000000Sample Output208124327HintFor the first test case, the counter will display 5 hexadecimal numbers (89ABCDEF, 89ABCD...
2018-10-22 22:11:46
195
原创 POJ 1160 Post Office【区间DP+四边形不等式优化】
POJ 1160 Post Office题意：给你nnn个点，在这nnn个点中选择mmm个点建立基站，定义节点iii到基站jjj处的花费abs(j−i)abs(j - i)abs(j−i)，让你求解最小花费.分析：我的暴力：预处理区间(L,R)(L,R)(L,R)建立一个基站的最小花费，dp[i][j]:表示前i个点建立j个基站的最小花费dp[i][j]:表示前i个点建立j个基站的最小花费d...
2018-10-19 22:06:09
187
原创 HDU 2438 Turn the corner【三分+公式推导】
记录：我一直把拐角处作为三分点(让车以拐角处旋转)，突然发现这个点并不固定，zz。。。应该让汽车靠着右侧和下侧移动(不考虑现实生活车技)，建立坐标系如下图，三分角度(红色直线与x轴夹角)，求出当y=Xy=Xy=X时的最大fabs(x)fabs(x)fabs(x)，若小于街道yyy即“yes”“yes”“yes”.#include<bits/stdc++.h>using na...
2018-10-18 22:11:11
206
原创 hihocoder #1142 : 三分求极值【三分】
分析：【三分】三分最近距离的(xx,yy)(xx,yy)(xx,yy)中的xx，画图可知，对于P到曲线上任一点(x,y)(x,y)(x,y)，并不是单峰问题。当 −INF&lt;xx&lt;=−b/2a-INF &lt; xx &lt;= -b / 2a−INF<xx<=−b/2a，对于P点到该曲线距离满足三分，同理−b/2a&lt;=xx&...
2018-10-18 19:53:51
168
原创 HDU 3480 Division【区间DP+四边形不等式优化】
题意：将含有n个元素的一个集合分成m个子集，定义一个子集的价值为：最大值与最小值差的平方，求m个子集的最小和.记录：四边形不等式优化：还不是很懂这个。。。目前总结的话，遇到区间DP，先弄一个O(n3)O(n^3)O(n3)，然后如果不可行，就直接放for(intk=s[i][j−1];k&amp;lt;=s[i+1][j];++k)for(int k = s[i][j - 1]; k &amp...
2018-10-17 11:31:55
232
原创 Wannafly挑战赛26
链接：https://www.nowcoder.com/acm/contest/212/A作为「Misaka Network」的中心司令塔的 LastOrder出事了，为了维持 「Misaka Network」的正常工作，需要临时选出一个Sister作为中心司令塔。为了弥补能力上的不足，对于选出的Sister有一些要求。具体来说，平面上有 n 个 Sister，问能否找到一个Sister作为...
2018-10-16 17:00:33
166
原创 P3914 染色计数【树形DP】
题目描述有一颗N个节点的树，节点用1,2,⋯,N编号。你要给它染色，使得相邻节点的颜色不同。有M种颜色，用1,2,⋯,M编号。每个节点可以染M种颜色中的若干种，求不同染色方案的数量除以(10^9 + 7)的余数。输入输出格式输入格式：第1 行，2 个整数N,M。 1≤N≤5000;1≤M≤5000接下来N行，第i行表示节点ii可以染的颜色。第1个整数k，表示可以染的颜色数量。接下来k个...
2018-10-09 21:09:54
599
原创 HDU 5952 Counting Cliques【完全图爆搜】
题意：给你n个点m条边，挑选s个点构成完全图的方案数？分析：根本需要任何优化，直接爆搜。。。(还是需要一点的)建图很经典，G[min(a,b)]pushG[min(a,b)]pushG[min(a,b)]push_back(max(a,b))back(max(a,b))back(max(a,b))，这样方案就不会重复计数；爆搜：对于每一个点出发，询问孩子节点加入，是否同集合内的所有点都有边，...
2018-10-06 10:01:04
163
原创 HDU 5950 Recursive sequence【矩阵快速幂||分块】
题意：f[n]=f[n−1]+2∗f[n−2]+i4f[n] = f[n - 1] + 2*f[n - 2]+i^4f[n]=f[n−1]+2∗f[n−2]+i4，给你f[1],f[2]f[1],f[2]f[1],f[2]，让你求f[n]?f[n]?f[n]?分析：把i4i^4i4拆开得到关于常数的一个递推式，如下图：PS：之后遇到后面带常数或者i的矩阵都可以这么解。。。我的写法：比较...
2018-10-06 09:48:55
346
原创 牛客国庆集训派对Day4
A:把b=n；#include<cstdio>#include<bits/stdc++.h>#include<algorithm>#include<string.h>using namespace std; int main() { double n; scanf("%lf", &n); printf("...
2018-10-05 10:41:01
239
原创 HDU 4347 The Closest M Points【KD树】
题意：给你n个k维的点，再给你一个目标点x，让你查询离x最近的M个点？分析：【KD树模板】#include&lt;cstdio&gt;#include&lt;bits/stdc++.h&gt;#include&lt;algorithm&gt;#include&lt;string.h&gt;using namespace std;const int N = 50000
2018-10-04 11:03:10
179
原创 NAIPC2016 I. Tourists【LCA】
题意：求一棵树上∑i\sum i∑i号节点到它所有因子的路径和;分析：预处理因子，LCA求树上两点距离(logn).#include <cstdio>#include <algorithm>#include <cmath>#include <queue>#include <vector>#include <cstrin...
2018-10-03 09:53:34
310
原创 牛客国庆集训派对Day1
A:看样例过题；#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <vector>using namespace std;typedef long long LL;typedef pair<LL, LL>...
2018-10-03 09:47:35
137
原创 NAIPC 2016 Mountain Scenes【计数DP】
题意：给你n个方块，放置在w*h的矩形内，有多少种不同的方案？分析：dp[i][j]:截至到第i列放置了j个方块的方案数；dp[i + 1][j + k] = dp[i + 1][j + k] + dp[i][j];#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigne...
2018-10-03 09:36:57
196
原创 南京网络赛 B. The writing on the wall【矩形计数】
题意：n*m的一个矩形，其中有k个位置为空，问你该矩形内有多少小矩形？$ 1<=n，k<=1e5, 1<=m <= 100$分析：详解：不怎么容易理解！无空位置时：从上到下先枚举行i，从左到右再枚举列j，对于(i，j)，那么右端紧靠着j列的矩形高度为1,2,3…i 的各有1个，所以ans += i;有空位置时：从上到下先枚举行i，从左到右再枚举列j，对于(i，j)...
2018-10-02 22:15:53
161
原创 POJ 3311 Hie with the Pie【状压DP+floyed】
题意： 将所有外卖送去所有对应地点再回到店铺，求最短路。分析：Floyed预处理任意两点最小距离，然后二维状压(最后的结束位置要考虑，不然回到起点的距离没办法计算)。dp[j+1][(1&amp;lt;&amp;lt;j)+i]=min(dp[j+1][(1&amp;lt;&amp;lt;j)+i],dp[k+1][i]+mp[k+1][j+1])：表示以第j个位置结束的状态i的路径长度dp[...
2018-09-26 20:53:36
128
原创 POJ 1185 炮兵阵地【状压DP+状态预处理】
题目链接题意：P处放大炮H不可放，黑色区域为攻击范围，求大炮不能相互攻击的情况下，安装最多的大炮数.分析：三维状压DP一开始乱写了一通，真不知道写的是什么，竟然过了样例，欺骗了自己？？？看了题解要提前把状态预处理一下，其实也就60个状态满足，然后三维状压，突然灵感来了。仔细一想，二维就够了呀，上去就是写一个二维状压？？？不过样例？？？dp[i][j]=max(dp[i][j],dp[...
2018-09-26 13:22:00
131
原创 南京网络赛 E. AC Challenge【状压DP详解】
题意：n个题目，对于每个题目，在做这个题目之前规定了必须先完成哪些题目，第t秒做的题目i得分是t×ai+bi，每一秒必须且只能做一题，问最终的最大得分是多少？ 分析：状压DP。。。 对于枚举每一种状态，是否可以合理的推到下一种状态呢？也就是对于已经做过的题去推下一道该做的题。 如果当前状态有值(被计算过了)，那么其他没做过的题就可以被当做接下来要做的那一道，就暴力推下一种状态。这样想是完全合...
2018-09-12 11:51:47
209
原创 bzoj 1799: [Ahoi2009]self 同类分布【数位DP*好题】
1799: [Ahoi2009]self 同类分布 Time Limit: 50 Sec Memory Limit: 64 MB Submit: 2152 Solved: 957 [Submit][Status][Discuss] Description 给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。 Input Output Sample Input 10 ...
2018-09-11 16:13:20
239
原创 2018 南京网络赛 J. Sum【离线打表】
J. Sum； 题意：f[x] = {x=a∗b的个数|a,b不能有平方因子x=a∗b的个数|a,b不能有平方因子x = a * b的个数|a,b不能有平方因子}，求：∑ni=1f[i]∑i=1nf[i]\sum_{i=1}^{n} f[i]. 分析： 离线分段打表，然后暴力查询。#pragma GCC optimize ("O3")#pragma GCC optimize ("O2...
2018-09-05 11:15:31
320
原创 2018 南京网络赛 G. Lpl and Energy-saving Lamps【线段树】
G. Lpl and Energy-saving Lamps； 题意：每个月买m个灯，依次从1~n的房间去装灯，每个房间都有需要的灯数kikik_i，当你有灯数大于等于kikik_i时才能装。问你第q个月，装了几个房间，剩了多少盏灯？ 分析： 按照kikik_i排序后，线段树维护区间最小编号(两个tag，房间编号和kikik_i)。 注意：预处理时，房间都装完后，就不在买灯，答案固定了。...
2018-09-05 10:51:47
280
原创 2018 南京网络赛 L. Magical Girl Haze【Dij+分层图】
L. Magical Girl Haze； 题意：一张有向图，求1~n的最短路，你可以使路径中的k条边权值为0； 分析：建一张(k+1)∗n(k+1)∗n(k + 1) * n个点的有向图，k+1层。 每层为原图只是点的编号对应放大，层与层之间的边权值可以为0，最后1->(k + 1) * n这条Dij路径即为答案。#pragma GCC optimize ("O3")#pr...
2018-09-05 09:17:24
240
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人