- 博客(64)
- 收藏
- 关注
RSS订阅原创 HDU6406 Taotao Picks Apples（单调队列+二分）
当时只差临门一脚，多了许多罚时，贴个代码警示一下；#include<bits/stdc++.h>#define MAXN 100000using namespace std;int s[100005],a[100005],b[100005],c[100005];int lis[100005];struct node { int x,y,id; bool ...
2018-08-16 20:25:35
193
1
原创 杭电多校HDU6333，6336，6341代码
//6333////ID: taoxiaa1//PROG: concom//LANG: C++////URAL ID:248353QC//#include<iostream>//#include<algorithm>//#include<string>//#include<cstring>//#include<map&...
2018-08-02 16:44:55
468
原创 CodeForces - 337D Book of Evil （树形dp）
题意：有一颗有n个结点的树，树上存在一个污染源（位置不确定），它可以污染与它距离不超过d的节点，现给出m个被污染的节点（污染源本身也可能是被污染的节点），求污染源可能的位置数。思路：树形dp，树的最长链，dp[i][0]表示i到i的子树中最远污染源的距离，dp[i][1]表示i到i的子树中次远污染源的距离，dp[i][2]表示i经过i的父节点到最远污染源的距离。那么污染源到这些被污染的点的最远...
2018-07-24 14:50:28
710
原创 牛客网暑期ACM多校训练营（第一场）B Symmetric Matrix
B Symmetric Matrix链接：https://www.nowcoder.com/acm/contest/139/B来源：牛客网 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld题目描述Count the number of n x n matrices A satis...
2018-07-20 15:55:35
200
原创 codeforces 722C Destroying Array
题意：给出长度为n的序列，每次去掉一个数，使得序列分成几块，问当前权值最大块的权值。 思路：提供两种，第一种用multiset和前缀和直接暴力模拟。 第二种用并差集，假设坐标i为一个去掉的数，那么f[i]记录的是i所在连续的去掉的数的区间的最左端，其余的看代码QAQ。第一种#include<bits/stdc++.h>using namespace std;long ...
2018-04-17 19:14:04
203
原创 Ural 2018 The Debut Album
题意：一个由’1‘，‘2’组成的长度为n的字符串，要求连续的1不超过a个，连续的2不超过b个，求满足条件的字符串的数量，答案模1e9+7； 思路：dp[i][j]表示长度为i，以j结尾，满足条件的字符串的数量；#include<bits/stdc++.h>using namespace std;const int Mod=1e9+7;long long dp[50005][...
2018-04-14 15:02:43
179
原创 Ural 1014 Product of Digits(水题）
题意：给出n，求最小正整数q，q各个位置上的数的乘积为n； 太水了，就只贴代码了；#include<bits/stdc++.h>using namespace std;int s[100];int main() { int n; scanf("%d", &n); if(n == 0) { printf("%d\n", 10...
2018-04-14 14:39:06
207
转载 Ural1136-Parliament
博客出处：https://blog.csdn.net/Walton_/article/details/53366909 题目大意 给出一棵二叉搜索树左子树+右子树+根的后序遍历，要求输出右子树+左子树+根的遍历顺序解题思路 根据给出的遍历顺序可知最后一个节点一定是根节...
2018-04-13 20:36:06
116
原创 USCAO 1.3.2 Barn Repair
题意：给出l头牛的坐标，要求用n块板子讲l头牛拦住，要求板子总长最小。思路：首先如果只用一块板子的话，那么长度sum为最后的牛的坐标-第一条牛的坐标+1，用n块板子相当于在一块板子上切n-1刀，那么只需要求出相邻距离最大的n-1块，用sum减去这n-1块的距离即可； /*ID: taoxiaa1PROG: barn1LANG: C++*/#include<bits/stdc++...
2018-04-10 19:52:35
129
原创 UVA - 10328
题意和思路于zoj3747类似zoj3747博客链接：https://blog.csdn.net/qq_36542637/article/details/79842141只不过数据范围大，使用了java大数类import java.math.*;import java.util.*;public class Main { public static BigInteger dp[][] = n...
2018-04-07 15:55:57
165
原创 ZOJ 3747
参考博客：https://blog.csdn.net/cc_again/article/details/24841249题意：给出长度为n，由字符'G'，'P'，'R'，组成的字符串，要求至少有m个连续的'G’，至多有k个连续的'R'。问有多少满足条件的字符串。思路：可以转换成求最多有n个连续的'G'，至多有k个连续的'R'的字符串数量sum和最多有m-1个连续的'G'，至多有k个连续的'R'的字...
2018-04-07 15:52:02
211
原创 CodeForces 429B Working out
题意：有两个老哥分别从左上角走到右下角，左下角走到右上角，中途要求相遇一次，相遇处的权值不算，求两位老哥的路径权值最大和；思路：dp1[i][j]为左上角走到坐标i,j的最大值，同理有dp2,dp3,dp4分别对应其他三个角，那么答案为：max(max(sum,dp1[i][j-1]+dp3[i+1][j]+dp2[i-1][j]+dp4[i][j+1]),max(sum,dp1[i-1][j]+...
2018-04-07 15:36:45
141
原创 codeforces761 D. Dasha and Very Difficult Problem
题意简单不解释了；思路：就按ci的大小将序列c从小到大排个序，然后满足bi-ai>(bi-1)-(ai-1)即可；#include <bits/stdc++.h>using namespace std;struct node { int a, c, id; bool operator<(const node &x)const { ...
2018-03-28 21:26:59
139
原创 codeforces761 C. Dasha and Password
题目大意：这是一个类似组合密码的东西。初始状态密码设置在第一列，我们可以通过拨动来改变每一行的密码。合法的密码必须满足三个条件：1.至少有一个数字。2.至少有一个小写字母。3.至少有一个特殊字符（*&#）问最少拨动多少下就能得到合法的密码。思路：分组背包加状态压缩#include <bits/stdc++.h>using namespace std;char s[55];...
2018-03-28 21:23:47
148
原创 codeforces761 B. Dasha and friends
题意：告诉你两个运动员与跑道上每个障碍物的距离和跑道的长度，要求你判断他们是否在同一跑道； 思路：可以通过已知条件得知两个由相邻障碍物之间的距离组成的序列，判断两个序列是否相等即可；#include <bits/stdc++.h>using namespace std;int a[105], b[105];int main() { int n, l; ...
2018-03-28 21:14:52
170
原创 HDU2128 （dfs）Tempter of the Bone II
我是题目快戳我The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze was changed and the way he came in was lost.He realized that the bone ...
2018-03-20 21:09:00
296
1
原创 UVA 11729简单贪心
题意：你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务，然后他会立刻独立的执行Ji分钟后完成任务。你需要选择交待任务的顺序，使的所有任务尽早执行完毕（即最后执行完成的任务的结束时间应尽量早）。注意，不能同时给两个部下交代任务，但部下可以同时执行他们自己的任务；思路：生活常识，执行时间长的任务应该尽早做；所以，先排个序吧；#include<iostream>#include
2017-09-20 20:45:11
305
原创 UVA - 11292 简单贪心
题意：你的王国里有一条n个头的恶龙，你希望雇佣一些骑士把龙的头全部砍掉。村里有m个骑士可以雇佣，一个能力值为x的骑士能砍掉一个直径不超过x的头。且需要支付x金币，每个骑士只能雇佣一次。如何雇佣骑士才能砍掉所有的头且花费的金币最少；输出最小花费，无解即输出“Loowater is doomed!”。思路：很明显的贪心，先将m个骑士根据能力值从小到大排序，对于直径为r的头，我们只需要雇佣第一个能力值大于
2017-09-20 20:36:50
202
原创 UVA - 12716
题意：给出范围n，在[1,n]中，有多少对a,b（a>b），gcd（a,b）=a xor b;（xor为异或）； 思路：因为若a xor b=c，那么a xor c=b，又因为c=gcd（a,b），所以只需要枚举所有的c，再枚举c的所有倍数a，判断是否a xor c=b，gcd(a,b)=c;#include<iostream>#include<cstdio>#include<cstring>
2017-09-13 20:11:26
176
原创 HDU6201 | 2017 ACM-ICPC 亚洲区(沈阳赛区)网络赛-H transaction transaction transaction
题意：一个n个点n-1条边的无向图，每个点每条边都有权值，求一条路径W终点-W路径-W起点的最大值； 思路：dp，dp[i]表示以i为终点的路径的最大值，若x于y相连，那么有dp[x]=max(dp[x],dp[x]-Wx-Wxy+Wy);#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<
2017-09-11 20:49:13
444
原创 Codeforces842C dfs+set
题意：有一颗n个点，n-1条边的树，每个点的权值为wi，问从1到每个点，每条路径所经过点的gcd，可以选择将该条路径中某一个点改为0； 思路：dfs是肯定要的，至于set处理看代码吧；#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<map>#include<stack>#includ
2017-08-30 11:03:15
360
原创 Codeforces 842B 简单几何
题意：平面上有一个圆心为原点的圆，半径为r,内圆半径为r-d（题意读错以为d是内圈半径，wa到爆炸），询问n个小圆zi（zi为半径），问有多少个圆完全在外壳内（即完全在圆内，但与内圈无交集）； 思路：已知n个圆的圆心xi,yi，可以知道圆心距为sum=sqrt(xi*xi+yi*yi),那么只需要保证sum>=r-d+zi&&sum+zi<=r即为完全在外壳内；#include<iostream>
2017-08-30 10:58:18
353
原创 CodeForces - 27C
题意：再给定的序列中找出一组最短的无序子序列#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath>#include<stack>#include<vector>#include<cstdio>#define M
2017-08-23 19:10:34
201
原创 Coderforces 20C 最短路记录路径
题意：给定一个带权无向图。你需要求出从点 1 到点 n的最短路。 思路：使用Dijkstra算法，当进行松弛操作时用数组记录下前缀，输出时先从n向1回溯记录再输出；#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath
2017-08-23 19:07:35
343
原创 poj1942组合数学
题意：给定一个矩阵网格n*m，要从左下角走到右上角，每次只可以往上或者往右走，问有多少种走法； 思路：以为每次只能向上或者向右，那么总共只需要走n+m步，其中n步向上，m步向右，所以我们只需要确定哪几步向上走那么向右的也就确定了。即从n+m步中选出n步向上，即C（n+m，n），组合问题；#include<iostream>#include<algorithm>#include<string>
2017-08-16 12:27:28
369
原创 poj1019组合数学
题意：给定一个序列，问序列第i位数字； 思路：显而易见，在1~9中，序列长度依次增加1，在10~99中，序列长度依次增加2。那么我们可以求出所有num[n]（num[n]以数n结尾的序列长度），因为给的条件(1 ≤ i ≤ 2147483647），所以n最大为31269（对所有的num[n]求个和就知道了）；具体思路看代码吧；#include<iostream>#include<algorith
2017-08-16 12:21:08
202
原创 poj1850组合数学
题意：给你一个字符串s，输出s在字典序全排列中的位置(从小到大排列)。 思路：长度为m的字符串有C（26，m）,这是显而易见的，从26个字母中挑m个，因为要升序排列，所以只有一种排法，即C（26，m)为个数；这样我们就可以求出长度比字符串s小的字符串有多少个。len为字符串s的长度。 长度相同但排在字符串s前面的有多少个？对于 s 的每一位 s[i] 和左边相邻的 s[i-1]，如果s[i] >
2017-08-14 20:04:07
286
原创 poj3252组合数学
题意：一个数转换成二进制数，零的个数大于等于一的个数的数称为圆数，例如9转换成1001，0的个数为2，1的个数为2，所以9为圆数；输入两个数start和end，问start到end有多少个圆数。 思路：start到end中有多少个圆数，我们只需要求出num[0，start]和num[0,end)，num[0，start]-num[0,end)即为所求； 以二进制数10011000为例，位数为8，
2017-08-14 17:13:06
208
原创 CodeForces - 5C
题意：给定一个由字符 ( 和 ) 组成的字符串。您需要找出它的最长子串，且该子串是一个合格的括号序列。同时，还需要找出这样的子串的数目。（像（），（（））样的为合格的括号序列，（(（）（））为不合格）； 思路：设dp[i]表示到第i个右括号所获串的长度。则dp[i]=dp[t-1]+i-t+1。t表示离i最近的那个左括号的位置。#include<iostream>#include<algorit
2017-08-12 10:11:20
197
原创 CodeForces 1C
题意：给出正多边形的三个顶点，求正多边形的最小面积； 思路： 海伦公式: p=(a+b+c)/2，S=√p(p-a)(p-b)(p-c)（a,b,c为三角形的三边，S为三角形面积） 1.求外接圆半径r=a*b*c/4S 2.由余弦定理求出三个圆心角num[3] (要注意的是,当三个点在同一段半圆弧上时,这时第三个圆心角应该用2π-num[0]-num[1],防止麻烦直接就令num[2]=2
2017-08-11 20:51:09
329
原创 POJ - 2392 多重背包
题意：有K种块，每种高度为Hi，数量为Ci，拿这K种块去建塔，每种块再塔中所处的高度不能超过Ai，问塔最高能有多高； 思路：首先因为每种块所出的高度不能超过Ai，那么这个塔的最大高度不会超过max（Ai），以max（Ai）为数组大小，为了保持结果能最优应保证Ai小的在下层，所以应该以Ai从小到大排序，之后每次以Ai为背包容量去求解；#include<iostream>#include<algor
2017-08-09 16:36:23
257
原创 POJ - 1276 裸完全背包
题意：要取价值为cash的钱，ATM机里面有N种面额的钱，每种面额为Ni，数量为Di，问最多能取出多少钱（要小于等于cash）； 思路：以cash为背包容量，多重背包#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmat
2017-08-09 16:27:42
339
原创 HDU - 2191 裸多重背包
#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath>#include<stack>#include<vector>#include<cstdio>#define MAXN 33000#define INF
2017-08-09 16:22:50
172
原创 HDU - 1059 多重背包模板题
题意：有价值为1，2，3，4，5，6的物品，每种物品都有一定数量，问这些物品能不能平分成价值相同的两份； 思路：多重背包模板题，以价值总额的一半为背包容量#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath>#in
2017-08-09 16:21:26
600
原创 HDU - 1114完全背包模板题
题意：你有一个存钱罐，空的时候质量为E，满的时候为F，你有N种硬币价值为P，质量为W，问把存钱罐状满的最小价值； 思路：完全背包模板题#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath>#include<stac
2017-08-09 16:18:51
331
原创 zoj3623
#include <stdio.h>#include <string.h>#include <stdlib.h>const int N = 35;const int M = 1000;int n,l;int v[N],w[N];int dp[M];int max(int a, int b) {return a > b ? a : b;}int main(){ int i,j,k
2017-08-09 12:54:31
207
原创 POJ - 2063 完全背包
#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#include<cmath>#include<stack>#include<vector>#include<cstdio>#define MAXN 33000#define INF
2017-08-09 12:47:51
271
原创 POJ - 3260 完全背包和多重背包
题意：农夫约翰要购买价格为T的物品，他有N种硬币，每种硬币的面额为Vi，数量为Ci，同时店主也只有这几种面额的硬币，但数量无限，问约翰总共要经手的硬币数量（约翰买东西给店主的硬币数量+店主找钱给约翰的硬币数量=约翰经手的硬币数量）（约翰是多重背包，店主是完全背包） 思路：我们用约翰所拥有的硬币总额来做背包容量是肯定不行的； 可以注意到，上界为w*w+m（w最大面额的纸币），也就是24400元。（
2017-08-09 11:30:12
1069
原创 POJ - 1787 完全背包，记录路径
题意：你有1，5，10，25四种硬币数量有限，你想买价格为p的咖啡，问你能不能购买，要求花的硬币尽量多，并且输出每种硬币花了多少； 思路：看起来像多重背包加记录路径但用完全背包比较好写#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>#include<queue>#inc
2017-08-08 20:40:04
430
原创 POJ - 3181 完全背包
题意：Farmer John 想知道，在一家商品价格为1至K (1 <= K <= 100)的店有多少方法能正好花完他的N(1 <= N <= 1000)元钱 。商品数量充足。 思路：完全背包，dp[j]表示价格为j时花光钱的方法数，所以状态转移方程为dp[j]+=dp[j-i]（i为商品价格） 因为方法数过大超longlong了，所以开两个longlong数组将大数存下；#include<io
2017-08-08 20:34:03
243
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人