DDOSvoid's Blog

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4747

简要题意：给定一个长度为 $n$ 的排列 $p$，如果区间 $[l,r]$ 内的数排序之后是连续正整数，则称 $[l,r]$ 为一个合法区间，现在有 $m$ 次询问，每次询问给定一个区间 $[x,y]$，求最小的一个合法区间 $[l,r]$ 满足 $l\le x\le y\le r$

$n,m \le 10^5$

阅读全文 »

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/CF1136E

简要题意：给定一个长度为 $n$ 的数列 $a_i$ 以及一个长度为 $n-1$ 的数列 $b_{i}$，现在有两种操作，第一种操作是给定 $x$ 和 $y$，首先将 $a_x$ 加上 $y$，如果 $a_{x+1}<a_x+b_x$，那么将 $a_{x+1}$ 变成 $a_x+b_x$，接着如果 $a_{x+2}<a_{x+1}+b_{x+1}$，将 $a_{x+2}$ 变成 $a_{x+1}+b_{x+1}$，以此类推，直至不满足条件；第二种操作是求 $\sum_{i=l}^ra_i$

$n,m\le 10^5$

阅读全文 »

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P1525

简要题意：给定一张 $n$ 个点 $m$ 条边的无向图，现在要求将这 $n$ 个点分成两个点集，一个点集的权值为点集内的点之间的边的权值的最大值，现在要求一种分法，使得两个点集的权值的最大值最小

$n\le 2\times 10^4,m\le 10^5$

阅读全文 »

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/1117/G

简要题意：给定一个长度为 $n$ 的排列 $p$，还有 $m$ 次询问，每次询问给定 $l,r$，求 $f(l,r)$，其中 $f(l,r)=(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)$，$m_{l,r}$ 表示 $[l,r]$ 中的最大值的位置，对于 $l>r$ 的情况，$f(l,r)=0$

$n,m\le 10^6$

阅读全文 »

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

https://ac.nowcoder.com/acm/contest/21733/K

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问求区间 $[l,r]$ 中的所有数排序去重后得到的序列 $b_i$，这个区间的价值是 $\sum b_if_i$，其中 $f_i$ 表示斐波那契数列第 $i$ 项

$n,m\le 3\times 10^4$

阅读全文 »

发表于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=7134

简要题意：给定一张 $n$ 个点 $m$ 条边的有向图，每条边有两种权值 $a_i,b_i$，对于一条路径，如果路径上的第 $i$ 条边的 $a$ 大于第 $i-1$ 条边的 $a$，那么第 $i$ 条边的权值为 $a-b$，否则为 $a$，求 $1$ 到其它所有点的最短路

$n\le 10^5,m\le 2\times 10^5$

阅读全文 »