DDOSvoid's Blog

题目描述

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

简要题意：现在有 $T$ 组询问，每次询问给定 $n$，求所有长度为 $n$ 的每个位置是 $[1,n]$ 的序列的价值和，定义一个序列的价值和为 $\sum_{i=k}^{\min(k,n-1)+n-1}\frac{lcm(i-k+1,n)}{k+1}$，其中 $k$ 是该序列中未出现的数的种数

$n,T\le 10^6$

题目描述

https://codeforces.com/problemset/problem/660/E

简要题意：给定 $n,m$，求所有长度为 $n$ 的每个位置为 $[1,m]$ 的序列的价值和，定义一个序列的价值为其本质不同的子序列的数量

$n,m\le 10^6$

题目描述

https://codeforces.com/problemset/problem/1613/F

简要题意：给定一棵以 $1$ 为根 $n$ 个点的有根树，现在要为每个点赋一个权值 $p_i$，要求 $p_i$ 为 $[1,n]$ 的排列，且对于 $u$ 为 $v$ 的父亲 $p_u\neq p_v+1$，求方案数

$n\le 2.5\times 10^5$

题目描述

https://codeforces.com/contest/1749/problem/F

简要题意：给定一棵 $n$ 个点的无根树，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x$，求 $x$ 的权值；第二种操作给定 $u,v,k,d$，将距离 $u$ 到 $v$ 的简单路径的距离小于等于 $d$ 的点的点权加上 $k$

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

题目描述

https://codeforces.com/contest/1749/problem/E

简要题意：给定一个四连通网格图，其中有一些点是障碍，需要添加最小的障碍使得不存在一条从第一行出发到达最后一行的路径，需要保证任意两个障碍不相邻

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

题目描述

https://codeforces.com/contest/1732/problem/D2

简要题意：现在你有一个集合 $S$，$S$ 中只有一个元素 $0$，同时有 $q$ 次操作，操作有三种，第一种操作向集合中加入一个数 $x$；第二种操作从集合中删掉数 $x$；第三种操作给定 $k$，询问集合的 $k-mex$，$k-mex$ 表示最小的数 $x$，满足 $x$ 是 $k$ 的倍数，且在 $S$ 中不存在

$q\le 2\times 10^5,x,k\le 10^{18}$

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=1}^n\varphi(gcd(a_i,a_j^3))$

$n\le 3\times 10^5,a_i\in[1,n]$

题目描述

https://loj.ac/p/6289

简要题意：给定一个 $n$ 个点有点权的无根树，求所有大小为 $m$ 的点集的贡献和，要求点集内不存在任何两点相邻，一个点集的贡献是点集内所有点的点权积

$n\le 8\times 10^4$

题目描述

https://atcoder.jp/contests/abc269/tasks/abc269_h

简要题意：给定一棵大小为 $n$ 的有根树，求对于所有 $k\in[1,n]$，有多少大小为 $k$ 的集合，满足集合内不存在任意两点使得一个点是另一个点的祖先

$n\le 2\times 10^5$

题目描述

简要题意：给定一个长度为 $n$ 的串 $S$，定义一个长度为 $k$ 区间序列 $[l_1,r_1],\cdots,[l_k,r_k]$ 为一个合法区间序列，当且仅当满足于 $l_1<l_2<\cdots<l_k\le r_k<r_{m-1}<\cdots <r_1$，求有多少区间套序列满足，$\forall i\in[1,m],S[l_i..r_i]$ 是回文串

$n\le 10^6$