pretend_fal-CSDN博客

转载嫁给幸福 ——汪国真

嫁给幸福 ——汪国真有一个未来的目标总能让我们欢欣鼓舞就像飞向火光的灰蛾摆动着的是你不停的脚步在一往情深的日子里什么是甜什么是苦只知道确定了就义无返顾要输就输给追求要嫁就嫁给幸福

2017-10-20 16:17:28 1017

转载 p游戏

program xiyou(input,output);varq,w,e,r,t,y,u,i,o,p,a,lv,s,d,f,djingyan,jingyan,g,h,j,k,l,money,rwjingyan,zwq,fwq,zhiye,gong,fang,bisha,xsheng,dsheng,qian,shangyao,bigshangyao:longint;z,x,c,v,b,n,m:

2017-11-08 18:18:53 1505

原创 luogu P3202 [HNOI2009]通往城堡之路

就是把所有的都先设为最差值；然后一点点的往上调；然后就是贪心；定义： low : 从n到现在i b[i]<=a[i] 的个数； up : 从n到现在i b[i]>a[i] 的个数；我们找一个 low-up 最大的后缀；先上调；调的距离是 min ( a[i]-b[i] ) |a[i]>b[i]; 因为这样我们 up 增加的值可以用 low 增加的值来抵消；

2017-11-03 07:20:04 286

原创 luogu P1484 种树

这个题的解法我是在河南听过的；但是尴尬；没好好听，所以忘了；大致意思就是：选k个数，要求选的任意两个数不能相邻；大致是一种抵消的反悔方式；假设我们当前选了a[i]，那么如果我们下次选了a[i-1] and a[i+1]，那么他们的代价差是：a[i-1]+a[i+1]-a[i]; 所以我们把 a[i] = a[i-1]+a[i+1]-a[i]; then a[i-1] and

2017-11-03 07:18:45 391

原创 luogu P3119 [USACO15JAN]草鉴定Grass Cownoisseur

这道题显然要先 Tarjan 缩点预处理；这里就不多说了；之后的点都是缩点之后点集；我们考虑两种点： <1> 以 1 为起点可以直接到达的；我们这里叫它一类点； <2> 以该点为起点，可以直接到达 1 的；我们这里叫它二类点；所以我们先用 spfa 处理出来从 1 到这两种点的点权值；统计 ans 用；然后枚举每一个一类点；由于我们只能走一次反边；所以我们所要

2017-11-03 07:17:28 271

原创 luogu P1155 双栈排序

我们可以考虑在什么情况下会需要双栈； middle big small ;这样的情况需要双栈；因为我们 middle 入栈后；不能直接弹出；而是需要等待 small 进入；所以这时候需要把 big 压入另一个栈中；所以我们找这样的三个点；将 middle and big 连边；然后染色；如果有相邻的两个点的颜色一样；证明不合法；否则，模拟；#includ

2017-11-03 07:15:53 212

原创 luogu P2375 动物园

这个题是KMP；然后比较坑；我们记录当前这个位置的 sum[] 是从那个位置转移过来的；然后我们在求 next 的时候；顺便把这个数组更新；显然它会顺着位置前移；最多一位；#include "iostream"#include "stdio.h"#include "algorithm"#include "cstring"#define II int#define C

2017-11-03 07:14:25 175

原创 ST表

求最大值#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#define II int#define R register#define I 123456using namespace std;II f[I][30];II n,q;int main(){ scanf("%d%d",&n

2017-10-17 16:25:56 258

原创对拍

首先我们有三个程序，bao_li.cpp，zheng_jie.cpp，data.cpp全部运行后有三个exe然后写一个bat————————————-~~~————————————:again // 开始data.exe > input.txt // 从data中产生数据，放到input.txt中bao_li.exe < input.txt > bao_li.txt // 把input.txt中

2017-10-16 20:16:38 216

原创手工开栈

int size = 256 << 20; // 256MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p));

2017-10-16 14:03:36 536

原题位置： http://cogs.sxysxy.org:8080/cogs/problem/problem.php?pid=729（这个有SPJ）这个题是一个裸的网络流板子题，都说网络流难在建图，我只能说+1；这个题的建图方式有两种，但大同小异；<1> 超级源，超级汇，拆点，拆出的两个点之间为代表数（桌子数），代表和桌子之间的边是1，超级源（汇）与代表（桌子）之间是正无穷； <2> 超级源，超级

2017-09-29 17:21:46 237

原创 51nod P1096 距离之和最小

原题位置：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1096这道题还好吧，首先看到这道题的时候，也是懵逼了一会，然后我们知道有一个数学常识：两个点之间的点距离两个点的距离之和不变且最小；根据这个小常识，我们就可以想到所选的点一定在所给的线段上，所以我们进一步分析，发现两点之间的距离和是不变的，所以说，如果我在线段AB

2017-09-28 16:48:06 184

原创 luogu P2709 小B的询问

这道题是莫队，据说在离线区间查询上，莫队无敌，但是感觉还好吧；首先这道题是一个用来练手的好题，因为这是板子题；所以主要就是排序，然后while查询；至于排序方式：首先，应用分块思想，以查询左端点所在块为第一关键字，以右端点为第二关键字，均从小到大排序；然后就没有然后了；———————–分割线啊——————————–#include<iostream>#include<cstdio>#in

2017-09-25 08:41:08 258

原创 gcd&exgcd

其实这个东西可以背板子的；所以我打算直接上板子：———————————–begin———————————–gcdII gcd(R II a,R II b){ while (b) { R II c=b; b=a%b; a=c; } return a;}——————————–fen a~ fen a~ fen ge xian——————————

2017-09-24 16:50:40 565

转载博弈论

一．巴什博奕（Bash Game）：首先我们来玩一个比较古老的报数游戏。A和B一起报数，每个人每次最少报一个,最多报4个。轮流报数,看谁先报到30. 如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题，但是如果知道的人一定知道怎样一定可以赢。比如A先报数的话,那么B一定可以赢(这里假定B知道怎么正确的报数) B可以这样报数,每次报5-k(A)个数,其中k(A)是A报数的个数这样的话没

2017-09-24 15:34:54 502

原创素数筛

好像有叫做线性素数筛的东西，而且我不知道我的是不是；至于为怎么写这篇文章，其实就是背不过，然后以后复习用；鉴于以上目的，我就直接上代码了，挺好背的，背过就好了；———————————biu biu biu————————————-#include<iostream>#include<cstdio>#include<algorithm>#define II int#define R regis

2017-09-24 07:46:26 302

原创 51nod P1183 编辑距离

原题位置： https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1183这是一道经典的DP，所以我还是忘了转移方程，然后推的；令两个串为a串和b串；这道题的状态是f[i][j]代表a串前i个和b串前j个的最小编辑距离；然后就可以推了；首先，当a[i]==a[j]时，等价于f[i-1][j-1]，所以直接赋值就好了；当a[i]!

2017-09-24 07:26:12 152

原创 vijos P1571 笨笨的导弹攻击

原题位置： https://vijos.org/p/1571这道题说是个经典DP，但是感觉还好吧，一开始感觉和NOIP花匠是一样的，但是发现自己找不到状态，因为我们要知道当前这个导弹在抽出的序列中的奇偶位置，所以自然而然把原来的状态定义改了，但是还是b[1][i]和b[2][i]，但是定义为b[1][i]是i这个位置是基数位置时的最长序列，b[2][i]是i这个位置是偶数位置时的最长序列，那么就有转

2017-09-23 15:04:03 307 1

转载一个在网上找到的用C++写的游戏

#include <iostream>#include <cstdlib>#include <ctime>using namespace std;int sc[10],j=1,hp=100,jq=200,m4,m4d,ak,akd,us,usd,de,ded,ka,fi,pk,pkd,mi,mid,ly,lyd,l1,l1d;bool b=true;string s;void SHOP

2017-09-22 10:54:37 2450

原创 luogu P2401 不等数列

原题位置: https://www.luogu.org/problem/show?pid=2401这个题说是个DP,但是感觉想一个递推式;先把式子摆出来: f[i][j] = f[i-1][j-1] * (i-j) + f[i-1][j] * (j+1) ;那我们就要说一下这是为什么了；首先我们要明确f[i][j]代表前i个人j个小于号；所以我们可以假设我们有一种情况是： @<@>@<@<@>@<@

2017-09-21 15:30:15 189

原创 luogu P1167 刷题

原题位置： https://www.luogu.org/problem/show?pid=1167这道题其实很简单，但是我之所以要写这篇题解，是因为有一个点需要掌握；就是如果两个时间差不好算，可以找一个比较小的时间来作为底；然后，分别计算两个时间距离底的差，然后做差，得到答案；cpp#include<iostream>#include<cstdio>#include<algorithm>#de

2017-09-20 17:14:59 331

原创 luogu P1095 守望者的逃离

原题位置： https://www.luogu.org/problem/show?pid=1095这个题好久之前就见过，当时写的贪心，但是没A；刚刚换成了DP，A了；所谓DP，我们可以把这个过程看做两个人在一起跑，只是跑的方式不同；一个跳一下休息一会，一个一直跑；所以这个东西就可以分成两个DP；cpp#include<iostream>#include<cstdio>#include<algor

2017-09-20 15:50:13 299

原创 luogu P2619 奶牛工资

原题位置： https://www.luogu.org/problem/show?pid=2619这道题是个贪心，怎么说是贪心呢，就是先选大的，后考虑小的；千万不要把上句话的意思理解歪了，一开始我就理解歪了，然后华丽丽地TLE了；其实就是for，然后如果当前这个值可以被选，就选到不能再选这个值为止；还有一个小技巧，就是我们定义一个值，等于c，然后用这个值减，知道小于等于0，这样子比一直加到c好处理多

2017-09-20 10:50:07 400

原创 luogu P2890 便宜的回文

题目连接： https://www.luogu.org/problem/show?pid=2890这个题的题解比较少；首先，这个题我一上来就想到了一道白皮上的DP；那道题的转移方程是if(a[i]==b[j]) f[i][j]=f[i-1][j-1];else f[i][j]=min(f[i-1][j],f[i][j-1])+1;大概就是当前a串字母和b串字母相同时，等价于前一个位置相同；否则就改变

2017-09-20 09:10:05 319

原创天天和树

天天和树tree.in/.out/.cpp【问题描述】个树由 n 个点，n 1 条边组成，结点编号为 1:::n。树上任意两个点之间路径唯一。定义一个点到一条路径的距离为：该点到路径上最近的一个点需要经过的边的数量。现在想知道怎样选两个点确定一条路径，使得距离这个路径最远的点尽量近。要求你输出距离路径最远的点距离路径的距离。【输入格式】第一行个整数 n。其中 1<=n<=100,000 接下来 n-

2017-09-16 15:18:16 263

原创 NOIP2015 信息传递

题目描述有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请

2017-08-09 09:47:34 1103

原创 luogu P1970 花匠 (NOIP)

题目描述花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具体而言，栋栋的花的高度可以看成一列整数h1,h2..hn。设当一部分花被移走后，剩下的花的高度依次为g1,g2..gn，则栋栋希望下面两个条件中至少有一个满足：条件 A：对于所有g(2i) > g(2i-1)

2017-08-03 21:26:29 428

原创 luogu P2697 宝石串

题目描述有一种宝石串，由绿宝石和红宝石串成，仅当绿宝石和红宝石数目相同的时候，宝石串才最为稳定，不易断裂。安安想知道从给定的宝石串中，可以截取一段最长的稳定的宝石串，有多少颗宝石组成。请你帮助他。绿宝石用‘G’表示，红宝石用‘R’表示。输入输出格式输入格式：一行由G和R组成的字符串输出格式：最长的稳定的宝石串有多少颗宝石组成输入输出样例输入样例#1：GRGGRG输出样例#1：4说明RGGR为

2017-08-03 17:25:38 1011 4

原创并查集

并查集，顾名思义，就是把元素并到一个集合里，然后还可以查找某个元素在哪一个集合里；这其实就是并查集了，思想很简单，而且很好写，不过很少会有题专门考并查集，但是，不可否认的是，并查集是一个极为有用的辅助算法，或者说是思想，再或者是一种实现方式；并查集有几个主要操作：<1> 初始化：我们会把每一个点放入一个单独的集合，即fa[x]=x，代表x所在的这个集合的代表元素是x；<2> 查询：我们每一个集合的表

2017-08-02 21:49:42 202

原创 NOIP总结

动态规划：线性dp，区间dp，树形dp*，线段树优化，前缀和优化，单调队列优化，滚动数组优化内存。（状压dp，数位dp，斜率优化，矩阵乘法加速）数据结构：堆、栈、队列、双向链表(约瑟夫环)，树状数组，线段树。（树剖，主席树，平衡树，树套树，kd-tree，动态树）图论：MST，最短路，Tarjan（强联通分量，割点割边），并查集，拓扑排序，2-sat，差分约束，二分图（判定是否是二分图，二分图最大匹

2017-08-02 21:15:48 426

原创 luogu P1073 最优贸易

题目描述C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到

2017-08-02 21:06:38 472

原创 Tarjan 求割边割点

Tarjan是多种算法的总称，因为Tarjan这个人太牛*了，那我们今天就来看一看Tarjan神的算法之一：Tarjan求割边割点；首先我们要清晰什么是割边割点：割点：首先我们有一张连通图：对于这张图，显然它是一张联通图，那么割点的定义就是：“某一个点A，若删除这个点并且删去这个点所练的边，那么这张图的强联通分量增多”；所以我们可以根据定义来推断出上图中的点3和点4是该图的割点，因为原图中的一

2017-08-02 20:31:16 804

原创 MST （最小生成树）

我们有一个无向图，然后要求生成一棵边权之和最小的树首先，我们可以暴力，枚举每一条边选不选，然后计算边权和，更新答案，必定会TLE，这是显然的；那么我们需要一种较为高效的算法来解决这种问题，这时候，我们就可以学一下MST（最小生成树）的Kruskal算法了这个算法用到了一些贪心的思想，就是我们每次选当前待选的边权最小的那条边，如果这条边符合性质，我们就把它加入到树中，否则，我们换下一条边，一直重复这个

2017-08-01 21:37:33 8156

原创 luogu P1318 积水面积

题目描述一组正整数，分别表示由正方体迭起的柱子的高度。若某高度值为x，表示由x个正立方的方块迭起（如下图，0<=x<=5000）。找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。如图：柱子高度变化为 0 1 0 2 1 2 0 0 2 0图中蓝色部分为积水面积，共有6个单位面积积水。输入输出格式输入格式：两行，第一行

2017-08-01 20:52:44 401

原创 luogu P1525 关押罪犯

题目描述S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。每年年末，警察局会将本年内监狱中的所有冲突

2017-08-01 17:11:56 474

原创 luogu P1759 通天之潜水

题目背景直达通天路·小A历险记第三篇题目描述在猴王的帮助下，小A终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小A有n个潜水工具。由于他还要背重重的背包，所以他只能背m重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有v阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。输入输出格式输入格式：三个

2017-08-01 11:48:16 301

原创 Tarjan

Tarjan是多种算法的总称，因为Tarjan这个人太牛X了，那我们今天就来看一看Tarjan神的算法之一：Tarjan求割边割点；首先我们要清晰什么是割边割点：割点：首先我们有一张连通图：对于这张图，显然它是一张联通图，那么割点的定义就是：“某一个点A，若删除这个点并且删去这个点所练的边，那么这张图的强联通分量增多”；所以我们可以

2017-07-31 21:41:45 276

Peipei