utpc2012 Wrapping 题解
题目链接题意用一个绳子去包绕一个三维空间的单位立方体，要求绳子有一段和向量 $(a,b,0)$ 平行。求最少需要的绳子长度。$a,b \leq 10^{18}$题解绕绳子问题由于会循环多个面，所以我们首先考虑将这个东西展开在无限的二维平面上，这样跳跃到另一个面就可以看作是走到相邻的面了。考虑一个形象的过程：先从结束的位置把绳子断开，然后我们按照需求往上或者往右滚动，这个绳子也会被留在平面上形...
题目链接题意用一个绳子去包绕一个三维空间的单位立方体，要求绳子有一段和向量 $(a,b,0)$ 平行。求最少需要的绳子长度。$a,b \leq 10^{18}$题解绕绳子问题由于会循环多个面，所以我们首先考虑将这个东西展开在无限的二维平面上，这样跳跃到另一个面就可以看作是走到相邻的面了。考虑一个形象的过程：先从结束的位置把绳子断开，然后我们按照需求往上或者往右滚动，这个绳子也会被留在平面上形...
A如果 $x > k$ 那么可以随便选。$[1,k]$ 我们选择后一半，这样保证任意两个数字相加都 $> k$ 就好了。B直接枚举即可。$0,1,8$ 反转后不变，$2,5$ 反转后互换。C$\geq s$ 最小，也就是尽量靠近 $s$。于是从大到小枚举相同的前缀长度，每次暴力看一下是否有一种方案可行，如果有的话就直接贪心按照字典序放置剩下的字符。D我赛时的做法：对于 $\leq...
A暴力枚举每个字母对应的括号即可。$O(2^3 n)$CodeB发现行列之间的影响只会在于四个角上，所以暴力枚举四个角是否填，然后确定上下界判断即可。$O(2^4)$。CodeC显然 $a_i,b_i > 0$ 和 $a_i,b_i < 0$ 可以分开做：我们只考虑 $a_i,b_i > 0$ 的情况。排序之后，我们枚举「推」到的最后一个位置是 $b_x$，那么我们找到 $...
上来因为 $C$ 题（细节没写好我甚至写了个对拍）和 $E$ （也是细节没写好）的问题卡了很长时间，导致差点没做出 $F$ 和没做出 $G$ ，并且最后 $E$ 题还 fst 了。要不然怎么说也上红了A维护当前有几个 $0$，几个 $1$ 即可。B由于有一个 $0$ 列和 $10^6+1$ 列，所以这大概率是个分类讨论题：先判断是否都堵住了，用 $|a_i-a_{i-1}| \leq 1$ ...
感觉只会抄题解。。AGC020E首先自己可以想到如果只是要单纯的求一个串的方案数可以区间 dp：观察这个表达式，可以写成f := g | g + f g := '0' | '1' | '(' + f + '*' + 'x' + ')'其中 x 是一个数字，要求 $1$，并且 $f$ 是 $g$ 的一个长度为 $x$ 的循环节。那么就可以根据上面的定义写出 dp 了：设 $f_{l,r},g...