4 河渔船

尚未进行身份认证

我要认证

成长的小垃圾

等级
TA的排名 1w+

P1278 单词游戏

题目链接记忆化搜索。#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#define LL long longusing namespace std;const int M=(1<<17);int f[M][20],n,len[20],ans;char s[20]

2017-11-09 15:49:47

模板汇总

本博客所有模板都经过测试,保证正确。归并排序#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;cmath&gt;using namespace std;const int N=1e5+77;int a[N],n,tmp[N];void Sort(int l,int r){ if(l==r) return;

2017-11-08 14:44:23

luogu 模拟题 赤夜

做法一:对于每一个点的修改,顺序改变一下是不会影响结果的。我们离线做,可以一个点一个点的修改。 (还是过不了啊,仍然T)qwq。 做法二: 我们尽量把实际的操作搞成标记,不操作,以降低复杂度。 我们用三个数组实现。 pushup[x]表示x周围的点对x的影响,tag[x]记录的是x这个点操作的次数,sontag[x]表示的是x所有的儿子节点的操作次数。 那么修改时:pushup[x]+=

2017-11-08 14:25:55

luogu 模拟题 青蛙叫

等差数列。 因为直接算的话可能会有较大的精度丢失(个人认为), 所以用到二分,二分有多少项。 时间复杂度O(nlogT)#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long longusing namespace std;const

2017-11-08 11:36:50

P1078 文化之旅

题目链接搜索过的。 不过中间加上一个类似spfa里面的松弛优化。 数据好像比较水。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int M=107*107;int n,m,s,t,k;int b[109][

2017-11-08 09:13:51

洛谷八连测 #R8

题目链接T1答案是求C1x+1∗Ck−1n−1/Ckn+xC_{x+1}^1*C_{n-1}^{k-1}/C_{n+x}^k 取得最大值时的x值。 数学题。 化简,求单调性。T2对每一门成绩都建一棵树。 每条边都加一条反向边。 能够通过正向边到达的点都是比自己成绩低的,反向边则是比自己高的。 最好成绩是只有三门成绩搜比自己高时才比自己高。 最坏成绩是只有三门都比自己低时才比自己低。

2017-11-07 21:02:51

洛谷 NOIP 模拟 DAY2

T1 入阵曲题目链接 n^4的做法很容易想到。 100分的做法一开始没想到; 我们枚举两行,然后求这两行之间的和时,记录下和的种类和数量,求到第j列的时候,前面有几列取模k得到的数与当前求得的一样时,那么这两列之间的和一定是k的倍数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#includ

2017-11-07 20:51:12

洛谷 NOIP 模拟 DAY1

T1题目链接 每次新产生的兔子一定是前面的兔子生的。 先预处理出菲波那切数列,然后用a-f[x]就是a的父亲。(f[x]是小于a的最大的)#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long longusing namespace std;const int N=30

2017-11-07 17:07:44

洛谷八连测 #R6

题目链接 T1 100做法:dp[i][j]表示后一个串匹配到了i,lcs的长度达到了j,第一个串最早能在什么地方结束。转移维护从某个位置开始的第一个某个字符在哪里。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long longusing namespace std;

2017-11-07 11:36:52

洛谷八连测 #R7

LISTT1T2T3题目链接T1T1 每次spfa(或者bfs),时间复杂度O(spfa*Q); 每次先把每一个查询的特殊点入队,距离为0; spfa或者bfs即可。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cti

2017-11-06 16:29:55

P2985 [USACO10FEB]吃巧克力

题目传送二分答案+贪心需要注意的问题是,最后上下的巧克力要在最后一天吃完! 因为这个问题,调了2个小时!#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath> #define LL long longusing namespace std;int n,d,a[50009

2017-11-05 17:29:55

P3017 [USACO11MAR]布朗尼切片Brownie Slicing

题目传送 二分答案+贪心+前缀和优化对于二分的答案x,我们对于每一条,先假设宽为1,看看能不满足分为不小于x的b块,如果不满足,宽度就加宽,如此处理即可。 一开始循环中的终止条件写错,调了好长时间。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath> #define L

2017-11-05 15:53:33

两道贪心题

一、 P1809 渡河问题 二、 P1325 雷达覆盖#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long longusing namespace std;const int N=100009;int n,a[N];LL ans;int main(){

2017-11-05 14:23:42

刷题#R12

T1 贪心模拟 从右往左,遇见m是1的位,有选或者不选两种操作:如果这一位是负数,那肯定不选更优,把这一位的二进制看做0,那么前面就可以任意选;如果选,那么sum+a[i],继续向前扫。 T2 二分答案 +DP 二分两个数之间的差的最大值 F[i]表示i不改变的最小修改的元素个数 f[i] = min(f[j] +(i-j-1), i-1) abs(A[j]-A[i]) < 二分出来

2017-11-05 13:56:38

刷题#R6

题目链接 T1 画图可以找出规律; 所有有环的都仅有两种情况, 而树上的方案数为n种; 先跑出带环的图记下乘几个2,然后在与所有的树相乘 如果出现一个联通图中有两个及以上的环时,无论如何也不能匹配成功,那么方案数就是0 期望得分 100 T2

2017-11-04 21:38:52

刷题#R14

三向城 题目描述 三向城是一个巨大的城市,之所以叫这个名字,是因为城市中遍布着数不尽的三岔路口。(来自取名力为0的出题人) 具体来说,城中有无穷多个路口,每个路口有唯一的一个正整数标号。除了1号路口外,每个路口都连出正好3条道路通向另外3个路口:编号为x(x>1)的路口连出3条道路通向编号为x*2,x*2+1和x/2(向下取整)的3个路口。1号路口只连出两条道路,分别连向2号和3号路口。 所

2017-11-04 18:56:35

刷题#R13

纸牌 题目描述 在桌面上放着n张纸牌,每张纸牌有两面,每面都写着一个非负整数。你的邪王真眼可以看到所有牌朝上的一面和朝下的一面写的数字。现在你需要将一些牌翻过来,使得所有牌朝上的一面中,至少有一半(≥n/2)的数字是一样的。请你求出最少需要翻几张牌,或者判断无解。 注意:在翻牌的时候,你不能把牌扔掉,不能偷偷把别的牌放进来,也不能用笔涂改牌上面的数字。输入格式 第一行包含一个整数n,

2017-11-04 18:48:08

刷题#R11

卖书 问题描述 大 C 开了一家 noip 辅导资料店,每本资料售价 5 元,且每人限购一本。前来买书的人络绎 不绝,他们带着 5 元,10 元和 20 元。可是由于启动资金有限,大 C 进完货之后手上已经没 有钱了,所以他只能用前面收的钱找钱。现在大 C 想知道他能不能成功的找钱。输入格式 第一行一个整数 n 表示来买书的人数 第二行 n 个整数表示每个人身上带的钱数,数据保证一定是

2017-11-04 08:17:41

刷题#R10

T1 理解题意,模拟即可。 T2 and是递减的,or是递增的。 用倍增预处理。 然后枚举左端点,二分右端点的范围或者用倍增求右端点的范围。 建议用倍增法,因为二分好像很慢,我的二分T掉三个点,二倍增查找0.1秒。 T3 树上dp+dfs来优化。 分析:显然的,树形dp,状态也很好想到:f[i][j]表示以i为根的子树收集到j个果子的方案数.转移的话就相当于是背包问题,每个子节点可

2017-11-03 21:17:05

刷题#R9

立方体 cube.in/.out/.cpp 【问题描述】 在 n 维空间中,一个单位立方体由 2^n 个点组成。 他们的坐标形如 (x 1 ,x 2 ,…,x n ),x i ∈ {0,1}。 定义 n 维空间中两点的距离为其曼哈顿距离,点 p (p 1 ,p 2 ,…,p n ) 与点 q (q 1 ,q 2 ,…,q n ) 的距离为 ∑ n i=1 |p i −

2017-11-03 11:10:03

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!