题解 战争p4557 2018

## 题意 给定一个$1\sim N$的排列，在这个排列中选出两段互不重叠的区间，求使选出的元素排序后构成公差为1的等差数列的方案数。选出的两段区间中元素构成的集合相同时视为同一种方案。$1\le N\le 3\times 10^5$。 [传送门](https://www.luogu.com.cn/ ......

# P5643 [PKUWC2018]随机游走 [洛谷：P5643 [PKUWC2018]随机游走](https://www.luogu.com.cn/problem/P5643) ## Solution 对点集 $S$，记 $\max(S)$ 表示将 $S$ 中所有点都遍历过的步数，$\min(S ......

## 题目描述 给你四个正整数 $a,\,b,\,c,\,d$ ，求一个最简分数 $\frac{p}{q}$ 满足 $\frac{a}{b} \dfrac{r}{s}$。那么有以下结论： $$\dfrac{r}{s} \leq \dfrac{r + u}{s + v} \leq \dfrac{u}{ ......

1.分糖果 原题：https://www.luogu.com.cn/problem/P7909 原代码： #include<bits/stdc++.h> #define ll long long using namespace std; ll n,l,r; int main(){ cin>>n>>l ......

[$\text{link}$](https://www.luogu.com.cn/problem/CF1781F) 。也是一道非常巧妙的 $\texttt{dp}$ 。 容易想到把括号变成 $\pm 1$。考虑括号序列合法等价于前缀和 $\ge 0$，我们可以想加入 $()$ 或 $)($ 对前缀的 ......

显然，如果选择的 $k$ 个“合法集合”固定了，那么可以放置装置的点如果存在，那么必然形成一个连通块，也就是说，答案等于所有合法方案中，可以放置装置的点形成的连通块个数之和。而根据点减边的套路，这等价于，枚举每个点，计算有多少种方案满足可以在其放置装置，再枚举每条边，计算有多少种方案满足这条边两个端 ......

### 题意 给出一棵 $n$ 结点树，从结点 $x$ 出发，每次从当前点的所有边中选一条走过去，$Q$ 次询问给定一个点集 $S$，随机游走直到经过 $S$ 中的每一个点至少一次的期望总步数，出发点 $x$ 默认在开始时已经被经过。 $n\le 18, Q\le 5000$ ### 解法 萌新第一 ......

左偏树维护动态区间中位数。 [传送门 P4331 BalticOI 2004 Sequence 数字序列](https://www.luogu.com.cn/problem/P4331)。 ## Solution ### 1 我的思路和题解前半部分完全重合了（（ 如果按照单调不增去分割 $a$ 序列 ......

1.植树节 原题：https://www.luogu.com.cn/problem/U285015 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e6+255; int a[N ......

1.数字游戏 原题： https://www.luogu.com.cn/problem/P5660 代码： #include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<algorithm ......

怪异题。 阈值分治。权值不超过 $2^{16}=65536$，于是把前后八位砍开。把每个点和上边 $256$ 个点分成一块，那么每块内的 $dis$ 的前八位是相同的，因此可以分开考虑。 前边 $8$ 位设一个 $f_{x,i}$ 表示跳了 $i$ 块跳到 $x$，这一块的前八位最大值。这个暴力把这 ......

题意: 给定一个长度为 $n$ 的整数数组 $a$，求 $a$ 中前 $k$ 大的异或区间和之和。 首先对 $a$ 处理一个异或前缀和数组 $s$，这样区间 $[l,r]$ 的异或和就转化成了 $s_{l-1} \oplus s_r$。题目就变为求 $n+1$ 个数（包含一个空前缀）两个数异或前 $ ......

传送门 交通运输（Wormhole Transportaion） 题目大意 有 $n$ 个点和 $m$ 个点对，你需要构造一张 $m-1$ 条边的无向图，使得 $m$ 个点对间最短路之和最小。 求最小值及取到最小值的方案数。 $2 \le n \le 2000,2 \le nm \le 2 \tim ......

题目链接 一道诈骗题，英语课上一直在想然后想出来了（ 正难则反，我们很难按照题目所说的得到最少步数，可以考虑从排好序的状态开始。 这样，每次就从首或尾中选择一个移到任意一个位置了，简单了些。 （因为我们只能移动首尾，当前移动到哪里最优貌似可以贪心） 所以下面令初始状态为有序的那个，目标状态为初始时给 ......

第一种方法：枚举 从素数的定义中，我们可以知道，一个整数m要被判断为素数，需要判断n是否能被2、3…n-1中的一个整除，只有2,3，…,n-1都不能整除n,n才能判定为素数，而只要有一个能整除n的数出现，n就可以判定为非素数。 #include<iostream> #include<cmath> u ......

一、题目描述： 维护这样的一个长度为 $n$ 的数组，支持以下两种操作 $1$：在某个历史版本上修改某一个位置上的值 $2$：访问某个历史版本上的某一位置的值 每进行一次操作，就会生成一个新的版本（对于操作2，生成的就是一个完全一样的版本）。 版本编号即为当前操作的编号（从 $1$ 开始编号，版本 ......

题目链接 怎么唯一一篇题解这么抽象，完全看不懂。 给定一张无向图，求给这张图定向成 DAG 之后的最长路最短是多少。转化一下变成对 DAG 进行分层，每一层之间的点没有连边，使得层数尽可能少，那么最后的层数就是答案。 那么就求出若干个独立集，让独立集总数尽可能少。这是经典的色数问题，我们使用状压 D ......

自己下午闲着没事单挑了一下，两小时左右一度rk1，但后继无力了。。。。 A. Max or Min 肯定沿着出现过的数操作；然后发现如果a[i]=k,a[j]>k,a[k]<k就会增加一次操作 所以维护一下差分序列即可。 B. Level Up 两维DP，这个疑似edu出过。 要注意的是：需要关于x ......

一、题目描述: 给定 $n$ 和 $k$，表示有 $n$ 个点，其中有 $k$ 个点是关键点，这 $k$ 个点随机分布。 给出 $n$ 个点的连接方式，保证构成一棵树，求有期望多少个点使得这个点到 $k$ 个关键点的距离之和最小，答案对 $1e9+7$ 取模。 数据范围：$1\leq n\leq 2 ......

layout: post title: "matlab求逆运算：左除，右除，inv，pinv的用法及区别" author: "heleiqiu" header-style: text tags: [matlab, 求逆, 左除, 右除, inv, pinv] excerpt: 介绍矩阵求逆运算：左除 ......

layout: post title: "向量与矩阵的范数及其在Matlab中的用法" author: "heleiqiu" header-style: text tags: [Matlab, 范数, 矩阵, 向量] mathjax: true excerpt: 介绍向量与矩阵的范数及其在Matla ......

layout: post title: "使用Git上传本地项目到GitHub/Coding/码云" date: 2018-06-16 12:00:00 author: "qiuhlee" header-img: "img/bg-computer.jpg" header-mask: 0.3 cata ......

这一篇笔记我在新浪博客记录过，在这里也记录一次，新浪博客地址citect2018R2使用数据表控件显示大量查询结果_来自金沙江的小鱼_新浪博客 (sina.com.cn) 最近现场安装了CITECT 2018R2需要做报表的功能，先在家里电脑上做一下练习，很久没有使用这个功能了。以前做过练习，数据量 ......

upd: 修改了一些思路的表达，帮助理解。 首先膜拜 yyc 大佬出这样的~~毒瘤~~好题。另外感谢 永无岛、xtx1092515503、hs_black 提供的思路。这里整理了一下这些思路，可能会有所启发。 题意： 给定一个字符串构成的序列，多次查询给定区间内各字符串的最长公共子串长度。 提供一种 ......

题意： 给定 $m$ 个限制 $(l_i,r_i,p_i)$ 及 $n,k$，求满足以下条件的长度为 $n$ 的不同序列 $a=(a_1,a_2,\cdots,a_n)$ 的数目。 $\forall i \in[1,n],0\leq a_i\leq k$ $\forall i \in[1,m],\m ......

题目传送门 题目分析 我们发现，$\text{min}$ 操作实际上就是把两数当中较大的那个删除，较小的那个数不受影响，所以用最小的数删还是用另一个数删是无区别的。 一个性质： $$\gcd(x,y) \le \min(x,y)$$ 不管 $a_{min}$ 是原来的还是在 $\text{gcd}$ ......

题目 点这里看题目。 给定 $A,B,C$，求： $$ \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sigma_0(ijk) $$ 单个测试点内有 $T$ 组测试数据。 所有测试点满足 $1\le T\le 10,1\le A,B,C\le 10^5,1\le \sum ......

Part I Preface 原题目(Luogu) 原题目(AtCoder) Part II Sketch 给定一个正整数 $N(1 \leq N \leq 100)$，表示时钟数量。 接下来 $N$ 行，每行一个正整数 $T_i(1 \leq T_i \leq 10^{18})$，表示每个时钟旋转 ......

Part I Preface 原题目(Luogu) 原题目(AtCoder) Part II Sketch 给定一个正整数 $n(100\leq n \leq 999)$。 求 $n$ 是否是一个回文数，是输出 $\texttt{Yes}$，不是输出 $\texttt{No}$。 Part III ......

洛谷 P8714 题意 自己看（ 思路 分五个小题去考虑。 问题 A 枚举门牌号，看门牌号中有多少个 $2$，统计答案即可。 void sloveA () { // 问题 A int sum = 0; for (int i = 1, j; i <= 2020; i++) { // 枚举门牌号 j = ......