Codeforces Round 954 (Div. 3)
题目列表：
- A. X Axis
- B. Matrix Stabilization
- C. Update Queries
- D. Mathematical Problem
- E. Beautiful Array
- F. Non-academic Problem
- G1. Permutation Problem (Simple Version)
- G2. Permutation Problem (Hard Version)
A. X Axis
题目大意：
t组测试样例，每组样例给出三个整数，分别表示数轴上三个点的坐标，选取数轴上任意一个点，使得这个点到给定的三个点的距离和最小，求出这个最小距离和。
分析：
纯水题，显然答案就是给定的这三个点中最大的坐标减去最小的坐标。
B.Matrix Stabilization题目大意：
C. Update Queries题目大意：
给你两个字符串S、C，长度分别为n和m，以及一个大小为m的数组$ind[]$表示索引，有m次操作，从1到m依次进行，第i次操作需要把 $ S_{ind[i]} $变为$C_i$。并且你可以把字符串$C$以任意顺序排列，比如对于$C=abc$，你可以将它变为$acb,bca,bac,cab,cba$。求出m次操作之后所能得到的字典序下最小的$S$。 D.Mathematical Problem分析:
\(n\le20\) 这是 \(O(n^2)\) ？NO!
非 DP 整体复杂度 \(O(n)\) 可做！可以当成并不困难的规律题做。
思路分析：
首先我们要想到一些特殊情况（原因在代码注释中解释）：
- \(n=2\) 时直接输出原数；
- \(n=3\) 时，若第一位或第三位数为 0，则答案为 0；
- \(n>3\) 时，有 0 则答案为 0。
此题有一个显而易见的性质：对于已知的一组数，除了 0 和 1 之外的数直接加和答案最小。
证明：显然。其他题解中对于这一条已有很好的解释，这里不再多做叙述了，也可以自己手膜一下容易发现。
在想到这条性质后，那么我们需要做的就是分出一个二位数使答案最优，以下我们称要找的这个二位数为最优二位数。
按照容易想到的 \(O(n^2)\) 做法，就是遍历出所有二位数，对每一个二位数，都求一遍 1 以为的数的加和，答案即为所有和的最小值。
那么我们能不能直接 \(O(n)\) 找出最优二位数呢，再仔细分析一下，又发现以下性质：
（若两个二位数 \(a,b\)，有 \(a\) 优于 \(b\)，则我们写成 \(a>b\)）于是有如下“优排列”（注意 11，21 等个位数为 1 的数的位置）
$ 12=13=14=15=16=17=18=19>11=22=...=29>21>...$
以此类推。（不含个位数为 0 的， 因为特殊情况中 0 已经考虑）即十位数相同的所有二位数，个位数不为 1 的数要优于个位数为 1 的。
为什么呢？我们假定将原数列除 1 之外的总和为 \(sum\)，找出最优二位数之后除 1 之外的总和为 \(you\)，最优二位数为 12 时，则 \(you\) 相比于 \(sum\) 增加了 \(12-2=10\)，（\(sum\) 中只加了 2 ，而 \(you\) 中加了 12，对于所有十位数为 1 的二位数，\(you-sum\) 的值都为 10，而对于 11 ，\(you-sum=11-0=11\) (因为 1 在 \(sum\) 都不进行计算)。\(11>10\)，所以十位数相同时，个位数不为 1 的要优于个位数为 1 的。那么十位数为 2、个位数不为 1 时，\(you-sum=18\)，对于 21，\(you-sum=20\)，同理，便得出了上述“优排列”。
这样我们就可以 \(O(n)\) 找出最优二位数了，之后直接计算即可。
处理的时候我们可以分别找出最小的各位为 1 的二位数和各位不为 1 的二位数，比较它们十位数即可。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int t, n, a[N];
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
scanf("%d", &t);
while(t--)
{
scanf("%d", &n); bool if_end = false;
for(int i=1; i<=n; i++){
scanf("%1d", &a[i]);
}
if(n == 2){ //n-2=0，即不需要添加运算符，直接输出
int ans = 0;
ans = a[1] * 10 + a[2];
printf("%d\n", ans);
continue;
}
if(n == 3){
if(a[1] == 0 or a[3] == 0){//特判0
puts("0");
continue;
}
if(a[2] == 0){//n=3，只能有一个运算符，第二位数为0答案不为0
if(a[1] == 1) printf("%d\n", a[3]);
else if(a[3] == 1) printf("%d\n", a[1]);
else printf("%d\n", a[1]+a[3]);
continue;
}
}
int sm = 2008, id = 0;//记个位数不为1的最小二位数及位置
int _1 = 2008, id_1 = 0;//个位数为1的最小二位数及位置
for(int i=1; i<=n; i++){
if(n > 3 and a[i] == 0){ //有0，全部相乘便为0
puts("0"); if_end = true; break;
}
int now = a[i-1] * 10 + a[i];
if(i > 1 and a[i] == 1){
if(_1 > now) _1 = now, id_1 = i;
}
if(i > 1 and a[i] != 1){
if(sm > now) id = i, sm = now;
}
}
if(if_end) continue;
int y = sm - sm % 10;//y为个位数不为1的最小二位数的十位数
if(_1 < y and _1) sm = _1, id = id_1;//此时最优二位数为最小的个位数为1的二位数
int ans = sm;
for(int i=1; i<=n; i++){ //1之外的加和
if(i == id or i == id - 1 or a[i] == 1) continue;
ans += a[i];
}
printf("%d\n", ans);
}
return 0;
}