ZFATM-CSDN博客

原创 2022.1.21

T1【GDOI2008】彩球游戏给一个4 * 4的矩阵，每个格子上有一个彩球，有红蓝绿三种颜色。有两种操作，一种是选择一个2 * 2的矩形，把矩形的球顺时针旋转。另外一种也是选择一个2 * 2的矩形，红的变蓝，蓝的变绿，绿的变红。现在给定初始状态和最终状态，问最少需要多少次操作。遇到这种有初始状态和最终状态的题，如果范围不是很大，可以考虑双向BFS。直接双向BFS即可。T2 【GDOI2008】彩球游戏给n个高度互不相同的楼，然后每个建筑上有猫，建筑i上的猫可以保护建筑j当且仅当楼i到楼j之间没有

2022-01-21 16:15:31 2706 1

原创 2022.1.19

T1 【GDKOI2006】新红黑树T2 【GDKOI2006】防御力量给n个点，还有一个A点，要求删除一些点，使得A点在剩下的点的凸包上。枚举一个点，作出与A点的直线，那么点被分为两侧，取两侧中较小的作为答案。T3 【GDOI2006】拯救亚特兰蒂斯给K个怪物，以及剑术和法术，给出每种术法能打败的怪兽，且每个怪兽只会被一种剑术和一种法术击败，学习每种术法的时间为1，求打败所有怪兽需要的时间。这种题目很容易往网络流方向想，把可以击败同一怪兽的剑术和法术连边，那么问题就变成了选择最少的点，使其覆盖

2022-01-20 21:56:30 327

原创 2022.1.20

T1【GDKOI2007】大航海有n个黑点，m个白点，有一些连接黑点和白点的边，现在从任意一个点出发，沿着边走，要求不能经过重复的点，且不能经过编号小于等于已走过的点，求经过的点的最大权值和。一个朴素的dp，设fi,j,0/1f_{i,j,0/1}fi,j,0/1表示黑点走到i，白点走到j，现在在i或j的最大价值。转移显然。但是这样时间空间都无法承受，但我们发现fi,j,0f_{i,j,0}fi,j,0由fk,j,1(k<i)f_{k,j,1}(k<i)fk,j,1(k<i)转

2022-01-20 21:55:08 262

原创【GDKOI 2021提高组DAY1】回文

DescriptionSolution马拉车跑一遍，然后对于每一个询问二分答案，这样就得到了每个回文串中心的范围，st表求最大值即可。反思比赛时想都没有想过，直接暴力。其实正解不太难想，主要就是不会马拉车。马拉车这个知识点不难，但是我已经遇到过很多次了，我居然都不会。这告诉我们，以后学新知识点，最好学以前遇到过，但又没有学会的知识点。...

2021-01-29 21:13:23 243

原创 2020CSP-J/S游记

前一天晚上睡得不是很好，十点四十就睡着了，结果十一点就行了，最要命的是，我还特别得清醒。结果一直躺倒了十二点半，终于睡着了，结果五点又醒了。有一种预感我会翻车？到了我们的老地方——纪中后，我们等了将近20分钟的CDC，然后他才带我们进去，真的好麻烦，好险只是普及组。进入考场，两边都是大熟人，也没什么好紧张的。开始比赛，T1跳过。看到T2，我懵了！这咋做？怎么连普及T2都这么难了，平静心态在想，这不就是个权值线段树吗？可是，普及T2权值线段树？这没病？结果一波心理挣扎，想了十分钟的其他方法，想不到只能

2020-11-11 19:37:02 370 1

原创【Usaco2009 gold 】过路费

Description跟所有人一样，农夫约翰以着宁教我负天下牛，休叫天下牛负我的伟大精神，日日夜夜苦思生财之道。为了发财，他设置了一系列的规章制度，使得任何一只奶牛在农场中的道路行走，都要向农夫约翰上交过路费。　　农场中由N（1 <= N <= 250）片草地（标号为1到N），并且有M（1 <= M <= 10000）条双向道路连接草地A_j和B_j（1 <= A_j <= N; 1 <= B_j <= N）。奶牛们从任意一片草地出发可以抵达任意一片的草地

2020-09-19 16:30:41 186

原创 2020.09.12【NOIP提高B组】模拟反思

过了好几天了，我才来发总结……我太弱了那天早上早餐吃得挺多的，有了上次比赛的经验，早餐要吃多。（上次比赛就是饿得不行，连打题的力气都提不起来，光荣垫底）。那天状态还算不错，T2T4都能眼切，T1不知道是什么鬼，T3题意纠结了半天，T5果断打暴力（好像没有几个人打brute force，光荣得到22.5points)最后T3在犹豫之下，打了一个暴力，光荣得到60points，实际上如果是另一种题意的话打暴力可以光荣AC。以后呢，要多思考，能打暴力就打暴力，想那天一样。...

2020-09-16 19:35:47 140

原创【2014广州市选day1】字符串距离题解

Description给出两个由小写字母组成的字符串 X 和Y ，我们需要算出两个字符串的距离，定义如下：1)我们可以在字符串的头、尾、中间插入若干空格，组成一个新的扩展串2)对X扩展成扩展串X1，对Y扩展成扩展串Y1，并且令X1和Y1具有相同的长度3)定义X1、Y1的距离为每个对应的字符的距离之和，其中两个空格的距离为0，两个非空格字符的距离为其ASCII码之差的绝对值，一个空格字符到任意非空格字符的距离为K4)对于字符串X、Y，必然存在两个等长的扩展串X1、Y1，使得X1、Y1的距离达到最少，

2020-09-12 14:21:23 773

原创【NOIP2013模拟11.7A组】图书馆题解

Description圣玛格丽特大图书馆是一座由石材砌成的角柱型高塔，是欧洲屈指可数的巨大书库。图书馆整面墙壁都是巨大的书架，书架与书架之间就像巨大的迷宫一般，以细窄的木制楼梯连结。大图书馆的最高处是一个绿意盎然的植物园，维多利加正在那无聊地看着书。今天，一如往常地，久城要爬上这迷宫般的楼梯给维多利加送讲义。图书馆墙壁上有N个平台，编号为1到N，入口为1号，植物园为N号。有M个连接两个不同平台的楼梯，爬每个楼梯需要消耗一定的体力值。楼梯一定是由低处通往高处的，为了省时间，久城只能选择上楼梯而不能下楼梯，

2020-08-16 10:11:10 325

原创方差公式化简

最近有好多道题都用到了方差，所以来发一下方差公式的化简首先我们知道方差的公式是：K=(∑i=1m(xi−p)2)∗mK=(\sum^{m}_{i=1}(x_{i}-p)^2)*mK=(∑i=1m(xi−p)2)∗mKKK即方差，ppp为平均数。把(xi−p)2(x_{i}-p)^2(xi−p)2拆开，可以得到K=(∑i=1m(xi2−xi∗p−xi∗p+p2))∗mK=(\sum^{m}_{i=1}(x_{i}^2-x_{i}*p-x_{i}*p+p^2))*mK=(∑i=1m(xi2−

2020-08-16 10:01:58 4506 1

原创【GDOI2014模拟】服务器题解

Description我们需要将一个文件复制到n个服务器上，这些服务器的编号为S1, S2, …, Sn。首先，我们可以选择一些服务器，直接把文件复制到它们中；将文件复制到服务器Si上，需要花费ci > 0的置放费用。对于没有直接被复制文件的服务器Si来说，它依次向后检查Si+1, Si+2, …直到找到一台服务器Sj：Sj中的文件是通过直接复制得到的，于是Si从Sj处间接复制得到该文件，这种复制方式的读取费用是j – i（注意j>i）。另外，Sn中的文件必须是通过直接复制得到的，因为它不可

2020-08-14 21:56:51 136

原创【GDKOI2014】石油储备计划

DescriptionData ConstraintData Constraint对于20%的数据，N<=15对于100%的数据，T<=10，N<=100，0<=si<=10000，1<=X,Y<=N，1<=Z<=10000。Solution经过观察可以发现，每一种平衡状态一定是由sum个x和sum1个x+1组成的。其中sum1=∑ainsum1=\frac{\sum a_{i}}{n}sum1=n∑aisum=n−sum1sum=

2020-08-13 21:53:21 168

原创【NOIP2015模拟10.27】魔道研究题解

改了这么久，终于把这道题A了，我太弱了感谢ZLZ巨佬的教导以及CZC帮忙调试。来写一篇题解吧。Description“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。”——《The Grimoire of Marisa》雾雨魔理沙魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理沙还是战不过帕秋莉。好在魔理沙对自己的借还和研究结果进行了记录，从而发现

2020-08-11 21:53:59 215 2

原创【NOIP2015模拟11.5】Lucas的数列题解

DescriptionSolution首先我们把整个式子化简一下：K=(∑i=1m(xi−p)2)∗mK=(\sum^{m}_{i=1}(x_{i}-p)^2)*mK=(∑i=1m(xi−p)2)∗m把(xi−p)2(x_{i}-p)^2(xi−p)2拆开，可以得到K=(∑i=1m(xi2−xi∗p−xi∗p+p2))∗mK=(\sum^{m}_{i=1}(x_{i}^2-x_{i}*p-x_{i}*p+p^2))*mK=(∑i=1m(xi2−xi∗p−xi∗p+p2))∗m也就

2020-08-05 20:40:10 978 1

原创【NOIP2015模拟11.5】旅行

DescriptionSolution经过观察，可以发现题目有一个比较不错的性质：1、一条合法的路径必须由两条路径组成，一条是奇数，另一条是偶数。所以我们可以先把每一个点到达根节点的路径求出来，深度为奇数的点放进一个aaa数组里，偶数的放进bbb数组里，再给他们分别进行排序。然后进行两两结合，先把a数组里的所有数跟b1b_{1}b1结合，把路径丢进一个小根队里。每次取出堆顶，假设取出来的是aia_{i}ai和bjb_{j}bj，那么我们就把aia_{i}ai和bj+1b_{j+1}bj+1

2020-08-05 20:14:35 272

原创【NOIP2015模拟11.5】俄罗斯套娃题解

DescriptionInputOutputSample Input10 1000Sample Output3628800Data ConstraintSolution一道比较简单的dp。对于60%的数据设fi,jf_{i,j}fi,j表示插入iii这个数，逆序对个数为jjj的方案数。那么插入iii这个数所能产生的逆序对个数为kkk,kϵ[0,i−1)k\epsilon[0,i-1)kϵ[0,i−1)。很容易理解，因为你前面已经插入了1~i-1里的数，你插入在哪一个位置都行

2020-08-05 20:00:00 416

原创【NOIP2015模拟11.2晚】舳舻牌

DescriptionCZL发明了一种叫作舳舻牌的双人纸牌游戏，据说具有提神醒脑，延年益寿的功效。这次，CZL和他的对手YYY进行游戏，CZL先手。首先，桌子上平铺着N张牌，从1至N标号。每张牌都有一个收益值，可正可负，收益值用Wi表示。每张牌对每个人都有一个诱惑值，与收益值无关。游戏开始时，CZL先手，两人交替进行游戏。轮到某个人时，ta报出一个整数X，然后拿走桌上剩余的牌中所有诱惑值小于等于X的牌（至少拿一张）。当桌上没有牌时，游戏结束。收益值总和高者获胜。我们对CZL和YYY的智商还是不怀疑的

2020-08-04 22:13:28 231

原创【NOIP2015模拟11.2晚】Lala买面包题解

Description众所周知，lala是一名非常喜欢看天线宝宝拉拉吃面包的高中生，在经过无数次的重播那堪称经典的画面之后，lala终于感到看不下去了，决定自己也去吃回面包。于是lala来到了一家面包店，但由于这家面包店的面包实在太多了，lala难以选择该买哪些面包，但这自然难不倒机智的lala，他先给每种面包定了一个美味度，并只购买美味度能表示成x^p(x，p均为大于等于2的正整数)的面包，但即便如此，lla还是难以快速地知道该买哪些面包，会买多少面包，你能帮帮他吗？Input第一行一个整数N，表

2020-08-04 15:52:40 255 1

原创【NOIP2015模拟11.2】有趣的有趣的家庭菜园

Description职业经营家庭菜园的JOI君每年在自家的田地中种植一种叫做IOI草的植物。IOI草的种子在冬天被播下，春天会发芽并生长至一个固定的高度。到了秋天，一些IOI草会结出美丽的果实，并被收获，其他的IOI草则会在冬天枯萎。JOI君的田地沿东西方向被划分为N个区域，从西侧开始的第i个区域中种植着IOI草i。在第i个区域种植的IOI草，在春天的时候高度会生长至Hi，此后便不再生长。如果IOI草i会结出果实，那么将会获得Pi的收益，否则没有收益。春天到了，查看田地样子的JOI君决定拔掉一些种植

2020-07-28 19:59:41 207

原创【NOIP2015模拟10.28B组】序章-弗兰德的秘密题解

Description弗兰德的密室里，机关上方画着两棵树的字样，机关下方是一个有数字的刻度……弗兰德最高的两棵树，只要知道两棵树的共同的相似度就行了……给定两棵有根树，可以任意删除两棵树上的节点（删除一棵节点必须保证该节点的子树内的所有节点也必须要被删除，换一种说法，删除后的树必须联通并形成一棵树，且根节点不能被删除），使得删除后的两棵树同构，这两棵树有一个共同大小，即树的size，最大化同构的树的size即为机关的答案……注：两棵同构的树要满足以下条件：1、两棵树节点个数相等。2、两棵树的以根

2020-07-24 16:34:23 204

原创【NOIP2015模拟10.28B组】终章-剑之魂题解

DescriptionMy soul of my sowrd!终焉的试炼即将到来，作为一名有修养的剑士，虽然没有习得n刀流但是二刀流还是没问题的。然而我也是个剑的收藏者，家里屯着n把剑，每一把剑都有一个灵魂值a[i]，由于一些剑之间可能有共鸣，所以我需要两把契合度最高的剑。据剑圣所说，两把编号为i,j剑的契合度为a[i] and a[j]。如何深得剑的灵魂呢？注：AND 为按位与运算，先将数转成二进制，不满位数的补全0，然后成为两个长度相同的二进制数，处理的时候，两个相应的二进制位都为1，该位的结果值

2020-07-24 15:29:52 144

原创【NOIP2015模拟10.28B组】圣章-精灵使的魔法语题解

Description【题目描述】“伦福萨”【即" ( “】和“密西卡”【即” ) “】是两种不同的精灵咒语，已知一个成功的咒语符合如下的规定：每一个密西卡之前都可以对应匹配到一个伦福萨，即为一个合法的精灵魔法咒语。方便的是，我们将“伦福萨”视为” ( “，“密西卡”视为” ) “，合法的精灵魔法咒语即为一个合法的括号序列。如：” ( ( ( ) ) ) “” ( ( ) ( ) ) “” ( ) ( ) ( ) “均为合法的魔法咒语，” ) ( “” ( ) ) ( “” ( ( “均为不合法的

2020-07-24 15:01:53 162

原创小X的佛光题解

DescriptionInputOutputSample Input3 3 11 22 31 2 31 1 33 1 3Output113Data constraintHint样例2、3、4见所附文件Solution对于90%的数据很明显是一道裸的LCA。对于每一个询问我们就先用倍增或树剖、Tarjan这些算法求出a,b的LCA和b,c的LCA。很容易可以发现，对于每一个询问，点b到这两个lca中深度较大的点必然属于答案，即depb−max(deplca,

2020-07-23 14:41:31 218

原创【NOIP2015模拟10.22】最小代价题解

Description给出一幅由n个点m条边构成的无向带权图。其中有些点是黑点，其他点是白点。现在每个白点都要与他距离最近的黑点通过最短路连接（如果有很多个黑点，可以选取其中任意一个），我们想要使得花费的代价最小。请问这个最小代价是多少？注意：最后选出的边保证每个白点到离它最近的黑点的距离仍然等于原图中的最短距离。Input第一行两个整数n，m；第二行n 个整数，0表示白点，1 表示黑点；接下来m 行，每行三个整数x，y，z，表示一条连接x和y 点，权值为z 的边。Output如果无解，

2020-07-21 14:32:50 629

原创昂贵的珍珠垂饰题解

DescriptionSolution【T2】一道坑爹的只有一个测试点的题目。经过不断地讨论，我们终于搞懂了。先不考虑不合理的方案，那么对于某一个n，它的方案最多就是，那么运用容斥原理的话，对于这一个n，它的答案就是即最后我们把每一项提出来，就可以发现这是一个等比数列。在提一下求等比数列之和的方法：设和为s，公比为q。那么它们的差就是：唉，终于把这道题调出来了，又是因为答案没有加上模数，一定要记得，一定要记得！#include<cstdio>#include&lt

2020-07-20 20:51:27 157

原创五子棋题解

DescriptionSolution状压dp，设 f[s]，s是一个二进制数，第i位为0表示1号选手没有跟i选手进行比赛，1表示已经比赛过了的最大积分。很容易得到状态转移方程：f[s]=f[s2]+(sum[1]>sum[i])*a[1][i]sum表示的是经验值，a表示的是得到的积分。哎呀！比赛时就是没有想到状压，倒是想去贪心了，以后看到数据小的可以考虑状压。#include<cstdio>#include<cstring>#include<algo

2020-07-20 16:28:56 466

原创【CQOI2008】矩阵的个数题解

DescriptionSolution一道数据很水的dp，也是唯一一道有多个测试点的题目。设f[i][j][k]表示第i行，当前第一列总和为j，第二列总和为k的方案数。很多人会问：那么第三行呢？只要我们细心观察可以发现，当我们知道第一列和第二列的总和时，我们可以直接求出第三列的总和，用一个前缀和就好了。可得状态转移方程：为当前第一列要填的数，a2为当前第二列要填的数。在此声明一点：不需要打前缀和，我比赛时本来就是五重循环就对了，结果因为打了前缀和就错了，到现在都不知道为什么错！期望得分：100

2020-07-20 16:10:18 274

原创 2020.07.18【NOIP提高组】模拟反思与总结

昨天有点膨胀，今天就会翻车。——我太弱了！今天我比得不好，只能够想到大致的思路，但是在实现方面还是有很大的差距。【T1】Description我看到第一眼，就觉得T1很简单，就简简单单地打了个dp过了样例就交了。孰不知，T1没有这么简单，还是有一些情况没有考虑到。以后比赛也一定要周全地考虑。解法：先对于每一个蛋糕，使它的 ,然后在根据为第一关键字进行排序。拍完序后，枚举h，先把1~h的蛋糕以为关键字丢进一个小根堆。然后扫一遍h+1~n，每一次把堆顶弹出，把当前的蛋糕i丢进堆里，并更新答案。期

2020-07-19 21:47:06 134

原创 2020.07.17【NOIP提高组】模拟反思总结

还行，197分，Rank.7【T1】Decription这一道题用了我好久。看到题，我一下就想到是用树型dp，转移时用插板问题。但是我对插板问题不是很熟悉，搞得我先是想了接近一个小时，调了一个小时。好险功夫不负有心人，成功地把样例都过了，最后AC100。以后一定要把每一个知识点都学透、熟悉。设为做完以根的子树排序有多少种方案。那么根据插板问题就可以得出转移方程：最后根据费马小定理求出C即可。预处理阶乘，用快速幂求出C。（注：附上费马小定理。a^(p-1)≡1(mod p) a的

2020-07-17 16:54:47 959 1

原创 NOIP2013模拟联考5】休息（rest）题解

Description休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。在某一天，某LMZ 开始整理他那书架。已知他的书有n 本，从左到右按顺序排列。他想把书从矮到高排好序，而每一本书都有一个独一无二的高度Hi。他排序的方法是：每一次将所有的书划分为尽量少的连续部分，使得每一部分的书的高度都是单调下降，然后将其中所有不少于2 本书的区间全部翻转。重复执行以上操作，最后使得书的高度全部单调上升。可是毕竟是休息时间，LMZ 不想花太多时间在给书排序这种事上面。因此他划分并翻转完第一次书之后，他想计

2020-06-20 16:40:04 290 2

原创【NOIP2013模拟联考6】秀姿势(sugata)题解

Description“蓝猫淘气三千问，看蓝猫，我有姿势我自豪！”话说能考上HYSBZ的孩纸们肯定都是很有姿势的孩纸们，但是大家普遍偏科，都只有一门科目考得好。已知HYSBZ的入学考试科目数量小于等于10^9，而有n个学生参加了入学考试。现在HYSBZ要刷人了，招生办每一次刷人会把一个科目考得好的人全部刷掉，但是最多不能刷超过K次。（刷就是不录取）而HYSBZ的校长看录取名单时，最喜欢看的就是连续都是同一个科目考得好的人。他定义完美学生序列为连续且考得好的科目都为同一门的学生序列。现在招生办主任想让你帮他

2020-06-20 16:32:02 332

原创【NOIP2013模拟联考5】小麦亩产一千八题解

Description“有了金坷垃，肥料一袋能顶两袋撒，小麦亩产一千八，吸收两米下的氮磷钾……”，话说HYSBZ（Hengyang School for Boys & Zy）学识渊博孩纸们一讲到粮食，都会想起印度那个著名的故事：国王要在第一个格子里放入一粒小麦，接下来的格子放入前面一个格子的两倍的小麦。这样所需小麦总数是巨大的，哪是不用金坷垃就能完成的任务？不过为了减轻国王的任务，那个下棋获胜的宰相换了一个要求：“我只需要你在棋盘外放一粒小麦，可以将其理解为第0 个格子，然后你需要在第一个格子里放

2020-06-20 16:17:37 599 1

原创 Why Did the Cow Cross the Road III题解

大大的四个字：数据结构！！！Description给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，对于每一对i∈[1,n],j∈[1,n]且i!=j，求满足ai<aj<bi<bj的对数.Solution这道题我们可以转换一下题意：如果比赛时可以想出来这个我一定能AC 有n条线段，给出每条线段的左端点和右端点，求有多少对线段重合又不是包含被包含的关系。这样就可以想出来一个很好的思路。首先，我们给左端点拍个序。然后我们扫一遍每一条线段，把右端点插

2020-06-15 20:09:00 342

原创【USACO 2017 December Silver】Milk Measurement题解

Description最初，农夫约翰的每头奶牛每天生产G加仑的牛奶(1≤G≤10^9)。由于随着时间的推移，奶牛的产奶量可能会发生变化，农夫约翰决定定期对奶牛的产奶量进行测量，并将其记录在日志中。他的日志中的记录如下:35 1234 -214 2345 +3第一个条目表明：在第35天，1234号奶牛的产奶量比上次测量时降低了2加仑。第二个条目表明：在第14天，2345号奶牛的产奶量比上次测量时增加了3加仑。农夫约翰只有在任何一天内做最多一次测量的时间（即每天最多做一次测量，但可能不做）。不幸的

2020-06-08 19:52:57 823

原创 2020.05.30【NOIP提高组】模拟反思

100+100+10=210 Rank.1 还行。T1题解T2题解T3题解反思：1、以后想题要想得更优化一点，这样就可以拿到更多分了。

2020-06-03 20:15:27 225

原创【USACO 2017 December Gold】A Pie for a Pie题解

DescriptionBessie and Elsie have each baked N pies (1≤N≤10^5). Each of the 2N pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie. Bessie is thinking about giving one of her pies to Elsie. If Elsie

2020-06-03 20:09:57 385

原创【USACO 2017 December Gold】Haybale Feast

DescriptionInputThe first line contains the integers N and M, the number of haybales and the minimum total flavor the meal must have, respectively. The next N lines describe the N haybales with two integers per line, first the flavor F and then the spic

2020-06-03 20:03:46 289

空空如也

空空如也