首页 模拟赛

dp + 矩阵乘法，贪心 + 贪心 + 贪心，期望 dp + 线段树

# A. 【长沙 2020 年 1 月集训 day10】黎曼几何

简单推式子题。

设第一个环到第二个环需要的次数为 fif_i，第一个环到第三个环需要的次数位 gig_i。

  • 对于 fif_i，先把前 i−1i - 1 个硬币扔到 ③ 上面，再把第 ii 个硬币扔到 ② 上面，最后把前 i−1i - 1 个硬币从 ③ 扔到 ② 上面（① →\rightarrow ③ 和 ③ →\rightarrow ② 是相等的）。

    所以 fi=2×gi−1+1f_i = 2 \times g_{i - 1} + 1.

  • 对于 gig_i，同样考虑上述过程，不难推出 gi=2×gi−1+fi+2g_i = 2 \times g_{i - 1} + f_i + 2.

然后发现需要矩阵加速一下，所以给他放到一个向量里面：

∣1figi∣\begin{vmatrix}1 & f_i & g_i\end{vmatrix}

稍微推一下矩阵，可以推出：

∣1figi∣∗∣112001022∣=∣1fi+1gi+1∣\begin{vmatrix}1 & f_i & g_i\end{vmatrix} * \begin{vmatrix}1 & 1 & 2 \\ 0 & 0 & 1 \\ 0 & 2 & 2 \end{vmatrix} = \begin{vmatrix}1 & f_{i + 1} & g_{i + 1}\end{vmatrix}

但是每次都跑一遍 log⁡n\log n 的矩阵快速幂也会 T，所以还要使用光速幂，也就是把矩阵快速幂的结果记录下来，每次询问的时候直接调用矩阵即可。

（由于考场上一直在卡常，导致代码有些丑陋，甚至还把 nn 存了下来，排了个序，但还是没卡过去 /kk）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int mod = 998244353;
const int N = 2e6;
const int B = 1e6;
int T;
ll n[N];
struct matrix{
    int num[5][5];
    matrix() {memset(num, 0, sizeof(num));}
    inline void init() {num[0][0] = num[1][1] = num[2][2] = 1;}
    inline void Clear() {num[0][0] = num[0][1] = num[0][2] = num[1][0] = num[1][1] = num[1][2] = num[2][0] = num[2][1] = num[2][2] = 0;}
    matrix operator * (const matrix &b) const{
        matrix r;
        for(int i = 0; i < 3; ++i)
            for(int j = 0; j < 3; ++j){
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][0] * b.num[0][j]) % mod;
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][1] * b.num[1][j]) % mod;
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][2] * b.num[2][j]) % mod;
            }
        return r;
    }
    matrix operator ^ (ll b) const{
        matrix r, a;
        memcpy(a.num, num, sizeof(num));
        r.init();
        for(; b; a = a * a, b >>= 1)
            if(b & 1) r = r * a;
        return r;
    }
}A, f, I, pw[2][N];
int a, b;
inline void prework(){
    I.num[0][0] = I.num[1][1] = I.num[2][2] = 1;
    pw[0][0] = pw[1][0] = I;
    for(int i = 1; i <= B; ++i) pw[0][i] = pw[0][i - 1] * A;
    for(int i = 1; i <= B; ++i) pw[1][i] = pw[1][i - 1] * pw[0][B];
}
inline matrix ksm(ll n) {return pw[1][n / B] * pw[0][n % B];}
signed main(){
    // freopen("riemannian.in", "r", stdin);
    // freopen("riemannian.out", "w", stdout);
    A.num[0][0] = A.num[0][1] = A.num[1][2] = 1, A.num[0][2] = A.num[2][1] = A.num[2][2] = 2;
    f.num[0][0] = f.num[0][1] = 1, f.num[0][2] = 2;
    prework();
    T = read();
    for(int i = 1; i <= T; ++i) n[i] = read();
    sort(n + 1, n + 1 + T);
    int pos;
    for(int i = 1; i <= T; ++i)
        if(n[i]){
            if(n[i] > 1)  A = ksm(n[i] - 1), f = f * A;
            a ^= f.num[0][1], b ^= f.num[0][2], pos = i;
            break;
        }
    for(int i = pos + 1; i <= T; ++i){
        if(n[i] - n[i - 1] == 0){a ^= f.num[0][1], b ^= f.num[0][2]; continue;}
        A = ksm(n[i] - n[i - 1]), f = f * A;
        a ^= f.num[0][1], b ^= f.num[0][2];
    }
    printf("%d %d\n", a, b);
    return 0;
}
// X.K.
# B. 【长沙 2020 年 1 月集训 day10】代数几何
巨大贪心，你需要找到三个结论方可通过此题。
不难发现，在放数时有的时候会出现一些循环节，那么……
最重要的结论： 循环节个数为 gcd⁡(n,k)\gcd(n, k)。
至于为什么，建议打表……
所以对于每个循环节我们分别考虑即可。
另外两个结论：
  • 每一个循环节中的数一定是连续的。
  • 摆放方式一定是：⋯,x−3,x−1,x,x−2,x−4,⋯\cdots, x - 3, x - 1, x, x - 2, x - 4, \cdots
这两个都不难理解，大的数和大的数相乘一定更优，因此感性理解一下上面这两个结论都是正确的。
然后代码就十分的 easy\text{easy} 了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 5010;
int n, m, ans;
int a[N], b[N], c[N];
inline int add(int x) {return x >= n ? x - n : x;}
inline int sub(int x) {return x < 0 ? x + n : x;}
inline bool cmp(int a, int b) {return a > b;}
inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
inline int calc(int n){
    if(n == 1) return a[0] * a[0];
    if(n == 2) return a[0] * a[1] * 2;
    int res = a[0] * a[1] + a[0] * a[2] + a[n - 2] * a[n - 1];
    for(int i = 3; i < n; ++i) res += a[i] * a[i - 2];
    return res;
}
inline void solve(int k){
    int t = gcd(n, k);
    int len = n / t, cnt = 0;
    ans = 0;
    for(int l = 1; l <= t; ++l){
        for(int i = 0; i < len; ++i) a[i] = b[cnt++];
        ans += calc(len);
    }
    write(ans), puts("");
}
signed main(){
    n = read();
    for(int i = 0; i < n; ++i) a[i] = b[i] = read();
    sort(b, b + n, cmp);
    m = read();
    while(m--) solve(read());
    return 0;
}
// X.K.
# C. 【长沙 2020 年 1 月集训 day10】几何考试
考场上甚至连题目都没有看懂，遗憾离场了 QwQ
我现在只会 80pts 做法，满分做法先咕了。
题目就是要求别人对你排名贡献的期望和（我一直以为是一个人总排名的期望）。
我的做法是先对每个人排序，按照左端点从小到大排序，相同的按右端点从小到大排。
设 pi,jp_{i, j} 表示 ii 赢 jj 的概率（由于贡献都是 1，所以概率等于期望）。
对于两个人 i,j(i≤j)i, j(i \leq j)，此时 jj 的得分区间一定在 ii 的右边，分类讨论一下：
  • i,ji, j 得分区间交叉：如果 ii 想赢 jj，那么只有 i,ji, j 得分都在交叉的那段区间才行，设交叉区间长度为 bb，那么 pi,j=bleni×blenj×12p_{i, j} = \frac b{len_i} \times \frac b{len_j} \times \frac12.
  • i,ji, j 得分区间不相交：此时 ii 必输，所以 pi,j=0p_{i, j} = 0
  • ii 的得分区间包含 jj：此时 ii 获胜概率为 ii 在交叉区间得分的概率除以二加上 ii 在 jj 得分区间右边的概率，假设交叉区间长度为 bb，c=ri−rjc = r_i - r_j，那么 pi,j=bleni×12+clenip_{i, j} = \frac b{len_i} \times \frac12 + \frac {c}{len_i}。
pj,i=1−pi,jp_{j, i} = 1 - p_{i, j}.
然后对于每个人求个和即可。
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 5010;
int n;
struct node{
    int l, r, id;
    bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r < b.r;
    }
}a[N];
double p[N][N], ans[N];
signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read(), a[i].id = i;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){// p[i][j]: p[i win j]
            if(i == j) continue;
            int l1 = a[i].l, l2 = a[j].l, r1 = a[i].r, r2 = a[j].r;
            double a = l2 - l1, b = r1 - l2, c = abs(r2 - r1), len1 = r1 - l1, len2 = r2 - l2;
            if(l1 <= l2 && r1 <= r2) p[i][j] = (((b / len1) * (b / len2) / 2));
            if(r1 < l2) p[i][j] = 0;
            if(l1 <= l2 && r1 >= r2) p[i][j] = ((c / len1) + ((len2 / len1) / 2));
            p[j][i] = 1 - p[i][j];
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) ans[a[i].id] += p[j][i];
    for(int i = 1; i <= n; ++i) printf("%.8lf\n", ans[i] + 1);
    return 0;
}
// X.K.
 更新于   阅读次数  次