题解sorting binary string
CSPRO 历届题目与题解
官方题目链接：http://118.190.20.162/ \(\Huge目录\) 201609 201612 201709 202104 202109 202112 202203 202206 202209 202303 202305 202309 \(\Huge\text{CSP201609}\ ......
CF1884B Haunted House 题解
CF1884B Haunted House 题解 借鉴了当前 另一篇题解，加了更多的说明。 简化题意 给定一个长度为 \(n\) 的二进制串 \(S\)，求 \(f(1),f(2),\cdots,f(n)\)。 其中，\(f(i)\) 定义为，每次交换相邻的两个二进制位，将 \(S\) 的后 \(i ......
AT_abc325_g offence 题解
AT_abc325_g offence 题解 一道不难但是需要想一想的区间 DP。 有一个比较复杂的例子：ooofofxxx，简单的分析可知，一个 of 后面删除多少，与其前、后都有关，于是考虑区间 DP。 想到这里，其实问题已经解决一半了。 状态设计 设 \(f(l,r)\) 为闭区间 \([l, ......
AT_abc326_d ABC Puzzle 题解
AT_abc326_d ABC Puzzle 题解 看题 事实上，即使在 \(N=5\) 的情况下，也只有 \(66240\) 个网格满足「每行/每列恰好包含一个 A、B 和 C」。——官方题解 其实看到这道题，就感觉是搜索，这很显然。 但是我们会发现，最最最 native 的搜索，是 \(4^{5 ......
AT_abc326_f Robot Rotation 题解
AT_abc326_f Robot Rotation 题解 经典问题，以前遇到过一个类似的问题：[ABC082D] FT Robot。 建议对比着看一看这两道题，是两种不同的思路。 （那一道题不用输出方案，因此可以用 bitset 优化；而此题需要输出方案，因此需要双向搜索。 思路 注意到每次只能「 ......
AT_abc325_f Sensor Optimization Dilemma 题解
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." 题解
AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解 一道简单的概率论+动态规划题目（然而我赛时没看这道题 题意 有一个长度为 \(n\) 的序列 \(A\)、一个 \(n\) 面骰子，掷若干次骰子，如果这一次掷骰子的点数小于等于上一次的点数， ......
String常用API
方法名 说明 public int length()： 获取字符串当中含有的字符个数，返回字符串长度 public char charAt(int index)： 获取指定索引位置的单个字符 public String concat(String str)： 将当前字符串和参数字符串str连接，返回 ......
CSP-S2023题解
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] 儒略日 题解
[CSP-S2020] 儒略日 今儿终于做掉困扰多年的题目了，其实想好细节也不难。 容易发现儒略历和格里高利历的润年判断方式不一样，并且中间有消失的十天，计算起来相当不方便。所以我们可以首先计算出 \(-4713.1.1\) ～ \(1582.10.4\) 会经过多少天，可以通过一天一天暴力跳的方法 ......
P8256字符串 题解
传送门 考虑\(DP\)： 记状态 \(f_{i,j,st,en}\) 表示现在枚举到第 \(i\) 个字符，匹配了 \(j\) 个字符，要在前面删 \(st\) 个字符，在后面删 \(en\) 个字符的方案数 不难发现 \(f_{n+1,m,0,0}=1\) 状态转移有 当 \(s_i='-'\) ......
[eJOI2020 Day1] Fountain 题解
题目链接 原题做法：用单调栈求出每个圆盘中的水溢出后会 直接 流到哪个圆盘，因为每个圆盘中的水向下流有且仅有一个圆盘会 直接 接住它（将水池视作直径和容量都是正无穷的一个圆盘），因此构成了一棵树，根节点即为水池，每个点有点权，即该点代表的圆盘的容量。记 \(dis_{i,j}\) 表示节点 \(i\ ......
std::string_view
在原来的string操作中，大多数都是复制string进行操作，如：substr()、string&传参。它们都会复制占用额外内存。 使用std::string_view犹如只是对它的视图映射进行处理，有一个指针指向一个起始位置，然后会有一个size参数去决定这个指针的移动步数。 #if 1 Pri ......
P4309 [TJOI2013] 最长上升子序列题解
P4309 [TJOI2013] 最长上升子序列题解 正文 单调队列?单调锤子队列！！ 本题的操作可以省略成： 单点修改 区间查询 好极了，此时我们有两种选择： 线段树和树状数组，（平衡树，真不会，下一位 因为不需要其他操作，所以我们还是选择更小巧更可爱的树状数组吧。 关于vector vector ......
题解 AGC034D【Manhattan Max Matching】
题解 AGC034D【Manhattan Max Matching】 problem 在一个二维坐标系内，点 \((RX_i,RY_i)\) 上有 \(RC_i\) 个红球，点 \((BX_i,BY_i)\) 上有 \(BC_i\) 个蓝球，且保证 \(\sum_{i=1}^{n}RC_i=\sum ......
String的padStart() 和 padEnd()方法
String.prototype.padStart() padStart() 方法从字符串的开头用另一个字符串填充一个字符串到一定长度，并返回一个达到一定长度的结果字符串。下面说明了 padStart() 方法： String.prototype.padStart(padLength [,padSt ......
[整理]CSP-S 2023 题解
题简单还考稀烂，别学了。 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 ......
数据结构与算法 | 二分搜索（Binary Search）
文承上篇，搜索算法中除了深度优先搜索（DFS）和广度优先搜索（BFS），二分搜索（Binary Search）也是最基础搜索算法之一。二分搜索也被称为折半搜索（Half-interval Search）也有说法为对数搜索算法（Logarithmic Search），用于在已排序的数据集中查找特定元素... ......
题解 ABC326G【Unlock Achievement】
题解 ABC326G【Unlock Achievement】 problem 有 \(n\) 项属性，第 \(j\) 个属性的等级 \(l_j\) 初始为 \(1\)，每提升一级花费 \(c_j\) 的钱。又有 \(m\) 项成就，第 \(i\) 项成就要求对于所有 \(1\leq j\leq n\ ......
CF1889A. Qingshan Loves Strings 2
不妨考虑什么时候会无解！ 显然当原序列 \(0,1\) 数量不同，或者序列总长为奇数时会无解！ 否则我们设 \(l=1,r=n\)！开始回文配对！ 如果配上了就直接删掉！并把左右端点向内移动！ 如果两者都是 \(0\)，就在末尾加上 \(01\)！都是 \(1\) 就加最前面！ 以在末尾加入举例！此 ......
ADASTRNG - Ada and Substring 题解
ADASTRNG - Ada and Substring 题解 题目描述 给定一个小写字符串。 输出 \(26\) 个数，代表以 \(\texttt{a}\sim \texttt{z}\) 开头的本质不同的子串个数。 题目分析 高度数组模板题。 可以想到将以每个字符开头的本质不同的子串数目转化为： ......
synchronized使用String做锁定互斥
依靠ConcurrentHashMap特性，自己实现一个工厂类： import lombok.Data; import lombok.extern.slf4j.Slf4j; import org.springframework.util.StringUtils; import java.util.c ......
『做题记录』[CF1601F]Two Sorts
[CF1601F]Two Sorts link:https://codeforces.com/problemset/problem/1601/F Description 有一个数列 \(\{a_1, a_2, \ldots, a_n\}\) 是一个 \(1 \sim n\) 的排列，且所有的数都按照 ......
Luogu P4168 [Violet] 蒲公英 题解
题目链接 [Violet] 蒲公英 分析 可以先将 \(a[i]\) 离散化 然后考虑分块 对于询问 \(x,y\)， \(x\) 属于 \(p\), \(y\) 属于 \(q\) 当 \(q-p<=1\) 时 直接暴力枚举即可 \(else\) 如图 中间为分好块的地方 我们发现， \(ans\) ......
PAT甲级：1174 Left-View of Binary Tree
题目：1174 Left-View of Binary Tree 25分 题解：层次遍历输出每一行最左边的元素。(最开始以为输出部分节点的左子树...想不到思路) using namespace std; #include <iostream> #include <vector> #include ......
ARC137C 题解
blog。很牛的题，想了差不多一个小时。 经典结论 此处 \(S\to T\) 表示状态 \(S\) 可以变成状态 \(T\)。 \(\textbf{Conclusion: }\) 若 \(\forall S\to T\to P\) 都有 \(S\to P\)，则 \(S\) 为必胜态。（用中文讲： ......
2023年10月第四周题解------输入与输出
问题 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 Platinum 部分题目题解
USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences 原题网址 这个题目有两种做法，一种是矩阵，一种是 CDQ 分治。矩阵我只大概口胡了一下，没仔细想，这里主要介绍一下 CDQ 分治的做法。 CDQ 分 ......
题解：「NOIP2022 提高组」种花
题解：「NOIP2022 提高组」种花 题目大意：给定一个 \(n \times m\) 的01矩阵，0表示可以种花，1表示土坑（无法种花），现在要在图上种出一个C型或F型（C,F横着的两条线的长度都可以不同，但一定是面向右边的），现在问你种C和F分别有多少种方案（除了这个形状外不能在任何地方种花） ......
【梦熊联盟】10月28日 NOIP十连测 第五场 题解
目录T1 男女排队简要题意：题解：T2 树上最多不相交路径简要题意：题解：T3 生日T4 组队比赛简要题意：题解： T1 男女排队 简要题意： 求长度为 \(n\) 的01序列不包含字串101或111的个数。 \((n\leqslant 10^{18})\) 题解： 一开始往容斥的思路去想，但是在推 ......