nhl19961226的博客

原创 学长推荐的博客（一直学习）

【1】https://blog.csdn.net/ACdreamers/article/category/1159392 【2】http://www.cnblogs.com/qscqesze/ 【3】http://www.cnblogs.com/kuangbin/ 【4】https://projecteuler.net/about 【5】http://www.shuizilong.com/...

原创 数学有关的知识点

【球冠的面积】链接：传送门 假定球冠最大开口部分圆的半径为 r ，对应球半径 R 有关系：r = Rc osθ，则有球冠积分表达： 球冠面积微分元 dS = 2πr*Rdθ = 2πR^2*cosθ dθ 积分下限为θ，上限π/2 所以：S = 2πR*R(1 - sinθ) 其中：R(1 - sinθ)即为球冠的自身高度H 所以：S = 2πRH S=∫dS =∫2πr*...

原创 专题的知识点总结与例题

【网络流】1.网络流之isap算法：讲解链接：ISAP算法 2.网络流之全局最小割：全局最小割 3.什么是割：最大流与最小割【连通图】1.Trajan算法：传送门 2.连通图的割点：传送门，以例题来看：Network ，例题题解：传送门【LCA与Trajan】1.入门博客：链接 2.LCA与最近公共祖先：算法讲解博客，相关例题：Closest Common An...

原创 函数的知识点（总结）

1.unique();//这是一个去重函数，去掉相同的元素 sort(a,a+n,cmp);//必须先排序 n=unique(a,a+n)-a;//n为数组a的个数2.reverse();//前后翻转。reverse(a,a+n);//a为数组（或字符），n为长度3.strcpy()与strncpy()的用法博客链接：传送门#include&l...

原创 自己遇到的几种非知识点的错误

1.学会宏定义：#define maxx 5009//否则会超时（最短路时遇到）int u[maxx],v[maxx],w[maxx];int first[maxx],next[maxx];//next有时无法定义，在打网络赛时遇到过，有的oj过不了int dp[maxx],xia[maxx];以后会不断添加，如果有人写过类似的，请留言（借鉴一下），谢谢

原创 指针问题

指针问题请留言！

原创 hdu - 6406 Taotao Picks Apples(离线+离散+技巧)

题目链接：Taotao Picks Apples题目大意：有n个数，m个操作，每个操作x,q,将x位的数字改为q，输出改完数后数组的递增序列有多长（只能从第一个数开始找，并且必须依次找更大的数）。思路：我是用离线的方法，先记录x位置之前的有多少个数，然后再求x之后有多少个数，然后输出就行了，之前的好算，之后的不是太好算。 之后的算法： 先用离散这n个数和更改的数，并且将最大的数离散为最...

原创 初级莫队算法的详解（附加一个例题）

例题链接：D-query题目大意：给你n(1 ≤ n ≤ 30000)个数(1 ≤ ai ≤ 10^6)，q(1 ≤ q ≤ 200000)个询问，每个询问有l,r两个数，问这个区间内有多少个不同的数。Input51 1 2 1 331 52 43 5Output323 最暴力的方法就是，先从【1，5】区间一个一个查询，在从【2，4】区间一个一个查询…… 但是这...

原创 P3389 【模板】高斯消元法（模板，高斯消元法）

题目链接：P3389 【模板】高斯消元法思路：没学线代的可以去学一下，很简单的。 直接看落谷的解析吧，感觉很好了。代码：#include<cstdio>#include<cmath>const double EPS=1E-8;double B[110][110];int n;int main(){ scanf("%d",&n)...

原创 POJ-2728 Desert King 01分数规划 二分/迭代

题目链接：Desert KingDesert King Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 28809 Accepted: 7948 DescriptionDavid the Great has just become the king of a desert country. ...

原创 最小化价格(贪心，排序)

题目链接：最小化价格链接：https://www.nowcoder.com/acm/contest/112/A 来源：牛客网题目描述 现有n组人，m个地点，给出每组人的人数，每个地点可容纳的最大人数和选择的价格 要求一种方式，使得每组人都到一个各不相同的地点，最小化选择的价格 每个队伍的人都要在同一个地方每个地方只能有一个队伍 输入描述: 第一行n,m 第二行n个数，表示每...

原创 D 探 寻 宝 藏（双线程DP）

题目链接：D 探 寻 宝 藏D 探 寻 宝 藏内存限制:64MB 时间限制:1s Special Judge: No题目描述: 传说HMH大沙漠中有一个M*N迷宫，里面藏有许多宝物。某天，Dr.Kong找到了迷宫的地图，他发现迷宫内处处有宝物，最珍贵的宝物就藏在右下角，迷宫的进出口在左上角。当然，迷宫中的通路不是平坦的，到处都是陷阱。Dr.Kong决定让他的机器人卡多去探险。但机...

原创 Cinema in Akiba（线段树求解位置）

题目链接：Cinema in AkibaCinema in Akiba Time Limit: 3 Seconds Memory Limit: 65536 KB Cinema in Akiba (CIA) is a small but very popular cinema in Akihabara. Every night the cinema is full of peopl...

原创 Largest Rectangle in a Histogram（单调栈）

原创 373-时间复杂度（表达式求值）

题目链接：373-时间复杂度在 ACM 里面，计算复杂度是一项非常重要的事情，常见的复杂度格式有三种：O(n) O(lg(n)) O(sqrt(n)) 一个算法往往有多种解法，每种解法的复杂度有上述常见的的复杂度组合成，例如排序的两种算法：快速排序： 时间复杂度为 O(n*lg(n))冒泡排序： 时间复杂度为 O(n*n)现在给定你一个 n ， m 个算法复杂度，请确...

原创 威佐夫博弈

博客讲解链接：威佐夫博弈而 bk= ak + k。然后公式化就得到了奇异局势的状态公式: ak = [ k * (1 + √5) / 2 ] , ([x]表示对x取整，也就是 (int)x ) bk = ak + k 性质1：每个自然数都包含在且只...

原创 Friend Number II（简单思路题）

题目链接：Friend Number IIGiven a positive integer x, let S(x) denotes the sum of all x’s digits. Two integers x and y are friend numbers if S(x)=S(y). Here comes the problem: Given a positive integer x,...

原创 hdu--2089 不要62（数位DP的入门题目）

题目链接：不要62不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 53366 Accepted Submission(s): 20401Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为6...

原创 ZJU---Problem Arrangement(状压DP)

题目链接：Problem ArrangementProblem Arrangement Time Limit: 2 Seconds Memory Limit: 65536 KB The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is ...

原创 Vijos--最小总代价(状压DP)

题目链接：最小总代价描述 n个人在做传递物品的游戏,编号为1-n。游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系； 求当物品经过所有n个人后，整个过程的总代价是多少。格式 输入格式 第一行为n,表示共...

原创 1785 数据流中的算法（思路题，细心点就行了）

题目链接：1785 数据流中的算法51nod近日上线了用户满意度检测工具，使用高级人工智能算法，通过用户访问时间、鼠标轨迹等特征计算用户对于网站的满意程度。现有的统计工具只能统计某一个窗口中，用户的满意程度的均值。夹克老爷想让你为统计工具添加一个新feature，即在统计均值的同时，计算窗口中满意程度的标准差和中位数（均值需要向下取整）。 Input 第一行是整数n与k，代表有n次操作...

原创 Surround the Trees（凸包，好坑啊）

题目链接：传送门There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know ho...

原创 nyist-78 圈水池(建立凸包)

题目链接：传送门78-圈水池内存限制:64MB 时间限制:3s Special Judge: Noaccepted:1 submit:1题目描述: 有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）输入描述: ...

原创 问题 G: 矩阵（二维树状数组）

题目链接：问题 G: 矩阵 输入 输出 样例输入 1 3 4 4 Q 1 1 1 1 Q 1 1 3 2 M 1 1 3 Q 1 1 3 4 样例输出 2 21 55提示 思路： 二维树状数组求解矩阵的区间和，和单点更新。树状数组的讲解：传送门代码：#include <stdio.h>#include <stri...

原创 D. MUH and Cube Walls(好裸的KMP啊)

题目链接：D. MUH and Cube Wallstime limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Polar bears Menshykov and Uslada from the zoo of St. Petersbur...

原创 数学考试---2018年长沙理工大学第十三届程序设计竞赛

题目链接：数学考试链接：https://www.nowcoder.com/acm/contest/96/H 来源：牛客网今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完， 他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间, 即[L,L+1,L+2,….,L+k-1]，[R,R+...

原创 Problem F. A-maze-ing-----“今日头条”杯2018年湖北省赛（网络赛）

“今日头条”杯2018年湖北省赛（网络赛）：所有题目链接可以提交的链接（不知道现在还能进不了，你还要有账号）：传送门Problem F. A-maze-ing题目大意：很坑啊，当初读了半天题，没读懂是什么意思。 给你n个点，m条有向边，问你：其中一条路中包含点最多是多少。思路：先用Trajan缩点，然后，深搜找出其中包含点最多的。代码：#include <cst...

原创 牛客网 Big Boss(完全背包)

题目链接：Big Boss链接：https://www.nowcoder.com/acm/contest/102/L 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述 Many years later, Rainbow Island is in the mer...

原创 Need for Speed（二分）

题目链接：Need for SpeedSheila is a student and she drives a typical student car: it is old, slow, rusty, and falling apart. Recently, the needle on the speedometer fell off. She glued it back on, but sh...

原创 Scrambled Polygon（凸包+极角排序）

题目链接：Scrambled Polygon先给出知识点的讲解链接：传送门极角就是高中学的，极坐标系中的极角。 sort对结构体排序，不都有一个cmp的函数吗？就是这个函数。 我们都会按照一个参数来改，这回我们就按照极角来排序。bool cmp(node a,node b){ int f=mul(a,b,edge[0]);//以edge[0]点为三角形的角点，求他们的...

原创 D. The Union of k-Segments（贪心）

题目链接：D. The Union of k-SegmentsD. The Union of k-Segments time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given n segments on t...

原创 #1722 : 最小差值

题目链接：#1722 : 最小差值题目大意：从n组数中各挑出一个，找出最大值与最小值差的最小值思路：记录每一个数（包括他是第几组的，从0到n*m，从新编号）存入cun结构体中，然后排序，按数值从小到大排序，记录每一组数遇到的最大值，刚好n组数都取到的时候，就更新最大值与最小值的差，然后再剔除最小的那一组数，直到结束。因为我每一次找到的都是最大值，所以当个数刚好为n的时候，就一定是这种情况下...

原创 hihocoder #1148 : 2月29日（容斥原理，有坑）

题目链接：#1148 : 2月29日时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。只有闰年有2月29日，满足以下一个条件的年份为闰年：年份能被4整除但不能被100整除年份能被400整除输入 第一行为一个整数T，表示数据组数。之后每组数据包含两行。每一行格式为”mon...

原创 4 Values whose Sum is 0（二分）

题目链接:4 Values whose Sum is 0啊啊啊，这一题真是亏了，应该二分交一发的，只怪那回lower_bound和upper_bound写出阴影了，导致这回都不敢交了（要好好学习一下了）。题目大意：给你n组数，每组给出四个数，从每一列选出一个数，使得四个数的和为0，问有多少种组合方法。思路：前两组任意组合，记录所有的情况存入sum1数组中，后两组也任意组合，记录所有的情...

原创 优先队列（目前遇到的各种写法）

最近遇到了，就总结一下。优先队列是按照其中的某一个参数，先输出最大（或者最小）的那一个。优先队列的写法：priority_queue<int>q;//括号里可以填各种数据类型priority_queue<node>q;priority_queue<int,vector<int>,greater<int&

原创 卢卡斯定理的详解和线性求解逆元（含题目）

【卢卡斯定理】卢卡斯定理是用来求解：Cmn+mCn+mmC_{n+m}^m%mod的值，而mod是一个质数。我也是看了很长时间的讲解才看懂的（感觉好弱啊~~~）这张图是我认为讲解最全的，（可能一时看不懂，我再补充一下）。 首先，你要看懂(1+x)p≡1+xp%p(1+x)p≡1+xp%p(1+x)^p≡1+x^p\%p 并推出(1+x)a≡(1+x)a0∗(1+xp)a1∗∙∙...

原创 幸运数字Ⅱ（打表+思路）

题目链接：幸运数字Ⅱ思路： 打表你会发现1e9以内的数，有1022个幸运数，将他们存入数组即可。 然后查找每一个数的next(l)的值（我们这里是按幸运数来计算的，不需要遍历所有的数）。打印幸运数的思路：因为只有4和7，所以先记录4，和7，并放入队列中，从队列中取一个数，将它分别乘以4和7，小于1e9的记录并放入队列中，直到队列为空为止，最后要加入4444444444，因为例如1e9的...

原创 m皇后（思路题目）

这道题当初有两点没有想到，一点是不知道该如何处理斜着的方向，另一点是没想到只用求该直线上的两端点。这题要开四个数组，分别记录该方向上的点的最左端和最右端。 然后遍历所有的点，遍历该点的四个方向（上下是一个方向，左右是一个方向，斜向上一个，斜向下一个），如果该方向上只有一个点，就不存在威胁，如果该点在最右端或者最左端，在该方向上就有一个威胁，否则该点在中间，就有两个威胁。然后记录该点有几个威胁...

原创 送分啦-QAQ（斐波那契博弈）

这一题就是一个斐波那契博弈问题。斐波那契博弈： 有一堆个数为n(n>=2)的石子，游戏双方轮流取石子，规则如下：1)先手不能在第一次把所有的石子取完，至少取1颗；2)之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。约定取走最后一个石子的人为赢家，求必败态。结论：当n为Fibonacci数的时候，必败。f[i]：1,2,3,5,8,13,21,34,55...

原创 迷宫2（牛客网，最短路）

这一题主要就是思路加最短路。首先你要知道这是一道求最短路的题目。 因为起点或者终点是没有办法被围起来的，所以只能从下边或者左边的一个点出发，到达上边或者右边的一个点（这个过程只能走上下左右四个方向，因为蜥蜴可以走八个方向），过程的和最小即可，所以是多起点到多终点的最短路问题。下面就是求最短路了，能找到就输出，找不到就输出-1。 当初求最短路一直超时，而且最短路的思路也还有点问题。 用...