JAG2018 Day2 做题记录
Japan Alumni Group Summer Camp 2018 Day 2 做题记录：
更好的阅读体验
vp 赛时过题：ABCDEFH。
A 10^N+7
哈哈，CRT 板子。
Submission
B Coins
好难，不会正解。
写个暴力发现 \(n>50\) 时答案均为 \(500\)，小数据写个 \(\text{bitset}\) 就好了。
正解好像是发现除了最大面值，其他的面值使用次数都不能达到其下一个面值与其的商，背包即可。
Submission
E Self-contained
发现答案只有两种形式：\(0,a,b,a+b\)，或者是 \(0,g,2g,\cdots,kg\)。
证明可以看 wxh 的题解。
第一种情况做一遍卷积，第二种情况枚举 \(g\) 调和级数即可。
Submission
H Prefix Suffix Free
简单题，可惜没早点看到。
一眼容斥，然后令 \(f_i\) 为钦定 \(S_{0,\cdots,i-1}\) 为后缀的容斥系数之和，做个 kmp dp 一下就好了。
Submission
C Equiangular
好难，为什么大家都会！！！
可以发现合法的多边形一定满足对于任何连续的三条边 \(a,b,c\)，都有 \(a=c\)。
于是分边长全部相等和不相等讨论一下，不相等就枚举一下和，复杂度就是枚举因数的复杂度。
Submission
D Knapsack And Queries
一眼原题。
用两个栈模拟队列，一个栈弹空就把另一个栈劈成两半暴力把一半塞到弹空的栈中，这样压/弹栈次数势能分析是 \(O(n)\) 的。
询问单调队列优化一下，复杂度 \(O(q\cdot\text{mod})\)。
Submission
F Point Sequences
直接写计算几何肯定会被卡精度，但是发现操作与真正的数值大小无关，在模意义下也能成立，直接模拟即可。
Submission
J AB Sort
好难/ll。
考虑如何求 \(f(S)\)，我们去掉 \(S\) 最后面连续的 B，令 A 为 \(-1\)，B 为 \(1\)，将前缀和绘成折线图后，可以发现一次操作会把所有的峰往下移动（其余位置一定不会在操作后超过峰）。
由于最后的形态是 AAAAABBBB，所以所有的峰一定会移动到 \(1-x\)（其中 \(x\) 是 A 的总数），那么答案就是最大前缀和加上 A 的数量。
由于是 \(f(B+S+A)\)，所以并不需要去除结尾的 B，线段树维护即可。
Submission
K Short LIS
maroon 的题。
首先令 \(p_i=n-p_i+1\)，题意变为 LDS 不超过 \(2\)。若 \(A>B\)，那么交换下标和值，显然 LIS 和 LDS 还是不变。
根据 Dirworth 定理可知序列可以划分成两个上升子序列，我们将序列前缀最大值位置提取出来，剩余位置必须是上升的。所以我们只需要确定序列的前缀最大值位置与值即可。
我们考虑一个非前缀最大值位置 \(p_x=y\)，它前面至少有一个比它大的，后面所有数一定都比它大，那么 \(1+(n-x)\leqslant n-y\)，即 \(x>y\)。
由此可知位置 \(A\) 一定是前缀最大值。
将前缀最大值形成的柱状图放到平面上，考察其上方的路径，可以发现其是一条从 \((0,0)\) 到 \((n,n)\)，只使用右步、上步，不低于 \(y=x\) 的格路。
（图源 ）
而 \(p_A=B\) 的限制就变成：路径在 \((A-1,B-1)\) 使用了一个上步和一个右步到达了 \((A,B)\)，因此我们可以将路径拆成两个部分，每个部分用折线法算一下方案数相乘即可。
复杂度 \(O(n)\)。
Submission
I ADD DIV MAX RESTORE
wxh 的题解太简短了，看了 Itst 代码才会（
可以发现一个区间进行若干次整体操作后最大值位置不会改变，所以考虑给线段树上每个位置维护一个类似 \(\lfloor\frac{ax+b}{c}\rfloor\) 的 \((a,b,c)\) 标记。
考虑标记 \(p,q\) 如何合并，若 \(p.c\cdot q.c\leqslant 10^8\)，那么我们可以直接合并成 \((p,a,p.b+p.c\cdot q.b,p.c\cdot q.c)\)，否则可以发现 \([0,10^8]\) 内的数在运算之后只有两种结果，随便推一下结果即可。
复杂度 \(O(n\log n)\)。
Submission
G Construct One Point
判定直接用 Pick 定理就好了，重点在构造。
不妨将 \(A\) 平移到 \((0,0)\)，且 \(B\) 在 \(AC\) 逆时针方向。（否则可以对称过去）
令 \(AC\) 为三角形的最长边，那么若上面存在整点，取一个距离中点最近的整点 \(D\)，然后找一下 \(BD\) 上的整点，若没有就递归到两边有整点的三角形找。（显然只会递归 \(\log\) 层）
否则若 \(C=(x,y)\)，那么 \(\gcd(x,y)=1\)，考虑直接构造出 \(D\) 的下标。
用 exgcd 解出一组 \((u,v)\) 满足 \(uy-vx=-1\)，且 \(0\leqslant u
此时 \(\vec{AD}\times\vec{AC}=-1\)，也就是 \(AC\) 在 \(AD\) 顺时针方向，且 \(S_{\triangle ACD}=\frac{1}{2}\)，根据 Pick 定理可知 \(\frac{1}{2}=i+\frac{3}{2}-1\)，即 \(i=0\)，也就是 \(\triangle ACD\) 内部无整点。
我们作 \(D\) 关于 \(C\) 的对称点 \(D'\)，可以类似地证明 \(\triangle ACD'\) 内部无整点。一直作下去可知直线 \(CD\) 与 \(A\) 关于 \(CD\) 平行线组成的带形区域内无整点。
同理可知直线 \(AD\) 与 \(C\) 关于 \(AD\) 平行线组成的带形区域内无整点。
那么 \(B\) 一定在直线 \(CD,AD\) 的逆时针方向，于是 \(D\) 在 \(\triangle ABC\) 内部，证毕。
Submission（还没调出来）