题解rounding maximum 1857b

这道题目千岩万转，需要用到多次转化，其中有一些转化较为常见，有一些则需要思考。 首先观察原问题：给定数列 \(a\)，对于所有 \(1\sim n\) 的排列 \(p\)，构建一张只有 \(j-i\le k\) 的 \((i,j)\) 之间有权值为 \(\max\{a_{p_i}, a_{p_j}\ ......

根据期望的线性性，总工资的期望等于在每一个 \(i\) 处获得的工资的期望之和，而在 \(i\) 处获得的工资的期望 \(E(i)=A_i\times p(i)\)，其中 \(p(i)\) 表示掷骰子掷到 \(i\) 且有效的概率。 初始 \(p(0)=1\)，则只有从 \(0\sim i-1\) ......

A. Doremy's Paint 3 记数组中数的种类数为\(k\)，当\(k=1\)时，答案为\(yes\)；当\(k=2\)时，记两个种类的数的个数差为\(d\)，当\(d≤1\)时，答案为\(yes\)；其他情况答案为\(no\)。 时间复杂度：\(O(nlogn)\) 1 void sol ......

题目链接 观察题目，我们发现直接计算是困难的，先构造单个合法的 \(T\) 分析其性质。 为了构造出 \(T\)，先考虑构造时 \(T\) 时什么时候会出现不合法的情况，此时 \(T\) 会有一段和 \(S\) 相同的前缀，且这段前缀后面跟着的字符比 \(S\) 所跟的小。 为了避免这种情况出现，我 ......

官方题目链接：http://118.190.20.162/ \(\Huge目录\) 201609 201612 201709 202104 202109 202112 202203 202206 202209 202303 202305 202309 \(\Huge\text{CSP201609}\ ......

tilian 代码很长 但是思路很清新 我们发现k=2 意思我们只用考虑sum[i]<=2的地方 不从天入手而是反而考虑这些个 sum[i]<=2 的地方 sum[i]2 这个地方被两个区间cover过 我们可以算出这两个区间的相交的<=2的数量+这两个区间<=1的数量 sum[i]1 这个地方被一 ......

提炼 感觉这种题还是很金典的 我们看到乘积 就应该想到其很容易爆 而我们省1的话 也最多就是2e5数量级的 我们为了省事不用算上界 可以直接把这个上界设为1e9 也不会爆LL 只要乘积突破这个上界 我们就肯定要是有旁边的 大于1的数 我们都要吃掉 因为增量都超过了1e9那么多 我们只要算出左右两边 ......

CF1884B Haunted House 题解 借鉴了当前 另一篇题解，加了更多的说明。 简化题意 给定一个长度为 \(n\) 的二进制串 \(S\)，求 \(f(1),f(2),\cdots,f(n)\)。 其中，\(f(i)\) 定义为，每次交换相邻的两个二进制位，将 \(S\) 的后 \(i ......

AT_abc325_g offence 题解 一道不难但是需要想一想的区间 DP。 有一个比较复杂的例子：ooofofxxx，简单的分析可知，一个 of 后面删除多少，与其前、后都有关，于是考虑区间 DP。 想到这里，其实问题已经解决一半了。 状态设计 设 \(f(l,r)\) 为闭区间 \([l, ......

AT_abc326_d ABC Puzzle 题解 看题 事实上，即使在 \(N=5\) 的情况下，也只有 \(66240\) 个网格满足「每行/每列恰好包含一个 A、B 和 C」。——官方题解 其实看到这道题，就感觉是搜索，这很显然。 但是我们会发现，最最最 native 的搜索，是 \(4^{5 ......

AT_abc326_f Robot Rotation 题解 经典问题，以前遇到过一个类似的问题：[ABC082D] FT Robot。 建议对比着看一看这两道题，是两种不同的思路。 （那一道题不用输出方案，因此可以用 bitset 优化；而此题需要输出方案，因此需要双向搜索。 思路 注意到每次只能「 ......

AT_abc325_f Sensor Optimization Dilemma 题解 Date 20231025：修复手滑公式 \(\min\)、\(\max\) 写反了。 动态规划。类似背包问题。 朴素算法 记 \((x,y)\) 表示使用 \(x\) 个 (1) 传感器、\(y\) 个 (2) ......

AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解 一道简单的概率论+动态规划题目（然而我赛时没看这道题 题意 有一个长度为 \(n\) 的序列 \(A\)、一个 \(n\) 面骰子，掷若干次骰子，如果这一次掷骰子的点数小于等于上一次的点数， ......

lock 直接模拟题意，过程略。 #include<bits/stdc++.h> using namespace std; int st[15][15]; int dis(int x,int y){ if(x < y)return y - x; return y + 10 - x; } bool m ......

[CSP-S2020] 儒略日 今儿终于做掉困扰多年的题目了，其实想好细节也不难。 容易发现儒略历和格里高利历的润年判断方式不一样，并且中间有消失的十天，计算起来相当不方便。所以我们可以首先计算出 \(-4713.1.1\) ～ \(1582.10.4\) 会经过多少天，可以通过一天一天暴力跳的方法 ......

传送门 考虑\(DP\)： 记状态 \(f_{i,j,st,en}\) 表示现在枚举到第 \(i\) 个字符，匹配了 \(j\) 个字符，要在前面删 \(st\) 个字符，在后面删 \(en\) 个字符的方案数 不难发现 \(f_{n+1,m,0,0}=1\) 状态转移有 当 \(s_i='-'\) ......

题目链接 原题做法：用单调栈求出每个圆盘中的水溢出后会 直接 流到哪个圆盘，因为每个圆盘中的水向下流有且仅有一个圆盘会 直接 接住它（将水池视作直径和容量都是正无穷的一个圆盘），因此构成了一棵树，根节点即为水池，每个点有点权，即该点代表的圆盘的容量。记 \(dis_{i,j}\) 表示节点 \(i\ ......

P4309 [TJOI2013] 最长上升子序列题解 正文 单调队列?单调锤子队列！！ 本题的操作可以省略成： 单点修改 区间查询 好极了，此时我们有两种选择： 线段树和树状数组，（平衡树，真不会，下一位 因为不需要其他操作，所以我们还是选择更小巧更可爱的树状数组吧。 关于vector vector ......

题解 AGC034D【Manhattan Max Matching】 problem 在一个二维坐标系内，点 \((RX_i,RY_i)\) 上有 \(RC_i\) 个红球，点 \((BX_i,BY_i)\) 上有 \(BC_i\) 个蓝球，且保证 \(\sum_{i=1}^{n}RC_i=\sum ......

题简单还考稀烂，别学了。 T1 密码锁 观察数据范围，可以直接枚举密码。 #include<bits/stdc++.h> #define ls (k<<1) #define rs (k<<1|1) #define nmid ((l+r)>>1) #define tmid ((tr[k].l+tr[k ......

比赛地址 A. Doremy's Paint 3 题意：给出一个数组\(b\)，问能否通过重新排序使得数组满足\(b_1+b_2=b_2+b_3=...=b_{n-1}+b_{n}\) Solution 首先判断元素个数 如果是1，则满足条件 如果是2，需判断不同元素个数的差是否小于等于1 其余的均 ......

题解 ABC326G【Unlock Achievement】 problem 有 \(n\) 项属性，第 \(j\) 个属性的等级 \(l_j\) 初始为 \(1\)，每提升一级花费 \(c_j\) 的钱。又有 \(m\) 项成就，第 \(i\) 项成就要求对于所有 \(1\leq j\leq n\ ......

ADASTRNG - Ada and Substring 题解 题目描述 给定一个小写字符串。 输出 \(26\) 个数，代表以 \(\texttt{a}\sim \texttt{z}\) 开头的本质不同的子串个数。 题目分析 高度数组模板题。 可以想到将以每个字符开头的本质不同的子串数目转化为： ......

题目链接 [Violet] 蒲公英 分析 可以先将 \(a[i]\) 离散化 然后考虑分块 对于询问 \(x,y\)， \(x\) 属于 \(p\), \(y\) 属于 \(q\) 当 \(q-p<=1\) 时 直接暴力枚举即可 \(else\) 如图 中间为分好块的地方 我们发现， \(ans\) ......

blog。很牛的题，想了差不多一个小时。 经典结论 此处 \(S\to T\) 表示状态 \(S\) 可以变成状态 \(T\)。 \(\textbf{Conclusion: }\) 若 \(\forall S\to T\to P\) 都有 \(S\to P\)，则 \(S\) 为必胜态。（用中文讲： ......

问题 A: ly喜欢玩石头 解题思路 题目告诉我们(1<=a,b <=1e9),那么int类型就够了。因为这两个数相加最大为20亿 定义两个变量a和b 输入a和b的值 打印a加b的值 #include <stdio.h> #include <string.h> #include <stdlib.h> ......

USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences 原题网址 这个题目有两种做法，一种是矩阵，一种是 CDQ 分治。矩阵我只大概口胡了一下，没仔细想，这里主要介绍一下 CDQ 分治的做法。 CDQ 分 ......

题解：「NOIP2022 提高组」种花 题目大意：给定一个 \(n \times m\) 的01矩阵，0表示可以种花，1表示土坑（无法种花），现在要在图上种出一个C型或F型（C,F横着的两条线的长度都可以不同，但一定是面向右边的），现在问你种C和F分别有多少种方案（除了这个形状外不能在任何地方种花） ......

目录T1 男女排队简要题意：题解：T2 树上最多不相交路径简要题意：题解：T3 生日T4 组队比赛简要题意：题解： T1 男女排队 简要题意： 求长度为 \(n\) 的01序列不包含字串101或111的个数。 \((n\leqslant 10^{18})\) 题解： 一开始往容斥的思路去想，但是在推 ......

【题解】P9753 [CSP-S 2023] 消消乐 不知道考场脑子是抽了还是有病，全程都不知道在放什么屁。 特别鸣谢：@dbxxx 给我讲解了解法一的满分做法，并让我对哈希有了更加深刻的认识；@Daidly 给我讲解了解法二。 题目链接 P9753 [CSP-S 2023] 消消乐 题意概述 给定 ......