- 博客(56)
- 收藏
- 关注
RSS订阅原创 SRM549
250 PointyWizardHats 题意：n个圆锥型小帽子和m个圆锥形大帽子,现在要把一顶小帽子和一顶大帽子组合起来，组合的条件是xxx,问最多能组合多少对分析：直白的二分图匹配，少见250出这个600 MagicalHats 题意：一块13*13的板子，一些位置有帽子，某些帽子后面藏有面值不同的硬币，且任意时刻每个帽子后面只有至多一枚硬币，现在要猜K次，魔术师在每次猜之前可以改变硬币
2016-07-13 00:58:04
517
原创 SRM546
250 KleofasTail 题意：定义x的生成数列为f(x)=x&1?x−1:x/2f(x)=x\&1?x-1:x/2,给出K,L,R,询问有多少个位于L,R之间的数，它们的生成数列中至少出现一次K.0≤L,R,K≤10180\leq L,R,K\leq10^{18}分析： 观察发现生成数列中含有K的充要条件是二进制前缀与K相同(K为奇数)，或者与K+1相同(K为奇数)，因此只要枚举位数，
2016-07-13 00:56:51
385
原创 SRM545
275 StrIIRec 题意：求一个字典序最小的排列满足他的字典序>=minStr并且逆序>=minInv，n<=20分析：枚举第一个不同的位置，然后从小到大暴力填，判断一下逆序是否足够500 Spacetsk 题意：求有多少个K元组，满足0≤x≤L,0≤y≤H0\leq x\leq L,0\leq y \leq H并且它们在一条直线上，且这条直线和x轴有非负整数交点L,H,K≤2000L
2016-07-13 00:55:44
426
原创 SRM694
250 TrySail 题意：把一个数列分成非空的三组，要求每组异或和的和最大(0≤a[i]≤255,n<=50)(0\leq a[i] \leq 255,n<=50)分析：由于异或有减法，所以只要确定两组的异或值，第三组的异或值就确定了，因此可以dp[i][j]代表第一组异或和为i，第二组异或和为j是否可能，注意到取到最大值的三组必然是非空的，因为有a^b<=a+b500 Distingui
2016-07-13 00:53:31
565
原创 SRM541
550 AkariDaisuki 题意：f(X) = Waai + X + Akari + X + Daisuki,求F在f^k(S)种出现的次数，k<=10^10,S,F,A,B,C串长<=50分析：显然F出现次数的增量之和X的前后缀有关，因此当到达一定次数之后X的前后缀就不会发生变化了，只要矩阵算算就可以了，次数较少的时候可以暴力1000 XorLife 题意：一个无限大的平面，初始除了
2016-07-13 00:52:56
329
原创 5528Count a b
题意：考虑一块N∗NN*N的板，a[i][j]=i∗j%Na[i][j]=i*j\%N,记f(n)为这块板上非0的数目，求g(n)=∑i|nf(i)g(n)=\sum_{i|n}f(i),n<=109,T<=20000n<=10^9,T<=20000分析：考虑i∗j%N==0的(i,j)i*j\%N==0的(i,j)有什么性质； 不妨枚举ii,那么合法的j应该满足gcd(i,n)∗j%N==0gc
2016-06-28 20:50:06
400
原创 round15
F:问有多少对n个元素的集合A,B满足它们的笛卡尔和恰由1 ~ n2n^2构成，其中A包含0，B包含1 n<=1012,T<=5000n<=10^{12},T<=5000分析：考虑固定B，如何去确定A; 首先，0在A中，那么所有B中的元素就都在笛卡尔和中；考虑第一个B中没有出现的数x，那么x-1必然在A中（不然1和这个数作用就会重复），然后我们把x-1和B中所有元素再做一遍笛卡尔和； 接着我们
2016-06-28 01:40:03
711
原创 SRM540
250 ImportantSequence 题意：告诉你相邻两数的操作符和运算结果，求有多少满足要求的正整数序列分析：固定了第一个数，答案就固定，由于有每个数都是正整数的限制，因此可以把限制都转移到第一个数上，把每个数用第一个数表示，就可以得到一系列不等式，解一下即可550 RandomColoring 题意：定义颜色为（R，G，B）的三元祖，给定一个初始颜色，按照某种规则生成等概率生成下一
2016-06-14 23:50:40
409
原创 AX+BY<=C的解的个数
目标就是求满足AX+BY<=C的(X,Y)对数，即求∑x=0∑y=0[Ax+By<=C]\sum_{x=0}\sum_{y=0}[Ax+By<=C]其中1<=A,B<=1e9,C<=1e9*min(A,B),X>=0,Y>=0稍微化简二重和式得到∑x=0⌊CA⌋⌊C−A∗xB+1⌋\sum_{x=0}^{\lfloor \frac{C}{A}\rfloor}\lfloor \frac{C-A*x}{
2016-04-11 21:30:17
1168
原创 线性规划单纯形模板
#include<bits/stdc++.h>using namespace std;const int Maxn=110,Maxm=59;class Simplex{ /* 功能： 接受有n个约束，m个基本变量的方程组a[0~n][0~m] a[0][]存放需要最大化的目标函数，a[][0]存放常数 Base[]存放基本变量的i
2016-04-11 18:57:45
2487
原创 欧拉筛法和积性函数
众所周知，求素数可以使用筛法，代码大概是这样子for(int i=2;i<N;i++){ if(!isp[i]){ pri[tot++]=i; for(int j=i+i;j<N;j+=i) isp[j]=1; }} 这样子的复杂度怎么算呢，可以粗略估计，内层for循环只会在ii是素数的时候进行,因此，总的计算次数大约是∑k
2016-04-11 17:13:04
822
原创 3月第三四周小结(3.16~3.27）
距离上一次写总结时间太久，自己也没能很好的履行预期的计划华为软件精英赛暂时rk1,所以可以先暂时搁置，过一段时间必要时再去看结果，因为之后有复赛，可以想一下如何构造数据卡别人这两天要把tc和数学补起来，尤其是tc,对思维的训练提高帮助比较大英语暂时搁置一下不进行早读，等过两天英语卷子到了再去总之，下一周还是要恢复之前的作息与时间安排暂时需要思考的就是有趣的游戏和tc524 500
2016-03-26 21:57:22
529
原创 3月第二周(3.8~3.14)总结
本周做了些什么呢？ 按照考研复习计划，3月份只复习数学，英语和专业课。数学： 第三章仍然还有一个知识点没看，有若干作业题没有完成。。。学习了数值分析中的插值法；看了一眼高数中的二重积分TBD：具体数学第三章习题必须要补完了，补完之后再看一下第五章组合恒等式，第五章可能两三个星期都未必能完成，但是是后面生成函数的基础，有必要好好学习英语： 这一周因为各种各样的理由只去背了两天英语（颓）
2016-03-15 21:42:21
499
原创 3月第一周总结(3.1~3.7)
本周做了些什么呢？ 按照考研复习计划，3月份只复习数学，英语和专业课。数学： 完成了具体数学第二章的摘抄和课后题，第三章开了个头（第三章最后一节的难度看上去比较大TAT，不过也许和别人讨论一下会好一点）；学习了数值分析和离散数学第一章的内容，完成了少量课后题（并没什么用）；至于数学分析，线性代数，概率论什么的，当然还没开始！TBD：具体数学第三章摘抄和习题英语： 坚持早起（7:15）
2016-03-08 16:19:19
528
原创 2016CampDay1总结
今天是campday1,做下总结， 早上是热身赛,T1是去年出过的题目，T2是：给出一个{1,2..n}的集合，求一个最大的子集，满足x和2x+2不同时在这个子集当中；(n<=10^100) 赛后问了xg,感觉还是可做题，大概是说，直接枚举链的长度，根据长度，可以得出最后一项的范围，还没仔细想（坑） 之后是day1的正赛，据叉姐说，这场是所有比赛中最简单的，结果我们还是只通过了两题。。。。大概
2016-01-26 01:27:11
857
原创 虚树留坑
上一期的cf上出了一道虚树的题目，“虚树”一直听别人讲，但自己始终没有去学习，于是去这里学习了下，还是比较简单易懂的。大概就是说，针对一类每次询问树上部分点的信息的问题，我们可以把被询问的点单独拿出来，为了维护这些点的相对位置，我们找到一个点数最少的关于点的子树（相当于缩掉那些无关紧要的点),然后再在这棵树上做操作。可以证明，这棵树的大小将是O(询问点的个数)O(询问点的个数)，这颗树就叫做虚树。
2016-01-19 22:22:40
525
原创 某类线段树的复杂度分析
题目：http://codeforces.com/contest/610/problem/E 题意：给出一个长为n,n<=200000n,n<=200000只含前k,k<=10k,k<=10个字母的ssss，有m,m<=2wm,m<=2w次操作,每次： 1 l r c1\space l \space r \space c 将[l,r]范围内的字符都改为c 2 s2\space s保证
2015-12-29 22:06:51
2858
原创 HDU5599GTW likes tree
题目 题意：给出一棵点有权的树，求∏i,jgcd(val[i],....val[j])\prod_{i,j}gcd(val[i],....val[j]),就是求所有路径gcd的乘积,保证1<=val[i]<=1051<=val[i]<=10^5分析：一个简单的思路就是暴力树dp，开一个vector记录每个点向下连出去的gcd的情况，通过前缀积的做法可以做到O(n∗fac)O(n* fac),然而比
2015-12-15 21:42:45
521
原创 ASC 20简要题解
题目链接 A:暴力kmp,dp计算答案,一个串是循环串当且仅当i%(i-f[i])==0，此时(i-f[i])为最小循环节 B：模拟，注意第二种规则是说，“括号的方向朝着箭头指向的方向”，把“(“当成+1,”）“当成-1,找到前缀和最小的地方，从那里将循环切断即可得到一个必然合法的括号序列 C：树哈希。由于这里数据范围比较小，可以直接用set记录每个节点所有儿子的id.可以看出，两个节点不同意
2015-11-27 17:07:38
1268
原创 ACM-ICPC北京赛区2015网络同步赛E:Stamps
链接 题意：Bob向Alice买邮票，每种邮票有无限张，Bob每次等概率选择一种邮票买（可以买买过的），每次代价为H[i][k]H[i][k],其中kk为给定常数且k<10k<10,HH的定义为：H(i,0)=1, i=1,2,...H(i, 0) = 1, \space i = 1, 2, ... H(i,k)=H(1,k−1)+H(2,k−1)+...+H(i,k−1),k>0, i>0H(
2015-11-15 23:52:26
1137
2
原创 cf#327 (Div. 1)E. Birthday(最长反链)
链接：http://codeforces.com/contest/590/problem/E 题意：给出n(n<=750）个字符串，要求从中选出尽可能多的串，使得两两不是包含关系，并输出方案。（串长不超过10710^7）用AC自动机处理包含关系之后，题目转化为求最长反链，并输出方案。关于DAG的最长反链，可以参考这个，然而本题的难点在于输出方案。结论是：最小点覆盖的补集就是最长反链的方案。首先，由
2015-10-27 20:35:15
635
原创 Codeforces Round #327 (Div. 1)题解
A：给出一个01串，每次把一个位置ii上的数a[i]a[i]变成{a[i],a[i+1],a[i−1]a[i],a[i+1],a[i-1]}的中位数（两端不变），问几次之后这个串不再发生变化。分析：模拟尝试发现假如a[i]a[i]和任意相邻的数相同则他永远都不会再发生变化，因此要考虑的就是连续的01串，这里也之要根据连续01串长奇偶性讨论下即可B：二维平面给出起点，终点坐标，要求静止时的速度不超过v
2015-10-27 20:02:00
474
原创 最近两场cf总结
最近做了两场cf,通过了当中所有的题目，稍稍做下总结 Codeforces Round #325 (Div. 1) 这场是我排名最靠前的一次（23）,虽然04写的比较慢，但是幸运的猜出了03,05和06都是短代码的可做题，然而并没有时间去看，这说明代码能力还是很重要的 A：有n个小孩依次去看牙齿，每个小孩看的时候会对后面的小孩造成等差递减的伤害，假如小孩不能承受这个伤害就会逃跑，问最后有几个小
2015-10-25 14:39:48
412
原创 HDU4624Endless Spin(clj计数ppt）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4624 题意：总共有n个球，每次随机选择一段区间染黑（每段区间被选择的概率相同），求期望多少次所有球都被染黑。分析：虽然ppt中说显然，但我认为这个问题最为精妙的地方就在第一步：期望次数=∑i=1∞p[i]期望次数=\sum_{i=1}^\infty p[i]，其中p[i]p[i]为i次之后仍然存在白球的概
2015-10-15 19:46:16
1661
原创 HDU4903The only survival(clj计数问题ppt)
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4903 题意：问有多少种无向完全图满足1-n最短路径为k且每条边都在[1,L]; L<10910^9,n,k<=12; 分析：先想暴力怎么计算答案，一种方法是枚举1到每个点的最短路长度，然后图的种数就可以计算了；仔细思考发现我们只关心d[i]=x的点个数即可，由于我们只关心d[i]#include<bi
2015-10-08 23:30:39
939
原创 插头dp模板（简单路径+一条回路+广义路径）
#include<cstdio>#include<algorithm>#include<cstring>#define Ms(a,x) memset(a,x,sizeof(a))/*插头dp模板1.解决1条简单路径问题2.本模板使用括号表示法，hash使用链表4.输入的为地图权值，输出的为一条简单路径可以得到的最大权值（有障碍，路可以不走）5.记得当状态表示的太大时code的类型要
2015-10-04 19:07:09
599
原创 四川省赛G.Party
题目链接：http://acm.bnu.edu.cn/v3/contest_show.php?cid=6865#problem/G 题意：n只青蛙，要么只喝绿茶，要么只喝红茶，要么两种茶都能接受，还有m个憎恶关系，互相憎恶的两只青蛙不能喝同一种茶，憎恶关系构成的图保证是一张二分图，当然，你还可以选择花费w[i]的代价删掉某只青蛙。问最少需要花费多少代价。分析：题目问最小代价，给出的又是憎恶关系，容
2015-10-01 20:58:38
476
原创 卡諾图
在上计算机组成原理的时候老师介绍了一个问题：化简一个只含与或非的逻辑表达式。不清楚什么是最简的（囧），暂时认为他指的是所有变量出现的总次数最少（包括变量的非）。老师介绍了一种神奇的一般的化简方法：卡諾图。记与运算为×\times,或运算为++,具体来说， 1.把原式化成若干个最小项相或的形式，因为A=A×(B+B˜)A=A\times(B+\widetilde{B}),因此，所有项都可以补成最小项
2015-09-30 21:25:02
652
原创 Codeforces Round #319 (Div. 1)E.Painting Edges(并查集)
题意：给出n个点,m条边的一张无向图,给出q个操作，每次给一条边染色，假如染色后相同颜色构成的边仍然是二分图，则输出YES并且执行这次染色，否则输出NO并跳过这次染色 n<=50w,m<=50w,颜色数k<=50,q<=50w分析：经典的题目。套用分治+并查集可以解决这类带删边的判定图的联通性或者是否是二分图的问题。思路就是给每个修改一个作用域（l,r），按照时间分治solve(L,R)，假如(l
2015-09-18 15:07:52
585
原创 Bubble Cup 8 - Finals [Online Mirror]C. Party
题意：n个人n场宴会，每个宴会有白天和黑夜两种选择，要求一半人参加白天的宴会，一半人参加晚上的，且一个宴会只有一个人能参加，求最大带权匹配。(n<=20) 思路：枚举每个宴会选择白天还是晚上，最后跑KM匹配，这样会得到一个C(20,10)∗n3C(20,10)*n^3，考虑到KM匹配是一个点一个点添加进去，因此显然可以在dfs的过程中顺便寻找增广路。另外，我采用之前的KM算法并没有通过这道题，学习
2015-09-10 20:39:06
573
原创 矩阵行列式mod M
这是一个比较经典的问题，首先行列式的计算就是一个高斯消元的过程，然而有时候行列式的值会非常之大，因此题目常常让我们求det mod M.我们知道普通的高斯消元涉及除法，模意义下的除法当M为质数的时候显然可以通过求逆元解决，但当M非素数（例如M是一个素数的幂次）可能不存在乘法逆元。这里介绍一个经典的方法。 首先，高斯消元用除法只在用主元把非主元的行消成0.根据行列式的性质，一行减去另一行的任意倍行列
2015-08-30 17:20:30
3082
原创 hdu5412CRB and Queries(整体二分)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5412 题意：带修改的区间第k小，允许离线 分析：这道经典的问题有多种做法，其中知名度比较高的有树状数组套主席树(nlog2nnlog^2n空间+nlog2nnlog^2n时间)，线段树套平衡树(nlognnlogn空间+nlog2nnlog^2n时间)。然而树套树不仅代码量大，而且难写难调，令人望而
2015-08-21 14:44:48
1694
原创 hdu5405 Sometimes Naive
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5405 题意：给出一棵节点上有权的树，两种操作： 1.修改一个点的权 2.询问一条路径u到v，求∑wi∗wj\sum w_i*w_j,i到j的路径和uv有公共点分析：记road(u,v)road(u,v)为u到v的路径，对于询问，可以分两种情况考虑： 1.lca(i,j)∈road(u,v)lca(i
2015-08-19 17:04:38
1220
原创 hdu5393 Falsyta in Tina Town
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5393 题意：给出k,b,x0,pk,b,x_0,p,xn=(xn−1∗k+b)modpx_{n}=(x_{n-1}*k+b )\mod p,求最小的n,使得xn=x0x_n=x_0,如果不存在输出-1。 分析：通过简单的数学推导，题目即求最小的n使得 ((k−1)∗x0+b)∗(1+k+k2+k3+.
2015-08-16 13:31:59
1334
11
原创 Andrew Stankevich Contest 35 简要题解
F. Graph Factorization 题意：给出一张2n阶的完全图，现在要求将他的边划分为m个部分，每个部分要求每个顶点的度是aia_i,保证∑ai\sum a_i =n+n-1 分析：智商题，首先就是要构造全是1的，然后按照要求叠加就可以了，构造的核心在于如何能让边用的不重复，有一种简单的构造方法就是每次把1 i单独拿出来，剩下的点在i的两侧分布，对称的点之间连边就可以。J
2015-08-15 18:49:01
966
原创 hdu5377 Root
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5377 题意： 给出一个sum,询问m次，每次询问xi,yi,求一个最小的ki使得xkii=yi mod p对至少一个sum的素因子p成立。给出一个sum,询问m次，每次询问x_i,y_i,求一个最小的k_i使得 x_i^{k_i}=y_i\space mod\space p对至少一个sum的素因
2015-08-13 11:00:12
953
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人