A. Display The Number
题意：最多让n个灯管同时亮，问其表示的最大数是多少？
思路：观察0-9表示所需要的灯管数量，1最少，只需2个；7次小，需要3个；
贪心考虑，一个数位数越多，越大。如果剩下2个灯，我肯定凑1，如果剩下3个灯，我肯定凑7（因为7比1大）。因此，我们就判断n的奇偶性，如果n是奇数，那么一个7，剩下全是1。否则，全是1
AC代码

B. Infinite Prefixes
题意：给一个长度为n的01串，记为s。t是以s为循环节的无限长度的串，问t前缀中（包括空串），符合’0’的个数 - '1’的个数等于x 的前缀有多少个？
思路：观察t的形成，发现它是通过循环节构造。为了方便统计，'0’记为1，‘1’记为-1，那么’0’ 的个数 - ‘1’ 的个数即为前缀和。

pre[i]表示 s [ 1 ] + s [ 2 ] + s [ 3 ] + . . . + s [ i ] s[1] + s[2] + s[3] + ... +s[i] s[1]+s[2]+s[3]+...+s[i] 注意：s[i] = 1(此位置代表的字符为’0’), s[i] = -1(此位置代表的字符为’1’)

pre[n]是循环节长度，我们发现，从s[i]开始后面，都可以找到一个循环节【s[i+1], s[i+2], …,s[i + n]】，其权值和为pre[n]。
那我们就知道所有前缀和（空串特判即可）的权值和为：
s u m = p r e [ i ] + p r e [ n ] ( 循 环 节 ) ∗ k , i 属 于 [ 1 , n ] , k 属 于 非 负 整 数 sum=pre[i] + pre[n](循环节) * k,i属于[1, n], k属于非负整数 sum=pre[i]+pre[n](循环节)∗k,i属于[1,n],k属于非负整数
因此，ans即为（k的取值个数 + 空串可否），具体细节可参考下面代码
AC代码

C. Obtain The String
题意：字符串s，字符串t是题目给定的，问是否可以存s中最少取出多少Subsequence，从而拼接成t。(注意：每次取完s串不变)
思路：贪心地考虑，从t串的第一个字符，从左往右枚举，枚举到当前第i个字符时，看第i - 1字符从s中选择的位置，记为loc。那么在s中，找第i个字符时，肯定找比loc大的且最接近loc的位置！（贪心策略）寻找过程upper_bound一下即可。如果找不到，则以当前字符作为新一个Subsequence的开头。
AC代码

D. Same GCDs
题意：给a,m，问使得gcd(a + x, m) = gcd(a, m)的x有多少个，变量范围参考题目
思路：记gcd(a, m) = (a, m);
g c d ( a + x ( a , m ) , m ( a , m ) ) = 1 , 0 ≤ x < m , 1 ≤ a < m gcd(\frac{a+x}{(a,m)},\frac{m}{(a, m)}) = 1,0≤x<m,1≤a<m gcd((a,m)a+x​,(a,m)m​)=1,0≤x<m,1≤a<m

a<=(a+x) <(a + m)
因为a < m
所以a+x的范围可化为[a, m] （记为A）+ (m, a+m）（记为B）
g c d ( A ( a , m ) , m ( a , m ) ) = 1 gcd(\frac{A}{(a,m)},\frac{m}{(a, m)}) = 1 gcd((a,m)A​,(a,m)m​)=1
表示区间A【 a ( a , m ) \frac{a}{(a, m)} (a,m)a​, m ( a , m ) \frac{m}{(a, m)} (a,m)m​】中与 m ( a , m ) \frac{m}{(a, m)} (a,m)m​互质的个数
g c d ( B ( a , m ) , m ( a , m ) ) = 1 gcd(\frac{B}{(a,m)},\frac{m}{(a, m)}) = 1 gcd((a,m)B​,(a,m)m​)=1
表示区间B（ m ( a , m ) \frac{m}{(a, m)} (a,m)m​, a + m ( a , m ) \frac{a + m}{(a, m)} (a,m)a+m​）中与 m ( a , m ) \frac{m}{(a, m)} (a,m)m​互质的个数
由gcd性质， gcd(a, b) = gcd(a %b, b)
所以，区间B（ m ( a , m ) \frac{m}{(a, m)} (a,m)m​, a + m ( a , m ) \frac{a + m}{(a, m)} (a,m)a+m​）中与 m ( a , m ) \frac{m}{(a, m)} (a,m)m​互质的个数 = 区间B（0, a ( a , m ) \frac{a}{(a, m)} (a,m)a​）
综合上述分析，Ans即为区间【 1， m ( a , m ) \frac{m}{(a, m)} (a,m)m​】与 m ( a , m ) \frac{m}{(a, m)} (a,m)m​互质的个数
求解，可直接利用欧拉函数求解公式，具体可参考AC代码
AC代码

E. Permutation Separation
题意：长度为n的数组 (an array where each integer from 1 to n appears exactly once），把该数组从某处切割，得到两个数组A,B。A数组里面的任意元素转移B数组，需要cost。（B数组里面的任意元素转移A数组也需要cost），问最少需要多少cost使得A数组最大元素小与B数组最小元素？（具体题目一些细节参考题目）
思路：首先乍一看，感觉是数据结构题目。数据结构题目，一般都是枚举因素，然后剩下的因素可以通过数据结构维护，然后一直更新答案。
枚举因素:左区间长度、分割线
接下来的思路是基于，先枚举左区间长度，然后数据结构维护分割线，得出的。
另外一种组合，尚且没有思考是否可行。

p 记为左区间长度 | 分割线
数组[3、5、1、6、2、4]
代价[9、1、9、9、1、9]
p = 3
（分割）3 | 5 1 6 2 4
（代价）0 0 9 0 9 0 总代价（0 + 0 + 9 +0 + 9 + 0）
（分割）3 5 | 1 6 2 4
（代价）0 1 9 0 9 0 总代价（0 + 1 + 9 +0 + 9 + 0）
（分割）3 5 1 | 6 2 4
（代价）0 1 0 0 9 0 总代价（0 + 1 + 0 +0 + 9 + 0）
观察：
分割线右边的代价不变
分割线左边的不大于p的代价改为0
（仔细思考，也是很容易证明）
因为只需要考虑总代价，所以我们要考虑对于某一个p，怎样快速求得所有分割得出的总代价最小值？
问题一：
如何保证分割线右边的代价不变
分割线左边的不大于p的代价改为0
令
base = cost[1] + cost[2] + cost[3] + … + cost[p];
(cost[i]表示数组中元素为i的移动cost)
更改
cost[i] = -cost[i]（i <= p）
这样我们总代价=base + cost[p[1]] + cost[p[2]] + … + cost[p[k]] （k是分割线位置）
如果不懂总代价式子，自己看一下上面例子，推一下即可
问题二：
p = i 转移 p = i + 1
更改
cost[i + 1] = -cost[i + 1]
查询（左区间）为[1,1],[1,2],[1,3],[1,n-1]（分割后）最小总代价（线段树维护）

综上所述，线段树维护区间和(sum)，区间前缀最小值(mi)
（例如[a1,a2,a3]，区间前缀最小值<=min(a1, a1+a2, a1+a2+a3)）

node[o].sum = node[ls].sum + node[rs].sum;
node[o].mi = min(node[ls].mi, node[ls].sum + node[rs].mi)
o 父节点 ls左儿子 rs右儿子
node[ls].sum + node[rs].mi 维护区间连续性，保证区间前缀一定是从第一个元素开始

复杂度分析

枚举左区间长度【1，n - 1】O（N）
更新base O（1）更新i O( l o g 2 N log_{2}N log2​N) 查询（n-1）种分割后总代价最小值O(1)也就是第一个节点的mi，特别注意，我这个线段树，叶子节点个数只有n-1个，不是n个
总复杂度O（N * logN）

如果没有太理解，可以看下面代码，真得很短，维护信息很简单
AC代码