[BZOJ3798]特殊的质数 Description 求[A,B]之间的质数个数,并且满足X=Q^2+P^2,P,Q是正整数. Input 第一行输入A,B Output 输出有多少组P,Q满足条件 Sample Input 6 66 Sample Output 7 HINT 1<=A<=B<=3*10^8 题解:还有什么比表打错了更让人欲哭无泪的~ 注意一下几点: 1.分块不能太小,10^5很稳,再小有可能装不下了 2.2=1*1+1*1,也算~ 3.不要把x=i*i+0*0这样的算

「BZOJ 4228」Tibbar的后花园 Please contact lydsy2012@163.com! 警告 解题思路 可以证明最终的图中所有点的度数都 \(< 3\) ,且不存在环长是 \(3\) 的倍数的环.这是充分必要的,由于图不联通,其就是由若干个联通块组成的,每个联通块是一条链或者环长不是 \(3\) 的倍数的环,然后强上EGF就好了. 列出链的EGF和环的EGF \[ A(x)=x+\sum_{i\geq2}\dfrac{x^i}{2} \\ B(x)=\sum_{i>3,

「BZOJ 3645」小朋友与二叉树 解题思路 令 \(G(x)\) 为关于可选大小集合的生成函数,即 \[ G(x)=\sum[i\in c ] x^i \] 令 \(F(x)\) 第 \(n\) 项的系数为为权值为 \(n\) 的二叉树的方案数,显然有 \[ F(x)=F(x)^2G(x)+1\\ F^2(x)G(x)-F(x)+1=0 \\ F(x)=\dfrac{1\pm\sqrt{1-4G(x)}}{2G(x)} \] 当 \(x\to 0\) 时,\(F(x)\) 的值为 \(1\)

「BZOJ 4502」串 题目描述 兔子们在玩字符串的游戏.首先,它们拿出了一个字符串集合 \(S\),然后它们定义一个字符串为"好"的,当且仅当它可以被分成非空的两段,其中每一段都是字符串集合 \(S\) 中某个字符串的前缀.比如对于字符串集合 \(\{ "abc","bca" \}\),字符串 \("abb"\),\("abab"\)是"好"的 \(("abb"=

「BZOJ 4289」 PA2012 Tax 题目描述 给出一个 \(N\) 个点 \(M\) 条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点 \(1\) 到点 \(N\) 的最小代价.起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权 \(N \leq 10^5, M \leq 2 \times 10^5\) 解题思路 : 首先考虑一个暴力的做法,建一个新图,把每一条边看成新图的一个点' 对于原图的每一个点 \(u\) 对于边 \((u, x),

「BZOJ 2534」 L - gap字符串 题目描述 有一种形如 \(uv u\) 形式的字符串,其中 \(u\) 是非空字符串,且 \(v\) 的长度正好为 \(L\), 那么称这个字符串为 \(L-Gap\) 字符串 给出一个字符串 \(S\), 以及一个正整数 \(L\), 问 \(S\) 中有多少个 \(L-Gap\) 子串. \(1 \leq |S| \leq 5 \times 10^4, L \leq 10\) 解题思路 : 考虑要对特征串计数,不妨枚举 单个 \(u\) 的长度

「BZOJ 2956」模积和 令 \(l=\min(n,m)\).这个 \(i\neq j\) 非常不优雅,所以我们考虑分开计算,即: \[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1,i\neq j}^{m}(n \bmod i)(m\bmod j)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}(n \bmod i)(m\bmod j)-\sum_{i=1}^{\texttt{l}}(n \bmod i)(m\bmod i)\\ \

\(\mathcal{Description}\)   Link.   给定含 \(n\) 个点 \(m\) 条边的简单有向图 \(G=(V,E)\),求 \(H=(V,E'\subseteq E)\) 的数量,使得 \(H\) 是强连通图.答案模 \((10^9+7)\).   \(n\le15\). \(\mathcal{Solution}\)   仙气十足的状压容斥.   令 \(f(S)\) 表示仅考虑点集 \(S\) 的导出子图时,使得 \(S\) 强连通的选边方案数,那么 \(f(V

题目链接 luogu bzoj \(Solution\) 这个貌似没有什么好讲的吧,直接按照这个给的图建图就好了啊,没有什么脑子,但是几点要注意的: 建双向边啊. 要这么写,中间还要写一个\(while\)否则会\(T\)的: while(bfs()){ while((k=dfs(s,inf))) ans+=k; } \(Code\) #include<bits/stdc++.h> #define file(a) freopen(a".in","r",s

题目链接 luogu bzoj \(Describe\) 有一个\(n\)个节点的树,边有权值,定义两个节点之间的距离为两点之间的路径上的最小边权 给你\(Q\)个询问,问你与点\(v\)的距离大于等于\(k\)的点有多少个 \(Solution\) 这道题主要用并查集搞一下就好了啊. 离线的做. 首先将边按照权值排序,将询问的按照k排序 然后把权值大于等于\(k\)的放入并查集中,维护一个\(siz\)即节点的个数. \(End\) \(Code\) #include<bits/stdc++.

题意 \(T\)组数据,每次询问第\(k\)个无平方因子的数(\(1\)不算平方因子),\(T\leq 50,k\leq 10^9\) 题解 \(k\)的范围很大,枚举肯定不行,也没什么奇妙性质,于是可以想到二分. 二分的话我们需要实现一个函数\(f(n)\)表示\(n\)以内的数中无平方因子的数个数 这十分经典,相当于求\(f(n)=\sum_{i=1}^n\mu^2(i)\) 解法就是:我们考虑一个质数\(p\),\(p^2\)的倍数都不满足要求,也就是说答案得减去\(\lfloor \fr

题意 求基环树森林所有基环树的直径之和 题解 考虑的一个基环树的直径,只会有两种情况,第一种是某个环上结点子树的直径,第二种是从两个环上结点子树内的最深路径,加上环上这两个结点之间的较长路径. 那就找环,然后环上每个结点做树形\(dp\).然后把环断成长度为\(2n\)的链,记录环上的前缀和\(sum\).假设结点\(u\)子树内最深路径为\(dep[u]\),那么就是求\(max(sum[i] - sum[j] + dep[i] + dep[j]),j < i\).这个就转换成\(max(su

题目链接 戳我 \(Solution\) 题目为什么是\(a\ +\ b\ Problem\)啊?这和题面半毛钱关系都没有. 现在来讲一下这题的解法吧,我们首先看看没有奇怪的方格这一个条件吧. 其实没有这个条件还是很简单的,就只要将每个点连向原点表示选流量为\(B\)表示选黑色的,在将这个点连向汇点流量为\(W\)表示选白色的,跑一遍最小割就好了 现在来看看有奇怪的方格这一个条件吧,我们可以对于每个节点\(i\)新建一个节点\(i'\),我们将每个\(i\)连向\(i'\)流量为\(P\),在对

题目链接 戳我 \(Solution\) 这道题很像餐巾计划啊. 首先将每天拆成\(x\)和\(x'\),\(S->x\)流量为\(a_i\),费用为\(0\)表示一天下来有\(a_i\)个濒死的人, 再将\(x'->T\)流量为\(a_i\)表示一天需要有\(a_i\)个人 对于每个学校新建一个节点,将\(S\)和他相连流量为\(l_i\),在将这个节点和\(x'\)相连流量为\(inf\),费用为\(p_i\)表示每天可以在学校中选人 然后在将\(x\)连向\(x+1\),流量为\(inf

Title Link 戳我 Title Solution 这道题可以运用组合数的思想啊,数位dp也可以,随便你怎么做,这里就讲一讲组合数的做法吧,要小于n,所以我们可以枚举n二进制下1的位置,在i-1后面选j个1.用组合数做一下就好了啊 code #include<bits/stdc++.h> #define int long long using namespace std; const int mod=10000007; int c[1011][1011],f[101]; int read

题目链接 戳这 Title Solution 这一道题显然可以看出公式为: \[ans=C_{n}^{w_1}*C_{n-w}^{w_2}*...*C_{w_m}^{w_m}\] 然后就可以用扩展Lucas求解了. 至于扩展Lucas:戳这 code #include<bits/stdc++.h> #define rg register #define int long long #define file(x) freopen(x".in","r",st

题目链接 戳这 \(Solution\) 这道题看起来就像点分治对吧.没错就是点分治. 什么是点分治 如果你不会点分治,可以去看看这儿 现在看到这里,首先确保你已经会了点分治,如果不会你还往下看,听不懂概不负责虽然会但没看懂也不负责(逃) 点分治题目大部分都是模板对吧.只是calc(solve)的区别.首先看看暴力的calc.暴力枚举所有边,在判断是否为3的倍数. 但是这显然不行对吧,在仔细思考一下.发现%3的数的可能性只有三种情况 %3=0 %3=1 %3=2 所以想要为三的倍数的话有两种可能

题意 一个\(r\times c\)的棋盘,棋盘上有\(n\)个标记点,每个点有三种类型,类型\(1\)可以传送到本行任意标记点,类型\(2\)可以传送到本列任意标记点,类型\(3\)可以传送到周围八连通任意标记点.求最长路径. \(r,c\leq 10^6,n\leq 10^5\) 题解 这题做法很多,我就把每一行的所有类型\(1\)门缩到一起(直接找一个代表),列也同理,然后暴力连边,类型\(3\)连边用\(\text{map}\),这样每个点的入边中类型\(1\)或\(2\)最多有\(1\

题意 给定一个\(1\)为根的树,每个点有\(c,w\)两个属性,你需要从某个点\(u\)子树里选择\(k\)个点,满足选出来的点\(\sum_{i=1}^k w(i)\leq m\),最大化\(k\times c(u)\) 题解 可以启发式合并\(splay\)来做,\(\text{dfs}\)每个点,每次和儿子的\(splay\)合并,就得到了一个维护这个点子树的平衡树.再用这个点的\(w\)(题目中的领导力)乘以子树中最多选多少结点满足\(c\)(薪水)和\(\leq m\) 肯定贪心选,

题意 你需要维护若干连通快,有两个操作 合并\(x,y\)所在的连通块 询问\(x\)所在连通块中权值从小到大排第\(k\)的结点编号 题解 可以启发式合并\(splay\),感觉比较好些的 一个连通块就是一个\(splay\),每次合并挑小的\(splay\)遍历一遍把点按中序遍历存下来,然后一个一个插入大的\(splay\)就行了:查询就是\(splay\)的\(kth\)操作 这样时间复杂度\(O(n \log n)\),它的证明可以见2018论文集 :董炜隽<浅谈Splay与Treap的

题意 你有一个森林,你需要支持两个操作 查询两个结点路径上权值第\(k\)小 两个点之间连一条边 强制在线,结点数\(\leq 8\times 10^4\) 题解 如果可以离线,这就是一个主席树板子题,每个点开一个主席树表示树上的前缀和.询问的时候拿出来\(4\)棵主席树,\(x,y,lca(x,y)\)和\(fa(lca(x,y))\),然后每次用\(x,y\)的信息减去\(lca(x,y),fa(lca(x,y))\)的信息就能得到这条链的信息 这里要求在线,可以考虑启发式合并,比如连接\(