YIF丶-CSDN博客

原创 NOIP2017 D1游记

光棍节打NOIP。。。T1 有毒的T1。第一眼看去以为扩欧或者什么数论。。看了一会儿没什么想法就先过了。后来回头打了暴力。。。出来以后就跟我说T1规律ans=n*m-n-m。。当时心态瞬间爆炸。。。完了呀。。T2大模拟。感觉过了两个样例也不是很确定。。看了一会儿也看不出什么名堂。就这么交了。。。T3看看时间不够。。先打了个暴力。。完了一看数据范围

2017-11-11 12:59:17 375

原创洛谷P1270 树形DP

题目描述经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。输入输出格式输入格式：

2017-11-10 16:05:53 423

原创 hihocoder1014 trie树模板

描述小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。这一天，他们遇到了一本词典，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能对于每一个我给出的字符串，都在这个词典里面找到以这个字符串开头的所有单词呢？”身经百战的小Ho答道：“怎么会不能呢！你每给我一个字符串，我就依次遍历词典里的所有单

2017-11-04 15:06:25 355

原创常用模板1

1.最小生成树这里给出克鲁斯卡尔的板子。#include#includeusing namespace std;int n,m,fa[5001];struct edge{ int x,y,z; bool operator z;}}a[200001];int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}int mai

2017-10-30 20:18:55 199

原创 LCA模板

题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖

2017-10-28 18:39:16 203

原创双lazytag线段树板子

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.将某区间每一个数乘上x3.求出某区间每一个数的和输入输出格式输入格式：第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个

2017-10-27 20:55:14 257

原创 51nod 1202 dp

子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。对于给出序列a，有些子序列可能是相同的，这里只算做1个，请输出a的不同子序列的数量。由于答案比较大，输出Mod 10^9 + 7的结果即可。

2017-10-25 20:24:51 167

原创 bzoj1878 莫队

DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。Input

2017-10-24 21:20:57 208

原创强连通分量模板

【题目描述】给出一个有向图有n个点和m条有向边，输出连通分量的数量。概念： 1. 什么是连通分量？答：一个有向图中，选出某些点组成一个团体，这个团体中的任意两点都可互相到达。那么：选出来的这些点+这些点之间原有的边=叫做连通分量。 2. 只适合有向图答：如果是无向图，那么并查集就可以解决了（还记得“家族”吗？）附加1：什么是强连通图？答：如

2017-10-23 20:53:55 425

原创 hihocoder 1174 拓扑排序模板

描述由于今天上课的老师讲的特别无聊，小Hi和小Ho偷偷地聊了起来。小Ho：小Hi，你这学期有选什么课么？小Hi：挺多的，比如XXX1,XXX2还有XXX3。本来想选YYY2的，但是好像没有先选过YYY1，不能选YYY2。小Ho：先修课程真是个麻烦的东西呢。小Hi：没错呢。好多课程都有先修课程，每次选课之前都得先查查有没有先修。教务公布的先修课程记录都是好多年

2017-10-23 20:23:55 240

原创洛谷p1908 逆序对归并排序

题目描述猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i输入输出格式输入格式：第一行，一个数n，表示序列中有n个数。第二行n个数，表示给定的序列。

2017-10-23 18:49:00 414

原创 KMP模板

描述小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。这一天，他们遇到了一只河蟹，于是河蟹就向小Hi和小Ho提出了那个经典的问题：“小Hi和小Ho，你们能不能够判断一段文字（原串）里面是不是存在那么一些……特殊……的文字（模式串）？”小Hi和小Ho仔细思考了一下，觉得只能想到很简单的做法，但是又觉得既然

2017-10-22 21:13:14 182

原创二分图最大匹配入门题

【问题背景】n只公牛和m只母牛，某些公牛和某些母牛互相喜欢。但最后一只公牛只能和一只母牛建立一对一匹配。要使得最后牛群匹配对数最大。【输入】第一行三个整数n, m，k( 1下来k行，每行两个整数 x，y，表示一条边，连接X集合中x点和Y集合的y点。【输出】只有一行。输出一个整数，表示牛群匹配对数最大值.input:5 5 91 22

2017-10-20 15:39:29 3164

原创模板线段树1

题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1

2017-10-18 21:34:22 165

原创 codeforces round #441 D

D. Sorting the Coinstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputRecently, Dima met with Sasha in a phil

2017-10-17 14:28:26 239

原创 codeforeces Round #441B

B. Divisiblity of Differencestime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a multiset of n

2017-10-17 14:21:53 233

原创 51nod1605 博弈

上帝创造了一个n*m棋盘，每一个格子都只有可能是黑色或者白色的。亚当和夏娃在玩一个游戏，每次寻找边长为x的正方形，其中每个格子必须为黑色，然后将这些格子染白。如果谁不能操作了，那么那个人就输了。亚当喜欢质数。夏娃喜欢1，但讨厌2。因此他们规定，x只有可能是非2质数或者是1。现在他们想知道，如果他们都用最优策略进行游戏，谁会赢。上帝规定亚当先手

2017-10-15 21:16:43 403

原创 51nod1366 floyd

一个国家有N个公民，标记为0,1,2，...，N-1，每个公民有一个存款额。已知每个公民有一些朋友，同时国家有一条规定朋友间的存款额之差不能大于d。也就是说，a和b是朋友的话，a有x元的存款，b有y元，那么|x-y|Input多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5每组测试数据有相同的结构构成。每组数据的第一行两个整数N，d，表示人数与朋友间

2017-10-15 19:48:49 179

原创 caioj 1099 线段树

【题意】给出N个数，两种操作：1、C x y：修改第x个数的值为y；2、P x y：求第x到第y个的最大值，注：x未必比y小【输入格式】第一行输入N和M（0下来N个数然后是M个操作。【输出格式】遇到P操作的时候，输出结果。【样例输入】5 61 2 3 4 5P 1 5C 3 6P 3 4P 4 5C 2 9P 1 5【样例

2017-10-08 20:39:10 305

原创 luogu p1111 并查集

题目背景A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）输入输出格式输入格式：

2017-09-28 08:43:30 178

原创 luogu p1122 DP

题目描述小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：一株奇怪的花卉，上面共连有N 朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美

2017-09-28 07:41:29 778

原创快速幂

题意】求a^b mod c，a,b,c都是整数。【输入格式】一行三个整数 a、b、c。 1 ≤ a,b,c ≤ 10^9【输出格式】一行，a^b mod c的值。#includeusing namespace std;long long a,b,c;long long doit(long long x){ if (x==1) return a%c; else {

2017-09-27 20:32:12 153

原创 caioj 1088 最短路模板

【题意】给出一个图，起始点是1，结束点是N，边是双向的。求点1到点N的最短距离。哈哈，这就是标准的最短路径问题。【输入格式】第一行为两个整数N（1≤N≤10000）和M（0≤M≤200000）。N表示图中点的数目，M表示图中边的数目。下来M行，每行三个整数x，y，c表示点x到点y之间存在一条边长度为c。（x≠y,1≤c≤10000）【输出格式】输出一行，一个整数，即为点1

2017-09-26 21:35:38 281

原创 caioj 1078 dp

题目描述【问题描述】有n条线段（给出起点和末端），分别坐落在数轴上，要求它们之间彼此不重叠的条件下，最大可以覆盖数轴的长度。(数轴的长度指线段覆盖数轴数字的个数)（1~3和3~4的线段视为重叠）【输入】第一行一个整数n（1 第2～n+1行，每行两个整数start和end，描述线段的起点和末端,所有线段都落在[0,2000]的范围内。【输出文件】

2017-09-23 18:36:13 318

原创 caioj 1077 dp

题目描述【问题描述】共N根筷子，长度为T1，T2，T3，……，TN。组成K+3对，使每双的筷子长度差的平方和最小。【输入文件】输入文件共有两行，第一行为两个用空格隔开的整数，表示N，K（1≤N≤100，0 【输出文件】输出文件仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。i表示筷子的双数。j表示筷子下标。转移方程：f[i

2017-09-21 21:27:46 288

原创 caioj 1070 dp

题目描述【问题描述】设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和

2017-09-21 20:04:35 236

原创 caioj1066 DP

题目描述【题目】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足 T1 Ti+1 > … >TK(1你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

2017-09-13 21:28:06 301

原创 caioj1065 DP

教学视频1064【题意】有n个不相同的整数组成的数列，记为: a(1)、a(2)、……、a(n)例如：3，18，7，14，10，12，23，41，16，24。上例中挑出：3，18，23，24就是一个长度为4的上升序列，如果挑出： 3，7，10，12，16，24长度为6的上升序列。求出最长的上升序列的长度。【输入格式】第一行一个整数n（1下来n个整数。【输

2017-09-12 21:05:52 208

原创 caioj1064 DP

【问题描述】今天6:00起床，我转身发现枕头边有100美元。出门的时候发现门口有家冰淇淋店，拉了很长的横幅：“今天100美元和400马克互换”第二天的横幅是：“今天100美元和300马克互换”第三天的横幅是：“今天100美元和500马克互换”第四天的横幅是：“今天100美元和300马克互换”第五天的横幅是：“今天100美元和250马克互换”第五天的晚上，我灵光一闪，

2017-09-12 20:49:46 219

原创 caioj1092 并查集模板

题目描述【题意】n个人，m条关系(x,y),表示x和y是同一家族的。求最多可能有多少个家族。 (n【输入格式】第一行两个整数n和m(n下来m行，每行两个整数x、y(1【输出格式】输出一个整数，表示最多可能有多少个家族。【样例输入】5 3 1 2 2 4 3 4 【样例输出】2模板。#includeusi

2017-09-06 20:56:52 229

原创 D - Codeforces 725D 堆

D - Codeforces 725DOne tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by t

2017-08-30 20:07:10 366 1

原创 51Nod 1241

第一次n2华丽丽的tle。大佬教了o（n）的求最长递增序列的方法%%%%#include#include#includeusing namespace std;int n,a[50001],f[50001];int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); int maxn=0;

2017-08-27 15:31:10 187 1

原创 hdu6147 模拟

众所周知，度度熊最近沉迷于 Pokémon GO。由于太过沉迷，现在它只能按照游戏内置的指令行走了：对，简直就像一个现实中的Pokémon！游戏内置的指令实际上可以抽象成一种：保持现在的朝向前行X米，然后右转。度度熊相信，只要遵循这个指令，它就一定可以抓到最珍奇的精灵球。但不幸的是，这个指令并不是很有可信度，有时会引导度度熊走回原来的位置。现在它想知道，在第

2017-08-23 21:02:48 489 1

原创 hdu6146 递推

众所周知，度度熊最近沉迷于 Pokémon Go。今天它决定要抓住所有的精灵球！为了不让度度熊失望，精灵球已经被事先放置在一个2*N的格子上，每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏，抓捕格子上的精灵球，然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。例如，(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等

2017-08-23 19:26:46 182 1

原创 T1

/*#include#include#includeusing namespace std;long long n,m;int main(){ freopen("remainders.in","r",stdin); freopen("remainders.out","w",stdout); scanf("%lld%lld",&n,&m); long long sum=0; i

2017-08-20 14:56:06 190 1

原创【模板】树状数组洛谷P3374

#includeusing namespace std;int i,j,k,t,n,m,a[500001],tree[500001];int lowbit(int x){ return x&-x;}void add(int x,int y){ while (x<=n) { tree[x]+=y; x+=lowbit(x); }}int sum(int x){

2017-08-03 16:21:53 265 1

原创二分图判定

二分图一•二分图判定时间限制:10000ms单点时限:1000ms内存限制:256MB描述大家好，我是小Hi和小Ho的小伙伴Nettle，从这个星期开始由我来完成我们的Weekly。新年回家，又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表，上面都是姑姑介绍相亲的剩男剩女们。每行有2个名字

2017-07-27 10:14:36 258 2

原创 poj1511 spfa

题目大意：有向图。。点1到除点1外所有点的环的权值和。正着spfa反着spfa。。贴代码#include#include#includeusing namespace std;int i,j,k,t,x,z,y,tot,h[1000001],p[1000001];long long sum,diss[1000001],dis[1000001],que[1000001]

2017-07-24 15:49:38 180 1

原创 Floyd poj1125 poj3615

水上代码。。poj1125#include#include#includeusing namespace std;int i,j,k,n,m,a[101][101],x,y,maxn,maxm,t,tt;int main(){ scanf("%d",&n); while (n!=0) { memset(a,63,sizeof(a)); for (i=1;in

2017-07-05 10:53:15 195 1

原创 hihocoder p1077 线段树

线段树描述上回说到：小Hi给小Ho出了这样一道问题：假设整个货架上从左到右摆放了N种商品，并且依次标号为1到N，每次小Hi都给出一段区间[L, R]，小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种，并且告诉小Hi这个商品的重量。但是在这个过程中，可能会因为其他人的各种行为，对某些位置上的商品的重量产生改变（如更换了其他种类的商品）。小Ho提出了两种非常简单的方法，

2017-06-16 09:00:08 225 1

空空如也

空空如也