- 博客(97)
- 问答 (2)
- 收藏
- 关注
RSS订阅原创 连续邮资问题(LDU回溯专题)
这题过的少，先写个博客，增加波访问量回溯,不存在的,写发dp吧,搞懂思想即可dp[i][j][k],代表前i种数选j个是否可以凑成k，然后和背包一样乱搞一下就可以了,谨慎粘贴,以防查重#include<iostream>#include <algorithm>#include <string.h>#include <bits/stdc+...
2018-12-23 16:03:36
633
1
原创 poj1182 带权并查集
题意：一共有ABC三种动物，A吃B，B吃C，C吃A，现在共有n个动物，编号1~n，给出k句话，判断真假；每句话包含val,u,v;val==1,代表u,v,是同类，val==2代表u吃v假的条件为：1.与前面某些真话冲突；2.u,v,大于n3.当val==2时,u!=v, 即不能自己吃自己;思路：有联系的为一个集合，0代表和集合根同类，1代表吃集合根，2代表被集合根...
2018-08-23 10:34:19
195
原创 hdu 6395 Sequence 分块矩阵快速幂
容易知道 p/i (i=3......n); 在某一区间内是相同的，记录前一个区间的fn-1,fn-2,对本区间进行矩阵快速幂，确定本区间的界限可以用一句话 即 j=(p/i)==0?n:min(n,p/(p/i))，并不需要二分；AC 代码#include <iostream>#include <algorithm>#include <stri...
2018-08-16 10:39:21
230
原创 bzoj5296 [Cqoi2018]破解D-H协议【BSGS】
先把a求出来，然后求B^a,即可；已知A ≡ g^a (mod P) ,求 a，设a=i*m-j ===> A*(g^j) ≡ g^i(*m) (mod P);枚举 i,j ==> i的范围 为0---> ceil(sqrt(P)); j的 范围 1----->ceii(sqrt(P)); 先枚举j 将 A*(g^j)存到map里 mp[A*(...
2018-08-08 10:42:42
180
原创 hdu 5705 简单分类讨论
先把所给数据换成秒，然后算出当前时针与分针相差的角度，再算出 一秒钟分针与时针各能转多少度，然后每过一秒，时针与分针之间的角度缩小或者扩大的角度是一定的，然后直接O（1）出结果即可;这题数据水的一批，随随便便一个错误代码就能过，但是分类讨论绝对是正确的；AC代码#include <iostream>#include <string.h>#include <algo...
2018-06-13 21:00:19
333
原创 poj1157 LITTLE SHOP OF FLOWERS (简单dp)
就是简单dp....第一个自己敲了敲1A的dp，纪念一下；由于确实简单，不赘述，把第一行状态列在纸上，第二行思考一下，状态转移方程就出来了；注意一下每个花的插得花瓶范围即可，AC代码#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>using...
2018-06-06 17:36:57
193
原创 HDU - 6290 奢侈的旅行
首先 化简一下式子；log2[(1+a1)/1]+log2[(1+a1+a2)/(1+a1)]+log2[(1+a1+a2+a3)/(1+a1+a2)]+....+log2[(1+a1+a2+...+an)/(1+a1+a2+...+an-1)]=log2(1+a1+a2+a3+a4+a5+...an);直接维护 1+a1+a2+...+an的 最小值 ，相当于 最短路；其次 log2()手写AC...
2018-06-05 13:48:18
353
原创 poj1143 记忆化搜索+状态压缩
题意：给定一个序列，轮到谁，取出一个数k删除,并删除i*k(i=1,2,3,.....),设k1为已经删除的数，同时删除k1*i+k*j,(i=1,2,3,.....;j同上 )，思考:考虑n为最大为20，而且ai最大为20，对于每个输入的数状态压缩,二进制的从右到左第几位为1说明此数被输入，先手必赢得状态是走完当前步，后手没有必赢状态,依据这个 从下往上dfs，枚举每种情况并记录状态，重复状态不...
2018-06-01 19:37:15
498
原创 poj 1088 滑雪
dfs+dp一下，因为序列下降保证了 dfs不会 tle ，对于 每一个点 ，直接扫即可 ，同时更新最大值；AC代码#include <iostream>#include <string.h>#include <algorithm>using namespace std;int a[110][110];int cnt[110][110];int di...
2018-05-29 18:52:52
105
原创 Tak and Hotels II ABC044&ARC060 (倍增)
倍增模板题；关于倍增请看：点击打开链接然后就没什么技术含量了AC代码#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>using namespace std;typedef long long ll;const int maxn=2e5+...
2018-05-23 20:30:11
192
原创 第六届蓝桥杯个人赛决赛B组B题（软件类）
题意不再详述；思路：将最后的正方形看做154*154个格子，直接枚举每个合法现有正方形暴力正确结果，暴力方式很重要，具体看代码实现；//2 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 61#include <iostream>#include<algorithm>#include<strin...
2018-05-22 21:23:40
272
原创 codeforce 6D. Lizards and Basements 2
题意：有n个敌人，每个敌人有a[i]个血量，你能用火球射击第2~n-1个人，射击到第i个人,第i个人减少a血量，第i-1,i+1个人减少b血量,问最少射击几次能将所有人血量变为<0;解：dfs剪枝，考虑题目中所给的数据量较小；从左到右dfs，在射第i个人时,暴力射击次数，最少能将左边人射死，最大能将三个人射死，这样再做一下最优性剪枝1778ms，勉强能过。AC代码#include <i...
2018-05-22 21:18:25
168
原创 upc 6461: Tak and Cards
dp[i][j][k],i代表到第几个数，j代表次数，k代表数值，代表到第i个数时数值k的出现j次的方式有多少种；知道dp含义，直接上代码就行AC代码：#include <iostream>#include <string.h>#include <algorithm>#define STD std::ios::sync_with_stdio(false);...
2018-05-20 13:22:29
234
原创 Codeforces Round 6——E. Exposition
给定一个序列，让你求出最长的连续序列，要求序列中最大值减最小值<k，问有多少个这样的序列；没想出来，看了看题解，multiset+vector 可以来一波；用multiset维护现有序列的有序性，一旦最大值-最小值>k,按输入顺序一直删除到最小值就okAC代码#include <iostream>#include <string.h>#include <...
2018-05-19 16:02:40
222
原创 Codeforces 5E Bindian Signalizing
题意：有n座山围成一个圈，找出两座山，他们之间形成的两段圆弧任意一段中没有高于它们两个的山那么count++；统计有多少不同对这样的组合；思路：看别人的题解 ，先将环拆成链，从最高的山那里断开，比如5,3,7,1,4，可以断开为 7,1,4,5,3,7 在最后要加上一个最大值然后统计每个点左边第一个大于它的山的位置和右边第一个大于它的山的位置，对于相同高度的，只考虑右边就可以（避免重复）；l[i]...
2018-05-12 13:58:42
194
原创 codeforces 5C. Longest Regular Bracket Sequence(dp+栈)
题意：求出最长连续的规范括号序列，并求出长度和个数方法一：利用栈与括号特性，来一发dp，本着一个左括号与一个右括号对应，是左括号就入栈，否则寻找栈中与其相匹配的并计算距离；方法二：从左到右扫一遍，标记合法右括号，从右到左扫一遍，标记合法右括号。再对标记数组扫一遍，如果vis[i]=1;,ans++;否则ans=1；详看代码操作dp AC代码：#include <iostream>#i...
2018-05-09 17:51:04
166
原创 codeforces 4D D. Mysterious Present (dp||LIS)
LIS 的 限制条件变为了两个，然后记录路径倒序输出即可，注意答案为1的情况；AC代码#include <iostream>#include <algorithm>#include <string.h>using namespace std;const int maxn=1e5+10;struct point{ int w; int h; in...
2018-05-08 20:11:02
187
原创 山东省第六届 ACM 省赛 Stars （矩阵尺取）
因为星星静态，没有必要树状数组，直接2*(n^2) 记录(1,1)到(i,j)的矩阵和,然后枚举任意两行，尺取即可；AC代码：#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int star[420][420];int n,k;int chi(in...
2018-05-03 16:01:45
200
原创 Zoj 4029 Now Loading!!! (二分)
Now Loading!!!Time Limit: 1 Second Memory Limit: 131072 KBDreamGrid has integers . DreamGrid also has queries, and each time he would like to know the value offor a given number , where , .Inpu...
2018-05-02 10:45:58
229
原创 SWERC2017 Blowing Candles 凸包+旋转卡壳（模板题）
生日蛋糕上有蜡烛，问把蜡烛包括的两条平行线间的最短距离；#include <iostream>#include <string.h>#include <algorithm> #include <math.h>#include <vector>using namespace std;const int maxn=2e5+10;...
2018-05-01 21:42:38
269
原创 法里数列 Best Rational Approximation
上图 0/1和1/1(左边) 以及中间的是法里数列分母分子互质；0 1 ①0 1/2 1 ② 0 1/3 1/2 2/3 1 ③ 0 1/4 1/3 1/2 2/3 3/4 1 ④ 0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1 ⑤ ....题目大意：给个小数p(0<=p<1)，求差值与其最小的不可约分分数且分母不能超过n思路: 二分法里数列#incl...
2018-05-01 21:29:45
701
1
原创 RMRC2017 Polyline Simplification
给出点集，构成曲折线，如下图，每两个线构成一个三角形，三点共线认为面积为零，每次删掉面积最小的三角形和其顶点，余下两点自动连接，如下图，删掉面积S2(假设S2面积最小)，p3也被删去，形成下面的情况，一直删到剩余边数为m时停止，把每次删的点输出来；按题意模拟即可；利用向量叉乘求出面积存到set或priority_queue中，记录每个点前驱后驱，删除时不断更新；坑点：将一个三角形删除后，会产生一个...
2018-04-26 13:43:36
302
原创 codeforce 3D. Least Cost Bracket Sequence
题意：将问号变为左、右括号(代价分别为为left[i],right[i])使得原序列合法，合法即为如题所述；思路：贪心先不考虑问号：判断一个一串括号合不合法：设置变量ans=0；遇到')'，ans--,遇到')'，ans++；最后判断ans中途中是否出现ans=-1&&最后ans是否为0即可；对于有问号，先尝试将所有？变为），如果ans=-1时，判断前面是否有可用的“ 由问号变为的...
2018-04-25 19:40:33
168
原创 codeforce 3B lorry (贪心)
有货车运量V；有若干物品A 占2单位体积，有若干物品B占1单位体积；相同种类的物品价值不一定一样；序号按照输入顺序而定；问货车可以拉走最多多少价值的物品，并输出所选物品的序号；思路：贪心，先把A填到不能填，然后再补B，补完B后再考虑用B去替换前面A，此策略必定最优；考虑到B物品的可补行！因为涉及变量较多，时刻注意A，B，空余V的数量关系；下面是AC代码#include <iostream&g...
2018-04-23 21:01:31
199
原创 模拟退火 poj 2420
详见点击打开链接#include <iostream>#include <stdio.h>#include <string.h>#include <math.h> #define eps 1e-8#define T 100#define delta 0.98using namespace std;const int maxn=1e5+...
2018-04-18 21:46:46
125
原创 cerc2017 Justified Jungle
题意：一棵树有多少种切法使得每个分离的子树节点数相同，并输出每种方法需要切边的数目，升序输出；首先，想要均分这个树，那么剩下的子树节点必定是总节点数的因子（根据题意，排除这个数本身）；打个表，1~1e6的数最多有240个因子，那么只需要枚举因子,给的是6s；先转换为有根树，枚举每条边，只要这个边下的子树节点数是枚举的因子的倍数，ans++；最后如果[n/(枚举的因子)]-1==ans,则枚举得因子...
2018-04-16 18:02:07
221
原创 AtCoder Grand Contest 001 C Shorten Diameter
题意：给你一棵树，问最少删多少节点使得树中最远的两点距离为k（删完点后要保持树的连通性）；根据题意，就是每次都删叶子结点，我们可以枚举k长的树的中点，对于k为偶数，枚举中点，对于奇数，枚举中间边的中点；求最小；#include <iostream>#include <string.h>#include <stdio.h>#include <algor...
2018-04-05 09:52:32
534
原创 bzoj 1001 平面图转换求最大流（最小割）
数据好坑 ，说了最多1000*1000个点，head[]开了1e6+10，硬是不给过 _φ(❐_❐✧ ，改为2*就过了；因为给的边的顺序问题，可以将此题转换为平面图的同构图，然后跑spfa；所谓同构图就是把原来图中的面看为点，如图，1是源点，6是汇点，先将它们连起来，此时多了两个面（在同构图中多了两个点，分别为同构图的起点和终点），然后把同构图中相邻面的点连起来，权值为线割的那条边的权值，最后把...
2018-04-02 21:20:10
175
原创 最大流+最小割分点
可当模板 sto[]与sto1[]存的是最小割的两部分点#include <iostream>#include <string.h>#include <algorithm>#include <math.h>using namespace std;const int inf=0x3f3f3f3f;const int maxn=1e3+10;...
2018-03-05 20:10:32
156
原创 poj 2728 最优比率生成树
裸题 可当模板 用 prim堆优化会tle#include <iostream>#include <string.h>#include <algorithm>#include <queue>#include <math.h>#include <stdio.h>#define eps 1e-6using names...
2018-03-03 21:11:27
139
原创 poj2976 01分数规划
公式：r=sigam(a[i]*x[i])/sigam(b[i]*x[i]) ,i被选x[i]==1 否则 x[i]==0;设f(L)=sigam(a[i]*x[i])-L*sigma(b[i]*x[i]), 易知L为所求r, 求L最大；f(L)随L增大而递减；当f(L)>0==>sigam(a[i]*x[i])/sigam(b[i]*x[i])>L. 我们此时选的L更优；当==...
2018-03-01 09:59:35
207
原创 poj1050 最大子矩阵
a[i][j]表示从第一行到第i行第j个数的和，然后计算p到q行之间的最大子矩阵时，将p到q行之间第j个数的和看做一个元素，求这些元素的最大连续子序列和；#include <iostream>#include <string.h>#include <algorithm>using namespace std;int a[110][110];int ma...
2018-02-14 17:09:42
153
原创 poj1018
题意：从m组中每组选一个，一共选m个，从m个中选一个最小的带宽，使得（最小带宽）/（价格的总和）最大（价格总和为m个已选的价格的总和）；用dp[i][j]，表示前i组带宽为j时所花费的最小价格j最大取400（我也不知道为什么取400，但400就够，或者卡着1S时间设一个）poj double 型用%f 输出最好，%lf可能会wa，比如说此题；#include <iostream>#i...
2018-02-14 12:38:42
175
原创 nefu1028暑假计划 01背包
暑期将至，忙碌的DB小公主想要找一些零零碎碎的工作来补贴家用。 已知DB小公主一共有m天的假期，每天的编号从1到m，一共有n份可以做的工作，每份工作都知道起始时间s，终止时间e和对应的工资c，每份工作的起始和终止时间以天为单位(即天数编号)，每份工作必须从起始时间做到终止时间才能得到总工资c，且不能存在时间重叠的工作。比如，第1天起始第2天结束的工作不能和第2天起始，第4天结束的工作一起...
2018-02-12 17:38:47
126
转载 牛客练习赛10E
链接：https://www.nowcoder.com/acm/contest/58/E来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K64bit IO Format: %lld题目描述给你一个长为n的序列a，m次查询区间[l,r]内出现次数第k1小的数中值第k2小的数是多少？保证输入合法
2018-01-23 13:13:48
386
原创 莫队算法简单模板
求区间（l-r）内恰好出现k次数的个数#include #include #include #include using namespace std;const int maxn=1e5+10;struct Mo{ int l; int r; int id; int oid;};Mo mo[maxn];int sto[maxn];int cnt[maxn],ans,
2018-01-23 12:49:20
278
原创 code force 449 div2 C. Nephren gives a riddle
code force 449 div2 C. Nephren gives a riddle
2017-12-03 21:14:19
518
空空如也
java 导入json包后 JSONObject对象没有addPropery()方法
2018-12-10
用c++ 求智能手机的滑动解锁方式一共多少种？3*3格
2018-03-17
TA创建的收藏夹 TA关注的收藏夹
TA关注的人