- 博客(135)
- 收藏
- 关注
RSS订阅原创 CTS2021退役记
从前我总是等考试结束后才更游记，对着尘埃落定的成绩，小心翼翼地堆砌文字。这次我不会鸽了，也不会再有莫名其妙的十五进五了，我要勇敢地迎接最后的结局，而不是空自面对失败的无助与成功的无措。华丽精致的亭台楼阁走近之后突然化为乌有，但是过去与未来的漫漫征途才是真正值得怀念与期待的。七彩泡沫的破灭必然不是happy ending，但也不是bad ending，它只是true ending。...
2021-02-03 18:30:48
2044
2
原创 IOI2021 国家集训队作业部分题解
读者本地应该都有由各个集训队员撰写的题解。本文旨在对其进行一些补充。代码基本都能在cf gym的提交中找到，用户名zx2003（应该没人不知道吧。。。）WF2017-2019需要在loj上找，因为当时觉得loj交起来比较舒适。WF2014B本题复杂度是可以优于yht给出 O(w2logd)O(w^2\log d)O(w2logd) 的，虽然也没什么意思。对于每种离散物品，将背包容量按模 wiw_iwi 的值分类后，每一类都是可以决策单调性优化转移的，写个分治就没了，对zx还写了这个，每一类都是
2021-01-16 16:25:02
1396
原创 北大集训2020游记
Day-2 noip2020时间久了有点忘了考试过程了。。。上来倒序开题，T4稍微想了想会了 O(∑wi)O(\sum w_i)O(∑wi)，然后冷静了一下觉得正解就是套个插值。然后一直想T3，中途看了下T1和T2。T2一眼 O(nlogn)O(n\log n)O(nlogn)，再冷静一下发现利用异或的性质，加上exkmp就可以 O(nlog26)O(n\log 26)O(nlog26) 了，觉得AC稳了就没像djq一样继续想线性算法了。 T1一开始看错题了，以为10个点是包括起点和终点的，估了估
2020-12-16 19:26:43
1211
1
原创 NOI2020后记，以及其它
还是尽量精炼一点以节省你我的时间吧。整个高中生涯 WC Au,CTS Au,APIO Au,NOI Au 恰好都拿了一次。排名不尽相等，几乎每次或多或少都有些遗憾。主线剧情就这么结束了，可能还会玩一下支线剧情，但初三时那种初识OI的兴奋与天真，大概是很难再回去了。由于日期跨度过长，就按日期记了。真.流水账8.5 WC2020考试日开场看了下三个题，大概花了1h嘴巴阿克了。反正都是要阿克的感觉T3会挂，T1稳一点，我还是正序写题吧。然后喜闻乐见地算法假了，尝试fix了一会发现自己题看错了。中
2020-09-14 20:16:55
2021
原创 ZJOI2020游记
赛前心态挺平和的.主要是觉得去年像联赛那样自己吓自己挺不值的(现在还是觉得自我惊吓导致Day2在不会T2证明的情况下优先选择补证明而不去卡常太愚蠢了,到手的AK就这么没了…).就考两天试也没啥必要把自己折腾得死去活来,不如吃好睡好.虽然最后也没吃好,因为9:00~14:00的考试时间太反人类了.心态平和的另外一个原因是,听说我手上的NOI2019 Ag好像在强基计划里还是有用的.Day1开场看到个string,莫名兴奋.按照传统先看T2,发现T2名字叫传统艺能,又是个线段树上搞一搞的题.回忆
2020-06-22 08:30:56
3952
2
原创 CSP-S2019 游记
本来想等到真实成绩出来的，但是那样就要等太久了。前记NOI后就一直处于自闭状态，时常从梦中惊醒，梦见自己在各种各样的OI比赛场景中自爆。有一场5个小时的比赛好像是大众分150-，场上一直在调假算法，出来后一问别人发现有一档分很高的暴力没写。有一次出来后发现忘加文操了。还有一次应该是noip，D2T2好像是个差分约束；然后别人都总分接近600，我总分400-。很多细节记不清了，但是它们确...
2019-11-27 23:35:23
1967
原创 16周岁人类个体的思维碎片
还是讲大白话吧，抒情既不适合我的能力也不适合我现在的心情。新的赛季，同时也是我的最后一个OI赛季开始了。初三时曾经以为不挂分就稳了，毕竟当时noip不挂分能上500，NOI网上同步赛不挂分能上队线。高一时成功地只做到了前半句。另外两个成就是1.除了noipDay1外每场正好AC一题;2.奖牌颜色数++（唉）。其实回想过去6个月可能还算幸运吧，毕竟THUWC2019的惨痛经历得出的结论是打...
2019-09-08 23:18:58
1687
2
原创 十五进五
羽毛球馆里有个小游戏。从地上捡了张入场券进去玩。工作人员给了我个拍子和十五个球，让我从网的一边把球打到另一边放在地上的圈里，只要打中六个就有奖品。上一个玩家说挺简单的，我跃跃欲试。球是挺好的，只是一开始手抖连续打飞了好几个。后面稍微好了点，到还剩一个球的时候我中了五个。然后最后一个还是打飞了。...
2019-07-20 20:16:26
1129
原创 THUPC2019&CTS2019游记&APIO2019场外记
由于某些原因并没有参加APIO。Day0前一天晚上做硬卧到北京参加THUPC，因为我也知道的原因，早上四点多就起了。头晕乎乎的，但就是睡不着。队友supy,panole，cf rating都吊打我。开场supy拿2n−12^n-12n−1爆了三发D，一开始没开unsigned long long也没特判0，但是改对后还是WA了，心态有点小崩。换panole上去一A了M。然后panol...
2019-05-20 15:41:28
1245
原创 ZJOI2019R2退役记
简单记录一下考试过程吧，虽然以后可能也用不到。开场先把三题都看了一遍，发现自己会50(+20?)+?+50(+20?)又想了会T2，发现会一个log了。8点四十多开始写T2，十点左右过了大样例，随便造了几个大数据，只要1.2（时限3s），感觉不会T。又回去想了会T1，想到十点四十还是不会。取写了个T3 40,T1 50,T3 10，就到了12点零几。开始写T3的m=2，由于自己是转凸包...
2019-04-26 20:09:04
1458
2
原创 ZJOI2019后记
成绩咕到愚人节才出，游记也跟着咕成后记了。晚上吃完饭后听说成绩出了，怀着忐忑不安的心看到自己0+100+30。当时还没公布带联赛成绩的榜，操作了一波，发现成功忘掉打卡，鈤。好像rk24。把学车第六之后&初中生去掉后rk19。打不过初中小哥&学车第六真丢脸早上开场看T2，一眼线段树上维护边长lognlognlogn的矩阵。四个logloglog可能就40分吧。冷静了好...
2019-04-01 22:32:54
1799
原创 复活的做题记录
本来妄想摈弃博客，全靠自己大脑的记忆来安排学习。直到省选前几天发现，有个题，我的一个绝妙的处理办法，第三遍，被自己忘掉了。遗忘是个坏东西，它使人退步。稍微恢复下本博客的学术作用吧，每天怨天尤人并不能二试翻盘。至于为什么选在这个日子开始呢？本来想等到一试成绩出来，亲眼看到自己爆零。然后评测方咕咕咕了。选在愚人节开始又不大好。就这样了。1.#372. 【UR #17】滑稽树前做游戏...
2019-03-31 22:47:08
646
1
原创 无题-2019.3.1
第一次意识到用这个标题的妙处。据百度百科说这是“中国传统诗歌类型”，但自己文笔太差根本写不动诗，随便写点好了。冬天将去未去，滴答的雨声，湿冷的气息。思绪有点乱，心情有点抑郁。可能过于沉浸自己的世界了吧。今天晚上骑车外出，失去智力的状态下撞了另一辆自行车。有点担心被搞一波事，但第一反应仍然是停下来问下情况。被车主说“你先走吧”。突然回忆起thuwc回来的第二天早上在家门口几十米处骑车...
2019-03-02 18:35:01
626
1
原创 THUWC2019游记&WC2019场外vp记
菜鸡zx联赛炸了以后又去不了WC了。于是报了个THUWC来旅游，成功成为“体验选手”（thu对于非正式选手的说法）。然后真的成了体验选手。Day1 100+60+0，T2调了整场没调出来，害得T3也没好好想。本来搭个对拍可能就调出T2了。用生命证明了自己的代码能力在没有调试数据的情况下是负的。原以为Day1是偶然，然后Day2 100+32+74，爆了整场的T3没爆出来，真的输了。D...
2019-02-02 23:54:41
1050
原创 致我的2019
2018年过去了，2019年来了。一年里我究竟失去了什么，又获得了什么呢？从懵懂无知到懵懂无知，从一无所有到一无所有。2019年，是黄昏的延续，还是黎明的开始？脆弱的薄冰被车轮无情地碾碎。稚嫩的草尖在白雪之下艰难萌生。寒冷僵硬的手指困苦地敲击着键盘。光标闪烁，这会是无谓的挣扎吗？...
2019-01-01 00:22:53
700
1
原创 noip2018后记
达成成就：集齐一场比赛自己的前记，游记，后记目前尚未发现挂点。不过想想也没啥好开心的，最多说比去年有进步。毕竟D2几个naive暴力怎么挂呢？其实这次很多东西都影响了我的决策，诸如D2T1耗时远大于预估（预想15min，实际40min），D2T2快结束时才想到赛场上最经济的做法——打表，D2T3考了一个，虽然会，但是与往期联赛的知识范围不符的东西。不过自己当时以为起码要1.5h，确实是没有自...
2018-11-13 22:53:41
727
4
原创 noip2018游记
Day1没啥好说的。T1第一反应是笛卡尔树，真是无话可说。T2第一反应是同余最短路，硬是花了30min写了一个，并把二叉堆换成特技来少log，还以为这题挺牛逼的，二叉堆选手都要卡常成80（滚粗flag * 1）随机数据平均O(max(ai)+n)O(max(a_i)+n)O(max(ai)+n)，随机数据超快的。T3先写了multiset的程序过了大样例，然后菊花图跑了1.4s。于是改...
2018-11-11 20:23:51
1141
原创 noip前的一些话
这里是去年写过的旧版本。明天要noip了，现在对这篇文章打点补丁。文章核心侧重于“与算法水平相关性不是特别大”的问题。1.好好读题，一个字一个字看下来，不要怕浪费时间。2.想清楚再开始动键盘。3.noip没有“惯例”，唯一的“惯例”是每年的题风与难度等都会有所变化。A不出来不要紧，堆堆暴力也不会太差。4.然后最关键的是要稳住心态，相信自己。5.变量名不要打反(noip2017D2T3...
2018-11-09 21:57:01
503
原创 loj2474《北校门外的未来》题解
鉴于lca本人已经写过此题命题报告，所以可以认为本文是命题报告的注解以及实现指南。好神仙的一道题，前前后后总共耗了我差不多三整天时间。最开始看到这题是集训队互测loj上同步赛的现场，当时就觉得很吸引人。然而并不会做，膜了一波sol，然而还是不会。后来ZJOI2018R2第二天Scape讲题时又提到了此题，还是不会。暑假里尝试过一波，并没有什么进展。现在强推了一波，终于干掉了此题。题解...
2018-10-19 18:02:47
1055
1
原创 关于 ZJOI2018R2T2胖 ，题解&后记
题目连接谨以纪念ZJOI2018R2，那些失败甚至退役的OIer（包括自己）。下文认为∑k\sum k∑k和nnn同阶，故不再做区分。首先显然被某个点松弛过的点集是段区间。吉利sol里的做法，是直接二分这个区间的左端点和右端点，用线段树或(ST表+二分定位)来优化判定，复杂度O(nlog2n)O(nlog^2n)O(nlog2n)由于这里两个点A对B的影响不是简单的把带权中点拿出来，还有...
2018-10-02 13:47:41
1852
原创 CF#504，#505（based on VK Cup 2018 Final）上红记
去年的我这时还是蓝名小哥，然后勉强上了紫。 当时写过一篇上紫记。 我打cf频率在friends里还是偏高的，大概就是经常打出饱和状态。 1900- 徘徊过几场，2100+-徘徊了好几个月，从noip2017延续到ZJOI2018R2，中间codeforces大崩和小涨居多，OI赛事也差不多。 然后cf名字颜色的线压低，突然莫名上了黄。 6月份运气爆棚，打了场rk28，上div1后的历史最...
2018-08-21 20:29:36
586
1
原创 UOJ349【WC2018】即时战略有关的一些事情
这是一道好题，题意简洁，是多种树上分治结构各显神通的好地方。 WC2018当天晚上去写这题，写到0点，心力憔悴。 后来等到uoj上加了题后，交了若干发，全是97。 今天尝试去补救，发现以前的写法复杂度不太对。 本来LCT splay部分的复杂度是∑logszi+1szi=lognsz∑logszi+1szi=lognsz\sum log \frac{sz_i+1}{sz_i}=log\fr...
2018-08-16 11:02:47
851
原创 NOI2018情报中心
这题当场想了1h左右，自以为会正解。 当时的想法，在S2部分是对的，但在S1部分是错的。 在S1部分，我试图使用轻重链路剖分，轻儿子暴力，重链上就像链的部分分一样做。但事实上两条lca在同一条重链上的路径，他们的交可能还从重链上伸出去一点，然后我就gg了。 事后还是花了些时间才想出S1的正确做法。 大概就是对于两条链(u1,v1,lca1,lca2)和(u2,v2)，在lca(u1,u2)...
2018-07-22 11:22:46
2281
2
原创 NOI2018网上同步赛记
省选完挂选手并不能买到D类。 比上次WC口胡记更贴近于真实OI比赛。 Day1： 满怀憧憬打开题目。 T1读错题了，以为是神仙题，但还是一眼55pts。 T2应该可做，但数数题咋放D1T2。 T3一眼68pts，比T1还一眼。 回头看T1，发现读错题了，一开始以为每次起点和终点不固定，然后又读成每次起点固定，第三次才读对。 稍加思考会可持久化并查集的两个log做法，感觉4sO2稳了...
2018-07-18 23:55:06
1392
3
原创 loj2478林克卡特树
听说这题要用到一个叫做“带权二分”的黑科技（名称来自于APIO2018讲课课件），那就让我来体验一下。 写了一发，感觉概念还好懂，但特别容易挂。 有几个要点： 1.要对输入数据加以随机扰动，不然会被三点共线的数据卡。 2.如果上次答案和这次答案的差很小，则直接输出这次答案，不然会被卡精度。 3.其实可以把权值和方案封装成一个struct，这样写起来会方便一点。 然后就抢下了洛谷运行时间...
2018-06-25 23:20:06
666
原创 THUSC2018游记
Day0： 晚上敲了下SA和SAM的模板，之外就没干啥事了。 我校只有我一个人来THUSC，好孤独啊，幸好我爸正好要来北京出差，可以陪陪我。 听说隔壁PKUSC lyx_cjz又㕛叒叕AK了，太强了。 我校好像有两发260，感觉不错。 Day1： 上午考试，先干T1，看到q有1000万，想了半天“猫树”做法，后来突然意识到可以从左往右扫，使用树状数组，每个节点保存一个数组，表示以这个节...
2018-06-05 20:42:00
2048
3
原创 uoj219
明天就是thuscDay1，发现好久没写过SA模板了。正好以前没做过这题，那就钦定你来练手了。 然后模板题都敲错了： 1.query时没判询问下标是否真实存在于区间[1,n][1,n][1,n]中 2.求height数组时没有判下标<=n 25->55->80->100，感觉要是当时NOI赛场上，这样会血崩的。 明天要是有这种暴力95的题，我绝不写正解，除非只差这...
2018-06-02 22:49:59
238
原创 CTSC2018&APIO2018 游记
Day0： 第一次来帝都，感觉人好多，地铁好挤。酒店离地铁站略远啊。 下午试机，发现是九省联考Day1原题，没有提答，那么接下来两天是不是也没有提答呢？Day1: 开场冷静分析了三道题目，感觉T1 cn3cn^3应该是70，满分可能是 分块，分治，NTT,好像还能退背包。T2感觉跟WC T1有点像，但WC T1我没做过。T3感觉是个可做数数题。 回去做T1，写完退背包，连第一个样例都过不去
2018-05-09 23:35:47
808
原创 JSOI2018R2游记
ZJOIR2自爆选手来旅游啦！Day0: 试机时发现本机配备有NOI linux虚拟机，可自行选用。 写发NTT，百万多项式乘法O2下1.3s，速度还行。 点开配置，似乎跟评测机配置一样。 感觉比上次SHOI把我送掉20(+100?)分的辣鸡选手用机高到不知道哪里去了。Day1: 开场花了25min看了下题，T1有点怀疑复杂度，但又觉得是对的。T2 n只有200，直接n^3上就行...
2018-05-05 14:45:49
1392
原创 九省联考2018游记
Day0 上午到学校，去tututu寝室，入坑荒野求生，真tm好玩（虽然只打了一把） 下午坐高铁去SH，发现SH非正式选手只有HEZ的。 Day1 开局看T1，没意识到状态数是个组合数，于是写了个程序算状态数，还写挂了#include<cstdio>int n=10,m=10,f[15][15],i,j,k;int main(){ for(i=1;i<=m;++i)f[1][i]
2018-04-09 15:21:48
698
原创 ZJOI2018一试滚粗记
写在前面的话： 可能这篇游记不像前几篇游记那么沉重，因为阴郁的文章背后，是一只阴郁的欣。 而阴郁的欣只会心态爆炸，考试崩盘，从刚学OI时的第一场宁波市赛，考场里狂吐不止，住了几天院，再到前年暑假，每天考，每天几近泪奔，从noip初赛强行挂成85-，再到thuwc2018没过全场题，OI生涯长，全是黑历史，看来我一直如此。 然而我炸的多了，已无所畏惧。 唯有放下，才能收获。既然过分在意结果，...
2018-03-21 23:02:15
765
原创 WC2018口胡记
作为一个noip考挂选手，我并不能去WC2018。 当天下午一点半左右问@tututu要来题目，一开始只有T1的复述版本，感觉是个数据结构题，但并没有什么思路，而且部分分表也没有，似乎只会O(n2)O(n^2) 过了一会儿，tututu大爷发来了纸质题面的照片。这个T1好像44很显然啊，然后就扔掉先看T2,T3。 这个T2的O(3n)O(3^n)挺可做的，感觉正解可能是FWT优化？前些日子对着
2018-02-10 23:13:27
1313
2
原创 CF799F，随机+hash
好久没写过学术型的博客了。 一开始做这题时并没有什么思路 接着去看官方题解，似乎有一个无比巧妙的确定性做法，然而并没有看懂 百度了一下，发现好像可以给每个花园里的喷泉赋一个随机权值，然后再搞一搞就好了。 这几天感觉思维僵化，这么常见的手法都没想到，有点难过啊。#include<bits/stdc++.h>using namespace std;const int N=200005;ty
2018-02-06 10:04:17
903
原创 thuwc2018赛前的话
这是一个寒冷的冬天，多年不见的白雪，又一次笼罩了大地 回忆去年九月，那时盛夏的余热尚未散去，每天夜里，辗转反侧之时，总是满怀着一腔热血，渴望着联赛，渴望着证明自己，渴望脱离普及组的襁褓，去全新的赛场里征战，NOIP提高组,WC,ZJOI,CTSC,APIO，甚至是NOI。当时的我依然认为，NOIP2017，将会成为这一切的第一步。 结果到头来，数月的辛勤努力，毁于Day2，最后连初一小哥都不如
2018-01-28 22:26:09
1075
3
原创 CF235C
传送门 题意就是你有一个母串，每次查询给出一个串，问母串有多少个子串和查询串循环同构。 首先建出母串的SAM。 再将询问串复制一遍，在母串上跑就行了。 但直接这样是有问题的，比方说有一个串”abc”，复制一遍后就是”abcabc”，匹配到第二个a的时候，发现母串没有”abca”这个子串，但却有”bca”这个子串，怎么办？ 其实只要加一句话for(;step[pre[u]]+1>=l;z=s
2017-12-11 09:58:43
507
原创 NOIP2017后记
我身着单衣，骑行在大雨之中，水滴打湿了我的衣服，也打湿了我的心，阴暗，潮湿，冰冷。 今天是十一月三十日，光阴荏苒，一个月又过去了。 本想考完就写的，然而觉得成绩并未公布，一切都是未知数，还是等尘埃落定之后再说吧。 但是，等待CCF公布成绩，是件极其考验耐心的事。而我的悲痛，又迫不及待的想要宣泄。 还是先叙述下爆炸经历吧，感觉不想掺杂进过多的情感，因为亲身经历过的人，自然会明白，平白的文字背后
2017-11-30 22:37:35
589
3
原创 洛谷3987之我的解法
首先正如题解所述“瓶颈在于如何找出所有该被/的数而不在于如何维护”。 考虑离线来完成这一步。对于每个操作(id=这是第几个询问，l,r,x)(id=这是第几个询问，l,r,x)，在ll处添加xx（具体操作是用一个set<int> e[A+5];，并e[x].insert(id)）然后在r+1r+1处添加xx的删除标记。这样就可以知道每个数受哪些询问的影响。 然后对于一个aia_i，将它的因子（在
2017-11-27 22:32:17
335
原创 Uoj Test Round3，有生之年系列的比赛
UOJ好久没有过比赛了，上次可能已经是UNR2了，依稀记得那场我只参加了day2，然后被T1计数题卡死，写了一个70分暴力，还爆零了（事后把一个2改成1，就70了，再加上前缀和优化，就AC了，然而这是T1） 比赛传送门 官方题解传送门 这次比赛的T1是计算几何，初看挺水的，然后一开始没有很专心写。慢悠悠的写完后发现死活过不了样例，原来是算法错了，一个蓝点在（另外两个红点+原点构成的三角形）中，
2017-11-23 14:45:53
743
原创 TC12389
传送门 我想出了官方题解中第二种算法的一部分，苦于多项式太差，无法进行优化，最后写抄的是第一种方法。有机会还是学习一下多项式相关理论，学习一下第二种方法。 有几个要点要注意： 1.f[0]要视为常数项，而不能作为题目中所谓的n!0来看待，因为n!0并不直接参与递推，所以转移矩阵的第0列实际上是用于存放一些别的东西 2.根据题解里的定义，求出矩阵A0,A1,A2......A_0,A_1,A_
2017-11-19 18:29:55
238
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人