河渔船-CSDN博客

原创模板汇总

本博客所有模板都经过测试，保证正确。归并排序#include<iostream>#include<cstdio>#include<cstring>#include<cmath>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 535 3

原创 P1417 烹调方案

题目传送做法：贪心+01背包这里贪心的方法是很重要的。类似的题目还有P1012 拼数和NOIP 国王游戏贪心的原则 a1−(t+c1)∗b1+a2−(t+c1+c2)∗b2>a2−(t+c2)∗b2+a1−(t+c1+c2)∗b1a1-(t+c1)*b1+a2-(t+c1+c2)*b2>a2-(t+c2)*b2+a1-(t+c1+c2)*b1 得到 c1∗b2<c2∗b1c1*b2<c2*b1

2017-10-26 11:37:39 265

原创对拍

有时候我们对于一个题先写了不确定的貌似是正解的程序，然后又写了保证正确的暴力。那么我们怎样来确定我们想的正解对不对呢？对拍。对拍我们需要这样几个文件： data是数据生成器，right是暴力，test是待定正确程序。举一个a+b的例子，里面是这样写的。data.cpp#include<iostream>#include<cstdio>#include<ctime>#include

2017-08-12 09:09:02 247

原创 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 523

原创 luogu 模拟题赤夜

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

2017-11-08 14:25:55 392

原创 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 279

原创 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 321

原创洛谷八连测 #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 367

原创洛谷 NOIP 模拟 DAY2

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

2017-11-07 20:51:12 251

原创洛谷 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 218

原创洛谷八连测 #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 263

原创洛谷八连测 #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 497

原创 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 271

原创 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 552

原创两道贪心题

一、 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 186

原创刷题#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 238

原创刷题#R6

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

2017-11-04 21:38:52 248

原创刷题#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 290

原创刷题#R13

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

2017-11-04 18:48:08 612

原创刷题#R11

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

2017-11-04 08:17:41 460

原创刷题#R10

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

2017-11-03 21:17:05 226

原创刷题#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 380

原创刷题#R8

T1 这是一个更相减损。出现的所有的不同的数就是更相减损过程中出现的；直接这样做的话，会T或者爆；再进一步分析一下，就会发现，我们可以把更相减损优化为辗转相除，因为多几次更相减损就是辗转相除，那么不同数的个数在辗转相除中就是每次的a/b，因为a只有减损a/b次才会达到b，a%b的状态，这之间的数是递减的，不会出现重复。T2 50分，我们可以倒着加边，添加进新的边时，用并查集维护，合并

2017-11-03 08:05:21 221

原创刷题#R5

星空【问题描述】你是能看到第一题的 friends 呢。 ——hja 点点星空是一张n× m的棋盘，左下角有颗星星。尤和千每次可以将星星向右边、右上、上边移动一格。尤和千轮流移动，尤先手，问尤是否必胜？【输入格式】多组数据，每行两个整数n,m，当 n=m=0 时数据停止。【输出格式】对于每组数据，如果尤必胜输出“Yuri” ，否则输出“Chito” 。【样例输入】

2017-11-02 14:58:30 364

原创刷题#R7

集合集合【问题描述】给定一个可重集合，一开始只有一个元素 0 。然后你可以操作若干轮，每一轮，你需要对于集合中的每个元素 x 进行如下三种操作之一： 1 、将 x 变为 1 + x 。 2 、将 x 分裂为两个非负整数 z y, ，且满足 z y x + = 。 3 、什么都不做。每一轮，集合中的每个元素都必须进行上面三个操作之一。对于一个最终的集合，你的任务是判断至少进行

2017-11-01 15:59:22 893

原创刷题#R4

题目链接 T1 模拟即可，但是要仔细一点。 T2 素数筛，前缀和，简单二分就可以过。 T3 30分floyed暴力。 T1#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=100009;char s[N];int n,sl[N

2017-10-31 13:58:20 385

原创刷题#R3

题目链接 T1 60分可以写一些特判和暴力。 100分dp，解释一下dp的做法。我们用f[i][j]表示跳了i次，到第j层楼然后跳下去，需要的最小花费。还需要知道一个策略，如果跳过的楼是一样的，那么以高度升序或者降序肯定比乱跳更优。那么我们先将所有的楼按照高度升序或者降序排一下，然后dp就可以了。根据f数组的定义，那么f[0][i]=c[i]；然后有 f[i][j]=

2017-10-30 17:11:45 261

原创刷题#R1

立方数(cubic) Time Limit:2000ms Memory Limit:128MB题目描述 LYK定义了一个数叫“立方数”，若一个数可以被写作是一个正整数的3次方，则这个数就是立方数，例如1,8,27就是最小的3个立方数。现在给定一个数P，LYK想要知道这个数是不是立方数。当然你有可能随机输出一些莫名其妙的东西来骗分，因此LYK有T次询问~输入格式(cubic.in)

2017-10-29 11:45:47 281

原创洛谷10月月赛R2·浴谷八连测R4

Problem A. 逃避 (nigeru.c/cpp/pas) Input file: nigeru.in Output file: nigeru.out Time limit: 1 second Memory limit: 8 megabytes给定一篇只含有大小写字母，空格以及 ′ . ′ （不含引号）的长度为 L 的文章。文章被若干个 ′ . ′ 划分成若干个句子，句子被若

2017-10-28 15:33:11 332

原创洛谷10月月赛R2·浴谷八连测R3 -Chtholly-

T1 浮游大陆的68号岛 T2 Chtholly Nota Seniorious T1 这个题还是比较简单的，毕竟是第一题。首先，不要想复杂的数据结构，因为中间没有修改值，蒟蒻就是因为高大上的数据结构不精通，所以没有走弯路喽。用一个前缀和来记录储物点的物件数目； dis数组记录到1点的距离； cost数组记录前i个储物点的物品都搬到1点的花费。接下来就是模拟了。分为三种情况

2017-10-27 15:31:47 446

原创 P1868 饥饿的奶牛（区间问题）

题目传送和 P1280 尼克的任务差不多不重叠的区间最大覆盖。 dp解法。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define LL long longusing namespace std;const int M=3000009;const i

2017-10-27 10:53:30 419

原创最多区间

原题请允许我起个很土的名字。题目大意：有多个活动，每个活动都有开始和结束的时间，在同一时刻不能同时参见多个活动，问最多能参加多少个活动？对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。贪心。按照r从小到大排序，肯定优先选择r小的，这样能给后面留出更多的空间。#include<iostream>#include<cstdio>#include<cstring

2017-10-26 16:59:37 271

原创 P1736 创意吃鱼法

题目传送这个题和最大正方形差不多，是它的升级版。不同之处是这个题有约束条件：“如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼” 那么对于以i,j为右下角的，我们处理出b[i][j]表示从i,j开始左最远有多少个连续的0，c[i][j]表示从i,j往上最多有多少个连续的0，那么就有f[i][j]=min(f[i−1][j−1],min(b[i][j−1],c[i−1][

2017-10-26 15:52:31 329

原创 P1855 榨取kkksc03

题目传送二维费用的01背包。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#include<cstdlib>#define LL long longusing namespace std;int n,m,T,f[209][209];int w1[109],w

2017-10-26 14:18:39 400

原创 P1508 Likecloud-吃、吃、吃

题目传送dp或者记忆化搜索都可以过吧。但是我的记忆化搜索莫名其妙的WA了。 dp轻松AC.#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#include<cstdlib>#define LL long longusing namespace std;in

2017-10-26 11:10:18 197

原创 P1282 多米诺骨牌

题目传送最终还是看了题解。我一开始想的dp方程的两个状态分别表示第i个骨牌，翻转j次，记录的值为最小的差，最后扫一遍f[n]，应该是可以得出答案的，然而这种做法真的可以吗？？？正确的解法：我们用f[i][j]表示到第i个骨牌，得到差值为j，最小的翻转次数。那么转移方程就出来了 f[i][j]=min(f[i−1][j−(a[i]−b[i])],f[i−1][j+(a[i]−b[i])]+1

2017-10-26 10:15:20 414

原创 P1280 尼克的任务

题目传送我们用f[i]表示前i-1分钟最多空闲了多少分钟。那么对于每个任务，f[i+t[i]]=max(f[i+t[i]],f[i]); 而如果i处没有任务，那么f[i+1]=f[i]+1#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#include<cstd

2017-10-26 09:18:56 253

原创 P2066 机器分配

题目传送这个题是简单的dp+递归输出。注意一个问题，是要求字典序最小的，所以在递归时，倒着循环，而且找到一个合适的值就要break，否则就会在后面将前面的值覆盖。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>#include<cstdlib>#define LL

2017-10-26 08:07:32 281

原创 NOIP 模拟题天上掉馅饼

C 天上掉馅饼文件名输入文件输出文件时间限制空间限制 bonus.pas/c/cpp bonus.in bonus.out 1s 128MB题目描述小 G 进入了一个神奇的世界，在这个世界，天上会掉下一些馅饼。今天，天上会随机掉下 k 个馅饼。每次天上掉下馅饼，小 G 可以选择吃或者不吃（必须在下一个馅饼掉下来之前作出选择，并且现在决定不吃的话以后也不能吃）。馅

2017-10-25 17:00:03 517

原创 NOIP 模拟题国际跳棋

B 国际跳棋文件名输入文件输出文件时间限制空间限制 chess.cpp/c/pas chess.in chess.out 1s 512MB题目描述国际跳棋是一种古老的棋类游戏，远在古埃及法老时期就已存在，现代国际跳棋是在 12 世纪定型的。国际跳棋是由各国的民族跳棋演变而来，其历史源远流长。简化版（与标准国际跳棋略有差别）国际跳棋规则： • 国际跳棋的棋盘由 10 × 1

2017-10-25 16:50:52 1587

空空如也

空空如也