zhouyuyang233-CSDN博客

原创博主自传

ZJ蒟蒻一枚。从六年级参加pj，三年没一等。其中初一初二差10分一等。初三侥幸tg一等。望神犇指教。本人联系方式qq：1067933169

2017-02-28 20:34:22 2491 12

题目链接看到题面里的max⁡ai>=ax,i<xi\max_{a_i>=a_x,i<x} imaxai>=ax,i<xi和min⁡ai>ax,i>xi\min_{a_i>a_x,i>x} iminai>ax,i>xi,大概能想到笛卡尔树上的dpdpdp问题了。方便起见我们假设已经建立出来了笛卡尔树。接下来对于每个节点xxx，我们分别称按照规则与xxx主动连接的节点为lxl_xlx与rxr_xrx。性质1:　任意一组

2020-06-03 16:48:06 658 1

原创传递闭包的正确姿势

就是给你一个有向图，询问所有点对之间的可达性。直接floyed的复杂度为O(n3w)O(\frac{n^3}{w})O(wn3)。同时由于floyed的枚举有后继性，因此不能使用4毛子优化考虑先缩掉SCC，使得图变为一个DAG。按照拓扑序逆序构造答案。此时由于状态不存在后继性，因此可以对中间点每BBB个分块，每块预处理2B2^B2B个集合的出边。询问时查询nB\frac{n}{B}Bn...

2020-05-07 13:43:20 1559 1

原创 loj 3120 黑科技做法

牛逼的杜ls在CF上面发了一个生成函数黑科技。设k=n−2mk=n-2mk=n−2m,并且略去若干种边界情况。将答案写成生成函数形式，形如:n!2D[xn]∑i=0k(Di)(ex−e−x)i(ex+e−x)D−i\frac{n!}{2^D} [x^n] \sum \limits_{i=0}^{k} \binom{D}{i} (e^x-e^{-x})^i(e^x+e^{-x})^{D-i}2D...

2020-04-24 20:56:08 602

原创多项式exp的正确姿势

等到晚上应该可以更新当日题解。D1T1设DP状态fi,0/1,jf_{i,0/1,j}fi,0/1,j表示前iii个数字，总共有jjj个选择了A,上一个选择了A/B是否合法，直接暴力复杂度O(n2)O(n^2)O(n2)。观察性质，可以证明对于每个iii，其合法的肯定为一个连续段。证明略。因此转移只需要记录左右端点。复杂度O(n)O(n)O(n)#include<bits/std...

2020-04-16 23:08:14 1351

原创 JOISC2020题解

等到晚上应该可以更新当日题解。D1T1设DP状态f[i][0/1][j]f[i][0/1][j]f[i][0/1][j]表示前iii个数字，总共有jjj个选择了A,上一个选择了A/B是否合法，直接暴力复杂度O(n2)O(n^2)O(n2)。观察性质，可以证明对于每个iii，其合法的肯定为一个连续段。证明略。因此转移只需要记录左右端点。复杂度O(n)O(n)O(n)#include<...

2020-03-21 15:34:00 3375 3

原创 2019北大集训游记

不好意思，这篇文章鸽了Day -1Day 0Day 1Day 2Day 3Day 4Day 5Day -1坐高铁到了北京。感受到了帝都的寒冷以及暖气的极大优越性。晚上补了一下昨天的CF并且顺便吐槽了一下EC-final。Day 0报道日。早上九点到了酒店然后跟我说没房住。干等了约4个小时后终于成功办理了入住手续。接下来大概是若干快乐的放松心情时间。Day 1开场看T1，看到是...

2020-02-02 18:53:26 1417 1

原创 NOI2019游记

博主终于诈尸了。由于退役失败，这篇文章不鸽了。由于是比赛后一个月心血来潮补的，不保证内容无误。Day -1坐飞机到的广州。深刻感觉到广州热爆了。几乎全天围观ZJ-zzy打隔膜。DAY 0教练在一个礼拜前甩给我的口号锅在开幕式之前1分钟终于想好了。灯光师随机扫射差评。下午笔试的时候考前三分钟开始抱佛脚。和AH-zzy喜提NOI生涯首个笔试满分。晚上在尝试背LCT板子之后决定破...

2019-08-12 22:23:11 4035 3

原创 NOIp2017酱油记

好久没更了233. Day 0: 上午傻逼模拟赛。花说炸一个点一个俯卧撑有个小哥爆蛋233。（60个）中午去衢州。然后在市区堵了1个小时。晚上接着看骗导+RP导。话说某位大佬和他妈都没带雨伞233 PS：上午学校里RP++刷到15EDay 1: 居然和旺仔分到了一个考场伏地魔%%%%%% 开场先看T1。(考完发现给小学的人做过）傻逼题。在看T2 傻逼题

2017-11-12 20:09:45 1232

原创 NOI2017题解（挖坑待填）

day1T1：首先将加和减分开统计，只要比较后缀大小就行如何比较后缀大小？暴力找到下一个不等的位置。于是我们用set维护不等的位置，每次查找以下就可以了。然后你就在UOJ上拿到了96分（蛤）虽然时间复杂度是O（L log L）其中L表示涉及到的数字操作 UOJ96分代码然后我们发现时间复杂度在于修改。我们考虑二进

2017-08-26 21:32:27 1878

原创 NOI2017酱油记（伪）

好吧其实是因为菜没拿到名额才去打同步赛的。 day1：拿到题面： 1.不存在的 2.tan 90° 3.辣鸡吉利卧槽，全是假题。此时SKYDEC在裙上说第三道用dp骗分。于是我就愉快的撸了一个小时撸出来了。然后一看T2，好像可以哈希呀然后就愉快的花了一个小时码码码半个小时之后调完了。然后看第一道。还是不会于是就愉快的打了一发暴力了上去。然乎就愉快的

2017-08-26 21:04:45 1165 6

原创 bzoj1340: [Baltic2007]Escape逃跑问题

传送门我们大力拆点，在相邻两个距离小于等于200的点连边然后S向离上边界小于等于100的点连边离下边界小于等于100的点向T连边大力最小割一点不虚。#include<bits/stdc++.h>#define N 505using namespace std;int head[N],q[N],dis[N];int tot=1,l,w,n,S,T,ans;struct edg

2017-07-28 21:22:36 434

原创 bzoj1338: Pku1981 Circle and Points单位圆覆盖

传送门首先，最有解一定是有一个点恰好在圆上。然后我们枚举那个在圆上的点然后我们计算出当圆心绕该店旋转时，其他点能被覆盖的区间然后大力线段覆盖一发就行了时间复杂度O（N^2logN)#include<bits/stdc++.h>using namespace std;struct P{double x,y;}p[505];struct data{ double t;

2017-07-28 21:20:00 386

原创 bzoj1329: The Morning after Halloween小鬼回家

传送门根据题目我们推断又是搜索。但是你单次搜索（16^6*4^5）直接TLE 我们考虑Astar 首先我们预处理处三个终点到其他节点的距离。然后一个状态个估价函数就是三个节点到三个目标点的距离最大值。然后我们按照当前步数+估计函数来对状态进行增广然后你就驶过去了。辣鸡码农题吃枣药丸#include<bits/stdc++.h>using namespace std;s

2017-07-28 21:16:49 368

原创 bzoj1330: Editing a Book

传送门我们可直接暴力广搜算答案。但是你会发现你预处理完就要20s+ 于是我们考虑折半。我们首先计算出答案小于3的部分然后我们对于每次询问倒着广搜算出答案然后你就可以卡过去啦#include<bits/stdc++.h>#define ll long longusing namespace std;map<ll,int> mp,mp1;int a[12],b[12],h,

2017-07-28 21:10:32 367

原创 bzoj1331: 魔板

传送门直接大力广搜出奇迹。不需要任何优化#include<bits/stdc++.h>using namespace std;map<int,int> mp;int a[10],b[10],q[100005];int x,y;int cal(int *a){ int s=0; for (int i=0;i<8;i++) s=s*10+a[i];

2017-07-28 21:07:16 326

原创 bzoj1394: [Baltic2005]ancient

传送门大力动归。设f[i][k][l][p]表示前i位，连续相同字母个数k个，连续相同种类字母l个，字母是p的方案数然后大力dp一发就可以了。#include<bits/stdc++.h>using namespace std;int C[2],E[2],n,hsh[30],a[20];char s[20];long long f[20][10][10][30],ans;int

2017-07-28 21:04:51 322

原创 bzoj1395: [Baltic2005]Trip

传送门我们可以将问题转化为中间乘坐公交的最长时间。然后我们对于每条边我们把它当成在a时刻出发，中间乘坐时间为c-b，到达时间为d的一条线路。然后你就可以想到一个O（NM）的动归, f[i][j]表示在j时刻到达i的左右答案当然那一定是TLE+MLE 于是我们考虑优化。我们发现原方程有两种转移： 1：f[i][j]=f[i][j-1] 2：f[i][j]=f[k][l]+d

2017-07-27 21:51:33 289

原创 bzoj1399: Win

传送门根据数据范围我们推断算法是爆搜or状压dp 然后看着爆搜比较假，就去打dp了。首先我们发现每个人挂掉的顺序可以看成一颗树我们大力计算出树的高度，然后dp 设f[i][j][k]表示当前树的最大深度是k，选取的子集是j，胜利者是i的方案数然后我们每次大力枚举子集dp就可以了然后你就愉快的TLE了。你需要卡一下常数才能过嘿嘿嘿#include<bits/stdc++.h

2017-07-27 21:39:09 275

原创 bzoj1300: [LLH邀请赛]大数计算器

传送门最后的十二位我们大力质因数分解之后快速幂爆出来。前面已看只有三位于是考虑大力用log来爆过去。我们计算出答案的log值，然后截取ans-int(ans)+2的log值。然后我们大力pow一波然后取整爆过去你就AC辣。#include<bits/stdc++.h>#define mo 1000000000000ll#define ll long long#define N

2017-07-27 21:34:30 374

原创 bzoj1945: [Ceoi2007]Royaltreasury

传送门裸的树形dp。 f[i][0/1]表示当前位置没用/用了转移暴力就可以了然后就是喜闻乐见的高精度模板了。#include<cmath>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 1005

2017-07-26 21:19:39 368

原创 bzoj1943: [Ceoi2007]Nasty Calculations

传送门我们发现这个式子可以被化简为一个一次多项式。然后我们大力算出多项式每一次大力计算即可当然，我们显然需要取模偷懒233.#include<map>#include<cmath>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<alg

2017-07-26 21:15:22 270

原创 bzoj1942: [Ceoi2007]Ministry

传送门我们在建树的时候求出每个节点的哈希值哈希函数你就乱搞一下反正出题人不会来卡你哈希#include<map>#include<cmath>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 100

2017-07-26 21:07:33 330

原创 bzoj1939: [Croatian2010] Zuma

传送门看英文题解的辣。上图：翻译过来是： f[i][j][k]表示消除第i个到第j个珠子，且第i个珠子前面有k个同色珠子的最优解。有三种转移： 1.插入一个：f[i][j][k]=f[i][j][k-1]+1 2.k=K-1时在前面插入之后消掉：f[i][j][k]=f[i+1][j][0]; 3.消除中间一段后和前面合并。要求两段同色： f[i][j][k]=f[

2017-07-26 21:04:20 530

原创 bzoj1935: [Shoi2007]Tree 园丁的烦恼

传送门在不强制在线的情况下我们为啥要去写树套树呢？首先我们将询问离散化，然后我们将每一个询问分成四个小的询问然后我们将修改和询问按照x坐标排序。每次树状数组暴力求解即可。时间复杂度O（（N+M)logN)#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>

2017-07-23 17:29:26 351

原创 bzoj1934: [Shoi2007]Vote 善意的投票

传送门看到假题，我们就应该想到网络流。从S向不睡的人连单向边，流量1 从睡的人向T连单向边，流量1 每对朋友之间连双向边，流量1 大力最小割一发就可以了。#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cstdlib>#define i

2017-07-23 17:21:45 297

原创 bzoj1933: [Shoi2007]Bookcase 书柜的尺寸

传送门 S前面那一坨就是max(hi) 然后就是大力dp 设f[i][j][k]表示前i本书，第一层长度和为j，第二层长度和为k的最小第三层长度。显然可以滚掉一维转移十分简单。#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cstdlib

2017-07-23 17:14:38 326

原创 bzoj1932: [Shoi2007]Setstack 集合堆栈机

传送门大力哈希乱搞。每次操作产生的新的set我们判断之前有没有出现过每次大力插入就可以了。至于判断交集并集，我们大力使用stl中的函数 algorithm里封装了两个函数是set_union和set_intersection，用于求集合的并和交。用法是set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(x

2017-07-23 17:07:47 355

原创 bzoj1926: [Sdoi2010]粟粟的书架

传送门对于第一问(R,C<=200)；预处理f[x][y][k],s[x][y][k].表示从(1,1)到(x,y)中大于等于k的数的和与大于等于k的数的个数。然后二分最小的数即可。对于第二问(R=1): 我们还是二分最小数。判断就变成了询问一段区间内大于等于x的数的和以及它们的个数。显然主席树可以处理这个#include<iostream>#include<cstdio

2017-07-13 21:49:24 204

原创 bzoj1925: [Sdoi2010]地精部落

传送门我们设f[i][j]表示前i个数，第i个数排名是j的方案总数。我们可以强制第1个数是山峰。然后我们可以将整个序列高度取反，得到其他的方案数。然后我们发现这样做的时间复杂度是O（N^3）的加上前缀和优化就是O（N^2）了var f:array [0..1,0..5005] of longint; n,i,j,x,p:longint;begin read(n,p);

2017-07-13 21:34:29 261

原创 bzoj1924: [Sdoi2010]所驼门王的宝藏

传送门我们首先可以用O（NlogN）的时间建出来所有的边。然后我们大力tarjan求联通块之后大力拓扑排序一发就可以了。#include<cstdio> #include<iostream>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#include<vector>#include<

2017-07-12 21:50:25 440

原创 bzoj1923: [Sdoi2010]外星千足虫

传送门返现答案给出的是一些xor和的条件这个显然可以用高斯消元做加上bitset优化可以做到O（MN^2/w)#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cstdlib>#include<bitset>#define ll long

2017-07-12 21:46:14 191

原创 bzoj1922: [Sdoi2010]大陆争霸

传送门我们假设d1[i]表示机器人到达i的最短时间 d2[i]为结界消失的最短时间则一个点可以被访问到的最短时间为max(d1[i],d2[i]）我们跑一遍最短路等到该节点满足条件就向外扩展#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#incl

2017-07-12 21:40:23 226

原创 bzoj1913: [Apio2010]signaling 信号覆盖

传送门我们发现凸四边形贡献为2，凹四边形贡献为1 而且四边形总个数=C（n,4）所以我们只要知道凹四边形的个数就可以了我们枚举在凹四边形中内角大于180的点然后我们将其他点按照极角序排序枚举极角差刚刚不小于π的两条边那么这两条边之间的点和其中一条边上的点不包含中间点。由于按照极角排序，那么枚举的时间复杂度是O(n)。设p为不包含中间点的三角形个数，那么以该点为中间点

2017-07-11 22:03:05 298

原创 bzoj1912: [Apio2010]patrol 巡逻

传送门 k=0显然每条边都要走两次，答案=(n-1)*2 k=1我们找到树上最长链，在两段连边在环上的就不用再走一遍了答案=(n-1)-链长+1 k=2在k=1的基础上将那些边编圈变为-1，再跑最长链不再环上显然只要一遍但是在两个环上要走两遍。答案=(n-1)-链长1+1-链长2+1#include<iostream>#incl

2017-07-11 21:54:14 225

原创 bzoj1911: [Apio2010]特别行动队

传送门首先得到转移方程： f[i]=max(f[j]+a*(sum[i]-sum[j-1])^2+b*(sum[i]-sum[j-1])+c) 然后我们斜率优化一发：如果j>k且j比k更优 f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i] 然后……….就没有了#include<io

2017-07-09 21:59:23 177

原创 bzoj1910: [Ctsc2002] Award 颁奖典礼

传送门首先一个很显然的状态：f[i][j][k][0-2]表示在第i行左边界是j右边界是k，现在在上面/中间/下面的最优解然后我们大力枚举边界的时间复杂度是O（N^5) 然后我们大力前缀和有话就变成了O（N^3)uses math;var a:array [0..205,0..205] of longint; f:array [1..3,0..205,0..205,0..205]

2017-07-09 21:53:38 252

原创 bzoj1905: Soldier 士兵控制的棋盘

传送门首先我们大力转换坐标系。然后我们做一遍扫描线求出矩形面积的交。然后我们减去在外面的部分，可以发现一定是等腰三角形在搞一个面积并就可以了时间复杂度O（NlogN）#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>

2017-07-09 21:46:53 300

原创 bzoj1898: [Zjoi2005]Swamp 沼泽鳄鱼

传送门首先我们发现lcm(2,3,4)=12很小于是我们预处理出12个时刻内所有合法转移然后我们大力矩阵乘法就可以了。#include<cstring>#include<cmath> #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm>#define ll long lo

2017-07-08 21:59:42 267

原创 bzoj1895: Pku3580 supermemo

传送门发现题目中的所有东西都可以用splay维护然后就理所应当的成了splay裸题了。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cstdlib>#include<cmath>#define N 300030using namespace std;int n,m,

2017-07-08 21:55:20 243

空空如也

空空如也