wweiyiのblog

【解题报告】洛谷 P4753 River Jumping 原题链接 https://www.luogu.com.cn/problem/P4753 题目大意 一条宽度为 nnn 的河上，有 mmm 块石头，每块石头距离起点（坐标为0）有一个距离，我们要从起点跳到终点，通过一些方法使得跳到每个石头上一次，最终回到起点，每次跳的距离有一个下限 sss ,输出一种可能的方案 思路 看到这道题目，我们首先关注到的是一个下限 sss ，为什么我们要关注这个呢？因为，我们可以发现，如果你想跳的石头与你的距离 d≥sd \ge sd≥s 你是不是就可以随便跳？ 于是我们自然而然地想，我们是不是可以使用贪心算法？ 每次跳，跳到一个距离自己第一个 ≥s\ge s≥s 的石头上，一直向右，到右边了之后，我们再向左重复上述过程。因为在能完成的情况下我们跳到最右边的时候，离左边的距离一定大于 sss ，所以我们可以跳过去，然后再跳回来，反复横跳，最后就能完成了 那么，我们还要处理不能完成的情况，那么我们什么情况不能完成呢？ 最左边的石头和 000 距离小于 sss ，或者最右边的石头和 nnn 的距离...

【解题报告】洛谷P3275 糖果 原题链接 https://www.luogu.com.cn/problem/P3275 思路 在这样天气寒冷的日子里，怎么能不做题呢~！ 天气阴凉，我怀着激动的心情打开了这道题目 题意大概满足一堆要求，让你求一个满足要求的所有的变量的和 自己看去吧 然后我们读题发现，这不就是一个差分约束吗？ 待会？ 差分约束满足的形式是这样的 xi−xi′≤yix_i-x_{i'} \le y_ixi​−xi′​≤yi​ 所以题目中不少于不多于的都非常好搞，直接连边就可以了 那剩下的怎么搞呢？ 首先等于，等于的话我们可以双向连边，一个不大于，一个不小于，不就是等于了吗？ 然后后面呢？ 我们实际上可以他们变成 A≤B−1A \le B-1A≤B−1 , B≤A−1B \le A-1B≤A−1 之类的，这样就可以实现小于了，具体这样做的原因是因为 A,BA,BA,B 只能是整数啊喂 然后我们用一个 SPFASPFASPFA 跑就可以了 有一个玄学的东西，就是我们在跑的时候要对于超级源点从大边向小边连边，不然会被卡掉，或者连边的同时把连得边都 pus...

【CSP-S刷题班】Day3 A 题目描述 可持久化是OI比赛中的一个常规考点，部分毒瘤的出题人可能会将一个问题强行加上可持久化 在本题中，你需要维护一个可持久化的数组，具体的，你有一个长度为 nnn 的数组 a1,a2,...,ana_1,a_2,...,a_na1​,a2​,...,an​，你需要在这个数组上进行 mmm 次修改或询问，修改或询问的具体内容如下： 1 u v，将 aua_uau​ 的值修改为 vvv 2 u t，询问 aua_uau​ 在第 ttt 次操作后的值是多少 为了防止选手通过离线方式通过此题，本题部分测试点设置了强制在线，详见输入格式 输入格式 第一行三个整数 n,m,optn,m,optn,m,opt 第二行 nnn 个整数，第 iii 个整数表示 aia_iai​ 接下来 mmm 行，每行三个整数 1,ui,vi1,u_i,v_i1,ui​,vi​ 或 2,ui,ti2,u_i,t_i2,ui​,ti​，表示一次操作或询问。 本题部分测试点设置强制在线，如果 opt=1opt=1opt=1，那么每次操作的 ui,vi,tiu_i,v_i,t_...

【解题报告】CF815C 题目大意 Kellen想要买 nnn 件东西，她有 bbb 块钱，实际上，超市也就只有 nnn 件东西，超市为Kellen准备了 nnn 种优惠券，但是对于除第一件商品以外的优惠券，必须在使用第 xix_ixi​ 张优惠券之后方才可以使用，你能帮她了解一下在不超过她手上的钱的情况下，她最多能买多少东西 输入第一行两个整数，nnn 和 bbb 从第二行到第 n+1n+1n+1 行，除第二行前两个整数之外，后面的每行三个整数 ci ,di c_i \space,d_i \spaceci​ ,di​  和 xix_ixi​ 字母意义皆如题目所示 思路 这道题目，我们可以从必须使用 xix_ixi​ 之后才可以使用 iii 知道，这个类似于没有上司的舞会，或者是选课，因此我们要使用树形DP 按照之前的惯例，我们可以设置如下状态 设置 f[i][j][0/1]f[i][j][0/1]f[i][j][0/1] 表示在以 iii 为根的子树中，选择 jjj​ 个物品，在第 iii 个商品上面是否使用优惠券可以最多购买东西的数量 然后我们根据定义，我们可以列出如下初始状...

https://view.csslcloud.net/api/view/index?roomid=4ECE5F1C87E8367B9C33DC5901307461&userid=068A5B0B59D5CDBC

【解题报告】洛谷P3959 宝藏 原题连接 https://www.luogu.com.cn/problem/P3959 思路 这道题目，本来今天yht老师讲了个大力搜索，什么模拟退火来着，但是最后，还是回归了本源，状态动态规划 首先我们这么想 我们每条路肯定只联通一次，然后我们对于可以钦定一个集合S 用来表示某个点选不选的最小代价 但我们要进行状态转移，我们要从一个点走到另一个点，然后要用某个节点的深度来计算代价 所以我们设置f[x][S][d]f[x][S][d]f[x][S][d]来表示点x在S中并且深度为d的时候的最小代价 因为是从上一个状态走下来的，所以我们要加上这条边 则状态转移方程为 f[x][1<<(x−1)∣S][d]=min{sum+dis[y]+g[y][x]}f[x][1<<(x-1)|S][d]=min\{sum+dis[y]+g[y][x]\}f[x][1<<(x−1)∣S][d]=min{sum+dis[y]+g[y][x]} 其中y和x表示上次的点和这次的点，sum表示这次以前的最小代价 dis数组在dfs的时候...

CSP-S2020题目整理 T1 儒略日 这道题目在考场上卡爆我 然后我就废了 这道题实际上就是考察一个对于闰年和平年的研究 我们可以先预处理前四百年的情况，然后对于在1582年之前的和1582年之后的分类讨论一下，然后这样就可以直接加减了 用一个函数来返回月份的天数似乎比较方便 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long longusing namespace std;const int maxn=146097;int q;int y[maxn],m[maxn],d[maxn...

【游记】CSP-S2021 退役记 Day -1 今天早上一起床，外面便是阴森森的（PS：似乎暗示了今天的考试题目），朝阳似乎没有漏出脸来，但是还是给积雨云染上了一层淡淡的红妆。雨慢慢地下着，布满水洼的地上在脚的作用下溅起了一朵朵水花，我走向了教室明德楼 拿起了笔袋，拿起了《信息学奥赛一本通<初赛篇>》，我向大成楼赶去，等我再打着伞走到楼下的时候，天似乎变得不是那么羞涩，平静起来了，成熟起来了。 走过林荫小道，同学们来来往往，陆陆续续地赶向明德楼教室，准备开始早自习，准备一天的周考，而我恰恰相反，与他们相向而行，走向了机房 机房还是那个味道，但是比原来淡了许多，灰尘似乎在雨水之下收起了他的猖狂，安静地待在地上，无论机房内，还是机房外 打开灯，打开电脑，一阵阵熟悉感扑面而来，恩，这才是机房啊，我的生活方式 先打开了洛谷有题，做一做历年的真题，然后发现了一个规律，2013年和2020年初赛的题目有一些重复，于是我想，那是不是我应该看一下2014年的题目，我想着，确实，我也这么做了。 慢慢地，时间到了7：20，我去食堂吃了一个早饭，一碗相对于这鬼天气热腾腾的西红柿鸡蛋面，内...

【全程NOIP计划】初赛 计算机基础 IT发展历史 第一台计算机：埃尼阿克 ，1946 应用：计算，数据储存处理，通信，辅助工作等 第一个程序员：Ada（女），为了纪念她，命名了一个编程语言是她的名字 计算机：图灵奖 数学：菲尔兹奖 物理化学生物经济文学和平：诺贝尔奖 ACM（美国计算机协会），IEEE（美国工程院学会），臭名远扬CCF 【NOIP2018】下列关于图灵奖的说法中，正确的有（ ）。 A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。 B. 目前获得该奖项的华人学者只有姚期智教授一人。 C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。 D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。 【解析】答案选择BCD，图灵奖是又ACM设立的，其它的没得一点问题 计算机组成 冯诺依曼结构（储存程序原理）——计算机的基础模型 字长：32位和64位；意思指的是每次指令可以处理32位的数据或者64位的数据 主频：2.4GHz，指的是计算机处理的速度 内存：8GB，临时存放东西，也叫RAM，随机存储设备，断电丢失 位Bit：一个...

【解题报告】luoguP2158 仪仗队 原题链接：https://www.luogu.com.cn/problem/P2158 思路 这道题目经过分析，我们可以发现一个结论 即对于每一个点(x,y)(x,y)(x,y)，如果能被看到，则一定不存在一个点(xm,ym),m,xm,ym∈Z，(\dfrac x m,\dfrac y m),m, \dfrac x m,\dfrac y m\in Z，(mx​,my​),m,mx​,my​∈Z， 因为他们属于同一斜率k=yxk= \dfrac y xk=xy​ 观察可以得到，因为他们没有一个 mmm 可以使上面的上面的式子成立，即gcd(x,y)=1gcd(x,y)= 1gcd(x,y)=1 然后直接求gcd的话肯定是不行的，然后我们继续看 实际上对于一个固定的 xxx ，我们要统计的是一个数字 y∈[1,n]y\in [1,n]y∈[1,n] 让他们互质，所以我们要求的是x的欧拉函数 代码 123456789101112131415161718192021222324252627282930313233343536#include &...