题解product dice abc
abc290g O(TD)算法
前言 似乎洛谷上的题解和AT官方都给的 \(O(TD^2)\) 算法? 这里给出乱搞搞出的一种 \(O(TD)\) 算法。 题解 首先发现 \(D\) 虽然没给出固定上界,但显然不超过 \(log_2 10^{18}=60\)。 再接下来可以发现删边等价于先选一颗子树,再删掉这颗子树内部的子树。 先 ......
题解 NOIP2021 方差
原题 我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃 题意 题意概述: 给定非严格递增序列 \(a_{n}\) 可以进行若干次操作,求序列方差的最小值的\(n^2\)倍 方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2 ......
ARC168(A-C)题解
比赛链接:arc168 A 题意: 读入一个由<和>构成的字符串,在最开始,最后,字符之间可以填上任意数字,任意两个相邻数字之间必须满足字符代表的大小关系。求问最后填入的数字组成的数组最少有多少对逆序对。 题解: 签到。 <可以不去考虑,因为不会对答案造成影响。 >如果不是在连续段内,也可以不去考虑 ......
[Codeforces] CF1475C Ball in Berland 题解
Ball in Berland - 洛谷 题意 在毕业典礼上,有个男孩和个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。 现在你知道个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。 思路 暴力 最朴素,也是简单的方法,就是通过暴力组合进行配对。 #incl ......
【题解】HD2016.X1,HD2016.X3,HD2016.X4,HD2016.X5
[HD2016.X1] 价钱统计 题目描述 夏天到了,超市里摆满了各种各样的应季水果。现在知道:西瓜的价钱是每斤 1.2 元;桃子的价钱是每斤 3.5 元;葡萄的价钱是每斤 4.5 元;苹果的价钱是每斤 5 元。 现在分别给出上述四种所购买的斤数(均不超过 20),请你编写程序帮助售货员阿姨计算并依 ......
CF1898 E Sofia and Strings 题解
Link CF1898 E Sofia and Strings Question 给出两个由小写字母组成的序列 \(t\) ,\(s\) 我们有两种操作, 删去 \(t\) 中的任意一个字母 \(t_i\) 把 \(t\) 的任意一个区间 \(t_l\sim t_r\) 按从小到大排序 可以操作任意 ......
【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_ ......
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 ......
product 分区
product 分区 | Android 开源项目 | Android Open Source Project https://source.android.google.cn/docs/core/architecture/bootloader/partitions/product-partitio ......
[ABC328D] Take ABC 题解
链接 如果只是扫一遍肯定是不行的,所以我们使用一个栈,遇到 C 就判断栈顶的两个元素是不是分别为 B 和 A。这样就能做出来这道题了。 代码 #include<bits/stdc++.h> using namespace std; string s; char stk[200010]; int ma ......
【树链剖分】P3401 洛谷树 题解
P3401 考虑先将路径权值进行转化,因为很难对路径直接进行统计。考虑如何表示出这条路径的权值。记 \(s_i = \oplus_{j \in \text{path}(1, i)} w_j\),其中 \(\text{path}(i, j)\) 表示 \(i\) 到 \(j\) 的路径上的边集。则 \ ......
AtCoder Beginner Contest(abc) 326
B - 326-like Numbers 难度: ⭐ 题目大意 如果一个三位数的百位和十位的乘积等于个位, 那么这个数就是合法的; 问大于等于n的最小的合法的数是多少; 解题思路 因为数据范围很小, 所以可以直接暴力; 神秘代码 #include<bits/stdc++.h> #define int ......
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\) 个原本被碾压的人不再被碾压,则相当于从 ......
AtCoder Beginner Contest 329 (ABC329)
A. Spread 不说了,代码。 B. Next 不说了,代码。 C. Count xxx Description 给定一个长度为 \(N\) 的字符串 \(S\),求 \(S\) 中非空连续,并且包含重复字符的连续子串长度。 例如 $S = $ aaabaa,则它满足上述条件子串为 a,aa,a ......
CF1898 C Colorful Grid 题解
Link CF1898 C Colorful Grid Question 给出一个 \(N\times M\) 的网格图 给每一条边染色(R/B),需要存在一条长度为 \(K\) 的路径从 \((1,1)\) 到 \((N,M)\),路径允许重复通过一个节点。 Solution 非常有意思的一道题 ......