- 博客(40)
- 收藏
- 关注
RSS订阅
原创 博主介绍
本人是一个（新）初二信息学蒟蒻，发表的文章题目可能较简单，请不要在意。本人所写的文章都是本人呕心沥血打的，未经允许请不要转发，若想转发请来旧科学馆302找我。作为一个菜鸡，期末总结什么的是不可能写得了，关于游记有兴趣也许会写一下。 至于比赛题解当然是经常水了，但算法介绍什么的我知识面太少怕会误导，就写点简单的了。...
2018-08-16 17:04:20
427
2
原创 CSP-J/S 复赛总结（游记）
DAY -7~-1临近考试不仅不感觉紧张反而觉得有点兴奋（？）DAY 0听说语文物理作业全被免了，英语半免而且下午3:50就放学了。虽然六点才上车8:00左右到了酒店，把要做的作业补了一下就开始背码了9:00时听说有人点了外卖，开始放飞自我马上下载肯德基APP，花了我半小时9:30边吃边看球赛，吃完就睡了真想吐槽酒店的透明洗手间+猥琐高雅挂画+二格信号DAY 1上午比6:3...
2019-11-22 20:54:34
716
原创 2019.08.13【NOIP提高组】模拟 A 组总结
心态崩了，比赛体验十分快乐T1想到了k=2的情况k=3o(n)暴力一下T2找到了x为质数的规律顺便打了x=30和x=12的表（n<=4）然而前两个点必有n=5，三四五全T了T3人口普查...
2019-08-13 14:30:53
141
原创 2019.07.10【NOIP提高组】模拟 A 组T1 树的难题
树的难题题目连接一眼DP，但想不到状态怎么设，在半醒半睡中度过了四十分钟设f[i,j]表示第i个点，所在集合状态为j时的最小代价j=0表示有0个黑色点j=1表示有0个白色点j=2表示有1个白色点设a[i]为第i个点颜色黑色为0，白色为1，灰色为2j为i的儿子，s为i与j之间的边的权值当a[i]<>0时f[i,0]为当a[i]<>...
2019-07-10 21:50:54
233
原创 2019.07.05【NOIP提高组】模拟 A 组总结
今天的题画风突变心态崩了T1家族：比赛时一直在想如何维护可持久化并查集没想到m那么小可以给边排个序，m^2枚举选哪些边，跟枚举频率区间起点终点是一样的还快很多很多然后并查集判T2：5分人口普查,正解上下界最小费用可行流,不会.好吧现在会了设附加源ss，附加汇tt把一条边u,v,l,r拆成ss到v，容量为lu到tt，容量为lu到v，容量为r-l保留每...
2019-07-10 21:46:17
160
原创 2019.07.06【NOIP提高组】模拟 A 组总结
T1：之前觉得十分简单加了那个条件后再没看过一眼T2：一眼矩乘优化dp打了个程序造矩阵又打了个程序矩阵乘法再打了个主程序结果时间点弄错了，三个程序一直在拍，看哪个矩阵求出的答案是哪个时间点的十二个矩阵不记得乘起来，调了很久然后把两个数组内容换了又调了好久最终还发现两个数组弄混了T3：线段树可怜t2比赛没调出来...
2019-07-10 21:30:47
151
原创 2019.03.30【NOIP提高组】模拟 A 组 总结
8+5+0=13没有除以10T1：比赛的时候，推了一下样例和一个小数据，感觉答案好像很好求比较难描述，大概就是：一段路程，记路过人数为x当x=0时，只需经过一次，x>0时，要经过2x-1次挺好证伪的，但是我开始了思考，这可以用差分来做一开始想用线段树，但是太大了，想了一会优化了一下思路就真变成差分了，将一个区间拆成两段，头+1尾-1如果头位置在尾后面就调换...
2019-03-30 16:19:56
145
原创 2019.02.23【NOIP提高组】模拟 A 组总结
因为做过B组所以来A组水60+100+0=160oj太神奇所以第一题交了四次，最后一次才成功T1pascal会被卡快排（好像有人不会被卡），不然应该是90（有个地方觉得不用就没判边界，结果数组越界了）T2过了T3不会，不屑于打暴力思想225系统随机选择30%的幸运程序评测如果没这我觉得225拿不了第四如果没有T1：先快排可以看出删剩的必然是一段连续的数一眼...
2019-02-27 21:47:15
190
原创 2019.02.16【NOIP提高组】模拟 B 组总结
100+100+10+0=210题目难度两极分化T1：我们发现，n的方案可以是n-1的方案后面后面放个1,也可以是n-2的方案后面放00。由此可见f[i]=f[i-1]+f[i-2]找规律也可以找出签到题1号T2：一开始想到快排之后，每个数的前后两个数与这个数差距最小（错的）然后又看到每个人最多打两场，最多与一个等级比他高的和一个等级比他低的打排序后等级比他高的最优必然是他后面...
2019-02-17 09:47:25
156
原创 2019.02.15【NOIP提高组】模拟 B 组总结
100+80+30=210T1：很容易看出是棵树求出最长距离，深搜一下如果一个点是叶子节点暂时在它与它父亲那条边上放陷阱直到与根节点的距离达到最大值如果是父亲节点由于一个节点与它父亲的边上的陷阱可以影响这个点的所有儿子也就是说我们可以在i与i的父亲的那条边上放陷阱来减少i到i的儿子的边上的陷阱数但放太多会使某些点距离大于最大值求个min就好。T2：一眼状压但是2^15*...
2019-02-15 14:48:26
151
原创 2019.01.28【NOIP提高组】模拟 B 组 T3
T3：BDescription小D是雅礼高一著名的神犇，在NOI同步赛中获得了满分的优异成绩，而全国没有任何其他人获得如此的成绩。某天晚上，高一内部在讨论一道题目，然而包括小D之内的各种神犇都毫无头绪，这时候，高二的人赢小T上来给高二进行了精彩的讲解。小D被小T的神犇气场所折服，他知道小T之所以没有同步赛满分是不屑于，于是他决定拜小T为师。一日小T正在给小D讲解后缀数组。“把一个字...
2019-01-28 21:16:50
208
原创 2019.01.28【NOIP提高组】模拟 B 组 T2
T2：ADescription帝国时代3是一款十分刺激的RTS游戏。你需要控制自己的一块殖民地，发展殖民地的经济和军事，最终打败其他殖民地。小L是这个游戏的狂热爱好者。一次小L打算打AI试试身手。小L发展了几分钟，自己的殖民地人口便突破了30，然而小L发现大事不好了：小L还处在不能建造军事单位的“发现时代”，然而敌人早已经到了“殖民时代”，发展起了一支雄厚的殖民地军，小L的殖民地受攻击...
2019-01-28 21:07:17
195
原创 2019.01.28【NOIP提高组】模拟 B 组 T1序列
T1：序列改不起A组，来写博客了。题目： Fiugou想要在一个长度为N的序列A中找到不同位置的三个数，以这三个数为三边长来构成一个三角形。但是它希望在满足条件下，这三个数的位置尽量靠前。具体地，设这三个数的为Ai,Aj,Ak(i<j<k), Fiugou希望k尽量小；当k相等时，满足j尽量小；当k，j均相等时，满足i尽量小。但是这个序列中的数可能会发生变化。所以Fiug...
2019-01-28 20:39:17
240
原创 2019.01.26【NOIP提高组】模拟 B 组 总结
没错这三篇都是c我oj论坛的。茹科夫组题20+100+0=120=废物T1：我真想不起来还有折半搜索这种东西。你们牛。不知道我的算法怎么描述反正我也证不出正确性。WA20好像就是输出原数列的那二十分T2：真的水设f[i,j]表示第i天走到第j个城市不可以待在某个城市，每天必须走。转移方程很简单，不写了。反正就是钱是天数-1 mod 周期+1。记得第零天走到第一个城...
2019-01-28 20:31:36
157
原创 2019.01.27【NOIP提高组】模拟 B 组
又是茹科夫组织今天题目感觉有点难度两边分化对了第一题11:27分开始运行评测完上一题再交？11:30结束，交一道题一分多钟您还要我交题么？怎么比赛？T1：日常签到题。因为ai=ai-1*3 ai+1=ai*3反正很容易推出a1~i的和小于ai+1那么我们可以发现，设前i个数最大组合的编号为k那么第i+1个数加入后，第k+1小即为第i+1个数k+2小为原来的第一小加上第i+...
2019-01-28 20:29:14
202
原创 2019.01.28【NOIP提高组】模拟 B 组 总结
好久没有更新博客了，来写写。没什么好说的比赛100现在12:04，统计220T1：考试的时候觉得过不了打了优化比赛结束一个朋友切了，告诉我第一题卡不了确实，如果无法构成，最长边的增长是非常快的就像楼上说的斐波那契数列我们从前往后枚举，可以保证i,j,k最小所以就过了，所谓n^3特别简单，但我40T2：想复杂了比赛时的打法是错的正解十分简单：设sum为所有k-a[i]...
2019-01-28 20:27:38
208
原创 2018.12.15【NOIP提高组】模拟B组 jzoj100044.
jzoj100044.题目描述有四个长度为N的数组a,b,c,d，现在需要你选择n个数构成数组e，数组e满足a[i]<=e[i]<=b[i] 最大输入 输入文件名为abcd.in。输入文件共 N+1 行。第 1 行包含1个正整数N。第 i+1 行包含4个整数a[i],b[i],c[i],d[i]。输出 输出文件名为abcd.out。...
2018-12-15 16:49:44
200
原创 2018.12.15【NOIP提高组】模拟B组 jzoj100047. 基因变异
jzoj100047. 基因变异题目描述21 世纪是生物学的世纪，以遗传与进化为代表的现代生物理论越来越多的 进入了我们的视野。 如同大家所熟知的，基因是遗传因子，它记录了生命的基本构造和性能。 因此生物进化与基因的变异息息相关，考察基因变异的途径对研究生物学有着 至关重要的作用。现在，让我们来看这样一个模型：1、所有的基因都可以看作一个整数或该整数对应的二进制码；2、在 1 单位时间内...
2018-12-15 16:31:44
166
原创 算法模板：主席树模板
pascal主席树模板 //主席树模板var i,n,m,total,ans,x,y,z:longint; root:array[0..100000]of longint; t:array[0..4000000,1..3]of longint;procedure inw(x,y:longint;l,r:int64;z:longint);var mid:int64;begin...
2018-10-15 14:37:00
264
原创 算法模板：tarjan模板
tarjan模板pascal //tarjan模板var i,n,m,x,y,total,so:longint; h,dfn,low,ss,g1:array[1..10000]of longint; bz:array[1..10000]of boolean; z:array[0..10000]of longint; g,l:array[1..30000]of longint;p...
2018-10-15 14:36:15
136
原创 算法模板：匈牙利算法模板（二分图匹配）
pascal匈牙利算法模板//匈牙利算法模板var i,j,n,m,so,x,y,ans,t:longint; h:array[1..200]of longint; p:array[1..400]of longint; bz,gcl:array[0..400]of boolean; g,la:array[1..20000]of longint;procedure ad(x,y...
2018-10-15 14:36:02
223
原创 算法模板：后缀自动机模板
pascal后缀自动机模板 //后缀自动机模板var i,last,q,p,total,x,cur,clo:longint; s:ansistring; n:int64; bz:boolean; len,link:array[0..150000]of longint; //len——节点i到0的最短路,link——状态i的(来源?) son:array[0..150000,1....
2018-10-15 14:35:22
216
原创 算法模板：AC自动机模板
pascalAC自动机模板 //AC自动机模板var i,j,k,n,m,ans,total,l,r:longint; s,v:ansistring; t:array[0..200000,1..26]of longint; a,c,tail:array[0..200000]of longint; dl:array[1..200000]of longint;procedure d...
2018-10-15 14:35:04
150
原创 2018.08.19【2018提高组】模拟A组 题解 （JZOJ3363）Number
T2：Number题目描述JYY 来到了一个新的城市，为了和大家保持联系，第一件事就是办理新的手机号。JYY 对号码的要求很高，希望大家都能够顺畅地阅读手机号，因此 JYY 特别研究了地球人的电话号码阅读习惯，有如下重大发现 (请自行代入你们的手机号码)：地球人总是按照以下四种方式来朗读电话号码： 1. xxx-xxx-xxxxx 例如 151-958-83019 2. xxx...
2018-08-20 16:23:41
541
原创 2018.08.19【2018提高组】模拟A组 题解 （JZOJ100041）列车调度
T1：列车调度题目描述输入描述输出描述样例输入Sample1: 3 1 2 3 Sample2: 9 1 3 2 4 8 6 9 5 7样例输出Sample1: 3 Sample2: 5题解： 我们发现，如果要使轨道数k最小，那么应尽量在现有的轨道中塞（废话）。 而要保证倒叙出去，没有列车的编号能大于同一条轨道中前面所有列车的...
2018-08-20 16:01:39
275
原创 【线段树】一种二叉搜索树
线段树是什么 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。（以上转自百度百科）如果我们用根节点代表1~n这个区间，那么它的左儿子节点就代表区间1~(n+1)div 2，右儿子代表区间(n+1)div 2+1~n，以此类推（如下图） 线段树如何实现我们用深搜来插入，查询与修改。 1，建树与区间查询 每次走到一...
2018-08-20 15:24:47
416
原创 2018.08.18【2018提高组】模拟A组题解（JZOJ5829）string
T1：stringinput:string.in output:string.out Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits 题目描述给定一个由小写字母组成的字符串 s。有 m 次操作，每次操作给 定 3 个参数 l,r,x。如果 x=1，将 s[l]~s[r]升序排序；如果 x=0，将...
2018-08-18 20:12:19
656
原创 【并查集】基本思想与操作
1.并查集是什么？ 并查集是一种数据结构，通过维护每个点所在的集合，可以处理一些不相交集合（Disjoint Sets）的合并及查询问题。 2.并查集如何实现 我们可以将每个集合视作一棵树，用这棵树的根的编号代表这个集合，最开始所有点都属于不同的集合，即每个点为其所在的树的根。 在合并集合时，我们可以将其中一个集合的根的父亲设为另一个集合的根的父亲，这个操作我们可以通过从当前点往其父亲跳来...
2018-08-17 20:39:52
552
原创 后缀自动机的构造
好处：可用n(+一个常数)的空间存下一个字符串的所有子串，便于计算有关子串的答案，时间复杂度为o（n+一个常数)）状态0：即所有状态的祖宗（盗一张图）某个构造完的后缀自动机t0即为状态0last：上一个加入的字符最初所在的状态，即上一个curcur：最新一个加入的字符所在的状态link：离状态0 。 son[i][j]：第i个节点连出去的第j条边所连的状态len...
2018-08-16 17:18:51
231
原创 2018.08.08【2018提高组】模拟A组题解 城市猎人
T3：城市猎人题目描述：有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。输入第一行输入三个正整数n,m,q，其中q表示询问个数。接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。输出输出q行，每行一个...
2018-08-10 21:25:08
447
原创 2018.08.08【2018提高组】模拟A组题解 秘密通道
T2：秘密通道题目描述：有一副n*m的地图，有n*m块地，每块是下列四种中的一种：墙：用#表示，墙有4个面，分别是前面，后面，左面，右面。起点：用C表示，为主角的起点，是一片空地。终点：用F表示，为主角的目的地，是一片空地。空地：用 . 表示。其中除了墙不能穿过，其他地方都能走。主角有以下3种操作：1.移动到相邻的前后左右的地方，花费一个单位时间。2.向前后左右其中一个...
2018-08-10 21:12:16
580
原创 2018.08.08【2018提高组】模拟A组题解 没有硝烟的战争
T1：没有硝烟的战争 题目描述：被污染的灰灰草原上有羊和狼。有N只动物围成一圈，每只动物是羊或狼。该游戏从其中的一只动物开始，报出[1,K]区间的整数，若上一只动物报出的数是x，下一只动物可以报[x+1,x+K]区间的整数，游戏按顺时针方向进行。每只动物报的数字都不能超过M。若一只动物报了M这个数，它所在的种族就输了。问以第i只动物为游戏的开始，最后哪种动物会赢？输入第一行输...
2018-08-10 21:02:17
342
原创 2018.08.06【2018提高组】模拟A组题解 可爱精灵宝贝
T2：5770. 【2018提高组模拟A组8.6】可爱精灵宝贝 题目描述Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由1到n。刚开始玩家在k号房子前。有m个精灵，第i只精灵在第A[i]栋房子前，分值是B[i]，以及它在T[i]秒内（含）存在，之后消失。Branimirko可...
2018-08-10 20:50:30
467
原创 2018.08.06【2018提高组】模拟A组题解 引子
事先声明，我不会第三题T1：5769. 【2018提高组模拟A组8.6】引子 题目描述网上冲浪时，Slavko被冲到了水箱里，水箱由上而下竖直平面。示意图如下： 数字i所在的矩形代表一个编号为i的水箱。1号水箱为水箱中枢，有水管连出。除了1号水箱外，其他水箱上方会接进来恰好一条水管，也可能有水管连出。连出的水管会从水箱侧面连出去，同一个水箱连出去的水管会在不同的行与侧面连接...
2018-08-10 20:46:26
323
原创 2018.07.17【省赛模拟】模拟B组 比赛题解(&总结)
今天一看排名，what the，又垫底了，新初二第一YYT287.5，第二WYD120T1:最大公共子串 分类讨论+DP题目描述从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下的字符按原来的顺序组成的串是该串的字串。例如：“”, “a”, “aaa”,“bbb”,“xabb”,“xaaabbb”都是串“xaaabbb”的字串。（例子中的串不包括引号）编程求...
2018-07-19 07:32:43
414
原创 2018.07.13【省赛模拟】模拟B组 守卫者的挑战
3386. 【NOIP2013模拟】守卫者的挑战 (Standard IO)题目描述打开了黑魔法师Vani的大门，队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。擂台赛一共有N项挑战...
2018-07-14 11:49:25
307
原创 JZOJ2018.07.12【2018提高组】模拟B组 挑竹签
4269. 【NOIP2015模拟10.27】挑竹签 题目描述挑竹签——小时候的游戏夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？为了简化问题...
2018-07-14 10:34:50
333
原创 JZOJ2018.07.12【2018提高组】模拟B组 魔道研究
4270. 【NOIP2015模拟10.27】魔道研究 题目描述“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。” ——《The Grimoire of Marisa》雾雨魔理沙魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理...
2018-07-14 10:19:29
293
原创 JZOJ2530（/1812[初中]）双栈排序
题目描述Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a如果输入序列不为空，将第一个元素压入栈S1操作b如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c如果输入序列不为空，将第一个元素压入栈S2操作d如果栈S2不为空，将S2栈顶元素弹出至输出序列如果一个1~n的排列P可以通过一系
2017-11-02 14:57:07
306
原创 JZOJ2179【初中OJ】利比亚行动
题目描述：2011年3月16日以来，利比亚爆发的骚乱不断升级，已严重危及到普通民众和各国在利比亚工作的人员的安全。为了尽快救出在利比亚的同胞，根据利比亚的形势，我国政府告诉每个在利比亚的公民，如何行动才能最快地到达安全的地方，然后由我国派出的飞机、轮船、汽车接回国。假设将利比亚的地图划分为一个n行m列的长方形，待拯救的同胞小A在1行1列处，安全的目标位置在n行m列处。利比亚是一个多沙漠
2017-09-20 19:14:40
786
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人