RainAir
My OI Blog
RainAir

RainAir’s Blog

  SDOI2020.rp++ | 如果进队了你们可以任意指定一句话挂这里一天

「JZOJ6391」区间

题目链接 题解 一个我想不到的性质:每个点至多会被覆盖两次。 因为如果一个点被覆盖三次,那么肯定有一条线段的效果是可以被另外两条完全表达出来的,所以可以删去这个线段。 我们先将线段按照右端点排个序,有了这个性质,又因为它是个最优化问题,启发我们设 $f_{…

   227   2019-10-28   227 去吊打作者

JZOJ CSP 模拟 10.23

A.珂学家 题目链接 题解 如果 $l,r$ 的范围不大的话,我们记 $S$ 表示将每个区间的权值都加在区间上后得到的序列,$A_i$ 表示第 $i$ 个区间区间加后得到的序列。我们考虑预处理:答案多项式$$Ans = S^2 - \sum_{i=1}^n A_i^2$$ 前面可以 NTT,后面发现是一些区间加…

   266   2019-10-25   266 去吊打作者

「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…

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

CSP2019 游记

Day -inf 天天被校内神仙 shq,lgy 吊打,天天被市内神仙 zs 吊打,天天被省内神仙吊打。。。zbl [crayon-5e854e932fe9a190126613/] 先用这个头文件加 rp 吧。 发现突然出现很多我我不认识的省里非常强的人。。包括爆切 SAM/爆切 CF /爆切 SDOI2018R2 并怒斥难度低…

   1,454   2019-10-18   1,454 去吊打作者

ARC093F - Dark Horse

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

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

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 说:看到子集族先…

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

ARC099 题解

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

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

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…

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

「ARC102E」Stop. Otherwise...

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

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

「初赛」无向连通图计数

看了一个初赛题,题目大概是这样的: 由四个有标号的点构成的简单无向连通图的个数是: 感觉这应该是个经典问题。。就稍微写一下。 初赛上怎么解决 我们设 $f_n$ 表示 $n$ 个点的连通图的数量,转移只需要考虑计算出不连通的数量。可以枚举一号点所在的连通块大小计…

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