DDOSvoid's Blog

题目描述

简要题意：现在有 $n$ 个人，第 $i$ 个人手里有一个数字 $i$，现在开始传数字，第 $i$ 个人会将他手里的数字传给 $p_i$，$p_i$ 是一个排列，同时现在有 $m$ 次询问，每次询问给出一个整数 $x$，求传了 $x$ 轮后，每个人的编号乘上他手里的数字的和

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

https://ac.nowcoder.com/acm/contest/31454/E

题目描述

简要题意：现在有 $n$ 堆石子 $a_i$，$Alice$ 和 $Bob$ 准备玩最经典的取石子游戏，但是现在 $Bob$ 可以作弊，$Bob$ 在游戏开始前，可以选择移除 $k\in [0,n-1]$ 堆石子，现在再给定一个整数 $d$，求 $Bob$ 移除 $k$ 堆后先手必败的方案数，要求 $k$ 是 $d$ 的倍数

$n\le 5\times 10^5,d\le 10, a_i\le 10^6,\sum_{i=1}^na_i\le 10^7$，空间限制 $64MB$

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在要求至多选择 $m$ 个数，需满足选择的任意两个数都不相邻，求最大价值

$n\le 5\times 10^5,|a_i|\le 10^6$

题目描述

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}^{n}cnt_{a_i\oplus a_j}$，其中 $cnt_x$ 表示 $x$ 的二进制表示下 $1$ 的个数， $\oplus$ 表示异或

$n\le 36666666,a_i\le 2^{64}-1$

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作有两种：给定区间 $[l,r]$ 和 $v$，将区间 $[l,r]$ 加上 $v$；给定区间 $[l,r]$，求区间 $[l,r]$ 的历史版本和

$n,m\le 10^5,a_i,v\le 1000$

题目描述

https://codeforces.com/gym/103069/problem/G

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定区间 $[l,r]$，求区间 $[l,r]$ 有多少对子区间 $[i,j]$， 满足 $[i,j]$ 内不同的 $a_i$ 有奇数个

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

题目描述

https://ac.nowcoder.com/acm/contest/11188/E

简要题意：现在有一个长度为 $n$ 的序列 $a_i$，定义 $F_0(l,r)$ 为区间 $[l,r]$ 内的逆序对个数，同时 $F_k(l,r)=\sum_{i=l}^r\sum_{j=i}^rF_{k-1}(i,j)$，给定 $k$，求 $F_k(1,n)$

$n\le 3\times 10^5$

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，定义一个生成树 $T$ 的价值为 $\sum_{i=1}^{n-1}w_{e_i}\times(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})$ ，求所有生成树的价值之和

$n\le 30,m\le \frac{n(n-1)}{2}w_i\le 152501$

题目描述

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

简要题意：现在有 $n$ 个城市，有 $n-1$ 个公司来修路，每个公司可以修某些路，现在要求恰好修 $n-1$ 条路使这 $n$ 个城市连通并且每个公司恰好其中一条路的方案数

$n\le 17$

题目描述

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

简要题意：给定一个完全图，每条边的权值表示这条边存在的概率，求存在的边恰好构成一棵生成树的概率

$n\le 50$