摘要：
戒骄戒躁，自律当先。稳扎稳打，颗粒归仓。目标高远，落实当下。无惧将来，无畏过往。愿你们承担一份荣耀，愿你们书写一段辉煌。——致备战noip2018的你们 ——退役学姐致gryz备战中的勇士 ——lpy，lrh，ldx，zyh 老伙计们加油啊！ 阅读全文
posted @ 2018-10-19 23:47
TRTTG
阅读(1070)
评论(28)
推荐(2)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=5249 把树建出来 如果所有的d互不相同，后续遍历即可 现在有的d相同 将d从小到大排序，考虑如何将这n个数填进树里 相当与为x的子树预订d序列中的一段 而且当且这个d填的位置越靠后越好 CTSC试机 阅读全文
posted @ 2018-05-06 17:05
TRTTG
阅读(689)
评论(0)
推荐(1)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=1951 先欧拉降幂 然后模数质因数分解 分别计算组合数的结果，中国剩余定理合并 #include<cmath> #include<cstdio> #include<iostream> using na 阅读全文
posted @ 2018-05-05 10:14
TRTTG
阅读(412)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=2561 考虑Kruscal算法求最小生成树的流程 如果 u和v之间的长为L的边能出现在最小生成树里，说明<L的边不能时u和v联通 即求图中只存在<L的边时，u和v的最小割 如果 u和v之间的长为L的边 阅读全文
posted @ 2018-05-04 17:16
TRTTG
阅读(294)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=5251 第一问： 左边一列点代表学生，右边一列点代表导师 导师向汇点连流量为 人数限制的 边 然后从第一个学生的第一志愿往里面加边 如果当前学生的当前志愿可以满足，即目前网络流可以满流，保留这一志愿的 阅读全文
posted @ 2018-05-04 14:58
TRTTG
阅读(366)
评论(0)
推荐(0)
摘要：
http://hihocoder.com/problemset/problem/1465 求S的循环同构串在T中的出现次数 将串S变成SS 枚举SS的每个位置i，求出以i结尾的SS的子串 与 T的最长公共子串 若长度>=|S|，说明以i结尾的S的循环同构串在T中出现过 假设最后匹配i到达了后缀自动机 阅读全文
posted @ 2018-05-04 08:44
TRTTG
阅读(459)
评论(0)
推荐(0)
摘要：
http://hihocoder.com/problemset/problem/1457 val[i] 表示状态i所表示的所有字符串的十进制之和 ans= ∑ val[i]在后缀自动机上，从起始状态走任意一条路径到达任意一个状态，这条路径上的字符就是到达的状态的字符串之一 所以利用拓扑排序，记录从起 阅读全文
posted @ 2018-05-03 20:56
TRTTG
阅读(463)
评论(0)
推荐(0)
摘要：
http://hihocoder.com/problemset/problem/1445 求不同的子串个数 阅读全文
posted @ 2018-05-03 19:30
TRTTG
阅读(384)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=4939 ans= r1-l1+1 + r2-l2+1 +r3-l3+1 - ∑ min(cnt1[i],cnt2[i],cnt3[i])*3 计算cnt可以用莫队 关键在与如何对3个区间取小 用bit 阅读全文
posted @ 2018-05-03 19:07
TRTTG
阅读(529)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=2865 同上一篇博客 就是卡卡空间，数组改成map #include<map> #include<cstdio> #include<cstring> #include<algorithm> #defi 阅读全文
posted @ 2018-05-03 17:12
TRTTG
阅读(539)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=1396 后缀自动机的parent树上，如果不是叶子节点，那么至少有两个子节点 而一个状态所代表子串的出现次数就是子树中叶子节点的个数 所以只有叶子节点 即 |Right|=1的状态 代表的子串 出现了 阅读全文
posted @ 2018-05-03 16:52
TRTTG
阅读(320)
评论(0)
推荐(0)
摘要：
题意： 给出一个字符串，至多将其划分为n部分，每一部分取出字典序最大的子串ci，最小化 最大的ci 先看一个简化版的问题： 给一个串s，再给一个s的子串t，问能否通过将串划分为k个部分，使t成为划分后的s的字典序最大子串 对于这个问题，从串s的最后面开始，一个字符一个字符的向前推 如果当前[l,r] 阅读全文
posted @ 2018-05-02 18:12
TRTTG
阅读(739)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=4650 如果能够预处理出 suf[i] 以i结尾的形式为AA的子串个数 pre[i] 以i开头的形式为AA的子串个数 ans= ∑ suf[i]*pre[i+1] 这两个数组的求法，类似bzoj 21 阅读全文
posted @ 2018-05-02 15:03
TRTTG
阅读(283)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=3173 插入的数是以递增的顺序插入的 这说明如果倒过来考虑，那么从最后一个插入的开始删除，不会对以某个数结尾的最长上升子序列产生影响 所以 先原序列求出来，输出即可 还原原序列的方法： 可以用平衡树， 阅读全文
posted @ 2018-05-02 06:53
TRTTG
阅读(412)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=3172 构建AC自动机 在fail树上，点i的子树大小 表示trie树上根节点到i构成的单词 是 多少个(子)串的子串 #include<queue> #include<cstdio> #includ 阅读全文
posted @ 2018-05-01 22:10
TRTTG
阅读(279)
评论(0)
推荐(1)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=3238 跟 bzoj3879 差不多 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using n 阅读全文
posted @ 2018-05-01 21:16
TRTTG
阅读(226)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=3879 把所有的后缀取出，按rank排序 求出相邻两个后缀的lcp 每个后缀对答案的贡献就是 与在它之前的后缀的lcp之和 维护一个单调递增的栈，记录栈中元素的lcp之和 即可 #include<cs 阅读全文
posted @ 2018-05-01 21:00
TRTTG
阅读(338)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=2119 题意：将给定数组差分后，求ABA形式的字串个数，要求|B|=m，|A|>0 1、后缀数组求出 差分序列 和 翻转差分序列后的序列 的sa，rk，height 2、枚举len=|A|，对差分序列 阅读全文
posted @ 2018-05-01 18:04
TRTTG
阅读(324)
评论(0)
推荐(0)
摘要：
http://acm.hdu.edu.cn/showproblem.php?pid=2815 //解 K^D ≡ N mod P #include<map> #include<cmath> #include<cstdio> #include<iostream> using namespace std 阅读全文
posted @ 2018-04-30 09:40
TRTTG
阅读(294)
评论(0)
推荐(0)
摘要：
求LCA，N=1e6，原空间限制8MB 求LCA需要深度，需要跳跃一定距离的祖先，需要父节点 把一个整数压成3个char，f[]存父节点 g[],深度为奇数的点存往上跳576步能到的点，深度为偶数的点存深度 如果深度为奇数的点要求它的深度，求他父节点的深度+1 如果深度为偶数的点要求它往上跳576步 阅读全文
posted @ 2018-04-29 17:13
TRTTG
阅读(554)
评论(0)
推荐(0)
摘要：
不理解，背板子 #include<cstdio> using namespace std; int Pow(int a,int b,int p) { int res=1; for(;b;a=1LL*a*a%p,b>>=1) if(b&1) res=1LL*a*res%p; return res; } 阅读全文
posted @ 2018-04-28 21:52
TRTTG
阅读(653)
评论(0)
推荐(1)
摘要：
若m=0， 就是求n^2n ≡ x mod p （x--） 因为一定优解，所以x一定是p的二次剩余 令g为p的1个原根，且g^k ≡ x mod p 则k是偶数，证明k是偶数： 假设 g1^k1 ≡ x mod p g2^k2 ≡ x mod p，k2是偶数 g1^k3 ≡ g2 mod p 那么 阅读全文
posted @ 2018-04-28 20:13
TRTTG
阅读(578)
评论(0)
推荐(1)
摘要：
http://acm.timus.ru/problem.aspx?space=1&num=1132 题意： 求 x^2 ≡ n mod p p是质数 的 解 本题中n>=1 特判p=2，接下来求当p是奇素数时的解 引理1： 引理2：方程有解当且仅当 定理： 设a满足 不是模p的二次剩余， 即无解， 阅读全文
posted @ 2018-04-28 15:18
TRTTG
阅读(556)
评论(0)
推荐(1)
摘要：
https://uva.onlinejudge.org/external/119/p11916.pdf 令m表示不能染色的格子的最大行号 设>m行时可以染k种颜色的格子数有ck个，恰好有m行时可以染k种颜色的格子数有ckm个 分m行、m+1行、>m+1行讨论 如果是m行：k^ckm * (k-1)^ 阅读全文
posted @ 2018-04-28 11:37
TRTTG
阅读(254)
评论(0)
推荐(0)
摘要：
维护前i天的最优解，那么在后面可能会对前面几天的买卖情况进行调整 如果前面买入，买入的这个在后面一定不会卖出 如果前面卖出，卖出的这个可能会在后面变成买入，因为买这个，卖后面的会获得更多的收益 用一个小根堆，存储前面所有的卖出的股票的价格 如果后面想卖出，扔到堆里 如果后面想买入，与堆顶元素比较，如 阅读全文
posted @ 2018-04-27 21:53
TRTTG
阅读(469)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=5017 暴力： 对于每一个炸弹，枚举所有的炸弹，看它爆炸能不能引爆那个炸弹 如果能，由这个炸弹向引爆的炸弹连单向边 tarjan所点后拓扑排序 在拓扑图上倒着统计答案 可以得到一个炸弹能引爆的编号最小 阅读全文
posted @ 2018-04-27 21:45
TRTTG
阅读(454)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=5285 |0 和 &1 没有影响 若填‘|’，记为0，若填‘&’，记为1 先只考虑最后一位 若要求最后=1 那么最后一个|1 要在最后一个 &0 后面 将n个数的最后一位拿出来构成一个01序列 填在所 阅读全文
posted @ 2018-04-27 11:42
TRTTG
阅读(360)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=4332 因为如果一位小朋友得不到糖果，那么在她身后的小朋友们也都得不到糖果。 所以设g[i][j] 表示前i位小朋友，分到j个糖果，且前i位小朋友都分到糖果的方案数 令F(x) 表示分到x个糖果的欢乐 阅读全文
posted @ 2018-04-27 08:33
TRTTG
阅读(349)
评论(0)
推荐(0)
摘要：
求出序列的生成函数后，倍增FWT #include<cstdio> using namespace std; #define N 2048 const int mod=1e9+7; int inv; int f[N+1]; int Pow(int a,int b) { int res=1; for( 阅读全文
posted @ 2018-04-26 18:46
TRTTG
阅读(648)
评论(0)
推荐(0)
摘要：
https://www.lydsy.com/JudgeOnline/problem.php?id=4589 n*m*m 做法 dp[i][j] 前i堆石子，异或和为j的方案数 第一重循环可以矩阵快速幂优化 后面求出序列的生成函数可以FWT优化 做log次FWT也很慢（logn*m*logm） 两个合 阅读全文
posted @ 2018-04-26 17:24
TRTTG
阅读(265)
评论(0)
推荐(1)
浙公网安备 33010602011771号