跳转至

251007 模拟赛

T2 magic

有 \(n\) 个水晶球，初始所有水晶球初始时都是点亮的。每个水晶球都有三个属性 \(l_i,r_i,c_i\)，每次你可以熄灭一个水晶球，如果熄灭第 \(i\) 个水晶球，那么区间 \([l_i,r_i]\) 内每个点亮的水晶球都会产生 \(c_i\) 的价值（不算 \(i\)）。请你安排熄灭所有水晶球的顺序，使得总价值最大。

\(n\le 1000,~i-7\le l_i\le i\le r_i\le i+7\)

感觉数据范围很像状压。发现记录最后 \(7\) 位哪些水晶球已经熄灭没什么前途，因为本质上我们没有记录 \(i\) 后面的元素熄灭之后 \(i\) 前面的元素以什么顺序熄灭。因此考虑状压排列，然后转移改为向排列中插入一个元素。发现这样的贡献是容易计算的，只需在删除第 \(i-7\) 个元素时算一下它向后面的贡献和后面向它的贡献。容易做到 \(O(1)\) 转移，时间复杂度 \(O(n\times 7!\times 8)=O(n\times 8!)\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N = 1010;

inline void gmax(int &a, int b) { a = max(a, b); }

int n;
int l[N], r[N], c[N];

vector<int> sta[5050]; int nn;

void dfs(int x) {
    static int vis[8];
    static int a[8];
    if(x == 8) {
        ++nn;
        for(int i = 1; i <= 7; i++) sta[nn][i] = a[i];
        return;
    }
    for(int i = 1; i <= 7; i++) {
        if(vis[i]) continue;
        vis[i] = 1;
        a[x] = i;
        dfs(x + 1);
        vis[i] = 0;
    }
}

int trans[5050][9];
int f[N][5050];

void init() {
    vector<int> a(8);
    for(int t = 1; t <= nn; t++) {
        for(int c = 1; c <= 8; c++) {
            for(int i = 1; i <= 6; i++) a[i] = sta[t][i + 1];
            a[7] = c;
            for(int i = 1; i <= 7; i++) if(a[i] > sta[t][1]) --a[i];
            for(int i = 1; i <= 6; i++) if(a[i] >= a[7]) ++a[i];
            trans[t][c] = lower_bound(sta + 1, sta + 1 + nn, a) - sta;
        }
    }
}

inline int calc(int p, int t) {
    int res = 0;
    p -= 7;
    for(int i = 2; i <= 7; i++) res += sta[t][i] > sta[t][1] ? (p + i - 1 <= r[p] ? c[p] : 0) : (l[p + i - 1] <= p ? c[p + i - 1] : 0);
    return res;
}

inline int calc1(int p, int t, int v) {
    return v > sta[t][1] ? (p <= r[p - 7] ? c[p - 7] : 0) : (l[p] <= p - 7 ? c[p] : 0);
}

inline int calc_ans(int t) {
    int res = 0, p = n - 7;
    int a[8];
    for(int i = 1; i <= 7; i++) a[i] = sta[t][i];
    for(int i = 1; i <= 7; i++) {
        for(int j = i + 1; j <= 7; j++) {
            res += a[i] < a[j] ? (p + j <= r[p + i] ? c[p + i] : 0) : (l[p + j] <= p + i ? c[p + j] : 0); 
        }
    }
    return res;
}

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> l[i] >> r[i] >> c[i];

    for(int i = 1; i <= 5040; i++) sta[i].resize(8);
    dfs(1);

    if(n <= 7) {
        static int vis[10];
        int res, ans = 0;
        for(int t = 1; t <= nn; t++) {
            res = 0;
            for(int i = 1; i <= n; i++) vis[i] = 0;
            for(int ii = 1; ii <= n; ii++) {
                if(sta[t][ii] > n) break;
                int i = sta[t][ii];
                vis[i] = 1;
                for(int j = l[i]; j <= r[i]; j++) {
                    if(!vis[j]) res += c[i];
                }
            }
            ans = max(ans, res);
        }
        cout << ans << '\n';
        return 0;
    }

    init();

    for(int t = 1; t <= nn; t++) f[7][t] = 0;
    for(int i = 8; i <= n; i++) {
        for(int t = 1; t <= nn; t++) {
            int w = calc(i, t);
            for(int c = 1; c <= 8; c++) {
                gmax(f[i][trans[t][c]], f[i - 1][t] + w + calc1(i, t, c));
            }
        }
    }

    int ans = 0;
    for(int t = 1; t <= nn; t++) {
        gmax(ans, f[n][t] + calc_ans(t));
    }

    cout << ans << '\n';

    return 0;
}

T4 count

求有多少个有序四元组 \((a,b,c,d)\) 满足

  • \(1\le a,b,c,d\le n\)；
  • \(ab=cd\)；

\(T\le 10^6,~\sum n\le 10^{11}\)

我真的不是故意在每次模拟赛 T4 都放数论的。 --KaguyaH

直接枚举乘积，枚举量太大，没什么前途。考虑移项，设 \(\frac ac=\frac db=\frac pq,~(\gcd(p,q)=1)\)。那么答案可以写成

\[ -n^2+2\sum_{p=1}^{n}\sum_{q=1}^{p}[(p,q)=1]\Bigl\lfloor\frac np\Big\rfloor^2 \]

后面的式子可以写成

\[ \sum_{p=1}^{n}\Bigl\lfloor\frac np\Big\rfloor^2\varphi(p) \]

直接杜教筛即可，时间复杂度 \(O(n^{2/3})\)。考虑分析多测的复杂度，由于 \(n^{2/3}\) 是凹的，因此多测每一次 \(n\) 都取等时时间复杂度最高，可以写成 \(T(\frac{10^{11}}{T})^{2/3}=T^{1/3}\times 10^{2/3\times 11}\)，\(T\) 最大取到 \(10^6\)，无法通过。只需把较小的答案都预处理掉，使得多测次数不要太高。在杜教筛的预处理处顺便筛出 \(\le B\) 的答案。

考虑如何预处理答案。记上式为 \(f(n)\)，差分：

\[ f(n)=f(n-1)+\sum_{i|n}2(\frac ni-1)\varphi(i)+\varphi(i)=2\sum_{i|n}\frac{n}{i}\varphi(i)+n \]

再筛出 \(\varphi*\operatorname{Id}\) 即可。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include<iostream>
#include<cstring>
#include<cassert>
#define ll long long
#define lll __int128
using namespace std;
const int B = 2e7;

inline void read(ll &x) {
    char ch;
    while(!isdigit(ch = getchar()));
    x = ch - '0';
    while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
}

inline void write(lll x) {
    char buf[100], top = 0;
    do buf[++top] = x % 10, x /= 10; while(x);
    while(top) putchar_unlocked(buf[top--] + '0');
}

ll T, n;

int npri[B], pri[B], pcnt;
ll phi[B];

lll mem[(ll)(2e11) / B], f[B];

inline lll sum_phi(ll m) {
    if(m < B) return phi[m];
    if(mem[n / m]) return mem[n / m];
    lll res = (lll)m * (m + 1) / 2;
    for(ll l = 2, r; l <= m; l = r + 1) {
        r = m / (m / l);
        res -= (lll)(r - l + 1) * sum_phi(m / l);
    }
    mem[n / m] = res;
    return res;
}

lll calc(ll n) {
    if(n < B) return f[n];
    lll res = 0;
    for(ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res += (lll)(sum_phi(r) - sum_phi(l - 1)) * (n / l) * (n / l);
    }
    res = 2 * res - (lll)n * n;
    for(ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        if(l > B) mem[n / l] = 0;
    }
    return res;
}

int main() {

    // freopen("count.in", "r", stdin);
    // freopen("count.out", "w", stdout);

    phi[1] = f[1] = 1;
    for(int i = 2; i < B; i++) {
        if(!npri[i]) {
            pri[++pcnt] = i;
            npri[i] = i;
            phi[i] = i - 1;
            f[i] = phi[i] + i;
        }
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] >= B) break;
            if(i % pri[j] == 0) {
                npri[i * pri[j]] = npri[i] * pri[j];
                phi[i * pri[j]] = phi[i] * pri[j];
                if(i == npri[i]) {
                    f[i * pri[j]] = f[i] * pri[j] + phi[i * pri[j]];
                } else {
                    f[i * pri[j]] = f[i / npri[i]] * f[npri[i] * pri[j]];
                }
                break;
            } else {
                npri[i * pri[j]] = pri[j];
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
                f[i * pri[j]] = f[i] * f[pri[j]];
            }
        }
    }

    for(int i = 1; i < B; i++) f[i] = f[i - 1] + 2 * f[i] - i;
    for(int i = 1; i < B; i++) f[i] = 2 * f[i] - (lll)i * i;
    for(int i = 1; i < B; i++) phi[i] += phi[i - 1];

    read(T);
    while(T--) {
        read(n);
        write(calc(n));
        putchar_unlocked('\n');
    }

    return 0;
}