集训队 题解2019 day

Permutation and Minimum 看到 300 的数据范围，再加上计数题，很容易就往计数 DP 方向去想。 为方便，我们将 \(n\) 乘二。 因为是两个位置取 \(\min\)，于是我们便想到从小往大把每个数填入序列。于是DP数组第一维的意义便出来了：当前已经填入了前 \(i\) 小 ......

Maxim and Increasing Subsequence 首先，我们可以发现，当这个重复次数很大的时候，答案就等于序列中出现的不同权值个数。实际上，这个“很大”就可以被当作“大于等于不同权值个数”。 不同权值个数实际上是 \(\min(n,m)\) 级别的，其中 \(n\) 是序列长度，\( ......

Kuro and Topological Parity 我们考虑在一张染色完成的图里，我们连上了一条边，会有何影响？ \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边，但是出发点是个偶点（即有偶数条路径以其为终点的节点），终点的路径数增加了， ......

Subsequence Reversal P 思路： 发现，翻转一个子序列，就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示： \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为： \(L>R\) 时， \(f=-\inft ......

MRO-Ant colony 根据下取整除法的性质 \((\left\lfloor\dfrac{\left\lfloor\dfrac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\dfrac{x}{yz}\right\rfloor)\)，我们可以反 ......

Good Sequences 状态很显然，设 \(f[i]\) 表示位置 \(i\) 的最长长度。 关键是转移，暴力转移是 \(O(n^2)\) 的，我们必须找到一个更优秀的转移。 因为一个数的质因子数量是 \(O(\log n)\) 的，而只有和这个数具有相同质因子的数是可以转移的； 因此我们可以 ......

New Year and Arbitrary Arrangement 思路： 期望题果然还是恶心呀！ 我们设 \(f[i][j]\) 表示当串中有 \(i\) 个 \(a\) 和 \(j\) 个 \(ab\) 时的方案数。为了方便，设 \(A=\dfrac{P_a}{P_a+P_b},B=\dfra ......

Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场（注意是场，不是部）电影时，已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了， \(21\%\)。 发现当一场电影结束后，无论这一场是在哪里看的都没关系。 ......

给定一个排列，要求交换最多 $n-1$ 对元素，使得这个排列变成 [1,2,...,n] 的有序排列。 当然没有那么简单，对于交换还是有限制的，对于相邻的两次交换，不妨叫做 $(l_i, r_i)$ 和 $(l_{i+1}, r_{i+1})$，必须满足**这两个交换所对应的区间，没有交集**，即... ......

用户交互Scanner java.util.Scanner是java5的新特征，我们可以通过Scanner类来获取用户的输入。 Scanner s = new Scanner(System.in);​//通过Scanner类的next()与nextLine()方法获取输入的字符串，在读取前我们一般需 ......

题目描述 想象学竞赛网站 CodeFancy 举办了 \(m\) 场比赛。你在 CodeFancy 上关注了 \(n\) 个账号，编号为 \(1\) 到 \(n\)。你知道这 \(n\) 个账号分别参加了 \(m\) 场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况，你想知道这 \(n\) ......

题目链接 相当牛逼。 这种找数量的题型，确定树形 \(dp\) 没跑了。 首先思考常规树形 \(dp\)，不难想到设 \(f_{u,a,b}\) 表示以 \(u\) 为根节点的子树内（包括点 \(u\)），最大值是 \(a\)，最小值是 \(b\) 的连通子图数量，转移很容易，但是这样时间空间复杂度 ......

第一题是[977. 有序数组的平方]这题解题思路依旧可以用双指针，指针分别指向数组的头尾两端，然后对两端求乘积比较大小，把乘积值更大的存储到数组尾端，然后指针更新位置，代码如下。 public int[] sortedSquares(int[] nums) { //res用于存储平方和结果 int[ ......

###### [704. Binary Search](https://leetcode.cn/problems/binary-search/)入门必备二分查找了。必须是在一堆**有序的**数组中找到其中特定某个val值。###### 二分算法的思路：*首先取一个基准值，这个值我们一般取数组的中间位 ......

实时更新。 众所周知的，原创题就是即原神又创人的题。 当然有的题不会放，等考了在放。 波特 问题描述 流水线上有 \(n\) 个波特，每个波特有一个工作效能 \(a_i\) 。对于每一个波特，当它遇到一个工件时，它会对其进行加工，耗费 \(1\) 个单位时间，然后把它传递给它前面中工作效能最大的波特 ......

又是一道锻炼代码能力的题目。 首先遇到这种求经过多少个节点的题可以先缩点，然后我们考虑那个特殊限制怎么用。 如果对于两个强联通分量 \(x\) 能到 \(z\)，\(y\) 能到 \(z\)，则 \(x,y\) 之间一定有一个限制，假设这个限制是 \(x\) 能到 \(y\)，那么我们可以只记录 \ ......

首先对每个数分解只因数，然后把只因数的指数对3取模，把 \(s\) 划分成多个等价类。对于每一个等价类，有唯一对应的另一个等价类不能同时选，取最多的即可。 分解只因数用 polard's rho 算法，时间复杂度 \(O(nw^{0.25})\) code: #include<bits/stdc++ ......

整体二分板题 首先瑞平翻译。 考虑整体二分，用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边，查询这时的询问是否满足要求，进行整体二分即可。 由于多次加入边比较麻烦，我们用可撤销并查集维护。 时间复杂度 \(O(n ......

考虑 kruskal 算法的过程。 先将边按边权排序，考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中，所以对于所有的边权小于 \(L\) 的边，我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x, ......

一道十分有趣的题。 一眼推式子，发现自己不会。 看了题解，发现是有趣思维题。但是由于我的朋友学习了有趣的思维题做法，因此我决定学习更有趣的生成函数做法！！！ 考虑把原式拆开， \[\frac{1}{2}\times \left( \sum_{i=1}^{n}\sum_{j=1}^{n} \binom ......

非常有意思的思维题。 首先我先瑞平一下翻译，我根本没看懂，还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边，如果得到的图是联通的，那么就只能填入 \(1\) 种字符，否则就可以填入 ......

首先考虑一些简单的情况，比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果，于是可以钦定所有操作 1 在操作 2 之前。并且可以发现，进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......

变量 常量 作用域 变量 变量就是可以变化的量。--》通过变量操作内存中的数据 JAVA是强类型语言，每个变量就必须声明类型 确定。 JAVA变量是程序中最基本的存储单元，其要素包括变量名、变量类型和作用域。 type varName [=value] [{,varName[=value]}]; / ......

防止循环导入是编程中的常见问题，特别是在使用模块化的编程语言中。以下是一些方法来避免循环导入： 1. **重构代码**：重新组织你的代码，将重要的功能放在单独的模块中，以减少模块之间的相互依赖。 2. **使用导入语句**：在需要的时候才在函数内导入模块，而不是在模块的顶部导入。这样可以减少模块之间 ......

2023_10_12_MYSQL_DAY_04_笔记 14章课后作业 CREATE TABLE xi( xid INT PRIMARY KEY AUTO_INCREMENT, xname VARCHAR(10) UNIQUE, xhead VARCHAR(10) NOT NULL, xloc VAR ......

[CF1098E] Fedya the Potter 题解 前言 一道类欧好题。 题解 这道题让求 \(c\) 数组的中位数，那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 ......

NOIP比赛前的冲刺训练 - 第3天：矩阵挑战 问题描述 您有一个 n×m 矩阵，行编号从 0 到 n−1，列编号从 0 到 m−1。最初，第i行第j列的元素是 i*m+j。系统支持三种类型的操作： 交换两行。 交换两列。 交换两个特定的元素。 任务是确定执行 q 次操作后矩阵的状态。 输入格式 为 ......

T1 ###寻找有向图中的最小疲惫路径### 题目描述 有一张 n 个点 m 条边的有向图，每条边上有一个正整数边权，你要顺着图上的有向边从 1 号点走到 n 号点。 假设你经过的边边权依次为 (w_1, w_2, \dots, w_t)，则你的疲惫程度为 \[\ f(w) =\max_{i=1}^ ......

Day1 二分查找两种写法和快慢指针 //左闭右闭的情况，也是我最喜欢的一种写法，可能是因为比较对称 一个mid+1 一个mid—1 直接写就行，要注意左闭右闭和左闭右开的区别class Solution {public: int search(vector<int>& nums, int targ ......

软件测试面试day20231010邮储银行。题目面完就百度查是怎么回事？让我想起了，之前读书，考完试，就查试卷的题目不会应该怎么写，去订正。不断完善改进。做好自己对自己可以做好的事情。 专心做好一件事情就可以了。术业有专攻。 一个男生自己可以做的事情 ，偏要女生做，这个男的心胸太狭隘，不行。能和一个 ......