Loi_whales-CSDN博客

原创 NOIP前夕模板整理第二弹：数据结构

1、并查集例题：家族然而其实并查集的用处还有很多#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;int fa[100000];int find(int x){ return fa[x] == x?x:fa[x] = find(fa[

2016-11-13 21:51:39 378

原创 NOIP前夕模板整理第一弹：图论

最短路模板：SPFA 、 dijkstra 、floyd SPFA和dijsktra之前整理过了，直接放链接吧点这里O(∩_∩)O floyd用处很广，可以用来求多源最短路，例题codevs1077 多源最短路这里放一下核心代码 for(int k = 1 ; k <= n ;k++) for(int i = 1 ; i <= n ; i++)

2016-11-12 21:50:48 428

原创第一篇博客献给留言板

第一篇博客也得确实有些晚，而且不确定以后还写不写，毕竟以前也是不怎么写博客的，虽然也并没有什么人，但基于传统（外加第一篇不知道写什么），开此留言板。 RP++，over。

2016-10-20 21:04:44 890 5

原创 poj2376 Cleaning Shifts

题目是每只奶牛负责一个时间段，让你求覆盖完全部的时间段最少需要多少只奶牛，如果不能覆盖完输出“-1”，但是很多人理解成把整个区间都覆盖完需要多少个小区间，其实是覆盖完所有点需要多少的小区间，例如： 2 10 1 5 6 10 这样是可以覆盖完所有点的，所以输出2，而不是-1. 这个题目的思路是贪心，按起点由小到大排序，同一起点的，按能够延伸的长度由长到短排序，这样我们从起点开始，每次选择能

2017-10-27 10:15:43 289

原创 poj1111 Image Perimeters

题目大意：求联通块的周长（八联通），每个块的周长为4。我的做法是求出联通块的个数cnt，这样总的周长是cnt*4，但是有些块的某些边不能计算在内，有些块整个周长都不能计算在内，处理这个问题的方法是找一个块能够与多少块直接相连（最多有四个，上下左右），假设与x个块相连，再把每个块的x加起来，就是不需要计算在内的边数和，这样再用cnt*4减去就是真正的周长了。#include <cstdio>#i

2017-10-14 17:11:22 315

原创 poj3723 Conscription

这个题目大意就不写了，注意男生和女生区分的话可以：（女：1,2,3…；男：n+1,n+2,n+3…），把两人之间的亲密度当做点与点之间有权值，就是求最大生成树，把权值换成负的，就是求最小生成树了。数据输入量很大，要用scanf，不然会TLE。（poj教你养成随手scanf和printf的习惯，因为poj的题目老是卡这个）代码如下：#include <cstdio>#include <ios

2017-10-13 16:17:33 251

原创 poj2457 Part Acquisition

题目大意：给你一些点和边（单向边），所有边权都相等，问从第一个点到最后一个点最少经过多少点（包含初始和结束点），并把这条最短路的路径上的点输出来。当然，把题目直接翻译过来的话不是上述内容，你需要转换成上面的意思，这是一道最短路还原路径的典型题（模板题），具体实现如下：#include <cstdio>#include <iostream>#include <cstring>#include

2017-10-13 11:14:12 307

原创 poj1007 DNA Sorting

题意是给你一些DNA序列，让你计算每个序列里某个字母后面有多少个比它小的字母，加起来作为一个参数（就是求逆序数），然后按照这个参数从小到大的顺序排列这些DNA序列并输出，如果大小相等，按原来顺序输出。按题意模拟就好（表示看错题意WA了好多次T_T）#include <cstdio>#include <iostream>#include <algorithm>#include <cstrin

2017-10-13 09:01:57 275

原创 poj1002 487-3279

题目大意：就是给你一些符号和大写字母对应的数字，要求全部转化成电话号码XXX-XXXX的形式，其中X只能是数字，这些字符串的长度不等，里面会有一些‘-’，最后要求是找出出现次数>1的电话号码，输出号码和重复出现的次数，如果没有重复的号码，就输出：“No duplicates.” WA的同学注意“No duplicates.”不要漏掉“.”。 TLE的同学注意把cin和cout改成scanf和pr

2017-10-12 20:59:00 223

原创 poj1182食物链

Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是”1 X Y”，表示X和Y是同类。第二种说法是”2 X Y”，表示X吃Y。此人对N个动物，用上述两

2017-10-11 21:42:20 234

原创 poj2431 Expedition

这个题注意几点： 1、《挑战程序设计竞赛》上的代码并不能适用此题，这里的a[i]是到终点的距离 2、注意要排序！这里给出的a[i]并不一定是按顺序给的（只有WA过才会明白有多坑）#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace

2017-10-11 19:11:45 325

原创 poj 3069 Saruman's Army

题目大意就不说了方法是：先排序，然后从第一个点开始往右R个长度看看能覆盖多少点，再从最远能覆盖到的点P开始继续往右R个单位长度，这是点P能覆盖的范围，找到所有这些点做标记，就是最少能标记的点具体实现如下：#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace s

2017-10-11 08:24:32 216

原创 POJ3617 Best Cow Line

注意最后输出的时候每80个就要换一次行（PE两次后的教训之认真看题）#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n;char s[20000],T[20000];int main(){ scanf("%d",&n);

2017-10-10 21:23:06 240

原创 poj1852 Ants

这题考察思维的灵活性，此外这份代码用cin和cout会超时（orz）#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <cmath>using namespace std;int a[1000000];int ans[1000000];int main(){

2017-10-10 19:20:57 202

原创 poj 2709 Painter

题目翻译：杂货店出售一种由 N（3<=N<=12）种不同颜色的颜料，每种一瓶（50ML），组成的颜料套装。你现在需要使用这 N 种颜料；不但如此，你还需要一定数量的灰色颜料。杂货店从来不出售灰色颜料——也就是它不属于这 N 种之一。幸运的是，灰色颜料是比较好配置的，如果你取出三种不同颜色的颜料各 x ml，混合起来就可以得到 xml 的灰色颜料（注意不是 3x

2017-10-10 16:27:21 225

原创 poj2488 A Knight's Journey

题目大意是让你求出这个马不重复地跳完整个棋盘的字典序最小的路线，如果不能跳完整个棋盘，就输出impossible。这是一道搜索题，马能走的有八个方位，想要使字典序最小，我们就先从字典序为A开头的地方搜，不行再搜B，这样搜到的第一个答案就是字典序最小的答案或者没有答案。代码如下：#include <cstdio>#include <cstring>#include <iostream>#

2017-10-10 07:18:44 188

原创洛谷P1137 旅行计划

题目描述小明要去一个国家旅游。这个国家有N个城市，编号为1～N，并且有M条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于

2017-08-18 10:47:09 307

原创 bzoj4562: [Haoi2016]食物链

Description如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号 M条能量流动关系形如 a1 b1 a2 b2 a3 b3 …… am-1 bm-1 am bm 其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链 Input第一行两个整数n和m,接下来m

2017-08-16 14:41:54 422

原创 codevs2744养鱼喂妹纸

题目描述 Description 在某岛国，大多数居民都是渔民，这个国家的所有城镇都沿直线分布在海边。渔民们捕获大量的海鱼，但就象世界上大多数的渔民一样，他们并不喜欢吃鱼，所以他们决定从天朝收养一些贫困家庭的女孩纸，让她们来帮着吃鱼，顺便（和谐），国家规定每个城镇收养的贫困妹纸数量必须相等，这样才能建设和谐社会。一条又长又直的公路贯穿整个海岸将所有的城镇连接了起来，所以

2017-08-12 09:29:06 310

原创 codevs2173忠诚（st表）

题目描述 Description 老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时

2017-07-18 20:00:57 368

原创 codevs1373 射命丸文

引用块内容题目描述 Description 在幻想乡，射命丸文是以偷拍闻名的鸦天狗。当然，文文的照相机可不止能够照相，还能够消除取景框里面所有的弹幕。假设现在文文面前有一块N行M列的弹幕群，每一个单位面积内有分值有num[i][j]的弹幕。相机的取景框可以将一块R行C列的弹幕消除，并且得到这一块区域内所有弹幕的分值(累加)。现在文文想要取得尽可能多的分值，请你计算出她最多能够得

2017-07-18 14:32:01 360

原创倍增lca学习笔记（codevs2370小机房的树题解）

lca即为最近公共祖先，求两个点的lca有两种方法，一是暴力求解，二是倍增求解。这里主要讲倍增求解lca，时间复杂度nlogn。主要思想：首先用一个数组anc[u][i]表示从u节点跳2^i步到得位置，deep[]表示深度关于anc数组有一个递推公式：anc[u][i] = anc[anc[u][i-1]][i-1]; 这个公式就是先从u点跳2^i-1步再从anc[u][i-1]这个

2017-07-16 15:13:05 323

原创 codevs1215 迷宫

用dfs做的，还不嫌累的用if，当然bfs也很好做（代码很丑）。#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int n;bool flag;bool vis[50][50];char s[50][50];void dfs(int x,int

2017-02-08 21:24:12 386

原创 codevs1294 全排列

dfs入门题目#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n;int a[5000];bool vis[5555];void dfs(int x){ if(x > n) { for(int i = 1; i <= n; i ++)

2017-02-08 21:20:06 93

原创埃氏筛法与欧拉筛法

一、埃氏筛法时间复杂度：O（nloglogn）埃氏筛法的主要思想就是把小于√n的素数的倍数筛掉，剩下的就是素数具体代码实现如下：int prime[MAXN],n;void Prime(int n){ int cnt =0; memset(prime,1,sizeof(prime)); prime[0]=prime[1]=0;//表示不是素数 for

2016-11-15 11:42:39 1130

原创 codevs1506传话（tarjan）

这个题多种解法，我用tarjan又写了一遍#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <stack>using namespace std;const int MAXN = 2000;int n,m,to[MAXN<<1],head[MAXN],cd[MAXN],b

2016-11-11 14:16:42 433

原创 Codeforces Round #378 (Div. 2)A题

A. Grasshopper And the StringOne day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in

2016-11-11 11:34:21 335 1

原创 codevs2404糖果

题目描述 Description 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的

2016-11-11 11:23:58 322

原创 codevs1242布局【USACO】

题目描述 Description 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过

2016-11-11 11:11:12 366 1

原创 codevs1384黑色星期五【USACO】

题目描述 Description 13号又是星期五是一个不寻常的日子吗? 13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13 日落在星期一,星期二……星期日的次数.这个测试从1900年1月1日到 1900+n-1年12月31日.n是一个非负数且不大于400. 这里有一些你要知道的:1900年1月1日是星期一.4,6,11和9月有30天.其他月份除了2月有31天.

2016-11-11 10:51:16 667

原创 noip2015day1 T1神奇的幻方

直接放代码吧，以前写的，十分暴力#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int w[100][100];int main(){ int n; scanf("%d",&n); w[1][n/2+1] = 1;

2016-11-09 21:23:30 364

原创 noip2015D1T2信息传递

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

2016-11-09 21:12:52 322

转载搞懂树状数组

转载自：http://blog.csdn.net/int64ago/article/details/7429868 一、树状数组是干什么的？平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N

2016-11-07 15:23:37 309

原创 poj1308&&openjudge310:Is It A Tree?

这个题用并查集判断有没有森林就行了，注意一些细节的特特判，代码写的并不优美，刚开始思路有点乱，导致写了很多啰嗦的东西，然后就懒得精简了，-_-|||#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int fa[500000];int in[50000

2016-11-03 19:01:59 95

原创 openjudge每日推荐——9271奶牛散步

我们设f[n]为总的方案数，right[]为向右走的方案数，left[]为向左的方案数，up[]为向上的方案数，f[n] = right[n]+left[n]+up[n]；我们发现向左走的方案数只能由前一步向右走和向上走转移过来，同样的，向右走由前一步向左走和向上走转移过来，向上走由向左，右，上转移过来，那么 right[n] = left[n-1] + up[n-1]; left[n] =

2016-11-03 16:22:20 1138

原创 openjudge每日推荐——碎纸机

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int ans,num,m,vis[1000005],now[100],step[100],n;char s[100];void dfs(int pos,int sum,int cnt)//当前位置，

2016-11-03 16:09:10 385

原创 codevs1169传纸条

这个题跟方格取数是一样的额，不过是改成了从头到尾和从尾到头的两条路径，其实还是一样的。#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n,x,y,v,ans,m;int sum=0;int s[60][60];int f[51][51][

2016-11-03 11:26:44 370

原创 codevs2188最长上升子序列

这个题，我是先找到比第k个元素小的并且在它前面的，和比它大在它后面的元素，放到一个数组里，就保证我们找的最长上升子序列里一定包含第K个元素了，在新的数组里跑一遍最长上升子序列就行了，我发现我的做法跟DQS神犇的一样，然而本蒟蒻只会O（n²）的方法啊，于是在T掉两个点后跑去学了O（nlog(n)）的方法，就A了。。。。#include <cstdio>#include <iostream>#inc

2016-11-03 10:53:04 255

原创 codevs2980买帽子

将每个字符串翻转后得到一个新的字符串，再与原串找最长公共子序列就行了（话说我竟然卡在了字典序的问题上良久，还是string好搞，用char的时候打渣了WA了几次，就不想用它了）#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int dp[1000]

2016-11-03 10:47:25 258

原创 codevs1058合唱队形

初始化的时候出了点小问题导致调试了n~久，真是悲催这个题目我是先找到所有的拐点，再以每个拐点为终点和起点跑最长上升下降子序列再取最大的和，这也就是队形人数最多的情况，也是删去人数最少的情况#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int

2016-11-01 15:23:57 214

空空如也

空空如也