3 HPU王小二

尚未进行身份认证

不念过去,不畏未来...

等级
TA的排名 7k+

JAVA大数+常用函数

推荐:java中的BigIntegertest1题目描述:输入两个非常大的实数A和B,判断A是否等于B;importjava.math.BigDecimal;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){BigDecimala,b...

2018-11-07 12:14:14

Educational Codeforces Round 53 (Rated for Div. 2)

C.VasyaandRobot【二分】暴力左端点,二分右端点。在[L,R]区间内任意填方向,根据区间外的方向值和终点(x,y)计算出此区间需要能否填成。判断式:r-l>=abs(res1)+abs(res2)&&(r-l-abs(res1)-abs(res2))%2==0.#include<bits/stdc++.h&...

2018-11-02 12:02:05

简单记忆化搜索

以前极少写记忆化,大多都是直接推递推方程,推。不。动。。。所谓记忆化,就是一种优雅的暴力,最近在写数位DP,总感觉好强大的暴力。。。POJ1579FunctionRunFun分析:按照题意记忆化,每一步都记忆化一下;#include<cstdio>#include<cmath>#include<cstring>#include&l...

2018-10-24 22:35:32

P3413 SAC#1 - 萌数【数位DP+回文数】

题目描述只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。现在SOL想知道从l到r的所有整数中有多少个萌数。由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。输入格式:输入包含仅1行,包含两个整数:l、r。输出格式:输出仅...

2018-10-24 21:16:24

P2602 [ZJOI2010]数字计数【数位DP】

给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。输入格式:输入文件中仅包含一行两个整数a、b,含义如上所述。输出格式:输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。输入样例#1:199输出样例#1:9202020202020202020分析:类似于写的这个题;这个题要除去前导0,其他就是把之...

2018-10-23 10:59:55

ZOJ 3962 Seven Segment Display【数位DP*好题】

ZOJ3962SevenSegmentDisplaySampleInput3589ABCDEF3FFFFFFFF700000000SampleOutput208124327HintForthefirsttestcase,thecounterwilldisplay5hexadecimalnumbers(89ABCDEF,89ABCD...

2018-10-22 22:11:46

POJ 1160 Post Office【区间DP+四边形不等式优化】

POJ1160PostOffice题意:给你nnn个点,在这nnn个点中选择mmm个点建立基站,定义节点iii到基站jjj处的花费abs(j−i)abs(j-i)abs(j−i),让你求解最小花费.分析:我的暴力:预处理区间(L,R)(L,R)(L,R)建立一个基站的最小花费,dp[i][j]:表示前i个点建立j个基站的最小花费dp[i][j]:表示前i个点建立j个基站的最小花费d...

2018-10-19 22:06:09

HDU 2438 Turn the corner【三分+公式推导】

记录:我一直把拐角处作为三分点(让车以拐角处旋转),突然发现这个点并不固定,zz。。。应该让汽车靠着右侧和下侧移动(不考虑现实生活车技),建立坐标系如下图,三分角度(红色直线与x轴夹角),求出当y=Xy=Xy=X时的最大fabs(x)fabs(x)fabs(x),若小于街道yyy即“yes”“yes”“yes”.#include<bits/stdc++.h>usingna...

2018-10-18 22:11:11

hihocoder #1142 : 三分求极值【三分】

分析:【三分】三分最近距离的(xx,yy)(xx,yy)(xx,yy)中的xx,画图可知,对于P到曲线上任一点(x,y)(x,y)(x,y),并不是单峰问题。当−INF<xx<=−b/2a-INF<xx<=-b/2a−INF<xx<=−b/2a,对于P点到该曲线距离满足三分,同理−b/2a<=xx&...

2018-10-18 19:53:51

HDU 3480 Division【区间DP+四边形不等式优化】

题意:将含有n个元素的一个集合分成m个子集,定义一个子集的价值为:最大值与最小值差的平方,求m个子集的最小和.记录:四边形不等式优化:还不是很懂这个。。。目前总结的话,遇到区间DP,先弄一个O(n3)O(n^3)O(n3),然后如果不可行,就直接放for(intk=s[i][j−1];k<=s[i+1][j];++k)for(intk=s[i][j-1];k&amp...

2018-10-17 11:31:55

Wannafly挑战赛26

链接:https://www.nowcoder.com/acm/contest/212/A作为「MisakaNetwork」的中心司令塔的LastOrder出事了,为了维持「MisakaNetwork」的正常工作,需要临时选出一个Sister作为中心司令塔。为了弥补能力上的不足,对于选出的Sister有一些要求。具体来说,平面上有n个Sister,问能否找到一个Sister作为...

2018-10-16 17:00:33

P3914 染色计数【树形DP】

题目描述有一颗N个节点的树,节点用1,2,⋯,N编号。你要给它染色,使得相邻节点的颜色不同。有M种颜色,用1,2,⋯,M编号。每个节点可以染M种颜色中的若干种,求不同染色方案的数量除以(10^9+7)的余数。输入输出格式输入格式:第1行,2个整数N,M。1≤N≤5000;1≤M≤5000接下来N行,第i行表示节点ii可以染的颜色。第1个整数k,表示可以染的颜色数量。接下来k个...

2018-10-09 21:09:54

HDU 5952 Counting Cliques【完全图爆搜】

题意:给你n个点m条边,挑选s个点构成完全图的方案数?分析:根本需要任何优化,直接爆搜。。。(还是需要一点的)建图很经典,G[min(a,b)]pushG[min(a,b)]pushG[min(a,b)]push_back(max(a,b))back(max(a,b))back(max(a,b)),这样方案就不会重复计数;爆搜:对于每一个点出发,询问孩子节点加入,是否同集合内的所有点都有边,...

2018-10-06 10:01:04

HDU 5950 Recursive sequence【矩阵快速幂||分块】

题意:f[n]=f[n−1]+2∗f[n−2]+i4f[n]=f[n-1]+2*f[n-2]+i^4f[n]=f[n−1]+2∗f[n−2]+i4,给你f[1],f[2]f[1],f[2]f[1],f[2],让你求f[n]?f[n]?f[n]?分析:把i4i^4i4拆开得到关于常数的一个递推式,如下图:PS:之后遇到后面带常数或者i的矩阵都可以这么解。。。我的写法:比较...

2018-10-06 09:48:55

牛客国庆集训派对Day4

A:把b=n;#include<cstdio>#include<bits/stdc++.h>#include<algorithm>#include<string.h>usingnamespacestd;intmain(){doublen;scanf("%lf",&n);printf("...

2018-10-05 10:41:01

HDU 4347 The Closest M Points【KD树】

题意:给你n个k维的点,再给你一个目标点x,让你查询离x最近的M个点?分析:【KD树模板】#include<cstdio>#include<bits/stdc++.h>#include<algorithm>#include<string.h>usingnamespacestd;constintN=50000

2018-10-04 11:03:10

NAIPC2016 I. Tourists【LCA】

题意:求一棵树上∑i\sumi∑i号节点到它所有因子的路径和;分析:预处理因子,LCA求树上两点距离(logn).#include<cstdio>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<cstrin...

2018-10-03 09:53:34

牛客国庆集训派对Day1

A:看样例过题;#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<vector>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL&gt...

2018-10-03 09:47:35

NAIPC 2016 Mountain Scenes【计数DP】

题意:给你n个方块,放置在w*h的矩形内,有多少种不同的方案?分析:dp[i][j]:截至到第i列放置了j个方块的方案数;dp[i+1][j+k]=dp[i+1][j+k]+dp[i][j];#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefunsigne...

2018-10-03 09:36:57

南京网络赛 B. The writing on the wall【矩形计数】

题意:n*m的一个矩形,其中有k个位置为空,问你该矩形内有多少小矩形?$1<=n,k<=1e5,1<=m<=100$分析:详解:不怎么容易理解!无空位置时:从上到下先枚举行i,从左到右再枚举列j,对于(i,j),那么右端紧靠着j列的矩形高度为1,2,3…i的各有1个,所以ans+=i;有空位置时:从上到下先枚举行i,从左到右再枚举列j,对于(i,j)...

2018-10-02 22:15:53

查看更多

勋章 我的勋章
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得