Educational Codeforces Round 185 (Rated for Div. 2) 记录

xxx2022 · 2025-11-29 16:07:46 · 个人记录

Educational Codeforces Round 185 (Rated for Div. 2) 记录

糖丸的一场，早早三个题但是没把D的啥比错误看出来，赛后B因为不开long long 见祖宗了。

A

可以贪心地取右下的几个可能作为答案的点，但是由于数据范围较小，暴力求解也可以通过。

B

由于需要求的是 r-l+1 的最大值，所以我们只需要关心第一步操作最大能是多少。

而假设第一步操作对一个长度为 len 的区间合法操作，那么后续可以通过恰好 n-1 步操作把 a 变成 b 等价于 \sum{b_i}-len \ge n-1

将数组 b 排序并去 0 后枚举第一步操作的长度即可。

C

注意到题目中其实给出了一个标准的带余除法的形式，稍加转化即可变为：

x=yq_i+r_j

其中 1 \le y \le x \le k ，那么我们保证 y < r_j 的情况下 x 尽量小是比较优的。因此取 y=r_j-1 ，那么一组 q_i,r_j合法等价于:

(r_j-1)q_i+r_j \le k

注意到左边式子的值随 r_j,q_i 的增大而增大，所以贪心地对于每个较大的 r_j 匹配较小的 q_i 即可，使用双指针维护，时间复杂度 O(n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int N=2e5+10;
int n,k;
int q[N],rr[N];
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>q[i];
    }
    for(int i=1;i<=n;i++){
        cin>>rr[i];
    }
    sort(q+1,q+n+1);
    sort(rr+1,rr+n+1);
    int l,r;
    l=1,r=n;
    int ans=0;
    while(l<=n && r>=1){
        if(q[l]*(rr[r]+1)+rr[r]<=k){
            l++;
            r--;
            ans++;
        }else{
            r--;
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int i=1;i<=T;i++){
        solve();
    }
    return 0;
}

D

注意到当有 \text{I} 的时候填 \text{I} 是优的，所以可以先假设所有 \text{?} 处都被填为了 \text{I} ，那么就需要考虑在 \text{I} 不够用的时候将其替换为 \text{X,V} 即可。这里 \text{X,V} 除了值不一样没有本质不同，所以可以放在一起考虑，有 \text{V} 的时候优先填 \text{V} ，没了再填上 \text{X}。

接下来再考虑怎么填比较优。这里我们可以把这个串中各个连续的问号段拉出来一个个单独考虑，因为 \text{I} 的值只受其后面一个字符影响，各个被非问号字符隔开的连续问号段并不能相互影响。此时观察一下可以发现每一个问号存在三类情况：

$case2: IIX $ 或 $XII

case3: XIX

其中的 \text{X} 均可以由 \text{V} 替代。

对于第一类点，假设将其值变为 x ，对答案的影响为 x-1-2=x-3

同理第二类为 x-1 ,第三类为 x+1 。

因此转换顺序为一类点-二类点-三类点。

此时则会出现一个问题，在转化过程中点的类型可能会发生变化。这个只需先将一类点标记完再考虑二类点，剩下的均化为三类点即可。

而对于各个连续问号段，我们还需要讨论它两边字符的值才能计算其中各类点的数量。

$$s_1= \lceil \frac{len}{2} \rceil$$ $$s_2= [len \mod 2=0]$$ $$s_3=len-s_1-s_2$$ 其余情况也同理。 $case2:$ 两边其中一个不为 $\text{I}$, 此时 $$s_1= \lfloor \frac{len}{2} \rfloor$$ $$s_2= [len \mod 2=1]$$ $$s_3=len-s_1-s_2$$ $case3:$ 两边均不为 $\text{I}$, 此时 $$s_1= \begin{cases} \lfloor \frac{len}{2} \rfloor & len \mod 2=1 \\ \frac{len}{2}-1 & len \mod 2=0 \end{cases}$$ $$s_2= [len \mod 2=0]$$ $$s_3=len-s_1-s_2$$ 先预处理出各种点的数量，询问时将多出的被 $\text{I}$ 覆盖的问号点分配给 $\text{X,V}$ 即可，时间复杂度 $O(n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int T;
int n,q;
char s[N];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)   cin>>s[i];
    int s1=0;
    int s2=0;
    int s3=0;
    int res=0;
    int ss=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='X')   res+=10;
        else if(s[i]=='V')  res+=5;
        else{
            if(i+1<=n && (s[i+1]=='X' || s[i+1]=='V'))  res--;
            else    res++;
        }
        if(s[i]=='?')   ss++;
    }
    s[n+1]='I';
    s[0]='X';
    int ss1,ss2,ss3;
    for(int i=1;i<=n;i++){
        if(s[i]=='?'){
            int j=i;
            while(s[j]=='?')    j++;
            j--;
            int len=j-i+1;
            ss1=ss2=ss3=0;
            // cout<<i<<" "<<j<<'\n';
            if(s[i-1]=='I' && s[j+1]=='I'){
                ss1+=len/2+((len&1)?1:0);
                ss2+=(len&1)?0:1;
                ss3+=len-ss1-ss2;
            }else if(s[i-1]=='I'){
                ss1+=len/2;
                ss2+=(len&1);
                ss3=len-ss1-ss2;
            }else if(s[j+1]=='I'){
                ss1+=len/2;
                ss2+=(len&1);
                ss3+=len-ss1-ss2;
            }else{
                if(len&1){
                    ss1=len/2;
                    ss3=len-ss1;
                }else{
                    ss1=len/2-1;
                    ss2=1;
                    ss3=len-ss1-ss2;
                }
            }
            // cout<<ss1<<" "<<ss2<<" "<<ss3<<'\n';
            s1+=ss1;
            s2+=ss2;
            s3+=ss3;
            // cout<<s1<<" "<<s2<<" "<<s3<<'\n';
            i=j;
        }
    }
    // cout<<s1<<" "<<s2<<" "<<s3<<'\n';
    // cout<<res<<'\n';
    ss1=s1,ss2=s2,ss3=s3;
    while(q--){
        int cx,cy,cz;
        cin>>cx>>cy>>cz;
        int ans=res;
        if(cz>=ss){
            cout<<ans<<'\n';
            continue;
        }
        s1=ss1,s2=ss2,s3=ss3;
        int now=ss-cz;
        if(cy<=now){
            now-=cy;
            if(cy>=s1){
                cy-=s1;
                ans+=s1*2;
                s1=0;
            }else{
                ans+=cy*2;
                s1-=cy;
                cy=0;
            }
            if(cy>=s2){
                cy-=s2;
                ans+=s2*4;
                s2=0;
            }else{
                ans+=cy*4;
                s2-=cy;
                cy=0;
            }
            if(cy>=s3){
                cy-=s3;
                ans+=s3*6;
                s3=0;
            }else{
                ans+=cy*6;
                s3-=cy;
                cy=0;
            }
            // cout<<"ok "<<ans<<'\n';
            if(now>=s1){
                now-=s1;
                ans+=s1*7;
                s1=0;
            }else{
                ans+=now*7;
                now-=s1;
                now=0;
            }
            if(now>=s2){
                now-=s2;
                ans+=s2*9;
                s2=0;
            }else{
                ans+=now*9;
                s2-=now;
                now=0;
            }
            if(now>=s3){
                now-=s3;
                ans+=s3*11;
                s3=0;
            }else{
                ans+=now*11;
                s3-=now;
                now=0;
            }
            cout<<ans<<'\n';
        }else{
            if(now>=s1){
                now-=s1;
                ans+=s1*2;
                s1=0;
            }else{
                ans+=now*2;
                s1-=now;
                now=0;
            }
            if(now>=s2){
                now-=s2;
                ans+=s2*4;
                s2=0;
            }else{
                ans+=now*4;
                s2-=now;
                now=0;
            }
            if(now>=s3){
                now-=s3;
                ans+=s3*6;
                s3=0;
            }else{
                ans+=now*6;
                s3-=now;
                now=0;
            }
            cout<<ans<<'\n';
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int i=1;i<=T;i++){
        solve();
    }
    return 0;
}

E

稍加观察容易发现，当block数量为1是不行的，而当其数量大于一时，若有偶数个block，移除开头的即可转化为奇数个，若有奇数个block，移除中间的一个即可。所以字符串是完美的等价于这个字符串中的字符不全相等。

考虑dp。记 f_i 为当考虑前 i 个字符，第 i 个字符和第 i+1 个字符不相等时时的合法方案数。此时若不考虑各个给出区间的限制，有转移式：

f_i= \sum_{j=0}^{i-1}{f_j}

这个式子的实际意义即为：对于每个 j ，令区间 [j+1,i] 全部相等，再拼上前面 j \not= j+1 的合法串所形成的新的合法串。在dp时我们相当于是钦定了第一位为 0/1 ，所以最终答案为 f_{n} \times 2

在这之后我们再考虑题目中给出的各个区间的限制。对于一个区间 [i,j] ，我们无法将 \sum_{j=0}^{i-1} 转移到 f_j ，因为这相当于钦定了 [i,j] 中的字符全部相等，与限制相矛盾。所以转移时对于每一个点 i ，我们不能让任意一个位置坐标小于等于前 i 个元素中最大的左端点的的点的答案转移过来。

此时我们记以 i 为右端点时最大的左端点为 R_i ，那么有：

R_i = \max(R_{i-1},R_i)

最后dp转移的时候前缀和优化即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=3e5+10;
int T;
int n,m;
int f[N],sum[N];
int R[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        R[r]=max(R[r],l);
    }
    for(int i=1;i<=n;i++)   R[i]=max(R[i],R[i-1]);
    sum[0]=f[0]=1;
    for(int i=1;i<=n;i++){
        if(R[i]){
            f[i]=(sum[i-1]-sum[R[i]-1]+mod)%mod;
            f[i]%=mod;
        }else{
            f[i]=sum[i-1];
            f[i]%=mod;
        }
        sum[i]=sum[i-1]+f[i];
        sum[i]%=mod;
        // cout<<f[i]<<" ";
    }
    // cout<<'\n';
    cout<<2*f[n]%mod<<'\n';
    for(int i=1;i<=n;i++)   R[i]=0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int i=1;i<=T;i++){
        solve();
    }
    return 0;
}