- 博客(114)
- 收藏
- 关注
RSS订阅原创 【DP】Gym100524E Ebola Virus
Souce:2014-2015 Summer Petrozavodsk Camp, Andrew Stankevich Contest 46 (ASC 46)Problem:n个村庄，如果第i个村庄没有被治疗，每天会死掉a[i]个人。现在起始在第一个村庄，每次选择花费一天的时间 往前走/往后走/治疗当前村庄，使得总共死去的人数最少。但行动有个限制，如果你的前进方向上有一个曾经被路过但没有被治...
2018-12-07 18:43:30
299
原创 【树形DP】Gym101667A Broadcast Stations
Souce:2017-2018 ACM-ICPC, Asia Daejeon Regional ContestProblem:一棵5e3的树，可以选择一些点放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖的最小价值。Idea：g[u][j]g[u][j]g[u][j]表示u点这颗子树里距离u点大于j的点都被覆盖的最小价值。显然g[u][j]=∑g[...
2018-12-04 21:25:15
548
1
原创 【斯坦纳树】18牛客多校1G Steiner Tree
Source:牛客网暑期ACM多校训练营（第一场）Problem:求斯坦纳树的个数Idea:斯坦纳树的dp分成两个部分，其中第一部分dp[S][u]→dp[S][v]dp[S][u] \to dp[S][v]dp[S][u]→dp[S][v]通过最短路更新，不会算重复，定义这一部分得到的斯坦纳树为fff，最后一步为根的延伸。第二部分dp[S0][u]+dp[S0⊕S][v]→dp[S][v]d...
2018-12-04 18:01:44
524
原创 【LCT】HDU5398 GCD Tree
Souce:Souce:Souce: 2015 Multi-University Training Contest 9Problem:Problem:Problem:1e5个查询，每次给一个n，表示一张n个节点的完全图，点的标号从1到n，任意两点之间的边权为标号的gcd，求最大生成树。Idea:Idea:Idea:如果只有单次查询，直接按gcd大小从后往前做就好了。那么现在只能从前往后动...
2018-12-01 17:55:43
172
原创 【并查集】Gym101840E Evaluations
Souce:Souce:Souce: Egyptian Collegiate Programming Contest 2017 (ACM ECPC 2017)Problem:Problem:Problem:给一颗1e5的树。树上路径定义为两点之间所有连边的边权的乘积。1<=边权<=1e5。问有多少条路径刚好是两个不同质数的乘积。Idea:Idea:Idea:由于1很特殊，对所...
2018-11-28 01:04:35
280
原创 【sam+二分】Gym101840B Breaking the Curse
Souce:Souce:Souce: Egyptian Collegiate Programming Contest 2017 (ACM ECPC 2017)Problem:Problem:Problem:给定两个字符串s1和s2，q次查询，每次查询s1中的一段区间[L,R]中有多少个子串在s2中出现过。Idea:Idea:Idea:对s2建sam，用s1跑最长公共子串，得到每个位置i往左...
2018-11-28 00:50:29
268
原创 【广义sam】Gym101194F Mr. Panda and Fantastic Beasts
Sourcce:Sourcce:Sourcce:2016-2017 ACM-ICPC CHINA-FinalProblem:Problem:Problem:给n个串，找一个最短且字典序最小的子串只在第一个串中出现过。Idea:Idea:Idea:如果不需要字典序最小，可以二分答案+hash或者对后n-1个串建广义sam，跑失配，但是这样比较最小字典序就很麻烦（虽然暴力比能过）。考虑对n个串...
2018-11-23 02:22:27
297
原创 【莫比乌斯反演】CodeForces 1043F Make It One
Souce:Souce:Souce: Codeforces Round #519 by Botan InvestmentsProblem:Problem:Problem:给n个数(n<=3e5)，每个数<=3e5，选择最少的数，使得他们的gcd为1。输出这个最小子集的大小。Idea:Idea:Idea:可以二分，或者直接枚举，因为2 * 3 * 5 * 7 * 11 * 13 * ...
2018-10-29 15:50:11
685
原创 【DP】Gym101933A Altruistic Amphibians
Source:Source:Source:2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)Problem:Problem:Problem:坑里有一堆青蛙，青蛙有身高、跳跃高度、体重。青蛙可以叠罗汉，但是不可以撑起超过自己体重的重量。问有多少青蛙可以跳出去。体重总和<=1e8Idea:Idea:Idea...
2018-10-27 03:08:29
577
1
原创 【LCA】Gym101669I Divide and Conquer
Source:Source:Source:2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017)Problem:Problem:Problem:n=1e5,m=2n−1n=1e5, m=2n-1n=1e5,m=2n−1的图，其中n−1n-1n−1条边构成A树，另n−1n-1n−1条边...
2018-10-07 16:19:47
220
原创 【原根+FFT】牛客国庆Day1 I Steins;Gate
Souce:Souce:Souce: 牛客国庆集训派对Day1Problem:Problem:Problem:N=1e5，a1,a2,...,aNN = 1e5，a1,a2,...,aNN=1e5，a1,a2,...,aN，对于每一个akakak，求有多少个有序二元组(i,j)(i,j)(i,j)满足a[i]∗a[j]=a[k](modP)a[i]*a[j] = a[k] (mod P)a[i...
2018-10-06 15:56:26
360
原创 【差分+DP】Gym101620K Kitchen Knobs
Souce:Souce:Souce:2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)Problem:Problem:Problem:n=500n=500n=500个长度为7的整数。需要把每个整数都变成最大循环表示，每次操作可以使连续的一段整数循环移动k位（往左/往右），求最少操作。Idea:Idea:Idea:除去每...
2018-10-04 23:03:13
358
原创 【线段树】Gym101620I Intrinsic Interval
Source:Source:Source:2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)Problem:Problem:Problem:n=1e5n=1e5n=1e5的全排列。定义一个区间是好区间当区间内的值域是连续的，即mx−mn=R−Lmx-mn=R-Lmx−mn=R−L。mmm个查询[li,ri][l_i, r_i...
2018-10-04 21:05:33
423
原创 【带权中位数】CodeForces 1053C Putting Boxes Together
Source:Source:Source:Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1)Probelm:Probelm:Probelm:n=2e5个物品从左到右排列，第i个物品的位置pos[i]，重量w[i]。每次询问如果将pos[l]…pos[r]这段物品移到某个连续区间[x, x+(r-l...
2018-10-02 15:27:07
193
原创 【四维偏序】18牛客多校9G Longest Common Subsequence
source:source:source:牛客网暑期ACM多校训练营（第九场）problem:problem:problem:n=1e4n=1e4n=1e4，求四个序列的最长公共子序列。前三个序列每个数不会出现超过两次。Idea:Idea:Idea:每个数在不同序列中的下标构成的元素（pa,pb,pc,pd）（pa,pb,pc,pd）（pa,pb,pc,pd）的四维偏序问题，总共只有8n8n8...
2018-09-18 20:06:46
189
原创 【杜教筛/min25筛】计蒜客 Easy Math
Source:Source:Source:ACM-ICPC 2018 徐州赛区网络预赛 Idea:Idea:Idea: f(n,m)=∑i=1mμ(i∗n)=μ(n)∗∑i=1mμ(i)[gcd(i,n)=1]f(n,m)=∑i=1mμ(i∗n)=μ(n)∗∑i=1mμ(i)[gcd(i,n)=1]f(n,m)=\sum_{i=1}^{m}\mu(i*n)=\mu(n)*\sum_{i=1}^...
2018-09-11 02:20:32
271
原创 【线性基】计蒜客 The Great Nim Game
Souce:Souce:Souce:ACM-ICPC 2018 南京赛区网络预赛 Problem:Problem:Problem: n=1e10000000堆石头；f(i)=(af(i−1)4+bf(i−1)3+cf(i−1)2+df(i−1)1+e−1)%k+1,(k≤212)，表示每堆石头的大小。求多少个石头子集可以使得nim游戏的先手必胜。n=1e10000000堆石头；f(i)=(af(...
2018-09-01 22:34:48
423
3
原创 【基环树】HDU5329 Question for the Leader
Souce:Souce:Souce:2015 Multi-University Training Contest 4 Problem:Problem:Problem:一棵n=1e5n=1e5n=1e5的基环树，对于k=1...nk=1...nk=1...n，问是否能将基环树切割成k份大小相同的连通块。 Idea:Idea:Idea:如果只是一棵树切成k份，当且仅当kkk个点sz[u]≡0mod...
2018-08-07 21:55:21
187
原创 【分治+线段树】HDU6328 Rectangle Radar Scanner
Souce:Souce:Souce:2018 Multi-University Training Contest 3 Problem:Problem:Problem:二维平面上给出n=1e5个有权值w=1e9的点，且x坐标刚好从1到n各不相同，1&lt;=y&lt;=n。现在m=1e6的询问，每个询问给出一个矩形，问矩形内所有点的权值积、最大值、最小值。 Idea:Idea:Idea:查询离线...
2018-08-03 17:10:40
424
原创 【cdq分治+DP】HDU5324 Boring Class
Source:Source:Source:2015 Multi-University Training Contest 3 Problem:Problem:Problem:给两个长度为n=5e4的序列，A和B，要求在A序列中找一个非递增的子序列，同时这个子序列的下标在B串中非递增。要求这个子序列最长，输出字典序最小的方案。 Idea:Idea:Idea:经典的三维偏序，CDQ分治。由于要求字典...
2018-07-31 22:25:57
195
原创 【FFT】CodeForces528D Fuzzy Search
Source:Source:Source:Codeforces Round #296 (Div. 1) Problem:Problem:Problem:有两个基因串S和T，他们只包含AGCT四种字符。现在你要找出T在S中出现了几次。 有一个门限值k≥0。T在S的第i(1≤i≤|S|-|T|+1)个位置中出现的条件如下：把T的开头和S的第i个字符对齐，然后T中的每一个字符能够在S中找到一样的，且位...
2018-07-29 14:14:44
198
原创 HDU6314 Matrix
Souce:Souce:Souce:2018 Multi-University Training Contest 2 Problem:Problem:Problem:n*m的方格，黑白染色，至少x行，y列全是黑色的方案数。 Idea:Idea:Idea: 令f(n,m)为n∗m的方格，没有任意一行，任意一列全是黑色的方案数令f(n,m)为n∗m的方格，没有任意一行，任意一列全是黑色的方案数令...
2018-07-26 21:00:54
665
原创 【基环树】18牛客多校2B discount
Source:Source:Source:牛客网暑期ACM多校训练营（第二场） Problem:Problem:Problem:n种物品，两种买法，一种选择折扣价，一种选择原价购买，使得自己的父亲可以免费。求最小值买下全部物品。 Idea:Idea:Idea:基环内向树DP。先找到树上的环，对于环上的每个点悬挂的树都跑一次树DP。然后断环为链，跑一次链DP。链上考虑两种情况，断开的边为u-&amp;g...
2018-07-23 21:12:57
206
原创 【广义sam】bzoj3277 串
Source:Source:Source:串 Problem:Problem:Problem:n个字符串，对于每个串，有多少个子串至少存在于k个字符串中 Idea:Idea:Idea:right集合用set存出现的串标号。由于广义sam有废点（我这种写法），废点对parent树有影响，所以不能基排，直接建树跑dfs更新right集合，考虑启发式合并。之后每个串都扔进去跑一遍就行了。不需要考虑在...
2018-07-22 22:42:02
172
原创 【sam+树DP】POJ 3415 Common Substrings
Source:Source:Source:Common Substrings Problem:Problem:Problem:求AB两个字符串的公共子串长度&amp;gt;=k的数量 Idea:Idea:Idea: 基础的后缀自动机操作。 对A建sam，B串通过失配跑最长公共子串，在lcs&amp;gt;=k时即使更新答案，方便处理，并对父亲打上lazy标志，dp[u]表示该状态在B串中出现了几次。sam...
2018-07-22 14:56:05
179
原创 【树上斜率优化】18牛客多校1H Longest Path
Source:Source:Source:牛客网暑期ACM多校训练营（第一场） Problem:Problem:Problem:一棵树，两点的路径和d(u,v)d(u,v)d(u,v)为相邻边权差的平方和的总和。对于每个点，求maxvd(u,v)maxvd(u,v)\max_vd(u,v) Idea:Idea:Idea: 先考虑两遍树形DP。 down(i)down(i)down(i)表示...
2018-07-21 21:55:05
352
原创 Wannafly挑战赛14F 细胞
Source:Source:Source:Wannafly挑战赛14 Problem:Problem:Problem: 已知t和m,ansi=∑k=0+∞2k∗C(t,k)∗[kmod2m==i]已知t和m,ansi=∑k=0+∞2k∗C(t,k)∗[kmod2m==i]已知t和m, \quad ans_i = \sum_{k=0}^{+\infty} 2^k*C(t, k)*[k \bmod...
2018-07-18 13:34:33
131
原创 【树上莫队】HDU 5799 This world need more Zhu
Source:Source:Source:2016 Multi-University Training Contest 6 Problem:Problem:Problem:一棵树，每个结点都有颜色。两种查询，第一种，u的子树上有颜色x出现了A次，t1+=x，有颜色y出现了B次，t2+=y，求gcd(t1, t2)，第二种，询问u到v链上的情况。 Idea:Idea:Idea:第一种情况，dfs...
2018-07-15 16:42:30
167
原创 【DAG博弈+主席树】Wannafly挑战赛15 F 下棋
Source:Source:Source:Wannafly挑战赛15 Idea:Idea:Idea: 有向无环图直接求每个点的sg，放棋子相当于是一个新点。每个棋子对应一个游戏，最后求nim游戏和。那么问题在于求mex[L,R]mex[L,R]mex[L,R]，用莫队+分块直接就能做。 然后学习一波主席树的做法。对于mex[L,R]mex[L,R]mex[L,R],相当于在前...
2018-05-13 17:53:15
167
原创 【splay】BZOJ1500 维修数列
Source:Source:Source:[NOI2005]维修数列 Problem:Problem:Problem:模板题。Splay的一些基础操作：插入/删除/求和/求最大子段和/翻转 Idea:Idea:Idea: 1.处理T[0],maintain时不能影响父亲。 2.首尾放两个哨兵，防止越界。 3.pushdown放到get_kth中，注意maintain的时机。 4.不会m...
2018-04-10 20:43:28
127
原创 【自适应辛普森】Gym100198I Two Cylinders
Source:Source:Source: ASC3 Problem:Problem:Problem: 求两圆柱垂直相交的体积。 Idea:Idea:Idea: 积分积不出来，扔给自适应辛普森公式。Code:Code:Code:#include&lt;bits/stdc++.h&gt;using namespace std;#define fi first#define se ...
2018-03-13 13:45:16
180
原创 【循环节+线段树】ZOJ4009 And Another Data Structure Problem
Source:Source:Source:151 - ZOJ Monthly, March 2018 Problem:Problem:Problem: 1 l r: Change (al,al+1,…,ar)(al,al+1,…,ar)(a_l, a_{l+1}, \dots, a_r) to (a3l,a3l+1,…,a3r)(al3,al+13,…,ar3)(a_l^3, ...
2018-03-10 22:47:36
490
原创 【带修莫队】CodeForces 940F Machine Learning
Source:Source:Source: Codeforces Round #466 (Div. 2) Problem:Problem:Problem: nnn个整数，mmm种操作，一种是查询[l,r][l,r][l, r]的mex{c1,...,c109c1,...,c109c_1, ..., c_{10^9}}，cxcxc_x指xxx出现的次数，另一种是修改一个整数的值。 Idea:Id...
2018-02-27 17:29:06
515
原创 CodeForces 936C Lock Puzzle
Source:Source:Source: Codeforces Round #467 (Div. 1) Problem:Problem:Problem: Shift(n)Shift(n)Shift(n)操作使得字符串 p = αβp = αβp = αβ 变成 βRαβRαβ^Rα，其中Length(β)=nLength(β)=nLength(β) = n，最多进行3∗n3∗n3*n步操作，...
2018-02-26 15:23:13
641
原创 CodeForces 909F AND-permutations
Source:Source:Source:Codeforces Round #455 (Div. 2) Problem:Problem:Problem:给一个N(1 ≤ N ≤ 105)N(1 ≤ N ≤ 105)N (1 ≤ N ≤ 10^5)，构造两个n的全排列，第一个序列pi ≠ i且pipi ≠ i且pipi ≠ i 且 pi &i = 0i = 0 i = 0，第二个序列pi ...
2018-02-25 16:47:25
309
原创 【欧拉降幂】CodeForces 907F Power Tower
Source:Source: Codeforces Round #454 Problem:Problem: 欧拉降幂公式。改进了一下之前的写法。 Code:Code:#includeusing namespace std;#define fi first#define se second#define pb push_back#define ALL(A) (A).begin()
2018-01-11 22:44:21
251
原创 CodeForces Gym101173 Bipartite Blanket
Source:Source:Source: 2016-2017 ACM-ICPC, Central Europe Regional Contest (CERC 16)Problem:Problem:Problem: 给你一个二分图，每个点都有点权，问这个图有多少个子集，满足点权之和不小于给定值ttt，并且被某个匹配覆盖。Idea:Idea:Idea: 容易证明若XXX集存在子集AAA属于...
2017-12-13 16:28:50
349
原创 CodeForces Gym101147F Bishops Alliance
2016-2017 ACM-ICPC, Egyptian Collegiate Programming Contest (ECPC 16)
2017-11-29 11:36:51
193
原创 CodeForces Gym101158H Animal Companion in Maze
给一张图，图上的边有单向边也有双向边。双向边有一项限制是，当使用一条双向边从A->B时，不可以立刻使用这条边回去。如果图中有环，输出INF，否则输出最长路径长度。
2017-11-28 16:23:04
452
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人