ABC224 部分题解

E.Integers on Grid

题意

给定(R imes C)的矩形，其中(N)个位置有权值(a_{i}) 从当前位置可以移动到当前列或当前行比当前位置权值大的位置

求这(N)个位置能移动的最大次数

[2 leq R,C leq 2 imes 10^5\ 1 leq N leq min(2 imes 10^5,RC)\ 1leq a_i leq 10^9 ]

分析

对于位置为(i,j)的元素，我们有明显转移方程

[dp_{i,j} = max(dp_{k,j}) + 1, 1 le k le n,a_{i,j} < a_{k,j}\ dp_{i,j} = max(dp_{i,k}) + 1,1 leq k leq m,a_{i,j} < a_{i,k} ]

这题用位置转移显然是麻烦的，不妨直接根据权值从大到小转移，对于每一行维护最大值即可

代码

const int maxn = 2e5 + 5;

int r[maxn],c[maxn],a[maxn];
int rm[maxn],cm[maxn];
int dp[maxn];
map<int,VI> mp;

int main(){
    int h = rd();
    int w = rd();
    int n = rd();
    for(int i = 1;i <= n;i++){
        r[i] = rd();
        c[i] = rd();
        a[i] = rd();
        mp[a[i]].push_back(i);
    }
    for(auto it = mp.rbegin();it != mp.rend();it++){
        for(auto i:it -> se) 
            dp[i] = max(rm[r[i]],cm[c[i]]);
        for(auto i:it -> se)
            rm[r[i]] = max(rm[r[i]],dp[i] + 1),cm[c[i]] = max(cm[c[i]],dp[i] + 1);
    }
    for(int i = 1;i <= n;i++)
        printf("%d
",dp[i]);
}

F.Problem where +s Separate Digits

题意

给定一个包含1-9的字符串，可以在字符串的非首尾位置随意插入‘+’ ，如1234可以成为12+34，那么这个方案的值为12+34=36

求所有方案的值的和

[1 leq |s| leq 2 imes 10^5\ ]

分析

考虑每个数的贡献即可，相当于对于一个数钦定其后面几个不能有'+',其余位置随便插入的方案数，这个系数显然是可以转移得出的，于是扫一遍即可

代码

const int maxn = 2e5 + 5;

char s[maxn];
int p2[maxn];
int p10[maxn];

int main(){
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    p2[0] = 1;
    p10[0] = 1;
    for(int i = 1;i <= n;i++)
        p2[i] = mul(p2[i - 1],2),p10[i] = mul(p10[i - 1],10);
    int ans = 0;
    int sum = 0;
    for(int i = 0;i < n - 1;i++)
        add(sum,mul(p10[i],p2[n - 2 - i]));
    for(int i = 1;i <= n;i++){
        add(ans,mul(s[i] - '0',sum + mul(p10[n - i],p2[i - 1])));
        add(sum,MOD - mul(p10[n - i - 1],p2[n - 1 - (n - i - 1) - 1]));
    }
    cout << ans;
}

G - Roll or Increment 思维期望

题意

给定(N)个面上分布(1-N)的骰子，初始给定的面是(S),询问最少花费策略下的期望花费使得骰子的面达到(T)

每次可以进行以下任意两种操作

花费(A)使得当前面所在的值+1(不影响下次)
花费(B)再投一次

保证每次投的概率分布均匀

[1 leq N leq 10^9\ 1 leq S,T leq 10^9\ 1 leq A,B leq 10^9 ]

分析

显然我们不可能在进行操作1后进行操作2

所以操作可以归纳为进行若干次操作2后进行若干次操作1

由于(A)是固定的，我们必然能找到一个阈值(X),使得一旦操作2随机到$geq X $就停止操作2，进行操作1

期望的花费 = 操作2的花费 + 操作1的花费

为方便计算令(X = T - X + 1)

操作2的期望花费 = $Bfrac{1}{P} = Bfrac{N}{X} $

操作1的期望花费 = (Asum_{i = T - X = 1}^T (T- i ) / X =frac{A(X-1)}{2})

把花费看作(X)的方程(f (X ) = frac{BN}{X} + frac{A(X-1)}{2})

它在(X = sqrt{2BN/A}) 时有极值，此题再加上一些特判即可

代码

inline ld f(int x){
    return (ld)a * (x - 1) / 2 + (ld)b * n / x;
}

int main(){
    n = rd();
    s = rd();
    t = rd();
    a = rd();
    b = rd();
    ld ans = 1e18;
    if(t >= s) ans = (ld)(t - s) * a;
    int x = sqrt(2. * b * n / a);
    ans = min(ans,f(1));
    ans = min(ans,f(t));
    for(int i = max(0,x - 1);i <= min(t,x + 1);i++)
        ans = min(ans,f(i));
    printf("%.10Lf",ans);
}