ZY_discovery-CSDN博客

原创 AtCoder AGC001F Wide Swap 　&&　 NOIP2017模拟赛１０.８Ｔ２

传送：http://agc001.contest.atcoder.jp/tasks/agc001_f 官方菌：http://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf题意：给你一个n的排列P，以及一个数字Ｋ，你可以进行的操作为：对于两个满足 |i − j| ≥ K 且 |P i − P j | = 1 的下标 i 与 j,交换 P

2017-10-09 11:59:01 497

原创 Codeforces 757F && NOIP2017 2017-09-28模拟T3

题意：给定一个n个点，m条边的带权无向图，和起点S。请你选择一个点u(u!=S)，使得在图中删掉点u 后，有尽量多的点到S的最短距离改变。写完痛快极了，虽然作死要写spfa以至于还要求拓扑序，但是写完真的脱胎换骨啊，还好上天保佑一Ａ不然会死．．．题解：最短路＋灭绝树灭绝树：灭绝树是一个点灭绝后，子树中的点都灭绝的一棵树（其实就是一种支配树）对于这道题，我们可以根据你最短路建立一个DAG 先定义：堵

2017-09-28 18:26:35 344

原创 AtCoder AGC 005D　容斥＋二分图＋ＤＰ

题意：给定k，求有多少个n的排列，满足对于任意i，|a[i]−i|≠k n<=2000比较巧妙的一道题，考试一直刚这道题结果把自己刚死了。。。根据类似错排的推法＆容斥，我们可以得到答案为： ans=ans+f[i](n-i)!(-1)^i (i=0,1,2…n) 其中fi表示有i个不合法位置的方案数我们考虑怎么求fi我们可以构建一个二分图，从左边的i向右边的i+k,i-k连边，可以发现一个完美

2017-09-27 19:01:31 415

原创八数码问题有解条件&推广N×N，N×N×N

对于简单的八数码（3*3）一般的目标状态是这样的（我们把矩阵表示为序列，0表示空格）： 1 2 3 4 5 6 7 8 0 即： 123456780对于每个状态定义一个逆序：除0以外的数字的逆序对数目抛出结论：两个状态可以达，当且仅当两个状态序列逆序奇偶性相同简单证明必要性：对于空格的移动，左右移动不会影响逆序，上下移动导致被替换数字跨过两个数字，这两个数字可能都比它大，可能都比它小，

2017-09-24 20:29:39 646

原创 CodeForces 614D 二分+贪心

原题链接：http://codeforces.com/problemset/problem/614/D题意：有n门学科，每一门最高水平为A，一共可以提高的水平为m，计算经过提升后的最大得分，得分=（达到A分数的科目个数）*cf+（最低分数）*cm最开始真的一脸懵逼完全不会啊仔细想了想，可以枚举达到A的数目，把原数组从小到大排个序倒着选择成为满分的科目，然后在剩下没达到满分的科目里选择最低分。复杂

2017-09-10 23:26:35 404

原创 NOIP2012 开车旅行：SET+倍增

啊，看到题：字好多。然后就直接开始码暴力模拟了，觉得可以预处理一下每个点可以到达的最近点和次近点，这样大概就有50分了（然而实际有70分。。我忽略了只能往后走这一点带来的便利，于是每一次都要找一次最近点&次近点= =果然弱啊(。・・)ノ）暴力的过程写的蛮。。。第一次只骗到15分= =，后来发现了BUG调到35.。就开始在精度这里卡。。。换了几种最后终于有50了。。。【我还存了一次余数除数hh

2017-07-23 17:23:56 406

原创 BZOJ1010--HNOI2008--玩具装箱Toy

题意：给你一串长度不一定相同的物体，问你怎么分段使代价最小。求最小代价。i-j放在一起的代价=（j-i+i到j的长度和-L）^2。MY Solve: 首先难得自己推出了一次DP方程。。。。dp[i]表示前i个装好箱所需的最小代价。sum[i]很显然就是为了方便算一段连续物体的长度总和所记录的前缀和。转移方程是这样的： dp[i]=min(dp[j]+(i−j−1+sum[i]−sum

2017-06-08 21:18:33 901

原创 DP-斜率优化初探之记录

初探这种东西。。曾二dalao今天在讲国集dalao的论文《浅谈决策单调性动态规划的线性解法》by-冯哲。。然后先慢慢吃下第一步：斜率优化。其实以前GBZ也讲过，不过没怎么细听。。。然后还要看后面一坨诡异的东西：比如凸包上面二分，CDQ分治来搞之类的。。。SMAWK算法果断掉线啊啊啊啊（显然一下午烦的死然后和天神一起去思考人生了。。。）本篇博客其实是摸鱼，是来推荐一篇很棒的博客的。。。。在此附上链接

2017-06-08 21:08:56 736

原创 [BZOJ 2125]最短路---仙人掌图+Tarjan缩环+LCA

题目：给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。Input输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问Output输出Q行，每行一个整数表示询问的答案Sample Input9 10 21 2 11 4 13 4 12 3 1

2017-05-31 22:01:40 1562

原创 NOI2014--起床困难症

题意：有n个关卡，你有一个初始攻击值，这个值初始不能超过m，每个关卡有一个攻击类型op（位运算：& | ^），和参数t；现在问你通过这些关卡最后你的攻击值最大是多少。最开始直接看到这道题直接就先打了O(nm)的暴力枚举，m<=2^30.。所以显然知道自己过不了，依旧抱着好玩的态度去水了30分暴力，然后想正解。。最开始是想让最后结果的每个二进制位尽量是1，说到底就是个贪心。。后来仔

2017-04-23 13:51:12 458

原创 Catalan数

事情是这样的，某天在洛谷题库乱翻题写，突然看到一道普及-的东西【P1044 栈】，觉得啊，可以娱乐一下身心，就点开了，自己水了一下之后，照例围观题解，发现了这是“卡特兰数”的裸题【在此之前也听说过似乎】，然后一脸憧憬地去百度，get以下内容：Catalan数是用来解决以下类似问题的:n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的个数不小于0的个数，试求满足这条件的数有多少

2017-03-18 13:45:22 516

原创 uoj 魔法森林--LCT

【魔法森林】为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为 1…n1…n，边标号为1…m1…m。初始时小E同学在 11 号节点，隐士则住在 nn 号节点。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 11 号

2017-03-16 10:03:10 665 2

转载 NIM游戏&SG函数

Nim游戏Nim游戏定义Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的

2017-03-15 20:03:57 418

原创关于考试2-22的总结反思

第一题看到第一反应，见过，是冬令营集训某神犇讲过，然而我清晰地记得我忘了。。。。。然后第二题第三题。。暴力极其好打啊。。。然而第二题最开始又脚妙地看错了题目，马上改暴力瞬间从O(QN)变成了O(N^3Q)。。。。第三题暴力调好以后，重新回去看第一题。。好像是可以DP做的。。。开始想DP想不出就出去静了一下继续想，get到DP方程。。。一阵兴奋。。打完后取模次数少了又调了好久。。预计最开始应该是

2017-02-23 19:13:30 337

原创从基础开始的异世界生活------poj2109

题意不解释题解：最初猜想是二分+高精，想想代码都头疼23333后来知道，哦，一句话水过23333不过这道题也可以引发很多思考，譬如技巧与算法。。。这里用double避免高精然后pow函数搞。。。没了-_-#include#include#include#include#include #define maxn 1010using namespace std;

2017-02-12 20:29:55 253

原创从基础开始的异世界生活------poj1328

题意：地图的x轴的上方为海，下方为陆地，海中有n个小岛，坐标为(isl[i].x,isl[i].y)。有一种雷达，能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的，也就是x轴上的。题解：真的是水题啊。。。。。稍微想一下就好以每个点作圆心然后画一个半径为d的圆，储存下与x轴的前后交点将这一堆交点按照后一个交点排序最后

2017-02-12 20:20:07 388

原创从基础开始的异世界生活------poj2965

此开关的同一行、同一列所有的开关都会自动改变状态。要想打开冰箱，要所有开关全部打开才行。输入：一个4×4的矩阵，+表示关闭，-表示打开；　输出：使冰箱打开所需要执行的最少操作次数，以及所操作的开关坐标。题解：类似与poj1753.....可以用状压+BFS写。。。【尤其是不想算那些二进制转十进制的数，当然dalao肯定不一样】但是。。。不想写。。。就想了一下，

2017-02-12 15:14:27 337

原创从基础开始的异世界生活-----poj1753

题目大意：有一个4*4的方格，每个方格中放一粒棋子，这个棋子一面是白色，一面是黑色。游戏规则为每次任选16颗中的一颗，把选中的这颗以及它四周的棋子一并反过来，当所有的棋子都是同一个颜色朝上时，游戏就完成了。现在给定一个初始状态，要求输出能够完成游戏所需翻转的最小次数，如果初始状态已经达到要求输出0。如果不可能完成游戏，输出Impossible。题解：状压+广搜？？？我们可以把一个格

2017-02-09 20:38:48 345 2

原创 POJ1741 Tree.

Give a tree with n vertices,each edge has a length(positive integer less than 1001).Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is

2017-02-07 20:44:39 306

转载 LCT维护问题

扯淡（前言）众所周知LCT可以支持关于点权的链修改，换根，LINK，CUT和查询链信息操作，但是总有那么些神犇（毒瘤）出题人会让你在支持链修改，换根，LINK和CUT操作的情况下去支持子树查询，或者维护关于边权的链修改，换根，LINK，CUT和链查询。网上似乎讲解这两种LCT写法的blog比较少或者不怎么能搜到？总之我来写一发（LCT基础知识回顾）【我自己做了一个ppt，ftp里面有，

2017-01-16 10:35:53 1059 3

原创 hdu1143 Tri Tiling

题目大意就是说：输入一个数n，表示给定一个n*3的矩阵，你有2*1的方块，有多少种方式去铺满这个矩阵。1.如果n为奇数，显然无法铺满，方案数为02.如果n为偶数，则：（1）.如果n=2，那么显然只有三种方法（2）.如果n>2，那么每种只有2种方法：（如下图，分别为n=4,6,8时的情况，图来自于%%%orz）分别是倒着和正着两种此时我们设定一个递推数组a[n]表示n

2016-12-06 21:57:59 358

原创进制转换

显然，有很久没来码博客了。。。。【反思反思】进制转换问题有很多很多进制之间相互转换的【例如n进制各种n】，因此只在这里打打任意进制的好了。。。其他的在此不做赘述，留给读者思考【刘汝佳上身 doge.jpg】显然。十进制小学生都知道，例如从小学到大的1+1=2。。。具体看注解——#include #includeusing namespace std; int main(

2016-09-20 21:45:57 277

原创素数判定

前言：应该说是很久前之前制定的打怪计划，但是由于各种原因迟迟没有开始动手，现在这里反思一下。。。关于素数判定的基础知识：)（1）素数判定有一个很基础很基础的写法，应该都知道的，就是求n以内的素数的时候，我们可以知道一个数i，它的因子数目一定是小于或等于sqrt(i)的，那么由此我们可以很简单的写出一段简短且简短且容易的代码：如下#include#include#includ

2016-09-12 20:54:19 462 2

原创数论的巴拉拉魔法大门就此打开，请收下这波来自数论的友好邀请信，准备变身各位小魔仙噗哈哈哈哈

【申明：前言是为了丰富枯燥的数论生活，并无恶搞之意，毕竟生活总是要什么东东来让它更加有趣的撒】又名：和haha一起战胜数论的生活背景——魔仙堡在noip的大战即将打响，在各大神变身结束【划掉】披上战袍准备殊死一搏的时候Orz，haha作为一只弱弱的成员之一，也决定加入这一场正邪之战，可是成神之路遥遥无期，修炼的过程岂是朝夕可就，于是，haha决定从拥有最强大力量的数论世界开始。

2016-09-05 20:22:47 888 6

原创来来来来吃一发STL

What is stack?翻译过来就是就是“栈”撒~使用stack显然要调用头文件然而stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不指定容器类型时，默认的容器类型为deque。定义stack 对象的示例代码如下：stack s1;stack s2;然后咱来看看stack的一些基本操作:入栈，如例：s.

2016-08-26 20:51:49 440

转载线段树的一些脑残东西例如向上回溯延迟更新的恶心东西

此题题意很好懂：给你N个数，Q个操作，操作有两种，‘Q a b ’是询问a~b这段数的和，‘C a b c’是把a~b这段数都加上c。需要用到线段树的，update:成段增减，query:区间求和介绍Lazy思想：lazy－tag思想，记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。在此通

2016-08-08 21:23:28 423 3

转载一篇讲左偏树的好文章~

传送门：http://blog.csdn.net/iaccepted/article/details/6748038二、左偏树的定义和性质.......................................................................................... 22.1 优先队列，可并堆.....................

2016-08-07 21:43:34 3219

原创猴子大王可并堆

#include#include#include#includeusing namespace std;struct node{ int v,l,r;}tree[1000010];int fa[10010];void hb(int x,int y){ if(x==0) return y; if(y==0) return x; if(a[x].v>a[y].v){ int

2016-08-06 22:10:48 302

转载背包

http://www.cnblogs.com/LUO77/p/5587121.html

2016-08-05 22:02:28 275

转载聪明的打字员POJ1184

出处：http://blog.csdn.net/lyy289065406/article/details/6648695

2016-08-05 19:18:36 462

原创 circle POJ动态规划某一题。。题号。。。额。。。。

题意：输入一个数k，则一个圆里面有2k个点，点与点之间可以连接，求出可执行方案数目N和最少划分的平面数目P样例输入：2样例输出：2 3题解（本菜综合各大神题解自行理解）： 1：定义数组f[i]表示连i个点所用方案数【i就是k咯】 2：k=1的时候，容易知道N=1，P=2； 3：k=2的时候，将

2016-08-05 15:04:56 382

原创虫食算

题目大意：输入n，n进制的算式，输入三行字符串，分别表示加数与和，根据等式求出每个字母所代表的数字大致解法：从右往左搜，因为较右面的位上相加后可能有进位数字要从大往小搜（从N-1到0）判断还未枚举到的列，如果此列三个字母都已确定，但有无进位都不合适，则顺序不正确

2016-07-31 16:55:46 392

原创神奇的别墅

#include#include#include#include#includeusing namespace std;const int maxn=20,max1=1<<12;int p[maxn][max1],end;vectord[maxn],l[maxn];struct node{ int num,ligh;};queueq;int main(){ int i,

2016-07-23 21:25:20 727

转载迭代加深搜索

迭代加深搜索，实质上是限定下界的深度优先搜索。即首先允许深度优先搜索K层，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，直到搜索到目标为止。这样可以看出重复搜索了好多。但是它的好处在于：1.空间开销小每个深度下实际上是一个深度优先搜索，不过

2016-07-23 20:29:42 1299 1

转载网络流之SAP算法学习

网络流之SAP算法学习终于决定开始学习网络流了=.=>那本书讲了很多关于求最大流的算法，然后我就只挑了一种传说中神奇的SAP算法学习。首先引入几个新名词：1、距离标号：所谓距离标号，就是某个点到汇点的最少的弧的数量（即边权值为1时某个点到汇点的最短路径长度）。设点i的标号为level[i]，那么如果将满足level[i]=level[j]+1的弧(i,j)叫做允许弧

2016-07-15 20:07:58 351

转载 C++ STL set和multiset的使用

C++ STL set和multiset的使用std::set s;那个s这个对象里面存贮的元素是从小到大排序的，(因为用std::less作为比较工具。)1，set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。 set和multiset的区别是：set插入的元素不

2016-07-14 16:05:50 269

原创心灵终结。。。。终结我的心灵。。。。T—T

#include#include#include#define ll long longconst int maxn=20;using namespace std;int a[maxn][maxn];ll f(ll x){ if(x%4==0)return x; if(x%4==1)return x+1; if(x%4==2)return x+2; if(x%4==3)ret

2016-07-11 21:06:41 1090

原创 babystep.....脑残的baby（QAQ）提高训练

#include#include#include#includeusing namespace std;const int maxn=555;int f[maxn*maxn];int n,m;int x[5],y[5];int find(int x){ return f[x]==x?x:f[x]=find(f[x]);//并查集}int idx(int x,int y){

2016-07-11 20:25:07 399

转载深度理解链式前向星

我们首先来看一下什么是前向星.前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.用len[i]来记录所有以i为起点的边在数组中的存储长度.用head[i]记录以i为边集在数组中的第一个存储位置.那么对于下图:

2016-07-09 08:45:45 1577

原创 circle!!!!哇啊哇。。生活美好世界再见（手动再见

#include#include#include#include#define LEN 110using namespace std;char s[200]; // 输入串int k; // 输入参数int ans[LEN] ; // 存放结果void zy(int a[], int b[], int bl, int c[

2016-07-06 21:23:31 513

空空如也

空空如也