MENU

Tags: 构造

Solution. P1 Sandalphon

Description

以下区间均只考虑整数。

给定 $n,k$,将 $1\sim2^n$ 的 $2^n$ 个数划分为两个集合 $A$ 与 $B$,使得 $\forall p\in[0,k]$,有 $\sum_{x\in A}x^p=\sum_{x\in B}x^p$。

$1\le n\le16,0\le k<n$

Read More

Solution. CF1329D Dreamoon Likes Strings

Description

我们称相邻字符不同的字符串是美丽的。

给定字符串 $s_{1\dots n}$,每次操作可以删除 $s$ 的一个美丽子串,剩下的字符会按照原来的顺序拼接起来。

求将 $s$ 变成空串的最小步数。

$n\le2\times10^5$

Read More

Solution. CF1710D Recover the Tree

Description

根据以下信息构造一棵树:

  • 树的节点个数为 $n$,编号为 $1\sim n$。
  • 对于每个编号区间 $[l,r]$ 给出是否构成连通块。

$n\le 2000$

Read More

Solution. Codeforces Round #781

现在是 12:35,只做了 ABC,简单记一下关于 DE 的想法。

D,给了 30 次询问,从信息论的角度看,$\left\lceil\log_2 10^9\right\rceil$ 恰好等于 30,那是否要求了每一次询问都将可能的答案减半,或者每次询问确定一个二进制位这样。

能够想到的就是可以通过 $\gcd(x,x+prime)$ 来判断 $x$ 是否拥有 $prime$ 这个质因子。

Read More

Solution. Codeforces Round #779

Div.2 only,打得烂到飞起,简直像是一年前的自己。

上来先 D 开,一看发现 D 大概很简单,写了一发过了 D1 的 pretests,D2 看了看没啥思路就先放着,A 和 B 打完之后(B 上浪费了不少时间)跑去看 C,结果想了一辈子也不会,实际上我那个 -1 的 submission 已经无限接近正解了。

Read More