DDOSvoid's Blog

题目描述

http://codeforces.com/problemset/problem/923/E

简要题意：你现在有一个整数 $x$，题目给出它属于 $[0,n]$ 中某个数的概率，现在要进行 $m$ 次随机，每次随机将等概率的将 $x$ 变成 $[0,x]$ 中的任意一个整数，求 $m$ 次操作后，整数 $x=k$，其中 $k\in[0,n]$ 的概率

$n\le 10^5,m\le 10^{18}$

题目描述

http://codeforces.com/gym/103415/problem/K

简要题意：给定 $n,m,p,q$，对于一个长度为 $n$ 的序列 $a_i$，$a_i$ 的每一位都是 $[1,m]$，如果整个序列的 $gcd$ 小于等于 $q$，且整个序列的 $lcm$ 大于等于 $p$，那么这个序列是合法的，每个合法序列的价值是 $\prod_{i=1}^na_i$，求所有合法序列的价值的和

$n\le 998244351,p,q\le m\le 2\times 10^5$

题目描述

http://codeforces.com/gym/103366/problem/I

简要题意：给定一个棵有 $n$ 个点的无根树，现在有 $m$ 次操作，操作有三种：修改某一个点的权值；修改某一条边的权值；查询每个点完成作业的时间。在这颗树上，每个点有一个人，每个人单独完成作业所需的时间为 $a_i$，每个人除了单独完成作业，还可以去别人那里请教，如果 $i$ 要向 $j$ 请教，则必须等 $j$ 完成作业之后，才能出发到 $j$ 所在的位置请教，然后返回自己所在的位置，注意如果 $i$ 向别人请教作业，那么只有当他回到自己位置后，才算他完成作业，另外需要注意的是，$i$ 到 $j$ 请教并返回的总时间为 $i$ 到 $j$ 的最短路径的长度的一倍

$n,m\le 10^5$，最多只有 $200$ 查询

题目描述

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

简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有两种，给定 $l,r$ 区间中每个 $a_i$ 变成 $\sqrt{\lfloor a_i\rfloor}$；给定 $l,r$，区间中每个数 $a_i$ 变成 $a_i^2$，在所有操作进行完之后，请输出 $\sum_{i=1}^na_i$

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

题目描述

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

简要题意：给定一个棵有 $n$ 个点的无根树，现在有 $m$ 次操作，操作有两种，给定 $x,y$ 求 $x$ 到 $y$ 的简单路径上所有点组成的可重集合的子异和；给定 $x,y,z$ 将 $x$ 到 $y$ 上每个点异或上 $z$，其中集合 $S$ 子异和的定义为子集 $S$ 的所有子集的异或和的和

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

题目描述

https://codeforces.com/problemset/problem/730/I

简要题意：现在有 $n$ 个人，要将这些人分成两个队伍，每个人只能属于一个队伍，如果将第 $i$ 个人分到第一个队伍，那么能够得到 $a_i$ 的收益，如果将第 $i$ 个人分到第二个队伍，那么将得到 $b_i$ 的收益，第一个队伍有 $p$ 个人，第二个队伍有 $s$，求收益最大的分配方案

$n\le 3000$

简介

本质上就是用类似于堆或者 $dp$ 的东西来模拟费用流增广的过程

题目描述

https://ac.nowcoder.com/acm/contest/5477/H

简要题意：现在一个空栈和 $n$ 次操作，操作有三种：在时间 $t$ 入栈 $v$；在时间 $t$ 出栈；求时间 $t$ 的栈顶元素，需要注意的是每次查询操作，是相当于将之前操作按照给出的时间排序依次执行的结果，输入保证出入栈合法，且时间 $t$ 互不相同

$n\le 2\times 10^5$

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=3032

简要题意：给 $n$ 堆石子，每次操作可以 $n$ 堆石子中取若干个石子或者将一堆石子数大于等于 $2$ 的石子分成两堆石子

$n\le 10^6$

题目描述

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

简要题意：现在有 $n$ 个派以及 $m$ 个奶牛，第 $i$ 个奶牛只吃 $[l_i,r_i]$ 的派，同时第 $i$ 个奶牛如果吃到派，则有 $w_i$ 的贡献，现在要求选择若干个奶牛，按照某种顺序排序后，保证每个奶牛都能吃到派，且它们的贡献和最大，当轮到一个奶牛吃派时，它会将 $[l,r]$ 内所有剩下的派都吃掉

$n\le 300,m\le \frac{n(n+1)}{2}$