程序员进阶之算法练习（二十）

前言

这四个题属于中等，有的需要一定的代码量，有的需要奇妙的思考。

正文

1. Sonya and Queries 题目链接 ** 题目大意：** 给出一个集合T，n个操作； 每个操作有3种情况： 1、往集合T里面添加一个数字x； 2、往集合T里面删除一个数字x； 3、询问集合T里面，里面与s能匹配的数量。 匹配的方式：对于两个数字x、y，如果两个数字每一位的奇偶性都相同，则认为匹配（不足的位数补0）。 357和135： 357 135 匹配；

13和257： 013 257 匹配；

13和247： 013 247 不匹配；

Exmample input 4 + 200 + 200 - 200 ? 0 output 1

n<=10w, x的范围10^18，添加的数字可以相同，删除时如果有多个数字x只删除一个；

题目解析： 从匹配方式入手。 奇偶性相同，意思就是对于每一个数字，可以转换成01010111的字符串。 那么数字x是否和数字y匹配，就相当于他们的010101字符串是否相同，那么我们可以定义一个trans操作。 数字x和数字y匹配，当且仅当trans(x) = trans(y)。

再来看操作1和操作2，对于询问来说245、45和5是等价的（001，01，1）。 那么操作1可以简化成加入一个trans(x)的数字，操作2简化成删除一个trans(x)的数字。 题目可解。

2. Sonya and Problem Wihtout a Legend 题目链接 题目大意： 给出n个数字，每次可以把一个数字+1或者-1，代价为1； 问把n个数字改为严格递增序列的最小代价。 n (1 ≤ n ≤ 3000) ai (1 ≤ ai ≤ 1e9).

Example ** input** 5 5 4 3 2 1 ** output** 12 样例解释： 1 2 3 4 5 |5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12

题目解析： 如果是非严格递增（即是a[i]=a[i+1]是可行的），可以用dp来解决。 令b[i]=第i大的数字， dp[i][j] 表示第前i个数字转移到第j大的数字的代价； 那么有dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(a[i] - b[i])); 1<= k <= j； 在求dp[i][j] 的过程中，维护一个dp[i-1][1~j]的最小值即可。 代码非常简短，如下：

    int n;
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = b[i] = a[i] - i;
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        lld maxInf = llinf;
        for (int j = 1; j <= n; ++j) {
            maxInf = min(maxInf, dp[i - 1][j]);
            dp[i][j] = maxInf + abs(a[i] - b[j]);
        }
    }
    lld ans = llinf;
    for (int i = 1; i <= n; ++i) {
        ans = min(dp[n][i], ans);
    }
    cout << ans << endl;

3. Plus and Square Root 题目链接 ** 题目大意：** 有一个特殊的计算器，只能执行加号和求平方根的操作，计算器有一个等级，用数字k表示；初始值为x。 执行完加号操作后，x=x+k; 执行完求根操作后，x=sqrt(x);（这个操作只有当x是perfect square的时候才能执行，且要求执行完的x必须是等级的倍数） 执行完求根操作后，等级会上升，k=k+1;（注意，执行完求根操作后，等级+1后再进行倍数的判断） 初始等级是1，初始值是2，问要到达等级n+1，在每次求根操作前需要执行几次加号操作？ 如果有多个解，输出任意解都可以。

** Examples** ** input** 3 ** output** 14 16 46 样例解释：表示在等级1、2、3的时候分别按14、16、46次加号；

** 题目解析：** 思路是从根号入手，题目要求x进行sqrt操作后的数字是等级的倍数，列出等级和初始值

 LEVEL  Init
 1      2, 2+1, 2+1+1
 2      2, 2+2, 2+2+2, ..., 2*(3*3*2)
 3      3*2, 3*2+3, 3*2+3+3, ..., 3*(4*4*3)
 ...
 i      i*j, i*j+i, i*j+i+i, ..., i*((k+1)*(k+1)*i)

sqrt( i*((k+1)*(k+1)*i)) = i * (k+1) 这样就找到一种构造方式，满足题意。

4. Complete The Graph 题目链接 题目大意： 给出n个点，m条边，边的长度为0到10^9；长度为0的边表示可修改边。 可修改边都需要赋值，边长必须是正整数。 要求赋值完成后，点s到点t的最短路刚好为L。 s n, m, L, s, t (2 ≤ n ≤ 1000,  1 ≤ m ≤ 10 000,  1 ≤ L ≤ 1e9,  0 ≤ s, t ≤ n - 1,  s ≠ t)

Examples input 5 5 13 0 4 0 1 5 2 1 2 3 2 3 1 4 0 4 3 4 output YES 0 1 5 2 1 2 3 2 3 1 4 8 4 3 4 样例解释：把边1-4的长度赋值为8。

** 题目解析：** 先不考虑可修改边。 求出s到t的最短路。 枚举每一条可修改边，先按照长度为1的大小加入；如果加入后的最短路小于L，则找到解，剩下的所有可修改边重置为inf。 在最短路中的找到刚刚添加的最后一条可修改边，把变成重置为L-dis+1，得到一个解。

总结

脑海中还积累着一部分知识，仍需一点时间理清思路。

灰蒙蒙的天气，犹如心情一样低沉。 昔日的球友在上海中医药大学打野球，本来阳光明媚的球场照片里应该也有我的身影。