• avatar just_sort 2017-03-20 20:24:17

    URAL 1995 Illegal spices 贪心构造

    题目链接:这里 题意: 有n个物品,然后有k个东西留了下来 如果x/(i-1) //URAL 1995 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; int n, k, p, a[ma

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 20:03:37

    Educational Codeforces Round 12 C. Simple Strings 贪心

    题目链接:这里 题意:现在给你一个串,让你使得相邻的字符都不一样,要求修改的字符最少。问你最后的字符串长什么样? 解法:贪心,能变就变。。。 //CF 655C #include <bits/stdc++.h> using namespace std; char s[200010

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 19:52:46

    Codeforces Beta Round #11 A. Increasing Sequence 贪心

    题目链接:这里 题意:你每次操作可以使得一个数增加d,问你最小操作多少次,可以使得这个序列变成一个递增序列 解法:直接贪心,能变就变。。。 //CF 11A #include <bits/stdc++.h> using namespace std; int a[2010]; in

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 19:38:09

    Codeforces Round #228 (Div. 1) A. Fox and Box Accumulation 贪心

    题目链接:这里 题意:有n个箱子,现在对于每一个箱子告诉你这个箱子的上面最多放多少个箱子。现在你需要使得箱子的列数最小,请问是多少? 解法:从小到大排序之后直接贪心。 //CF 388A #include <bits/stdc++.h> using namespace std;

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 17:30:29

    Codeforces Round #353 (Div. 2) E. Trains and Statistic dp 贪心,DP,线段树

    题目链接:这里 题意:你可以从第i个城市买的从i到[i+1,a[i]]的车票,现在Pij表示从i到j的最小车票花费。现在让你求sigma p[i][j]。 解法:CF题解。 首先我们理解一下为什么是取这个m,显然出题人的意思是dp[i]是要从这个a[m]最大上面去继承答案。我们简单画一下图

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 16:10:03

    Codeforces Beta Round #37 B. Computer Game 暴力 贪心

    题目链接:这里 题意:有一个boss有hp点血,然后每秒钟回复reg。现在你有n个魔法,每个魔法只能在BOSS的血量大于p[i]%的时候使用,会给boss挂上一个每秒钟掉d[i]的buff。现在问你你怎么使用这个魔法,才能让boss死的最快。 解法:贪心,每一秒钟使用最厉害的技能就好了…… 然后

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 14:57:49

    2016多校5 hdu 5783 Divide the Sequence 贪心

    题目链接:这里 题意:说的是,给你n个数,让你分成最多的块,使得每一块的任何前缀,都是大于0的。问你最多分成多少块? 解法:把长度为n的序列分成尽量多的连续段,使得每一段的每个前缀和都不小于0。保证有解。 从后往前贪心分段即可。 //HDU 5783 #include <bits/st

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 14:44:26

    HDU 5821 Ball (贪心排序) -2016杭电多校联合第8场

    题目链接:这里 题意:T组数据,每组给定一个n一个m,在给定两个长度为n的数组a和b,再给定m次操作,每次给定l和r,每次可以把[l,r]的数进行任意调换位置,问能否在转换后使得a数组变成b数组。 解法:贪心,用结构体存储a数组,一共两个域,一个是值,一个是下标,这个下标指的是他最后应该在的位置

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 15:23:22

    HDU 5744 Keep On Movin 贪心,找规律

    题目链接:这里 题意:有n个字符,每个字符ai个,你需要构造一些字符串,使得这些字符串都是回文串,而且这些回文串恰好用完所有字符而且最短的回文串最长,输出这个长度。 解法:贪心去构造,考虑奇数的字符,我们可以拆成偶数+1,那么显然我们知道,奇数的就一定是单独的一行,然后偶数一定要成对的扔进去。

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 14:30:59

    HDU 5835 Danganronpa 贪心

    题意:这里 题意:有n类礼物,每个礼物有a[i]个,然后你要分发给尽量多的小朋友,使得每个小朋友都有一个神秘礼物和普通礼物,要求相邻的小朋友的普通礼物都不相同。 解法:大神题解 //HDU 5835 #include <bits/stdc++.h> using namespace

    来自 just_sort
    00
  • avatar just_sort 2017-03-20 13:58:25

    2013-2014 ACM-ICPC, NEERC, Southern Subregional Contest Problem B. Travelling Camera Problem set贪心

    题目链接:这里 题意:给你摄像头的坐标,给你人依次所在的位置,你摄像头能够照到这个人的条件是,你们俩的坐标距离相差小于等于k 问你摄像头最少走多少米 解法:对于每个人,可以划分出一个区间来,然后贪心的走最少的路程到达这个区间就好了。 //CF gym100253 #include <

    来自 just_sort
    00
  • avatar just_sort 2017-03-19 21:27:30

    AIM Tech Round 3 (Div. 1) A. Letters Cyclic Shift 贪心

    题目链接:这里 题意:你可以调整一个子串,使得这个子串的所有字符都往前减小一个字典序,问你能够得到的最小字典序的字符串是哪个? 解法:贪心,从前往后,能变就变。特判掉全是a的情况就好了。 //CF 708A #include <bits/stdc++.h> using names

    来自 just_sort
    00
  • avatar just_sort 2017-03-19 21:19:38

    Codeforces Round #374 (Div. 2) B. Passwords 贪心

    题目链接:这里 题意:有n个字符串,这个人从短的密码开始输入,如果密码长度相同,那就随便输出其中一个。每当他输错k次的时候,就会暂停五秒。问你最好情况下,他需要多少秒输对密码,最差情况呢? 解法:水题, 排序后贪心。 //CF 721B #include <bits/stdc++.h&

    来自 just_sort
    00
  • avatar just_sort 2017-03-19 21:07:06

    Codeforces Round #374 (Div. 2) D. Maxim and Array 贪心

    题目链接:这里 题意:给你n个数,你可以操作k次,每次使得一个数增加x或者减小x,你要使得最后所有数的乘积最小,问你最后这个序列长什么样子。 解法:贪心,根据符号的不同,每次贪心的使得一个绝对值最小的数减去x或者加上x就好了,这个贪心比较显然。假设当前乘积为ANS,那么你改变a[i]的大小的话,

    来自 just_sort
    00
  • avatar just_sort 2017-03-19 20:42:34

    Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) D. Generating Sets 贪心

    题目地址:这里 题意:一个数x,可以变成2x,或者变成2x+1,可以变化若干次。现在给你n个不同的数Y,你需要找到n个不同的x,使得这n个不同的x经过变化之后,能够得到Y数组,你要使得最初的最大值最小。问你应该怎么做。 解法:贪心,每次选择最大的数,然后使得最大数变小即可,能变就变,用一个set

    来自 just_sort
    00
  • avatar just_sort 2017-03-19 17:11:45

    2017信息ACM英雄定级赛(同步赛) 题解

    A:寻找爱吃饭的你。 水题,按照题意,用map映射一下,然后遍历找最大值即可。 #include <bits/stdc++.h> using namespace std; map <string, long long> mp; int main(){ //fre

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 21:55:10

    Codeforces Round #375 (Div. 2) C. Polycarp at the Radio 贪心

    题目地址:这里 题意:有一个歌单,歌单上面有n首歌,你喜欢1,2,3….m号乐队唱的歌。你希望改变这个歌单,使得你喜欢的乐队们唱歌唱得最少的尽量大。问你最少修改多少次,且输出方案。 解法: 显然是每个乐队演唱n/m首歌,然后我们就维护一下这个就好了。贪心的for两次。 //CF 723C #

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 21:21:40

    CDOJ 1402 三角形棋盘上的博弈游戏 状压DP

    题目链接:这里 柱爷有天上课无聊,于是和同桌卿学姐一起下一种奇特的棋: 棋盘如图: title 在开始游戏前,棋盘上已经放好了一些边,然后柱爷先手,开始在棋盘上没有边的位置添加一条边上去 如果添加边后围成一个三角形则获得一分(对于棋盘上游戏开始前已经围好了的三角形,两个人都不得分)并且下一

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 20:04:02

    Educational Codeforces Round 13 E. Another Sith Tournament 状压dp

    题目地址:这里 题意:有n(n≤18)个人打擂台赛,编号从1到n,主角是1号。一开始主角先选一个擂主,和一个打擂的人。两个人之中胜的人留下来当擂主等主角决定下一个人打擂,败的人退出比赛,直到比赛只剩一个人。已知任意两人之间决胜的胜率Pij,求主角最终能够获胜的概率。 解法:设d(S,i)表示存活

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 19:18:02

    Codeforces Round #358 (Div. 2) D. Alyona and Strings dp

    题目链接:这里 题意:给你两个串,s和t,现在要你在s中找k个不相交的子串,然后在t中这k个都出现,而且顺序和在s中一致,让你最大化长度和 解法:DP。dp[i][j][k][0]表示s中第i个等于t中第j个,一共匹配了k段后,且继续往下延续,这时候的总长度为多少。dp[i][j][k][1]表

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 11:38:00

    Codeforces Round #360 (Div. 2) E. The Values You Can Make dp ,滚动数组

    题目地址:这里 题意:所有能组成K的C的子集方案中,能拼出哪些面额 解法:DP。n^3dpdp[i][j][k]表示用到了第i个数,当前和为j,子集和为k可不可行 裸的会稍微卡一下空间,这个滚动数组优化,或者直接用bool就可以了。我滚动数组优化的。 //CF 688E #include

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 11:05:35

    【BZOJ3875】【Ahoi2014】骑士游戏 SPFA处理有后效性动规

    Description 【故事背景】 长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会 扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。 【问题描述】 在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻 击。两种攻击方式都会消耗JYY一些体

    来自 just_sort
    00
  • avatar just_sort 2017-03-18 10:14:38

    hdu 5763 Another Meaning kmp+dp

    题目链接:这里 题意: 给你一个字符串A,给你一个字符串B。 说B这个字符串有两个意思,请问字符串A一共有多少个意思 解法: DP,dp[i]表示以i结尾有多少种意思,然后用kmp去转移就好了。首先dp[i] = dp[i-1] 当i点是匹配点是, dp[i] += dp[i-len2]。

    来自 just_sort
    00
  • avatar just_sort 2017-03-17 21:33:24

    HDU 5773 The All-purpose Zero DP,贪心,LIS

    题目地址:点我 题意:给你一个序列,找出最大上升子序列的长度,其中序列中的0可以变为任意整数(正负都可以)。 解法:无疑LIS,将所有的0全部提取出来,求出此时序列的LIS(不含0的),这是针对0在子序列的外面的情况,如0,1,2,3,0.那么如果0在子序列中间怎么办?很简单,把读入的非0的数的

    来自 just_sort
    00
  • avatar just_sort 2017-03-17 15:39:24

    HDU 5781 ATM Mechine dp

    题目链接:这里 题意: 你在银行里面存了不超过k元的钱,然后你可以取钱。 如果你取的钱超过了你在银行存的钱,那么你会被警告。 你最多被警告w次,问你采用最优策略之后,期望取完所有钱的次数是多少 解法: E(i,j):存款的范围是[0,i],还可以被警告j次的期望值。 E(i,j) =

    来自 just_sort
    00
  • avatar just_sort 2017-03-17 15:12:05

    hdu 5791 Two dp

    题目链接:这里 题意:给你两个数组,问你公共子序列的数量是多少 解法:dp[i][j]表示第一个串考虑到i位,第二个串考虑到j位的答案是多少 那么dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] 如果a[i]=b[j],dp[i][j]+=dp[i-

    来自 just_sort
    00
  • avatar just_sort 2017-03-17 14:50:22

    UVALive 6908 Electric Bike dp,BFS

    题目链接:这里 题意:给了n段路,每段路长度不同,你有一辆车最多可以提供E的能量,你的车有四个档,最多换k次档 Assist Level 0 1 2 3 Assist Power 0 4 8 11 0档花费能量0,走的路程长度为0,1档花费1能量,走得最大路程为4…. ,每段路用一个档,如果

    来自 just_sort
    00
  • avatar just_sort 2017-03-16 16:56:15

    UVALive 6912 Prime Switch 状压DP,贪心

    题目链接:这里 题意:你有n盏灯,有m个开关,开关上面都写着一个质数。那么这个开关就控制着上面写着的数字的倍数。灯泡按奇数次就亮着,偶数次,就熄灭。问你最好情况下,最优有多少个灯亮着。 解法:对于小于等于31的素数,我们状压去跑dp,对于大于的,我们就贪心。因为大于31的素数一定是不会冲突的,因

    来自 just_sort
    00
  • avatar just_sort 2017-03-16 15:03:27

    UVALive 6913 I Want That Cake 博弈dp

    题目链接:这里 Description There was an interesting game played on a popular Korean reality TV Show. 12 players in 3 teams — 4 persons in each team — line

    来自 just_sort
    00
  • avatar just_sort 2017-03-16 11:55:39

    Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess DP

    题目链接:这里 题意:一个n*m的图,让你从左上角走到右下角,有一些点不能经过,问你有多少种方法 解法:令dp[i]表示从原点不经过任何坏点到第i个点的方案数 dp[i]=C(xi,xi+yi)−sigma(dp[j]∗C(xi−xj,xi−xj+yi−yj))

    来自 just_sort
    00
  • avatar just_sort 2017-03-16 11:07:12

    Codeforces Round #375 (Div. 2) D. Lakes in Berland 贪心

    题目链接:这里 题意:给你一个n*m的矩阵,然后你们有不少于k条河流,然后你需要使得一些河流变成陆地,使得河流的数量恰好等于k,问你至少填多少个水。河流的定义是水塘,且不与外界相连的地方。 解法:直接dfs搜出每一条河流,然后贪心排序,从小到大去填满就好了。 //CF 723D #inclu

    来自 just_sort
    00
  • avatar just_sort 2017-03-15 15:55:26

    Codeforces Round #382 (Div. 2)B. Urbanization 贪心

    题目链接:这里 题意:一共有n个数,第i个数是a[i],现在你需要选出n1个数和n2个数,使得那n1个数的和除以n1加上n2个数的和除以n2的值最大。 解法:贪心,如果n1>n2,那么交换。然后选择最大的n1个数为n1集合,然后次大的n2个数为n2集合。 代码: //CF 735B

    来自 just_sort
    00
  • avatar just_sort 2017-03-15 10:54:50

    Codeforces Round #394 (Div. 2) D. Dasha and Very Difficult Problem 贪心,二分

    题目链接:这里 题意:c[i]=b[i]-a[i],现在给你a[i]和c[i]的相对大小,问你可不可能出现b[i]满足条件,如果有的话,输出。 解法:贪心,最小的显然要最小,次小的在比最小大的基础上最小就好了。对于每一个数都二分一下就完了。 二分的时候把l打成了1,死活WA19。。。 //C

    来自 just_sort
    00
  • avatar just_sort 2017-03-15 10:08:43

    Codeforces Round #396 (Div. 2) B. Mahmoud and a Triangle 贪心

    题目链接:这里 题意 : 问你能否从n个数字中抽出来三个,使得可以构成不退化的三角形。 解法 : 只要排个序,然后判断a[i],a[i-1],a[i+1]能否组成三角形就好了,这样贪心肯定是对的。考虑排序之后a,b,c,d,如果a,b,c不能构成三角形,那么a,b,d肯定更不能构成三角形。 /

    来自 just_sort
    00
  • avatar just_sort 2017-03-15 09:55:06

    Codeforces Round #272 (Div. 2) B. Dreamoon and WiFi dp,组合数学

    题链:这里 题意: 给你一个串s1,和一个串s2 然后s2中有一些问号,有0.5的概率是向左边,有0.5的概率是向右边走。 问你s2结束之后,恰好走到s1串走到的目的地的概率是多少。 解法: 一种是直接用组合数来计算,一种是概率DP,dp[i][j]表示考虑到执行第二个串的第i位现在在j

    来自 just_sort
    00
  • avatar just_sort 2017-03-14 21:43:03

    Codeforces Round #272 (Div. 2) E. Dreamoon and Strings 动态规划

    题目链接:这里 题意:给你一个串S,和另外一个串P。把k从0到|S|枚举,然后问你去掉k个字符后,s串里面最多有多少个不重叠的p字符串 解法:还以为是什么kmp之类的。看了题解才知道可以dp做。dp[i][j]表示考虑到第i个位置,去掉了j个字符的最大值。然后我们对于每一个位置,先暴力找到最少去

    来自 just_sort
    00
  • avatar just_sort 2017-03-14 20:00:04

    BZOJ 3400: [Usaco2009 Mar]Cow Frisbee Team 奶牛沙盘队 动态规划

    题目链接:这里 Description 农夫顿因开始玩飞盘之后,约翰也打算让奶牛们享受飞盘的乐趣.他要组建一只奶牛飞盘 队.他的N(1≤N≤2000)只奶牛,每只部有一个飞盘水准指数Ri(1≤Ri≤100000).约翰要选出1只或多于1只奶牛来参加他的飞盘队.由于约翰的幸运数字是F(1≤F≤1

    来自 just_sort
    00
  • avatar just_sort 2017-03-14 19:32:23

    Codeforces Round #369 (Div. 2) C. Coloring Trees 动态规划

    题目链接:这里 题意:给你n棵树,如果ci为0的话,那么这棵树就没有上色,否则这棵树就是ci颜色的。 相同颜色的树会被当成一段,现在你要恰好刷漆刷成k段,问你最小花费是多少。 把第i棵树刷漆刷成j颜色的花费为p[i][j]。 解法: dp[i][j][k]表示第i棵树,刷成了j颜色,当前有k

    来自 just_sort
    00
  • avatar just_sort 2017-03-14 17:49:29

    Codeforces Beta Round #14 (Div. 2) D. Two Paths 树形dp

    题目链接:这里 题意:给你一棵树,让你选择两条不相交的路径,使得长度的乘积最大。 解法:枚举删除哪条边,然后再跑树形dp就好了。(维护最长和次长就可以了) //CF 14D #include <bits/stdc++.h> using namespace std; const i

    来自 just_sort
    00
  • avatar just_sort 2017-03-13 18:35:51

    HDU 5900 QSC and Master 区间DP

    题目链接:这里 Problem Description Every school has some legends, Northeastern University is the same. Enter from the north gate of Northeastern Universit

    来自 just_sort
    00
  • avatar just_sort 2017-03-13 13:50:06

    HDU 5907 Find Q dp

    题目链接:这里 题意:问你有多少个子串,全部只含有q这个字母。 解法:直接dp就好了,dp[i]表示以i结尾的方案数,最后对dp累加求和就是答案。 //HDU 5907 #include <bits/stdc++.h> using namespace std; const int

    来自 just_sort
    00
  • avatar just_sort 2017-03-13 13:35:15

    Xtreme8.0 - Play with GCD dp,离散化 求一个序列里面gcd值等于x的集合个数

    题目链接:这里 题意:给你n个数,问你里面有多少个集合的gcd为x。最多有10000个不同的数。 解法:dp[i]代表有多少个集合的gcd为i,我们直接DP的话,复杂度高达10000*100000 显然T的对吧。但是发现题目里面给的数字最多10000个不同的数,所以我们先离散化之后再DP,复杂度

    来自 just_sort
    00
  • avatar just_sort 2017-03-13 13:04:48

    Xtreme9.0 - Car Spark 动态规划

    题目链接:这里 题意:给你n个区间,每个区间有权值,然后让你选择不相交的区间,使得权值和最大。 解法:照右端点排序之后,然后跑dp。这道题数据范围很小,所以直接暴力跑就行了。数据范围大了之后,我们随便找一个维护区间最值的数据结构来优化转移就行了。 //hackerrank Xtreme9.0

    来自 just_sort
    00
  • avatar just_sort 2017-03-12 17:26:39

    BZOJ 4300: 绝世好题 DP

    Description 给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。 Input 输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数,第i个整数表示ai。 Output 输出文件共一行。 包括

    来自 just_sort
    00
  • avatar just_sort 2017-03-12 16:53:31

    CF 735C Tennis Championship dp,Fib

    题目链接:这里 题意:一个选手只能和一个比赛次数与他的比赛次数的差的绝对值不超过一的人比赛,求冠军最多能进行多少把比赛。 解法:不要只往人数上想,可以往场数上想: 赢 1 把: 至少要 2 个人: 2把: 3个人, 3把:至少为 至少2把的人数+至少1把的人数。 4把:至少为 至少3把的

    来自 just_sort
    00
  • avatar just_sort 2017-03-12 16:33:10

    [swust]Fighting for 2017 season contest 8 快速幂,简单DP,暴力or指针交换,树上背包,线段树区间开根

    题目地址:https://oj.splayx.com/vjudge/contest/view.action?cid=4#problem/A A:水题,一个快速幂搞定。 //tvoj 1116 #include <bits/stdc++.h> using namespace std;

    来自 just_sort
    00
  • avatar just_sort 2017-03-12 14:09:31

    Codeforces Beta Round #17 C. Balance DP

    题目链接:这里 题意:你可以使得一个元素变成他周围的元素的颜色,可以改变无数次,现在给你一个串,问你一共有多少种方案,使得a和b和c的个数相差不超过1。 题解:dp[i][a][b][c],表示考虑到第i个位置,当前有a个a,b个b,c个c 的方案数 然后转移就好了 维护一个next[i][

    来自 just_sort
    00
  • avatar just_sort 2017-03-12 10:37:53

    Codeforces Round #384 (Div. 2)D - Chloe and pleasant prizes 树形dp

    题目链接:这里 题意 给你一棵树,让你找到其中的两个子树,使得子树和最大。 要求子树不相交。 题解 树形dp,dp[i]表示以i为根的子树里面存在的子树最大值是多少 记录最大值和次大值,俩加起来就是最大的。 //743 D #include <bits/stdc++.h>

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 20:56:03

    Codeforces Round #396 (Div. 2) C. Mahmoud and a Message 倒着DP

    题目链接:这里 Mahmoud wrote a message s of length n. He wants to send it as a birthday present to his friend Moaz who likes strings. He wrote it on a magic

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 17:21:25

    HDU 4388 Stone Game II 博弈,规律题

    题目链接:这里 题意:最初有n堆石子,每堆石子个数已知。两人轮流执行操作,如果当某人无法执行有效操作时即输。操作分两步: 第一步为:选择其中一堆石子假定石子个数为a,拿走个数不为0的一些石子使得该堆石子剩余k个并且保证(0 < k < a,k^a < a),^为异或符号。第二步为

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 16:45:18

    ZOJ 3057 Beans Game 博弈DP

    题目链接:这里 题意:三堆石头,每次从一堆中取走若干,或者从两堆中取走相同的数量 ,最后取的人胜。 解法:博弈DP,dp[i][j][k]表示三堆石头分别为i,j,k状态时候是否为必胜。 之后便是N,P态的转换,成必败态能到达的一定是必胜态。不能用记忆化搜索,常数太大,会TLE。而且还卡内存,

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 15:50:45

    POJ 3710 Christmas Game 无向图删边 经典的删边游戏 Tarjan缩点

    题目链接:这里 题意:有多棵树进行删边博弈,注意这里的”树“可能存在环,形状也许是非常诡异的。 解法:下面来自cxlove神的博客 我们利用The Fusion Principle:任何环内的节点可以融合成一点而不会改变图的sg值。(下面我们称它为融合原则) 融合原则允许我们把任意一个根图简

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 10:59:28

    POJ 1740 A New Stone Game 博弈,规律

    题目链接:这里 题意:对于n堆石子,每堆若干个,两人轮流操作,每次操作分两步,第一步从某堆中去掉至少一个,第二步(可省略)把该堆剩余石子的一部分分给其它的某些堆。最后谁无子可取即输。 解法:算规律题吧。。来自网上大神的一段分析。 首先看两堆:1 1 的状态肯定是先手输~~但是俩数不一样的话就是

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 10:26:43

    POJ 2348 欧几德里博弈,博弈好题

    题目链接:这里 题意:给两个整数a和b,两个人先后用较大的数减去较小数的整数倍,并且保证相减后不为负数。先把一个数变为0的人获胜。 解法:真心觉得博弈难,可能是自己找必胜状态找得不好,感觉是需要一些智商来刚博弈的。下面的分析来自这位同学 很显然,当大数是小数的整数倍时为必胜态。 从这道题学会

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 10:01:32

    POJ 3480 John Anti-Nim博弈变形

    题目链接:这里 题意:有若干堆石子,两个人轮流从其中一堆里面取出若干个(不能不取),若某个人取完后没有石子了,则这个人输。先手的人叫John。 解法: 先手胜当且仅当 (1)所有堆石子数都为1且游戏的SG值为0 ,(2)存在某堆石子数大于1且游戏的SG值不为0 证明: (1)若所有堆石子

    来自 just_sort
    00
  • avatar just_sort 2017-03-11 09:22:08

    CF 222D Olympiad 双指针

    题目链接:这里 题意:第一行给出两个个数字k和n,第二三行分别有k个数字,求将第二、三行之间的数字相互组合,求最多有多少个组合的和不小于n 解法:将两行数字分别排序,用双端指针分别从头和尾查找最多有多少组合。 代码: //CF 222D #include <bits/stdc++.h

    来自 just_sort
    00
  • avatar just_sort 2017-03-10 20:43:58

    CF 493C 二分

    题目链接:这里 题意:两个人比赛篮球投篮,与正常的篮球比赛不同的是,三分线与篮筐的距离d是不确定的。输入第一个人投了n个球,n个球每个球投的时候他与篮筐的距离;然后输入第二个人头了m个球,m个球每个球投的时候他与篮筐的距离,然后让你选择一个d,使得它对于第一个人最为有利,所谓有利即使得“第一个人的

    来自 just_sort
    00
  • avatar just_sort 2017-03-10 19:19:54

    CF 501B Misha and Changing Handles 模拟,水题

    题目链接:这里 题意:按照时间顺序给了n对新旧字符串,其中如果满足a->b&&b->c那么最后只会存在a->c,然后让输出最后字符串对。 解法:水题,按照题意模拟就可以了,用map //CF 501B #include <bits/stdc++.h&g

    来自 just_sort
    00
  • avatar just_sort 2017-03-10 18:53:34

    HDU 5098 Smart Software Installer 双队列拓扑排序或者DAG的最长路

    题目:这里 题意:软件在安装之后需要重启才能发挥作用,现在给你一堆软件(有的需要重启有的不需要)以及安装这个软件之前需要哪些软件发挥作用,求最少的重启次数。 解法:真拓扑好题,但是我不会。然后这个题有两种解法,解法1来自斌神:普通的拓扑排序用了一个队列,而现在用两个队列q1,q2分别来存 不需要

    来自 just_sort
    00
  • avatar just_sort 2017-03-10 14:00:38

    CF 489D Unbearable Controversy of Being BFS

    题目链接:这里 题意:给了一个有向图,问有多少个点对(a, b, c, d)满足a->b->d并且a->c->d,求组成这样的菱形的个数。 解法:水题,对每个点aBFS标记,最后那些对于每个点来说标记了2次以上的肯定就是d点。 复杂度O(n*m) //CF 489D

    来自 just_sort
    00
  • avatar just_sort 2017-03-10 09:32:37

    CF 489C Given Length and Sum of Digits... 贪心

    题目链接:这里 题意:此题要求找到一对数字,长度和数字之和满足n和m的条件,求出这对数的最大区间。 解法:贪心,让第一个数的首位尽可能小,让最后一个数的首位尽可能大。只能说我开始写的代码巨丑,从test3开始wa到test9,最后推了重新构思一发过了,做题还是得想得非常清楚啊, 不然容易把自己写

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-03-05 19:28:00

    开箱即用,Springboot第一个demo

    在使用Spring之前,需要知道,SpirngBoot其实并不能称之为一个框架,而是针对spirng在整合各种技术的配置繁琐性进行统一的管理配置。Spring Boot设计的目的是让您尽可能快地启动和运行,并尽量减少前期的开销 。 使用idea开始对Springboot进行首次使用

    来自 Mr.Robot、
    00
  • avatar Mr.Robot、 2019-02-26 10:22:00

    javase(集合框架)

    1. 集合框架 为什么出现集合类? 面向对象对事物的体现都是以对象的形式,为了方便对多个对象的操作,就对对象进行存储。 集合就是存储对象最常用的一种方式。 数组和集合都是容器,两者有何不同? (1)数组长度固定,而集合长度是可变的。 (2)数组值可以存储对象,还可以存储基本数据

    来自 Mr.Robot、
    00
  • avatar just_sort 2017-03-09 16:13:33

    CF 387C 贪心

    题目链接:这里 题意:就是给处一个长度不超过10^5的十进制正整数, 是按照题目所给的方法从一个数组中拼出来的,为初始的那个数组最多有多少个元素。 解法:从末尾向开头贪心加更大字符串的字符串即可。 //CF 387C #include <bits/stdc++.h> using

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-26 10:22:00

    javase(多线程)

    1. 进程和线程 进程:正在进行的程序。每一个进程执行都有一个执行顺序,该顺序是一个执行路径,或者叫一个控制单元。 线程:是进程内部的一条执行路径或者一个控制单元。 两者的区别 (1)一个进程至少有一个线程。 (2)进程在执行过程中拥有独立的内存单元,而多个线程共享内存。

    来自 Mr.Robot、
    00
  • avatar 有赞欢迎你呀~~ 2019-11-01 22:04:21

    笨法,排序输出哈哈

    import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<I

  • avatar just_sort 2017-03-09 15:43:21

    CF 446B DZY Loves Modification 优先队列

    题目链接:这里 题意: 有一个n*m的矩阵,你需要操作k次,每次操作是选择一行或者一列,使得ans+=这一行或者这一列的和 然后再使得这一行或者这一列的数全部减去p 现在问你他操作k次之后,最多获得多少分数 解法: 假设你最后操作了k次,那么对于整体的答案,你需要减去i*(k-i)*p这

    来自 just_sort
    00
  • avatar just_sort 2017-03-09 14:01:54

    CF 490E 贪心,回溯法

    题目链接:这里 题意:一个严格递增序列 某些数字的某些位被盖住了 求 恢复后的序列。 解法:贪心,让每个数在大于前一个的基础上尽量小,先考虑数字长度。if(len[i] < len[i+1])输出NO,当len[i] > len[i-1],如果第一位是?就改成1,其他的问号改成0,接

    来自 just_sort
    00
  • avatar just_sort 2017-03-09 09:54:01

    CF 496E 贪心,排序,set

    题目链接:这里 题意:有n首曲子,每首曲子的范围为ai~bi。有m个演奏家,每个演奏家的范围为ci~di,并且可以出演次数为ki次。如果ci<= ai<=bi<=di,则说明该曲子可以由演奏家演出。问是否存在合法方案使得所有曲子都能被演奏。第一行为一个整数表示曲子的数量n,之后n

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-22 15:07:00

    freemarker的使用与应用

    什么是freemarker FreeMarker是一个用Java语言编写的模板引擎,它基于模板来生成文本输出。FreeMarker与Web容器无关,即在Web运行时,它并不知道Servlet或HTTP。它不仅可以用作表现层的实现技术,而且还可以用于生成XML,JSP或Java 等。目前企业中

    来自 Mr.Robot、
    00
  • avatar Mr.Robot、 2019-02-20 16:55:00

    消息队列ActiveMQ

    什么是ActiveMQ ActiveMQ 是Apache出品,最流行的,能力强劲的开源消息总线。ActiveMQ 是一个完全支持JMS1.1和J2EE 1.4规范的 JMS Provider实现,尽管JMS规范出台已经是很久的事情了,但是JMS在当今的J2EE应用中间仍然扮演着特殊的地位。 主要

    来自 Mr.Robot、
    10
  • avatar 是个呆雁 2019-11-01 22:05:37

    MAX“比较宏”关于++的一些改进

    转载至:https://mp.weixin.qq.com/s/0ZVNbTj7fGs8Gi03vj541A公众号:LINUX内核之旅 上述这种写法没能解决宏参数++问题 这种写法解决了首先,它的结构是这样({语句1;语句2;语句3;语句4;}),根据GCC的扩展特性,这个表达式最终的值应该是语句4的

    来自 是个呆雁
    10
  • avatar just_sort 2017-03-08 21:00:05

    HDU 3400 Line belt (三分套三分)

    题目链接:这里 题意:就是给你两条线段AB , CD ,一个人在AB以速度p跑,在CD上以q跑,在其他地方跑速度是r。问你从A到D最少的时间。 解法: 先三分AB上的点,再三分CD上的点即可。 证明: 设E在AB上,F在CD上。 令人在线段AB上花的时间为:f = AE / p,人走完Z

    来自 just_sort
    00
  • avatar 有赞欢迎你呀~~ 2019-11-01 22:05:43

    新思路:用堆来做

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) { if (k > nums.length || k <= 0) return new ArrayList<

  • avatar Mr.Robot、 2019-02-19 20:42:00

    SolrCloud服务搭建及使用solrj管理集群

    什么是SolrCloud SolrCloud(solr 云)是Solr提供的分布式搜索方案,当你需要大规模,容错,分布式索引和检索能力时使用 SolrCloud。当一个系统的索引数据量少的时候是不需要使用SolrCloud的,当索引量很大,搜索请求并发很高,这时需要使用SolrCloud来满

    来自 Mr.Robot、
    00
  • avatar Mr.Robot、 2019-02-19 16:26:00

    linux环境下的solr服务搭建及soloj的使用

    Solr服务搭建 Solr是java开发。 需要安装jdk 安装环境Linux 需要安装Tomcat 搭建步骤 第一步:把solr 的压缩包上传到Linux系统 第二步:解压solr。 第三步:安装Tomcat,解压缩即可。 第四步:把solr部署到Tomcat下。 第五步:解

    来自 Mr.Robot、
    00
  • avatar just_sort 2017-03-08 18:41:20

    UVALive 6424 Russian Dolls 贪心

    题目链接:这里 题意:每个玩具有占用的空间和内部可容纳的空间。规定每个玩具只能直接嵌套一个玩具,可以间接嵌套,即A套B,B再套C,但是不能A同时套B和C。A能套B的条件是A的内部空间严格大于B的占用空间。第i个玩具有一个单位花费ci,乘以该玩具内部还剩于的空间即为花费。要问的是经过适当的嵌套之后,

    来自 just_sort
    00
  • avatar just_sort 2017-03-08 17:28:32

    POJ 2993 Emag eht htiw Em Pleh 模拟,题意

    题目:这里 题解:2996反过来就行了。题解这里 //POJ 2993 #include <stdio.h> #include <string.h> #include <iostream> char mp[40][40]; char s1[40], s2[4

    来自 just_sort
    00
  • avatar just_sort 2017-03-08 16:56:53

    POJ 2996 模拟,读题

    题目链接:这里 题意:打印棋盘上棋子的位置。 解法: 研究一下输出: White: Ke1,Qd1,Ra1,Rh1,Bc1,Bf1,Nb1,a2,c2,d2,f2,g2,h2,a3,e4 Black: Ke8,Qd8,Ra8,Rh8,Bc8,Ng8,Nc6,a7,b7,c7,d7,e7,f

    来自 just_sort
    00
  • avatar just_sort 2017-03-08 11:31:09

    HDU 4781 Assignment For Princess 图论,构造,思维

    题目链接:这里 题意:构造一个n个点,m条有向边的图,需要满足两个要求: 1.任意一对点对之间最多有一条有向边,且没有自环。 2.保证图联通,m条边的边权严格属于[1, m]且互不相同,从任意点出发,经过任意路径后回到起始点,经过的边权总和是3的倍数。 解法:构造好题,方法 对于每个点i &

    来自 just_sort
    00
  • avatar just_sort 2017-03-08 10:51:42

    UVALive 7043 International Collegiate Routing Contest 字典树,递归

    题目链接:这里 题意:给出n个IPv4的子网地址,格式是a-b-c-d/l,a b c d l都是十进制数,然后l是网络地址的长度,最长到32,要求输出最低限度的所有的未能划分出的子网地址,这些子网和给出的n个子网没有交集,这些地址和给出的n个地址能组成完整的网络地址。 解法:把所有的ip地址*

    来自 just_sort
    00
  • avatar just_sort 2017-03-07 19:52:07

    UVALive 7040 Color 容斥,组合数递推,线形逆元,基础数论

    题目链接:这里 题意:首先有T组数据,每组数据有 3 个数 n, m, k,分别代表一共有 n 个方格,m种颜色,而我们要 恰好(注意是恰好) 使用 k 中颜色对这些方格进行涂色,并且保证的是每两个相邻的方格的颜色必须是不一样的。 解法:m种颜色选k种,所以有C(m,k),对于选出的k种颜色去给

    来自 just_sort
    00
  • avatar just_sort 2017-03-07 18:53:07

    HDU 5445 Food Problem 2次背包,二进制优化

    题目链接:见这里 题意:首先有n种点心,每种点心的t,u,v代表该点心每个所提供的能量,体积,数量。然后有m中车,每种车的x,y,z代表这种车的容量,费用,数量。又有一个p,问你所选的点心达到p的能量值的时候所需要的最少费用。(点心可以切割,即可以分开到每辆车里面,但是只要你选了一个,就整个点心都

    来自 just_sort
    00
  • avatar just_sort 2017-03-07 15:17:02

    CF 776E 欧拉函数

    题目链接:这里 题意:如题。 解法:对于f(n),若自然数对(x,y)满足 x+y=n,且gcd(x,y)=1,则这样的数对对数为f(n) 证明f(n)=phi(n) 设有命题 对任意自然数x满足x < n,gcd(x,n)=1等价于gcd(x,y)=1 成立,则该式显然成立,下面证明

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-18 12:38:00

    linux环境下Redis集群搭建

    Redis的安装 Redis是c语言开发的。 安装redis需要c语言的编译环境。如果没有gcc需要在线安装。yum install gcc-c++ 安装步骤: 第一步:redis的源码包上传到linux系统。 第二步:解压缩redis。 第三步:编译。进入redis源码目录。

    来自 Mr.Robot、
    00
  • avatar Mr.Robot、 2019-02-15 19:07:00

    利用Nginx实现反向代理和负载均衡

    什么是反向代理? 正向代理(基于客户端的代理) 正向代理 反向代理(基于服务器端的代理) 反向代理 反向代理服务器决定哪台服务器提供服务,返回代理服务器不提供服

    来自 Mr.Robot、
    00
  • avatar just_sort 2017-03-07 14:33:33

    CF 776D The Door Problem TwoSAT 模板题

    题目链接:这里 题意:有n道门,m个开关,每道门由m个开关中的两个控制,若门的状态是0(关),那么改变控制这道门的一个开关之后,门的 状态就变为1(开),若门的状态是1(开),那么改变控制这道门的一个开关之后,门的状态就变为0(关)。 现已知n道门的初始状态,以及m个开关分别控制哪些门,问能不能通

    来自 just_sort
    00
  • avatar just_sort 2017-03-07 13:55:51

    CF 776C Molly's Chemicals 前缀和,STL

    题目链接:见这里 题意:给出n个数,和一个数k,现在问你有多少个区间和等于k的x次方,x从0到无穷 解法:先求出前缀和,也就是求有多少个sum[r]-sum[l]=pow(k,x),r>l。x最大只有lg(1e14),可以将式子变为sum[r]-pow(k,x)=sum[l]。每次结束后将

    来自 just_sort
    00
  • avatar just_sort 2017-03-07 13:37:47

    CF 778B Bitwise Formula 位运算,贪心

    题目链接:这里 题意:选择一个 m 位的二进制数字,总分为 n 个算式的答案之和。问得到最低分和最高分分别应该取哪个二进制数字 解法:因为所有数字都是m位的,因为高位的权重大于地位 ,我们就从高到低考虑 ans 的每一位是取 0 还是取 1,统计该位的权重(即n个式子该位结果之和)即可。 //

    来自 just_sort
    00
  • avatar just_sort 2017-03-06 19:20:07

    CF 779D String Game 二分,贪心匹配字符串

    题目链接:见这里 题意:给了一个串A和一个串B,现在有一个排列,a[]现在你可以在A字符串按照排列删除对应位置上的字符,问你最多可以在哪个位置删除字符使得这个删除之后的字符串还有字串为B,问这个最后的位置。 解法:二分这个最后的,位置然后check就可以了。 //CF 779D #inclu

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-15 14:37:00

    Nginx的安装和使用

    什么是nginx Nginx是一款高性能的http 服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器。由俄罗斯的程序设计师Igor Sysoev所开发,官方测试nginx能够支支撑5万并发连接(tomcat貌似最高支持1000并发),并且cpu、内存等资源消耗却非常低,运行非

    来自 Mr.Robot、
    00
  • avatar Mr.Robot、 2019-02-14 15:14:00

    Mybatis-PageHelper分页插件

    数据库: 该插件目前支持Oracle,Mysql,MariaDB,SQLite,Hsqldb,PostgreSQL六种数据库分页。 第一步:把PageHelper依赖的jar包添加到工程中 <dependency> <groupId>c

    来自 Mr.Robot、
    00
  • avatar just_sort 2017-03-06 17:52:47

    CF 779 C Dishonest Sellers 贪心,排序

    题目链接:见这里 题意:给了一些物品,每个物品有俩个价格,一个是打折前的,一个是打折后的(打折发生在一周后),现在一个人必须先买k个物品,然后剩下的物品既可以选择现在买,也可以选择一周后买,其中打折后的价格不一定比现有价格低,无良商人,大家都懂。 解法:我们先考虑一下必须买的k个物品,肯定要优先

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-13 23:58:00

    Dubbo+ZooKeeper实现分布式服务搭建

    架构的分析 基于soa的架构,表现层和服务层是不同的工程。所以要实现商品列表查询需要两个系统之间进行通信。 如何实现远程通信? 1.Webservice:效率不高基于soap协议。项目中不推荐使用(跨语言跨平台性好,一般用于两个公司之间的业务模块通信)。 2.使用restful

    来自 Mr.Robot、
    00
  • avatar just_sort 2017-03-06 17:24:04

    CF 779B Weird Rounding 贪心

    题目链接:见这里 题意:给一个数,和一个k,要你删除数里面的某些数字使得这个数能被k整除,求最少删除多少个数? 解法:贪心,注意到要被k整除,那么这个数最后至少有k个0,所以我们从后往前删,删到k个0的时候停下来,这个时候就可以得到答案了。 //CF 779B #include <bit

    来自 just_sort
    00
  • avatar just_sort 2017-03-06 16:50:43

    CF 779A Pupils Redistribution 模拟,水题

    题目链接:见这里 题意:给了两个数组a, b。现在你可以交换a,b数组的任意两个数,问最少交换多少次,可以让a,b数组里面每个数的出现次数相同,不能达到上述状态输出”-1”。其中a,b数组里面每个数是1-5. 解法:模拟,想想就可以知道如果对于1-5这每个数,如果出现次数之和为奇数那么肯定不能达

    来自 just_sort
    00
  • avatar just_sort 2017-03-06 16:02:02

    CF 782D. Innokenty and a Football League 贪心,思维,模拟

    题目链接:见这里 题意:每个队名有两种选择,然后第一个选择队名相同的那些队只能选第二种,让你安排队名,使得最后每个队名都不一样。 分析: 首先全都选成第一种队名,然后第一种队名相同的队,它们只能全都变成选第二种队名的了,这个时候如果第一种队名相同的那些队里面,变成第二种队名后有重复的,直接输出无

    来自 just_sort
    00
  • avatar just_sort 2017-03-06 14:55:27

    CF 782C 贪心,DFS染色,水题

    题目链接:见这里 题意:给了一颗树,要让每个连起来的(u, v, w)三个点的颜色不同,默认1点被染成颜色1,问最少多少种颜色可以完成,并输出每个点的颜色编号。 解法:贪心+DFS,直接记录一下,这个点的父亲的颜色,和这个点的父亲的父亲的颜色,只要颜色颜色和它们不同就可以用这个颜色更新当前这个点

    来自 just_sort
    00
  • avatar Mr.Robot、 2019-02-11 20:56:00

    计算机网络知识面试题(干货)

    计算机网络的常见问题 OSI七层模型: OSI分层 (7层):物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。 TCP/IP分层(4层):网络接口层、 网际层、运输层、 应用层。 五层协议 (5层):物理层、数据链

    来自 Mr.Robot、
    02
  • avatar just_sort 2017-03-06 14:06:28

    CF 782 B CoB. The Meeting Place Cannot Be Change 3分求极值

    题目链接:见这里 题意:开始每个人都在一条数轴上的某个位置上,位置大于等于1都是整数,每个人有个最大移动速度,为在数轴上面哪个点集合,所用的集合时间最短,求这个时间,集合地点可以不是整数。 解法:3分位置然后求极值。check就是对于每个位置,每个人以最大速度跑到的时间的最大值 #includ

    来自 just_sort
    00