- 博客(144)
- 收藏
- 关注
RSS订阅原创 决策单调性小结
1D1D动态规划指状态数为O(n)O(n)O(n)，每个状态的决策数为O(n)O(n)O(n)，直接求解的复杂度为O(n2)O(n^2)O(n2)的动态规划方程dp[i]=min/max{dp[j]+S[i,j]}dp[i] = min/max \{dp[j] + S[i, j]\}dp[i]=min/max{dp[j]+S[i,j]}。斜率优化斜率优化是1D1D的一种常见优化方式，一般的套...
2018-10-28 23:35:50
730
原创 BZOJ 5335 智力竞赛
大致题意：给出一个DAG，问能否用n+1条可重复路径覆盖整个图。最小有重复路径覆盖问题，先传递闭包，转化成无重复路径覆盖问题。然后把原图每个点拆成两个点建立二分图，然后用原图点数−-−最大匹配数就是答案。如果可以覆盖就输出AKAKAK，否则二分一个最大可行权值midmidmid，大于midmidmid的点连一个i−>ii -> ii−>i的边，表示忽略这个点...
2018-09-30 10:06:10
282
原创 2014西安区域赛G The Problem to Slow Down You 回文树
问AAA和BBB两个串中，相同的回文串的对数。为A和B建立两棵回文树，然后记录每个点的次数（也就是回文串的个数），随后分别从两棵树对应的奇长度树和偶长度树向下遍历即可，遇到相同的节点就统计答案，否则停止搜索。#define others#ifdef poj#include <iostream>#include <cstring>#in
2018-09-20 11:21:17
230
原创 2018ACM-ICPC徐州网络赛 D Easy Math
求解∑mi=1μ(in)求解∑i=1mμ(in)求解\sum_{i=1}^{m}\mu(in) 记:S(m,n)=∑mi=1μ(in)S(m,n)=∑i=1mμ(in)S(m, n) = \sum_{i=1}^{m}\mu(in) =μ(n)∑mi=1μ(i)[gcd(i,n)==1]=μ(n)∑i=1mμ(i)[gcd(i,n)==1]=\mu(n)\sum_{i=1}^{m}\mu(i)[...
2018-09-14 14:54:41
256
原创 2018 ACM-ICPC 沈阳网络赛C Convex hull
题目链接：https://nanti.jisuanke.com/t/31444考虑杜教筛就跑偏了… 定义gay(i)=i2∗μ2(i)gay(i)=i2∗μ2(i)gay(i) = i^2 * \mu^2(i) ∑ni=1∑ij=1gay(i)=∑ni=1(n−i+1)gay(i)=∑ni=1(n−i+1)i2μ2(i)∑i=1n∑j=1igay(i)=∑i=1n(n−i+1)gay(i)...
2018-09-13 16:29:08
564
1
原创 低于线性时间积性函数前缀和
学习了一发tls的博客：https://blog.csdn.net/skywalkert/article/details/50500009，做一些小小的总结。常见转化： 1. ∑ni=1∑j|ij=∑ni=1i∗⌊ni⌋=∑ni=1⌊ni⌋∗(1+⌊ni⌋)2∑i=1n∑j|ij=∑i=1ni∗⌊ni⌋=∑i=1n⌊ni⌋∗(1+⌊ni⌋)2\sum_{i = 1}^{n} \sum_{j|...
2018-09-11 18:37:00
468
原创 2018沈阳网络赛:J kachang KD树
把每个点建立(dfs序，depth），所有操作和查询转化为矩形操作，用KD树就可以n(√n)n(n)n\sqrt(n)完成了。#include <bits/stdc++.h>using namespace std;typedef long long LL;const LL maxn = 110000;const LL INF = 1e18;const LL dimen...
2018-09-10 00:21:19
656
原创 字符串学习：字符串算法选讲-金策
周期和border0&amp;lt;q≤|s|,s[i]=s[i+p],∀i∈1...|s|−p0&amp;lt;q≤|s|,s[i]=s[i+p],∀i∈1...|s|−p0 &lt; q \le |s|, s[i] = s[i+p], \forall i \in {1...|s|- p}, ppp就是sss的周期。 0≤r≤|s|,pre(s,r)=suf(s,r),pre(s,r)0≤r≤|s|,pre(s...
2018-09-08 21:28:53
1626
原创 wannafly cap day3 计算几何选讲
Airport Constructionwf2017 A直线打断多边形点在多边形内部 O(n^4) 点在多边形内，判断点和线段交点，交在线段端点，线段上向下的点，cnt+1，否则cnt-1。Castle2018SDOIGetting LostCCPC qinghuangdao 抠关键点跑最短路 如何抠关键点？ 考虑几何对象点到圆，有切线 ...
2018-08-04 19:26:30
242
原创 wannafly camp day2 数论函数
昨天下午比赛结束前赶到机房，爆写300行树剖线段树之后没时间了，晚上带着一票人出去烧烤，现在牙龈还肿痛着，当然这都不是问题。 今天来到了阶梯教室，无空调，人还多，还有异味…忍一忍算了。 回到今天的重点，今天的知识点是数论。NWERC2015 Debuggingsol1sol1sol1. 单纯的logn次二分运行的时间下界是logn∗(r+p)logn∗(r+p)logn * (r ...
2018-08-03 11:24:23
662
1
原创 HDU 6305 RMQ Similar Sequence
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6305意识到RMQ相同的含义就是序列的相对大小关系保持一致，而相同的大小关系建立出的笛卡尔树相同（特殊的不是笛卡尔树，而是建树的方式）。 考虑B数组的排列中能够符合A数组构成的笛卡尔树的概率为1/∏sz[i]1/∏sz[i]1/\prod sz[i]，可以简单理解为，在对应笛卡尔树的节点上，当前位...
2018-07-29 01:32:09
231
原创 BZOJ 1455 罗马游戏
可并堆的裸题，pbds练手用。#define others#ifdef poj#include &lt;iostream&gt;#include &lt;cstring&gt;#include &lt;cmath&gt;#include &lt;cstdio&gt;#include &lt;algorithm&gt;#include
2018-07-27 13:37:55
166
原创 牛客多校第3场：C Shuffle Cards
https://www.nowcoder.com/acm/contest/141#question之所以补这题，是因为第一次使用rope，这是一个可持久化平衡树。 不过本题没有用到可持久化就是了，平衡树的split和merge。#define others#ifdef poj#include &amp;lt;iostream&amp;gt;#include &amp;lt;cstring&amp;gt;#inc...
2018-07-27 12:53:50
247
原创 React教程：以井字游戏简单游玩React
原链接：https://reactjs.org/tutorial/tutorial.html 个人学习使用，如有侵权请告知…React简介在我们开始之前 让我们做一个交互式井字游戏。class Square extends React.Component { render() { return ( &amp;amp;amp;amp;lt;button className=&amp;amp;amp;quot;squa...
2018-06-06 10:16:51
547
原创 2016 ChinaFinal F. Mr. Panda and Fantastic Beasts SAM
简略题意：问第一个串的子串中，不在其他n-1个串出现的长度最小且字典序最小的子串是什么。将n-1个子串用不会出现的字符拼接起来，那么问题转化成 问A串的子串中，不在B串出现的长度最小且字典序最小的子串是什么。将B串建立后缀自动机，用A串在自动机上跑。和湖南大学校赛的那题一样，动态维护A的子串匹配上B的子串的长度，当失配的时候更新答案即可。#define others#ifdef...
2018-05-29 18:14:38
418
原创 2018湖南大学校赛 B DSU
简略题意： 有n张牌 每张牌2面， 你每张牌只能选一个面， 把这n张牌排序后从 最大能从1开始连续到多少会断掉？想法很棒棒啊。 首先把牌面看做一条边，考虑一棵n大小的树的情况，那么可以使得其中n-1个点被选出来。如果这不是一个树，那么这个图里的任意节点都可以满足。 为了让答案更优，对于每个联通块，我们必然选择每个联通块序号最小的n-1个点。 用并查集来维护，每次启发式合并两个联通块。...
2018-05-28 19:11:21
260
原创 2018湖南大学校赛 F SAM
简略题意： B串的所有子串在A串中的出现次数之和是多少。首先考虑A求A串自身的子串在A中出现次数之和是多少。 考虑parentparentparent树，树上节点数为cntcntcnt，那么答案就是: ∑cnti=1(maxlen[i]−minlen[i]+1)∗right[i]∑i=1cnt(maxlen[i]−minlen[i]+1)∗right[i]\sum_{i = 1}^{cn...
2018-05-28 18:09:28
303
原创 codeforces 8E 数位DP
简略题意：字典序第k小的，满足以下条件的长度为n的01串是什么。 1.字典序小于其取反串 2.字典序小于其逆串 3.字典序小于其逆反串给定指定长度，问有多少串满足上述条件，我们可以用数位来求得。 令dp[l][r][inv][rev]dp[l][r][inv][rev]dp[l][r][inv][rev],invinvinv代表前lll个010101字符和后lll个010101字符取逆...
2018-05-24 19:26:22
328
原创 codeforces23E Tree 树形DP + 大数
令dp[i][j]dp[i][j]dp[i][j]代表以i为根的子树，其所在通块大小为jjj时的最大乘积。那么暴力枚举其子树所在的联通块大小，即得到转移： dp[u][j+k]=max(dp[u][j+k],dp[u][j]∗dp[v][k])dp[u][j+k]=max(dp[u][j+k],dp[u][j]∗dp[v][k])dp[u][j+k] = max(dp[u][j+k], dp...
2018-05-24 19:08:02
242
原创 HDU5909 FWT加速异或卷积
简略题意： 从一个节点数为nnn的树中选出一颗子树，这个子树的值为它所有的节点的值异或起来的结果。现在需要你输出异或值分别为[0,m)[0,m)[0, m)的方案树。先考虑简单的树形DPDPDP 以dp[u][i]dp[u][i]dp[u][i]代表以u为根的子树，所有节点的值异或起来为iii的方案树。 那么存在转移 dp[u][i]=∑v∈son(u)dp[v][j]∗dp[u][i...
2018-05-17 17:25:56
510
原创 sgu106 扩展欧几里德
简略题意： 给出aaa, bbb,ccc和x1x1x1, x2x2x2, y1y1y1, y2y2y2, 问满足ax+by+c=0ax+by+c=0ax + by + c = 0的xxx和yyy的对数有多少。首先把输入处理成ax+by=cax+by=cax + by = c的形式，且a,b,ca,b,ca,b,c都为000或正数。然后分类讨论a,b,ca,b,ca,b,c分别是000的情...
2018-05-04 18:57:08
168
原创 朝花夕拾之欧几里得
gcd(a,b)=gcd(b,a%b)gcd(a, b) = gcd(b, a\%b).证明： 设r=gcd(a,b)r = gcd(a, b) 那么存在 r|a,r|br|a, r|b. 又因为a%b=a−a/b∗b=a−k∗ba \% b = a - a/b * b = a - k * b. a−k∗ba - k * b是aa和bb的一个线性组合，因此r|(a%b)r|(a\%b)。
2018-04-26 18:41:14
131
原创 sgu105 找规律
打个表，显然是n - (n + 2) / 3.#define others#ifdef poj#include <iostream>#include <cstring>#include <cmath>#include <cstdio>#include <algorithm>#include <vector>...
2018-04-26 15:12:03
173
原创 sgu101 欧拉路
简略题意：给出n个多米诺骨牌，每个牌正面反面有不同的数字，一个牌iii能连在另一个牌jjj的后方当且仅当，iii的反面数字等于jjj的正面数字。可以把多米诺骨牌的看做边，两侧的数字看做节点，那么就可以转化成一个无向图欧拉路问题。 需要注意一下：1. 判定无解2. 判定图是否连通#define others#ifdef poj#include <iostream>#...
2018-04-26 15:02:32
180
原创 sgu104 DP
简略题意： 有n个花瓶和m朵花，第i个花瓶插着第j朵花的价值是v[i][j]v[i][j]v[i][j]，问n个花瓶插满的最大价值是多少。 需要注意的是里面有一组偏序关系： 若第i个花瓶插着第j朵花，那么第i−1个花瓶插着的花的序号一定小于j。若第i个花瓶插着第j朵花，那么第i−1个花瓶插着的花的序号一定小于j。若第i个花瓶插着第j朵花，那么第i-1个花瓶插着的花的序号一定小于j。那么两...
2018-04-26 14:57:18
167
原创 sgu102 欧拉函数
phi[x]=x∗∏ni=1(p[i]−1)/(p[i])phi[x] = x * \prod_{i = 1}^{n} (p[i]-1)/(p[i])#define others#ifdef poj#include <iostream>#include <cstring>#include <cmath>#include <cstdio>#include <algorithm>#incl
2018-04-25 14:31:12
246
原创 sgu103 最短路
简略题意： 给出S和T，问从S到T的最短路。 但是两个节点能通行当且仅当两个节点的颜色相同。 每个节点有一个初始颜色，当前颜色剩余的时间，以及每种颜色的持续时长。需要注意的点:1. 双向边2. 无解（两种颜色无限交替）稍微修改一下最短路，每次从一个路口走到另一个路口时，需要附加上额外的时间代价，这个代价可以通过模拟得到。然后就是一个普通的最短路。#define ot...
2018-04-25 14:23:12
454
原创 关于一个菜鸡ACMer找实习的路程...
简述一下从三月到现在，作为一个菜鸡ACMer找实习的过程。首先内推了腾讯和阿里，pony.ai。 然后全挂了= =… 腾讯和阿里一贯作风，问了一堆计算机基础，问得我怀疑人生… 阿里更是因为不明白什么是ACM，然后挂了我的简历面… pony比较奇怪…据我所知的几个人投递之后的面试官或多或少都是接触过ACM的，但是很明显我遇到的两个都没有… 一面简单过了之后，二面问了一个前序后序求中序方...
2018-04-24 17:38:30
1123
2
原创 UVALive - 8144 Sacred Scarecrows DP + FMT 未解决
简略题意：R∗CR*C的庄稼地，有些地方已经种了庄稼了。现在需要放置一些稻草人，使得满足以下两个条件： 11. 所有行都包含稻草人。 22. 相邻的两列至少包含两个稻草人。这题目前还没有ACAC，但是值得记录。注意到行很少，因此可以状压进行DPDP。 令dp[i][0/1][j]dp[i][0/1][j]代表，前i列的稻草人存放了那些行，当前列是否有稻草人。用∗∗**代表集合并卷积，那么转移有
2018-04-17 17:10:52
273
1
原创 第十二届东北师范大学程序设计竞赛正式赛题解
A 可以想到，先手必胜的条件是，存在一个奇数。 所以后手想要必胜就需要把所有奇数+1，使其变成偶数。 统计一下奇数的个数即可。#include <bits/stdc++.h>using namespace std;int main() { int t; scanf("%d", &t); while(t--) { int n; scanf
2018-04-15 21:56:48
559
1
原创 第十二届东北师范大学程序设计竞赛热身赛题解
A. Math loser 首先如果一个L(x)L(x)L(x)和R(x)R(x)R(x)相同，那么必然不满足条件，所以我们可以排除x−−√x\sqrt x为素数的情况。 那么我们只需要筛出所有的素数，那么一个数的L(x)L(x)L(x)和R(x)R(x)R(x)必然是相邻的素数，那么我们就枚举LLL和RRR，来按区间来统计答案惹。 现在考虑一个简单容斥，假如我们要计算的是只能LLL或RRR...
2018-04-14 15:36:38
406
原创 关于出题
最近出了不少垃圾题，开个地方存下自己的出题程序。数据生成#define others#ifdef poj#include <iostream>#include <cstring>#include <cmath>#include <cstdio>#include <algorithm>#include <ve...
2018-04-09 14:30:19
260
原创 题解 2017-2018 ACM-ICPC East Central North America Regional Contest (ECNA 2017)
A - Abstract Art问n个多边形的面积并是多少。 直接粘板子过了…#define others#ifdef poj#include <iostream>#include <cstring>#include <cmath>#include <cstdio>#include <algorithm>#include <vector>#include <string>#inc
2018-04-08 17:37:11
2629
原创 ProjectEuler 108 Diophantine reciprocals I
1x+1y=1n\frac{1}{x} + \frac{1}{y} = \frac{1}{n} =>1y=x−nnx\frac{1}{y} = \frac{x-n}{nx} =>y=nxx−ny = \frac{nx}{x-n}令b=x−n,x=b+nb = x - n, x = b + n y=nxx−ny = \frac{nx}{x-n} =>y=n∗(b+n)b=n+n2by = \f
2018-04-05 09:23:47
188
原创 ACM竞赛高校联盟训练 第10场 题解
A. Math loser 首先如果一个L(x)L(x)L(x)和R(x)R(x)R(x)相同，那么必然不满足条件，所以我们可以排除x−−√x\sqrt x为素数的情况。 那么我们只需要筛出所有的素数，那么一个数的L(x)L(x)L(x)和R(x)R(x)R(x)必然是相邻的素数，那么我们就枚举LLL和RRR，来按区间来统计答案惹。 现在考虑一个简单容斥，假如我们要计算的是只能LLL或RRR...
2018-03-31 22:07:49
867
原创 hihocoder[Offer收割]编程练习赛50 题解
题目1 : 循环数组 考虑枚举从位置i断开，移到前面。那么需要确保从当前位置i开始的前缀和都大于0。记此时i到n的总和为x，那么若x大于从1开始到i-1的前缀和中的最小值，则i必然可行。所以需要维护的东西有，从i位置开始到n的前缀和，为了支持i到i+1的数值变化，需要用一个支持区间加法的线段树。维护从1开始的前缀和的最小值可以用前缀和数组来完成，就酱。#define others#...
2018-03-11 14:31:51
653
原创 codeforces 332C Students' Revenge 贪心
简略题意：有nn项工作，每项工作有两个属性aa和bb，代表如果主席接受了这份工作，就要长aa根白头发，不接受董事会就要有bb的不满意度。我们需要从nn项工作里挑出pp项工作使得主席的白头发尽可能多，多种方案选董事会最不满意的那个方案。而主席从pp份工作里挑kk个工作，首先使得董事会满意，多种方案选取自己白头发最少的方案。先明确主动权在我们手里，对于主席而言理想化的状况就是选了bb最小的p−kp-k份
2018-03-08 15:55:59
287
原创 hihocoder[Offer收割]编程练习赛49 题解
1700 相似颜色 模拟 + 暴力，随便搞一搞就好了#define others#ifdef others#include <iostream>#include <cstring>#include <cmath>#include <cstdio>#include <algorithm>#include <vector>#include <string>#include <map>
2018-03-05 11:42:33
283
原创 LA 4636 Cubist Artwork 构造 存疑
中心思想是，与主视图相同高度的方块侧视图一定也能用上。 然而我只能感性理解，却不能理性证明。 这样下去不行啊…namespace Solver { int n, m; void solve() { while(~scanf("%d%d", &n, &m) && (m + n)) { LL ans =...
2018-02-23 15:25:30
173
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人