[数据结构与算法]2021牛客多校第五场题解

J题

题目大意：有n个珠宝，每个坐标为(xi , yi , zi),且过t时间珠宝下沉至（xi , yi , zi + t * vi) , vi为每个珠宝下沉速度。每个时间只能打捞一个珠宝，代价为d2，d为（0，0，0）到该珠宝的距离。求打捞全部珠宝的最小代价。

思路：我们发现这是一个完全偶图求最佳匹配的问题。那么直接上KM板子！下面是大佬n3的板子，现在它就是我的了）

ac代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

long long n,x[N],y[N],z[N],v[N];

long long w[N][N];

namespace KM {
    long long cal(int n, int m) {
        std::vector<long long> u(n + 1), v(m + 1), p(m + 1), way(m + 1);
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            long long j0 = 0;
            std::vector<long long> minv(m + 1, 1e18);
            std::vector<char> used(m + 1, false);
            do {
                used[j0] = true;
                long long i0 = p[j0], delta = 1e18, j1;
                for (int j = 1; j <= m; ++j) {
                    if (!used[j]) {
                        long long cur = w[i0][j] - u[i0] - v[j];
                        if (cur < minv[j]) {
                            minv[j] = cur, way[j] = j0;
                        }
                        if (minv[j] < delta) {
                            delta = minv[j], j1 = j;
                        }
                    }
                }
                for (int j = 0; j <= m; ++j) {
                    if (used[j]) {
                        u[p[j]] += delta, v[j] -= delta;
                    }
                    else {
                        minv[j] -= delta;
                    }
                }
                j0 = j1;
            } while (p[j0] != 0);
            do {
                long long j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0);
        }
        long long res = 0;
        for (int i = 1; i <= m; i++) {
            res += w[p[i]][i];
        }
        return res;
    }
}

long long get_cost(int id,int t){
	return x[id] * x[id] + y[id] * y[id] + (long long)(z[id] + v[id] * t)*(z[id] + v[id] * t);
}

int main(){
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> x[i] >> y[i] >> z[i] >> v[i];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n ;j ++)
			w[i][j] = get_cost(i,j - 1);
	cout << KM::cal(n,n) << endl;
	return 0;
} 

p.s. 注意板子里的w二维数组代价矩阵i和j都是从1开始的。

D题

题目大意：有两个字符串，求两个串的全部子序列中长度相等且a < b的数量 len < 5e3

思路：将字符串拆分成三个部分：前面k个字符a与b相同，第k+1个a<b，后面的
\sum_{i=0} ^ {min(x,y} Cⁱ_x*Cⁱ_y。其中x和y表示两个串从k到结尾还有多少个字符。
前面的用动态规划：f(i , j)表示A串的前i个和B串的前j个里面有多少对长度大小都相等的串。转移方程为：如果A[ i ] == B[ j ]，f[ i ][ j ] = f[ i - 1 ][ j ] + f[ i ][ j - 1 ] - f[ i - 1 ][ j - 1 ] + f[ i - 1 ][ j - 1 ] + 1,否则f[ i ][ j ] = f[ i - 1 ][ j ] + f[ i ][ j - 1 ]-f[ i - 1 ][ j - 1 ]
后面的式子可以转化成C^x_x+y，用乘法逆元预处理

ac代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 10050;

typedef long long LL;

int fact[N],infact[N];
const int mod = 1e9+7;
LL ksm(LL a,LL b){
    LL res = 1;
    while(b){
        if(b&1)res = (LL)res*a%mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

LL ksc(LL a, LL b) {
	return ((a * b - (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}

char a[N],b[N];

LL f[5050][5050];

LL C(int a,int b){
//	cout << (((fact[a] * infact[b]) % mod) * infact[a - b]) % mod<< " aaaa"<< endl;
	return ksc(ksc(fact[a] , infact[b]) , infact[a - b]);
}

int main(){
	fact[0] = infact[0] = (LL)1;
    for(int i = 1;i < N;i++){
        fact[i] = (LL)fact[i - 1]*i%mod;
        infact[i] = (LL)infact[i - 1]*ksm(i,mod - 2)%mod;
    }
    cin >> a + 1 >> b + 1;
    LL res = 0 ;
    int len1 = strlen(a+1),len2 = strlen(b+1);
    for(int i = 1;i <= len1;i++)	
    	for(int j = 1;j <= len2;j++)
    		if(a[i] != b[j])f[i][j] = ((f[i][j - 1] + f[i - 1][j])%mod - f[i - 1][j - 1] + mod)%mod;
    		else f[i][j] = (f[i][j - 1] + f[i - 1][j] + (LL)1)%mod;			
	for(int i = 1;i <= len1;i++)
		for(int j = 1;j <= len2;j++)
			if(a[i] < b[j]) 
				res = (res + (LL)(f[i - 1][j - 1] + 1)*C(len1 - i + len2 - j,len1 - i)%mod)%mod;
	cout << res << endl;
	return 0;
}

p.s. 快速乘之前的板子tle了，这个写法不错。