第46届ICPC济南站部分题解

第46届ICPC济南站题解（部分）

补题通道在PTA的教育商店，这里会简单给出题意

C：Optimal Strategy

题意：有两个人正在玩游戏，他们每次可以从给定数组中取出一个数字，其值作为自己的得分，轮流取数。每个人都想自己的得分更高，问让自己得分更高的情况下，有几种取数方法

思路：组合计数

建议先自己模拟下过程，才好理解以下我说的话。

一步一步来，

当我先手时，如果最大值的个数有奇数个，那么我一定会去选最大的那个。

相对的，如果最大值的个数有偶数个，那么我可以先放着最大的不选。但是假如有一方先选了最大值，那么另外一个必须得先选最大值了。

所以初步得到，方案数和最大值的奇偶性有关。

当为偶数时候，可以先放着，等对面选了自己跟着选，或者反之。

当为奇数的时候，先手先选，然后又变成了偶数的情况。

所以我们可以先找出得分数字的组合（相同的数字没有位置的差别），最后乘以所有相同的数字的全排列即可。

所以现在需要解决子问题，找出得分数字的组合方案数即可。

从小到大取数字，当当前数字个数为奇数的时候，必须得排第一个，剩下的两个一组进行插入即可

最终的柿子也就是

\[\sum_{i = 1}^n cnt[i]! * C_{\sum_{j = 1}^{i - 1} + \lfloor \frac{cnt[i]}{2} \rfloor}^{\lfloor \frac{cnt[i]}{2} \rfloor} \]

解释下这个柿子的组合数部分吧

其实就是一个经典问题，把 \(n\) 个相同红色球插入到 \(m\) 个蓝色球中的方案数

答案就是 \(C_{m + n}^{n}\) 因为插入之后一共有 \(n + m\) 个，其中 \(n\) 个是红球，相当于从中取出 \(n\) 个位置放红球，剩下的按照原来位置排序即可

#include 
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
const int INF = 0x3f3f3f3f, N = 1e6 + 10;
const int MOD = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

LL f[N];

LL q_pow(LL a, LL b, LL p) {
    LL res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
    }
    return res;
}

LL get_inv(LL x) {return q_pow(x, MOD - 2, MOD);}

LL C(int n, int m) {
    return f[n] * get_inv(f[n - m]) % MOD * get_inv(f[m]) % MOD;
}

inline void solve() {
    int n; cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] * i % MOD;
    vector a(n + 1), cnt(n + 1);
    LL res = 1;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], cnt[a[i]] ++;
    for (int i = 1; i <= n; i ++ ) {
        if (!cnt[i]) continue;
        res = res * f[cnt[i]] % MOD;
    }
    int num = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (!cnt[i]) continue;
        int now = cnt[i] / 2;
        res = res * C(num + now, now) % MOD;
        num += cnt[i];
    }
    cout << res << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

D: Arithmetic Sequence

题意：给一个数组，对于每个数字来说，都有将该值+1或者-1操作，问将该数组变成等差数列的最小次数操作是多少。

思路：三分

容易想到，对于公差 \(d\) 来说，若 \(f(d)\) 表示公差为 \(d\) 值时候的最少操作次数，那么 \(f(d)\) 是含有一个极小值的函数，这个极小值就是我们要求的答案，所以想到三分 \(d\) 然后计算即可。

接下来讲 \(f(d)\) 的求解

我们定义一个数组 \(d[i]\) 表示首相为0，公差为 \(x\) 的时候的操作次数。

那么显然，取 \(d\) 的中位数作为最终数列的参照就是正解。（和货仓选址差不多原理）

那么接下来也没啥难度了，不过注意此题如果直接三分会爆long long，所以要上int128，或者在 \(n\) 较大的时候减少三分范围。

#include 
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

LL a[N], d[N], c[N];
int n;

LL check(LL x) {
    for (int i = 1; i <= n; i ++ ) c[i] = x * i - (a[i] - a[1]);
    nth_element(c + 1, c + (n + 1) / 2, c + 1 + n);
    LL mid = c[(n + 1) / 2];
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(mid - c[i]);
    return res;
}

inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    LL l = (LL)-1e13, r = (LL)1e13;
    while (l < r) {
        LL mid1 = l + (r - l) / 3;
        LL mid2 = r - (r - l) / 3;
        if (check(mid1) <= check(mid2)) r = mid2 - 1;
        else l = mid1 + 1;
    }
    cout << check(l) << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

J:Determinant

题意：给定一个行列式，再给一个行列式的值的绝对值，问你行列式的值应该是绝对值本身，还是绝对值的负数。

想法：高斯消元取模

其实很简单，但是如果直接用python计算就会T，因为数字巨大。

所以用高斯消元加个取模即可。

#include 
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
const int INF = 0x3f3f3f3f, N = 120;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

LL q_pow(LL a, LL b, LL p) {
    LL res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
    }
    return res;
}

LL p[N][N];
int n;

LL inv(LL x) {return q_pow(x, MOD - 2, MOD);}

LL Gauss() {
    LL res = 1;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = i; j <= n; j ++ ) {
            if (p[j][i] != 0) {
                if (j == i) break;
                res = -res;
                for (int k = i; k <= n; k ++ ) swap(p[j][k], p[i][k]);
                break;
            }
        }
        if (p[i][i] == 0) return 0;
        LL now = inv(p[i][i]);
        for (int j = i + 1; j <= n; j ++ ) {
            LL tmp = p[j][i] * now % MOD;
            for (int k = i; k <= n; k ++ ) p[j][k] = (p[j][k] - p[i][k] * tmp % MOD + MOD) % MOD;
        }
        res = (res * p[i][i] % MOD + MOD) % MOD;
    }
    return res;
}

inline void solve() {
    cin >> n;
    LL now = 0;
    string s; cin >> s;
    for (auto ite : s) now = (now * 10 % MOD + ite - '0') % MOD;
    for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) cin >> p[i][j];
    if (Gauss() == now) cout << "+\n";
    else cout << "-\n";
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}