• avatar 寒江陪烟火🔥 2016-11-19 11:10:00

    codeforces724E Goods transportation(欧拉回路)

    题意: 给你n个点m条无向边,不保证图联通,让你给每条边定向,使得图中入度=出度的节点数量最大 思路: 图中奇数度节点肯定是不行的,奇数度节点有偶数个,可以把他们都连到附加的n+1这个节点上转为偶数度 这样全部的节点都为偶数度,然后跑fleury就可以了,注意图的联通,有n+1节点的边不输出

  • avatar 寒江陪烟火🔥 2016-11-19 10:19:00

    UVAlive4097 Yungom(思路)

    题意: 给你一个n(200)和d(200),表示你有d种字母,要用他们组成无公共前缀的n个字符串, 接下来给你d个数,以此表示每种字母的花费,问你最小花费 思路: 可以暴力找,首先把d种花费排序,然后存入前d个下标中,如果n>d就后面都存入inf ans初值为1-n的下标数之和,然后

  • avatar 寒江陪烟火🔥 2016-11-07 22:34:00

    hihocoder1251 Today Is a Rainy Day(暴力)

    题意: 给你两个长度不超过110的数字串,只有1-6,让你把下面的串通过最少的操作变为上面的串 操作1:改变一个位置的数字 操作2:选取1-6其中的一个数字,让串中所有等于这个数字的数字全部变为一个其他的数字 思路: 当时做的时候一直在考虑怎么解决操作2的次序问题(如第四组样例,需要转换7

  • avatar 寒江陪烟火🔥 2016-11-05 13:23:00

    卡特兰数及其扩展

    普通(n==m):c(n*2,n)/(n+1) 扩展(n>m):(n-m+1)/(n+1)*c(n+m,n)

  • avatar 寒江陪烟火🔥 2016-11-04 20:57:00

    最小表示法

    int work(int m,int p[]) { int i,j,l; i=0;j=1; while(i<m&&j<m) { for(l=0;l<m;l++) if(p[(i+l)%m]!=p[(j+l)%m]) b

  • avatar 寒江陪烟火🔥 2016-11-03 20:30:00

    求1——10^x-1各个位置的和

    求1——10^x的各位和=45*x*10^(x-1) 如求1——10^18的各位和=45*18*10^17  

  • avatar 寒江陪烟火🔥 2016-11-03 19:10:00

    ural1979 Resources Distribution(构造)

    题意: 给你一个n(100)阶魔方,共有6*n*n个块,让你填入1-6*n*n这些数字,要求使得从任意点出发朝任意方向绕一圈的和都相等,让你输出魔方 spj 思路: 绕圈每个点被饶了两次,也就是这些块的总贡献是这些数字的和*2,然后圈的数量也是一定的,是3*n,然后每一圈的和是相等的,所以也是

  • avatar 寒江陪烟火🔥 2016-11-03 18:50:00

    codeforces722D Generating Sets(构造 set)

    题意: 给以一个目标序列n(5e4)个数,每个数大小1e9,问你最大值最小的原序列是什么 spj 每个数可以变为*2或者*2+1,原序列和目标序列没有重复的数,变换过程中可以出现 思路: 把最大的数/2变小,直到当前序列中的最大值无法变小就得到了一个原序列了 /* *********

  • avatar 寒江陪烟火🔥 2016-11-01 16:57:00

    Gym 100801H Hash Code Hacker(构造)

    题意: 一个长度为n的字母串的数值为s [0]*31^( n -1) + s [1]*31^( n -2) + ... + s [n -1],其中s[i]为字母的ASCII码,数值用int表示 现在给你一个k(2-1000)要求你构造出k个数值相同的字母串,长度小于等于1000 思路: 可以

  • avatar 寒江陪烟火🔥 2016-11-01 16:49:00

    Gym 100801D Distribution in Metagonia(构造)

    题意: 给你一个LL的数,让你把它分解为许多个数相加的形式, 要求这些数的质因子只有2和3并且这些数的因子2的个数和因子3的个数不能同时小于等于其他任意一个数 要求这些数的数量不超过100个 思路: 递归构造,如果当前数正好符合条件就终止,否则先让他把2和3尽可能的除去,并乘在tmp中作为

  • avatar 寒江陪烟火🔥 2016-10-30 21:28:00

    codeforces721C Journey(dp暴力)

    题意: 5000个点5000条边的图,总长为t(1e9) 每条边都有边长(1e9) 问你从1到n走的路程不超过总长的条件下经过节点数最多的方案输出任意路径 思路: 5000*5000暴力 最多答案就是n,dp[i][j]代表经过了i个节点到达了节点j的最小距离 每一层对所有的边更新,记

  • avatar 寒江陪烟火🔥 2016-10-30 17:47:00

    HDU5952 Counting Cliques(暴力)

    题意: 100个点1000条边的图,问你有多少个s个点的团,每个节点的度不超过20 思路: 暴力。。边太少,直接纯暴都可以 2106ms /* *********************************************** Author :devil *

  • avatar 寒江陪烟火🔥 2016-10-30 12:22:00

    HDU5943 Kingdom of Obsession(思路题+二分匹配)

    题意: 给你两个数n,s(1e9),问你能否使得s+1--s+n和1--n全部匹配 每个数只能匹配他的因子 思路: 要匹配的这一段数中非重合部分最多有1个素数,也就是说n和s不能同时很大 我打了1e9的素数间隔表,发现最大间距才280多。。 然后索性直接当n和s都大于500的时候就输出n

  • avatar 寒江陪烟火🔥 2016-10-30 12:18:00

    HDU5938 Four Operations(思路水题)

    题意: 给你一个长度为5-20的数字串(1-9),让你在其中顺序添加+-*/使得运算结果最大 思路: 假设是a+b-c*d/e的形式,可以发现,c*d越小越好,所以c d各占1位 然后e的话只可能是1位或者两位(长度为6,7的时候可能会有,如111991) 然后a和b就有两种情况,一个占1

  • avatar 寒江陪烟火🔥 2016-10-30 12:14:00

    HDU5935 Car(精度水题)

    题意: 给你一些递增的正整数点,让你从0开始沿着这些点走 之间速度不能下降,然后任意两点间的时间是整数 思路: 最后一段肯定是1分钟过的,然后就有了初始速度,向前推就可以了 但是用double存的速度结果就喜闻乐见了,改成分数就过了 /* *********************

  • avatar 寒江陪烟火🔥 2016-10-30 12:09:00

    HDU5945 Fxx and game(单调队列)

    题意: 给你三个数x,k,t(1e6),表示你在x每次可以减1-t或者可以整除k的时候除以k 问你到达1的最小步数 思路: 这次BC简直福利场。。过了题就上分 我是用单调队列维护的前k个值,然后被卡掉了- - 看了题解改成单调队列维护,当时就没想到啊(其实是以为不会被卡就没改而已)

  • avatar 寒江陪烟火🔥 2016-10-24 22:36:00

    codeforces717E Paint it really, really dark gray(树上dfs)

    题意: 给你一棵树,2e5个节点,每个节点有一种颜色(黑色或粉色) 让你从节点1开始,自由沿边行走,到达节点时会把这个节点的颜色改变 要求你输出任意一条路径使得从节点1出发,所有节点的颜色都变为黑色 思路: 很明显要递归遍历 每到达一个节点就先改变节点的颜色标志并输出当前节点 如果当前

  • avatar 寒江陪烟火🔥 2016-10-22 20:22:00

    笔试助攻题(思路)

    题意: 给你一个长度为1e5的串,包含数字0-9和? ?可以替换成任意数字 要求保证任意相邻的10个数均不相同 问有多少种方案? 思路: 乍一看还像个dp什么的,每个位置跟前后9个都有关系,越想越复杂 然而仔细一想发现,每隔10个数的数字是相同的 也就是说串中的1,11,21,,,这

  • avatar 寒江陪烟火🔥 2016-10-22 19:41:00

    uvalive6913 I Want That Cake(博弈dp)

    引自:http://www.cnblogs.com/qscqesze/p/5734143.html 题意: 有两支队,每只队都有n个人,一共有m个蛋糕,每个人至少吃一个,最多吃k个。 都采取最优策略,谁吃到最后一个蛋糕,那么那只队就胜利。 按照给定的顺序去吃蛋糕,问你最后谁胜利。 思路:

  • avatar 寒江陪烟火🔥 2016-10-22 12:40:00

    POJ1741 Tree(树分治)

     题意: 求树上距离小于等于K的点对有多少个 思路: 每次分治,我们首先算出重心,为了计算重心,需要进行两次dfs,第一次把以每个结点为根的子树大小求出来,第二次是从这些结点中找重心 找到重心后,需要统计所有结点到重心的距离,看其中有多少对小于等于K 但是这些求出来满足小于等于K的里面只有

  • avatar 寒江陪烟火🔥 2016-10-14 12:27:00

    codeforces713D Animals and Puzzle(二维倍增)

    引自:http://www.cnblogs.com/qscqesze/p/5929117.html 题意: 给你一个01矩阵,然后Q次询问,每次询问一个矩形区域中,最大的全一正方形的边长是多少。 思路: 首先考虑Dp,dp[i][j]表示以(i,j)位置为右下角,最大的正方形边长是多少,显然

  • avatar 寒江陪烟火🔥 2016-10-14 10:58:00

    codeforces713C Sonya and Problem Wihtout a Legend(dp)

    题意: 给你一个序列,你可以改变任意一个数字的大小,代价是改变量 问你使其变成严格单调递增序列的最小代价 思路: 单调不减的最小代价可以用O(n^2)的时间搞出来,而让单调递增转化为单调不减只需要让a[i]-i就可以了 /* *********************

  • avatar 寒江陪烟火🔥 2016-10-11 15:14:00

    codeforces724E Goods transportation(最小割——dp)

    题意: 原点汇点连所有的,流量给出,左边点连右边的,流量为c,问最大流 思路: /* *********************************************** Author :devil ********************************

  • avatar 寒江陪烟火🔥 2016-10-10 20:53:00

    codeforces710E Generate a String(dp)

    题意: 给你一个n(1e7),和x,y 每次可以+1/-1/*2 +-花费x,*2花费y 问你从0变到n的最小花费 思路: 关键是n小啊~ 对于每个i,他可能是由i-1加了1 或者i/2乘了2得来的 当前是奇数的时候,可能是i/2*2+1或者(i/2+1)*2-1得来的 前者在i

  • avatar 寒江陪烟火🔥 2016-10-09 14:26:00

    codeforces Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) 题解(A-D)

    A. Checking the Calendar 题意: 给你两个星期几,问你非闰年能否有相邻的两月的一号满足前面那月是第一个后面那月是第二个 思路: 水水就过了,就看是不是差0,2,3 /* *************************************

  • avatar 寒江陪烟火🔥 2016-10-06 12:58:00

    BNUOJ52317 As Easy As Possible(树上倍增)

    题意: 给你一个1e5长度的easy串(只含easy四个字母) 1e5个询问,每个询问一个区间l,r 问这个区间内easy的个数 思路: 当时还想预处理出最优的easy区间,然后lower_bound wa了几发发现这样并不是最优的,然后就放弃了~ 出题解后补了一个倍增 每个字母记录

  • avatar 寒江陪烟火🔥 2016-09-29 17:19:00

    hihocoder1386 Pick Your Players(dp)

    题意: 你需要买一个足球队(11个球员),每个球员有位置、价值。花费,有以下限制: 位置分为前锋(1-3人)、中腰(2-5)、后卫(3-5)、守门员(1) 每个人有 value,总的 value 是每个人的value加起来 ,选一个队长,队长的加两次 每个人有个 cost,总花费不能超过给定值 求

  • avatar 寒江陪烟火🔥 2016-09-22 12:57:00

    常用函数

    #include <math.h> double exp(double x)  求e^x的值 double fmod(double x,double y)  浮点数取模x%y double modf(double x, double *y)  返回x的小数部分,将整数部分给y #

  • avatar 寒江陪烟火🔥 2016-09-21 22:17:00

    hdu5901 Count primes(大素数模版)

    题意: 1——n(10^11)的素数个数 思路: 参考:http://blog.csdn.net/chaiwenjun000/article/details/52589457 第一个O(n^(3/4)) /* *************************************

  • avatar 寒江陪烟火🔥 2016-09-21 21:59:00

    hdu5900 QSC and Master(区间dp)

    题意: 给你一个长为300的序列,每个位置有个代号和价值 如果相邻两个位置的代号不互质就可以得到他们的价值和并移除他们 问最大价值 思路: 区间dp,n才100,直接n*3就可以 /* ***********************************************

  • avatar 寒江陪烟火🔥 2016-09-21 21:36:00

    hdu5898 odd-even number(数位dp)

    题意: 求L到R区间内,连续奇数个数是偶数,连续偶数个数是奇数的数的个数 思路: 裸数位dp,赛场上忘了不合法的break,妈的调了一个多小时简直是日了狗了! 本来就是蒟蒻还感冒了什么题都写不出来   /* *************************************

  • avatar 寒江陪烟火🔥 2016-09-21 17:07:00

    hdu5894 hannnnah_j’s Biological Test(组合数取模)

    题意: n个桌子围成圈m个人,间隔至少k个桌子,问方案数 思路: 这可以推出来一个公式C(n-m*k-1,m-1),然后第一个人有n中选择,每个人是相等的 所以就*n/m就好了,除改成乘逆元就好了 /* ****************************************

  • avatar 寒江陪烟火🔥 2016-09-20 22:25:00

    HDU5883 The Best Path(并查集+欧拉路)

    题意: n个点m条边,问m条边构成的是否为欧拉路。 是的话输出路径上所有点的异或和,每个点经过几次异或几次。 思路: 先用并查集判断是否连通,然后如果是欧拉路的话有两种情况 如果奇数度节点有2个,就枚举这两个点做起点,选大的 如果都为偶数度节点,就枚举n个起点,选大的 /* *

  • avatar 寒江陪烟火🔥 2016-09-20 15:39:00

    HDU5881 Tea(简单题)

    题意: 你有一个容量为【l,r】的壶,你要往两个杯子里倒水 水壶你只能判断是否为空 使得最后杯中水相差<=1升,壶中剩余的水<=1升 思路: 这个题简直太遗憾了 当天网络赛的时候我感冒了很难受状态几乎为0 然后学弟最后40分钟左右的时候把这个题跟我说了一下,我当时就想出来正

  • avatar 寒江陪烟火🔥 2016-09-20 14:49:00

    组合数取模

    参考:http://blog.csdn.net/acdreamers/article/details/8037918 NM较小 const int N = 1e6+5; const int mod = 1e9+7; int f[N]; int inv(int x) {

  • avatar 寒江陪烟火🔥 2016-09-20 13:36:00

    codeforces703D Mishka and Interesting sum(区间偶数异或)

    题意: 给你一个序列,q个询问l,r 要求出l到r区间内出现偶数次的数的异或值 思路: 预处理异或前缀sum 将询问按r放入vector,存的pair<l,i> 树状数组部分有点同于求区间数的种数。 last记录每个数前一次出现的位置。 走到i时,如果a[i]出现过,那

  • avatar 寒江陪烟火🔥 2016-09-09 21:31:00

    upcoj2679 Binary Tree(思路题)

    题意: 给你两个串,每个串有LRU三个操作,L(R)为去左(右)子树,U为回到父亲(根节点不作处理) 然后按这样的规则遍历完第一个串,将现在的位置作为第二个串的起始位置 然后遍历第二个串,第二个串的每个位置都可以执行或者不执行,U操作为将原点倒退(按第一个串行进的过程反向) 问你最多能到多少

  • avatar 寒江陪烟火🔥 2016-09-09 21:19:00

    upcoj2673 It Can Be Arranged(isap)

    题意: 有N节课,每节课有起止时间和学生数 然后给你M是每个教室容纳的学生数 然后给你n*n的矩阵表示上完第i节课然后上第j节课需要a[i][j]的时间调整 第i节课结束时间加上调整时间要严格小于第j节课的开始时间 问你最少需要多少个教室 思路: 很简单的一个最大流 每节课分为两个节

  • avatar 寒江陪烟火🔥 2016-09-09 16:23:00

    bzoj1050 旅行comf(并查集)

    题意: Description   给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T ,求一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,

  • avatar 寒江陪烟火🔥 2016-09-08 19:52:00

    bzoj1012 最大数maxnumber(线段树)

    题意: Description   现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L 个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加 上t,其中t是最近一次查询操作的答案(如

  • avatar 寒江陪烟火🔥 2016-09-08 16:34:00

    bzoj1003 物流运输(dijkstra+dp)

    题意: 一共有n天,每天都要把货物从1运到m,代价是路长 然后每个地方都可能有几天不能走 然后你就必须改变路线在那天避开这些地方,这需要代价k 问你n天的最小代价 思路: 一共最多100天,可以n^2暴力时间段,表示这段时间的路径是一样的 然后跑dijkstra,得出最优解 然后用d

  • avatar 寒江陪烟火🔥 2016-09-06 23:23:00

    hihocoder1198 Memory Allocating Algorithm(链表~)

    题意: 小Hi和小Ho最近在研究内存分配的机制,他们写了一个比较简单的内存。内存可以表示成M个连续的存储空间,下标为0..M-1: 每当有数据写入时,内存分配程序会从下标0开始向右找一块足够存放下该数据的区域,将该数据写入。比如写入一个长度为2的数据,因为是第一个数据,我们用1来表示:

  • avatar 寒江陪烟火🔥 2016-09-06 15:57:00

    hihocoder1199 Tower Defense Game(树形dp)

    题意: 给定一颗以1为根节点的树,每个节点有一个购入价格p和卖出价格q。 进入一个节点时需要花费p,离开时可以收回q,每个节点只产生一次购入和卖出。 请你选择一个遍历的顺序,要求在遍历的过程中身上的钱数不小于0,且出发时带的钱数最少。 按照遍历的顺序是指:当你选择了一颗子树之后,你需要将这个

  • avatar 寒江陪烟火🔥 2016-09-06 11:12:00

    hihocoder1200 Increase Charisma Points(二进制log拆解答案)

    题意: 给定一张N个点的完全图,可以从任何一个点出发,同一个点可以经过多次。询问总路径长度不超过M的情况下,最多能够经过多少个点。 思路: 首先我们能够想到一个最简单的模拟算法。 建立数组dist[][],dist[i][j]表示经过i个点后,最后停留在j所以经过的最短路径长度。 那么有如

  • avatar 寒江陪烟火🔥 2016-09-05 20:05:00

    AtCoder Grand Contest 004 C - AND Grid(思路题)

    题意: 给你一个n*m的矩阵,矩阵中有.和#,#表示两图重合的部分,边缘没有# 然后要你构造两个n*m的图,要求#是连通的,然后合并之后重合的部分就是原图中的# 思路: 又是一到思路题 当时被B题智商压制没读这道题 就是构造一个这种图 然后重合部分两个图都填为#就可以了 /

  • avatar 寒江陪烟火🔥 2016-09-05 19:32:00

    AtCoder Grand Contest 004 B - Colorful Slimes(思路题)

    题意: 给你长度为n(n<=2000)的一个序列(环),每个位置有一个数值 (1e9) 你可以翻开这个位置,消耗为这个位置上的数值 你也可以循环右移一位(n移到1),比如原先你翻开了1,现在移动完成后你翻开的是2 这个操作消耗为x(1e9) 问你使所有的位置都翻开需要的最小带价是多少

  • avatar 寒江陪烟火🔥 2016-09-04 19:52:00

    hihocoder1238 Total Highway Distance(树形dp)

    题意: 给定一颗有N个节点的带权树,之后进行M次操作: Q操作:询问树上所有点对之间的距离之和 E操作:修改树上某一条边的权值 思路: 树形dp求出每条边被利用的次数并统计 然后修改的时候就把这个边权修改并将改变值乘上利用次数更改ans /* **********

  • avatar 寒江陪烟火🔥 2016-08-28 20:37:00

    POJ2104 K-th Number(主席树)

    题意: 静态区间第K大 思路: 之前学划分树的时候当了模版练了, 感觉划分树真是不该学。。 又拿来练主席树吧 /* *********************************************** Author :devil **************

  • avatar 寒江陪烟火🔥 2016-08-12 16:07:00

    SPOJ3267 D-query(主席树模版)

    题意: 给一个序列,问区间内有多少个不相同的数 思路: 主席树模版,按斌巨的模版写了一发orz /* *********************************************** Author :devil ***********************

  • avatar 寒江陪烟火🔥 2016-08-07 16:31:00

    HDU5807 Keep In Touch(分段式dp)

    题意: 在Byteland一共有n个城市,编号依次为1到n,同时有m条单向道路连接着这些城市,其中第i条道路的起点为ui​​,终点为vi(1≤u​i​​<v​i​​≤n)。 特工团队一共有3名成员:007,008,以及009,他们将要执行q次秘密任务。 在每次任务中,三人可能会处于

  • avatar 寒江陪烟火🔥 2016-08-07 16:21:00

    HDU5806 NanoApe Loves Sequence Ⅱ(二分ortwo-pointer)

    题意: 求满足区间中>=m的数>=k个的区间有多少 思路: 记小于m的数为0,大于等于m的为1,用sum维护区间和 然后我的做法是枚举右端点,二分左端点得到答案,复杂度O(nlogn) /* ****************************************

  • avatar 寒江陪烟火🔥 2016-08-07 15:14:00

    hihocoder1356 分隔相同整数

    题意: 给你一个序列,让你重新排序,相邻不能相同,且输出字典序最小的 如果不行输出-1 思路: 用map存储每个数字出现的次数 用set的排序选出次数多的数字 然后如果当前数字必须要填了就填上,否则填尽可能小的那个 /* *****************************

  • avatar 寒江陪烟火🔥 2016-08-06 14:55:00

    BZOJ4509 Angry Cows(dp)

    题意: 大概就是一条线上有n个炸弹,然后让你随意扔一个爆炸半径为r的炸弹使他们全部爆炸, 第一次被引爆的炸弹爆炸半径为r-1,第二次为r-2。。。 求r最小是多少 思路: 用两个数组处理得到从左往右和从右往左到当前炸弹时的爆炸半径最小是多少,然后枚举投弹位置就可以了 /* ****

  • avatar 寒江陪烟火🔥 2016-07-30 16:58:00

    POJ2887 Big String(块状数组)

    参考:http://blog.csdn.net/htt_h/article/details/44862813 题意: 给你一个不超过1e6的字符串,和不超过2000次的操作 操作分为两种: 1.将一个字符插入到某个位置的前面 2.询问当前位置的字符 思路: 学了一发块状数组,就是把1e

  • avatar 寒江陪烟火🔥 2016-07-29 14:21:00

    HDU5775 Bubble Sort(树状数组求逆序数)

    题意: 给你一段序列(排列)和排序方式 让你求出每个数在排序过程中移动的范围 思路: 序列排序结束是升序的,能移动到的最左端就是min(i,a[i]) 如果a[i]比较大,他就不会向左移,就是a[i],如果比较小就最多移动到i的位置 能移动到的最右端就是当前的i加上从右向左比他小的数的个

  • avatar 寒江陪烟火🔥 2016-07-29 13:37:00

    HDU3449 Consumer(依赖背包)

    参考:http://www.cnblogs.com/wuyiqi/archive/2011/11/26/2264283.html 题意: 有n个箱子,每个箱子里装有一些物品 要买这些物品就要先买这个箱子 这就符合依赖背包的条件了 要想买b就必须买a 思路: 先写二维的,dp[i][j]

  • avatar 寒江陪烟火🔥 2016-07-28 17:47:00

    HDU5763 Another Meaning(KMP+dp)

    题意: 给你一个主串一个子串,然后主串中匹配到子串就可以把当前部分改为*, 问主串有多少中不同的样子 思路: 先KMP预处理主串中所有匹配到子串的末尾位置 然后用dp dp[N][2]只更新成功匹配的末尾位置 其中dp[i][0]保存当前位置不参与改变*的总情况 dp[i][1]保存

  • avatar 寒江陪烟火🔥 2016-07-28 17:38:00

    HDU5773 The All-purpose Zero(LIS)

    题意: 给你一个长度为10W的数组,每个数范围0-100W 其中的0可以变为INT范围内的任意值 问最长上升子序列的长度 思路: 这题当时水过了。。数据太水 比赛结束了看了题解,简直膜拜神思路。。 0可以转化成任意整数,包括负数, 显然求LIS时尽量把0都放进去必定是正确的。 因此

  • avatar 寒江陪烟火🔥 2016-07-28 17:10:00

    快速乘法模版(quick_mul)

    就是把快速幂*改了+ 这样就解决了乘法暴LL的问题了 LL quick_mul(LL aa,LL bb,LL mod) { aa%=mod; LL ret=0; while(bb) { if(bb&1) ret=(ret+aa)%mo

  • avatar 寒江陪烟火🔥 2016-07-25 16:22:00

    codeforces 700B Connecting Universities

    题意: 给你一棵树,边权均为1,上面有2K个点为学校 让你将学校配对,配对的学校需要修路连接 问修的路最长为多少 思路: 每条边计算最大价值 即这条边两端学校中较小的那个数量 因为最大利用这条边就要把两端的学校配对 较少的那端的学校全都配对过去,就全都走了这条路 然后把每个边的价值

  • avatar 寒江陪烟火🔥 2016-07-25 15:43:00

    HDU3107 Godfather(树的重心)

    题意: 给你一棵树,求树的所有重心并按字典序输出 思路: 树形dp找一遍,把重心记到一个数组里,最后sort一下 这个题用vector居然超时。。。。。。 这让习惯用vector的人瞬间感觉就不好了。。 /* ************************************

  • avatar 寒江陪烟火🔥 2016-07-25 15:24:00

    POJ1655 Balancing Act(树的重心)

    题意: 给你一棵树,求树的重心 如果有多个就输出序号最小的 思路: 树的重心就是以它为根的所有子树中节点最多的节点数最小 树形dp轻松可以解决 /* *********************************************** Author :dev

  • avatar 寒江陪烟火🔥 2016-07-22 21:50:00

    codeforces 691F Couple Cover(暴力预处理)

    题意: 给你一个长度为n的序列,m个询问,每次学问一个数 让你回答序列中乘积不小于它的数对有多少对 思路: 预处理当前序列中不大于当前值的数对有多少,然后用总数减去他的前一个就是答案了 /* **********************************************

  • avatar 寒江陪烟火🔥 2016-07-22 21:18:00

    codeforces 691E Xor-sequences(矩阵快速幂)

    引自:http://www.cnblogs.com/shuguangzw/p/5674089.html /* *********************************************** Author :devil **********************

  • avatar 寒江陪烟火🔥 2016-07-22 21:04:00

    codeforces 691D Swaps in Permutation(并查集)

    题意: 给你一个长度为n的数列,然后给你m组数, 表示这两个数可以交换 然后让你给出字典序最大的数列 思路: 用并查集,可交换的数都是成组的,把同一并查集中的数加在根节点的vector后, 在一个并查集中的数,从大到输出就好了 /* ***********************

  • avatar 寒江陪烟火🔥 2016-07-20 17:08:00

    HDU5727 Necklace(环排+匈牙利)

    这个题是参考网上各大聚聚的代码才写出来的,没办法我太弱了 题意: 给你阴阳珠子各n个,让你串成阴阳相间的串。 给你m种搭配,表示某阳珠子与某阴珠子相邻时会变暗 问你最少有多少阳珠子变暗 思路: 当时想到了可能与二分图有关,但是一直没有什么好的思路 看了网上的题解才恍然大悟 大概就是先

  • avatar 寒江陪烟火🔥 2021-03-26 07:59:00

    非常抱歉,全站内容审核中...

    为了更加合法合规运营网站,我们正在对全站内容进行审核,之前的内容审核通过后才能访问。 由于审核工作量巨大,完成审核还需要时间,我们正在想方设法提高审核速度,由此给您带来麻烦,请您谅解。 如果您访问园子时跳转到这篇博文,说明当前访问的内容还在审核列表中,如果您急需访问,麻烦您将对应的网址反馈给我们

  • avatar 寒江陪烟火🔥 2016-06-23 15:28:00

    codeforces679C Bear and Square Grid(dfs优化)

    题意: 给你n*n的矩阵(n<=500),矩阵内有x和.,然后给你一个k 你可以把一个k*k的矩阵内全部变成. 问你最多有多少个.可以联通 思路: n^2枚举炸的位置,先预处理联通块和区间.的和 每次向右枚举只需要删掉左边一列,加上右边一列 每次枚举的区间是k*k然后扩展一圈((

  • avatar 寒江陪烟火🔥 2016-06-22 18:00:00

    codeforces679B Bear and Tower of Cubes(思路)

    题意: 给一个m<=10^15,每次都减最接近当前值的立方数 让你找一个不大于m的最大的数并且这个数是减法次数最多的数 思路: 每次有两种情况,一个是减去第一个不大于当前值的立方数 另一个是减去第二个不大于当前值的立方数 但是这时候当前数应变为下一个立方数-1-当前立方数 dfs

  • avatar 寒江陪烟火🔥 2016-06-10 20:08:00

    UPCOJ2012 The King’s Walk(dp)

    题意: 给你一个n*n的地图,起始位置和目标位置 你每次可以八向走 问你有多少种最少步数到达的方案 答案取模 思路: 走的步数是确定的,是横坐标、纵坐标只差较大的那个 然后就是用确定的步数走另一个坐标差这样的距离 每次可以不走,前进一步,后退一步,不超出地图范围即可 这尼玛简直看出

  • avatar 寒江陪烟火🔥 2016-06-10 14:25:00

    第七届山东省省赛D Swiss-system tournament(归并排序)

    题意: 给出2n个选手的id,能力值和初始分数 然后按分数从大到小,id从小到大排序 相邻的选手打 能力值大的分数+1 进行r轮 问你比赛过后,排名第q的选手id是多少 思路: 开始先sort一遍,每一轮比赛都归并处理 赢得人分一组,输的人分一组,保证两组有序 然后合并到原数组

  • avatar 寒江陪烟火🔥 2016-06-10 14:20:00

    第七届山东省省赛C Proxy(最短路)

    题意: 给出n个点和一些单向边,问从0到n+1 如果不能到则输出-1 如果能一步到则输出0 否则输出第一个到达的节点 如果两条路距离相等,则输出较小的节点 思路: 赛场上从前向后扫然后又向前推的,,,特别别扭 回来之后想了下,可以建反向边,从n+1走到0记录前驱就好了 /*

  • avatar 寒江陪烟火🔥 2016-06-09 15:46:00

    hihocoder1185 连通性·三

    输入 第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000 第2行:N个正整数,第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000 第3..M+2行:2个正整数,u,v。表示存在一条从u到v的单向路径。1≤u,v≤

  • avatar 寒江陪烟火🔥 2016-06-09 14:37:00

    hihocoder1184 连通性二·边的双连通分量

    输入 第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000 第2..M+1行:2个正整数,u,v。表示存在一条边(u,v),连接了u,v两台服务器。1≤u<v≤N 保证输入所有点之间至少有一条连通路径。 输出 第1行:1个整数,表示该

  • avatar 寒江陪烟火🔥 2016-06-09 14:07:00

    hihocoder1183 连通性一·割边与割点

    输入 第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000 第2..M+1行:2个正整数,u,v。表示存在一条边(u,v),连接了u,v两台服务器。1≤u<v≤N 保证输入所有点之间至少有一条连通路径。 输出 第1行:若干整数,用空格

  • avatar 寒江陪烟火🔥 2016-05-31 10:59:00

    SDUTOJ1755 装备合成(dfs序+线段树)

    题目描述 小白很喜欢玩儿LOL,但是无奈自己是个坑货,特别是在装备的选择和合成上,总是站在泉水里为选装备而浪费时间。现在小白试图解决这个问题,为了使问题简单化,我们把游戏中的装备合成规则简化如下: (1)装备的合成关系构成一棵合成关系树,如图(a)所示,装备的下级装备叫合

  • avatar 寒江陪烟火🔥 2016-05-30 17:36:00

    HDU2509 Be the Winner(反NIM)

    题意: N堆苹果,先取完的输。。 思路: 反NIM 先手获胜的条件是所有堆都为1并且异或值为0 或者有的堆大于1并且异或值不为0 /* *********************************************** Author :devil Crea

  • avatar 寒江陪烟火🔥 2016-05-29 12:23:00

    HDU1536 S-Nim(SG函数)

    题意: 给一个集合f,表示可以取的个数 N堆石子,每次取其中一堆的f[]个, 谁先取完所有的就赢了 输出 思路: sg最后异或 /* *********************************************** Author :devil Crea

  • avatar 寒江陪烟火🔥 2016-05-29 11:51:00

    HDU1848 Fibonacci again and again(SG函数)

    题意: 3堆石子,每堆个数已知,每次只能取一堆的fib个 思路: sg最后三堆异或 /* *********************************************** Author :devil Created Time :2016/5/29 11:5

  • avatar 寒江陪烟火🔥 2016-05-29 11:32:00

    HDU1850 Being a Good Boy in Spring Festival(NIM统计)

    题意: NIM题,问你第一个人有多少种取的方案 思路: 全部异或完后,然后让这个值分别异或每一个数 如果结果小于当前数,就说明可以从该堆中取走异或这个数这么多石子 ans就++ /* *********************************************** A

  • avatar 寒江陪烟火🔥 2016-05-29 11:20:00

    HDU1849 Rabbit and Grass(NIM整理)

    这类题就是有N堆东西,每次可以取任意堆的任意个 最后取完的获胜 就是把N堆读进来全部异或,不等0就赢了 /* *********************************************** Author :devil Created Time :2016/

  • avatar 寒江陪烟火🔥 2016-05-29 11:13:00

    HDU1847 Good Luck in CET-4 Everybody!(SG函数)

    Problem Description 大 学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考 场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,K

  • avatar 寒江陪烟火🔥 2016-05-26 23:03:00

    HDU2516 取石子游戏(fibonacci博弈)

    Problem Description 1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win". I

  • avatar 寒江陪烟火🔥 2016-05-25 17:23:00

    HDU3488 Tour km

    /* *********************************************** Author :devil Created Time :2016/5/25 17:22:34 ********************************************

  • avatar 寒江陪烟火🔥 2016-05-25 16:59:00

    HDU2255 奔小康赚大钱(km模板题)

      Description          传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。         这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容

  • avatar 寒江陪烟火🔥 2016-05-25 15:49:00

    NYOJ61 传纸条(一) 双线程dp

    题意: 从左上向右下传纸条,再传回来,经过不同的路径 中间每个人都有一个好心程度 问最大的好心程度 思路: 去了再回来就等于直接走两遍不同的路径 三维dp 第一维记走了多少步 第二维记第一条路径的纵坐标 第三维记第二条路径的纵坐标 优化了一下32ms过掉 /* *****

  • avatar 寒江陪烟火🔥 2016-05-17 22:28:00

    POJ3189 Steady Cow Assignment(二分图多重匹配)

    题意: N头牛M个棚,每头牛对每个棚都有喜爱顺序 每个棚都有自己的容量 问你怎么分配使得所有牛的喜爱程度差距最小 思路: l r表示一段喜爱程度的范围 建图就按l 到 r里的棚子建 然后两个标移动从头到尾就可以扫出最小值了 /* ************************

  • avatar 寒江陪烟火🔥 2016-05-17 22:07:00

    POJ2112 Optimal Milking(二分图多重匹配)

    题意: K个产奶机,C头奶牛,每个产奶机最多可供M头奶牛使用;并告诉了产奶机、奶牛之间的两两距离Dij(0<=i,j<K+C)。 问题:如何安排使得在任何一头奶牛都有自己产奶机的条件下,奶牛到产奶机的最远距离最短?最短是多少? 思路: 二分图多重匹配 先用floyd求最短距离

  • avatar 寒江陪烟火🔥 2016-05-17 17:56:00

    POJ2289 Jamie's Contact Groups(二分图多重匹配)

    题意: 给定一个规模为n的名单,要将名单中的人归到m个组中,给出每个人可能的分组号,需要确定一种分配方案,使得最大规模的组最小。 思路: 二分图多重匹配 如果所到的组没满,就去那个组 如果满了,就从那个组里踢出一个 如果能踢出来,就把那个踢出来,把当前的放进去 如果所有能到的组都踢不出

  • avatar 寒江陪烟火🔥 2016-05-17 17:13:00

    HDU3829 Cat VS Dog(最大独立集)

    题意: n个小孩,每个小孩喜欢一种动物讨厌一种动物 你是管理员,可以任意去掉一些动物 当小孩讨厌的动物被去掉并且喜欢的动物没有被去掉时, 他是开心的 问最多让多少小孩开心 思路: 让有矛盾的小孩建边,求最大独立集即可 /* ***************************

  • avatar 寒江陪烟火🔥 2016-05-17 16:46:00

    POJ2594 Treasure Exploration(最小路径覆盖+传递闭包)

    题意: 派机器人去火星寻宝,给出一个无环的有向图,机器人可以降落在任何一个点上, 再沿着路去其他点探索,我们的任务是计算至少派多少机器人就可以访问到所有的点。。 思路: 最小路径覆盖,只是点可以重复去,就需要求传递闭包,用floyd   /* *******************

  • avatar 寒江陪烟火🔥 2016-05-17 11:55:00

    HDU1151 Air Raid(有向图最小路径覆盖)

    题意: N个点M条边的有向图 意思就是问最小覆盖 思路: 有向图建单向边,然后匈牙利求最大匹配数 用N-最大匹配就可以了 /* *********************************************** Author :devil Created

  • avatar 寒江陪烟火🔥 2016-05-17 11:46:00

    HDU1054 Strategic Game(二分匹配)

    题意: 给你一个图,然后每个点被覆盖的时候,相邻的点也会被覆盖 求最小的数量使所有点被覆盖 思路: 学树形dp的时候做过这道题了,绝对比二分图快。。 现在刷二分图,n=1500,用匈牙利和HK算了下 先上匈牙利。。624ms /* ************************

  • avatar 寒江陪烟火🔥 2016-05-17 11:26:00

    POJ3020 Antenna Placement(最小边覆盖)

    题意: 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。 问至少放置多少个基站才能使得所有的城市都覆盖无线? 思路: 给每个城市编号,建双向边,跑匈牙利,然后城市数量-匹配数/2就是答案 因为假设每个城市都要建基站,然后有多少个匹配

  • avatar 寒江陪烟火🔥 2016-05-16 22:11:00

    hihocoder1059 String Matching Content Length(带长度条件的最长公共子序列)

    给定只包含字母的两个字符串A,B,求A,B两个字符串的最长公共子序列,要求构成子序列的子串长度都必须大于等于3。比如"abcdefghijklmn"和"ababceghjklmn",其最长满足题意要求的子序列为"abcjklmn",其由公共

  • avatar 寒江陪烟火🔥 2016-05-14 17:24:00

    SDUTOJ2880 Devour Magic(线段树两重延迟标记)

    题意: 每个点能量每秒加1 按时间顺序给你N组时间+区间 表示在时间t时取走区间内的能量 问取走了多少能量 思路: 区间修改区间查询 加能量数延迟一下 去走后延迟一下 用两个flag保存延迟状态 /* ************************************

  • avatar 寒江陪烟火🔥 2016-05-14 17:20:00

    SDUTOJ2879 Colorful Cupcakes(dp)

    山东省赛的一道题 题意: 聚会一个圆桌,相邻字母不能重复,有ABC三种字母 问有多少种方法 思路: dp 第一维滚动,第二维ABC当前位置,后三维存ABC用的个数 由于放在了UPCOJ上,判题比较慢,优化了一下, 在SDUTIJ上20ms /* ***************

  • avatar 寒江陪烟火🔥 2016-05-12 14:48:00

    HDU4185 Oil Skimming(匈牙利)

    题意: n*n的图 相邻两##可除去 问最多除去多少 奇偶建图,OK /* *********************************************** //Author :devil //Created Time :2016/5/12 14:48:

  • avatar 寒江陪烟火🔥 2016-05-10 23:13:00

    HDU2389 Rain on your Parade(HK模版)

    题意: 在一个二维坐标系上有n个人和m把伞,每个人都有自己的移动速度, 问有多少人可以在s min内移动到不同的雨伞处(不允许两个人共用一把伞)。 思路: 由于nm太大(3000),匈牙利会超时,就用HK算法 整理了HK的模版 /* ************************

  • avatar 寒江陪烟火🔥 2016-05-10 21:49:00

    HDU2819 Swap(二分匹配+输出结果)

    题意: 给一个n*n的01矩阵,问能否通过行列交换使得 主对角线上的数都为1 如果能输出交换的过程,如果不能输出-1 思路: 线性代数学过,行列交换都不改变矩阵的秩 三秩相等 如果能改变成主对角线上的数都为1 则原矩阵必为满秩 /* *********************