前言
这四个题属于中等，有的需要一定的代码量，有的需要奇妙的思考。
正文
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，得到一个解。
总结
脑海中还积累着一部分知识，仍需一点时间理清思路。
灰蒙蒙的天气，犹如心情一样低沉。
昔日的球友在上海中医药大学打野球，本来阳光明媚的球场照片里应该也有我的身影。
