分类 - bzoj

2017-04-07 10:31:20    195    0    0
首先将图缩成dag 如果存在多于一个出度等于0的强连通分量,说明无解 如果只有1个出度等于0的强连通分量,则这个强连通分量的大小就是答案 练习手工栈... ``` #include #define mset(a,b) memset(a,(b),sizeof(a)) #define scan(a) scanf("%d",&a) #define debug puts("Hello,world.") using namespace std; typedef long long ll; typedef unsig
2017-04-06 21:42:26    265    0    0
因为SDOI常年cena评测还不开栈, 导致树链剖分\tarjan等根本没人干写, 神通广大的OIer们就开始写手工栈, 强行代替系统栈 * 树链剖分 * 第一次dfs * 开个数组模拟访问栈, 存节点编号 * 每次取顶上的尝试扩展下一个节点 * 扩展到就将它进栈, 重新取栈顶元素 * 扩展不到就说明这个节点的子树访问完了
2017-04-06 15:41:53    89    0    0
枚举第一列有没有雷, 剩下的列的情况就确定了. ``` #include #define mset(a,b) memset(a,(b),sizeof(a)) #define scan(a) scanf("%d",&a) #define debug puts("Hello,world.") using namespace std; typedef long long ll; typedef unsigned long long ull; inline int init(){ int x = 0,f =
2017-03-04 14:25:00    169    0    0
  • 题意:求第k(<109)个不含平方因子的数
  • sol:
    • 不难发现此题满足二分性质,答案区间为[k,4k)
    • 现在的问题转化为如何快速计算区间[1,n]内不含平方因子的数有几个
    • 可以用容斥原理:
      Q=n(4,9...)+(36,100,...)...
    • 可以看出系数就是
2017-04-04 20:57:36    232    0    0

询问x串在y串中出现几次,相当于询问y中多少个前缀的后缀是x
AC自动机中trie树的正常边维护了一个前缀信息,fail边维护了一个后缀信息,也就是说从根节点到表示y串路径上有多少节点的fail边直接或间接指向x节点
我们将fail边反向,由这些边构成的有向图所有点的入度为1,是一颗树,对应询问(x,y)就变成了x对应节点的子树上有多少y的前缀节点
每次暴力去遍历x的子树显然可以卡到O(nm)
题目不要求在线,我们想离线做法,我们发现每个串y的前缀节点构成一条根节点到y串节点的路径,也就是说我们去dfs原trie,访问y时的调用栈内所有的点都是y串的前缀,我们为这些点设置一个权值1, 询问就变成了x串子树上节点权值和,而到了y节点,所有对应它的询问就都可以处理了,而维护子树权值和的工具就是树状数组维护dfs
做法显而易见,dfs trie,每访问一个节点它的权值+1,然后处理所有当前节点的询问,退出时权值1
时间复杂度O(n+mlogn)

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<set>
  7. #include<map>
  8. #include<vector>
  9. #include<stack>
  10. #include<queue>
  11. #define scan(a) scanf("%d",&a)
  12. #define mset(a,b) memset(a,(b),sizeof(a))
  13. using namespace std;
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. const int inf = 0x3f3f3f3f;
  17. const int maxn = 100005;
  18. int m;
  19. namespace bit{
  20. int s[maxn];
  21. inline int lowbit(int x){
  22. return x&-x;
  23. }
  24. void a
2017-04-04 17:11:43    139    0    0

http://www.lydsy.com/JudgeOnline/problem.php?id=3172
做法1: 直接建出论文的sam,每个单词间添加一个非法字符,最后在sam中匹配所有单词,输出|right|, 太暴力了
做法2: 构建单词的ac自动机,保存fail边,所有fail边构成一个树结构,类似于sam中的suffix_link也是保存了节点间的后缀关系,插入的时候访问到的点count+1,最后按fail树的拓扑关系累加count值,最后输出每个单词对应ac自动机节点的

2017-04-01 22:15:28    377    0    0
首先建出禁忌串的AC自动机来, 把AC自动机上的正常边和$fail$边都一视同仁, 看成一个有向图对待, 答案就是从$0$节点开始随便走$len$步能走到几个禁忌串的期望 不妨新建节点$n+1$(与题干中意义不同)来辅助统计答案, 对于走一步能到禁忌串$endpos$的点$u$向$0$节点连边, 代表已经划分出一个禁忌串, 并且再向$n+1$连相同的边, 意义同上, 然后$n+1$只与$n+1$
2017-04-01 10:40:29    409    0    0
http://www.lydsy.com/JudgeOnline/problem.php?id=3143 不难想到一个贪心, 设每条边的期望经过次数为$EX(i)$, 那么我们按$EX(i)$给边从大到小排序, 然后依次给它编号$1..$, 就有 $$ ans = \sum i*EX(i) $$ 问题转化为怎么求$EX(i)$, 直接求是很困难的, 我们做过很多与点有关的期望题, 想想与点的信息
2017-04-01 09:40:57    190    0    0
设$f(i,j)$为Petya在$i$, Vasya在$j$的概率, 有如下关系式 $$ f(i,j)=f(i,j)p_ip_j+∑_{(i,x),(j,y)∈E}f(x,j)p_jgo_x+f(i,y)p_igo_y+f(x,y)go_xgo_y $$ 很显然是一个循环的转移, 没法递推, 所以$f(i,j)$移到右侧, 得到$n^2$个方程进行高斯消元, 并且有$f(a,b)=1$ 权限
2017-04-01 08:18:06    191    0    0
首先不难发现路径一定是一条$1\to n$的链加上一些环 而这些环与路径是否有交点完全无所谓, 因为图是联通的, 你完全可以走到某个环上的点再原路走回来, 这样环上的异或值取到了, 中间的路径由于经过两遍, 异或值抵消掉了 所以我们可以先$dfs$搞出所有环的异或值来, 然后用高斯消元. > 异或消元最后得到的是一组线性基,那么这些数能够异或出来的值,都是这些基线性组合形成的数 然后一组基要么