- 博客(128)
- 收藏
- 关注
RSS订阅
转载 kuangbin-poj题目归类
初期: 一.基本算法: (1)枚举. (poj1753!,~~poj2965~~) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:
2017-09-14 15:20:43
831
原创 java报错 Property 'xxx' not found on type 包名.类名
在使用EL表达式的时候疯狂报错。查了好久之后有博客说命名规则的问题，原来我的变量命名是Bname这样，后来全部改成小写bname然后改一改getter和setter问题就解决了。...
2018-10-14 15:13:50
5594
2
原创 2018蓝桥杯决赛赛后总结（游记）
省赛时候水到了一个省一，然后我们学校的决赛地点在北大，所以就可以愉快的去北京(旅游)参加比赛了。坐高铁到北京南站，然后换乘地铁去北大附近，排队买票的人贼多，然后被强制安装注册了zfb。。。。。到了旅馆才发现我们住的地方就在北大南门几十米，第二天可以不用太早去了很棒。下楼随便吃了点东西（羊肉汤真难喝，初步体会到了帝都的物价），然后就愉快的出发前往颐和园，在高铁上睡着了起来头疼，之前生病还没痊愈，...
2018-05-30 12:27:45
1616
4
原创 AtCoder - 2334（搜索）
MenagerieTime limit : 2sec / Memory limit : 256MBScore : 500 points Problem StatementSnuke, who loves animals, built a zoo.There are N animals in this zoo. They are conveniently numbered 1 th...
2018-05-22 18:46:57
564
原创 “浪潮杯”山东省第九届ACM大学生程序设计竞赛 G Games（DP）
Problem DescriptionAlice and Bob are playing a stone game. There are nnn piles of stones. In each turn, a player can remove some stones from a pile (the number must be positive and not greater than ...
2018-05-19 20:50:04
402
2
原创 “浪潮杯”山东省第九届ACM大学生程序设计竞赛 F Four-tuples (容斥原理)
题目链接比赛时推了好久的容斥，结果推错了，过了样例就交了，然后A了。后来才知道这题有bug。菜啊。题意：给定四个区间(li,ri)(li,ri)(l_i,r_i)（闭区间）,求一个四元组(x1,x2,x3,x4)(x1,x2,x3,x4)(x_1,x_2,x_3,x_4)，满足xixix_i在区间(li,ri)(li,ri)(l_i,r_i)内，且任意两个相邻的xixix_i不能相等。...
2018-05-14 19:53:56
968
原创 玲珑学院1087
题目链接题意：有一颗高度为k的满二叉树，每个节点上都有一堆石子，对于一个节点，你可以将其中的石子挪到左子节点或者右子节点，如果它是叶子节点，就拿走。问先手有多少种必胜策略。 题解：类似阶梯博弈，奇数层次的石子数异或和不为0时先手必胜。对于奇数层次的某个节点，一定可以使总异或和成为0（变成必败态），如果不是叶子节点，就可以拿石子给左右子节点。 偶数层次的某个节点，如果sg^左子节点的大小在（...
2018-05-01 14:21:02
137
原创 UVALive - 5059 （SG打表）
题意：n堆石子，一次最多拿这堆石子的一半，当石子只有1的时候不能操作，问先手是否必胜。题解：SG打表找规律，这里主要MARK一下这种思想。 规律：石子数为偶数时候SG值为n/2，奇数时为SG（n/2）#include<cstdio>using namespace std;long long sg(long long x){ if(x % 2 == 0) ...
2018-04-30 21:26:26
189
原创 Codeforces934C (区间DP)
题目链接题意：给定一组由1和2组成的数字串，你可以选定一个区间[l,r]，然后将其翻转，然后使翻转后的数字串最长不下降子序列最长，输出最长不下降子序列的长度。题解： dp[i][j][k],表示i~j区间内，k为0时代表以2结尾的最长不上升子序列（也就是2的个数） k为1时表示以1结尾的最长不上升子序列。 dp[i][j][0] = dp[i][j - 1][0] + (num[j]...
2018-04-30 19:37:55
234
原创 第十四届华中科技大学程序设计竞赛 K.Walking in the Forest（二分）
题目链接 题意：给定n个点，要求从第一个点经过k步到达第n个点。一次可以跨过任意多个点，求最小的最大步是多少。题解:最小化最大值问题，二分。 一开始看见这个题知道是最小化最大值问题知道是二分但是没思路，然后想DP试一试，GG之后写二分写了一年。。。。#include<cstdio>#include<algorithm>#include<cstring&...
2018-04-29 19:40:27
139
原创 牛客练习赛16 B 漂亮的树
题目链接本来想签到抽奖，但是这个题没做出来，总感觉有思路。看了题解果然还是我想多了。题意：给定一个数字串，将这个串前半段变成递增后半段递减，而且要求是回文串，问最少需要改动多少个数字。题解： 常规思路枚举a1=ka1=ka_1 = k,然后后面依次是a1+ia1+ia_1 + i，但是枚举会超时。 那么对于每一个位置的ai−iai−ia_i - i是固定的的，将这些数记录下来，出现...
2018-04-29 19:17:54
174
原创 HDU2476（区间DP）
题目 话说，这区间DP怎么能这么毁天灭地的难啊。 （达成成就，被爆锤X6） 题意： 给定两个字符串A,B，要把A串变成B串，你可以选择任意一个区间，然后将这个区间之内的字符全部变成某一个你想要的字符。题解： 先不用考虑如何从字符串A变成B，直接计算由空串制作一个字符串B需要多少花费，然后再考虑将A转变。 先考虑由空串制作字符串B dp[i][j]代表使区间i~j成为B串i~j的最...
2018-04-26 20:55:01
307
原创 HDU4283(区间DP)
题目链接DP这东西还是一如既往的毁天灭地的难啊。题意：有n个人参加非诚勿扰，每个人都有ninin_i的屌丝值，如果前面有k个人比他早，他就会有（k−1）∗（ni）（k−1）∗（ni）（k-1）*（n_i）的屌丝值，你可以让一些人进入一个小黑屋，来改变上场顺序，但是小黑屋是类似栈，先入后出。题解： dp[i][j]表示i~j区间的最优解。 对于i~j区间来说，第i个人可以第一个上，也...
2018-04-25 20:06:00
349
原创 ZOJ3469(区间DP)
DP的题。。。。还是一如既往的难到毁天灭地啊。。。（大佬们纷纷表示简单DP而已。） 上篇博客才写了感觉区间dp有套路，分分钟又被爆锤。 那么问题来了，什么时候才能看到曙光呢。题意：在一条坐标轴上，位于x位置有一家餐馆，有n个人订餐，要给他们送饭，收不到饭很不开心，每分钟会增加NiNiN_i的不开心值。一直每个人的位置和快递员的速度，求最少的不开心值。题解：先不用考虑快递员的速度问题，因...
2018-04-24 21:17:09
435
原创 POJ1651(区间DP)
好像区间DP都是枚举起点终点然后找一个中间状态进行一种类似松弛一样的更新？？？ 题目链接 题意：给定一组数字，从中任选除了首尾之外的数字，每次拿数字的花费为这个数这个数之前的数这个数之后的数，求总花费最小。题解： 区间DP dp[i][j]从i到j的最优解。 比较容易想到通过求解小区间最优解得到最后总区间的最优解。 很明显当l == r - 1时候DP值为0 当l == r - ...
2018-04-24 18:37:58
606
2
原创 LightOJ1422（区间DP）
题意：一个人要去参加舞会，对于第i个舞会他要穿第ni件衣服，他可以穿很多件衣服，一件套一件（厉害啊），但是如果这件衣服已经穿在身上了并且外面还有别的衣服，就要把外面的脱掉。问最少穿多少次衣服。 题解：dp[i][j]表示从第i个到第j个的舞会最少穿衣服的次数。 考虑第i个舞会要穿的衣服。如果i~j中没有和第i件相同的衣服，那么dp[i][j] = dp[i + 1][j] + 1 如果i~j...
2018-04-23 20:05:22
156
原创 2018 ACM-ICPC 中国大学生程序设计竞赛线上赛 B(素数筛 + MR)
题意：给你一个合数，将其分解为两个质数，合数<2^63题解：素数筛打表打到1e6，然后对每一个素数用MR判断n-这个素数是不是素数，如果是输出就好了。 （暴力大法好） 但是，所给的合数太大了，MR中很容易爆，所以要用unsigned longlong，输入输出用%llu。 一下午疯狂T，以为MR太慢。 （牛* 牛 *，本垃圾这厢有礼了。）#include<cstdio&...
2018-04-22 21:26:57
189
原创 CodeForces - 484B（二分）
题意：给定一些数字，求在ai>ajai>aja_i > a_j情况下，aiaia_i % ajaja_j的最大值。题解：先将数字排序，然后枚举每个数的k倍，k>1且k∗当前数字小于最大值k>1且k∗当前数字小于最大值k>1 且 k * 当前数字小于最大值，然后二分搜索小于k倍当前数字的最大值，然后记录最大值输出就好了。 不过我的二分在边界判断时候出错了，我写的l#...
2018-04-22 20:27:55
159
原创 CodeForces - 645C（最大化最小值问题 二分）
题意：农夫带着他的牛们离家出走了（为什么农夫一定要和牛联系在一起？？？），他们到了一个旅店，旅店房间状况通过一个01串告诉你，0代表空的，1代表被占了，问怎么安排住宿可以使牛离农夫的最远距离最小。题解：通过前缀和处理出某个位置之前的0的个数，然后二分枚举对于位置i的左右两边可以放置下所有牛的最小距离。然后输出最小的那个一个就可以了。没怎么接触过这种题，好像小白上面有，当初看小白的时候二分部...
2018-04-22 19:12:36
228
原创 HDU1864(01背包)
题目链接题意：中文题，但是注意单项是一类的意思。题解:根据题意筛出可以报销的发票，做01背包就可以了。输入的处理比较麻烦。#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 35;const int maxm = 3...
2018-04-21 19:21:57
180
1
原创 POJ3616（最长上升子序列）
题意：母牛要规划自己后面n个小时的行程，然后农夫有一个时间间隔的表，表示在某一段时间间隔之间母牛可以产出多少奶，问最多可以产多少奶。做了这么多题，DP能力没有多少长进，英语阅读能力到是强了。。。 题解：把时间间隔按开始时间从小到大排序，然后写一个最长上升子序列的变式就好了。#include<cstdio>#include<cstring>#include<...
2018-04-20 20:28:17
272
原创 hihocoder1044（状压DP）
题目链接看博客一律都说很简单，还有各种骚操作。体验好差。考虑第到第i个位置的情况，我们只需要知道前面m-1个位置的情况就可以了。所以将前面m-1加上i这m个位置压缩为一个状态，然后可以求出取了几个位置，如果取了超过q个就不再考虑。 考虑小于等于q的情况。基本的状态转移方程就是 dp[i][j]=max(dp[i−1][j>>1],dp[i−1][j/2+(1<<...
2018-04-20 20:09:44
108
原创 HDU4272（DFS+优化小套路）
题意：给一个数字栈，用栈顶的元素和与他下面距离小于（或等于）6的相同元素进行。。。连连看中的消除。然后被消除元素之上会都“落”下来。问能否全部消掉。题解：直接暴力dfs，然后用map存下每个数出现的次数，如果有不是偶数的就说明一定不能全部消掉。这个用map计数因吹斯听，这里MARK一下。 据说这题可以状压DP做，学习之后试试。#include&lt;cstdio&gt;#include...
2018-04-19 19:42:59
164
原创 HDU2859(DP)
题目链接题意：给你一个字符矩阵，找一个沿着右上左下对角线对称的子矩阵，求子矩阵最大边长。题解：枚举每一个点作为左下角的情况，然后枚举这个点所在行右边和所在列上边的相同的点对数，和右上角的dp值+1进行比较，取小值。没有想出来，为什么做了一些题之后感觉没有一点进步。。。。。。 不过这个题的写法感觉真的很惊艳。#include<cstdio>#include<...
2018-04-17 21:25:27
216
原创 HDU1078(记忆化搜索)
题目链接题意：整个NXN的矩阵中每个位置都有一块奶酪，有一只老鼠从（0，0）出发，横着或者竖着最多走k步，并且只能在当前奶酪大于出发位置的奶酪时候才能停在这里。问最多能吃大奶酪。 没弄懂题意，我以为是横着+竖着可以走k步，也就是可以交叉走。所以不会。。所以，重点在于either，是二选一的意思。。？ 题解：记忆化搜索一下就好了（没写出来）#include&lt;cstdio&gt;#...
2018-04-17 20:16:42
189
原创 POJ3186(区间DP)
题目链接题意：有一个双向队列，可以从中取数，取出的第k个数乘以k就是这个数的价值，然后求所有数的最大价值。题解： 容易得到dp[i][j]=max(dp[i+1][j]+v[i]∗(n−j+i),dp[i][j−1]+v[j]∗(n−j+i))dp[i][j]=max(dp[i+1][j]+v[i]∗(n−j+i),dp[i][j−1]+v[j]∗(n−j+i))dp[i][j] = m...
2018-04-16 20:34:40
489
原创 CodeForces 906C（状态压缩 +BFS）
题目链接题意：某人举办了一个party，邀请了他的朋友来，他的朋友也邀请了他们的朋友.etc。然后某人并不认识他朋友的朋友，这样聊天很尬，所以就让邀请他不认识的人的朋友给某人介绍。假设通过朋友C介绍的话，那么朋友C的所有朋友都会成为朋友，问让所有人成为朋友需要几个人来介绍，输出他们。题解： 因为最多只有22个人，所以比较容易想起用状态压缩，然后BFS枚举每一个人做第一个介绍的情况就好了。...
2018-04-14 20:49:38
310
原创 HDU1260（简单DP）
题目链接题意：某人在八点开始卖票，共有K个人来买票，每个人买票都有时间花费NiNiN_i，对于连续的两个人可以一起买票，时间花费为SiSiS_i，问这个人最早可以什么时候卖完票。题解：一个简单DP，对于第i个人来说，可以与第i-1个人一起买，也可以自己单独买，那么状态转移方程就是dp[i]=min(dp[i−2]+S[i],dp[i−1]+N[i])dp[i]=min(dp[i−2]+S[...
2018-04-12 19:13:49
1407
3
原创 HDU1087（最长上升子序列）
题目链接一个最长上升子序列，只不过把长度换成和。#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define ll long longll num[1005],dp[1005];int n;int main(){ while(~s...
2018-04-11 20:25:01
189
原创 HDU1074(状压DP)
题目链接题意：有n门课，每门课都要交作业，作业有时间花费和最晚提交日期，如果超过日期交作业，每超过一天就要扣一分，问最少扣多少分并且给出最少扣分的方案。题解： 因为最多只有15门课，所以可以压缩成一个数，二进制位上每一位代表一门课是否完成。然后开始DP。 枚举从1到1<< n的每一个状态i，然后枚举每一门课j（倒叙枚举，因为输入是按照字典序递增输入的），检查状态i是否完成了...
2018-04-11 19:59:06
429
原创 HDU1069（最长上升子序列）
题目链接这个题题意难一半。 表示看题看了好久。 题意：给定n种长方体，给定长方体长宽高，每个长方体有无限个，要堆成塔形，问最高能堆多高。下面的必须长宽均大于上面的。题解：每个长方体怎么放是没有限制的，也就是说一个长方体可以有六种方法（刚开始我对这个存疑，但是亲手摆摆试试就知道了），也就是说我们最多将一个长方体可以扩展成六个，然后排个序，求最长上升子序列就可以了。#include...
2018-04-10 20:57:17
172
原创 CodeForces - 919E（费马小定理）
题目链接题意：给定a，b，p，x，求n∗an≡b（modp）a，b，p，x，求n∗an≡b（modp）a，b，p，x，求n*a^n{\equiv}b（mod p） 可以设n=i∗(p−1)+jn=i∗(p−1)+jn = i*(p - 1) + j,那么原式就等于(i∗(p−1)+j)∗ai∗(p−1)+j≡b(modp)(i∗(p−1)+j)∗ai∗(p−1)+j≡b(modp)(i*(p...
2018-04-10 19:14:03
233
原创 SDNU1261（搜索）
题目链接 题意：有n堆石子，分别为ninin_i个，可以每次从最左或最右两堆之中选择一堆拿走，问先手最多可以拿多少石子。题解：搜索，对于当前是否是先手拿石子的情况分别讨论，如果轮到先手拿，则ans=max(dfs(l+1,r,!f)+nl,dfs(l,r−1,!f)+nr);l,r为左右边界ans=max(dfs(l+1,r,!f)+nl,dfs(l,r−1,!f)+nr);l,r为左右边界...
2018-04-03 20:56:42
123
原创 NIMK博弈
一般的nim博弈是任选一堆石子，从中取出任意个石子。解法是将所有堆的石子数进行异或，最后如果是0则先手必败，否则先手必胜。而nimk博弈则是任选k堆石子进行任意操作。异或可以看成是二进制按位相加，然后按位对2取模，这里对k堆石子进行操作也相似，按位相加之后对（k+1）取模，如果全都是0则先手必败，否则先手必胜。 大佬传送门const int MAXN = 10005;int SG[MAXN...
2018-04-02 19:59:13
727
原创 POJ3020（最小路径覆盖）
题目链接这题意是真的醉了，强行增加难度。（六级没过的人的泪水。） 题意： 给你一个图，*代表城市，圆圈代表空地，要用什么发射器覆盖所有城市，一个发射器可以覆盖两个城市（上下左右）。问最少需要多少个发射器。题解： 可以先对图上所有城市进行编号，记下城市数量mount，然后搜索整个图，对于一个城市可以与他上下左右的城市建边。这样建图就完成了。跑一个二分图匹配。然后答案就是mount - ...
2018-03-29 20:57:56
171
原创 POJ1091（拓扑排序）
题目链接 题意：给定n与m，表示会出现前n个大写字母，组成m个不等式。问能否判断给定字母的大小关系，并且判断第几个不等式之后可以判断成功，还要判断第几个之后会出现循环。情况分析都在代码里了。 可怜我少了一个点wa了一晚上。#include<cstdio>#include<algorithm>#include<cstring>#include&l...
2018-03-29 19:07:12
310
原创 hihocoder1175
题目链接中文题。 没有注意在拓扑排序的过程中也要取模。 记一下。#include<cstdio>#include<algorithm>#include<cstring>#include<queue>#include<cmath>#include<vector>using namespace std;...
2018-03-28 19:55:53
106
原创 HDU5884（K叉哈夫曼树 + 二分）
题目链接题意：给了你n个数，要把这n个数合成一个，每次可以拿k个，每次拿数的权值是所拿数之和，比如3 4 4三个数每次可以拿2个，那就是（3+4）+（3+4+4）。 求最后权值总和不超过m的最小k。用2叉哈夫曼树疯狂tle，竟然还有k叉这种东西。 尽管在这个问题中k叉已经比2叉快了很多，但是还是需要二分枚举k的最小值，不然还是会超时。 k叉哈夫曼树大概就是用两个数组a，b来模拟哈夫曼...
2018-03-26 21:25:04
224
原创 HDU1024(DP)
Max Sum Plus PlusTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12589 Accepted Submission(s): 4146Problem Description Now I think you...
2018-03-20 20:53:11
174
原创 HDU1176（DP）
题目链接以前做过的一道题，再做依旧很费劲，动态转移方程不难写，但是在细节卡了好久。很气。 因为初始位置在5，所以一开始就从5模拟4次拿馅饼的位置，然后后面都一样了，最后在最大时间内找馅饼数最大。后来发现倒着推更简单。 设最最后一块馅饼是m时落下，那么从m-1时开始，dp[i][j]+=max(dp[i+1][j],dp[i+1][j−1],dp[i+1][j+1])dp[i][j]+=ma...
2018-03-16 20:26:59
112
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人