Joky_2002-CSDN博客

原创【bzoj4540】[Hnoi2016]序列

题目链接好久以前写的东西了==，现在已经记不起来当时线段树咋写的了于是YYYYYY出一个CDQCDQCDQ的做法好像还没人发过CDQCDQCDQ的题解？抢个fb首先先把给的序列预处理一把记L[i]L[i]L[i]为 iii左边小等a[i]a[i]a[i]的位置+1+1+1同理有R[i]R[i]R[i]为 iii右边小等a[i]a[i]a[i]的位置−1-1−1然后上一把二维数点叫我二...

2018-12-14 11:47:32 418

题目链接终于补了这个坑了。。先考虑O(n2)O(n ^ 2)O(n2)咋整显然可以得到式子 f[i]=max⁡1≤j&amp;amp;amp;lt;i{f[j]∗Rj∗Ai+BiRj∗Aj+Bj} f[i] = \max_{1 \leq j &amp;amp;amp;lt; i} \left\{ f[j] * \frac{R_j * A_i + B_i}{R_j * A_j + B_j} \right\} f[i]=1≤j...

2018-12-12 16:46:20 202

原创【bzoj4543】[POI2014]Hotel加强版

题目链接先考虑n ^ 2如何做不是直接暴力dfs设f[u][i]f[u][i]f[u][i]为uuu的子树中，到uuu距离为i的点有多少个，g[u][i]g[u][i]g[u][i]表示在uuu的子树中，有两个点到他们的lcalcalca的距离为ddd，并且uuu到他们的lcalcalca的距离为d−id - id−i的方案数有多少个考虑动态地去计算这两个东西像树形背包那样显然有g[...

2018-11-23 10:46:22 439

原创【bzoj3237】[Ahoi2013]连通图

题目链接太神辣，想我这种zz根本想不到orz yjt这里就不写了（其实是我懒代码：#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<vector>#include<algorithm>#include<cstr...

2018-09-25 09:49:04 214

原创【bzoj3489】A simple rmq problem

题目链接经典套路记第iii个数前一个和他一样的数的位置为pre[i]pre[i]pre[i]，后一个和他一样的数为suf[i]suf[i]suf[i] 然后只有当pre[i]+1≤l≤i  and  i≤r≤suf[i]−1pre[i]+1≤l≤i  and  i≤r≤suf[i]−1pre[i] + 1 \...

2018-09-13 11:27:38 195

原创【bzoj5427】最长上升子序列

题目链接额。。我简直像个智障啊。。想了一个错的解还给学弟们比比半天。。然后学弟们也没指出错误。。首先考虑最优方案肯定是把所有的NNN都装进去为什么呢？（因为没有找到证明，智障我就自己想了一个）我们考虑有两个下标i、ji、ji、j，其中i&amp;amp;lt;ji&amp;amp;lt;ji &amp;lt; j 记sumisumisum_i为iii之前的NNN的数量如果中间的NNN的个数过少，能装进把aiaia_i...

2018-08-27 21:15:02 389

原创【bzoj2901】矩阵求和

题目链接我靠。。博主没有脑子了啊。。这种题都不会写了。。。观察式子 ans=∑i=xlxr∑j=ylyr∑k=1nA[i][k]∗B[k][j](40)(40)ans=∑i=xlxr∑j=ylyr∑k=1nA[i][k]∗B[k][j]\begin{eqnarray}ans = \sum_{i = xl}^{xr}\sum_{j = yl}^{yr}\sum_{k = 1}^{n}A[...

2018-08-21 10:08:08 552

原创【bzoj3720】Gty的妹子树

题目链接想了一个O(n&amp;nbsp;n−−√&amp;nbsp;log2n)O(n&amp;nbsp;n&amp;nbsp;log2n)O(n\ \sqrt{n}\ log_2n)的做法，以为不能过，然后百度了一下题解，结果全都是这个复杂度的东西。。。（注：以下为博主口胡，博主觉得麻烦并没有去写讲一下我的做法吧，可能和树分块大同小异就是我是这样去考虑分块的：我先把树给转化成括号序列，如果没有加点的话就很...

2018-08-15 22:16:50 220

原创【bzoj3744】Gty的妹子序列

题目链接hhhhhhhhhhhhhhhh凭借着O(nn−−√)O(nn) O (n \sqrt{n}) 的做法，成功卡到了rank7rank7rank7（然而小号rank6rank6rank6那我们来讲一讲怎么n−−√n\sqrt{n}吧首先分块是很明显的我们先假设询问都是整块整块询问的（即不会有一个块被左端点或右端点分成两半的情况）那么答案你可以这样去考虑：分成跨越块的和...

2018-08-14 23:22:54 467

原创【bzoj4802】欧拉函数

题目链接想瞎搞过去的可能就只有我一个。。。。。正解Pollard_rho算法（啥rho算法？）Pollard_rho算法是专门解决这类大数质因数分解的，当然还要搭配Miller_Rabin判素数（推荐一篇入门博文）先质因数分解，然后按φ(i)φ(i)\varphi(i)的式子算就行了代码：#include<cstdio>#include<vector...

2018-08-07 19:57:36 262

原创【bzoj4035】[HAOI2015]数组游戏

题目链接SGSGSG函数niubia 设SG(i)SG(i)SG(i)为第iii位为白色的估价函数显然有 SG(i)=mex{SG(j∗i)}  (2≤j≤⌊ni⌋)SG(i)=mex{SG(j∗i)}  (2≤j≤⌊ni⌋)SG(i) = mex \{ SG ( j * i ) \}\ \ (2 \leq j \leq \lfloor \fra...

2018-08-06 19:01:20 285

原创【bzoj2749】[HAOI2012]外星人

题目链接。。。。。模型转化错了被自己蠢到哭就首先这题如果说质因数只有222的时候，操作次数肯定是222的个数如果质因数不只有222的时候考虑φ(i)φ(i)\varphi(i)的式子，做一次操作就相当于把每种质因数取一个出来，都减去111，然后再质因数分解回去由于质数除了222都是奇数，所以减111再质因数分解肯定会多很多222出来形式化点，如果存在除了2以外的质因数，我们...

2018-08-04 15:32:40 217

原创【bzoj2302】[HAOI2011]Problem c

题目链接话说csdn的html编辑器格式好像变丑了不能贴题面，那以后就用markdown吧hahahahhaha这题正解是dp，我们考虑怎么来底辟首先考虑什么时候方案会合法，瞎举例子会（hennan）发现当且仅当对于所有的编号iii，编号≤i≤i\leq i的人数≥i≥i\geq i就行了那我们可以这样考虑设f[i][j]f[i][j]f[i][j]表示编号≤i≤i...

2018-08-01 22:11:25 839

原创【bzoj2342】[Shoi2011]双倍回文

题目链接发现博客里没有回文树的板子所以写一道**题来补一下（话说我之前都没补吗被学长嘲讽博客里都是模板（我的博客就是用来存模板的ya hahahahahhaa这题就是瞎搞不用想太多直接瞎搞回文树建出来问题就转化成对于每个长度为4的倍数、且fail树上存在一个父亲的长度为自身长度的一半的节点的长度最大值就是这样了，dfs一下就好代码：#include&l...

2018-07-27 21:29:16 177

原创【bzoj5249】[2018多省省队联测]IIIDX

5249: [2018多省省队联测]IIIDXTime Limit: 40 Sec Memory Limit: 512 MBSubmit: 499 Solved: 236[Submit][Status][Discuss]Description【题目背景】Osu听过没？那是Konano最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司KONMAI...

2018-06-18 19:22:16 232

原创【bzoj5016】[Snoi2017]一个简单的询问

5016: [Snoi2017]一个简单的询问Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 326 Solved: 221[Submit][Status][Discuss]Description给你一个长度为N的序列ai，1≤i≤N和q组询问，每组询问读入l1,r1,l2,r2，需输出get(l,r,x)表示计算区间[l,r]中，数字x出现了多少...

2018-06-15 18:38:10 366

原创【bzoj2007】[Noi2010]海拔

2007: [Noi2010]海拔Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2975 Solved: 1442[Submit][Status][Discuss]DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包...

2018-05-24 21:39:23 213

原创【bzoj4316】小C的独立集

4316: 小C的独立集Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 472 Solved: 263[Submit][Status][Discuss]Description图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取...

2018-05-16 09:51:07 303

原创可持久化Treap

可持久化treap主要是建立在无旋treap的基础上（好像这种东西也叫fhq treap？通过新建节点等常规操作来达到可持久化的目的下面先来介绍一下可持久化treap的两个常规操作：1、split能把一颗treap o给分成小等k和大于k的两个部分，然后把两个部分分别用x和y来存储，观察发现这样分其实就像一刀砍下去，把treap分成两半，然后需要拼接进x和y的实际上只有这一刀会波及到的节点然后我们...

2018-05-15 11:18:53 836

原创【bzoj2149】FFT快速傅立叶

2179: FFT快速傅立叶Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 4214 Solved: 2259[Submit][Status][Discuss]Description给出两个n位10进制整数x和y，你需要计算x*y。Input第一行一个正整数n。第二行描述一个位数为n的正整数x。第三行描述一个位数为n的正整数y。Output输出...

2018-05-03 20:43:28 201

原创【bzoj2811】[Apio2012]Guard

2811: [Apio2012]GuardTime Limit: 10 Sec Memory Limit: 128 MBSubmit: 936 Solved: 401[Submit][Status][Discuss]DescriptionInputOutputSample Input5 3 41 2 13 4 14 4 04 5 1Sample Output3 5 HINT在这个样例...

2018-04-17 10:38:12 183

原创【bzoj4826】[Hnoi2017]影魔

4826: [Hnoi2017]影魔Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 798 Solved: 464[Submit][Status][Discuss]Description影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英...

2018-04-15 22:17:49 211

原创【bzoj3105】[cqoi2013]新Nim游戏

3105: [cqoi2013]新Nim游戏Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1562 Solved: 918[Submit][Status][Discuss]Description传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一...

2018-03-22 19:52:29 151

原创【bzoj4004】[JLOI2015]装备购买

4004: [JLOI2015]装备购买Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 1752 Solved: 526[Submit][Status][Discuss]Description脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量zi(aj ,.....,am) 表示 (1 <= i <= ...

2018-03-22 19:49:09 181

原创【bzoj4184】shallot

4184: shallotTime Limit: 30 Sec Memory Limit: 128 MBSubmit: 668 Solved: 339[Submit][Status][Discuss]Description小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从...

2018-03-22 19:44:05 225

原创【bzoj2460】[BeiJing2011]元素

2460: [BeiJing2011]元素Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 1985 Solved: 1036[Submit][Status][Discuss]Description 相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。...

2018-03-22 19:41:13 148

原创【bzoj3600】没有人的算术

3600: 没有人的算术Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 1118 Solved: 452[Submit][Status][Discuss]DescriptionInputOutputSample InputSample OutputHINTSource湖北省队互测 Week1[Submit][Status][Discuss]。。。。...

2018-03-16 13:03:22 517

原创【bzoj1912】[Apio2010]patrol 巡逻

1912: [Apio2010]patrol 巡逻Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 1740 Solved: 907[Submit][Status][Discuss]DescriptionInput第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行，每行两个整数 a, b，表示村庄a与b之间有一条道路(1 ≤ a,...

2018-03-07 19:32:58 257

原创【bzoj3531】[Sdoi2014]旅行

3531: [Sdoi2014]旅行Time Limit: 40 Sec Memory Limit: 512 MBSubmit: 2833 Solved: 1227[Submit][Status][Discuss]Description S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地...

2018-03-06 21:10:15 224

原创【bzoj3171】[Tjoi2013]循环格

3171: [Tjoi2013]循环格Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1149 Solved: 727[Submit][Status][Discuss]Description一个循环格就是一个矩阵，其中所有元素为箭头，指向相邻四个格子。每个元素有一个坐标（行，列），其中左上角元素坐标为（0,0）。给定一个起始位置（r，c），你可以沿着...

2018-03-05 17:26:56 166

原创【bzoj2648】SJY摆棋子

2648: SJY摆棋子Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 5570 Solved: 1952[Submit][Status][Discuss]Description这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋...

2018-03-03 23:55:20 241

原创【bzoj1305】[CQOI2009]dance跳舞

1305: [CQOI2009]dance跳舞Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 3822 Solved: 1631[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢...

2018-02-27 17:01:16 214

原创【bzoj1101】[POI2007]Zap

（markdown下题面排版好像很丑。。还是贴链接吧题目链接很显然的莫比乌斯很容易就能写出式子：f(d)=∑d|nn<=min(a,b)  F(n)μ(nd)f(d)=∑n<=min(a,b)d|n  F(n)μ(nd)f(d) = \sum^{d | n}_{n F(n)=⌊an⌋⌊bn⌋F(n)=⌊an⌋⌊bn⌋F(n) = ...

2018-02-26 22:28:25 212

原创【bzoj1049】[HAOI2006]数字序列

1049: [HAOI2006]数字序列Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1842 Solved: 797[Submit][Status][Discuss]Description　　现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。Inpu...

2018-02-25 09:46:47 201

原创【bzoj4227】城市

4227: 城市Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 44 Solved: 16[Submit][Status][Discuss]DescriptionA国是一个拥有n个城市的国家，其中城市s是A国的首都。A国还有m条道路，每条道路连着两个不同的城市，但是一对城市间可能有多条道路。每一条道路都有它的长度，一条道路的通行...

2018-02-23 23:58:04 321

原创【bzoj2229】[Zjoi2011]最小割

2229: [Zjoi2011]最小割Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 2527 Solved: 898[Submit][Status][Discuss]Description小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： “对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t...

2018-02-23 23:39:44 154

原创【poj1958】Strange Towers of Hanoi

Language:DefaultStrange Towers of HanoiTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 2929 Accepted: 1895DescriptionBackground Charlie Darkbr

2018-02-06 22:08:06 297

原创【bzoj2957】楼房重建

2957: 楼房重建Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1179 Solved: 560[Submit][Status][Discuss]Description　　小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋

2018-01-26 23:35:19 168

原创【bzoj4516】[Sdoi2016]生成魔咒

4516: [Sdoi2016]生成魔咒Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1362 Solved: 766[Submit][Status][Discuss]Description魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串

2018-01-16 11:56:48 332

原创【bzoj3505】[Cqoi2014]数三角形

3505: [Cqoi2014]数三角形Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1881 Solved: 1147[Submit][Status][Discuss]Description给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。

2018-01-11 22:17:22 255

空空如也

空空如也