集训队 线段 题解p10009

第一次参加CTF新生赛总结与反思 因为昨天学校那边要进行天梯模拟赛，所以被拉过去了。16点30分结束，就跑回来宿舍开始写。第一题和第二题一下子getshell，不用30分钟，可能我没想那么多，对比网上的WP，自己和他们有点不太一样，比较暴力。大概17点10的时候，写第三题，可能自己第一次遇到随机数问 ......

题面传送门 很好的题目。 首先我们假设 $a$ 没有初始值，这貌似是平凡的。因为这样的话如果两个位置 $x<y$ 那么 $a_x\leq a_y$ 对于任意时刻都成立。取 $\min$ 的过程只需要线段树上二分加上区间覆盖即可。 但是有初始值怎么办呢？这个问题开始变得棘手起来。但是我们发现上面那个性 ......

题目链接：https://codeforces.com/contest/1646/problem/E 题目大意： 有一个 $n \times m$ 的矩阵，其中第 $i$ 行第 $j$ 列的格子中的数字是 $i^j$。 问：矩阵中存在多少个不同的数？ 解题思路： 可以很明显地发现，第 $1$ 行的数 ......

[洛谷NOIP1999 普及组] 导弹拦截(DP+二分维护单调不上升和单调下降子序列) 首先用二分不断替换or添加 维护一个不上升子序列 第二个维护的是每次新系统的子序列末尾的min值的一个数组 int main() { int x; while (cin >> x) a[++n] = x; int ......

传送门 #include <iostream> #include <algorithm> #include <cstring> typedef long long ll; typedef std::pair<double, int> PDI; const int N = 1e5, M = 2e5 + ......

传送门 大致题意： ** 给定一个n和m，表示有区间大小为n，进行m次操作。** ** 输入m行，每行3个数字v, l, r。如果v等于0则表示查询[l, r]内桃子的数量，如果v不为0则表示给[l, r]区间修改全部加v，如果有某个点数量+v小于0，则修改为0即可。** 大致思路： ** 这个题和 ......

题目链接：https://www.luogu.com.cn/problem/P7492 解题思路： 分块。解题思路全部来自 yzy1大佬的博客 额外掌握技能： 编译时加入 -Wall 参数。 示例程序： #include <bits/stdc++.h> using namespace std; co ......

###一. 概述 线段树（Segment Tree）是一种用于处理区间查询和更新的数据结构 常用于解决一维区间相关的问题，如区间最值、区间和、区间乘积等 线段树的基本思想是将区间划分为一些小的子区间，并在每个子区间上维护一些信息 例如该区间的最值、和、乘积等，通过将大区间不断划分为小区间，直到每个小 ......

Prefix Equality 题意 给定长度为 $n$ 的整数序列 $a$ 和 $b$。 对于每组询问，回答以下内容： 如果 $a$ 的前 $x_i$ 项数值构成的不重复集合与 $b$ 的前 $y_i$ 项相同，输出 Yes，否则输出 No。 数据范围 $1 \leqslant x_i, y_i ......

250-like Number 题意 给定一个整数 $n$，求有多少小于等于 $n$ 的满足以下条件的整数 $k$： $k$ 可以被表示为 $k = p \times q^3$，其中 $p \lt q$，并且 $p, q$ 均为质数。 数据范围 $1 \leqslant n \leqslant 10 ......

神仙题，我会把我自己思考的过程一步步写出来。 初看这题时感觉没什么思路，所以随便算了点东西。很容易发现如果对于一个 $i$，$q_i\geq q_{i+1}$，那么 $q_i$ 就没有意义，每次把元素放进来时先把头部比它大的都弹走，再把它放进去，设处理完的 size 为 cnt。 然后就是这道题的精 ......

我们可以把这个理解成一种类似卡塔兰数的形式，我们发现，被安排的 $0$ 球总数 $i$ 和已经出现的颜色种数 $j$ 在任意时刻都必须满足 $i\ge j$。 然后就可以 $dp$ 了，我们每次钦定下一个转移的球是某种颜色。如果下一个转移的球不是 $0$，那么我们就一次性把后面所有这种颜色都安排好， ......

$$吓死我了，还以为写了半天的被自己删掉了$$ $$但是 \text{Ctrl+S} 会保存草稿啊$$ $$以后一定要保留这个好习惯$$ 第一步转化题意，我们把“所有机器人移动”转化成“出口带着边框移动”，而在出口运动过程中超出边框的机器人，就“死”了。 然后我们发现，出口运动过程中，假设出口目前走 ......

我们考虑转化题意，一个合法的将 $1\sim N$ 划分成长度依次为 $a_1,a_2,\cdots a_k$ 的小区间，对答案的贡献为 $a_1^2a_2^2\cdots a_k^2$。 化贡献为方案数，我们在每个长度为 $a_i$ 的小区间内放置两个独立的标记，每个合法的划分方案对放置标记方案种 ......

D. AB Graph 2000 构造 https://codeforces.com/problemset/problem/1481/D 题解：由于只有两种边，我们可以枚举较小结构的特性并循环来构造整体解。对于任意两个点，[u->v,v->u]只有4种情况，对于[1,1],[0,0]直接得解，可以循 ......

BZOJ4212 神牛的养成计划 Description 给定大小为 $N$ 的字符串集合 $S$ 和 $M$ 组询问，每次给定字符串 $s_1$ 和 $s_2$，询问 $S$ 中有多少串满足其前缀为 $s_1$ 且其后缀为 $s_2$。 强制在线，$N \le 2000$，$M \le 10^5$ ......

TJOI 2015 概率论 题解 题意 求 $n$ 个点随机生成的有根二叉树（所有互不同构的二叉树出现情况等概率）的叶子节点数的期望值。 题解 70 答案显然是 $\dfrac{g(n)}{f(n)}$ ，$g(n)$ 是 $n$ 个点为所有二叉树的叶子总数， $f(n)$ 是 $n$ 个点能生成的 ......

Ignore Operations 题意 Takahashi 有一个整数 $x$，初始 $x = 0$。 有 $n$ 次操作。第 $i$ 次操作用两个整数 $t_i, y_i$ 描述： 如果 $t_i = 1$，将整数 $x$ 替换为 $y_i$。 如果 $t_i = 2$，将整数 $x$ 替换为 ......

Index Trio 题意 给定长度为 $n$ 的整数序列 $a = (a_1, a_2, \dots, a_n)$。请你求出有多少个整数三元组 $(i, j, k)$ 满足： $1 \leqslant i, j, k \leqslant N$ $\frac{a_i}{a_j} = a_k$ 数据范 ......

这是一道很好的最短路的题目 #### 难点1.如何建图\2.如何进行更新最短路\3.求最小方案 #### 建图输入中有药水的配置\A + B = C```1 2 0 4 5 1 3 6 2```这看上去是不是很像图论?\选用链式前向星\如下```cppint head[1010],cnt;void ......

题目链接 场上被 F 干碎了，没看见这个典题。原题差不多是这个吧 ......

一道简单构造题。 如果 $m=\frac{n(n-1)}{2}$，此时任意两个数都要有偏序关系，但是又要求第二个数列有两个数相等，因此无解。 否则一定有解。不难想到构造两个数列使它们几乎完全相等。可以找到两个没有偏序关系的下标 $(i,j)$，在第一个数列中分别赋值为 $n-1,n$，在第二个数列中 ......

NOC 2022 初中组选择题和编程题题解 注意：本文有几个问题： 部分题目我也不确定答案，而且我水平不行，有些题目我还真不会，大家就把我的答案当个参考吧。 目前有一大半的题目因为作者比较懒，暂时没写，空在那儿，可以下载原题自己做做。 1 初中组选拔赛 原题链接，提取码：efy6。 1.1 选择题部 ......

P6631 [ZJOI2020] 序列 题解 注意到原题是个整数规划，记所有操作的集合为 $\mathcal{I}$，操作 $i$ 的次数为 $x_i$ 化成标准型如下： $$ \begin{align*} &\max\sum_{i\in\mathcal{I}}x_i\ s.t.\ & \sum_{ ......

Potted Flower POJ - 2750 思路：我们将题目简单化，假设我们要求的是序列的最大连续子段和，且可以包括所有数。 我们的线段树需要维护这段区间的最大前缀和pre，最大后缀和suf，区间和sum，区间连续最大和mx。 那么难点就在于如何由子节点更新父节点。 我们可以知道，tr[p]. ......

A 题目： 给定一个串，我们拥有他的一个反串，进行k次操作，每一次把当前的串加上反串加在后面，或者加在前面，问最后我们可以得到最多几种序列？ 思路： 模拟一下会发现，当一个串是回文的，最终的结果一定是1。 如果最开始的串不是回文的，经过一次操作之后也会变为回文串。（所以k==0时输出1.k>0时输出 ......

P4317 花神的数论题【数位DP】 题目描述 最开始其实没有什么想法 第一次遇见数位dp求相乘的题 想就按照常规做法来做，但不知道如何去处理* 于是写了一个错误的代码 //当前枚举到第id位，前面的1的个数为sum，是否达到上限limit ll dfs(int id,int sum,int lim ......

题意 传送门 给定一个 $n$ 行 $m$ 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。 现在你可以矩阵实施以下操作： 使用一块钱，选定一个包含 $(1,1)$ 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。 使用三块钱，选定一个包含 $(n ......

发现和最短路差不多，不过不能朴素的跑最短路。考虑对于每两个相隔 $2$ 的整数次幂的点建边，在这个新图上跑最短路就是答案。设 $f_{i,j,k}$ 表示从点 $i$ 跳 $2^k$ 步能否到点 $j$，转移方程就是一个普通的倍增。如果点 $i$ 和点 $j$ 可以一步到达，那么就在新图上建一条长度 ......

前言 题目传送门！ 更好的阅读体验？ 很好玩的贪心。 思路 如果第 $i$ 次操作为覆盖操作，那么 $1 \sim i-1$ 次操作都是无效的，原因显然。 这启示我们从后往前扫（前面的会被忽略，后面的不会啊！）。 在此基础上，就是分类讨论一下（假设当前的最大答案为 $sum$）： 当前操作是覆盖操作 ......