TheWolfWhistlingSong-CSDN博客

原创 HEOI2016游记

无论是省选之前还是出完成绩的现在，一切都是那么迷茫……自己那么弱，考得那么渣，居然能进队？4.22:启程的一天。从学校出发显然不能带任何电子设备，于是花了一上午整理了100+篇复习资料，很鬼畜的样子，反正打印到最后打印机罢工了QAQ，于是我留着莫比乌斯反演这个巨坑出发了QAQ……学校很良心啊居然这么早就准备了午饭。坐大巴去保定，上车就睡，一觉就到，然后我们到得太早了并没有人来…

2016-04-24 21:26:53 1955 6

翻译蜜の夜明け

寝息よりそっと夜明けが来る君の梦は今森を駆ける目覚めて灯りを探しすしぐさなくしたなら见つけてあげよう君と仆の未来に隠れている那隐藏我们的未来的光辉>さあここへ手をつないだらほどけないよ君と远くへ遥かな日の记忆に咲いた青い国を见るストーリー是在那青色的国度中所见的传说>辉く瞳伝えよう冷えた霭の色甘い羽音震える肩先に

2016-03-29 21:41:52 1015 3

翻译旅の途中

[00:01.00]旅の途中[00:27.92]ただひとり (孤身一人)[00:30.01]迷(まよ)い込(こ)む (迷失于)[00:32.66]旅(たび)の中(なか)で(旅途之中)[00:36.21]心(こころ)だけ(唯有心灵)[00:38.37]彷徨(さまよ)って(彷徨迷茫)[00:41.08]立(た)ち尽(つ)くした (始终伫立)[00:44.66]でも今(いま)

2016-03-29 21:40:01 2000

原创 Bzoj1801:[Ahoi2009]chess 中国象棋:dp

题目链接:[Ahoi2009]chess 中国象棋设dp[i][j][k]表示前i行中有j列有1个炮,k列有2个炮，分情况讨论转移即可注意一行最多两个炮#include#include#include#include#define ll long longusing namespace std;const int maxn=110;const int mod=999997

2016-07-21 10:42:28 564

原创 Bzoj2839:集合计数:组合数学+容斥

题目链接:集合计数答案是含有至少k个的-至少k+1个的+至少k+2个的……从n个数中选出k个作为交集中的数,是C(n,k)，这样的集合共有2^(2^(n-k))-1个2^(n-k)是包含选定的k个数的可选集合的数量，选取方案有2^(2^(n-k))-1个(不能有空集否则无法保证k个元素)所以ans=C(n,k)*C(k,k)*(2^(2^(n-k))-1)-C(n,k+1)*C(k

2016-07-20 19:38:33 1513

原创 Bzoj3551:[ONTAK2010]Peaks加强版:Kruskal+主席树

题目链接:[ONTAK2010]Peaks加强版做一遍Kruscal，对于要合并联通块的两个点x,y新建节点z令fa[x]=fa[y]=z，并且节点z的权值为这条边的边权那么我们对于一个询问只需要倍增出最后一个权值>x的节点，这颗子树就是我们要找到的联通块主席树维护即可#include#include#include#includeusing namespace std;

2016-07-18 17:47:00 861

原创 Bzoj3545:[ONTAK2010]Peaks:Splay启发式合并

题目链接:[ONTAK2010]Peaks离线，将边按照边权从小到大排序，询问按照x从小到大排序对于每个询问，将边权小于他的x的边加入图中，用splay维护每个联通块的权值，查找第k大即可加入一条边时会合并联通块，这个用Splay的启发式合并#include#include#include#includeusing namespace std;const int maxn

2016-07-18 15:28:45 557

原创 Bzoj3531:[Sdoi2014]旅行:树链剖分+动态开点线段树

题目链接：[Sdoi2014]旅行对于每种颜色维护一颗线段树，为了节约空间这里我们动态开点然后就是弱鸡的线段树操作了指针的动态开点线段树现在才会写……#include#include#include#includeusing namespace std;const int maxn=100010;const int maxc=100001;int n,m,tot=0,

2016-07-18 08:05:31 469

原创 Bzoj2819:Nim:树链剖分

题目链接:Nim线段树维护异或值得沙茶题然而dfs会爆栈所以得开手工栈(见代码)#include#include#include#includeusing namespace std;const int maxn=500010;int tot=0,h[maxn],ind=0,s[maxn],fa[maxn];struct edge{int to,next;}G[maxn<

2016-07-17 19:27:42 379

原创 Bzoj1565:[NOI2009]植物大战僵尸:拓扑排序+网络流

题目链接：1565:[NOI2009]植物大战僵尸显然的最大权闭合图模型，但是裸上是错的每个植物相他所攻击的位置连边，如果形成一个环那么这个换必然无解进一步，这个环所保护的点都不能取到所以我们拓扑排序求出可以干掉的植物集合再做网络流即可#include#include#include#include#includeusing namespace std;const

2016-07-17 09:37:24 478

原创 Bzoj3790:神奇项链:manacher+线段树+贪心

题目链接：3790:神奇项链处理出每个位置的最长的回文串，然后就是用最少的回文串覆盖整个区间贪心一下，线段树维护即可，每次在左端点在合法区间里的回文串中找右端点最远的即可#include#include#include#include#includeusing namespace std;const int maxn=210000;const int inf=0x7fff

2016-07-14 15:52:38 397

原创 Bzoj3782:上学路线:组合数学+Lucas+CRT+DP

题目链接：上学路线设dp[i]为到了第i个坏点且是第一次到达坏点的方案数那么dp[i]=C(x[i]+y[i],x[i])-∑C(x[i]+y[i]-x[j]-y[j],x[i]-x[j])dp[j]（x[j]对于mod=100003Lucas直接上对于mod=1019663265分解质因数得到3*5*6973*10007然后每个因数分别Lucas后CRT合并#include

2016-07-13 15:37:09 921

原创 Bzoj3509:[CodeChef] COUNTARI:分块+FFT

题目链接：3509:[CodeChef] COUNTARI题目要求求出(i,j,k)的对数满足i式子变形得到a[j]*2=a[i]+a[k];考虑对于每个a[j]求出左边的i和右边的k发现这个可以用生成函数来搞一搞，生成函数的指数代表数值系数代表个数，左右两边分别搞出一个多项式然后FFT一下即可但是复杂度nmlogm(m=max(a[i]))会T考虑分块，对于每个块[l,r

2016-07-13 09:34:22 1039

原创 Bzoj2162:男生女生:网络流+容斥

题目链接：男生女生第一问只需要将没有关系的男女生之间连边，将不合法的点对割去即可题目要求在人数相同的情况下男生尽量多，于是我们将变权扩大，对于男生，连边，女生连边这样跑最小割的时候会尽量先割去女生，剩下的男生就多了第二问用容斥原理，设S(x,y)为x个男生y个女生满足条件的方案数，则S(x,y)=C(boy,x)*C(girl,y)*C(x*y,k);然后容斥得到ans=S(x

2016-07-11 09:09:18 582

原创 Bzoj1823:[JSOI2010]满汉全席:2-sat

题目连接：1823:[JSOI2010]满汉全席2-sat首题!2-sat的图中每一条变、边表示选了i必须选j拆点，一个表示选一个表示不选，跑tarjan，如果有一个点拆成的两个点在一个联通分量里就是BAD#include#include#include#includeusing namespace std;const int maxn=2010;int n,m,h[m

2016-07-06 16:20:11 879

原创 Bzoj3140:[Hnoi2013]消毒:二分图

题目连接：3140:[Hnoi2013]消毒首先如果只是两维的平面我们直接二分图覆盖集那么三维的话枚举在x上枚举哪些层直接消去剩下的同二维做法#include#include#include#includeusing namespace std;const int maxn=5111;int n,m,tot=0,h[maxn],cnt=0,a,b,c;struct edg

2016-07-03 20:32:03 515

原创 Bzoj4006:[JLOI2015]管道连接:斯坦纳树

题目连接：4006:[JLOI2015]管道连接刚刚学会的斯坦纳树QAQ把关键点之间的联通性加入状态，枚举当前考虑的点进行转移即可#include#include#include#include#includeusing namespace std;const int maxn=1051;const int inf=0x7fffffff/2-1;int n,m,tot=

2016-07-03 16:08:06 623

原创 Bzoj3533:[Sdoi2014]向量集:线段树+凸包+三分

题目链接[Sdoi2014]向量集维护一颗线段树，线段树每个节点上有对应区间的上下凸壳可以发现答案一定在凸壳上取得，所以在凸壳上三分即可，y>=0时在上凸壳上三分，否则在下凸壳#include#include#include#include#include#define ll long long#define pb push_back#define pii pair#d

2016-06-23 19:21:19 500

原创 Bzoj2178:圆的面积并:Simpson积分

题目链接：2178:圆的面积并Simpson积分裸上即可Ac，精度必须开到1e-13,1e-12都会wa貌似有高大上的做法但是不会Simpson真是慢死了QAQ这篇博文用来学习Simpson很好#include#include#include#include#includeusing namespace std;const double eps=1e-13;c

2016-06-22 21:42:58 750

原创 Bzoj4540:[Hnoi2016]序列:莫队+RMQ

题目链接4540:[Hnoi2016]序列考虑莫队算法，在移动一个端点的时候，假设要处理的区间为[l,r]切向左扩大区间，最小值所在位置为k，那么a[k]的贡献为(r-k+1)*a[k]，即[k,r]的新增序列都以a[k]为最小值还有一段区间[l,k-1]没有处理，设s[i]为以i为左端点的合法区间的答案，r[i]为i右侧第一个不大于a[i]的输的位置，那么s[i]=s[r[i]]+1ll

2016-06-20 15:43:44 633

原创 Bzoj1822:[JSOI2010]Frozen Nova 冷冻波:计算几何+网络流

题目链接：[JSOI2010]Frozen Nova 冷冻波二分答案，把最优性问题转换为判定性问题对于判断树木是否与线段相交，分两种情况讨论：1:圆心作线段的垂线垂足不在线段上2:圆心作线段的垂线垂足在线段上对于1，直接比较圆心与线段两个端点距离的最小值是否小于半径对于2，算出垂线长度后比较区分1、2两种情况用点积即可，相当于间接判断cos的值得正负#include

2016-06-20 09:44:38 703

原创 Test Problem:Play With Array:分块+链表

题目大意：有一个长度为n的数列a1-an支持两个操作：1 l r 把a[r]放到a[l]的前面a[l]-a[r-1]顺次后移2 l r k询问a[l]-a[r]中k的个数n,m题解：每个块内记录sum[i]表示i出现的次数，同时维护一个链表，链表中每个元素的下标全局使用，但是每个块内的链表只维护块内元素换句话说叫“跳表"？同学说的说错了没我事QAQ然后就是在块内

2016-06-18 19:03:10 321

原创 Bzoj3456:城市规划:NTT

题目链接：城市规划设g[i]表示i个点的连通图的个数，h[i]表示i个点的图有多少个有容斥一下，假设有j个点组成了合法的图，剩下的i-j个点不合法，那么新图不合法有组合数拆掉，等式除以(i-1)!，移项合并后可得这是卷积令那么多项式求逆即可#include#include#include#include#inc

2016-06-17 07:49:49 768

原创 Bzoj3992:[SDOI2015]序列统计:NTT+DP

首先设dp[i][j]表示前i个数余j的方案数dp[i][j]->dp[i+1][j*s[k]%m]=>O(n*m^2);发现M是个质数，有原根将j用j的原根表示为j'则dp[i][j']=∑dp[i-1][k']((k'+s[p]')%(m-1)==j')这是一个卷积，可以用NTT优化=>O(nmlogm)对n快速幂一下就是O(mlognlogm)#include#

2016-06-15 14:58:49 500

原创 Bzoj3270:博物馆:概率与期望，高斯消元

题目链接：博物馆我们用id[i][j]代表一个人到了i另一个人在j的状态假设id[i][j]代表的状态可以一步走到id[x][y]代表的状态，那么id[x][y]一步也可以走到id[i][j]所以状态之间的转移形成了一个环，这时候要用高斯消元来解决一下了设a[id[x][y]][id[i][j]]为从状态id[i][j]转移到id[x][y]的概率来列个方程组假设现在在id[i

2016-06-13 20:00:04 1460

原创 Bzoj3566:[SHOI2014]概率充电器:概率dp

题目链接[SHOI2014]概率充电器woc我的高考概率是怎么学的这么简单的概率公都忘了233公式：设事件A,B，p为概率，则p(A|B)=p(A)+p(B)-p(A&B)意思是发生A或B事件之一的概率是发生A的概率+发生B的概率-A和B同时发生概率那么一个点x有电的情况为1:自己给自己充上了电；2:子节点给他充上了电；3：父节点给他充上了电设事件1的概率为p[x]，那么1

2016-06-12 21:21:19 476

原创 Bzoj2626:JZPFAR:K-D-Tree

题目链接：JZPFARK-D_Tree复习，直接忘记了写point的比较函数导致nth_element出错调了好久QAQ#include#include#include#include#include#define LL long longusing namespace std;const int maxn=100010;struct qqq{LL dis; int id;

2016-06-09 20:11:27 658

原创 Bzoj3786星系探索:splay维护dfs序

题目链接：星系探索最近越来越懒了都不想写blog了QAQ子树修改，链查询，树结构改变，单纯的lct已经不能满足这道题了QAQ考虑dfs序，设每个点再dfs序中的位置为st[x],ed[x]，我们在st[x]的位置上赋值为x的值，在ed[x]上赋值为-x的值，这样查询链的时候不在链上的点的贡献会被抵消修改也很简单至于改变父节点，只要把当前子树的那一段dfs序删去并加在新父节点的后

2016-06-09 14:59:24 757

原创 Bzoj3196:Tyvj1730二逼平衡树:树套树，线段树套splay

题目链接：3196: Tyvj 1730 二逼平衡树麻麻我终于会写树套树辣这3个小时没白花QAQ#include#include#include#includeusing namespace std;const int maxn=1200010;const int inf=1e9-1;int tot=2,n,m,c[maxn],root[maxn];struct seg

2016-05-18 11:39:29 753

原创 Bzoj4196:[Noi2015]软件包管理器:树链剖分

题目链接：4196:[Noi2015]软件包管理器这是一道沙茶题昨天写一道树链剖分题调了3h最后莫名其妙地过了被人D了一顿今天我不服我要秒A一道树链剖分给你们看看然而……建立线段树的时候写成了这个"p->l;p->r=r;"然后调了1hQAQ交了一发E了又调了0.5h，发现dfs1(int x,int deep)中对儿子进行dfs时写成了dfs1(v,x)QAQ

2016-05-17 20:14:25 323

原创 Bzoj2331[SCOI2011]地板:插头dp

题目链接：[SCOI2011]地板裸插头，知道做了这道题才发现我以前插头学得是个什么XX样子啊QAQ用0表示没有插头，1：插头类型为直线，2：插头类型为L具体情况都在程序中标注顺便吐槽一句，这道题我wa了千百遍居然只是因为数据中'_'写成了'*'！白白浪费了一个上午TAT#include#include#include#include#include#include

2016-05-15 14:10:11 338

原创 Bzoj2561:最小生成树:网络流，最小割

题目链接：最小生成树发现如果这条边可能出现在最大生成树上的话，那么可以代替这条边的所有边都不连通，换句话说这条边是连接u,v必不可少的于是我们把所有权值大于L的边建成一张边权去为1的图对U,V跑最小割即可知道最少删去多少条边最小生成树同理QAQ#include#include#include#include#include#includeusing namespace

2016-05-03 21:07:50 522

原创 Bzoj4538:[Hnoi2016]网络:整体二分+树状数组

题目链接：4538:[Hnoi2016]网络整体二分，用dfs序+树状数组判断当前答案是否可行对于一段区间[l,r]，我们二分得到的答案为mid，我们把[l,r]中大于mid的数据交互请求加入树状数组，同时也有撤销操作的删除这样知道我们发现了一个询问操作，我们在树状数组中做子树查询，就可以知道当前点坏掉会影响多少条数据交互请求设区间[l,r]中我们在当前操作的时候还存在有num个数

2016-04-29 17:35:04 1088

原创 Bzoj2809:[Apio2012]dispatching:左偏树

题目链接：2809:[Apio2012]dispatching考虑对于以节点x为根的一颗子树，我们只要在m的限制下尽量多地选择忍者即可，这个可以用大根堆维护考虑x向x的父亲y转移时，相当于y的各颗子树在m的限制下尽可能多的选择忍者，显然我们不能暴力重建堆，用可并堆logn维护即可，这里我用的是左偏树每转移到一个节点就更新一遍答案#include#include#include

2016-04-29 10:17:32 528

原创 Bzoj1061:[Noi2008]志愿者招募:单纯形算法

题目链接1061:[Noi2008]志愿者招募线性规划的裸题，然而蒟蒻并不会，放个代码慢慢研究QAQ看线性规划的资料的话可以去找那个《线性规划与单纯形算法》这里有个算法的模拟，可以加深理解#include#include#include#include#include#includeusing namespace std;const int maxn=10010;

2016-04-28 18:57:47 699

原创 Bzoj3190:[JLOI2013]赛车:半平面交

题目链接：[JLOI2013]赛车对每个赛车列出他的x-t函数画在二维坐标系中，发现其实就是水平可见直线那道题了我们将函数按照第一维v从小到大，第二维起始位置从大到小排序，然后对于有序的三发函数a,b,c，如果b,c的交点在a,b的左边b就不会成为领跑的了最后要把交点在第二象限的函数删去注意数据中有v全是0的情况QAQ#include#include#include#in

2016-04-27 07:53:38 715

原创 Bzoj4069:[Apio2015]巴厘岛的雕塑:dp+贪心

题目链接：[Apio2015]巴厘岛的雕塑一开始先写了个既错误又高复杂度的dp，令dp[i][j]=min(dp[i][k],dp[j][k-1]|(s[i]-s[j]))，其中s[]代表前缀和首先超时不说，在或的情况下单纯地每步取最小值无法保证全局的最优性，但是即使是这样我还是奇奇怪怪的过了好几个点QAQ正解是这样的：首先处理出答案最多的可能位数bit，然后倒序从最高位开始枚举每

2016-04-25 17:17:18 828

原创 Bzoj1857:[Scoi2010]传送带:三分

题目链接[Scoi2010]传送带首先由猜测法证得函数具有下凸性QwQ然后就可以三分辣#include#include#include#include#includeusing namespace std;const double eps=1e-5;struct point{double x,y;}A,B,C,D;double p,q,r,ax,ay,bx,by,cx,

2016-04-22 08:07:42 481

原创 Bzoj:1758:[Wc2010]重建计划:树的点分治

题目链接：[Wc2010]重建计划纯粹是为了复习板子，也没有什么思考，感觉是糟蹋了这道题了……#include#include#include#includeusing namespace std;const int maxn=200010;const int inf=1000000000;const double eps=1e-4;int n,m,s[maxn],dp[m

2016-04-21 16:24:19 885 1

原创 Bzoj1004:[HNOI2008]Cards:置换群+dp

题目链接：1004:[HNOI2008]Cards首先看到题目就知道是个有关群论的题Burnside:真正染色方案数=(Σ每种置换下不变的染色方案数)/置换总数；发现这里卡片的数量有限制所以Pólya并不能用了于是要用dp求出不变的方案数发现两个在某置换下可以互相到达的序列如果本质相同那么必须涂上相同颜色可以处理处循环节长度，然后裸dp了注意不洗牌也是一种方案最后求

2016-04-21 10:38:37 457

空空如也

空空如也