题解：P12006 【MX-X10-T2】[LSOT-4] 网易云

_jxy · 2025-03-30 20:52:04 · 题解

简单题。

我们发现只要知道第一首歌的好听值就可以通过 S 把所有歌的好听值求出来。

所以我们考虑随机 500 个第一首歌的好听值，每次计算一遍答案，看看是否相等就好了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
ll a[N];
ll b[N];
pair<ll, ll> q[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    random_device rd;
    mt19937 sj(rd());
    for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%lld%lld", &q[i].first, &q[i].second);
    set<ll> se;
    for (int c = 1; c <= 500; c++) {
        b[1] = sj();
        for (int i = 2; i <= n; i++) b[i] = a[i] - b[i - 1];
        ll ans = 0;
        for (int i = 1; i <= m; i++) ans += b[q[i].first] * q[i].second;
        se.insert(ans);
    }
    if ((int)se.size() == 1) {
        printf("%lld\n", *se.begin());
    } else {
        printf("Impossible\n");
    }
    return 0;
}