171 AGC059E Grid 3-coloring
一个很脑洞的想法，我们构造一个矩阵，使得其与颜色模 \(3\) 同余。
若能构造一个这样的矩阵一定能得到答案，而可以发现一个答案矩阵也能构造出一个数字矩阵。
证明：按照 \((i,j)\) 字典序填数，如果 \(i=1\) 或 \(j=1\)，那么可以根据其邻居填数，否则若其两个邻居颜色相同，则正常填色，否则填其左上方格子的颜色。
尝试写一个这个矩阵存在的必要条件：外围存在填数方案且外围相对的数之间差绝对值不超过 \(n-1\)。
事实上这也充分，我们直接写出 \(a_{i,j}=\max\{a_{1,j}-(i-1),a_{n,j}-(n-i),a_{i,1}-(j-1),a_{i,n}-(n,j)\}\)，因为四个数都模 \(2\) 同余 \(i+j\)，因此相邻奇偶性一定不同，而四个数值变化不超过 \(1\)，因此差一定为 \(1\)。
172 P8125 [BalticOI 2021 Day2] The short shank
我们可以把人分成两类，造反事件在 \(T\) 之前的与在 \(T\) 之后的，分别成为激活点和非激活点。
对于一个非激活点 \(x\)，可以找到一个最靠右可以传播到他的激活点 \(l\)，那么 \(x\) 不被激活当且仅当没有 \(l\) 或 \([l,x]\) 中有隔板。
一个性质：\([l,x]\) 区间要么不交，要么包含，因为靠右的 \(x\) 对应 \(l\) 一定能激活靠左的 \(x\)。
那么可以对区间建出树的结构，长链剖分取前 \(d\) 长链即可。
173 NFLSPC #2 Polynomial
最后的操作序列形如 \((((x^{k_0}+c)^{k_1}+c_1)^{k_2}+\cdots+c_m)^{k_m}\)。
先假设 \(k_0=1\)，那么可以归纳证明 \([x^{n-1}]Q(x)=nc\)。
得到 \(c\) 之后，我们将 \(Q(x)\) 平移 \(c\) 位来还原，这是一个卷积形式，我们可以得到 \(Q'\)。
我们将 \(Q'\) 所有非零系数的下标取 \(\gcd\) 可以得到 \(k_0\)，若 \(k_0=1\) 则无解，否则继续做下去。（每次 \(n\) 至少减半）
复杂度 \(O(n\log n)\)。
174 NFLSPC #3 星
直接给出构造：对于所有 \(-\frac n2\leqslant x\leqslant\frac n2-1\)，取 \((x,x^3)\)，方案数可做到 \(\frac{n^2}{8}\) 级别。
我们发现对于 \(a+b+c=0\)，\((x-a)(x-b)(x-c)=x^3+(ab+bc+ac)x-abc\)，因此 \((a,a^3),(b,b^3),(c,c^3)\) 均在 \(y=-(ab+bc+ac)x+abc\) 上。
任取 \(x<0<y\)，那么 \(-x-y\) 一定在范围内，所有 \(-x-y=0\) 的三元组会被统计一遍，所有 \((x,x,-2x)\) 型三元组会被统计一遍，其余三元组会被统计两遍。
那么答案不少于 \(\frac{(\frac n2)(\frac n2-1)+\frac n2-\frac n2}{2}=\frac {n^2}8-\frac n4\)。
175 NFLSPC #3 计算几何
给出结论，答案为 \(2n-2-\) 凸包点数。
先证明这是答案下界。
我们每次取出点集的凸包，并将这些点去掉，重复做直到所有点被去掉。我们能得到 \(k\) 个凸包 \(l_1 \cdots l_k\)。
对于相邻层之间三角剖分，可以剖出 两层凸包点数和 个三角形，最内部的凸包 \(l_k\) 也进行三角剖分，于是我们能得到 \((l_1+l_2)+(l_2+l_3)+\cdots+(l_k-2)=2n-l_1-2\) 个不交三角形，每个三角形至少需要一个红点。
接下来给出构造。
我们随机一个与所有蓝点直线不平行的向量 \(P\)（不妨令 \(|P|=eps\)），将所有点平移 \(P,-P\)，取出这 \(2n\) 个点，这个点集一定合法。
原因是，对于任意三角形，三个角与三个对顶角恰好能覆盖一个圆周所有的角度（除了三角形的三边对应角度），向量 \(P\) 一定会落在这些角的范围内。
但是 \(2n\) 还不够，注意到有 \(l_1+2\) 个红点落在了凸包外，我们可以将其删掉。（凸包上每个点会平移出至少一个凸包外的红点，凸包最两侧的点平移出的两个点都会在凸包外）
176 P8946 The Lost Symbol
标签：frac,31,2023,矩阵,凸包,放映机,n2,2n From： https://www.cnblogs.com/xiaoziyao/p/17077752.html