集训队 题解2019 day

`2022-08-26 13:02:02` [原题戳这！](luogu.com.cn/problem/P8482) ## 如何求最大乘积 我们令 $num1$ 为前几位较大的数， $num2$ 为前几位相对较小的数。 ### 浅浅地证明 首先我们肯定得使高位尽可能大，那么在高位都尽可能大的情况下，两 ......

`2022-08-26 12:34:22` [原题戳这！](https://www.luogu.com.cn/problem/P8481) ## 题意分析 不难看出，这道题是一个对于二分查找中 $mid$, $l$, $r$ 如何取值使得总查询次数最少问题。 这个 $w$ 是影响最终结果的决定性因素 ......

`2022-08-11 16:45:02 洛谷题解` 比赛的时候乍眼一看这么多 $2$ 直接不想写了,结果在重现赛重现看的时候感觉没有那么难了，就勇敢去贪就好了。 ## 贪心思路 首先，我们很容易得到,无论前面有重复出现了多少次该位的数，不管它前面是被异或了还是或了,我们只需要在该位最后一次出现的时 ......

# 思路 任意两个序列都有至少一个相同的元素，但相同的元素不必在相同的位置。 保证每两个之间都要有相同的元素？ 我们先考虑一下 $n=k\times 2$ 的情况，此时如果你左边取一半,右边取一半,这时两边的元素才可能不一样。 那么当 $n using namespace std; typedef ......

## 集训杂题整理： [蒲公英](https://www.luogu.com.cn/problem/P4168) 求区间众数。 像这种不好合并的数据我们可以考虑分块处理。先离散化，再分块维护离散化后的值。此时，如果查询的区间左右端点所属的块相邻或相间，可以直接暴力查询。那如果两个块之间隔了多个块呢？ ......

一道贪心题。 根据题意，我们需要在原序列中找出一条从 $1$ 到 $n$ 的路径，这条路径能被分成几个长度为 $k$ 且颜色相等的连续段。我们可以将这个问题简单化，那么这个问题就能被转化为从 $1$ 开始向后找一个颜色连续段，从 $n$ 开始向前找一个颜色相同的连续段，只要这两个连续段不相交即可，代 ......

我们首先可以观察到这道题的 $m$ 很大，所以要考虑这么多列里面是否存在一个性质，让我们求出前 $n$ 列之后快速求出后 $m$ 列的答案。观察一下可以发现第 $i,j$ 两列的答案等价时满足 $i \equiv j \pmod n$。这样的话我们只需要求出前 $n$ 列的答案即可。记 $s_i$ ......

这道题显然是一道 dp。转移方程式也很好推，我们记 $f_{i,j}$ 为前 $i$ 位且第 $i$ 位为 $j$ 的 DNA 序列数量。而对于输入的字符串，我们用 $vis_{i,j}=0$ 表示第 $i$ 个字母后面不能放第 $j$ 个字母。那么转移方程式即为： $$f_{i,j}= \sum ......

# CF1178F1题解 根据题意，每次选择一个区间染色，我们可以发现这道题满足了区间 dp 的一些性质，即区间答案可以合并，大区间的答案可以由小区间的答案更新而来。那么我们就可以设 $f_{i,j}$ 表示区间 $i$ 到 $j$ 的答案，那么接下来就考虑如何转移。然后考虑到题目要求从 $1$ 到 ......

这是一道比较板子的数位 dp 。 首先观察到 $k$ 很大，肯定不能用枚举的方法求，然后就考虑用数位 dp 。对于这道题来说，我们可以在用记忆化搜索做数位 dp 的时候存一个当前各数位之和对 $d$ 取余的余数，当把数填完之后判断余数是否为 $0$ 就能判断这个数是否符合条件。 ```cpp #in ......

这是一道~~比较简单~~的博弈论。 我们假设 $x \ge y$，那么此时可以分两种情况讨论： - $x using namespace std; #define int long long inline int read(){ int f=1,w=0; char c=getchar(); whil ......

简要题意： 对于一张$n$条边的无向完全图，每条边有两个权值$a_i,b_i$,求一棵最小生成树使其$\frac{\sum{a_i}}{\sum{b_i}}$最小。 这道题如果没见过这种技巧可能不好想，但我们也可以考虑一个朴素的想法，那就是猜！ 我们猜这个答案是$ mid$,然后就可以推一下柿子。 ......

显然，我们可以先忽略两个串已经一样的部分，只考虑剩下不一样的部分，然后我们就可以将它抽象成一个链上游走问题。我们记 $g_i$ 为从第 $i-1$ 个到第 $i$ 个点的期望步数，此时 $g_1=1$。且 $g$ 满足： $$g_i=\frac{n}{n-i}+\frac{i \cdot g_{i- ......

## 题目：[70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/description/) ### 思路： 除了`dp[i] = dp[i-1] + dp[i-2]`还可以用完全背包的方法，可以放无数个1或者2，看有多少种排列(先背包后物品) ......

[题目传送门](https://www.luogu.com.cn/problem/P8693) ## 思路 用队列实现广度优先搜索，碰到障碍停止，来过了停止，越界了停止，这一部分跟普通的广度优先搜索差不多，那为何这道题评绿呢？因为小明的宽度会缩小啊，其实处理这个点十分简单，我们让小明在必要时停止运动 ......

## A.Ekiden Race ### 题目描述： 有 $n$ 个人参加了往返赛跑，每个人有一个编号 $1$ 到 $n$。已知以下信息： - 如果按照往路的成绩排序，那么任何两个人的成绩都不相同。同时第 $i$ 个人在往路中排名第 $i$。 - 如果按照往返的成绩排序，那么任何两个人的成绩都不相同 ......

发现操作是可逆的，如果起始状态和终止状态都能走到同一个状态，那就能组合出一组解。 以任意一节点为根，考虑贪心地确定每个人最后的位置，使他对答案影响最小。策略是将可以放的人放到深度最大的点，然后删掉该点相邻的点，反复去做。 大多数情况下，总有一种方式使得一个节点能走到当前选择的深度最大点，但是有唯一一 ......

### 1. 一个简单的类 认识类 成员变量 类方法 ``` public class Person { //类的成员变量 int age; String name; double height; double weight; public void eat(){ System.out.printl ......

## Description 奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。 FJ 可以进行无数次以下操作： - 捡起当前房间的钥匙。（FJ 可以同时手持多个 ......

双倍经验 [CF559C](https://www.luogu.com.cn/problem/CF559C) 前置知识：网格图内任意两点间的路径数量。这个我们可以通过组合数的方法计算出来。假设我们从点 $(1,1)$ 走到点 $(i,j)$，在这个过程中我们的移动步数是 $|i-1+j-1|=|i+ ......

被 C 卡了。 最后被 E 的各种分讨劝退，但是同时也学习到了一种换根 dp 的简单写法。 评价：It's educational for me. ## A.Typical Interview Problem ### 题目描述： 有一个包含 F 和 B 的字符串，最开始是空的。我们开始从 $1$ 向 ......

## 前置知识： ### 1. [P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376) ### 2.[P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P489 ......

# 苍穹外卖-Day01 ## 1. 项目整体介绍 ### 1.1 项目定位 项目的定位：专门为餐饮企业（餐厅，饭店）定制的一款软件产品。 项目主要分为两个端： （1）管理端：外卖商家使用。 （2）服务端：点餐用户使用。 ### 1.2 项目的功能架构 项目的功能架构：体现项目的业务功能模块 1. ......

写的非常好的一个Git系列文章，强烈推荐 原文链接：https://github.com/doggy8088/Learn-Git-in-30-days/tree/master/zh-cn 有没有遇过这种情境，某个系统开发写到一半，结果被老板或客戶「插单」，被要求紧急修正一个现有系统的 Bug 或添加 ......

VB6-SirkMini_2019.02.20 VB6的精简优化版分享（xp-win10） 时隔三年，VB6.0 迷你版本又更新了，喜欢VB的千万不要错过呦~完美支持 win10系统作者：dk_fangkai visual Basic 6.0 Sirk 迷你版 2019.02.20 ( VB6 Si ......

某网站的题解标点符号的要求真是a piece of bloody shit. 在这里会自由一些. ## 0. 题目大意 题目的大意是模拟黑白棋游戏。简单而言有如下的要求： - 列出可能的移动。合法移动的规则是：新下的棋子必须 "夹住" 原来的。所谓夹住，其实就是一段横向、竖向、斜向的棋子之间的两段必 ......

216. 组合总和 III 详解 class Solution { public: vector<vector<int>> result; vector<int> path; int sum = 0; void dfs(int k, int n, int start){ if(path.size() ......

什么是名称空间？就是存放变量名与变量值关系的地方名称空间的分类 1. 内置的名称空间 '内置': Python解释器中本身就存在的，可以直接使用的 len 2. 全局的名称空间 在py文件中，顶格编写的变量名等都是全局的名称空间 3. 局部名称空间 """一般大多数都是在函数内部存在的都是局部的!" ......

回溯算法理论基础 77. 组合 class Solution { public: vector<vector<int>> result; vector<int> path; void dfs(int n, int k, int start){ if(path.size() == k){ result ......

``` @app.route('/getUrl', methods=['GET', 'POST']) def getUrl(): url = request.args.get("url") host = parse.urlparse(url).hostname if host == 'suctf.c ......