A.Parallelepiped
题意：给一个六面体三面的面积，求12条边的长度和。
题解：因为都是整数，设边长分别为a,b,c，面积为xyz,那么可设x=a*b,y=b*c,z=c*a，简单解方程就可以了。
#include <iostream>
#include <math.h>
using namespace std; int main()
{
int a, b, c;
int x, y, z;
while (cin >> x >> y >> z) {
a = sqrt(x * z / y);
b = x / a;
c = z / a;
cout << * (a + b + c) << endl;
}
return ;
}
B.Array
题意：给一个长度为N的数列，求一个连续子序列，包含K个不同的数。要求这个子序列不能有满足条件的子序列，但不要求长度是最小。
题解：从头开始，每得到一个数就放入set，并记录每一个数字出现的最后的位置。当set的大小等于k时，就是子序列结束的位置，因为要开始位置尽可能靠后（否则就存在求得序列的子序列也满足条件），其次每个数字至少出现一次，那么求last最小值即可。
#include <stdio.h>
#include <math.h>
#include <set>
#include <string.h>
using namespace std; int a[];
int last[]; int main()
{
int n, k;
while (~scanf("%d%d",&n, &k)) {
for (int i = ; i < n; ++i) scanf("%d", a + i);
memset(last, -, sizeof last);
set<int>s;
int l = n;
int r = -;
for (int i = ; i < n; ++i) {
s.insert(a[i]);
last[ a[i] ] = i;
if (s.size() == k) {
r = i;
break;
}
}
if (r == -) {
printf("-1 -1\n");
continue;
}
for (int i = ; i <= r; ++i) {
if (last[ a[i] ] != - && last[ a[i] ] < l) l = last[ a[i] ];
}
printf("%d %d\n", l + , r + );
}
return ;
}
C.Bracket Sequence
题意：给一个只含有()[]的字符串，求一个括号匹配且没有相互嵌套的连续子序列，要求'['的个数最多。
题解：dp。对于每一个字符，都希望向前找到最长的子串，那么最长子串含有'['一定也是最多的。设一个数组f[n]，f[i]表示以字符i为最后一个字符的子序列能向前匹配到不能匹配的位置。f[i]=-1表示能匹配到第一个字符。f[i]=i表示子序列长度为0。当a[i]=a[f[i-1]]，f[i]=f[ f[i-1]-1 ] 。ans[i]表示包含第i个字符的最长子序列含有多少个'['。
#include <stdio.h>
#include <string.h>
#include <stack>
#include <utility>
using namespace std;
char a[];
int f[];
int ans[]; int main()
{
while (~scanf("%s", a)) {
int len = strlen(a);
f[] = ans[] = ;
for (int i = ; i < len; ++i) {
if (f[i-] == -) {
f[i] = i;
ans[i] = ;
} else if (a[ f[i-] ] == '(' && a[i] == ')') {
f[i] = f[i - ] - ; ans[i] = ans[i - ];
if (f[i] != -) {
ans[i] += ans[ f[i] ];
f[i] = f[ f[i] ];
}
} else if (a[ f[i-] ] == '[' && a[i] == ']') {
f[i] = f[i - ] - ; ans[i] = ans[i - ] + ;
if (f[i] != -) {
ans[i] += ans[ f[i] ];
f[i] = f[ f[i] ];
}
} else {
f[i] = i;
ans[i] = ;
}
}
int maxn = ;
int pos = ;
for (int i = ; i < len; ++i) {
if (maxn < ans[i]) {
maxn = ans[i];
pos = i;
}
}
printf("%d\n", maxn);
for (int i = f[pos] + ; i <= pos; ++i) printf("%c", a[i]);
printf("\n");
}
return ;
}
D.Two Strings
题意：给2个字符串S和T，求S中所有和T相等的子串（不要求连续），能不能使用S中所有的字符至少一次。
题解：从前向后扫一遍求每个字符能匹配到最靠右的位置l，从后向前扫一遍求每个字符能匹配到最靠左的位置r，如果前面的能l>=r，证明该字符可以被用到。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std; const int N = ; char s[N], t[N];
int l[N], r[N];
int ok[];
int main()
{
while (scanf("%s%s", s, t) == ){
memset(ok, -, sizeof (ok));
int slen = strlen(s);
int tlen = strlen(t);
int pos = ;
bool flag = true;
for (int i = ; i < slen; ++i) {
if (pos < tlen && s[i] == t[pos]) {
ok[ s[i] ] = pos;
l[i] = pos++;
} else {
if (ok[ s[i] ] == -) {
flag = false;
}
l[i] = ok[ s[i] ];
}
}
if (!flag) {
puts("No");
continue;
}
memset(ok, -, sizeof (ok));
pos = tlen - ;
for (int i = slen - ; i >= ; --i) {
if (pos>= && s[i] == t[pos]) {
ok[ s[i] ] = pos;
r[i] = pos--;
} else {
if (ok[ s[i] ] == -) {
flag = false;
}
r[i] = ok[ s[i] ];
}
}
if (!flag) {
puts("No");
continue;
}
for (int i = ; i < slen; ++i) {
if (l[i] < r[i]) {
flag = false;
break;
}
}
if (!flag) puts("No");else puts("Yes");
}
return ;
}
E.Partial Sums
给一个长度为N的数组，做n次操作后求该数组。公式如下。
很容易想到通过矩阵快速幂解题，设转移矩阵F，通过A*(F^K)求的结果。然而(1 ≤ n ≤ 2000, 0 ≤ k ≤ 109)，复杂度为n^3*logk，妥妥的超时了。
这个题的矩阵是特殊的矩阵，上三角矩阵（当然也可以是下三角），而且每个值都是1。
对于如下图的矩阵——上三角矩阵，且为带状矩阵。每个对角线值都相等。
对于这个类型的矩阵，只要知道了第一行的元素就可以推出整个矩阵的样子。那么存该矩阵的时候也可以只存一行。
两个这样的矩阵相乘，还为这样的矩阵。
于是可以考虑把矩阵压缩成一维，那么矩阵乘法的复杂度也从n^3降到n^2。
设A*B=C
可以推出
c[0][i]
=sigma(j=0..n-1)a[0][j]*b[j][i]
=sigma(j=0..i) a[0][j]*b[j][i]（因为是上三角矩阵，下面的元素都为0）
=sigma(j=0..i) a[0][j]*b[0][i-j]（因为是带状矩阵，b[j][i]==b[0][i-j]，可以对照上面的图算一下）
对于此题，转移矩阵压缩为一维后，求得F^k。
然后对于A*F，可以通过F的性质求的F[i][j]，即F[i][j]=F[0][j-i]。
（一份糟糕的代码）
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat; const int M = ;
int n, k;
// A*B
mat mul(mat &A, mat &B)
{
mat C(, vec(n));
for (int i = ; i < n; ++i) {
for (int k = ; k <= i; ++k) {
C[][i] = (C[][i] + A[][k] * B[][i - k]) % M;
}
}
return C;
} // A^k
mat pow(mat A, int k)
{
mat B(, vec(n));
B[][] = ;
while (k > ) {
if (k & ) B = mul(B, A);
A = mul(A, A);
k >>= ;
}
return B;
} void solve()
{
mat f(, vec(n));
for (int i = ; i < n; ++i) {
f[][i] = ;
}
f = pow(f, k);
mat A(, vec(n));
for (int i = ; i < n; ++i) cin >> A[][i];
cout << A[][];
for (int i = ; i < n; ++i) {
ll tmp = ;
for (int j = ; j <= i; ++j) {
tmp = (tmp + A[][j] * f[][i - j]) % M;
}
cout << " " << tmp;
}
} int main()
{
scanf("%d%d", &n, &k);
solve();
return ;
}