搜索结果
查询Tags标签： 洛谷，共有 252条记录-
洛谷 P3384 【模板】轻重链剖分/树链剖分
【模板】轻重链剖分/树链剖分 题目描述 如题，已知一棵包含 \(N\) 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上…
2022/7/23 6:25:22 人评论 次浏览 -
《关于电话号码是绿题这件事》
题目：P2037 电话号码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 我服了 鄙人看到这是一道绿题，开心地点了进去。 然后惊奇地发现 这**根本就是道蓝题啊，我******* 真不知道洛谷干什么吃的 终于，三天后，本蒟蒻完成了这道题（本就不富裕的发量雪上加霜QAQ） 这道题…
2022/7/22 23:27:15 人评论 次浏览 -
洛谷-P2254 瑰丽华尔兹
瑰丽华尔兹 \(dp\) + 单调队列优化 \(dp[k][i][j]\) 表示在第 \(k\) 次倾斜后 \(x = i\) 且 \(y = j\) 的位置上，能够滑动的最长距离，第一纬可以直接用滚动数组消除 显然每次倾斜都要对所有的状态进行更新，分四个方向进行更新，以向右滑动为例，有状态转移方程： \[dp[…
2022/7/15 23:25:33 人评论 次浏览 -
洛谷 P5461 赦免战俘
题目背景借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！题目描述现有 2^n\times 2^n (n\le10)2n2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长…
2022/7/12 6:22:21 人评论 次浏览 -
洛谷 P3350 - [ZJOI2016]旅行者（分治+最短路+复杂度分析）
洛谷题面传送门 肿么没有人证明复杂度，那我来证一个。 考虑分治，每次像猫树那样处理一个分治区间 \([l_x,r_x],[l_y,r_y]\) 表示当前处理 \(x_1,x_2\in[l_x,r_x]\)，\(y_1,y_2\in[l_y,r_y]\) 范围内的所有询问。处理当前层的询问是好办的，考虑令 \(mid=\lfloor\dfrac{l…
2022/7/7 23:20:25 人评论 次浏览 -
洛谷 P4298 [CTSC2008]祭祀 题解--zhengjun
思路 第一问 第一问与YbtOJ「图论」第1章 二分图匹配 J. 祭祀一模一样。 考虑处理出原 dag 图的两两点之间能否可达（可用 Floyd），然后题中是求最大的若干点之间没有两两可达的点对。 那么建出二分图之后，发现如果出现一对匹配，那么相当于这两个点里面有一个不能选了，…
2022/6/28 23:32:20 人评论 次浏览 -
洛谷 P4145 上帝造题的七分钟 2 / SP2713 GSS4
Description 给出一个长度为 \(b\) 的数列 \(a\)，要进行 \(m\) 次操作，每次操作输入 \(k\)， \(l\)， \(r\)，要求支持以下两种操作：\(k=0\) 表示给 \([l,r]\) 中的每个数开平方（下取整）。\(k=1\) 表示询问 \([l,r]\) 中各个数的和。数据中有可能 \(l>r\)，所以遇…
2022/6/23 23:20:46 人评论 次浏览 -
洛谷P7960 [NOIP2021] 报数 （筛法）
禁止报的数的生成规则与埃式筛法类似，考虑用筛法预处理可以报出的数字列表和不可报出的数字，从而 O(1) 回答每一组询问。 用check函数判断数字中是否含有7，用nx[i]记录数字i的下一个合法数。1 #include<bits/stdc++.h>2 using namespace std;3 const int N=1e7+1…
2022/6/17 23:28:22 人评论 次浏览 -
洛谷-P4011 孤岛营救问题
孤岛营救问题 bfs + 状态压缩 对钥匙的状态进行压缩，然后 bfs 剪枝搜索 #include <iostream> #include <cstdio> #include <queue> using namespace std; int dp[20][20][1 << 16 | 1]; int dr[20][20][20][20]; int dor[20][20]; const int xi[…
2022/6/11 23:54:11 人评论 次浏览 -
洛谷 P6291 [eJOI2017]骆驼 题解--zhengjun
题目传送门 思路 一看就是构造题，显然要分成若干块 \(5\times5\) 的小块，然后发现对于一个小块中，只有最中间的那格可以从别的小块中一步跳进来。 然后我们打一个爆搜，打出从当前小块的中间走到各个方向相邻的小块的方案。 这样就可以在小块间移动了。 由于我们需要把…
2022/6/11 23:50:53 人评论 次浏览 -
洛谷P2627 [USACO11OPEN]Mowing the Lawn G （单调队列优化DP）
一道单调队列优化DP的入门题。 f[i]表示到第i头牛时获得的最大效率。 状态转移方程：f[i]=max(f[j-1]-sum[j])+sum[i] ,i-k<=j<=i。j的意义表示断点，因为不能连续安排超过k只牛，肯定要在中间断开一处。 max中f[j-1]-sum[j]只和j相关，我们可以对其做递减单调队列，…
2022/6/11 23:50:52 人评论 次浏览 -
洛谷 P1024一元三次方程求解题解--zhengjun
题目描述 有形如：\(ax^3+bx^2+cx^1+dx^0=0\) 这样的一个一元三次方程。给出该方程中各项的系数(\(a,b,c,d\)均为实数)，并约定该方程存在三个不同实根(根的范围在\(-100\)至\(100\)之间)，且根与根之差的绝对值 \(\ge 1\)。要求由小到大依次在同一行输出这三个实根(根与根…
2022/6/10 23:20:20 人评论 次浏览 -
洛谷 P1023税收与补贴题解--zhengjun
题目背景 每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数） 对于某些特殊商品…
2022/6/10 23:20:18 人评论 次浏览 -
洛谷P1064金明的预算方案题解--zhengjun
题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过\(N\)元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类…
2022/6/10 23:20:17 人评论 次浏览 -
洛谷 P1062数列题解--zhengjun
题目描述 给定一个正整数\(k(3≤k≤15)\),把所有\(k\)的方幂及所有有限个互不相等的\(k\)的方幂之和构成一个递增的序列，例如，当\(k=3\)时，这个序列是： \(1,3,4,9,10,12,13,\cdots\) （该序列实际上就是：\(3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…\)） 请…
2022/6/10 23:20:17 人评论 次浏览
