- 博客(212)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 信息学比赛经验错误总结（实时更新）
#**比赛经验总结****1.**数组上下标要多开几维以防爆数组。**2.**数据类型要注意，大多时候需要开long long。**3.**做题不能太大胆，想到什么就认为正解是什么；同样的，也不能太保守，无论想到什么都否定算法的正确性。**4.**打对拍时，特别要注意对拍与程序共用的部分，共用的部分一旦打错，即使程序是错的也检验不出来。**5.**某些运行时错误在编译器内运行是不会被显示出来的。（这个特别坑
2016-04-27 21:34:05
4103
1
原创 近期训练总结
3.12T1 Mas的仙人掌：考虑1=[路径上点的个数-路径上边的个数]，树链剖分后变成区间赋值，注意要考虑0的情况，要把运算struct起来。T2 Z的礼物 ：用b表示a，斯特林反演一下，用a表示b，倍增求出多项式即可。T3 Mas和Z玩游戏：Snack Down 2019 Final 原题。枚举最短的原串，根据给出的拼接串的每种长度的数量可以求原串中每种串的数量，从短往长一一还原出原串即...
2019-03-28 22:43:00
827
2
原创 Atcoder Grand Contest F Construction of a tree
Construction of a tree题目链接Solution考虑这样的一个二分图，图左边全是点xxx，右边全是集合EiE_iEi。若x∈Eix \in E_ix∈Ei，则让xxx向EiE_iEi间连一条边。假设我们已经把树建出来了，选择任意一个节点为根并把这个节点去掉，可以发现剩下的点和剩下的边恰好可以一一配对，这也就意味着，对于上述的二分图，去掉左边任意一个点后，二分图依旧...
2019-01-27 22:03:54
473
原创 AtCoder agc 030 E
Less than 3题目链接Solution首先我们可以发现一个性质，假设我们要变动第iii个位置上的字符，可以发现如果变动使得变动前后不存在连着相同的三个字符，那么一定有i−1i-1i−1位置上的字符和i+1i+1i+1位置上的字符不同。我们在000和111之间划一条蓝分割线，111和000之间划一条红分割线，在变动过程中，我们可以发现，以下两个性质：111、每次变动相当于左/右移一条...
2019-01-27 21:23:25
511
原创 Ynoi 2017 由乃的OJ
由乃的OJ题目链接Solution首先很显然每一位计算的结果是独立的。先对树进行树链剖分，每一条重链维护一棵线段树，每个线段树区间维护两个数组(t0,t1)(t_0,t_1)(t0,t1)分别表示某个数某一位为0/10/10/1时经过这段区间的运算这一位会变成000还是111，这两个数组可以用两个unsigned long longunsigned\ long\ l...
2019-01-16 22:05:41
331
原创 5995. 【WC2019模拟2019.1.12】二分的代价
二分的代价Description给出一个长度为nnn的序列，每个位置的数值是一个111至999的整数，考虑一个建二叉树的过程：对区间[l,r][l,r][l,r]建树，选择一个数iii满足l≤i≤rl\leq i\leq rl≤i≤r，对[l,i−1][l,i-1][l,i−1]和[i+1,r][i+1,r][i+1,r]分别建树，令iii为这两棵树的父亲，定义[i,i−1][i,i-1][...
2019-01-12 17:15:10
448
原创 Codechef December Challenge 2018 Before Having Donuts
Before Having Donuts题目链接Solution考虑用一个垂直于zzz轴的平面与截这些甜甜圈，截得的图形是一些圆环的并，设f(x)f(x)f(x)表示过点(0,0,x)垂直于zzz轴的平面截得圆环的面积并，那么答案为∫f(x)dx\int f(x)dx∫f(x)dx。我们可以使用自适应辛普森积分去逼近答案。那现在的问题就是知道xxx，求f(x)f(x)f(x)，也就是求n...
2019-01-12 16:50:42
276
原创 Uoj #419. 【集训队作业2018】圆形
圆形Description题目链接Solution我们有格林公式我们需要求圆的面积并，就是求∫∫D1dxdy\int\int_D1dxdy∫∫D1dxdy我们令Q=x,P=−yQ=x,P=-yQ=x,P=−y，则我们有∫∫D1dxdy=12∮Lxdy−ydx\int\int_D1dxdy={1\over 2}\oint_Lxdy-ydx∫∫D1dxdy=21∮Lxdy−y...
2019-01-12 15:59:27
597
原创 Codeforces Hello 2019 F. Alex and a TV Show
Alex and a TV ShowDescription添加链接描述Solution设Fi(j)F_i(j)Fi(j)表示第iii个集合中，是jjj的倍数的数有多少个，我们对于每个集合只维护对应的FFF。现在考虑第三个操作，显然有Fx(j)=Fy(j)∗Fz(j)F_x(j)=F_y(j)*F_z(j)Fx(j)=Fy(j)∗Fz(j)现在考虑第二个操作，显然也有Fx(j)=...
2019-01-05 22:16:20
479
原创 Codechef Lucas Theorem
Lucas TheoremDescription原体面中文版体面Solution题目即让我们求多项式∏i=1n(x+i)\prod_{i=1}^n(x+i)∏i=1n(x+i)的非零系数项的个数。有一个很妙的结论是∏i=1p−1(x+i)≡xp−1−1 (mod p)\prod_{i=1}^{p-1}(x+i)≡x^{p-1}-1\ (mod\ p)∏i=1p−1...
2018-12-04 16:24:45
971
原创 JZOJ 5970 space
SpaceDescription一个四维空间中有n4n^4n4个点，每个点的每一维坐标都是整数，范围为[1,n][1,n][1,n]，接着给出四个nnn的排列A，B，C，DA，B，C，DA，B，C，D，一开始在(1,1,1,1)(1,1,1,1)(1,1,1,1)点，现在要遍历四维空间中所有的点，假设当前在点(x,y,z,h)(x,y,z,h)(x,y,z,h)，则从这个点去到(Ax,By,C...
2018-12-04 15:54:10
216
原创 JZOJ 5157 没有上司的舞会
没有上司的舞会Description一开始整棵树只有111号点，接下来每次动态添加一条树边，求每个时刻树的最大独立集。Data Constraintsn≤3∗105n \leq 3*10^5n≤3∗105Solution有lctlctlct维护。设fi,0/1,0/1f_{i,0/1,0/1}fi,0/1,0/1表示iii节点在splaysplaysplay所代表的区间中左端/右端...
2018-11-30 22:18:56
295
原创 JZOJ 5915 【NOIP2018模拟10.19】明日之星
明日之星Description有n个由‘A’、‘C’、‘G’、‘T’、‘U’五种字符组成的字符串s_i。第i个字符串还会有一个权值a_i。点与点之间连成了一棵无根树。给出q个询问，每次给出一个字符串S和两个整数u,v，对于树上u到v的路径上任意的点i，都会贡献a_i*(s_i在S中出现的次数)。同时有可能会有修改操作，修改a_i的权值。强制在线。Data Constrints1≤...
2018-10-21 21:43:00
502
原创 Codeforces 983 E . NN country
NN countryDescription有nnn个城市形成一棵树的形状。有mmm辆双向班车往返于两个城市（中途经过的城市都会停）。有qqq个人要从城市xxx到城市yyy，问最少坐几趟班车。如果到不了，输出−1-1−1。Data Constrints1≤n,m,q≤2∗1051\leq n,m,q \leq 2*10^51≤n,m,q≤2∗105Solution首先从城市xxx...
2018-10-21 11:29:58
475
原创 CSA Balanced Strings
Balanced StringsDescription对于一个仅由a,b,ca,b,ca,b,c组成的字符串SSS，我们称这个串是合法的当且仅当对于任意一个SSS的连续子串TTT，满足 |f(T,x)−f(T,y)|≤K ,∀{x,y}⊂{′a′,′b′,′c′}|f(T,x)−f(T,y)|≤K ,∀{x,y}⊂{′a′,′b′,′c′}|f(T,x)-f(T,...
2018-09-14 21:48:14
334
原创 CSA Empty Triangles
Empty TrianglesDescription给出第一象限上的MMM个固定点，接着给出KKK次询问，每次询问四个整数(x1,y1,x2,y2)(x1,y1,x2,y2)(x_1,y_1,x_2,y_2)表示询问以(0,0),(x1,y1),(x2,y2)(0,0),(x1,y1),(x2,y2)(0,0),(x_1,y_1),(x_2,y_2)为顶点的三角形内是否有固定点。Dat...
2018-09-13 19:47:24
262
原创 YALI联合训练 2018 9.12 Dream
DreamDescription有一个nnn个点mmm条边的有向图，第iii条边从uiuiu_i连向viviv_i，其权重为wiwiw_i，设iii号点出边的权重之和为sumwisumwisumw_i。 LF会从某个点出发，一条边被选中的概率为wisumwiwisumwi\frac{w_i}{sumw_i}，然后LF会沿着被选中的出边走向出边通向的点。 每条边的长度会随着时间t变化，具...
2018-09-13 12:23:18
224
原创 伯努利数与自然数幂和推导
伯努利数Ps.在本篇blogblogblog中[xn]F(x[xn]F(x[x^n]F(x)表示F(x)F(x)F(x)的第nnn项的系数。定义我们用生成函数法来定义伯努利数BnBnB_n xex−1=∑i≥0Bii!xixex−1=∑i≥0Bii!xi\frac{x}{e^x-1}=\sum_{i\geq0}\frac{B_i}{i!}x^i 换言之，就是xex−1xex−1\f...
2018-08-23 22:09:03
2444
原创 Codechef April Challenge 2018 Division 1 S Semi-palindromic
Semi-palindromicDescription对于一个不含前导000的十进制非负整数，如果它是mmm的倍数，且出现次数为奇数的某个数字最多只有一个（前导000不算），那么称它是牛逼数。 给定m,nm,nm,n ，求小于10n10n10^n的牛逼数有多少个，输出答案模109+7109+710^9+7 。Data Constraints1≤m≤161≤m≤161\leq ...
2018-06-06 14:24:14
308
原创 lct学习小记
前言lctlctlct是我一直以来都不想接触的数据结构，最近，我终于把这个大坑填上了。基本定义边分成两种，轻边和重边。重边构成的链为重链，重链可以只为一个点。 在lctlctlct中，用一棵splaysplaysplay维护一条重链上的点，对于每一条轻边，必定有一端是连向一条重链上深度最小的点的，我们将这条轻边的信息记录在该重链对应的splaysplaysplay的rootrootr...
2018-06-06 11:17:26
423
原创 JZOJ 5746 和
Description给定mmm和kkk，共TTT次询问，每次询问一个nnn，输出∑ni=1ik mod m∑i=1nik mod m\sum_{i=1}^ni^k\ mod\ m 数据保证mmm的最大值质因子不超过3∗1053∗1053*10^5。Data Constraints2≤n,m,k≤1018 1≤T≤3∗1032≤n,m...
2018-06-03 22:17:39
1338
原创 51Nod 1847 奇怪的数学题
奇怪的数学题传送门DescriptionSolution考虑枚举gcd。 Ans=∑d=1n(dminp(d))k∑j=1n∑k=1n[(j,k)=d]Ans=∑d=1n(dminp(d))k∑j=1n∑k=1n[(j,k)=d]Ans=\sum_{d=1}^n(\frac{d}{minp(d)})^k\sum_{j=1}^n\sum_{k=1}^n[(j,k)=d] ...
2018-05-22 22:48:10
531
原创 Libre OJ #6053.简单的函数
简单的函数传送门DescriptionData Constraintsn≤1010n≤1010n\leq10^{10}Solution
2018-05-22 16:32:45
586
原创 Min_25筛学习小记
前言听说大家都会了Min_25Min_25Min\_25或州阁筛了，虚的一批的我马上学了一下。Min_25筛首先这种筛法可以用来筛某种积性函数的前缀和，当然也不一定要积性函数，某些特殊的函数也能筛，时间复杂度O(n34log(n√))O(n34log(n))O(\frac{n^{\frac{3}{4}}}{log(\sqrt n)})，当然我并不会证。筛质数的函数值现有一函...
2018-05-22 15:48:32
1821
4
原创 第二类斯特林数与自然数幂和
一般求法一般求自然数幂和都会用到拉格朗日插值法，但仅当存在逆元的时候能用，给出一种用第二类斯特林数求自然数幂和的方法，时间复杂度是O(k2)O(k2)O(k^2)而不是O(k log k)O(k log k)O(k\ log\ k)的。F(x)=∑i≥0xii!∑j=1F{Fj}ij–F(x)=∑i≥0xii!∑j=1F{Fj}ij_F(x)=\...
2018-05-21 12:34:35
1469
1
原创 GDOI 2018 Day1 小学生图论题
小学生图论题Description有一个点数为n的竞赛图，每条边的的方向等概率随机。 现在给出m条有向链，表示每条链上的边的有向边的方向都已被钦定。 保证一个点不会出现在两条给出的链中。 求该竞赛图强连通分量的期望个数。（答案模998244353998244353998244353）Data Constrainsn,m≤105n,m≤105n,m\leq 10^5...
2018-05-14 21:38:22
561
原创 GDSOI 2018 Day3 基地
基地Description有一棵点数为nnn的树，111号节点为根节点，对于剩下的任意节点xxx他的父亲为⌊x2⌋⌊x2⌋\lfloor\frac{x}{2} \rfloor,同时给出三个常数a,b,ca,b,ca,b,c，xxx到它父亲的道路长度为ax2+bx+cax2+bx+cax^2+bx+c，接下来有mmm轮操作，每次操作会删除一颗子树，每个操作后，需要回答两个询问，1、找到一...
2018-05-14 12:20:35
476
原创 GDOI2018 ？？记
前言已经好久没打这种比赛总结了。 这次比赛真的speechless了，本来以为可以被卡卡校线的，结果连前14都没进，果然还是我太naive了吗…… Day0领个参赛证，领个袋子，领个黄衣服，回家养生，晚上太紧张没睡好。Day1开场前打了个FFT，竟还没调出来，心态崩了 一开场用点时间看完了题目，t3一眼水题二维数据结构直接切，但还是想先打第一题，于是便用了5分钟想...
2018-05-03 16:16:03
649
3
原创 JZOJ 5680 绝对伏特加
Description进行nn轮随机数生成，每轮的数值在[11,KK]中随机出现。记aia_i表示nn轮投掷中，数值ii出现的次数，求(ΠLi=1ai)F(\Pi_{i=1}^La_i)^F的期望。答案对20032003取模。Solution0≤n,K≤1090≤n,K≤10^9 ,0<F≤1030<F≤10^3,0<L∗F≤500000<L∗F≤50000,L≤KL≤KSolution先把每个数被
2018-04-27 14:51:17
457
原创 Codeforces 891E Lust
Description给出一个长度为nn的数组aa，有一个计数器resres，接下来进行kk次操作，每次操作等概率的选择[1,n][1,n]中的某个数ii，然后resres加上∑j≠iaj\sum_{j\neq i}a_j，然后ai=ai−1a_i=a_i-1，求resres的期望值模109+710^9+7。Data Constraint2≤n≤5000 0≤ai,k≤1092≤n≤5000\
2018-04-23 22:33:39
422
原创 JZOJ 5662 尺树寸泓
Description给出一棵有nn个节点的二叉树，每个点都有一个点值wiw_i，定义一个节点的力量值为以该点为根的子树内的所有点的点值之和，接下来qq个曹作，分两种一个询问曹作，询问一个节点子树内的所有节点的力量值的积模109+710^9+7，或是旋转曹作，左旋/佑旋某个节点，如果旋转不了，请忽略这条曹作。Data Constraintn,q<=105n,q<=10^5 0<wi<109+70<w
2018-04-23 21:57:46
336
原创 JZOJ 5669 排列
Description有nn个数x1x_1~xnx_n 。它们的一个排列，满足mm个条件，每个条件(aa,bb)表示xax_a必须在xbx_b之前。求这个排列可能的最大子段和。Data Constraintn<=500，m<=1000，|xi|<=1000 n<=500，m<=1000，|x_i|<=1000 Solution首先把每个条件(a,b)(a,b)看成有向边(a,b)(a,b)，那么对于
2018-04-23 21:38:28
259
原创 JZOJ 5682 数字
Description两个数字xx和yy，它们需要满足x∨y=Tx∨y=T，且Lx≤x≤RxLx≤x≤Rx ,Ly≤y≤RyLy≤y≤Ry，求x∧yx∧y有多少种可能的不同的取值。Data Constraint0<=T,Lx,Rx,Ly,Ry<2610<=T,Lx,Rx,Ly,Ry<2^{61}CodePs.没开long long炸剩暴力分。 先考虑一下如果没有上下界的限制，那答案为显然为2bit
2018-04-23 16:10:30
380
原创 JZOJ 5612 T3
Description有个人要从(00,00)走到(nn,mm)，假设他现在在(xx,yy)，那么他可以走到(xx+11,yy+11),(xx+11,yy-11)或(xx+22,yy)，求方案数模100003。Data Constraintn,mn,m<=101810^{18}Solution首先变换坐标系，逆时针旋转45度，则原题目变成，每次可以从(xx,yy)走到(xx,y+1y+1)、(x+1
2018-04-23 15:28:02
222
原创 JZOJ 5630 Connection
ConnectionDescription给定一张NN个点MM条边的连通无向图，问最少需要断开多少条边使得这张图不再连通。Data ConstraintNN<=300300,MM<=10001000Solution题目要求求出无向图的最小割，我们无法知道哪一个点在SS集，哪个在TT集，我们强行规定某个点在SS集，那么一定有一个点在TT集，枚举nn-11次汇点跑网络流即可。时间复杂度O(?n)O(?n
2018-04-11 16:42:55
245
原创 JZOJ 5623 program
program对于一个仅有<、>、0~9组成字符串，执行一种操作，一开始指针在开头位置，指针移动方向默认为向右移，当遇到<或>，指针移动方向就要对应的修改成向左或向右。 当连续遇到两个非数字字符时，便要删掉前一个<或>。 若遇到了一个数字，便将此数打印出来，并将其数字-1，当发现一个数字在打印之前为0，打印后便将其删掉。 若指针移到了字符串外，结束整个过程。现在给出一个长度为nn的仅有<、>、
2018-04-11 16:30:18
222
原创 UOJ 【UR #12】密码锁
密码锁Descriptionhttp://uoj.ac/problem/181Data Constraint11≤nn≤3838, 00≤mm≤1919,00≤wiw_i≤10410^4Solution由于定向后原图是一个竞赛图，进行强连通分量缩点后，一定是一个拓扑序唯一的DAGDAG，此DAGDAG的点数的期望值就是答案。不难发现，此DAGDAG可以分成两个集合SS,TT使得SS和TT之间的所有连
2018-04-11 15:27:06
499
原创 JZOJ 5603 Xjz
Xjz Description给定字符串SS和TT。 串AA和串BB匹配的定义改为：存在一个字符的映射，使得AA应用这个映射之后等于BB，且这个映射必须为一个排列。 AA=121121,B=313 B=313，当映射f为{1->3, 2->1, 3->2}时f(A)=Bf(A)=B,可以匹配 求SS有多少个子串与TT匹配。Data Constraint|S|,|T|≤106|S|,|T|≤10
2018-03-30 22:49:28
264
原创 JZOJ 5608 Subset
SubsetDescription给出三个11到nn的排列aa,bb,cc。 称三元组（xx,yy,zz）是合法的当且仅当存在一个下标集合S⊆[n]S\subseteq[n]满足 (x,y,z)=(maxi⊆Sai,maxi⊆Sbi,maxi⊆Sci)(x,y,z)=(max_{i\subseteq S}a_i,max_{i\subseteq S}b_i,max_{i\subseteq S}c_
2018-03-22 22:33:13
332
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人