- 博客(459)
- 收藏
- 关注
RSS订阅原创 NOIP2018爆炸记
感觉一年啥都没学Day 0今年去学车考啊，从没去过学车的我感到瑟瑟发抖。而且大部分都是用笔记本考的，感觉很舒服。早上10点出发，车上一直在看昨天FQY安利给我的番（平生第一次看番好鸡冻），不知不觉就到杭州了。在宾馆里颓到4点去学校，把那部番看完了。领了狗牌后开始研究考场，woc什么鬼啊，七百多人全挤一个大厅里，那还不吵死！真羡慕那些被分到机房里的人（不过要是XP的话就好玩了）。一看时间差不...
2018-11-11 22:28:06
411
原创 BZOJ4059: [Cerc2012]Non-boring sequences
线段树题目传送门这道题正解是启发式分治，不过线段树也能做。和这道题很像，同样记一个nxt[i]nxt[i]nxt[i]表示a[i]a[i]a[i]下一次出现的位置，枚举左端点，撤销[i,nxt[i]−1][i,nxt[i]-1][i,nxt[i]−1]，加上[nxt[i],nxt[nxt[i]]−1][nxt[i],nxt[nxt[i]]-1][nxt[i],nxt[nxt[i]]−1]，并...
2018-11-07 18:52:19
294
原创 codeforces Gym 101623 F（BZOJ5200）
启发式分治BZOJ题目传送门codeforces题目传送门题目大意： 有一种二叉树，每个节点有权值 ，并且满足它与所有祖先的权值互质。现在给出一个序列，问这个序列是否是一棵这种树的中序遍历。还有启发式分治这种操作。。。显然如果一个点要是一颗子树的根，那么它一定与这颗子树里的所有点互质。在序列上则为与一段包含它的区间互质。我们预处理出每个位置左右与它互质的第一个位置。对于一个区间，同时用...
2018-11-07 18:31:09
324
原创 codeforces 992E. Nastya and King-Shamans
树状数组 二分题目传送门题目大意： 维护一个数列，每次操作为先修改一个数，再询问是否存在一个位置iii满足w[i]=sum[i−1]w[i]=sum[i-1]w[i]=sum[i−1]并输出这个位置。妙蛙问题要求出满足 Ax=sumx−1A_x=sum_{x−1}Ax=sumx−1 的位置，这个可以转化为 sumx=2sumx−1sum_x=2sum_{x−1}sumx=2sumx...
2018-11-06 21:16:38
320
原创 codeforces 1066E. Binary Numbers AND Sum
前缀和题目传送门疯狂划水题目大意： 两个很大的二进制数a,ba,ba,b，每次把答案加上a&ba\&ba&b并把bbb左移一位。求最终答案。考虑aaa的每一位对答案的贡献。如果这一位是000没有贡献，否则贡献为2i∗sum[i]2^i*sum[i]2i∗sum[i]，其中sum[i]sum[i]sum[i]为bbb从最高位到第iii位的1的个数。扫一...
2018-11-06 19:40:28
242
1
原创 codeforces 700B. Connecting Universities
贪心题目传送门题目大意： 一棵树上有2k2k2k个关键点，把这些关键点两两配对，贡献为配对点的距离之和。求最大贡献。树上两点之间的距离为dep[x]+dep[y]−2∗dep[lca(x,y)]dep[x]+dep[y]-2*dep[lca(x,y)]dep[x]+dep[y]−2∗dep[lca(x,y)]。对于这2k2k2k个点，它们的深度之和是确定的，那么我们要使尽可能多的lca深度尽...
2018-11-06 16:54:52
205
原创 codeforces 999F. Cards and Joy
DP题目传送门题目大意： 有nnn个人n∗kn*kn∗k张卡片，每个人都要分到kkk张卡片。卡片上有数字，每个人也有一个数字，当一个人分到iii张和他的数字一样的卡片时会有h[i]h[i]h[i]的贡献，求最大贡献。设g[i][j]g[i][j]g[i][j]表示iii张卡片分给jjj个人的最大贡献，那么有g[i][j]=max{g[i−p][j−1]+h[p]}g[i][j]=max\{g...
2018-11-05 20:03:45
195
原创 codeforces 1067A. Array Without Local Maximums
DP题目传送门题目大意： 有一个数列，满足a1≤a2,an≤an−1,ai≤max(ai−1,ai+1)a_1\leq a_2,a_n\leq a_{n-1},a_i\leq max(a_{i-1},a_{i+1})a1≤a2,an≤an−1,ai≤max(ai−1,ai+1)且1≤ai≤2001\leq a_i\leq 2001≤ai≤200。现在有一些数不知道，问原数列的所...
2018-11-05 14:40:40
375
2
原创 BZOJ2662: [BeiJing wc2012]冻结（洛谷P4822）
分层图最短路BZOJ题目传送门洛谷题目传送门同这道题，稍微改一改就好了。代码：#include<queue>#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 5005#define M 500005#defin...
2018-11-04 21:14:52
219
原创 codeforces 165E. Compatible Numbers
高维前缀和题目传送门学了一发高维前缀和。一般我们求多维前缀和是用容斥的，但是当维度很高时会很烦，这时就要用另一种求前缀和的方法。打个比方，假设我们要求二维前缀和：for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]+=a[i][j-1];for (int i=1;i<=n;i++) ...
2018-11-04 16:58:32
218
原创 BZOJ1855: [Scoi2010]股票交易（洛谷P2569）
单调队列 DPBZOJ题目传送门洛谷题目传送门设f[i][j]f[i][j]f[i][j]表示前iii天还剩jjj股的最多钱数。有四种转移方式。1.之前没有股票，直接从这一天开始买，f[i][j]=−j∗APi(j∈[0,ASi])f[i][j]=-j*AP_i\quad(j\in[0,AS_i])f[i][j]=−j∗APi(j∈[0,ASi])2.这一天啥也不干，f[i][j]=...
2018-11-02 20:55:52
267
原创 BZOJ1296: [SCOI2009]粉刷匠（洛谷P4158）
DPBZOJ题目传送门洛谷题目传送门我连背包都不会了做两遍DP，第一遍求出每一行刷kkk次分别最多能刷对多少个格子。第二遍就把第一遍的当作分组背包来选物品就好了。设f[i][j]f[i][j]f[i][j]表示当前这行做到第iii列，刷了jjj次的最多格子数。那么有f[i][j]=max{f[k][j−1]+max{s0i−s0k,s1i−s1k}}f[i][j]=max\{f[k][j...
2018-11-02 18:59:35
212
原创 BZOJ5334: [Tjoi2018]数学计算（洛谷P4588）
线段树BZOJ题目传送门洛谷题目传送门线段树维护每次操作的数，撤销就把那个位置变成1就好了。代码：#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 100005#define F inlineusing namespace ...
2018-11-02 10:41:21
209
原创 洛谷P3522 [POI2011]TEM-Temperature（BZOJ2276）
单调队列洛谷题目传送门BZOJ题目传送门单调队列维护最低温度递减的序列，同时保证队头的最低温度低于队尾的最高温度就好了。代码：#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 1000005#define F inlineu...
2018-11-02 09:34:37
221
原创 BZOJ3875: [Ahoi2014&Jsoi2014]骑士游戏（洛谷P4042）
最短路 DPBZOJ题目传送门洛谷题目传送门很显然有f[u]=min(ku,su+∑f[v])f[u]=min(k_u,s_u+\sum f[v])f[u]=min(ku,su+∑f[v])。但是这个是有后效性的，那么就用spfa搞（也可以用类似拓扑的方法做）。每次更新一个点后把所有指向它的点都加到队列里更新即可。代码：#include<queue>#include&l...
2018-10-31 14:06:22
185
原创 BZOJ2462: [BeiJing2011]矩阵模板
哈希题目传送门二维哈希就好了。注意不要用unsigned long long，会T的（BZOJ 32位机子）。代码：#include<cstdio>#include<cstring>#include<algorithm>#define N 1005#define M 105#define F inlineusing namespace std...
2018-10-30 08:34:20
189
原创 BZOJ2982 combination
BZOJ2982: combinationlucas题目传送门裸题不解释。代码：#include&lt;cstdio&gt;#include&lt;algorithm&gt;using namespace std;const int p=10007;#define N p+5int t,n,m,c[N],iv[N];int C(int n,int m){ if (n&lt;...
2018-10-29 14:52:46
168
原创 洛谷P3573 [POI2014]RAJ-Rally（BZOJ3832）
拓扑排序 堆洛谷题目传送门BZOJ题目传送门妙蛙注意到这是一个DAG，那么我们可以一遍拓排求出从起点到iii为最长路ds[i]ds[i]ds[i]和iii到终点的最长路dt[i]dt[i]dt[i]（s向所有入度为0的点连边，所有出度为0的点向t连边）。若一条最长路lll经过(u,v)(u,v)(u,v)，那么必有l=ds[u]+dt[v]+1l=ds[u]+dt[v]+1l=ds[u]+...
2018-10-29 13:52:35
198
原创 BZOJ1096: [ZJOI2007]仓库建设（洛谷P2120）
斜率优化BZOJ题目传送门洛谷题目传送门设f[i]f[i]f[i]为前iii个工厂且在iii建仓库的最小代价。那么有f[i]=min{f[j]+c[i]+∑k=jip[k]∗(X[i]−X[k])}f[i]=min\{f[j]+c[i]+\sum_{k=j}^ip[k]*(X[i]-X[k])\}f[i]=min{f[j]+c[i]+∑k=jip[k]∗(X[i]−X[k])}。因为第nn...
2018-10-28 19:44:32
180
原创 BZOJ2721: [Violet 5]樱花（洛谷P1445）
数学BZOJ题目传送门洛谷题目传送门来因式分解。1x+1y=1n!xy−n!(x+y)=0(x−n!)(y−n!)=(n!)2\frac1x+\frac1y=\frac1{n!}\\xy-n!(x+y)=0\\(x-n!)(y-n!)=(n!)^2x1+y1=n!1xy−n!(x+y)=0(x−n!)(y−n!)=(n!)2然后算n!n!n!的因数个数就好了。代码：#i...
2018-10-28 15:14:39
304
原创 BZOJ1260: [CQOI2007]涂色paint（洛谷P4170）
区间DPBZOJ题目传送门洛谷题目传送门设f[l][r]f[l][r]f[l][r]为涂[l,r][l,r][l,r]需要的最少次数。那么若左右端点的颜色相同，则有f[l][r]=min(f[l+1][r],f[l][r−1])f[l][r]=min(f[l+1][r],f[l][r-1])f[l][r]=min(f[l+1][r],f[l][r−1])。然后枚举断点kkk，f[l][r]=...
2018-10-28 14:53:28
160
原创 洛谷P3512 [POI2010]PIL-Pilots（BZOJ2096）
单调队列洛谷题目传送门BZOJ题目传送门划水用两个指针推，单调队列维护最大最小值。代码：#include<cctype>#include<cstdio>#include<cstring>#include<algorithm>#define N 3000005#define F inlineusing namespace std...
2018-10-27 15:59:48
223
原创 BZOJ1139: [POI2009]Wie（洛谷P3489）
最短路 状压BZOJ题目传送门洛谷题目传送门设f[i][s]f[i][s]f[i][s]为到点iii能杀的怪的状态为sss的最短路。用Dij刷分层图最短路的时候转移就好了。代码：#include<queue>#include<cctype>#include<cstdio>#include<cstring>#include<al...
2018-10-27 14:51:28
174
原创 BZOJ3747: [POI2015]Kinoman（洛谷P3582）
线段树BZOJ题目传送门洛谷题目传送门设nxt[i]nxt[i]nxt[i]为与f[i]f[i]f[i]相同的下一个位置。枚举左端点，用线段树维护最大值。假设当前推到lll，那么把[l,nxt[l−1]][l,nxt[l-1]][l,nxt[l−1]]的贡献减去，把[nxt[l],nxt[nxt[l]]−1][nxt[l],nxt[nxt[l]]-1][nxt[l],nxt[nxt[l]]−...
2018-10-27 09:31:59
138
原创 BZOJ1123: [POI2008]BLO（洛谷P3469）
TarjanBZOJ题目传送门洛谷题目传送门显然不是割点的点答案都是(n−1)∗2(n-1)*2(n−1)∗2，我们只需要算一算割点的答案就好了。而割点的额外答案为DFS树上各个子树之间两两配对的贡献加上子树内和子树外的贡献。这些在Tarjan求割点的同时都可以顺带出来。#include<cctype>#include<cstdio>#include<cs...
2018-10-26 19:57:49
145
原创 BZOJ4419: [Shoi2013]发微博（洛谷P3998）
STLBZOJ题目传送门洛谷题目传送门数据结构蒙蔽了我的双眼。对每个人用一个set维护当前和他成为好友的人，并记录他发的微博数。那么对于两个人x,yx,yx,y，xxx对yyy的贡献即为从成为好友到解除好友中xxx发的微博数量，yyy同理。所以减一减答案就出来了。注意最后结束后还要算一遍。因为有些人还没有解除好友。代码：#include<set>#include<...
2018-10-26 18:35:47
212
4
原创 洛谷P3431 [POI2005]AUT-The Bus（BZOJ1537）
树状数组洛谷题目传送门BZOJ题目传送门神TM裸的二维偏序我没看出来把其中一维离散后，用另一维排序。然后树状数组维护就好了。代码：#include<cstdio>#include<cctype>#include<cstring>#include<algorithm>#define N 100005#define F inline...
2018-10-25 19:10:53
155
原创 BZOJ1833: [ZJOI2010]count 数字计数（洛谷P2602）
乱搞BZOJ题目传送门洛谷题目传送门把题目转化成求1到n的出现次数。设f[i]f[i]f[i]表示第iii位出现的总次数，那么有f[i]=f[i−1]∗10+10i−1f[i]=f[i-1]*10+10^{i-1}f[i]=f[i−1]∗10+10i−1（先不管前导0）。我们对n的每一位进行处理。对于第iii位，没有到达边界的数字答案即为10i−1+f[i−1]∗a[i]10^{i-1}+...
2018-10-25 18:06:03
164
原创 BZOJ1511: [POI2006]OKR-Periods of Words（洛谷P3435）
KMPBZOJ题目传送门洛谷题目传送门一个串的最小循环节为i−nxt[i]i-nxt[i]i−nxt[i]，而如果要求最大循环节就是把nxt[i]nxt[i]nxt[i]跳到刚好不是000为止。求出nxtnxtnxt后我们可以扫一遍把nxt[i]nxt[i]nxt[i]赋成nxt[nxt[i]]nxt[nxt[i]]nxt[nxt[i]]。之后i−nxt[i]i-nxt[i]i−nxt[i]...
2018-10-25 13:34:10
255
原创 BZOJ2212: [Poi2011]Tree Rotations（洛谷P3521）
线段树合并BZOJ题目传送门洛谷题目传送门学了发线段树合并。对于一棵子树，无论它是否交换，都不会影响到这棵子树外的其它节点。那么我们只要每一次取小的那个就好了。对每个节点开一棵权值线段树，每次把左右儿子合并上来。而左右儿子有两个贡献，分别为一个儿子左区间的数个数*另一个儿子右区间的数个数，对这两个取min即可。代码：#include<cctype>#include<...
2018-10-25 11:29:10
117
原创 BZOJ2115: [Wc2011] Xor（洛谷P4151）
线性基BZOJ题目传送门洛谷题目传送门妙蛙假如我们已经找到一条路径，如果要使答案变大，显然只能在这条路径上加环。而从路径到环的边会走两遍，因此不会影响答案。那么我们把所有环扔进线性基里，然后用这条路径求出最大值即可。至于这条路径，其实是可以随便选的。因为如果另一条路径比它更优，它们就会形成环，在线性基里就会变成另一条路径了。代码：#include<cctype>#inc...
2018-10-25 08:56:36
144
原创 BZOJ1135: [POI2009]Lyz（洛谷P3488）
Hall定理 线段树BZOJ题目传送门洛谷题目传送门Hall定理：一张二分图有完美匹配的充要条件为对于左边点集任意一个子集（大小为∣S∣|S|∣S∣），都存在至少∣S∣|S|∣S∣个右边的点有边相连。对于这道题，我们只需要判断连续一段区间内的人是否满足即可。即∀ l,r ∑i=lrai≤(r−l+1+d)∗k\forall\ l,r\ \sum_{i=l}^ra_i\l...
2018-10-24 21:10:19
165
原创 BZOJ1131 [POI2008]Sta（洛谷P3478）
BZOJ1131: [POI2008]Sta（洛谷P3478）DFSBZOJ题目传送门洛谷题目传送门先一遍DFS算出每个节点的sizesizesize并统计根节点的答案。而对于一个子节点，当它作为根时，它子树到它的距离-1，其他点的距离+1。那么全算出来就好了。代码：#include&lt;cctype&gt;#include&lt;cstdio&gt;#include&lt;cs...
2018-10-24 18:28:39
159
原创 BZOJ1108: [POI2007]天然气管道Gaz
水题目传送门总代价即为∑xj−xi+yi−yj\sum x_j-x_i+y_i-y_j∑xj−xi+yi−yj，与顺序无关。那么直接算就好了。代码：#include<cstdio>#define N 50005using namespace std;typedef long long LL;int n; LL sx1,sx2,sy1,sy2;int main(...
2018-10-24 16:18:57
147
原创 洛谷P3891 [GDOI2014]采集资源
DP题目传送门预处理f1[i]f1[i]f1[i]表示用iii的资源能得到的最大效率。因为苦工的数量无限制，那么这就是一个完全背包。设f2[i][j]f2[i][j]f2[i][j]表示第iii时间剩下jjj的资源能得到的最大效率。那么就可以借助f1f1f1进行转移了。注意一有答案就要退出，不然会T。代码：#include<cstdio>#include<cstri...
2018-10-23 20:54:46
304
原创 BZOJ1112: [POI2008]砖块Klo（洛谷P3466）
平衡树BZOJ题目传送门洛谷题目传送门动态维护中位数，平衡树上一发就好了。代码：#include<cctype>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 500005#define F inlineu...
2018-10-22 20:25:41
169
原创 BZOJ1367: [Baltic2004]sequence
左偏树题目传送门首先把tit_iti都减掉iii，这样就可以构造非递减的ziz_izi了。对于原序列tit_iti，我们一定能把它分成若干段，使得它们都是非递增的（对于非递减的直接取zi=tiz_i=t_izi=ti即可）。此时ziz_izi都取这一段的中位数为最优。每次把新加入的数单独算一段，然后不断合并最后两段直到最后一段的中位数不小于倒数第二个为止。而维护中位数可以用左偏...
2018-10-19 20:12:15
147
原创 BZOJ4540: [Hnoi2016]序列（洛谷P3246）
莫队 ST表 单调栈BZOJ题目传送门洛谷题目传送门考虑添加r+1r+1r+1到[l,r][l,r][l,r]中产生的贡献。显然多了r−l+2r-l+2r−l+2个区间。设[l,r+1][l,r+1][l,r+1]的最小值取在ppp点，那么ppp产生的贡献为w[p]∗(p−l+1)w[p]*(p-l+1)w[p]∗(p−l+1)，剩下的贡献可以前缀和搞一搞。ppp可以ST表预处理后直接得到。...
2018-10-18 21:17:43
141
原创 BZOJ3131: [Sdoi2013]淘金（洛谷P3303）
数位DP 贪心BZOJ题目传送门洛谷题目传送门很显然最后有金子的格子坐标一定可以分解成2,3,5,72,3,5,72,3,5,7的幂次。暴枚后发现只有146721467214672个。那么离散化之后就可以DP求出每个数字一共出现多少次了。因为这是二维坐标，那么就相当于一个序列中取前kkk大的数对，每个数对的贡献为w[i]∗w[j]w[i]*w[j]w[i]∗w[j]。可以排序后对每一个位置...
2018-10-18 18:01:38
210
原创 BZOJ2750: [HAOI2012]Road（洛谷P2505）
最短路 拓扑排序BZOJ题目传送门洛谷题目传送门对于每个点跑一遍最短路（Dij很稳，spfa也可以）。一条边在最短路上当d[x]+d=d[v]d[x]+d=d[v]d[x]+d=d[v]。我们对跑出来的图进行拓扑排序，正着做一遍求出从起点到达点iii的最短路方案s1[i]s1[i]s1[i]，倒着做一遍求出以点iii为起点的最短路方案s2[i]s2[i]s2[i]。一条边在这张图里的贡献就是...
2018-10-17 19:44:25
200
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人