- 博客(30)
- 收藏
- 关注
RSS订阅原创 SDIBT_2018SummerVacationTraining_7
1016BSegment Occurrences题目链接题意：给你字符串a,b,查询区间q，在每个查询区间内b出现的次数分析：前缀数组#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;typed...
2018-08-10 11:31:41
129
原创 SDIBT_2018SummerVacationTraining_6
996B World Cup题目链接题意：给你n个通道，每一分钟一个通道只能进一个人到广场。一开始你站在第一个通道，如果该通道上还有人，你就要站到下一个通道，如果你站到最后一个通道时还不能进入，就站到第一个通道去。分析：每到一个通道减去该通道已经进去了多少人，再判断该通道排队人数是否小于等于0，如果是，则输出该通道，否则，进入下一个通道，重复刚才的过程。WA了一发，错在每次用通道人数-...
2018-08-10 10:11:21
125
原创 SDIBT_2018SummerVacationTraining_5
A 1015D比赛的时候看的第一道题就是这道题，看完觉得很简单，但是感觉会写很久，就先跳过了，后来也没时间补题的时候也卡了很久，也有很多特殊情况没考虑到//总之就是菜题意大致是，给你n个房子，你需要移动k次来达到步数s，问每次移动到达的房子，每次移动你不能停留在原地为什么会想到x=(ss-k)/(n-2)呢？每次移动最多能有(n-1)步，就是从第一个房子移动到最后一个房子，我想求出...
2018-08-04 10:48:11
143
转载 数位dp
转载自：https://blog.csdn.net/zhangxian___/article/details/75304335转载自：http://www.cnblogs.com/itlqs/p/5935308.html 数位DP其实是很灵活的，所以一定不要奢求一篇文章就会遍所有数位DP的题，这一篇只能是讲清楚一种情况，其他情况遇到再总结，在不断总结中慢慢体会这个思想，以后说不定就能达...
2018-08-03 16:03:27
164
转载 前向星和链式前向星
链接：https://blog.csdn.net/ACdreamers/article/details/16902023我们首先来看一下什么是前向星. 前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了. 用len[i]来记录所有以i...
2018-08-03 15:57:40
1321
转载 最近公共祖先
转载自：https://www.cnblogs.com/ECJTUACM-873284962/p/6613379.html首先是最近公共祖先的概念(什么是最近公共祖先？)： 在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。 换句话说，就是两个点在这棵树上距离最近的公共祖先节点。 所以LCA主要...
2018-08-03 15:55:44
233
原创 树状数组
Stars POJ2352 题意：求每个等级的数量，等级0-N-1;划分等级：有一个星星Ａ，横纵坐标均小于等于星星Ａ的横纵坐标的星星有多少个，则星星Ａ的等级为几．分析：该题给出的样例的纵坐标均是从小到大排列，所以我们只需要查找横坐标就行了，统计出现的小于等于该横坐标的横坐标有多少个，则该星星为等级几．用vis[getsun(x+1)]来统计该等级的数量．注意等级是0-n-1范围，而...
2018-08-03 15:43:04
99
转载 树状数组彻底入门
转载自：https://www.cnblogs.com/hsd-/p/6139376.htmlint lowbit(int t) { return t&(-t); }void add(int x,int y) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=y; }int getsum(int x) { int ans=0...
2018-08-03 15:04:13
179
原创 SDIBT_2018SummerVacationTraining_4
codeforces 899B这道题老有意思了哈哈哈哈～Everybody in Russia uses Gregorian calendar. In this calendar there are 31 days in January, 28 or 29 days in February (depending on whether the year is leap or not), 31...
2018-08-02 21:17:28
218
原创 线段树
敌兵布阵HDU1166C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。中央情报局要研究...
2018-08-02 14:44:02
153
转载 线段树
转载自https://blog.csdn.net/zearot/article/details/52280189线段树从零开始 By 岩之痕 一：为什么需要线段树？题目一： 10000个正整数，编号1到10000，用A[1],A[2],A[10000]表示。 修改：无 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <...
2018-08-02 11:08:14
705
原创 概率dp(期望)
Dice (III)Given a dice with n sides, you have to find the expected number of times you have to throw that dice to see all its faces at least once. Assume that the dice is fair, that means when you t...
2018-07-29 10:07:01
464
原创 CF1003BBinary String Constructing
Binary String ConstructingYou are given three integers a, b and x. Your task is to construct a binary string s of length n=a+b such that there are exactly a zeroes, exactly b ones and exactly x indi...
2018-07-27 09:26:06
268
原创 高斯消元
今天学了高斯消元...听懂是听懂了...写不出来...只能好好研究模板了ＱＡＱ高斯消元通常解方程组高斯消元用到了增广矩阵：增广矩阵（又称扩增矩阵）就是在系数矩阵的右边添上一列，这一列是线性方程组的等号右边的值。还用到了上三角矩阵：主对角线以下都是零的方阵称为上三角矩阵通过消元得到一个上三角矩阵：如果系数不全为整数，则数组需要是浮点数类型；当上三角矩阵中，m行ｎ列，１．如...
2018-07-26 16:56:38
164
原创 环排列/母函数/唯一分解定理/容斥原理/抽屉原理/卡特兰数/斯特林公式/黙慈金数/贝尔数/那罗延数
环排列把一个m个元素的环在m个不同的位置拆开记得到m个不同的线排列。由于n个不同元素中任取m个元素的排列方法为P(n,m)种，所以n个不同元素中任取m个元素的环排列方法有P(n,m)/m种。特别的，n个不同元素的环排列方法有P(n,n)/n=(n-1)！种。permutation排列（Arrangement），简单讲是从N个不同元素中取出M个，按照一定顺序排成一列，通常用A(M,N...
2018-07-24 17:35:15
705
转载 map 和set
链接https://blog.csdn.net/payshent/article/details/55223099关于容器我们知道的在STL中有关联容器和顺序容器，那么所谓的关联容器是什么？所谓的顺序容器又是什么呢？在STL中的哪些属于关联容器，哪些属于顺序容器呢？下面来做一个简单的介绍：关联容器中的元素是按照关键字来保存和访问的，C++中的关联容器重要就是map和set。而顺序容器是按照元素...
2018-07-24 16:44:55
166
原创 ＵＶＡ465 Overflow (2147483647,atof())
Write a program that reads an expression consisting of two non-negative integer and an operator.Determine if either integer or the result of the expression is too large to be represented as a “normal...
2018-07-24 16:37:43
266
原创 最长公共子序列lLCS/最长上升公共子序列LIS
最长公共子序列 ＬＣＳ１：找最长公共子序列的长度考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2...
2018-07-24 14:36:58
234
原创 打字
snow 是个热爱打字的家伙，每次敲出更快的速度都会让他很开心。现在，他拿到一篇新的打字文章，已知这篇文章只有 26 个小写英文字母，给出 snow 打出这 26 个英文字母分别需要多少时间 (s)，问 snow 打完这篇文章获得的 kpm（打正确的字数/所花的分钟数）最大为多少？注意 snow 可能会打错一些字哦。打错的必定是文章里面存在的。Input多组输入。对于每组数据，首先...
2018-07-22 21:43:24
196
原创 LINE BELT(二维完全背包）
Problem Description最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s...
2018-07-21 11:27:29
267
原创 中国剩余定理
模板#include<stdio.h>#include <iostream>using namespace std;//扩展欧几里得算法int exgcd(int a,int b,int &x,int &y){ int d; if(b==0) { x=1;y=0; return a; ...
2018-07-20 16:16:46
110
转载 逆元的三种求法（费马小定理，扩展欧几里德，递推打表）
1:扩展欧几里德51nod1256【exgcd求逆元】乘法逆元给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。Input输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)Output输出一个数K，满足0 < K &...
2018-07-20 15:13:47
207
原创 三种背包
01背包每种物品只有一件，可以选择拿或者不拿状态转移方程：① 二维解法设f[i][j]表示前i件物品 总重量不超过j的最大价值 可得出状态转移方程f[i][j]=max{f[i-1][j-a[i]]+b[i],f[i-1][j]}②一维解法设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程fj=maxj{fj,f[j−a[i]]+b[i]}完全背包有n件物...
2018-07-19 18:51:44
143
原创 动态规划
用于重叠子问题和最优化问题理解：阶段状态决策策略状态转移方程不容易系列之(4)——考新郎国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找...
2018-07-18 13:53:07
136
原创 三分法
二分法：单调增或单调减三分法：适用于凸函数mid=（l+r)/2;mmid=(mid+r)/2;//Light BulbCompared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bul...
2018-07-18 13:36:35
1778
原创 前缀和
本质：降维一维： 2 5 6 10 14 23 sum 2 7 13 23 37 60如果需要求出i到j的和sum[i-j]=sum[j]-sum[i];二维：简单容斥sum=sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];//一个正整数，如果它能被7整除，或...
2018-07-17 21:10:13
136
原创 尺取
常用在需要在给的一组数据中找到不大于某个上限的优先子序列比如：给长度为n的数组和一个整数m，求总和不小于m的连续子序列的最小长度那么我们先用sum存当前这个子序列的和，从左边第一个数来存，直到这个子序列的和大于等于m为止，再记录下当前长度。当不满足条件就入队，然后得到队列长度，再将队首元素出队，再进行下一次的入队，直到满足条件再次出队，并且将这一次的长度与历史最短长度进行取舍，最后扫到最后...
2018-07-17 20:52:23
244
原创 关灯计划
气愤！！！WA了很多遍！！！有一点坑从下往上 从右到左!!!Problem Description在某次活动上，某组织打算控制一栋宿舍楼的灯光来进行一次灯光表演。他们的实现方式是使所有宿舍全部打开房间内电灯开关，然后通过自己控制电闸来使部分房间通电亮灯，从而摆出一定的图案。已知该宿舍楼有 n 层，每层有 m 个房间，房间号从右向左递增，且房间号都是奇数。由于这个组织为了表演控制宿舍通电造成了在宿舍...
2018-06-12 20:29:43
154
原创 1164FatMouse' Trade(贪心算法)
ummm.sort排序果然好用。我有五块钱，最多能买多少豆子？现在有两块钱一斤，一块钱一斤，和十块钱一斤的豆子。最好是能买一块钱一斤的豆子啦~这样豆子最多DescriptionFatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favor...
2018-03-29 15:15:10
76
原创 1185Divisor Summation
注意：直接用循环找它的因数容易时间超限！！#include<stdio.h>int main(){ int n,i,sum,m,j; scanf("%d",&n); for(i=0;i<n;i++) { sum=0; scanf("%d",&m); if(m!=1) { ...
2018-03-28 20:03:16
178
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人