- 博客(190)
- 收藏
- 关注
RSS订阅原创 Codeforces Round 761F - Dasha and Photos
给出一个n×mn\times m 的只包含小写字母的矩阵AA。有kk次独立的操作，每次把原矩阵的某个子矩阵用一个字母覆盖得到一个矩阵AxAx(称之为特殊矩阵)。定义AxAx和AyAy的距离dis(Ax,Ay)=∑1≤i≤n,1≤j≤m|Axi,j−Ayi,j|dis(Ax,Ay) = \sum\limits_{1\le i \le n ,1\le j \le m}|Ax_{i,j} - Ay_{i,
2017-02-03 14:00:11
652
原创 Bzoj 2049 Cave 洞穴勘测
加边删边维护联通性因为保证中间过程都是一个树，所以可以LCT来做其实也可以按时间分治维护一个可撤销并查集我写的是后者具体见代码#include<bits/stdc++.h>using namespace std;const int maxn = 3123;int arr[maxn];int fnd(int x){ return x == arr[x] ? x : arr[x] = fn
2016-12-06 17:10:25
521
1
原创 Hdu 5967 小R与手机
LCT模板题如果某一次加边会成环，我们可以保证这个点一定是某一个根，在根上记录一下后继每一次切断某条边的之后同时查询根的是否有后继，后继是否可以连接具体见代码#include<bits/stdc++.h>using namespace std;const int maxn = 212345;struct Node{ int fa,son[2]; int vedg; void
2016-12-04 11:06:22
967
原创 Bzoj 2002 弹飞绵羊
学会LCT很久了，今天才会写LCT因为我使用数组而不是指针来保存节点，干脆利用起了根节点的fa这个空间来保存虚边具体的，如果fa为正数，则为splay中的边。如果是0，没有父节点。如果是负数，取反之后表示虚边所指向的父亲。具体见代码#include<bits/stdc++.h>using namespace std;const int maxn = 212345;struct Node{
2016-12-02 16:36:19
454
原创 Bzoj 4184 shallot
如果只有插入的话，直接维护线性基就好了但是现在有了删除，我们按时间分治，将操作建立成一个线段树。每一个数都有一个存活的区间，我们在线段树上更新这个区间。然后dfs线段树。线段树上每个节点维护的是到当这个节点的线性基。然后就可以免去删除操作了具体见代码#include<vector>#include<map>#include<stack>#include<cstdio>#include<cst
2016-11-24 10:35:13
473
原创 CodeForces 663E - Binary Table
给出一个n(n≤20)n(n \le 20)行m(m≤105)m(m\le 10^5)列的0101矩阵。每次操作可以将某一行取反或者将某一列取反。要求操作后的矩阵中的11的个数最少，求最小个数。因为行比较少，我们考虑状压。状压每一列的状态，stasta第ii位为11表示第ii行为11，为00表示第ii行为11用一个函数F(sta)F(sta)表示状态为stasta的列的数量考虑状压我们操作了哪些行，
2016-11-18 20:20:22
1384
1
原创 CodeForces Round 718D - Andrew and Chemistry
给出一个每个节点的度小于4的树，问有多少种增加叶子的方式（保持每个节点的度小于4）。增加之后的树同构的算一种第二个树哈希#include<bits/stdc++.h>using namespace std;#define LL long long const int maxn = 112345;vector<int> edge[maxn];int dep[maxn],fa[maxn];void
2016-11-16 11:33:43
489
原创 Bzoj 3875 骑士游戏
DP的本质是DAG上的最短路。但是如果不是DAG呢？那些常用的最短路算法，比如spfa或者是Dijkstra就可以了。感觉打开了新世界的大门。对于这个题来说，我们需要维护一个查分。具体的处理过程见代码#include<bits/stdc++.h>using namespace std;const int maxn = 212345;#define LL long long LL mag[maxn
2016-11-16 11:21:05
399
原创 Hdu 5732 Subway
给你两个同构的树，找出他们节点间的对应方式树哈希本质上就是一个树dp。考虑以树的唯一的一个节点（比如重心，直径中点）作为树根，然后用一个和子树顺序无关的方式去哈希就好了。具体见代码#include<bits/stdc++.h>using namespace std;const int maxn = 112345;#define LL long long #define Deagconst i
2016-11-14 22:12:19
318
原创 Hdu 4804 Campus Design
有一个n×m(n≤100,m≤10)n\times m(n\le 100,m\le10)的棋盘，除了一些不能被覆盖的位置外其他的地方用1×21\times2和1×11\times1的骨牌填满，1×11\times1的骨牌使用次数在[C,D][C,D]之间。问满足条件的方案数(mod109+7)\pmod {10^9+7}一个简单的插头dp入门题。不能覆盖的地方可以视作必须放下1×11\times 1
2016-11-04 16:19:36
297
原创 Codeforces 350E - Wrong Floyd
简单的构造，通过AA数组的元素个数我们可以确定可以构造出来的图的边的上界。然后判断即可。#include<bits/stdc++.h>using namespace std;const int maxn = 3123;bool vis[maxn];int getnod(int n){ for(int i = 1;i<=n;i++) if(vis[i] == false) return i;
2016-11-02 12:20:37
537
原创 Codeforces 350D - Looking for Owls
给出一些圆和线段。定义一个“猫头鹰”是满足以下四个条件的一个线段和两个圆的集合。两个圆半径相等两个圆没有交点两个圆关于线段对称两个圆圆心的连线和线段有交点圆的个数≤1500\le 1500，线段个数≤3×105\le 3 \times 10^5因为圆比较少，考虑枚举圆对统计符合条件的线段个数。首先将线段按照是否在同一条直线上分类。可以考虑用斜率和截距作为特征放在map<int,pair<i
2016-11-02 12:15:20
414
原创 Codeforces 350C - Bombs
将炸弹按照离原点点的曼哈顿距离排序之后顺序处理即可。#include<bits/stdc++.h>using namespace std;const int maxn = 112345;vector<pair<int,pair<char,int> > > ans;pair<int,pair<char,int> > npair(int st,char c = 'E',int tim = 0){
2016-11-02 12:10:54
413
原创 Codeforces 349E - Subset Sums
有n(n≤105)n(n\le 10^5)个数，有mm个下标的集合(集合的大小之和小于10510^5)维护两个操作询问操作:? k?\ k 将下标在第k个集合内数求和输出更新操作:+ k x+\ k\ x 将下标在第k个集合内的数都+x+x因为集合的大小之和小于10510 ^ 5，不妨记集合的大小之和为S考虑将集合分类。将大小超过 S−−√\sqrt S的集合称之为大集合，大小小于S−−√
2016-11-02 12:01:59
387
原创 Codeforces 349D - Apple Tree
有一个有根树，每个叶子节点都有一定量的苹果(可能为0)，非叶子节点上没有苹果。一个节点的重量定义为在以这个节点为根的子树内的节点的苹果个数和。对于一个节点称它是平衡的当且仅当这个节点的每个子节点的重量都相等。问最小需要拿走多少个苹果才能令所有节点都平衡。假设我们已经将一个子树拿成了平衡的，这个子树的父节点需要这个子树继续拿走苹果的时候，苹果是一份一份拿的，一份中含有的苹果的个数依赖于这个子树的形态。
2016-11-02 11:32:06
542
原创 Codeforces 349C - Mafia
Codeforces 349C - Mafia有nn个小朋友玩游戏。每一次游戏都必须有一个小朋友坐庄，其他的人作为playerplayer参加。对于小朋友ii，他希望至少有aia_i次游戏作为playerplayer参加，问至少需要多少次游戏才能满足所有小朋友的条件。二分游戏的次数，计算每个小朋友可以坐庄的次数，加和判断是否大于总次数即可#include<bits/stdc++.h>using n
2016-10-31 13:45:35
468
原创 Codeforces 347E - Number Transformation II
给出nn个数字xix_i，两个整数AA,BB(A−B≤106)(A-B \le 10^6)每一步可以做两个操作其中一个1 将AA变成A−1A-12 将AA变成 A−A(modx1)A - A \pmod{x_1}问将AA变成BB的最小步数。每次贪心的找到能减到的最小的大于等于BB的AA即可。如果一个A−A(modxi)<BA -A\pmod{x_i} < B ,那就可以将这个xix_i删掉。#inc
2016-10-31 13:44:13
538
原创 Codeforces 347D - Lucky Common Subsequence
给出两个长100100的字符串aa,bb。再额外给出一个长100100的字符串 virusvirus。询问aa和bb最长的没有字串是virusvirus的公共子序列。输出这个子序列。在经典的LCSLCS的dpdp解法上再加一维，记录当前的最长公共子序列匹配virusvirus的长度。第三维转移可以用KMPKMP或者ACAC自动机。#include<bits/stdc++.h>using names
2016-10-31 13:39:36
463
原创 Codeforces 347C - Alice and Bob
每一回合挑选集合中的两个数x,yx,y, 满足|x−y||x-y|不在集合中，然后把|x−y||x-y|加到集合里。给出集合最初的nn个数问是否先手必胜。游戏结束的时候最小的数就是这nn个数的gcdgcd，最大的数就是一开始给出的集合的最大的数。游戏结束的时候的集合的大小就是结束时最大的数最小的数\frac{最大的数}{最小的数}这样就可以得出游戏进行的步数,然后就可以得到结果了#include<b
2016-10-31 13:37:24
398
原创 Codeforces 344E - Read Time
二分后贪心#include<bits/stdc++.h>using namespace std;#define LL long long const int maxn = 112345;const LL INFF = 0x3f3f3f3f3f3f3f3fll;LL h[maxn],p[maxn];int n,m;bool check(LL x){ int pos = 0;
2016-10-31 13:35:39
245
原创 Codeforces 344D - Alternating Current
桌上有两根相互缠绕的电线，问能否在符合题目要求的移动下将这两根电线解开不难看出相邻的两个同色线结是可以消去的，那么能否解开就等价于能否把线结消空。这样用一个栈模拟即可。#include<bits/stdc++.h>using namespace std;const int maxn = 112345;char arr[maxn];stack<char> S;int main(){ sca
2016-10-30 22:10:33
264
原创 Codeforces 344C - Rational Resistance
刚开始有一个阻值为1的电阻。每次可以将一个电阻和某个阻值为1的电阻串联或者并联来获得一个新的电阻，问至少需要多少个阻值为1的电阻能凑出阻值为ab(1≤a,b≤1018)\frac{a}{b}(1 \le a,b\le 10^{18})的电阻假设当前手头上有xy\frac{x}{y}的电阻，那么每一次加电阻可以将其变为xx+y\frac{x}{x+y}或者x+yy\frac{x+y}{y}的电阻。通过
2016-10-30 22:07:31
272
原创 Hdu 4416 Good Article Good sentence
给出一个的字符串A,|A|≤100,000A,|A| \le 100,000，nn个字符串，分别为Bi,∑i=1n|Bi|≤100,000B_i,\sum\limits_{i=1}^n|B_i| \le 100,000，求AA中没有在任何一个BiB_i中出现的字串的个数。对AA建立SAMSAM，将每一个BiB_i都放在SAMSAM上运行，记录SAMSAM中的每个节点对应的Bi中最长的匹配长度。对于S
2016-10-25 22:05:24
241
原创 Hdu 5890 Eighty seven
有50个数，每次拿走至多三个数询问是否存在十个数满足和等于87。可以用bitset压位跑一个背包抠一抠常数就能过去惹#include<bits/stdc++.h>using namespace std;const int maxn = 55;int var[maxn];int n;int ans[maxn][maxn][maxn];bitset<88>dp[10];bool cal(){
2016-10-19 17:37:19
273
原创 Poj 3208 Apocalypse Someday
求第nn小的数位中含有三个连续的6的数。考虑小于xx的数位中含有连续三个6的数的个数，可以数位dp。状态为之前连续的6的个数，如果已经有三个6了，无论加什么数字都是合法状态，否则加一个不为6的数就重置个数为0。然后二分就好了#include<cstdio>#include<cstring>using namespace std;#define LL long long const int ma
2016-10-19 17:12:10
392
原创 Codeforces 55D - Beautiful numbers
统计[L,R][L,R]内能被自己每一非零位整除的数的个数。一眼数位dp考虑到LCM(1,2...9)=2520LCM(1,2...9) = 2520可以用前缀mod2520和前缀非0数的LCM做为状态注意到由1到9组成的lcm其实是很稀疏的，可以离散化一下。具体就见代码吧。#include<bits/stdc++.h>using namespace std;const int maxn = 20
2016-10-12 17:57:21
324
原创 Hdu 2243 考研路茫茫——单词情结
求长度小于n(1≤n<231)n(1 \le n < 2^{31})的串中包含至少一个模式串的个数。模式串总长度不超过25。市面上的题解几乎都是反着考虑。但是其实正着考虑也是可以的。我们在AC自动机的状态上额外添加一个状态AcpAcp，也就是接受态。对于两个状态St→cxSt \xrightarrow c x如果xx是某一个模式串的结尾，那么重定向St→cAcpSt \xrightarrow c A
2016-10-11 17:35:36
428
原创 Bzoj 3530 数数
求[1,n](n≤101000)[1,n](n\le 10^{1000})中不包含给定数字作为字串的数字个数(mod109+7)\pmod{10^9+7}，给定数字总长度≤1500\le 1500。一眼看过去是一个用AC自动机表示状态，用数位dp的模板题注意前导零是不会被统计到的具体见代码#include<bits/stdc++.h>using namespace std;const int ma
2016-10-11 16:54:04
271
原创 Hdu 4507 吉哥系列故事——恨7不成妻
Hdu 4507 吉哥系列故事——恨7不成妻求[L,R][L,R]中不满足以下任意一条的数的平方和1 整数中某一位是72 整数的每一位加起来的和是7的整数倍3 这个整数是7的整数倍；一眼看去又是一个数位dp，但是怎么统计平方和呢？假设我们在统计最高位为x的n个数的平方和有∑i=1n(x+a)2=n×x2+2x×∑i=1nai+∑i=1na2i\sum\limits_{i=1}^n ( x + a )
2016-10-09 10:15:56
321
原创 Lonlife 1016 Change of Life
定义f(x)f(x)为LIS(a0,a1...am)(n=a0+a1×10+...+am×10m,0≤ai≤9,am≠0)LIS(a_0,a_1...a_m)(n = a_0 + a_1\times 10+...+a_m\times 10^m,0\le a_i\le 9,a_m\neq 0)求∑ni=1f(i)\sum_{i=1}^nf(i)1≤n≤10151 \le n \le 10^{15}一眼
2016-10-09 09:56:36
275
原创 Codeforces 258B - Little Elephant and Elections
从[1,m][1,m]中依次选择77个数，满足前六个数中44和77的个数之和小于最后一个数的44和77的个数的方案数(mod1e9+7)\pmod{1e9+7}我们按照4和7的个数对[1,m]的数做等价类划分。然后dfs就好。前半部分可以用数位dp解决。#include<bits/stdc++.h>using namespace std;const int maxn = 12,mod = 1e9+
2016-10-08 08:40:15
347
原创 Hdu 5456 Matches Puzzle Game
问有多少个等式满足使用的火柴棍个数恰好为nn个输出等式个数(modm)\pmod{m}5≤n≤500,3≤m≤2×1095\le n \le 500,3 \le m \le 2\times 10^9就是求满足a+b=ca + b = c，并且a,b,ca,b,c每一位按照使用的火柴棍个数加权之后恰好等于n−3n-3的等式个数考虑到这个题的状态和之前使用了多少位无关并且保证剩下的火柴棍是单调递减的可以
2016-10-06 17:20:36
518
原创 Hdu 5921 Binary Indexed Tree
题解链接题意搬运: 用树状数组维护一个序列，在给区间 [l,r][l,r] 加上一个tt的时候，要给 [1,r][1,r]加上 tt，给 [1,l−1][1,l−1] 减去 tt，两次操作后值真正发生变化的节点个数就是这一次区间修改的代价，现在要修改每一个[1,n][1,n]的子区间，求总代价对 109+710^9+7取模后的结果。题解搬运 记cnticnt_i表示ii的二进制表达式中11
2016-10-05 21:53:14
1511
原创 Hackerrank Coprime Conundrum
计算小于乘积小于nn的互质二元组的个数具体的，计算\sum_\limits{i=1}^n\sum\limits_{j=i}^n[i \times j \le n][gcd(i,j)=1]\sum_\limits{i=1}^n\sum\limits_{j=i}^n[i \times j \le n][gcd(i,j)=1]其中n≤109n\le 10^9可以考虑枚举ii，计算和ii互质大于ii并且和i
2016-10-05 12:40:29
310
原创 计蒜客 青云的机房组网方案
题面: 有一棵点数10510^5的树，每个节点有一个权值，权值范围是[1,105][1,10^5]的，问所有两个权值互质的节点之间距离的和题解关于虚树，记下一些key point以后要是忘了可以回来看看虚树是保留原树的所选定的一些节点，保留这些选定节点两两的LCALCA，按照这些保留点在原树中的关系所建的一个新树。可以保证如果选定节点是kk个，那么虚树的节点不会超过2×k2 \times k。
2016-10-03 13:47:12
579
2
原创 Hdu 5909 Tree Cutting
n(n≤1000)n(n\le 1000)个点的树上每个点有一个权值(0≤Ci<m,m≤210)(0\le C_i < m,m\le 2^{10})，定义一个子树的权值为这个子树节点的权值的异或。分别求权值为[0,m−1][0,m-1]的子树的个数mod(109+7)mod(10^9+7)对于一个无根树的子树，如果我们钦定一个点作为无根树的根，那么对于这个树的所有子树都可以钦定出唯一的一个点作为根。
2016-10-02 23:20:15
930
原创 hihocoder 1387 A Research on The Hundred Family Surnames
题解网址以下为搬运 题意： 给一棵树，每个节点上有个颜色，很多询问，询问两种颜色，问从这两种颜色中各取一个节点，距离最大是多少。 题解：处理出每种颜色的节点们的直径(也就是距离最大的点对)。然后对于两种询问颜色(a,b)(a,b)的直径(au,av)(au,av)和(bu,bv)(bu,bv)，答案就是max{dis(au,bu),dis(au,bv),dis(av,bu),dis(a
2016-09-30 17:26:50
489
原创 UVA 1728 Toll Management IV
一个n(n≤104)n(n \le 10^4)个点m(m≤105)m (m \le 10^5)条带权(0≤Ci≤1000)(0 \le C_i \le 1000)边的无向图，给出原图的一个最小生成树(输入的前n−1n-1条边)对于第ii条边，定义AiA_i和BiB_i为在不改变最小生成树形态下增加和减少的最大的值求 ∑i=1mAi×i+Bi×i×i\sum\limits_{i=1}^m A_i \t
2016-09-23 15:08:04
444
原创 hdu 4899 Hero meet devil
给出一个模式串S,|S|≤15S,|S| \le 15问存在多少个长为m,m≤1000m,m\le 1000的字符串TT满足LCS(S,T)=x(0≤x≤|S|)LCS(S,T) = x(0\le x\le|S|)输出|S|+1|S|+1个结果(mod109+7)\pmod{10^9+7}|S||S|表示字符串SS的长度本题中的字符集为A,T,C,GA,T,C,G四个字母算是一个dp of dpdp
2016-09-20 20:37:08
493
原创 Hdu 5895 Mathematician QSC
f(0)=0,f(1)=1,f(n)=f(n−2)+2∗f(n−1)g(n)=∑i=0nf(i)2f(0) = 0, f(1) = 1, f(n) = f(n - 2) + 2 * f(n - 1) \\g(n) = \sum\limits_{i=0}^nf(i)^2, 求 xg(n∗y) mod (s+1)x^{g(n * y)}\ \mathrm{mod}\ (s + 1)首先有一个公式写作xa
2016-09-18 19:51:57
871
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人