ABC224 部分题解

E.Integers on Grid

题意

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

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

\[2 \leq R,C \leq 2 \times 10^5\\ 1 \leq N \leq min(2\times 10^5,RC)\\ 1\leq 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\n",dp[i]);
}

F.Problem where +s Separate Digits

题意

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

求所有方案的值的和

\[1 \leq |s| \leq 2\times 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的期望花费 = $B\frac{1}{P} = B\frac{N}{X} $

操作1的期望花费 = \(A\sum_{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);
}