题解034f agc
【luogu题解】P5461 赦免战俘
一、题目 现有 \(2^n\times2^n\ (n≤10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵,每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免,剩下 3 个小 ......
P8907 [USACO22DEC] Making Friends P 题解
明明看着不难的题目,却意外的卡人。 思路 考虑两头奶牛可以成为朋友条件是什么。 存在一条路径连接这两头奶牛。 且除去端点外的路径上的所有点的编号小于两端点的较小值。 充分必要性都比较显然。 如何维护。 我们可以从小到大加入点,维护这些路径。 对于每个点维护一个 \(\text{set}\)。 表示这 ......
【luogu题解】P9749 [CSP-J 2023] 公路
\(Meaning\) \(Solution\) 这道题我来讲一个不一样的解法:\(dp\) 在写 \(dp\) 之前,我们需要明确以下几个东西:状态的表示,状态转移方程,边界条件和答案的表示。 状态的表示 \(dp[i]\) 表示到达第 \(i\) 个站点所需要的最少钱数, \(w[i]\) 表示 ......
[IOI2015] Teams 题解
妙妙题。 不难发现,我们对于每个 \(k\) 取出的人都是满足 \(a_i \leq k \leq b_i\) 的。 经典的,我们直接将 \((a_i, b_i)\) 转化到二维平面上,将它转化成一个二维数点问题。 我们对于每一个询问,都使 \(k\) 有序,从小到大贪心的选择,也就相当于 \(x\ ......
【模板】最小度限制生成树 题解
其他的题解感觉都好高级,分享一种好想且好实现的方法。 我们可以先把点 \(s\) 和与其相连的边都删除,我们发现剩下的部分变成了一些连通块。 我们不难发现,当要求与 \(s\) 点相连的边的个数为 \(k\) 时,我们的连通块个数显然是 \(k\) 的。 接下来这个问题就转化成了:\(n - 1\) ......
P9870 题解
blog。NOIP2023 T3,特殊性质题。 什么是特殊性质题?就是题目给出了你极其神秘的性质,从而引导你想出正解。 本篇题解将从部分分的角度,一步步讲述部分分与正解的关系。这样看的话,本题会变得十分简单。 \(\text{Task }1\sim7\),\(O(Tnm)\) 首先转换题意。\(\f ......
P9868 题解
blog。NOIP2023 T1。 可以对字符串随意交换,即可以重排每个单词。对于询问 \(i\),最优方案显然是将 \(\forall j\ne i\) 的 \(w_j\) 重排至字典序最大,将 \(w_i\) 重排至字典序最小。 这件事情本质是将 \(w_i\) 与 \(\min\limits_ ......
【AGC】鸿蒙应用软件包上传问题解析
【问题背景】 近期收到了一些反馈,一些鸿蒙元服务开发者在发布应用市场的过程中,上传.app包时遇到了不同的报错,导致上传失败,下面来看一下这些报错的具体原因,如何正确打包上传。 【问题描述1】 HarmonyOS元服务软件包上传后,提示“软件包解析失败,请重新上传”,错误详情(5) 【问题 ......
UVA1396 Most Distant Point from the Sea 题解
Link UVA1396 Most Distant Point from the Sea Question 在大海的中央,有一个凸 \(n\) 边形的小岛,求出岛上离海边最远的一个点到海边的距离 Solution 二分答案,然后去验证是否有一个点,距离海的距离大于 \(mid\) 如何验证? 把每条 ......
CF1894 A Secret Sport 题解
Link CF1894 A Secret Sport Question 其实这个翻译有一点点小问题,正确的翻译应该是这样 \(A,B\) 两人玩游戏,游戏规则如下: 整场游戏有多轮,每轮游戏先胜 ,\(X\) 局的人获胜,每场游戏先胜 ,\(Y\) 轮的人获胜。 Solution 引用 haohao ......
T401305 平面划分(easy) 题解
Link T401305 平面划分(easy) Solution 平面上 \(n\) 条直线所划分处的区域最大个数 \(L_n\) 是多少 我们考虑假设已经有\(n-1\) 条直线,我们需要画一条直线,这条直线最多和 \(n-1\) 条直线相交产生 \(n\) 个新的区域 所以我们得到了 \[\be ......
[ABC328D] Take ABC 题解
链接 如果只是扫一遍肯定是不行的,所以我们使用一个栈,遇到 C 就判断栈顶的两个元素是不是分别为 B 和 A。这样就能做出来这道题了。 代码 #include<bits/stdc++.h> using namespace std; string s; char stk[200010]; int ma ......
AGC 020~039 记录
不想写 CF。 AGC020 D. Min Max Repetition 要令连续的相同字符个数的最大值最小,可以直接贪心将 A 和 B 尽可能分开,得出答案 \(k=\lfloor\frac{A+B}{\min(A,B)+1}\rfloor\)。 接下来要在这个基础上构造字典序最小的答案。 我们显 ......
【树链剖分】P3401 洛谷树 题解
P3401 考虑先将路径权值进行转化,因为很难对路径直接进行统计。考虑如何表示出这条路径的权值。记 \(s_i = \oplus_{j \in \text{path}(1, i)} w_j\),其中 \(\text{path}(i, j)\) 表示 \(i\) 到 \(j\) 的路径上的边集。则 \ ......
P9620 歌姬 题解
感觉题解做法都好神秘。 来一个容易理解,通俗易懂的树剖解法。 思路 容易发现原问题等价于维护一个虚树。 每一次询问虚树的根的所有儿子的最大值。 要求链修。 容易发现仅仅动态维护根是好做的。 我们用一个 \(\text{set}\)。 每次维护 \(\text{dfs}\) 的最小值和最大值。 对于这 ......
【题解】Atcoder snuke21_e Tournament
传送门:https://atcoder.jp/contests/snuke21/tasks/snuke21_e?lang=en 题意: 求所有 $n$ $(n \leq 100000)$ 个点的竞赛图中强连通分量个数之和。 思路: 竞赛图的好性质:对竞赛图 $SCC$ 缩点之后,所有点有一个拓扑序, ......
【线段树优化 dp】AT_dp_w Intervals 题解
AT_dp_w 先不看数据范围,考虑 dp。 令 \(f_i\) 表示前 \(i\) 个字符且强制第 \(i\) 个字符为 \(1\) 的最大分数。 则 \(f_i = \max(f_{j - 1} +\sum\limits_{r_k\ge i\ge l_k\ge j}a_k)\)。 这个是一份 \ ......
【区间 dp】UVA1331 最大面积最小的三角剖分 Minimax Triangulation 题解
UVA1331 区间 dp。 有一个很经典的问题:给定一个凸多边形,求它的最优三角剖分,对每个三角形规定一个权函数 \(f(i,j,k)\),求所有剖分方案中最大的权值。 发现这个东西不好直接入手。但是这个东西与矩阵最优链乘是相似的。考虑区间 dp。因为随意的转移是难以维护的,维护区间信息就等于强制 ......
CF1898 D Absolute Beauty 题解
Link CF1898 D Absolute Beauty Question 给出两个长度都为 \(n\) 的数组 \(a,b\) ,我们可以任意选择两个数 \(i,j\) 交换 \(b_i\) 和 \(b_j\) 一次,或者不换 求 \(\sum\limits_{i=1}^n |a_i-b_i|\ ......
[题解]CF1899D Yarik and Musical Notes
思路 暴力化简公式题。 假定 \(b_{i}^{b_j} = b_{j}^{b_{i}}\) 成立,那么有: \[2^{a_i \times 2^{a_j}} = 2^{a_j \times 2^{a_i}}\\ a_i \times 2^{a_j} = a_j \times 2^{a_i}\\ \ ......
【题解】JLOI2016 - 成绩比较
【题解】JLOI2016 - 成绩比较 https://loj.ac/p/2026 是我会的题,所以感觉难度不如 noip T3T4。 设 \(f_{i,j}\) 表示考虑到前 \(i\) 门课,有 \(j\) 人被 B 碾压。 转移,设这轮中有 \(k\) 个原本被碾压的人不再被碾压,则相当于从 ......
AGC054D (ox)
有点厉害题。对于括号序列和序列上邻项交换的问题的处理有一些启发。 首先考虑如果没有 ox 怎么样。容易发现,我们从前往后记录左括号与右括号的个数差,这个差值一旦为负就立刻从后面提一个右括号过来(一路交换过来),这个做法一定是最优的,并且是唯一最优的操作方法。这样理解比较感性,实际上我们可以对每个分界 ......
板刷 AGC
从 AGC001A 开始。 [AGC001A] BBQ Easy 显然排序后所有奇数位相加即为答案。 #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #inc ......
CF1898 C Colorful Grid 题解
Link CF1898 C Colorful Grid Question 给出一个 \(N\times M\) 的网格图 给每一条边染色(R/B),需要存在一条长度为 \(K\) 的路径从 \((1,1)\) 到 \((N,M)\),路径允许重复通过一个节点。 Solution 非常有意思的一道题 ......
CF1898 B Milena and Admirer 题解
Link CF1898 B Milena and Admirer Question 给出一个长度为 \(n\) 的序列 \(a\) ,我们可以做一种操作使得 \(a\) 非降,操作是: 对于一个 \(a_i\) 选择一个整数 \(0 \le x \le a_i\) ,用两个数 \(x,(a_i-x) ......
CF1899 G Unusual Entertainment 题解
Link CF1899 G Unusual Entertainment Question 给出一个排列 \(p_i\) 和一棵树,给出 \(Q\) 组询问,每组询问 \([L,R,x]\) 表示求 \(p_L \sim p_R\) 上是否存在 \(p_i\) 在 \(x\) 的字数上。 Soluti ......
noip2023 题解(民间数据)
P9868 [NOIP2023] 词典(民间) 直接把每个串 \(w_i\) 都从大到小/从小到大排一下,记作 \(a_i,b_i\)。如果 \(b_i\) 小于除了 \(i\) 之外的所有 \(a_i\),说明可以,否则不行。求一个前后缀最大值即可。复杂度 \(\mathcal{O}(26n+nm ......
P9713 「QFOI R1」抱抱 题解
P9713 「QFOI R1」抱抱 题解 Sol 前置知识:长方体体积公式:\(V = abh\)。 我们知道,切割掉 \(x \le k\) 的部分就是把 \(a\) 减去 \(k\),切割掉 \(y \le k\) 的部分就是把 \(b\) 减去 \(k\),切割掉 \(z \le k\) 的部 ......
NEFU OJ Problem 1496 绿巨人吃绿苹果 题解
Problem:H Time Limit:1000ms Memory Limit:65535K Description 从前有一个绿巨人,他有个习惯是每餐只吃n个绿苹果。他有一棵神树,无限大,每一层都有且仅有k个枝杈,这k个枝杈上正好分别有1,2,3...,k个苹果。为了锻炼身体,他在同一层仅仅能选 ......
[ABC328C] Consecutive 题解
Hello World 链接 这道题是一个很明显的前缀和,我们把 $sum_i$ 表示为前 $i$ 个字符有多少个有重复,查询的时候就用 $sum_{r-1}-sum_{l-1}$ 就行了。 代码 #include<bits/stdc++.h> using namespace std; string ......