EDU 153
A-Not a Substring
题意：给出一个长为 \(n\) 的序列，只含有左右括号，要求给出一个长为 \(2n\) 的合法括号序列，满足原序列不是该括号序列的子串。
判断是否有解，若有解，给出一个合法括号序列。
显然，我们先判掉原序列为 "()" 的情况，一个合法括号序列必然要出现该图形。
其次，容易发现，对于存在 "((" 或者 "))" 连续段的，则 "()()()……" 此类必然是一个解。
如果不存在，则显然 ((((())))) 此类是一个解。
B-Fancy Coins
题意：你有 \(a_1\) 个面值为1的普通硬币，\(a_k\) 个面值为 \(k\) 的普通硬币，以及无限个面值为1和 \(k\) 的印花硬币。
现在需要买一个价值为 \(s\) 的物品，求最少的印花硬币使用量。
首先，我们需要将 \(s\) 用一元硬币化为 \(s'\) 使得 \(k|s'\)。这一步的代价是 \(\max(0,(s\bmod k)-a_1)\)。记录剩下的一元普通硬币个数 \(a'_1\)
然后，我们将 \(a_k\leftarrow a_k+\lfloor\frac{a'_1}{k}\rfloor\)。只需判断还需要几个印花硬币就可以凑出即可。
int n,k,a1,ak;
cin>>n>>k>>a1>>ak;
int ans=0;
if(a1>=n%k)a1-=n%k,n-=n%k;
else ans+=n%k-a1,a1=0,n-=n%k;
int s=n/k;
if(s<=ak+a1/k)cout<<ans<<"\n";
else{
int t=a1/k;ak+=t;
ans+=s-ak;
cout<<ans<<"\n";
}
C-Game on Permutation
题意：有两个人轮流操作。最初有一个序列 \(a\)，是一个 \(n\) 的排列。
有一个筹码，最初由先手任意放在一个位置上，接着后/先手交替移动，每一次可以将筹码从 \(i\) 移动到 \(j\)，满足 \(j<i,a_j<i\)
当一个棋子不可以移动时，当前轮到的人获胜。
D-Balanced String
题意：给定一个01序列 \(a\)，记录 \(c_1=\sum_{i<j}[a_i=1][a_j=0],c_0=\sum_{i<j}[a_i=0][a_j=1]\)。
每一次可以交换任意两个数，求使得 \(c'_0=c'_1\) 的最小操作次数。
\(1\le |a|\le 100\)
E-Fast Travel Text Editor
题意：给定一个长为 \(n\) 的字符序列 \(a\)，有一个光标，它只会停留在两个字符之间，或者最后一个字符后，或者第一个字符前。
光标移动的规则如下：
每一次移动，从下列三种方案中选择一个：
- 从 \((x,x+1)\) 移动到 \((x-1,x)\)，前提是 \(x\neq 0\)
- 从 \((x,x+1)\) 移动到 \((x+1,x+2)\)，前提是 \(x+1\neq n\)
- 从 \((x,x+1)\) 移动到 \((k,k+1)\)，满足 \(a_x=a_k,a_{x+1}=a_{k+1}\)
现给出若干询问，每次给出 \(x,y\)，求光标从 \((x,x+1)\) 移动到 \((y,y+1)\) 的最小代价。
\(1\le m\le 5\times 10^4\)