green

¶brute force

¶151: Good Triples

在$digsum$ 相加过程中，若有进位，则每次进位，$digsum(n)$ 都比$\sum{digsum(i)}$ 少9，必不可能相等，所以每一位单独考虑，即拆位。
设$n$ 的每一位数为$m$ ，将其分成三份，有$C_{m+2}^2$ 种分法。
将每一位的分法相乘即为答案。

¶152: Chtholly’s request

打表发现：第$i$ 个$zcy$ 数的形式是$i+i[::-1]$。暴力枚举即可。

¶153: Binary String Copying

考虑该区间排序后最终形式是:$00000……1111$ 。
所以有效排序区间应该从该区间内的第一个$1$ 开始到最后一个$0$ 结束。
预处理出每个数右边（包含）第一个$1$ 的下标和左边（包含）第一个$0$ 的下标。
对于每次询问，得到有效区间，若$r<=l$，则统一记为$(1，1)$，存入$set$。

¶154: Vampiric Powers, anyone?

先选一个后缀$sub_i$，得到一个后缀值放在最后。再次选一个后缀$sub_j$，所得新的后缀值为$i,j$ 之间的异或值，所以转换为求最大异或区间值。
可以考虑字典树。但由于本题值域较小，可以先枚举右端点，再枚举前面的值。

¶155: Tracking Segments

二分答案。
$check$:把前$x$ 次的$1$ 都修改上，做一遍前缀和（快速统计区间内1的个数），枚举所有询问，检查是否有$cnt1>cnt0$ 。

¶156: Ice Sculptures

枚举每隔几个人里选一个，即$n$ 的约数。
设某个约数为$x$ ，在枚举前$x$ 个人里选哪个，再每个$x$ 人选一个。
对于每个约数，每个人都会枚举到一次，$O(n)$。$2\sqrt(n)$ 个约数，总时间复杂度为$O(n\sqrt(x))$ 。

¶157: Martian Dollar

数据很小，暴力枚举买入$i$ 和卖出$j$ 的时刻即可，$ans=max(ans,b$) 。

¶158: The Text Splitting

找出满足$ai+bj=n$ 的$i,j$ 。
数据很小，直接暴力枚举$i$ ，再查看是否存在适合的$j$ 即可。
增强数据的话或许能用扩展欧几里得。

¶159: Tear It Apart

暴力枚举所有最后留下的字母，计算所需步数。
记录所有非留下字母的下标，若当前下标与上一个删除的下标相邻，则放入下次，注意他的下标要减去已删除的字母数量才是他的新下标。直至删完。

¶160: Fire Again

bfs即可。

¶161: Constructive Problem

先求出$m=Mex(a)$ 。
想让$Mex(a)$ 变大，必定要将一些数据改成$m$ ，然后新的$Mex(a)=m+1$ 。
如果$m+1$ 本就存在，就要将第一个$m+1$ 到最后一个$m+1$之间的数都改成$m$ 。但不能修改后使$Mex(a)$ 变小，这种情况只有可能是某个小于$m$ 的数$x$ 的所有数都在这个区间内，也就是说把这个区间内的数都修改了就不存在这个$x$ 了。
如果$m+1$ 不存在，只要让一个不会影响$Mex(a)$ 的数改成$m$ 即可，可以是大于$m+1$ 的数或者小于$m$ 但个数不为$1$ 的数。

¶162: Accounting

观察数据范围，发现$x$ 最大为$1000$ 。
暴力枚举$x$ 从\-1000 到$1000$ ，快速幂$check$ 。

¶163: IQ test

求出每个数的奇偶性，输出不同的那个的下标即可。

¶164: Bargaining Table

暴力枚举左上方点和长宽即可。

¶165: Triangle

$RIGNT$:某两个向量点积为$0$。
$ALMOST$:枚举所有点朝四个方向移动后的新向量，判断是否点积为$0$ 且叉积不为$0$ 。
剩余情况为$NEITHER$ 。

¶166: Make It Permutation

答案最大为$cn+d$ 。
排序后从左往右遍历，看$a[i]$ 是否等于排列的下一个数$j$。
若$a[i]==j$，则$j++$ 。
若a[i]\<j，而$j$ 是从小到大枚举的，比当前$j$小的必定已经出现过，将$a[i]$删去，当前代价加$c$。
若$a[i]>j$，则将$j$ 到$a[i]-1$都加入，$j=a[i]+1$，当前代价加d\*(a[i]-j)。
每次处理完后将$ans$ 与res+c\*(n-1-i) 比较并更新，即将后面的数都删去。

¶167: Pull Your Luck

看到$p$ 这么大，可以猜到其中有循环节。
当$f=2n$ 时，$(f(f+1)/2)$ ，$x$ 又回到起点，接下来又是和之前一样的循环（可以模拟验证）。
所以枚举到$min(p,2n)$ 即可。
更暴力的解法：不知道循环节在哪？直接记录$y=(i(i+1)//2)$ 的次数，超过一定次数，直接输出$'No'$ 。至于到底多少次，实测$100$ 即可。

¶168: Unforgivable Curse (hard version)

排序后不等直接$NO$ 。
只有$n>=k+2$ 才能实现相邻交换，$n<k+2$ 的情况直接特判。
当$n>2k$ 时，相邻的数都能换。
这之间的情况，不能换的范围在$n-k+1$ 到$k$ 之间，这之间都相等就$YES$，否则$NO$。

¶169: Unforgivable Curse (easy version)

排序后不等直接$NO$ 。
$k=3$ ，可以交换间隔为$3$ 或$4$ 的数。如果至少有$5$ 个数，就可以交换边缘相邻的两个数。
但此时还有中间一个数不能动，但长度为$6$ 时相邻的数都能换。
对于小于$6$ 的情况，可以$bfs$ 。
大于等于$6$ ，排序后不等直接$NO$ ，否则$YES$。

¶170: Same Count One

首先$1$ 的总个数不是$n$ 的倍数时必不可能。
统计出每个数组$1$ 的个数。
枚举每一位，找出其中 这一位为$0$ 且$1$ 的个数小于目标个数的数组 和 这一位为$1$ 且$1$ 的个数大于目标个数的数组，尽可能配对。

¶constructive algorithms

¶171: Jumping Through Segments

二分答案$x$。
$check$ ：记录可以走到的范围。
一开始的范围为$L=-x,R=+x$ ，每次与下一个要到的区间取交集：$L=max(L,l),R=min(R,r)$ ，然后之后能走的范围为$L-x,R+x$。
若无交集，则$false$ 。

¶172: ABBC or BACB

如果一段$A$ 串前面或者后面存在一个$B$，那么这段中的$A$ 都可以被替换。
$s$ 中必须同时出现$A$ 和$B$ ，否则答案为$0$ 。
如果最前或最后为$B$ ，那么所有的$A$ 都可以被替换。
否则就是若干$B$ 插在$A$ 串中，只有一段$A$ 不能被替换，答案为所有$A$ 的个数减去最短的那一串的长度。

¶173: Salyg1n and the MEX Game

最优策略：$Alice$ 先插入$Mex(S)$ ，然后$Bob$ 每次拿出什么数就插入什么数。

¶174: Madoka and Childish Pranks

若$s[1][1]==1$ ，直接无解。
从右下到左上遍历，若$s[i][j]==1$，则将这个方格与它左边一个方格染色；
如果是最左边的，则与上边一个染色。

¶179: No Prime Differences

若$m$ 为素数，从上往下从左往右填充即可，差值只有$1$ 和$m$ 。
否则将每一行都加上一个偏移量，使差值为$1$ 和$m+1$ 。
加偏移量方法：ans[i][j]=1+i\*m+(i+j)%m 。