RainAir
My OI Blog
RainAir

题解
文章归档

「CF379D」New Year Letter

题目描述 令 $s_i$ 表示第 $i$ 个字符串,我们有递推式 $s_i = s_{i-2}+s_{i-1}$(其中+ 是将两个字符串拼接起来的符号) 现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ ,满足 $s_k$ 中串 AC 作为子串出现了 $x$ 次。 $3 \leq k \leq 50,0 \leq x \leq…

   313   2019-10-21   313 去吊打作者

ARC093F - Dark Horse

题意 有 $2^N$ 个人打锦标赛,他们的过程是随机一个排列,然后按照这个排列站好。每轮是第 $2_i − 1$ 个人和第 $2_i$ 的人比赛,败者淘汰。 你是 $1$ 号选手,你碰到$A_1,A_2,\cdots,A_m$ 会输,碰到剩下的会赢。如果比赛和你无关,那么编号小的赢。 求有多少个排列…

   233   2019-10-18   233 去吊打作者

ARC096E - Everything on It

题意 求有多少个子集族,满足: 1. 其中任意一个子集都是 $[n]$ 的子集; 2. 任意两个子集互不相同; 3. $1,2,\cdots ,n$ 都在其中至少出现了 $2$ 次。 答案对 $M$ 取模。 $2 \leq N \leq 3000,10^8 \leq M\leq 10^9 +9$,$M$ 是质数。 题解 dyls 说:看到子集族先…

   160   2019-10-18   160 去吊打作者

ARC099 题解

C - Minimization 普及组题,不说了。 代码 D - Snuke Numbers 题意 将 $x$ 的数字和记作 $S(x)$。 称 $n$ 是好的,当且仅当 $\forall m>n, n \leq m$ 。 求第 $K$ 个好的数字。 保证答案不超过 $10^{15}$。 题解 全场最难的题。。。 我们设 $f(x)$ 表示满足 $\f…

   177   2019-10-18   177 去吊打作者

ARC101 题解

C-Candles 普及组题,不说了 代码 D-Median of Medians 题意 定义序列 $a_1,a_2,\cdots ,a_n$ 的中位数为排序后从小到大第 $\lfloor \frac{n}{2}\rfloor+1$ 个数。 给定长度为 $N$ 的序列 ${a}$,对于每一对 $1 \leq l \leq r \leq N$ 的 $[l, r]$,把 $a_l,a_{l+1…

   199   2019-10-18   199 去吊打作者

「ARC102E」Stop. Otherwise...

题目大意 有 $N$ 个 不可区分的 $K$ 面骰子。 对于每个 $i = 2, 3, \cdots , 2K$,求有多少种方案使得:任意两个点数不同 的骰子朝上的面之和不为 $i$。 答案对 $998244353$ 取模。 $2 \leq N \leq 2000,1 \leq K \leq 2000$。 题解 我们考虑对于 $i=x$ 怎么去计算…

   177   2019-10-17   177 去吊打作者

「NOI2017」游戏

建议大家去 UOJ 交题:链接 题目描述 有 $n$ 场游戏和三种车,每个游戏可以选择用一种车,每个游戏可能要求不能使用某种车,也可能没有要求。 给出 $m$ 个要求,表示如果第 $u$ 个游戏用了 $x$ 车,那么第 $v$ 个游戏要用 $y$ 车。求一种合法方案。 $n \leq 5 \times…

   235   2019-10-12   235 去吊打作者

「BZOJ2788」Poi2012Festival

题意 今有 $n$ 个变量, $x_1,x_2,\cdots,x_n$,还有 $m1+m2$ 个限制条件: 1. $x_a + 1 = x_b$ 2. $x_c \leq x_d$ 在满足所有限制的前提下,求集合 ${x_i}$ 大小的最大值(也就是不相同的数最多)。 题解 首先我们按照差分约束将图建出来,然后判出无解。 我们考虑…

   134   2019-10-12   134 去吊打作者

「CF599E」Sandy and Nuts

题意 给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。 $n \leq 13$,限制总数 $\leq 100$ 题解 这个题目太神仙了。。远古 CF 场的题目还是好。 考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 …

   213   2019-10-11   213 去吊打作者

「CF860E」Arkady and a Nobody-men

题目描述 给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数,定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的集合)。 现在要对于每一个点,求出 $f(v)$ $n \leq 10^5$ 题解 如果这题 $n \le…

   132   2019-10-09   132 去吊打作者
加载更多
标签
近期评论