- 博客(67)
- 收藏
- 关注
RSS订阅原创 GDOI省选游记
前言作为一个初二的小蒟蒻，我竟有幸参加人生中第一次省选，实属幸运。所以今天（4.9）便开始了这篇游记。无论结果如何（反正肯定进不了队）我都会努力把这篇游记完成，算是对自己的一个答复。day -？从上周二开始停课，停到周四，也便是昨天，然后回家收拾东西，今天中午到jz集合走人。清明节的一天假期被xc吃掉了，但是好处是周四下午一结束就比（fang）赛（jia）了。期间的训练被爆踩。明明只有提高a的水平，硬是去打省选组（因为只有省选组）每天根本切不动题目。周三周四的题目还纷纷爆零。真是不利啊。由于
2021-04-12 20:04:37
408
2
原创 GDKOI提高组总结——三天划（bao）水（zha）记
话前31号下午题解听不懂选择打总结，主要是今天下午就放假了，回家就不一定打了（话说好久没有打博客了）由于疫情GDKOI就是线上赛了，在jz度过的，不是特别爽，但是1600变成450良心了许多——个屁。若有人看过讲题那大概知道是为什么了。另外还有许多有意思的事情。接下来讲。day-3这天普及组开始了，虽然没有报名但是x姓老师让我们这些蒟蒻去303打，哦原来不交钱也可以打比赛啊，jz（高嘉煊，曹天佑）的派头就是足（我感觉自己赚了，GDKOI：你感觉你赚了，但是我永远不亏）开始看题T1：脑瘫题
2021-01-31 16:50:26
411
3
原创 noip游记
这是第一次noip，期望不要像csp2019爆0Day-9这天开始，是我至今为止第一次停课，将要停一周半，感觉是十分兴奋的，至于文化课心想回去水水就行了（结果回来以后发现作业根本补不动，不做又感觉亏了，很烦）Day-8来jz是真的舒服，地好饭好而且随心所欲，不用6：10起床，结果这天就睡到9点钟，模拟赛少打了1h，幸好不算炸。。。Day ?<0时间过得很快，模拟赛越来越难，每天就几十分，改题也改不动，愿rp++Day0这天没有比赛，消化题目，但是能做的都做了，不会的也改不出来，上午水了
2020-12-11 20:26:05
322
原创 csp2020提高组总结
好久没有写博客了，咕咕咕……赛前考试这周期中考试，自认为考的不错，于是周五考完试回家水了水题，当练练手感。赛时上午打完普及组T3暴力没打出来，感觉有些凉凉，T4也是n^3的，270左右，不过也没觉得什么，心态还好。然后中午突然想到对拍没有复习，又没有电子设备，有点小慌。进场前发现普及T1 2的幂只开到22，心想完了。。。普及可能连一等都没了。但也不管了，认真搞好提高组。看到题，T1题面很长，发现是一道算数题，感觉细节较多，先看了后面。T2一看就想到思路了，之后看了看T3亿眼弃疗，T4貌似博弈？
2020-11-11 19:37:24
1480
原创 讲讲分块算法 题目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
332
4
原创 最近的题目总结（树，电话线铺设，我的天）
总结树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
170
原创 手打堆
手打堆很多地方都要用到堆，但是优先队列有点慢，常数比较大让人有点反感，而且比较难搞，所以还不如手打呢。所以就手打堆了。这里打的是套结构体里的，应该打的还可以吧，挺简练的吧？这个打的是堆排序模板#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
212
原创 8.3总结T1prime T2Isfind T3Divide T4直径
2020.08.03【NOIP提高组】模拟赛时先看第一题，一看prime题目还有点激动，以为是道有点意思的题目，结果只是让一堆数，互质的分组然后问最小分的组数以及最小的最大组的大小，一看感觉是dp，再看n<=15，逆向思维猜测出题人就是想让暴力，旁边的yyh大佬一看到就上手感觉很不妙。但是自己暴力水准低所以先放着。看到T2，给个模式串和一堆匹配串询问是否为子序列，一看还以为AC自动机？结果发现是子序列不是匹配，哦哦，然后看看数据显然的淼法是肯定不行的，然后想着快速求答案，一看匹配串总和才400万
2020-08-03 19:17:59
139
原创 装饰大楼，备用钥匙，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
389
原创 最近的比赛总结
文章目录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
243
原创 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
349
原创 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
163
原创 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
105
原创 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
129
原创 2020.7.25T2魔道研究（jz暑假训练day10）
Description“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。”——《The Grimoire of Marisa》雾雨魔理沙魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理沙还是战不过帕秋莉。好在魔理沙对自己的借还和研究结果进行了记录，从而发现了那些魔导书的精妙之处。帕秋莉的那些魔导书，每本都有一个类别编号ti 和威力大小pi。而想要获得最
2020-07-27 18:37:08
150
原创 2020.7.25T1挑竹签（jz暑假训练day10）
题目大意挑竹签——小时候的游戏夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。一个拓扑排序就搞定了#include<cstdio>#include<queue&
2020-07-27 18:31:56
99
原创 2020.7.24 T3终章-剑之魂（jz暑假训练day9）
Description【背景介绍】古堡，暗鸦，斜阳，和深渊……等了三年，我独自一人，终于来到了这里……“终焉的试炼吗？就在这里吗？”我自言自语道。“终焉的试炼啊！就在这里啊！”我再一次自言自语道。“这背后可能有那个东西吗？”我自言自语道。“这背后一定有那个东西呢！”我又一次自言自语道。我沉默着，踏上黑漆漆的索桥，小心翼翼地，拿出锋利的注入我灵魂的双剑……“那么，我们开始吧……”我最后一次自言自语道。【题目描述】My soul of my sowrd!终焉的试炼即将到来，作为一名有修养
2020-07-24 16:01:55
125
原创 2020.7.24 T2圣章-精灵使的魔法语 （jz暑假训练day9）
Description【背景介绍】“魔法？？？算了吧，这种东西我肯定学不了的啦！”明明是个剑士，却被眼前这位洋洋自得的精灵使——弗洛莉拖出去学魔法，真是个没事找茬的家伙……“没事啦。作为一名冒险者会发生很多情况，中毒啦，受伤啦，被咒语束缚之类的，没有魔法就很难办的呀！”她到是好像一副什么都懂的样子，真是令人火大。“都说我是个人类了，魔法这种东西学起来很困难的吧！”我只好找个看似靠谱的借口。然而，她那不屈不挠的声音又响了起来：“人类虽然与自然的共鸣，也就是魔法的连接较少，但如果认真训练的话还是可以做
2020-07-24 15:59:03
110
原创 2020.7.24 T1序章-弗兰德的秘密 （jz暑假训练day9）
Description背景介绍弗兰德，我不知道这个地方对我意味着什么。这里是一切开始的地方。3年前，还是个什么都没见过的少年，来到弗兰德的树下，走进了封闭的密室，扭动的封尘已久机关，在石板上知道了这个世界最角落的最阴暗的东西。那种事情，从未忘怀，从未动摇，我还记得，那一天，我，里修，第一次拔起了剑……弗兰德的密室里，机关上方画着两棵树的字样，机关下方是一个有数字的刻度……弗兰德最高的两棵树，只要知道两棵树的共同的相似度就行了……给定两棵有根树，可以任意删除两棵树上的节点（删除一棵节点必须保证该节点
2020-07-24 15:56:07
145
原创 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
130
原创 2020.7.23 T2数列 （jz暑假训练day8）
题目大意有个数列a[i]，让其重新排列使得a[i]*a[i+1] (i=1~n-1)求和最大，之后输出重新排列后的编号，要求字典序最小。正解这个题是真的烦人，代码也很繁琐，就粗略看看吧。然后具体是贪心做法，假如没有重复的，那么显然是头放最小，尾放次小，头再放此次小，这样。（注意考虑字典序，也就是考虑是头放最小还是次小）之后假如有重复的，就自行讨论一下。如果这个数出现的次数>=2，那么这个数必定会放入待解决数列头和待解决数列尾。而取决于放多少个进待解决数列头，取决于，他后面的前两个数的最前位
2020-07-24 15:45:01
125
原创 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
107
原创 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
270
原创 2020.7.22 T2网格图游戏（jz暑假训练day7）
DescriptionInputOutputSample Input3 42 1 E 1 2 N2 1 N 1 1 N3 1 N 2 1 N2 2 N 1 1 NSample OutputYESYESNONO赛时暴力40分正解并查集，首先提一下这个题是强制在线啊，给你的两个路有一个是没有用的，看起来很绕，其实就是根据上一次的答案来确定这一次的查询。然后呢我们先画个图，跟上面不一样，我们将点看成一个矩阵：我们以样例的第一个查询为例，是2 1 E，也就是2,1和3,1这
2020-07-22 20:37:00
199
原创 2020.7.22 T1三色树（jz暑假训练day7）
Description给出一个N个节点的无根树，每条边有非负边权，每个节点有三种颜色：黑，白，灰。一个合法的无根树满足：树中不含有黑色结点或者含有至多一个白色节点。现在希望你通过割掉几条树边，使得形成的若干树合法，并最小化割去树边权值的和。Input第一行一个正整数N，表示树的节点个数。第二行N个整数Ai，表示i号节点的颜色，0 表示黑色，1表示白色，2表示灰色。接下来N-1行每行三个整数Xi Yi Zi，表示一条连接Xi和Yi权为Zi的边。Output输出一个整数表示其最小代价。Sam
2020-07-22 19:24:07
458
1
原创 2020.7.21 T4WTF交换（jz暑假训练day6）
sum = 0for i = 1 to N index = min{ ID[i], ID[i+1] } sum = sum + A[index] 将数组A往右循环移动R位将数组A内所有的数取相反数for i = 1 to N index = max{ ID[i], ID[i+1] } index = index + 1 sum = sum + A[index] 将数组A往右循环移动R位
2020-07-22 15:38:18
125
原创 2020.7.21 T3最小代价（jz暑假训练day6）
Description给出一幅由n个点m条边构成的无向带权图。其中有些点是黑点，其他点是白点。现在每个白点都要与他距离最近的黑点通过最短路连接（如果有很多个黑点，可以选取其中任意一个），我们想要使得花费的代价最小。请问这个最小代价是多少？注意：最后选出的边保证每个白点到离它最近的黑点的距离仍然等于原图中的最短距离。Input第一行两个整数n，m；第二行n 个整数，0表示白点，1 表示黑点；接下来m 行，每行三个整数x，y，z，表示一条连接x和y 点，权值为z 的边。Output如果无解，
2020-07-21 22:16:50
148
原创 2020.7.21 T2最大子矩阵（jz暑假训练day6）
Description我们将矩阵A中位于第i行第j列的元素记作A[i,j]。一个矩阵A是酷的仅当它满足下面的条件:A[1,1]+A[r,s]<=A[1,s]+Ar,1其中r为矩阵A的行数，s为矩阵A的列数。进一步，如果一个矩阵是非常酷的仅当它的每一个至少包含两行两列子矩阵都是酷的。你的任务是，求出一个矩阵A中的一个非常酷的子矩阵B，使得B包含最多元素。Input第一行包含两个整数R,S(2<=R,S<=1000)，代表矩阵的行数与列数。接下来R行每行包括S个整数，代表矩阵中
2020-07-21 22:14:18
88
原创 2020.7.21 T1矩阵（jz暑假训练day6）
Description给定一个由数字（0-9）构成的字符串s。我们可以由此定义出size(s) * size(s) 大小的矩阵b，其中b[i][j] = s[i] * s[j]；请问在这个矩阵b中，有多少子矩形满足其中的b[i][j]的和为另一个给定的数字a。Input第一行一个整数a。第二行字符串s。Output一个整数表示满足条件的子矩形数。Sample Input1012345Sample Output6【样例解释】b 矩阵为：01 02 03 04 0502 04 0
2020-07-21 21:57:38
133
原创 2020.7.20 T4五子棋 （jz暑假训练day5）
DescriptionWHU ACM的队员们迷上了五子棋游戏，他们决定组织一场队内友谊赛以便互相切磋棋艺。 比赛规则是这样的：每位选手都要和其他人进行一场比赛，每场比赛胜者将得到一定的积分，败者不得分，若和棋则双方都不得分。 每位队员都有一个经验值，我们可以认为比赛中经验值较高者获胜，若双方经验值相同则为和棋。 队员们都很聪明，他们会在比赛中不断进步。也就是说，和特定的对手进行比赛后，无论胜负，都会增加一定经验值。 小M作为WHU ACM集训队的队长有资格安排比赛顺序，而同时作为1号选手的他自然希望自己的
2020-07-21 21:40:52
138
原创 2020.7.20 T2昂贵的珍珠垂饰（jz暑假训练day5）
Description情人节之际，Alex决定用K种珍珠为他的GF做一串举世无双的珍珠垂饰与她的项链相配。珍珠垂饰是由珍珠连接而成的，其长度可以认为就是珍珠垂饰上珍珠的个数。众所周知，Alex家缠万贯，每种珍珠他都拥有N颗。根据将珍珠垂饰打开后珍珠不同的排列顺序可以区别不同种类的项链。现在，他好奇自己可以组成多少种长度为1至N的不同的珍珠垂饰？当然，为显富有，每串珍珠垂饰都要必须由K种珍珠连成。答案取模1234567891。Input输入包含多组数据。第一行是一个整数T，表示测试数据的个数。每组数据
2020-07-21 21:38:10
127
原创 2020.7.20 T1矩阵的个数（jz暑假训练day5）
Description给出一个N行3列非负整数矩阵的各行各列之和，统计有多少个矩阵满足此条件。输出答案模10^17的值。Input第一行包含四个正整数N，c1, c2, c3，即行数与三列之和。第二行包含N个正整数，即各行三个数之和。每行每列之和均不超过125。Output仅一个数，满足条件的矩阵个数模10^17的值。Sample Input3 2 3 41 2 6Sample Output17Hint1<=N<=200赛时100分，只有3列，有人暴力找两列来找矩阵，
2020-07-21 21:11:10
157
原创 2020.7.18 T3Ocd（jz暑假训练day4）
DescriptionInputOutputSample Input5 6 73 1 4 2 52 4 5 3 12 4 1 3 51 4 3 5 25 2 1 4 3Sample Output4 2 3 5 1Data Constraint正解首先考虑求出逆序对方案数，设f[i][j]表示当前第i位有了j个逆序对时的方案数。由于每个i最多贡献i-1个逆序对，那么f[i][j]+=f[i-1][l](l=max(0,j-i+1)至j）但是这么做就爆了，但是我们只要知道它的
2020-07-21 07:56:23
149
原创 2020.7.18 T2Captcha（jz暑假训练day4）
大意提莫大意就是给个这个玩意儿：样例输进来有问题。。。。。。就是说每次给你一些如上面的框框，对于每个框框，求一下表示的是哪个数字解这个题直接暴力就行了，我是记录每个框框有 **.**的五行，每行多少个点，那么如0就是3 2 2 2 3，大概如此。然后就发现2,3,5都是3,1,3,1,3那么再记录一下它们第二行，第四行是什么就行了，这种题普遍打得丑，代码就不放了。...
2020-07-21 07:39:57
135
原创 2020.7.18 T1Family（jz暑假训练day4）
Description在时间的流逝中一切都不断改变着，当我意识到这一点时，已经无法再前进了。Sarila在高中时参加了信息学竞赛。信息组就像一个大家庭，即便分开，羁绊仍然是存在的，这就是所谓的同学吧。Sarila负责为今年信息组的聚会制作蛋糕，她买了n个蛋糕，第i个蛋糕长度为 ai，宽度为bi，高度为1(这里长宽是可以互换的)。Sarila想组合出一个最大的长方体蛋糕塔，蛋糕塔每层的蛋糕尺寸是一样的。她决定从某一些蛋糕里切出一个xy的子矩形，再把这些xy的矩形蛋糕叠起来作为蛋糕塔。一块蛋糕只能切出一块
2020-07-21 07:34:37
201
原创 2020.7.17 T3水管（jz暑假训练day3）
DescriptionInputOutputSample Input15 71 2 21 4 12 4 24 3 22 3 14 5 11 5 2Sample Output5NoData Constraint赛时最小生成树打一遍，之后贪心的认为选一条没有选的边中最小的边，然后再打一遍最小生成树，竟然还有62分！之后把long long开了有82分！！！正解很多方法，我的方法大概是，先最小生成树，之后对于每个没选的边u,v,w，我们查找u到v的路径上最大的边权，那么
2020-07-20 07:34:56
127
原创 2020.7.17 T2数组（jz暑假训练day3）
Description InputOutputSample Input输入样例1：3 2 75 4 2输入样例2：5 3 15 4 3 5 5Sample Output输出样例1：999999732输出样例2：0Data Constraint赛时本来dp搞30分，之后搞特殊，结果包蛋。正解这一题先将所有的数取绝对值，并用bj标记出正负性。(1)当输出答案是非负数时，将能变号的数变号，并转到情况(2)。若不能将任何数改变符号，则要将数组中最小的数减去k*x。(2
2020-07-17 19:50:31
105
原创 2020.7.17 T1亲戚（jz暑假训练day3）
DescriptionInputOutputSample Input40 1 1 0Sample Output8Data Constraint赛时25分暴力+5分全排列正解树形dp方程是：f[x]=((f[x] * f[v])%mod*c(min(size[x]-1,size[v]),size[x]-1+size[v]))%mod;x为当前遍历的点，v为儿子，此时的size[x]并没有加上v的节点数。那么这个方程的意思也就是v的子树与前面x遍历过的子树求方案，f[x]*
2020-07-17 19:41:53
125
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人