5 olahiuj

尚未进行身份认证

我的女朋友不抽烟不喝酒不傲娇不化妆不存在

等级
博文 1k+
排名 1k+

GDSOI2019 退役记

小小的总结一下由于这大概是除了noip2020之外最后一场正式赛了,因此总结放在前面吧搁鸽了很久都没什么想写的欲望,但是总觉得还是得对我漫长但并不出彩的oi生涯有个交代嘛,于是还是写了这样一篇漫长同样不精彩的流水账,权当是练习语文作文凑字数了非要总结的话,大概就是没打出自己的水平吧。看了一下排名貌似很多人都挂了,再加上只有两天于是很多大爷级别的人物都没有进队。。不过对于我没进队这一事实我还...

2019-05-13 22:16:29

bzoj5384 有趣的字符串题 回文树+树状数组+离线

Description给一个长度为n的字符串,m次询问(l,r)求l到r内本质不同的回文子串数量Solution老年选手复习回文树。。考虑暴力怎么写。我们离线询问按照r排序,每次在回文树上暴力跳fail统计以r为结尾的新增回文串。注意到每一个回文串影响的左端点是一个区间,那么我们用树状数组区间加就可以了。这样做是O(n^2logn)的有一个小结论就是,所有以r为结尾的回文串的长度一定...

2019-04-30 09:14:08

loj #3088 「GXOI / GZOI2019」旧词 离线+树链剖分

Descriptionn个节点的树,m次询问(x,y)求∑i=1x(dep[lca(i,y)])k\sum_{i=1}^x{{\left(dep[lca\left(i,y\right)]\right)}^k}i=1∑x​(dep[lca(i,y)])k其中k是一个给定的常数Solution观察k=1的时候要怎么做。我们离线按x排序,对于一个节点t把根到t路径上的所有点全部+1。那么y...

2019-04-28 17:18:01

loj #3085 「GXOI / GZOI2019」特技飞行 扫描线+树状数组+计算几何

Description太长了自己看。。。Solution强行题套题,真·GDOI模拟首先可以发现A和B操作都不会影响交点的位置,那么C的贡献就是固定的了。这个可以先求出交点然后转换坐标系二维数点,离线拆分扫描线+树状数组就行了。因为有可能是实数所以离散不太好写考虑什么时候能交换就交换。注意到一次相交意味着二者在最后会交换顺序,因此每个交点都做一次A恰好能满足初始相对顺序,且在A&gt...

2019-04-24 19:49:33

AtCoder Regular Contest 098 题解

C-Attentionsb题,我们前缀后缀和一下直接O(N)算贡献就可以了#include<stdio.h>#include<string.h>#include<algorithm>#definerep(i,st,ed)for(inti=st;i<=ed;++i)constintINF=0x3f3f3f3f;con...

2019-04-22 21:58:08

AtCoder Regular Contest 097 题解

CK-thSubstringk才5,随便做都行。当然也可以SAM求第k大#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<string>#definerep(i,st,ed)for(int...

2019-04-22 15:06:16

AtCoder Regular Contest 102F Revenge of BBuBBBlesort! 乱搞

Description给一个n排列p[],若存在一个位置i使得p[i-1]>p[i]>p[i+1],那么就可以交换p[i-1]和p[i+1]Solution真·感性乱搞+分类讨论首先记a[i]=[p[i]=i],那么我们可以把p分成若干段01交替出现、首尾皆为0的子串。由交换性质可知这些段之间互不影响,即交换不会跨过这些段考虑一整段[l,r]什么情况会No。如果出现了最...

2019-04-21 21:31:54

AtCoder Regular Contest 102 E Stop. Otherwise... 组合数学

Description有n个k面骰子。对于i=2…2k,问存在多少种扔骰子的方案使得最终结果不存在两个骰子之和恰好等于i我们认为所有骰子是一样的n,m≤2000n,m\le2000n,m≤2000Solution首先肯定要枚举这个i我们发现有些数字是可以随便出现的,其余的数j一定对应了一个数i-j表示它们不能同时出现并且可以知道当且仅当i为偶数的时候存在一个(i/2,i/2)的对...

2019-04-21 20:40:28

loj#6495「雅礼集训 2018 Day1」树 dp

Description定义生成一棵树的方式:对于节点i从[1,i-1]随机一个父亲。求这棵树的期望高度n≤24n\le24n≤24Solution设f[i,j]表示i个节点高度为j的方案数。注意到2的父亲一定是1,我们可以枚举2为根的子树的情况,然后讨论一下能否成为最大值就行了转移看代码。。Code#include<stdio.h>#include<st...

2019-04-19 10:40:16

loj#6030 「雅礼集训 2017 Day1」矩阵 贪心

Description给一个n*n的01矩阵,每次可以用一行替换一列。问最少多少次操作使得整个矩阵全1n<=1000Solution先考虑怎么把一整行刷成1。我们枚举全1的行设为x,若存在第x列为1的行则可以填上第x行的0,否则我们可以多操作一次任意选一个存在1的行使得某行的第x列为1,然后照做就行了Code#include<stdio.h>#include...

2019-04-18 20:15:35

jzoj6133 [NOI2019模拟2019.4.18]商店 线段树模拟费用流

DescriptionN,M≤3e6N,M\le3e6N,M≤3e6Solution求dfs序的时候爆栈了QUQ考虑人和商品建点跑费用流,优化一下可能可以跑1e5?观察我们费用流实际上在干什么,就是从一个子树内选出最大的权值然后把它取反。那么我们可以用线段树维护dfs序区间最大值来搞这个东西。由于直接做没法退流因此需要按照dfs序降序贪心考虑到时限只有1s,nlogn要跑3e6,我...

2019-04-18 15:34:37

CF961G Partitions 组合数学

Description有n个带权物品,要把它们分成k个集合定义一个分法的权值为每个集合的大小*集合内权值之和问所有分法权值之和Solution一开始没看到要乘上一个集合大小。。以为是sb题讲一个头铁娃的做法显然每个物品对答案贡献的系数都是一样的。考虑枚举一个物品所在集合的大小s,那么有∑s=1ns(n−1s−1){n−sk−1}\sum_{s=1}^{n}{s\binom{n-...

2019-04-17 18:27:14

CS Academy Round 75 Permutations NTT

Descriptionq次询问(x,y),求长度为n的排列p[],满足p[y]是前y个中最大的,且p[x]*2<p[y]的数量Solution考虑枚举第y位选了啥,那么第x位的范围就出来了,于是答案就是f(y)=∑i=1n⌊i−12⌋(i−2y−2)(y−2)!(n−y)!f(y)=\sum_{i=1}^n{\lfloor\frac{i-1}{2}\rfloor\binom{i-2...

2019-04-17 12:28:48

洛谷P4233 射命丸文的笔记 分治NTT+竞赛图

Description给定n对于i从1~n,输出i个点组成竞赛图中,哈密顿回路的平均数量Solution竞赛图存在哈密顿回路的充要条件就是强连通设f(n)f(n)f(n)表示n个点形成强连通竞赛图的方案数,一个简单的容斥就是f(n)=2(n2)−∑i=1n−1(ni)f(i)2(n−i2)f(n)=2^{\binom{n}{2}}-\sum_{i=1}^{n-1}{\binom{n}...

2019-04-16 21:51:30

uoj#213 [UNR #1]争夺圣杯 单调栈+差分

Description给一个长度为n的序列,定义一个区间的权值为区间内最大值。记ans[i]表示长度为i的所有区间权值之和膜998244353问ans的异或和n≤1e6n\le1e6n≤1e6Solution考虑求出元素i作为最大值的区间[L[i],R[i]],记左右区间中较短的为mn,较长的为mx。我们讨论一下对于各个长度的区间这个位置的贡献是啥当x<=mn时,区间至少要包...

2019-04-16 20:45:56

CF555E Case of Computer Network 边双连通分量+树上差分

Description有一个n个点m条边的无向图,q个限制形如(x,y)。问能否找到一种给边定向的方式使得满足所有的限制可以从x到达ySolution复习一下图论的一些东西一个边双内的点肯定可以定成内部互达的情况。缩完边双之后就可以得到一个森林,我们用打标记的方式在这个森林上乱搞就可以知道是否存在两个限制它们产生了冲突。Code#include<stdio.h>#...

2019-04-16 15:08:26

loj#2562 「SDOI2018」战略游戏 圆方树+虚树

Description给一个无向连通图,多次询问一个点集S,问去掉哪些点后S集合不连通,S中的点显然不能算。n≤2∗105,  ∑∣S∣≤2∗105n\le2*10^5,\;\sum{|S|}\le2*10^5n≤2∗105,∑∣S∣≤2∗105Solution会破坏连通性的点容易发现就是建好圆方树后的圆点我们把S集的虚树搞出来,求一下这个虚树内部有多...

2019-04-16 10:47:11

hdu6036 Division Game 容斥+组合数学+NTT

Description有0~k-1共k束花,每一束花中有m种颜色的花,第i种颜色有e[i]朵第x次操作将会从第x%k束花中摘走至少一朵花,当一朵花被摘完游戏结束对于i=0~k-1输出游戏在第i个位置恰好结束的方案数Solution每次至少摘一朵,那么游戏至多进行n=∑i=1mein=\sum_{i=1}^{m}e_in=∑i=1m​ei​轮设f(x)f(x)f(x)表示在某个位置第...

2019-04-15 22:06:01

bzoj5217 [Lydsy2017省队十连测] 航海舰队 FFT+bfs

Description有一个矩阵,有的位置有障碍现在有一些关键点,每次这些关键点可以朝同一个方向同时走一步,要求任意关键点不能走到障碍上。问多少个点是可达的n,m≤700n,m\le700n,m≤700Solution30分非常好写,只需要暴力bfs就可以了,字面意义上的暴力60分就是记录左上角,然后二维前缀和一下bfs先把包含关键点的最小矩阵抠出来,关键点移动就可以看成矩阵平移...

2019-04-15 19:09:24

bzoj5219 [Lydsy2017省队十连测]最长路径 容斥+dp

Description给定n和p对于i从1到n,求n个点形成的,从1出发最长路恰好为i的竞赛图数量,对p取模n≤2000n\le2000n≤2000Solution由一些小常识可以知道,竞赛图一定存在一条哈密顿路径,且强连通分量缩点之后形成的,一定是一条若干scc形成的链,拓扑序小的scc向后连满边也就是说,1为起点的最长路,一定是从1出发,向后走完所有scc。所以最长路=n-[1...

2019-04-15 15:37:29
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。