2021牛客多校第五场题解

J题

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

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

ac代码：

#include 
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 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 minv(m + 1, 1e18);
            std::vector 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 > 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^i^x*C^i^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 
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了，这个写法不错。