ABC465 - LeAf146

LeAf146

公告

叶子的博客，随便看看吧。

Learn More

标签

服务器网络字符串 ACM Agnet AI Blog Blogging codeforces

805 字

3 分钟

ABC465

2026-07-20

ACM

/

Blog

A. Supermajority #

给定整数 $A$ 和 $B$ ，判断是否有 $A>B\times \frac{2}{3}$ .

避免除法，改为判断 $A\times 3>B\times 2$ .

1
signed main(){
2
    int a,b;cin>>a>>b;
3
    if(a*3>b*2) cout<<"Yes\n";
4
    else cout<<"No\n";
5
    return 0;
6
}

B. Parking 2 #

停车，从 $L$ 点到 $R$ 点整，每小时收费 $X$ 元，时间段以外收费 $Y$ 元。从 $A$ 点停到 $B$ 点，计算收费。

模拟，注意分割点即可。

1
signed main(){
2
    int x,y,l,r,a,b;cin>>x>>y>>l>>r>>a>>b;
3
    if(a>=r||b<=l){
4
        cout<<(b-a)*y;
5
    }else{
6
        if(a>=l){
7
            if(b<=r){
8
                cout<<(b-a)*x;
9
            }else{
10
                cout<<(r-a)*x+(b-r)*y;
11
            }
12
        }else{
13
            if(b<=r){
14
                cout<<(b-l)*x+(l-a)*y;
15
            }else{
16
                cout<<(b-r+l-a)*y+(r-l)*x;
17
            }
18
        }
19
    }
20
    return 0;
21
}

C. Reverse Permutation #

给定由 o 和 x 组成的长度为 $N$ 的字符串 $S$ 和最初为 $(1,2,\dots,N)$ 的整数序列 $A$ 。对于 $k=1,2,\dots,N$ ，当 $S_k=$ o 时，将 $A$ 的前 $k$ 项翻转；当 $S_k=$ x 时，不做任何操作。输出最后的 $A$ 。

注意到，只有 $S_k$ 会影响 $n$ 的位置，当 $S_k=$ o 时， $n$ 在输出的最前面，反之则在最后面。易得，用一个 tag 标记是否翻转，检查每一个 $S_k$ 来更改 tag，若翻转，则把 $k$ 放在输出的最前面，反之放在输出的最后面。用双向队列可以简单地实现。

1
signed main(){
2
    int n;string s;cin>>n>>s;
3
    deque<int> dq;
4
    int rev=0;
5
    dq.push_back(1);
6
    for(int i=2;i<=n;i++){
7
        if(rev)dq.push_front(i);
8
        else dq.push_back(i);
9
        if(s[i-1]=='o')rev=!rev;
10
    }
11
    if(rev){
12
        reverse(dq.begin(),dq.end());
13
    }
14
    while(dq.size()){
15
        cout<<dq.front()<<' ';
16
        dq.pop_front();
17
    }
18
    return 0;
19
}

D. X to Y #

给定整数 $X,Y$ 和至少为 $2$ 的整数 $K$ 。每次操作可以使得满足 $\left\lfloor \frac{x}{K} \right\rfloor=y$ 或 $\left\lfloor \frac{y}{K} \right\rfloor=x$ 的 $x$ 替换为 $y$ 。问最少多少次可以使得 $x=Y$ 。

显然，操作可逆。而将 $x$ 变大共有 $k$ 种可能，将 $x$ 变小则只有一种可能。不妨只变小两者中较大的数，直到相等。由数与数之间的关系做树，易得，这就是最优解。

1
void solve(){
2
    int x,y,k;cin>>x>>y>>k;
3
    int ans=0;
4
    while(x!=y){
5
        if(x>y)swap(x,y);
6
        y/=k;
7
        ans++;
8
    }
9
    cout<<ans<<endl;
10
}

E. Digit Circus #

以 $998244353$ 为模数，问从 $1\leq x\leq N$ 的 $x$ 中，有多少满足下面条件中恰好一个：

$x$ 是 $3$ 的倍数。
$x$ 的十进制表示包含 $3$ 。
$x$ 的十进制表示恰好用了三个不同的数字（没有前导 0）。

显然，数位 DP，不会或者忘记的话看看模板。太不喜欢数位 DP 了，找了板子来写。。。 DP 共四维，第一维为约束，第二维标记前导 0。第三维才和本题题意有关，做数字之和模 $3$ 的余数，当余数为 $0$ 时，即满足第一个条件。最后一维是状态压缩掩码，枚举已有的数字集合，从 $0$ 到 $9$ 共 $1024$ 个状态，要求必须有 $3$ 和另外两个不同的数字。

1
int dp[2][2][3][1024];
2
signed main(){
3
    string s;
4
    getline(cin,s);
5
    int n=s.size();
6
    dp[1][1][0][0]=1;
7
    for(int i=0;i<n;i++){
8
        int ndp[2][2][3][1024];
9
        memset(ndp,0,sizeof(ndp));
10
        int upper=s[i]-'0';//当前位最大可选数字
11
        for(int tight=0;tight<2;tight++){
12
            for(int lead=0;lead<2;lead++){
13
                for(int mod=0;mod<3;mod++){
14
                    for(int mask=0;mask<1024;mask++){
15
                        int val=dp[tight][lead][mod][mask];
16
                        if(val==0)continue;
17
                        int up=tight?upper:9;//如果当前为约束状态
18
                        for(int d=0;d<=up;d++){//枚举当前位的可选数，状态转移
19
                            int ntight=(tight&&d==up)?1:0;
20
                            int nlead=(lead&&d==0)?1:0;
21
                            int nmod=(mod*10+d)%3;
22
                            int nmask;
23
                            if(nlead) nmask=0;
24
                            else if(lead) nmask=1<<d;
25
                            else nmask=mask|(1<<d);
26
                            ndp[ntight][nlead][nmod][nmask]=(ndp[ntight][nlead][nmod][nmask]+val)%MOD;
27
                        }
28
                    }
29
                }
30
            }
31
        }
32
        memcpy(dp,ndp,sizeof(dp));
33
    }
34
    int cnt[8]={0};
35
    for(int tight=0;tight<2;tight++){
36
        for(int mod=0;mod<3;mod++){
37
            for(int mask=0;mask<1024;mask++){
38
                int val=dp[tight][0][mod][mask];//不能有前导 0
39
                if(val==0)continue;
40
                int a=(mod==0);//满足条件 1
41
                int b=(mask>>3)&1;//满足条件 2
42
                int c=(__builtin_popcount(mask)==3);//满足条件 3
43
                int idx=(a<<2)|(b<<1)|c;//恰好满足一个条件的只有 4,2,1
44
                cnt[idx]=(cnt[idx]+val)%MOD;
45
            }
46
        }
47
    }
48
    int ans=(cnt[4]+cnt[2]+cnt[1])%MOD;
49
    cout<<ans<<endl;
50
    return 0;
51
}

ABC465

https://leaf146.cn/posts/abc465

作者

LeAf146

发布于

2026-07-20

许可协议

MIT

部分信息可能已经过时

ABC 467

CF476

LeAf146's blog

A. Supermajority#

B. Parking 2#

C. Reverse Permutation#

D. X to Y#

E. Digit Circus#

A. Supermajority #

B. Parking 2 #

C. Reverse Permutation #

D. X to Y #

E. Digit Circus #