逆序对:
题意：求1-n的所有排列中，逆序对数为k的有多少个。
分析：令f[i][j]为1~i的所有排列中逆序对数为j的方案有多少个。我们想象每次把i插入原来的排列中，由于i是当前最大的数，所以它插入的位置就决定了增加的逆序对数。所以f[i][j] = f[j] + f[j-1] + f[j-2]... + f[j-i+1],用上前缀和优化令s[i][j] = f[i][j] + f[i][j-1] + f[i][j-2]...+ f[i][0]则f[i][j] = s[j] - s[j-i], s[i][j] = s[i][j-1] + f[i][j],在O(n*k)的时间内解决了这一问题。
硬币:
有合并与划分两种操作，需要将A序列转换为B序列。
我们可以等价于对A序列和B序列都只进行合并操作，问AB最少操作次数和，使得它们变成相同的序列。
由于数据范围很小，我们可以使用双向广搜。
广搜的初始结点是初始序列和目标序列，每次进行合并操作拓展出一层，如果拓展到相同的结点，则找到了最优解。对于结点的记录，可以对序列进行hash，而C++选手可以直接使用map来处理。
另外，这道题还有DP解法，有兴趣的同学可以进行探究。
二次方程
题意：二次方程x^2+2*b*x+c=0在1
4 条评论
-
Jeff2000323 LV 4 @ 2015-10-21 19:01:23
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn = 1005;
int main() {
string passwd, A;
cin >> passwd >> A;
int L1 = passwd.size(), L2 = A.size();
int res[maxn];
for (int i = 0; i < L2; i++) {
int p1 = passwd[i % L1], p2 = A[i];
if (p1 >= 'A' && p1 <= 'Z') p1 -= 'A' - 'a';
if (p2 >= 'A' && p2 <= 'Z') p2 -= 'A' - 'a';
res[i] = p2 - p1;
while (res[i] < 0) res[i] += 26;
if (A[i] >= 'a' && A[i] <= 'z')
res[i] += 'a';
else
res[i] += 'A';
}
for (int i = 0; i < L2; i++) {
putchar(char(res[i]));
}
putchar('\n');
return 0;
} -
@ 2012-11-05 10:37:48
题解还是有点看不懂。。。。
第二题说的有点简短了....
我就不说第一题是导刊原题了 太水了。。 -
@ 2012-11-02 17:54:37
第二题能不能解释得再详细些
谢谢。
-
@ 2012-11-02 17:50:56
pal3
RT
- 1
