4 sillyf

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 8w+

BZOJ 4504:K个串 [主席树][贪心]

题意给出一个长度为nn的数列an{a_n},一个区间[l,r][l,r]的和定义为其中的数字之和,相同的数字不重复算求第k大的和题解首先怎么求一个区间的和.对于aia_i维护它之前最近的与它相同的数的位置pre[ai]pre[a_i]对于固定的右端点维护每一个左端点到它的和,可以用线段树则从左往右扫描对于右端点ara_r只要把pre[ar]+1pre[a_r]+1到rr

2018-01-15 18:01:47

Codeforces 600E. Lomsat gelral [dsu on tree]

题解传送门新姿势dsu on tree 模板题#include#include#include#define N 100005#define LL long longusing namespace std;vectorint>e[N];int n,c[N],sz[N],son[N],num[N],mx;LL ans[N],sum;bool vis[N];inli

2018-01-15 17:59:35

HDU 4787 GRE Words Revenge [二进制分组][AC自动机]

题意维护支持插入和询问的AC自动机,强制在线题解二进制分组(可以百度xhr的答辩论文)对于每一个分组单独建立AC自动机,合并分组时暴力重构还有一个细节是对于重串,要直接踢掉,可以用set或者hash判一下因为一样的串在不同的AC自动机里出现还是当一次算代码又慢又长…大概是string的读入拖慢速度,用时倒数…//按我的打法原本AC自动机的初始状态各个用来模拟指针

2018-01-15 07:30:37

洛谷 P3796 【模板】AC自动机(加强版)

题面传送门题解随便统计一下每个单词出现的次数详见代码#include#include#include#include#includeusing namespace std;int n,size,pos[155];struct node{ int fail,lk[26],sum; bool mark;}ac[11000];char s[155]

2018-01-15 07:28:48

BZOJ 3932: [CQOI2015]任务查询系统 [主席树]

题意给出nn个由三元组(si,ei,pi)(s_i,e_i,p_i)表示的区间,si,eis_i,e_i表示头尾(包括头尾),pip_i表示这个区间的权重给出mm个询问,询问包含位置xx的按权重排序前kk小的区间的权重和输入先给出所有三元组,询问强制在线题解主席树的权值线段树按照pip_i来搞,因为值域比较大,要离散一下所有三元组先读入,拆成两个端点每个端点维护两个

2018-01-11 14:46:19

BZOJ 4140: 共点圆加强版 [二进制分组][凸包]

题意支持在平面直角坐标系内进行操作:1.加入一个圆心在(x,y)(x,y)且过原点的圆2.询问点(x,y)(x,y)是否被之前加入的所有圆包含(在圆内或圆心上)强制在线题解询问即判断(X−xi)2+(Y−yi)2≤x2i+y2i(X-x_i)^2+(Y-y_i)^2\leq {x_i^2}+{y_i^2}是否成立整理一下式子,得−X/Y∗xi+(X2+Y2)/(2∗

2018-01-11 10:00:39

BZOJ 3527: [Zjoi2014]力 [卷积][FFT]

题意即求Ei=∑i−1j=1(qj/(j−i)2)−∑nj=i+1(qj/(j−i)2)E_i=\sum_{j=1}^{i-1}(q_j/(j-i)^2)-\sum_{j=i+1}^{n}(q_j/(j-i)^2)题解令f(x)=qx ,g(x)=1/x2f(x)=q_x\ ,g(x)=1/x^2则Ei=∑i−1j=1f(j)g(j−i)−∑nj=i+1f(j)g(j−i)E_

2018-01-11 09:59:33

洛谷 P3803 【模板】多项式乘法(FFT)

题面题解fft模板题单向膜拜:从多项式乘法到快速傅里叶变换FFT 学习笔记大致理解为将多项式从系数表示法转化为点值表示法然后再变回系数表示法#include#include#include#define N 2621450#define pi acos(-1.0)using namespace std;int n,m,len,R[N];struc

2018-01-11 09:58:10

POJ 2891 Strange Way to Express Integers[中国剩余定理(非互质)][扩展欧几里得]

题意给出n个一元一次同余方程X≡ai(modX≡a_i(mod ri)r_i)求最小的XX,模数不一定互质题解模数非互质不能直接上中国剩余定理任意找两个式子出来:{X≡a1(mod r1)X≡a2(mod r2)\left\{\begin{array}\\X≡a_1(mod \ r_1)\\{X≡a_2(mod\ r_2)}\end{array}\right. 可以

2018-01-11 09:57:06

POJ 1006 Biorhythms [中国剩余定理]

题意给出a,b,c,d,求最小的SS满足:S≡a(modS≡a(mod 23)23) S≡b(modS≡b(mod 28)28) S≡c(modS≡c(mod 33)33) 输出S-d题解orz zzk 中国剩余定理直接求这个方程组就好了#include#include#define T 21252using namespace std;int

2018-01-11 09:54:06

BZOJ 3196: Tyvj 1730 二逼平衡树 [树套树]

题解不会写,标记一下,抄的是同学的板子#include<cstdio>#include<algorithm>#define N 50010#define M N*30using namespace std;int n,m,sz,ans,a[N],root[M],size[M],fa[M],ch[M][2],v[M];inline char nc(){ static char buf[

2018-01-09 19:01:43

codeforces449D&&51nod 1407 与与与与 [dp][容斥原理]

中文题面题解设f[x]f[x]为&x==x的数的个数,g[x]g[x]为x转化为二进制以后1的个数转化一下,求等于0的组数即 所有组合情况-含有位为1的组合数容斥求一下含有位为1的组合数∑x=1220=(−1)g[x]−1∗(2f[x]−1)\sum^{2^{20}}_{x=1}=(-1)^{g[x]-1}*(2^{f[x]}-1)2的幂减一是因为不能一个都不选,

2018-01-09 18:58:07

51nod 1406 与查询 [dp]

题面传送门题解一个数&x==x的条件可以理解为转换为二进制后,x为1的位要对应为1设f[x]f[x]为范围内与&x==x的数的个数若yy转换为二进制后的所有1位x都有(yy为xx的子集),则对f[x]f[x]有贡献的数一定对f[y]f[y]有贡献所以可以枚举子集转移,但是这样算会有重复,于是从高位向低位转移,想象一下把x​x​拆几个1掉就可以变成y​y​了记得加输入输出优化

2018-01-09 18:56:19

51nod 1486 大大走格子[容斥原理]

题面传送门题解好早以前就考过,当时根本不会O(nm)O(nm)的dp很简单,但是不够用啊。考虑通过障碍物转移

2018-01-09 18:54:53

cf582B&&51nod 1566 重复的最长不下子序列

题意给出一个长度为n的循环节,问有t个这样循环节的数列的最长不下降子序列题解若要让一个循环节的所有元素都出现则最多要n个循环节,若有相同的应该更少,因为n不大,直接构造长度为n×nn \times n的数列做最长不下降子序列.若剩下还有没用上的,一定是选择出现次数最多的元素插在n×nn \times n的数列中,不到n节的话直接做肯定是不会错的…貌似还有矩阵加速的方法,不太会

2018-01-08 20:39:58

BZOJ 1251: 序列终结者 [splay]

题意现在需要你维护一个长度为n的序列,需要支持三种操作:1.区间加 2.区间翻转 3.区间求最大值题解很明显splay裸题,复习了一下splay,感觉忘得一干二净按下标建splay树对于区间加和区间翻转:把l-1 splay到根,把r+1 splay到根的右儿子,然后直接对根的右儿子的左儿子打标记做起来习惯把[0,n+1][0,n+1]转到[1,n+2][1,n

2018-01-08 13:02:44

莫队初步

参考blog了解学习了一下莫队,果然是个很好用的东西啊,我为什么现在才学…用途处理一些离线的区间问题一般来说,令ansi,jans_{i,j}表示询问区间[i,j][i,j]的答案,则ansi,jans_{i,j}可以在常数的复杂度内由ansi−1,jans_{i-1,j}或ansi+1,jans_{i+1,j}或ansi,j−1ans_{i,j-1}或ansi,j+1ans_

2018-01-03 21:07:58

BZOJ 2124: 等差子序列 [树状数组][hash]

2124: 等差子序列题面传送门题解只要找有没有长度为3的等差子序列是一个排列,用一个辅助数组b[i]=0/1b[i]=0/1记录ii有没有出现过按顺序修改bb,如果数为xx,则查找是否有以xx为等差中项的数对(l,r)(l,r),并且这对数应该是一个出现了另一个没出现(b[l]==1b[l]==1&&b[r]==0 b[r]==0)可以用树状数组或线段树维护bb的hash值,正着一个反着一个,判断

2017-12-25 21:13:37

BZOJ 1911: [Apio2010]特别行动队 [斜率优化dp]

1911: [Apio2010]特别行动队题意给出一个常数a,b,c和数列{xnx_n},将其分成若干段每一段至少有一个数,并且每一段将产生一个贡献为a∗x2+b∗x+ca*x^2+b*x+c找到一种分组方案使贡献和最大解题报告前两天写的没来得及写博客现在找不到推式子的草稿纸了…只好再推一遍…斜率优化设置状态fif_i表示分到第ii个数,且以这个数为当前最后一组结尾的最大贡献和转移时若有j<kj<k

2017-12-25 21:08:57

BZOJ 1927: [Sdoi2010]星际竞速 [最小费用最大流]

1927: [Sdoi2010]星际竞速题面传送门题解类似DAG上的最小路径覆盖最小费用流,建图 令源点为SS,汇点为TT:S向所有入点连容量为1,费用为0的边S向所有出点连容量为1,费用为aia_i的边所有出点与T连容量为1,费用为0的边对于有边的(ui,vi)(u_i,v_i)其中ui<viu_i<v_i,从uiu_i的入点连向viv_i的出点容量为1,费用为wiw_i的边理解一下:相当于如果要

2017-12-25 21:08:01

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!