5 Tag_king

尚未进行身份认证

暂无相关简介

等级
TA的排名 3w+

HN集训比赛总结

天天被虐傻哦。。不写点总结就要废掉了。。Day1  T1应该是回文自动机的题,按照我的水平期望应该是40分。。然而我爆0了,因为少打了一对括号而挂在位运算上。。看到这种给几种变换的题如果不是搜索的话就要往DP想,就是状态转移嘛,但是我还是花了一点时间才想到。。时间多就看一看manacher吧。。   T2是LCT,看到题被吓傻,连暴力都不想写。。考场上期望应该是25-40分,看到要子树又不知道怎么

2015-07-05 19:08:05

[BZOJ3926]ZJOI2015诸神眷顾的幻想乡|后缀自动机

注意到非常关键的条件,只与一个空地相邻的空地数量不超过20个,也就是叶子不超过20个,这意味着啥?考虑u到v的路径,一定存在某个叶子,当以这个叶子为根的时候u是v的祖先,也就是说所有的序列都是某个叶子为根的树的一条直链,把一棵树看出一个trie那么我们要做的就是统计这最多20个trie拼成的大trie的不重复子串数量啦!陈老师是厉害呀…   窝只会SAM做法。。按大trie建出SAM,然后可以像3

2015-06-20 22:19:09

[BZOJ3998]TJOI2015弦论|后缀自动机

对SAM不太熟做这题想了很久才想清楚。。大爷们的博客都写的好简(我太弱)   首先对原串建SAM。。如果能求出f[i]表示以root走到状态i的路径为开头往后能得到的串的数量,我们就可以像线段树那样的查询了(26分?)。。设num[i]为已确定的一条root到i的路径对应的子串数量,当T=0的时候,显然num[i]=1,num[root]=0;对于T=1,root到i的路径对应的串还可以作为另一个

2015-06-20 22:15:19

[CODEVS3160]最长公共子串|后缀数组|后缀自动机

第一种做法是把两个字符串接起来,中间放一个奇怪的字符,然后建这个串的后缀数组,求出h数组,对于h[i]表示lcp(sa[i],sa[i-1]),如果sa[i]和sa[i-1]分布在奇怪的字符的两边就用h[i]更新答案。。   然后补了一下后缀自动机,就是裸题了,对一个串建SAM,另一个串在上面匹配即可。。 SA:#include<cstdio>#include<iostream>#inclu

2015-06-20 22:05:25

[BZOJ2730]HNOI2012矿场搭建|割点

首先最少数量显然大于1,那么考虑炸掉一个点,如果它不是割点并没有什么影响,如果是割点的话必须要满足炸开之后的每个联通块都有至少一个救援点。如果这个图没有割点的话选两个点放就行了,答案是C(n,2),否则求出每一个割点,把这个图按割点分割成若干个联通块,把这些联通块缩点就是一个树结构,要使树上任何一条边断掉之后分成的两块都有救援点,就一定要在每一个叶子块上放一个救援点。把所有叶子块的size乘起来就行

2015-06-20 22:00:17

[BZOJ4002]JLOI2015有意义的字符串|矩阵乘法

题目和字符串有啥关系吗。。。   熟悉特征方程就容易发现这其实是一个a[n]=c1∗a[n−1]+c2∗a[n−2]a[n]=c_1*a[n-1]+c_2*a[n-2]这样的数列的通项的一部分,a[n]=(b+d√2)n+(b−d√2)na[n]=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n,其中c1=b,c2=d−b24c_1=b,c_2=\

2015-06-20 21:58:14

[BZOJ3991]SDOI2015寻宝游戏|set|虚树

询问就是求包含所有宝藏点的最小子图(貌似叫虚树?   按dfs序用set维护宝藏点的序列,并把set中相邻点(头和尾也算相邻)在树中路径的距离累加记为sum,删除序列中第i个点时,设前面为l[i](l[1]=n),后面为ri,把l[i]到i和到r[i]的距离在sum中减去,并加上l[i]到r[i]的距离,插入是也是类似的。。

2015-06-20 21:43:27

[BZOJ2875]NOI2012随机数生成器|矩阵乘法

一开始想用等比数列公式搞,但是模数可能为合数。。然后裸上矩乘,注意要用快速乘要不然会爆long long。#include<cstdio>#include<iostream>#include<cmath>#include<memory.h>#define ll long longusing namespace std;ll m,a,c,x0,n,g,an;struct ju{

2015-06-20 21:40:42

[BZOJ3670]NOI2014动物园|KMP

其实这也是一道水题。。自已yy完之后思路乱的要死就挂了。。   先求正常的next数组嘛,然后next[i]向i连边,容易发现新next在i到1的路径上,且i往下走,后面点新next也会往下走,然后我们从1 dfs下去,把路径上的点记录下来,然后维护一个新next指针作为参数,由于新next是不会往上爬的所以这是O(N)的,num[i]的话显然等于新next[i]在树上的深度+1,然后就做完了。。

2015-06-20 21:38:06

[BZOJ3669]NOI2014魔法森林|LCT|最小生成树

这题证明我有多弱。。noip之前写了一发挂了由于noip不考这个我就没去调了,省选之前写了一发在火车上调了2h未果又弃了,第三次写不记得调了多久才过,最后发现后两次犯的一样的傻逼错误,以一个变量为参数调用两次同样void忘记这个变量在第一次调用时就变了。。不能再蠢。。 把边按a升序排序,不断加边,LCT维护b的 MST,不断更新答案就行了。。#include<cstdio>#include<io

2015-06-20 21:36:13

[BZOJ3668]NOI2014起床困难综合征|贪心

显然是可以按位做的。我们将二进制第i位初始时为0和1到最后的结果都求出来,扫一遍就行了,之后从高位向低位贪心,如果第i为初始为0能使最后为1这位就为0,否则如果初始为1可以且加上这位不超过m就为1,否则为0。#include<cstdio>#include<iostream>#define N 200005#define inf 0x7fffffffusing namespace std;

2015-06-20 21:34:33

Codeforces Round #306 div 2 solution

这场总的来说打的还行吧,不过fst了一题很郁闷。。感觉从pkusc回来看CF的英文题面就和看中文一样。。出AB的速度我觉得还是不错的。。没什么难题完全可以AK的,但是构造题有细节理不清,要加强处理复杂的关系的能力。。A:给一个字符串,问你能不能找到不重复的”BA”和”AB”我的做法是先找AB再找BA和先找BA再找AB各做一次。#include<cstdio>#include<iostream>

2015-06-05 10:13:45

FFT多项式乘法学习笔记

其实我不知道我是否真的理解了FFT,但是我会用FFT优化多项式乘法了QAQ。。(以下大多摘自算导前置知识1. 多项式  在一个代数域F上,关于变量x的多项式定义为形式和形式表示的函数A(x)=∑j=0n−1ajxj,其中a0…an−1为多项式各项的系数 A(x)=\sum_{j=0}^{n-1}a_jx^j,其中a0…an-1为多项式各项的系数2. 多项式的次数界  若多项式有非

2015-06-03 21:41:09

APIO2015 Skulptrues|贪心|DP

考场上这题爆0真是郁闷。。   按二进制位从高位开始贪心,当A等于1的时候对每一位记录f[i]f[i]表示前ii个使当前位为0且不与更高位冲突最少分几组,枚举上一块的右端点进行转移;当A>1的时候记录f[i][j]f[i][j]为前ii个分jj组是否能达到,转移同前。。

2015-06-03 21:11:44

[POJ1741]Tree |点分治

同样是点分治。。但是这题在合并的时候比较麻烦,假设重心为x,首先要从x向下求出子节点的深度,然后将子节点按深度排序,设排序后第ii个点过重心能到的最远的点为第r[i]r[i]个,那么显然r[i]r[i]是递减的,所以扫一遍就可以求出过重心的路径的贡献了。但是这里面还会用重复计算的,就是在重心的同一颗子树的两个点可能又被计算了,这个时候dfs每棵子树,按上面的方法把同一颗子树重复计算的去除就行了。#i

2015-06-03 21:01:56

[BZOJ2152]聪聪可可|树的点分治

学了学点分治,主要思想就是找重心来防止树退化成链这样的东西,感觉写的不是很顺但是1A了。。找到一个部分的重心之后答案变成两部分,一是过重心的路径,二是不过重心的路径,二可以递归地得到,一的话可以对每个重心向下求出每个子节点的深度mod 3,然后记录下余0,1,2的数量,然后0和0组合,1和2组合,要注意排除来自同一颗子树的点对的重复计算,还要注意点对是有顺序的而且可以相同。。#include<ios

2015-06-03 20:52:53

[BZOJ3969]WF2013 Low Power|二分答案|贪心

先排序,二分能量差,显然同个机器的两个芯片的电池的最小值是连续的,否则交换之后可以得到更优的解,那么贪心地选取2*n对连续的电池,如果能选出且它们的后面都可以放2*(k-1)个电池的这是一个可行答案。。#include<cstdio>#include<iostream>#include<algorithm>#include<memory.h>#define N 1000005using n

2015-06-03 20:52:39

[BZOJ3932]CQOI2015任务查询系统|主席树

CQOI好良心,都是裸题。。把任务差分裸上主席树就行了。。#include<iostream>#include<cstdio>#include<algorithm>#define ll long long #define N 100005#define M 4000010using namespace std;struct task{ int l,r,p;}t[N];st

2015-06-03 20:49:21

[BZOJ3997]TJOI2015组合数学|DP

这题的方法感觉比较巧妙,对于(i,j)(i,j)和(i′,j′)(i',j'),当且仅当i>i′i>i’且j<j′j<j’的时候(也就是(i,j)(i,j)在(i′,j′)(i’,j’)的左下方)这两点不可能出现在一条路径上,所以求出一个点集使其中任意两点满足上述条件,这个点集的最大权值和就是答案,那么可以把每一行翻转,做DP,f[i][j]=max(max(f[i−1][j],f[i][j−1]

2015-06-03 20:45:43

[BZOJ3931]CQOI2015网络吞吐量|最短路|最大流

网络流大裸题。。把在最短路上的边拉出来建图就行了。。#include<cstdio>#include<iostream>#define N 505#define M 100005#define inf 0x7fffffff#define INF 0x3f3f3f3f3f3f3f3fll#define ll long longusing namespace std;struct ed

2015-06-03 20:40:07

查看更多

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