集训队 题解2019 day

题目简述 给定一个字符串 \(t\)，由一个字符串 \(s\) 和这个字符串去掉所有 a 组成。求字符串 \(s\)。 思路 首先我们分析给定的字符串 \(t\)，它由 \(s\) 和 \(s\) 去掉所有 a 形成的字符串 \(s'\) 组成。那么当整个字符串 \(t\) 去掉 a 后，就得到了 ......

其实很简单的一道题。 思维路径 其实题目主要要考虑的就是以下三个条件。 每个人都要送一样多的硬币。 每个硬币都必须是不同的。 所有人送的硬币至少有 \(L\) 个是 Ivan 没有的。 我们一个一个来看。 每个人都要送一样多的硬币。 一共有 \(M\) 个朋友，所以说总共送的硬币的个数为 \(M\) ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

题目链接：洛谷 或者 CF 不是特别难的题，抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改，传统的 mex 求法里貌似就莫队类算法好带修，考虑带修莫队。 然而涉及到 mex 问题，你可能不由自主地想到回滚莫队求 mex 只删不加的板子题：P4137 Rm ......

有效括号 思路出来代码比较简单 左半括号出现就压右半进栈 这样比左右括号直接压进去 做的比较会少一些 栈为空但是还有符号出现或者是右半括号和当前元素对不上 显然为false 剩下的情况就是栈顶和当前元素匹配 pop即可 栈尤其适合做这类匹配类的题目 删除字符串中的所有相邻重复项 消消乐 直接压进栈做 ......

第1篇 基础知识 第一章 IDE--Visual Studio 在之前程序学习接触了Jetbrains的产品，其功能的强大、界面流畅度及其他编辑也是用该产品习惯等原因，所以主要使用 Rider进行C#的开发IDE。跳过Visual Studio的学习部分。 有关名词解释： SDK ： Softwar ......

Question LOJ2294 银河英雄传说 Solution 算是带权并查集一个比较典的题目了 定义 \(d[x]\) 表示战舰 \(x\) 与 \(fa[x]\) 之间边的权值，在路径压缩把 \(x\) 的 \(fa[x]\) 修改为根节点时，把 \(d[x]\) 更新成从 \(x\) 到树根 ......

直接上方案 1)请确保您取消选中工具>选项>调试>常规下的选项：使用托管兼容模式和要求源文件与原始版本完全匹配。如下图： 2)请先取消选中编辑并继续选项，然后关闭您的旧解决方案，删除解决方案文件夹中的.vs隐藏文件夹，解决方案中的每个bin和obj文件夹。 3)最容易忽略的一点。右键启动项目>属性> ......

CF1665E 直接做不是很好下手，考虑找些性质。 有一个比较显然的贪心，就是按位从高到低的考虑，如果当前位至少有 \(2\) 个 \(0\)，就可以去掉该位为 \(1\) 的数。但是时间上显然是不行的。 假如没有重复的数，可以发现扫到最后一位时，剩下的数的数量是 \(\log V\) 的，证明省去 ......

P8512 直接做不好做，考虑离线。这个覆盖操作和这道题很像，可以直接对某些段暴力修改，可以直接上 ODT。发现当 ODT 执行这些操作时，是容易求出不执行某些操作后带来的值的影响的，即可以直接用树状数组维护每个位置现在是被那个操作覆盖，求出 \(1\) 到 \(x\) 操作还覆盖了那些位置，以及这 ......

CF1870F 题意：给一个长度为 \(n\) 的排列，求在其在 \(k\) 进制下按字典序排序后 \(\sum[p_i=i]\) 的值（\(n\le10^{18}\)）。 直接做是不好办的，只能在一些数中找到 \(p_i\) 的大小关系。 在手摸的过程中会发现一些长度相等的数之间会插入一些其它长度 ......

P4700 简单的，但是考试的时候没看到是平面图，就只想到了缩点后 DAG 判断能到达哪些点。用 bitset 维护做到 \(\mathcal{O}(\frac{nm}{w})\) 的时空复杂度，但是空间会炸。 由于这个图是平面图，稍微推一下就可以知道所有能它最终所能到达的点一定是从西侧出发所能到达 ......

P4657 树形 dp。 首先，追逐者遇到的铁球的数量显然不会少于逃亡者遇到的铁球数量。 令 \(ss_i\) 表示与 \(i\) 相邻的点的权值之和。\(\mathcal{O}(n^2v)\) 的 dp 是很简单的。 令 \(dp_{i,j,0/1}\) 表示根节点到 \(i\) 的路径上，用了 ......

P9715 不一样的线段树做法。 假如只有 \(t=1\) 的操作是容易的。考虑加上 \(t=0\) 后怎么做。显然地，我们对每一个操作附上一个时间 \(tim\)，不妨令 \(tim\) 小的数能覆盖掉 \(tim\) 大的数。这时候就只需要维护区间取 min 和最后的 \(n\) 次求 \(c\ ......

P8386 platelett 讲的题欸。 先考虑给定序列怎么做。 问题显然可以转化为能否将序列分成若干个子序列。令 \(f_i\) 表示前 \(i\) 个数是否能够删完。则有 \(f_i = f_j[a_i=a_j, f_j=1]\)。这样是 \(n^2\) 的，也无法扩展至所有数列的情况。 建立 ......

P4067 因为不能直接减去 \(nmk\)，先把题目中的式子转化为求 \(i\oplus j \ge k\) 的数的个数与和。 这样就可以进行数位 dp 了。令 \(f_{bt,un,um,lk}\) 表示当前考虑到第 \(bit\) 位，\(n\) 有没有达到上界，\(m\) 有没有达到上界，\ ......

UVA12170 7 月份的题了，补一补。场上写挂了一点还是很遗憾的。 容易想到 dp。 但是由于值域非常大，直接 dp 是不行的。但是 \(n\) 非常小，容易想到离散化。 但是离散化后是不能直接加减的。有用的数值初看是有 \(\mathcal{O}(n^2d)\) 的，即 \(h_i + kd( ......

P9755 upd on 2023.11.20：增加细节说明。 刚开始浪费太多时间了，导致赛时没调出来，有点火大。 如果一开始没有头绪的话可以先看一下特殊性质，链是直接贪心。 考虑一下菊花，发现直接贪心是不可做的，但是发现树的高度随时间增大而增大，可以用二分转化为判定性问题解决。 对于任意的树来说， ......

P9753 法一： 这是赛时想法。 考虑 dp。 令 \(f_i\) 表示 \(i\) 为右端点的合法子串个数，则答案为 \(\sum\limits_{i=1}^{n}f_i\)。 赛时想过匹配指针不断跳的，但当时没敢写，用了一种更直观的方法。 仿照于括号序列，合法的子串只能为 \(cAc\) 或 ......

P8315 T3 写太慢了，就没看这道/gg。错过简单题+1。 不好直接对边或路径进行考虑，但是发现 \(m\) 非常小，考虑容斥。 即每次钦定集合 \(S\)，强制包含在 \(S\) 内的路径不合法，其它的都可以，容斥系数就是 \(-1^{|S|}\)。每次可以暴力覆盖染色，然后用一个并查集进行维 ......

P9340 记一下。称 \(\forall j\in[l,r]\) 的 \(c_j\) 为关键点。 法一： 最好想的。 有个显然的结论，将所有关键点按 DFS 序排序，走过的边的数量为排序后相邻的点之间的距离。记走过的边的数量为 \(cnt_e\)，则此时这些关键点所构成的虚树的大小为 \(\fra ......

CF1610F P7816 *3000 令 \(w_u\) 表示与 \(u\) 直接相连的边的权值和。显然当 \(2\mid w_u\) 时，这个节点是无法满足条件的，因为每次调整只能对 \(\mid d^+(u)-d^-(u)\mid\) 的值造成偶数的影响。 这时候肯定会猜答案就是 \(\sum ......

好久没写博客了？ 今晚写爽。 P5311 成都七中 这有黑？ 对于一个点 \(x\)，设其子树任意一点为 \(y\)。 我们可以求出这 \(x\rightarrow y\) 这条路径经过节点的的 \(l,r\)。 遍历 \(x\) 的子树，我们可以得到一些三元组 \((l,r,c)\) 表示 \(x ......

[ABC273D] LRUD Instructions 题解 很好的一道大模拟，使我爆 \(0\)。 思路解析 大模拟，我们只需要用一个 \(x,y\) 表示我们当前的位置，而对于每一个移动，我们就判断在当前移动方向上离当前点最近的点，若该点在当前行进路线上，则把当前位置设为该点前面的一个。 其中判 ......

9.8-基于Loki的日志收集系统 一、EFK vs LPG 架构和组件 Loki：Loki是一个开源的水平可扩展日志聚合系统，由Promtail、Loki和Grafana组成。 EFK：EFK是一个集成的解决方案，由Elasticsearch、Fluentd和Kibana组成。 存储和查询： Lo ......

2016年3月，谷歌围棋人工智能机器人“阿尔法狗”与韩国棋手李世石进行较量，“阿尔法狗”获得比赛胜利，最终双方总比分定格在4:1。 首场人机大战结束后，“阿尔法狗”之父、德米斯·哈萨比斯表示，人工智能的下一步目标是让计算机自己学棋。也就是说，下个版本的“阿尔法狗”将从零开始，不接受人类的灌输的特定知 ......

题目链接：洛谷 或者 CF 本题考虑转化为 cdq 分治模型 对于 cdq 分治来说，只需要考虑左边对右边的影响，那我们要考虑该怎样设置第一维度的左右对象。很显而易见的是抛开 \(q\) 限制而言，我们着眼于，如何让双方互相看到的严格条件转化为只需要关注单体看见。考虑什么情况下只需要一方看到对方，对 ......

栈模拟队列 大概了解一下思路自己就可以很快写出来了 我们需要第二个辅助栈帮助我们把stackIn的顺序颠倒，这样FILO的栈颠倒后 pop的顺序就和FIFO的队列顺序一致了 大概就是这张图 队列模拟栈 题目要求使用两个队列模拟栈 其实可以只需要一个队列就可以模拟 栈的出栈顺序是最后一个先出栈，那么队 ......

jwt 回顾 # jwt:simple-jwt >自定义表签发token -前端携带用户名密码到后端 -取出用户名密码 》去我们的表查询--》如果查到，说明是我们用户 -签发token： refresh = RefreshToken.for_user(user) refresh.access_tok ......

非常简单的一道题。要好好反思为什么没有做出来。 题意 给定一棵点带权的树，强制在线询问一条链上取恰好 \(m\) 个数按位与的最大值。\(1\le n\le 10^6, 1\le q\le 10^5, 1\le m\le 10, 0\le V< 2^{62}\)。 解法 考虑一个暴力：取出树链上所有 ......