Q779’s Blog

洛谷P4310 绝世好题 题解 题目链接：P4310 绝世好题 题意：给定一个长度为 \(n\) 的数列 \(a_i\) ，求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\)，满足 \(b_i \& b_{i-1} \ne 0\)，其中 \(2\leq i\leq k\)， \(\&\) 表示位运算取与。 设 \(dp[i][j]\) 为前 \(i\) 个数的每个子序列的最后一个数第 \(j\) 位为 \(1\) 的最大长度 然后对于每个数枚举一遍dp，再转移一遍dp即可 注意到这个递推式可以滚动数组，然后搞一搞就好了 答案就是 \(\max(dp[i][j])\) 时间复杂度 \(O(n \log \max(a_i))\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)() int n,res,dp[35]; signed main() ...

洛谷P4342 [IOI1998]Polygon 题解 题目链接：P4342 [IOI1998]Polygon 题意：多边形是一个玩家在一个有 \(n\) 个顶点的多边形上的游戏，如图所示，其中 \(n=4\) 。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。 第一步，删除其中一条边。随后每一步： 选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。 游戏结束时，只有一个顶点，没有多余的边。 如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。结果是0。 这里每条边的运算符旁边的数字为边的编号，不拿来计算 编写一个程序，给定一个多边形，计算最高可能的分数。 \(3 \le n\le 50\) 对于任何一系列的操作，顶点数字都在 \([-32768,32767]\) 的范围内。 容易发现我们需要断环为链，然后区间dp 注意到存在负数，而负负得正，说明不是简单的区间dp 不难发现两个负的极小值之乘积对答案有更大贡献 考虑维护区间最大值的同时维护区间最小值 即，设...

洛谷P4390 [BOI2007]Mokia 摩基亚 题解 题目链接：P4390 [BOI2007]Mokia 摩基亚 题意：摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户 C 的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。 在定位系统中，世界被认为是一个 \(w×w\) 的正方形区域，由 \(1\times 1\) 的方格组成。每个方格都有一个坐标 \((x,y)\)，\(1\leq x,y\leq w\)。坐标的编号从 \(1\) 开始。对于一个 \(4\times 4\) 的正方形，就有 \(1\leq x\leq 4\)，\(1\leq y\leq 4\)（如图）： 请帮助 Mokia 公司编写一个程序来计算在某个矩形区域内有多少名用户。 这道题的题解区一片互相抄袭的烂货，实在受不了了就来水一篇题解 可以发现这道题目就是个二维数点问题，不知道的推荐看看 这篇博客 然后这道题目，我们不能用归并排序来做 为什么呢？因为这个题目它还有一...

洛谷P4395 [BOI2003]Gem 气垫车 题解 题目链接：P4395 [BOI2003]Gem 气垫车 题意：给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。 \(N \le 10000\) 考虑树形dp 设 \(dp[u][i]\) 表示结点 \(u\) 的权值为 \(i\) 时其所在子树的最小总权值 则有 \[ dp[u][i]=\min_{k \ne i}(dp[v][k])+i \] 那么这个权值最大有多少呢 不难发现最多为 \(\left\lceil\log n\right\rceil + 1\) 那么就很简单了，时间复杂度 \(O(n\log n)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f #define N (int)(2e4+15) struct Edge { int u,v...

洛谷P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 题解 题目链接：P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 题意：村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x,y)\)，然后对于 \(x\) 到 \(y\) 的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。 然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮 显然这是板子题 我们利用树上差分的思想，自底向上统计答案 同时一路合并每个节点的线段树，即可 本文主要讲一讲为什么数组要开 1e5*70 左右 首先 \(z \le 10^5\) ，取最大值 \(Z=10^5\) （权值线段树嘛） 其次，动态开点线段树一次从根节点到叶子节点的修改操作 即 modify() 新建的点数为 \(O(\log Z)\) 的，在本题中 \(\log Z \approx \log_2 10^5 \approx 17\) 而观察代码可以发现，我们做树上差分的时候，一次差分会...

洛谷P5020 [NOIP2018 提高组] 货币系统 题解 题目链接：P5020 [NOIP2018 提高组] 货币系统 题意：在网友的国度中共有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\) 、面额数组为 \(a[1..n]\) 的货币系统记作 \((n,a)\) 。 在一个完善的货币系统中，每一个非负整数的金额 \(x\) 都应该可以被表示出，即对每一个非负整数 \(x\) ，都存在 \(n\) 个非负整数 \(t[i]\) 满足 \(a[i] \times t[i]\) 的和为 \(x\) 。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 \(x\) 不能被该货币系统表示出。例如在货币系统 \(n=3 ,a=[2,5,9]\) 中，金额 \(1,3\) 就无法被表示出来。 两个货币系统 \((n,a)\) 和 \((m,b)\) 是等价的，当且仅当对于任意非负整数 \(x\) ，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 现在网友...

洛谷P5110 块速递推 题解 题目链接：P5110 块速递推 题意：给定一个数列 \(a\) 满足递推式 \[ a_0=0,a_1=1 \\a_n = 233a_{n-1}+666a_{n-2} \] 求 \(a_n \bmod (10^9+7)\) 多组询问 这个题是有个循环节的，正好是 \(10^9+6\) ，据出题人说是凑好的 关于循环节怎么求的我也不太清楚，先留个坑，研究好了就补上来 upd.20220721 现在知道怎么求循环节了，详见本文最后 也就是，如果数列 \(a_n\) 在模 \(M\) 意义下存在循环节 \(p\) ，则有 \(a_n \equiv a_{n\,\bmod\, p} \bmod M\) 本题的解法就是手推通项公式 具体方法如下 对于二阶线性递推数列 \[ a_0=A,a_1=B \\a_n = pa_{n-1}+qa_{n-2} ,n\ge 2 \] 考虑使用特征方程求解 \(a_n=pa_{n-1}+qa_{n-2}\) 的特征方程为 \[ x^2=px+q \] 可以求出两个特解（不一定是实数） \(x_1,x_2\) ，则 \[ a...

洛谷P5322 [BJOI2019] 排兵布阵 题解 题意：小 C 正在玩一款排兵布阵的游戏。在游戏中有 \(n\) 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 \(m\) 名士兵，可以向第 \(i\) 座城堡派遣 \(a_i\) 名士兵去争夺这个城堡，使得总士兵数不超过 \(m\)。 如果一名玩家向第 \(i\) 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 \(i\) 分。 现在小 C 即将和其他 \(s\) 名玩家两两对战，这 \(s\) 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 \(s\) 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。 由于答案可能不唯一，你只需要输出小 C 总分的最大值。 设 \(dp[i][j]\) 表示第 \(i\) 个城堡放 \(j\) 个士兵可以获得的最大分数 显然我们会选择恰好为某名玩家放的兵数 \(x\) 的 \(2x+1\) ，不然多的都是浪费 因此这就是个类似背包的问题 没什么难度，直接看代码就能明白了吧（逃 时间复杂度 \(O(nms)\) ...

洛谷P5365 [SNOI2017] 英雄联盟 题解 题目链接：P5365 [SNOI2017] 英雄联盟 题意：正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。 现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！ 小皮球只会玩 \(\text{N}\) 个英雄，因此，他也只准备给这 \(\text{N}\) 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。 这 \(\text{N}\) 个英雄中，第 \(\text{i}\) 个英雄有 \(K_i\) 款皮肤，价格是每款 \(C_i\) Q 币（同一个英雄的皮肤价格相同）。 为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。 比如，小皮球共有 5 个英雄，这 5 个英雄分别有 \(\text{0,0,3,2,4}\) 款皮肤，那么，小皮球就有 \(3 \times 2 \times 4 = 24\) 种展示的策略。 现在，小皮球希望自己的展示策略能够至少达到 \(\text{M}\) 种，请...

洛谷P5658 [CSP-S2019] 括号树 题解 题目链接：P5658 [CSP-S2019] 括号树 题意：略。 注意到本题中，链的部分分很高，就先考虑这种情况 不难发现，每个与 \(l\) 配对的右括号 \(r\) 的贡献为 \(dp[r]=dp[l-1]+1 = dp[fa[l]]+1\) 则 \(k_i = dp[i] + \sum dp[j]\) ，\(j\) 是 \(i\) 的祖先结点 显然这个性质可以推广到树上 这样维护一个括号栈就好了，怎么维护呢？ 为了防止栈在回溯过程中被破坏，考虑回溯时执行相反操作 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(5e5+15) int n,fa[N],sum[N]; char val[N]; struct Edge { int u,v,next; }e[N]; int pos=1,head[N],...

洛谷P5656 【模板】二元一次不定方程 (exgcd) 题解 题目链接：P5656 【模板】二元一次不定方程 (exgcd) 题意：给定不定方程 \[ ax+by=c \] 若该方程无整数解，输出 \(-1\)。 若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 \(x\) 的最小值，所有正整数解中 \(y\) 的最小值，所有正整数解中 \(x\) 的最大值，以及所有正整数解中 \(y\) 的最大值。 若方程有整数解，但没有正整数解，你需要输出所有整数解中 \(x\) 的最小正整数值， \(y\) 的最小正整数值。 正整数解即为 \(x, y\) 均为正整数的解，\(\boldsymbol{0}\) 不是正整数。 整数解即为 \(x,y\) 均为整数的解。 \(x\) 的最小正整数值即所有 \(x\) 为正整数的整数解中 \(x\) 的最小值，\(y\) 同理。 \(1\le a,b,c\le 10^9\) 根据裴蜀定理， 对于 \(x,y\) 的二元一次不定方程 \(ax+by=c\) ，其有解的充要条件为 \(\gcd(a,b) \mid c\) ...

洛谷P5851 [USACO19DEC]Greedy Pie Eaters P 题解 题目链接：P5851 [USACO19DEC]Greedy Pie Eaters P 题意： Farmer John 有 \(M\) 头奶牛，为了方便，编号为 \(1,\dots,M\)。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 \(N\) 个派请奶牛吃，这 \(N\) 个派编号为 \(1,\dots,N\)。第 \(i\) 头奶牛喜欢吃编号在 \(\left[ l_i,r_i \right]\) 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 \(i\) 头奶牛有一个体重 \(w_i\)，这是一个在 \(\left[ 1,10^6 \right]\) 中的正整数。 Farmer John 可以选择一个奶牛序列 \(c_1,c_2,\dots,c_K\)，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 \([l_{c_i},r_{c_i}]\) 中所有剩余的派。F...