• 等级
  • 339482 访问
  • 1188 原创
  • 3 转发
  • 1248 排名
  • 125 评论
  • 94 获赞

UOJ #395. 【NOI2018】你的名字 后缀自动机

题意 给一个串S,每次询问给出一个串T和区间[l,r],问T中有多少个不同的子串满足其不是S[l…r]的子串。 ∣S∣,∣T∣≤5∗105,q≤105,∑∣T∣≤106|S|,|T|\le5*10^5,q\le10^5,\sum |T|\le10^6∣S∣,∣T∣≤5∗105,q≤105,∑∣T∣≤106 分析 在noi考场上打了个又臭又长的做法,还只有68分。正解其实并不算难。 先补集转化一下,...

2018-10-14 16:22:50

Codeforces 98E Help Shrek and Donkey 纳什均衡

题意 有n+m+1张牌,牌上的数字互不相同且均在[1,n+m+1]中。A有n张牌,B有m张牌,还有一张牌盖在桌上。现在A和B轮流操作,当前操作的那一方有两种操作: 猜盖在桌上的牌是什么,若猜对则直接获胜,猜错则直接输。 猜一张对方的手牌,若猜对则对方需要把该牌扔掉,猜错则没有影响。 假设双方都绝顶聪明,问先手获胜的概率是多少。 n,m≤1000n,m\le1000n,m≤1000 分析 想看比较详...

2018-10-04 12:30:21

AtCoder Regular Contest 103 F - Distance Sums 构造

题意 给出n和一个长度为n的数组d,满足d数组中的任意两个元素互不相同,要求构造一棵n个节点边权为1的树,使得所有节点到节点i的距离和恰好为d[i]。 n≤100000n\le100000n≤100000 分析 显然按d[i]排序之后,要么从小到大构造,要么从大到小构造。 由于d[i]互不相同,不难发现d[i]最小的一定是重心,d[i]最大的一定是叶子。 由于一棵树中除了根以外每个节点只有一个父亲...

2018-10-01 22:19:40

牛客练习赛27 B-手办 乱搞

题意 给出nnn,设f(x)f(x)f(x)表示有多少个有序数对(a,b)(a,b)(a,b)满足ab∣xab|xab∣x。 求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1n​f(i)。 n≤1012n\le10^{12}n≤1012 分析 看完题目就开始推式子,不难得到答案就是∑i=1n⌊ni⌋σ0(i)\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\s...

2018-09-24 11:44:30

牛客网Wannafly挑战赛24 D-无限手套 生成函数

题意 有n种物品,每种物品有两个参数ai,biai,bia_i,b_i。现在可以从每种物品中选出若干个,设第i种物品选了xixix_i个,则贡献∏i=1n(aix2+bix+1)∏i=1n(aix2+bix+1)\prod_{i=1}^n(a_ix^2+b_ix+1) 有q次询问,每次询问给出一个m,求所有选的物品总数为m的选择方案的贡献和,答案模998244353。 n,q≤1000,m≤...

2018-09-15 17:31:51

Codeforces 1037H Security 后缀自动机+线段树

题意 给一个长度为n的字符串s,有q次询问,每次询问给出一个区间和一个字符串t,求区间中字典序最小的子串使得该子串的字典序大于t。 n≤105,q≤2∗105n≤105,q≤2∗105n\le10^5,q\le2*10^5。 分析 无聊模版题。 先预处理出sam上的right集线段树,枚举答案串和t的lcp长度,再枚举下一个字符是什么,然后直接在线段树上查找即可。 时间复杂度O(n...

2018-09-09 17:25:23

牛客网Wannafly挑战赛23 F-计数 矩阵树定理+拉格朗日插值法

题意 给出一个n个点m条边的带权无向图,问有多少棵生成树满足边权和模k等于0,答案模p输出。 n,k≤100,p≤109,p为质数且满足k≡1(modp)n,k≤100,p≤109,p为质数且满足k≡1(modp)n,k\le100,p\le10^9,p为质数且满足k\equiv1\pmod p。 分析 一种直观的套路就是把每条边的边权看成是xwxwx^w,然后做矩阵树定理,最后得出来...

2018-09-09 16:13:42

AtCoder Regular Contest 102 题解

前言 开学之后估计就没办法打比赛了。 开场做掉A和B之后,C写了个NTT结果被卡常,然后就一直卡到快比赛结束,这时突然发现第二个生成函数只用预处理到一半!在还有两分钟结束的时候成功卡过,怒涨了一波rating。。。 题解 C - Triangular Relationship 乱做。。。 代码 #include<iostream> #include<cstd...

2018-09-01 23:54:38

Codeforces 1016G Appropriate Team 数学

题意 给出一个长度为n的数组a和两个数X,Y,问有多少个数对(i,j)满足存在一个数v使得gcd(a[i],v)=X且lcm(a[j],v)=Y。 n≤200000,X,Y,a[i]≤1018n≤200000,X,Y,a[i]≤1018n\le200000,X,Y,a[i]\le10^{18} 分析 显然X一定是Y的约数,然后有X是a[i]的约数,a[j]是Y的约数。 然后考虑X和Y...

2018-09-01 10:14:16

AtCoder Regular Contest 101 E - Ribbons on Tree 树形dp+容斥原理

题意 给一棵树,现在可以把节点之间两两配对,问有多少种配对方案满足每一条边都至少在某一对节点的最短路径上。 n≤5000n≤5000n\le5000 分析 很容易想到树形dp:设fi,jfi,jf_{i,j}表示以i为根的树中,还有j个点没有配对的方案。这样做显然是O(n3)O(n3)O(n^3)的,然后又发现没办法优化,于是就只能另寻出路。 考虑容斥,我们可以枚举有哪些边一定没有被...

2018-08-31 20:16:57

Codechef MONSTER 整体二分+分块

题意 有n个敌人,编号为0到n-1,每个敌人都有一个血量h。现在有q次操作,每次给出两个数x和y,表示将所有编号为x的子集(二进制下)的敌人血量都减去y。要求每次操作后输出还剩下多少个敌人的血量大于0。 n≤217,m≤218,h,y≤109n≤217,m≤218,h,y≤109n\le2^{17},m\le2^{18},h,y\le10^9 分析 已经颓废到开始写题了。 首先可以整...

2018-08-31 18:36:54

bzoj 4939: [Ynoi2016]掉进兔子洞 莫队算法+bitset

题意 有 m 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,比如三个区间是 [1,2,2,3,3,3,3] , [1,2,2,3,3,3,3] 与 [1,1,2,3,3],就一起扔掉了 1 个 1,1 个 2,2 个 3。 n , m <= 100000 , 1 &...

2018-08-26 10:41:55

Codeforces 1027G X-mouse in the Campus 数论+Pollard_rho

题意 给定mmm和xxx,满足gcd(m,x)=1gcd(m,x)=1gcd(m,x)=1。现在把每个小于mmm的整数都看作一个点,然后iii向ixixix连边,问最后最少需要选出多少个点使得每个点的后继中至少有一个点被选。 m≤1014m≤1014m\le10^{14} 分析 感谢sam队长教我做这题。 首先因为gcd(m,x)=1gcd(m,x)=1gcd(m,x)=1,所以最后...

2018-08-19 14:10:04

Codeforces 1019C Sergey's problem 构造

题意 给定一个n个点m条边的有向图,要求选出一个点集S,满足S中的任意两点间没有边相连,且对于任何一个不属于S的点y,必然存在S中的某个点x满足d(x,y)≤2d(x,y)≤2d(x,y)\le 2,其中d(x,y)d(x,y)d(x,y)表示x到y的最短路。 n,m≤106n,m≤106n,m\le10^6,题目保证有解。 分析 具体一点的题解可以看这篇文章。 大概做法就是,对于当前图...

2018-08-12 11:18:16

Codeforces 1019D Large Triangle 计算几何

题意 给出平面上n个点,问是否存在三个点构成的三角形的面积恰好为S。 n≤2000n≤2000n\le2000 分析 在这题做法的基础上套一个二分就没了。 代码 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include&lt...

2018-08-12 09:58:03

bzoj 3707: 圈地 计算几何

题意 2维平面上有n个木桩,黄学长有一次圈地的机会并得到圈到的土地,为了体现他的高风亮节,他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形,多边形的顶点就是一个木桩,圈得的土地就是这个多边形内部的土地。(因为黄学长非常的神,所以他允许圈出的第n点共线,那样面积算0) n≤1000n≤1000n\le1000 分析 先考虑枚举两个点,然后以这两个点所在直线为y轴旋转下坐标系...

2018-08-12 09:46:23

牛客多校 Playing games FWT

题意 给出nnn个数a1,a2,...,ana1,a2,...,ana_1,a_2,...,a_n,问最多选出多少个数使得这些数的异或和为0。 n,ai≤5∗105n,ai≤5∗105n,a_i\le 5*10^5 分析 震惊!老年退役选手居然开始写题解了。 这次回家本来也没打算写题的,但是在今早某人问了我这个题,想了快一个小时终于会了,然后就用睡觉的时间把这题过掉了。刚好现在闲得无...

2018-08-11 21:30:48

CodeM2018游记

前言 复赛的时候打了54名,本以为无望决赛了,过了几天后居然收到了CodeM的邮件,真不知道那些鸽掉的人是怎么想的。 day0 先去酒店报道,然后参加晚宴,每个人送书包好评。 晚上还有小姐姐送水果和酸奶。 day1 去美团总部参观,听工作人员介绍了一发美团的基本情况和,中午在员工餐厅吃盒饭。 下午先是去公司办公的地方参观了下,然后听了几个十分学术的讲座,唯一的印象就是茶点很棒...

2018-07-28 16:03:42

Codeforces 1010E Store KD树

题意 已知三维空间中有一个长方体,但现在并不知道长方体的位置。然后给出n个一定在长方体内部的点和m个一定不在长方体内部的点,之后会询问k次,每次询问一个点是否一定在长方体内部。 n,m,k≤105n,m,k≤105n,m,k\le10^5 分析 比赛的时候可能多给两分钟就可以过掉这题了。 先通过那n个点确定出一个长方体,然后对于一个询问的点,若其在该长方体内部,则它一定在原长方体内部,否...

2018-07-27 06:34:22

NOI2018退役记

前言 真·最终之战 day0之前 去了雅礼集训,每天的模拟赛要么早早ak,要么根本做不动,感觉一点都不仿真,被弄得信心全无。然后下午晚上基本就都在酒店写题或战斗,过的十分快活。 day0 早上去报道,签完到居然还被小姐姐采访了。跟我一起被采访的大佬麦看上了采访我们的小姐姐,之后费尽心思想要打听人家消息,但最后还是没要到联系方式。 下午和晚上就战斗一下顺便背了背笔试。 #day1 早...

2018-07-24 22:30:43

SFN1036

本人单身,一般不坑
关注
  • 中学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒
  • 1024超级勋章