1 jay_zai

尚未进行身份认证

我要认证

人群淹没,你我不及诉说。一声雁过,往事如昨。只望离别不多,再赏盛世烟火。

等级
TA的排名 16w+

讲讲分块算法 题目Lucas的数列

DescriptionInputOutputSample Input5 51 22 33 44 55 61 2 41 3 01 5 31 5 25 5 0Sample Output1empty61emptyData Constraintsolution先说一下题意,给定一个a数组,每次询问l到r之间复杂度不大于z的方差。20分做法直接模拟?嗯没错,但是一不小心还是会wa为什么呢,由于题目的数据过于**,注意到n方乘t方小于等于1e18,这说明当n十

2020-08-06 20:23:56

最近的题目总结(树,电话线铺设,我的天)

总结树solution电话线铺设Descriptioninputoutput数据solution我的天solution几天没打博客了,现在记录一下一些比较好的题目。树Description有n个点,它们从1到n进行标号,第i个点的限制为度数不能超过A[i].现在对于每个s (1 <= s <= n),问从这n个点中选出一些点组成大小为s的有标号无根树的方案数。n<=100样例是32 2 1答案3 3 2solution这一类的题目一般都会用到prufer编码,

2020-08-05 22:15:33

手打堆

手打堆很多地方都要用到堆,但是优先队列有点慢,常数比较大让人有点反感,而且比较难搞,所以还不如手打呢。所以就手打堆了。这里打的是套结构体里的,应该打的还可以吧,挺简练的吧?这个打的是堆排序模板#include<cstdio>#include<algorithm> using namespace std;int n,a[200010];struct node{ int q[200010],len; bool empty(){return len==0?1:0;}/

2020-08-05 18:41:45

8.3总结T1prime T2Isfind T3Divide T4直径

2020.08.03【NOIP提高组】模拟赛时先看第一题,一看prime题目还有点激动,以为是道有点意思的题目,结果只是让一堆数,互质的分组然后问最小分的组数以及最小的最大组的大小,一看感觉是dp,再看n<=15,逆向思维猜测出题人就是想让暴力,旁边的yyh大佬一看到就上手感觉很不妙。但是自己暴力水准低所以先放着。看到T2,给个模式串和一堆匹配串询问是否为子序列,一看还以为AC自动机?结果发现是子序列不是匹配,哦哦,然后看看数据显然的淼法是肯定不行的,然后想着快速求答案,一看匹配串总和才400万

2020-08-03 19:17:59

装饰大楼,备用钥匙,IOIOI卡片占卜总结

2020.07.30【NOIP提高组】模拟总结T1装饰大楼DescriptionInputOutputSample InputSample OutputData ConstraintT2备用钥匙DescriptionInputOutputSample InputSample OutputData Constraint正解T3IOIOI卡片占卜DescriptionInputOutputSample InputSample Output正解总结T1装饰大楼Description国际信息学奥林匹克竞赛将要

2020-07-30 20:53:13

最近的比赛总结

文章目录7.28【NOIP提高组】模拟赛时总结T1:DescriptionInputOutputSample InputcopypasteSample OutputData Constraint正解T2:DescriptionInputOutputSample InputSample OutputData Constraint正解T3:DescriptionT4:DescriptionInputOutputSample InputSample OutputData Constraint正解:7.29【NOI

2020-07-30 20:10:28

2020.7.27T4花花的聚会(jz暑假训练day11)

DescriptionInputOutputSample Input7 73 12 17 66 35 34 37 2 37 1 12 3 53 6 24 2 45 3 106 1 203567Sample Output10225Data ConstraintHint赛时考虑一个部分分的dp,然后空间竟然爆掉了!!!结果40分正解(呸 )一坨大佬暴力解决???加个小小剪枝?(if(当前答案>ans)return)然后水题开始#

2020-07-27 19:21:30

2020.7.27T3计算几何 (jz暑假训练day11)

DescriptionInput OutputSample Input34 5 33 5 421 13 3Sample Output03Data ConstraintHint正解首先这个线段的连接方式就是最小的y连最小的x这样一直连,之后我们看对于两个线段如何判断是否香蕉呢?假设询问的点是xx,yy,另个线段的纵坐标是y,横坐标是x,我们可以按照另一个线段的斜率求出yy此时应对应的横坐标,但是由于另个线段是由左上角到右下角的,所以此刻求出来的值应减去x,然后判断是否大

2020-07-27 19:09:37

2020.7.27T2走路(jz暑假训练day11)

DescriptionInputOutputSample Input33 2 44 3 43 6 4Sample Output2 2 2Data ConstraintHint一个人在t[i]之前不存在, 在走到f[i]之后消失.这个题n方做法就行了,然后说一下自己的做法,当我们要判断i与j是否能打招呼时,先让时间短的补到时间长的,这时将现在到达的位置计算一下,若超出了目的地,显然不合法。之后若没超出,判断是否等于另一个的起始点,等于就合法。最后若不在一个点上,那么同一个方向

2020-07-27 19:02:00

2020.7.27T1中位数(jz暑假训练day11)

DescriptionInputOutputSample Input50 1 0 1 0Sample Output20 0 0 0 0Data Constraint赛时直接枚举,预测应该能混个4,50吧?结果80分正解我们可以考虑怎么求出每个位置的变化次数.不难发现, 如果 ai−1 和 ai+1 中有至少一个和 ai 相同, 那么 ai 就不会变.因此, 会变的只能是 01010101 · · · 或者 10101010 · · · 这样的连续段. 而这样的连续段的变

2020-07-27 18:54:37

2020.7.25T2魔道研究(jz暑假训练day10)

Description“我希望能使用更多的魔法。不对,是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。”——《The Grimoire of Marisa》雾雨魔理沙魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。最开始的时候,魔理沙只是一本一本地进行研究。然而在符卡战中,魔理沙还是战不过帕秋莉。好在魔理沙对自己的借还和研究结果进行了记录,从而发现了那些魔导书的精妙之处。帕秋莉的那些魔导书,每本都有一个类别编号ti 和威力大小pi。而想要获得最

2020-07-27 18:37:08

2020.7.25T1挑竹签(jz暑假训练day10)

题目大意挑竹签——小时候的游戏夏夜,早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。挑竹签,就是在桌上摆上一把竹签,每次从最上层挑走一根竹签。如果动了其他的竹签,就要换对手来挑。在所有的竹签都被挑走之后,谁挑走的竹签总数多,谁就胜了。身为神明的诹访子自然会让早苗先手。为了获胜,早苗现在的问题是,在诹访子出手之前最多能挑走多少竹签呢?为了简化问题,我们假设当且仅当挑最上层的竹签不会动到其他竹签。一个拓扑排序就搞定了#include<cstdio>#include<queue&

2020-07-27 18:31:56

网络流dinic算法

网络流dinic算法转载https://www.cnblogs.com/SYCstudio/p/7260613.html

2020-07-24 16:10:15

2020.7.24 T3终章-剑之魂(jz暑假训练day9)

Description【背景介绍】古堡,暗鸦,斜阳,和深渊……等了三年,我独自一人,终于来到了这里……“终焉的试炼吗?就在这里吗?”我自言自语道。“终焉的试炼啊!就在这里啊!”我再一次自言自语道。“这背后可能有那个东西吗?”我自言自语道。“这背后一定有那个东西呢!”我又一次自言自语道。我沉默着,踏上黑漆漆的索桥,小心翼翼地,拿出锋利的注入我灵魂的双剑……“那么,我们开始吧……”我最后一次自言自语道。【题目描述】My soul of my sowrd!终焉的试炼即将到来,作为一名有修养

2020-07-24 16:01:55

2020.7.24 T2圣章-精灵使的魔法语 (jz暑假训练day9)

Description【背景介绍】“魔法???算了吧,这种东西我肯定学不了的啦!”明明是个剑士,却被眼前这位洋洋自得的精灵使——弗洛莉拖出去学魔法,真是个没事找茬的家伙……“没事啦。作为一名冒险者会发生很多情况,中毒啦,受伤啦,被咒语束缚之类的,没有魔法就很难办的呀!”她到是好像一副什么都懂的样子,真是令人火大。“都说我是个人类了,魔法这种东西学起来很困难的吧!”我只好找个看似靠谱的借口。然而,她那不屈不挠的声音又响了起来:“人类虽然与自然的共鸣,也就是魔法的连接较少,但如果认真训练的话还是可以做

2020-07-24 15:59:03

2020.7.24 T1序章-弗兰德的秘密 (jz暑假训练day9)

Description背景介绍弗兰德,我不知道这个地方对我意味着什么。这里是一切开始的地方。3年前,还是个什么都没见过的少年,来到弗兰德的树下,走进了封闭的密室,扭动的封尘已久机关,在石板上知道了这个世界最角落的最阴暗的东西。那种事情,从未忘怀,从未动摇,我还记得,那一天,我,里修,第一次拔起了剑……弗兰德的密室里,机关上方画着两棵树的字样,机关下方是一个有数字的刻度……弗兰德最高的两棵树,只要知道两棵树的共同的相似度就行了……给定两棵有根树,可以任意删除两棵树上的节点(删除一棵节点必须保证该节点

2020-07-24 15:56:07

2020.7.23 T3小X的佛光 (jz暑假训练day8)

题目大意给个树,每次询问给出3个点a,b,c,询问a到b的路径与b到c的路径之间重合的点的个数正解lca不多说啥了,统计答案就是分类讨论咯(这里本人似乎讨论的重复些,读者也可以有自己的方法,所以本人自己的方法也便不解释了),另外这题卡栈(就是说dfs(递归)是系统存储的,这道题递归的太深导致系统的存储空间爆掉了),所以要打人工栈(也就是bfs)#include<cstdio>#include<iostream>#include<cmath>#define N

2020-07-24 15:50:38

2020.7.23 T2数列 (jz暑假训练day8)

题目大意有个数列a[i],让其重新排列使得a[i]*a[i+1] (i=1~n-1)求和最大,之后输出重新排列后的编号,要求字典序最小。正解这个题是真的烦人,代码也很繁琐,就粗略看看吧。然后具体是贪心做法,假如没有重复的,那么显然是头放最小,尾放次小,头再放此次小,这样。(注意考虑字典序,也就是考虑是头放最小还是次小)之后假如有重复的,就自行讨论一下。如果这个数出现的次数>=2,那么这个数必定会放入待解决数列头和待解决数列尾。而取决于放多少个进待解决数列头,取决于,他后面的前两个数的最前位

2020-07-24 15:45:01

2020.7.23 T1同余(jz暑假训练day8)

DescriptionInputOutputSample Input21 1 5 10032 0 7 72 2Sample Output160Data Constraint正解dp,对于c,可以发现c在1至p-1之间时方案个数是一样的,所以c为多少不用考虑,只要判断是否为0就行了,然后我们设d[i][1]表示不是0的个数,d[i][0]表示是0的个数,然后d[i][1]=p-1^a[i]-1 d[i][0]就是总共的(p^a[i])-不是0的个数(p-1 ^ a[i]),

2020-07-24 15:32:35

2020.7.22 T3押韵(jz暑假训练day7)

Description小A非常喜欢所有押韵的东西,他认为两个单词押韵当且仅当他们的公共后缀的长度和两个单词中最长的单词的长度相等,或者是最长的单词的长度减一。也就是说LCS(A,B)>=max(|A|,|B|)-1。有一天,小A读了一个有N个单词的小故事,他想知道,如果挑选一些故事里出现的单词组成一个新的单词序列,能组成的最长的满足以下条件的单词序列的长度是多少:单词序列中任意相邻的两个单词都押韵。(每个单词最多只能用一次)Input第一行包含一个正整数N(1<=N<=500000

2020-07-22 21:25:55

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。