Wolf_Reiser-CSDN博客

原创 CF1285D Dr. Evil Underscores 01Trie+贪心

给出nnn个整数a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an，要求选出一个整数XXX，最小化max⁡1≤i≤n(ai⊕X)\underset{1 \leq i \leq n}{\max} (a_i \oplus X)1≤i≤nmax(ai⊕X)，输出这个最小值.1≤n≤105,0≤ai≤230−11\leq n\leq 10^5,0\leq a_i\leq...

2020-01-11 13:58:36 3238

原创 HDU5536 Chip Factory 01Trie处理xor

2015ICPC长春站J题给出一个长度为NNN的数组sss，求max⁡(si+sj)⨁sk\max (s_i+s_j) \bigoplus s_kmax(si+sj)⨁sk，其中i,j,ki,j,ki,j,k互不相同，有多组数据N≤1000N \leq 1000N≤1000辣鸡数据裸O(n3)O(n^3)O(n3)能过正解应该是把NNN个数插入01Trie中，询问时n2n^2n2枚举...

2019-11-19 20:51:42 229

原创 ARC058F 文字列大好きいろはちゃん / Iroha Loves Strings dp+贪心

给出NNN个字符串，要求选出其中一些串按顺序拼接成一个长度为KKK的串，并且要求拼接串的字典序最小。N≤2000,K≤10000,N≤2000,K≤10000,N\leq2000,K\leq10000, 每个串长度不超过KKK，总长度不超过10610610^6. 设ok[i][j]ok[i][j]ok[i][j]表示最后iii个串，能否组成长度为jjj的字符串. 背包转移即可，可以用bitse...

2018-06-04 11:41:23 1102

原创 BZOJ4568 [Scoi2016]幸运数字树上倍增+线性基

有一棵NNN个节点的树，QQQ个询问，每次询问树上从uuu到vvv的路径中能xorxorxor出的最大值。N≤20000,Q≤200000,N≤20000,Q≤200000,N\leq20000,Q\leq 200000,时限666s. 询问一个数集的xorxorxor最大值显然线性基模板。预处理树上每个点到它第2k−12k−12^k-1个父亲的线性基，合并时暴力将一个线性基插入另一个，每次...

2018-05-27 21:58:36 306

原创 BZOJ1001 [BJOI2006]狼抓兔子最小割模板

直接dinic跑最大流可过更新一下模板#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace std;const...

2018-04-18 14:07:52 279

原创 BZOJ2588: Count on a tree 树上主席树

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u和v这两个节点间第K小的点权，强制在线。N,M<=100000 边DFS边建出主席树，这样每次建出的树存储的都是该节点到根的sizesize前缀和这样每次在rt[u]+rt[v]−rt[lca]−rt[fa[lca]]rt[u]+rt[v]-rt[lca]-rt[fa[lca]]四棵树上查询即可

2018-03-07 11:02:26 284

原创 BZOJ1901 Dynamic Rankings 带修改主席树(模板)

给出一个数列，要求支持区间查询第K小和单点修改。因为不强制在线，先将修改操作和原数列一起离散化建树方式更改为使用树状数组维护前缀和，主席树只记录这一个位置的sizesize. 修改时要在logn\log n个节点上同时修改查询时同时累加logn\log n个节点的sizesize，每一层记录一下logn\log n个节点的左右节点对应位置最后在树上二分计算答案

2018-03-07 10:47:14 225

原创 BZOJ3932 [CQOI2015]任务查询系统主席树+差分

给出M个任务，Q个查询，第ii个任务从第sis_i秒开始，到第tit_i秒结束，优先级为pip_i.时间范围是N.要求支持查询[sj,tj][s_j,t_j]时间段内优先级最小的K个任务，查询强制在线。 M,N,Q<=100000. 注意到时间范围不大，因此对每个任务在时间上进行差分主席树上每个节点存储当前时间的这一段的sizesize和离散前的权值和sumsum，每次在第X颗主席树上查询前

2018-03-07 10:21:15 239

原创 BZOJ3524 [Poi2014]Couriers 主席树(模板)

给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。显然出现次数超过一半的数最多只有1个建出主席树，在树上二分查找即可/************************************************************** Problem: 3524 ...

2018-03-07 09:47:39 228

原创 BZOJ1058 [ZJOI2007]报表统计 STL

给定一个数列需要实现三种操作：①在某个数后面加入一个数，如果曾经加入过则加在之前加的数之后②查询所有相邻两个数的差的最小值③查询全局差的最小值用一个set和一个map维护相邻两数的差值每次插入就删除原来的差值，再插入新的差值因为全局差值只降不增所以再开一个set存出现过的数，每次二分查找后更新差值再插入因为BZOJ评测不分点所以卡过了#include#inc

2018-01-09 23:02:44 254

原创 BZOJ3687 简单题 dp+bitset

给出n个数，求所有子集和的异或和。n正常情况下就是一个01背包，但是范围过大会TLE于是用bitset优化一下这个bool dpbitset的第i位表示和为i出现次数的奇偶性这个东西可以像位运算一样操作，比较方便但是好像用的不多。。#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using

2018-01-09 22:52:44 315

原创 BZOJ1566 [NOI2009]管道取珠 dp

有两个栈，每个栈从底向上有一些颜色为A或B的球，现将这些球全部取出，假设能得到kk个不同的颜色序列，得到每个序列的方案数为aia_i. 求∑ki=1a2i\sum_{i=1}^ka_i^2. 这里需要巧妙转化 a2ia_i^2可以看做两个人每人取一次，取得的序列相同的方案数。那么设f[i][j][k]f[i][j][k]为第一个人在上面取ii个，下面取jj个，第二个人在上面取kk个，下面取

2018-01-03 21:11:11 506

原创 BZOJ3671 NOI2014随机数生成器贪心+暴力

14年NOI的题通过一系列操作生成了n*n个随机数，将这些数按顺序填入一个n*n的方格，求从左上角走到右下角，能得到的字典序最小的路径。前面直接模拟求路径序列的时候，考虑贪心取当前能走到的最小的数一定是最优的于是直接从1~n*n判断每个数能不能取能则输出并删除这个数的左下角和右上角所有格子256M只能开2个5000*5000的int和一个boolean所以记录每个数位置

2018-01-03 20:31:26 398

原创 BZOJ2464 中山市选2009小明的游戏 SPFA

给定一个n * m的棋盘，上面有两种格子#和@。给定一个起始位置和一个目标位置，每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是0，否则费用是1。计算从起始位置移动到目标位置的最小花费。最短路无误忘判边界WA两发也是醉了#include#include#include#define LL long long#define clr(x,i) memse

2017-12-31 23:00:58 276

原创 BZOJ1202 [HNOI2005]狡猾的商人并查集+前缀和

有一个长为n的数列，给出m个子段和信息，问是否一定存在冲突。数列可以为负。这个题用并查集做感觉很玄学按照题解打了一遍还是不太清晰 https://www.cnblogs.com/FallDream/p/bzoj1202.html 这篇题解思路比较好建图，并且插入反边，bfs判断一个点的距离是否不唯一#include<cstdio>#include<cstring>#include

2017-12-31 17:59:54 325

原创 bzoj1090: [SCOI2003]字符串折叠区间dp+hash

题目大意：一个重复k次的子串x可以折叠替换成k(x)的形式，问原串经折叠后的最短长度.n≤100n\leq100. k(x)的长度为 k的位数+x的长度+2. 区间dp，转移方程为f[i][j]=min(j−i+1,f[i][k]+f[k+1][j])f[i][j]=min(j-i+1,f[i][k]+f[k+1][j]) 如果i~j的子串可以由i~i+k-1的子串重复得来就要再转移f[i

2017-12-31 13:27:00 249

原创 BZOJ4028 [HEOI2015]公约数数列分块

给定一个数列，要求资磁以下两种操作: 1.单点修改. 2.求数列中最前的位置p，使前缀最大公约数gcd*前缀异或和xor==一个输入的数x.考虑分块+暴力. 按照n√\sqrt n分块，求出每一块的前缀gcd和前缀xor. 单点修改时对所在块暴力更新gcd与xor 每次更新的复杂度是n√logn\sqrt n \log n.查询时分两种情况①如果GCD(gcd_now,gcd_pre)==

2017-12-31 12:32:22 324

原创 BZOJ2946 [Poi2000]公共串二分+hash

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。n预处理出每个串的哈希值二分答案，

2017-12-30 22:09:14 355

原创 bzoj2393/bzoj1853 Cirno的完美算数教室/[Scoi2010]幸运数字搜索+容斥

这两个题是完全一样的，但1853会爆long long，中间要用long double估计一下。popo大神的题解：http://blog.csdn.net/popoqqq/article/details/41807333题目大意：求在[L,R]中能被“baka数”整除的数的个数.baka数是数位组成只含2和9(⑨)的数.范围1e10-1e11.先预处理出所有baka数，再把是另一个的

2017-12-23 18:32:36 247

原创 BZOJ1821 [JSOI2010]Group 部落划分贪心+并查集

平面上有N个部落，使划分成K个居住点后，最近的两个居住点之间的距离最远。两个部落的距离，定义为部落中距离最近的那两个居住点的距离。求这个距离。将完全图的边按照距离从小到大排序，选中边的两端用并查集并起来，第N-K+1条边的长度即为答案.这个题目不需要二分，贪心比较巧妙

2017-12-23 17:36:57 317

原创 bzoj1977: [BeiJing2010]次小生成树 kruskal+倍增LCA

给定一张无向图，求严格次小的生成树（保证存在）非严格次小的很好做kruskal求出最小生成树，倍增求LCA与区间最大边权枚举剩下的边两端点之间的最大值比较即可.但是要严格次小的话，要在倍增时维护一个次大边权值枚举时如果当前边与最大相等则比较次大做的时候一堆奇怪的bug。。#include #define LL long longusing namespace std

2017-12-23 16:51:43 301

原创 HDU4417 Super Mario 主席树 / 树状数组

给出n个数，m个询问，每次查询在[L,R]中≤x的数有多少个.在线做的话是主席树模板了离线做将查询按位置先后排序逐个向树状数组中插入数，并回答询问（类似查询逆序对）最后再按时间排回来都需要离散化.因为是小于等于，二分的时候要upper_bound.坑死了多组数据初始化坑爹啊。。主席树#include#include#include#include#def

2017-12-12 22:49:39 266

原创 POJ3461 Oulipo KMP模板

给出S串和T串，求T在S中出现的次数.KMP板子题#include#include#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace std;const int N=1000005;char s[N],t[N];int n,m,ans,nex[N];void get

2017-12-07 22:15:38 281

原创 bzoj1306 [CQOI2009]match循环赛

n支队伍进行循环赛，胜者得3分，平各得1分，负得0分.现给出各队伍最终分数，求可能符合的胜负情况数.（n这个没法状压，只能爆搜了吧。。主要剪枝有这几个：某个队伍剩下全赢都达不到分数或已经超过分数剪枝.当枚举到某个队伍的最后一场比赛时可通过与结果的差值直接确定这一场情况如果差3,1,0分就直接确定，差2分或3分以上直接剪枝。差不多8s刚好卡过去。。剪枝这个东西真的就是

2017-12-05 21:35:00 449

原创 BZOJ1007 [HNOI2008]水平可见直线贪心+栈

给出n条直线，求从y值无穷大处能看见的直线编号.n按照斜率k递增为第一关键字，与y轴截距b递减为第二关键字对直线排序.如果两条直线斜率不同，那新直线要被看到，必须与之前直线的交点在当前交点的左侧。如果斜率相同，则b值大的可见。没有卡精度还是可以的#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x)

2017-12-05 21:08:52 242

原创 BZOJ2151 种树贪心+双向链表+优先队列

#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))#define mp make_pair#define pii pairusing namespace std;const int N=200005;int n,m,a[N],nex[N],pre[N],ans,vist[N];priority_que

2017-12-05 20:59:02 307

原创 BZOJ3781 小B的询问莫队

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。n,m,K显然莫队裸题，样例一遍过。。。#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using

2017-12-01 22:47:39 283

原创 bzoj3293/1045 [Cqoi2011]分金币/[HAOI2008] 糖果传递贪心

圆桌上坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。n这个是刘汝佳蓝书P4的原题，还蛮巧妙的。证明这里也有http://blog.csdn.net/ycdfhhc/article/details/45437677#include#define LL long lo

2017-11-30 21:51:32 293

原创 BZOJ1051 [HAOI2006]受欢迎的牛 tarjan

定义一个点是受欢迎的，当且仅当其他所有点都能到达它.求有多少个这样的点.很显然用tarjan将强连通分量缩点，缩点后出度为0的点的size就是答案.如果出度为0的点有多个则不存在#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace std;const int N=100

2017-11-30 21:40:42 291

原创 BZOJ1067 [SCOI2007]降雨量 RMQ+乱搞

这恐怕是见过最恶心的题目了...一开始题目意思都理解错了，然而样例能过...总之题解就看hzwer的吧... http://hzwer.com/1655.html区间最值我用的RMQ，当然线段树也ojbk。。。代码可读性还是有的#include#include#include#include#define LL long long#define clr(x,i)

2017-11-30 21:28:11 295

原创 BZOJ1106 [POI2007]立方体大作战tet 树状数组

给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。碰到像1212这样的肯定要交换一次所以记录一下未消除的数字个数，以及出现过的数字的位置

2017-11-30 21:21:18 302

原创 BZOJ1087 [SCOI2005]互不侵犯King 状压dp

给定一个n*n的网格，问恰好摆放K个国王的方案数。n,m显然状压dp.因为国王最多只能向下影响1行.预处理出每个状态为i的棋子数cnt[i]，当前状态是否合法c0[i]，前一行状态为j时两个状态能否转移的c[i][j].所以设 f[i][j][k]表示摆到第i行，已经摆了j个棋子，当前行的状态为k的方案数.则f[i][j][k]=Σf[i-1][j-cnt[k]][l].(

2017-11-25 13:13:58 335

原创 BZOJ2005 [Noi2010]能量采集递推+容斥/欧拉函数

对题目手动简单分析后，可知要求这里考虑容斥.设f(x)表示最大公约数是x的数对个数，g(x)表示存在公约数x的数对个数.易得g(x)=(n/x)*(m/x).那么f(x)=g(x)-Σ(2*x从后往前递推即可.#include#define LL long long#define clr(x,i) memset(x,i,sizeof(

2017-11-21 22:33:59 288

原创 BZOJ1412 [ZJOI2009]狼和羊的故事最小割

有一个n*m的网格，其中标1的是狼，标2的是羊，标0的是空地。现在要在格子与格子之间修一些栅栏，使任意的狼与羊互不联通。n,m割的定义是：使S集和T集不存在通路。而题目又要求建的栅栏最少，于是就是最小割问题了。从源点向所有狼连INF的边，从所有羊向汇点连INF的边，保证狼和羊都在不同的点集里.再从狼、空地向空地、羊连1的边.跑最大流即可.#include#define L

2017-11-21 22:16:22 412

原创 BZOJ1305 [CQOI2009]dance跳舞最大流+二分

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？n看到数据范围可以考虑网络流建模.把每个男孩和女孩拆成

2017-11-20 22:19:45 278

原创 BZOJ1303 [CQOI2009]中位数图差分+前缀和

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。差分。找到b在数列中的位置设为pos，比b大的赋值为-1，比b小的赋值为1.再对pos左边做后缀和，右边做前缀和.乘法原理统计答案.#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace s

2017-11-20 21:05:12 323

原创 BZOJ4027 [HEOI2015]兔子与樱花树形dp+贪心

删掉一个结点的代价是c[i]+son[i]树形dp+贪心，每个结点显然选代价最小的儿子每个结点把儿子排序一下复杂度nlogn，虽然n一开始想到了但是没敢写。。看了题解发现nlogn能过...#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace std;

2017-11-19 12:43:47 317

原创 BZOJ4029 4029: [HEOI2015]定价贪心

定义一个数的“荒谬度”为：这个数去除末尾0后的十进制长度p*2，如果此时末尾为5则为p*2-1.求在区间[L,R]中“荒谬度”最小的数.贪心。每次在当前数的十进制最后一位+1,如果荒谬度更小则更新答案.好菜啊。。#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace s

2017-11-19 10:47:09 441

原创 BZOJ3612 [Heoi2014]平衡递推整数划分

#include#define LL long long#define clr(x,i) memset(x,i,sizeof(x))using namespace std;const int N=10005,KK=12;int n,K,p,f[N*KK][KK],ans;void solve(){ scanf("%d%d%d",&n,&K,&p); f[0][0]=1; for

2017-11-16 21:24:16 332

空空如也

空空如也