usedchang

题解题解 | #无穷无尽的力量#

题解

/ 注册

题解 | #无穷无尽的力量#

19 浏览 1 回复 2025-12-01

usedchang

+关注

无穷无尽的力量

https://ac.nowcoder.com/acm/contest/123788/A

A.无穷无尽的力量

输出长为2*n+1的串，当且仅当长为n+1的时候输出a,其余输出b

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n*2+1;i++){
        if(i!=n+1) cout<<'a';
        else cout<<'b';
    }
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;//cin>>T;
    while(T--) solve();
    return 0;
}

B.无穷无尽的字符串

差分的考虑[l,r]上的代价就是[0,r]上的代价减去[0,l-1]的代价 [0,x]上的代价分两段,

整块的只要考虑有几块接着考虑剩余不足3的块

如果剩余块大小大于1 a出现次数增加.

如果剩余块大小大于2 b出现次数增加.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    ll l,r;cin>>l>>r;
    auto calc=[&](ll x) ->array<ll,3> {
        ll res=x/3;
        array<ll,3>w={res,res,res};
        w[0]+=(x%3>=1);
        w[1]+=(x%3>=2);
        return w;
    };
    cout<<calc(r)[0]-calc(l-1)[0]<<' ';
    cout<<calc(r)[1]-calc(l-1)[1]<<' ';
    cout<<calc(r)[2]-calc(l-1)[2]<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;//cin>>T;
    while(T--) solve();
    return 0;
}

C.无穷无尽的力量2.0

分类讨论的小细节题目

先钦定 $n \leq m$ ，如果不满足交换即可

当 $n=1$ 时显然答案为1

当 $n=2$ 时答案取决于m的长度，每两段一划分马可跳的点数量为 $1+(m-1)/2$

当 $n=3$ 时,分两类,

$m=3$ ，此时通过手玩样例发现只能有8个点最多，中心点凿空

$m \geq 4$ ,此时矩阵看成多个个左右重叠的 $3\times 3$ 矩阵,就保证了都每个点可以遍历到

$n \geq 4$ 同理每个点都可以遍历到 ,答案为 $n\times m$ .

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    ll n,m;cin>>n>>m;
    if(n>m) swap(n,m);
    if(n==1) cout<<1<<endl;
    else if(n==2) cout<<1+(m-1)/2<<endl;
    else if(n==3&&m==3) cout<<8<<endl;
    else if(n>=3&&m>=4) cout<<n*m<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

D.无穷无尽的小数

首先因为 $n$ 和 $m$ 都很小，直接不考虑两个循环节部分位重叠情况，题目也没要求一定要最小的循环节

钦定答案最小循环节长度为 $lcm(n,m)$

补齐两个串的长度后直接启用高精减mini版本(题目保证了第一个小数比第二个小数大)

然后就转化为了高精减，直接套板子你会发现最后一位很讨厌，不好知道他到底末位是不是会-1

但是除了最后一位前面都是正常的，因此考虑给两个字符串长度翻个倍,统计答案时舍去后面一半

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
string operator-(string &a,string &b){
    vector<int>A,B;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    string ans;
    for(int i=0;i<A.size();i++){
        int x=A[i];
        int y=B[i];
        int t=x-y;
        if(t<0) {
            t+=10;
            if(i+1<A.size()) A[i+1]--;
        }
        ans.push_back(t+'0');
    }
    reverse(ans.begin(),ans.end());
    return ans;
}
void solve(){
    int n,m;
    cin>>n>>m;
    string s;cin>>s;
    string t;cin>>t;
    int k=lcm(n,m);
    int i=0,j=0;
    while(s.size()<k){
        s.push_back(s[i]);
        i=(i+1)%s.size();
    }//s循环补位
    while(t.size()<k){
        t.push_back(t[j]);
        j=(j+1)%t.size();
    }//t循环补位
    s=s+s;
    t=t+t;
    string ans=s-t;
    cout<<k<<endl;
    for(int i=0;i<k;i++) cout<<ans[i];
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

E.无穷无尽的树

删除叶子节点后留下的一定时非叶子节点，因此需要判定所有节点非叶子节点最深值及最深值的个数

可以做一个简单得树形dp,分dfs两次统计，第一次更新子树中不是叶子节点最深的深度,第二次统计最深值得个数

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e5+5;
vector<int>G[N];
int d[N];
int mx[N],ans[N];
void dfs(int u,int fa,int dep){
    d[u]=dep;
    if(u==1||G[u].size()!=1){//不是叶子节点条件
        mx[u]=max(d[u],mx[u]);
    }//统计每个子树中不是叶子节点的最深节点的数量
    for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u,dep+1);
        //树形dp,用子树最深值更新
        mx[u]=max(mx[u],mx[v]);
    }
}
void __dfs(int u,int fa){
    ans[u]+=(mx[u]==d[u]);
    for(int v:G[u]){
        if(v==fa) continue;
        __dfs(v,u);
        if(mx[v]!=mx[u]) continue;
        //树形dp,用子树最深值个数更新
        ans[u]+=ans[v];
    }
}
void solve(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0,1);
    __dfs(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<' '; 
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

F.无穷无尽的数

鉴定为B plus版本

考虑方法和B差不多，差分的去统计 [l,r]的代价就是 $[0,r]-[0,l-1]\times 10^{r-l+1}$

转化为考虑[0,x]代价如何统计

然后分成若干长为 $n$ 的整块和一个长度不足 $n$ 的剩余块

若干块之间满足等比性质，公比为 $10^n$ 长度为 $x/x$ ,首项就是作为循环节字符串代表的值 $S$

这样对若干整块等比数列求和即可, $ans_1=\dfrac{S·({(10^n)}^{x/n}-1)}{(10^n-1)}$

然后剩余块的值 $ans_2=rem$ 可以通过预处理直接O(1)的得出

这样最终答案就是 $ans=ans_1\times 10^{ans_2.siz()}+ans_2$

其中, $ans_1$ 表示长度为 $n$ 的整块代价累计和，

$ans_2$ 表示长度不足 $n$ 的剩余块的代价

$ans_2.siz()$ 用于表示剩余串的十进制长度

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll mod=998244353;
ll q_pow(ll x,ll y){
    y%=mod-1;//费马小定理降幂
    ll s=1;
    while(y>0){
        if(y&1){
            s=s*x%mod;
        }
        x=x*x%mod;
        y>>=1;
    }
    return s;
}
ll inv(ll x){return q_pow(x,mod-2);}
void solve(){
    int n;ll l,r;
    cin>>n>>l>>r;
    string s;
    cin>>s;
    s="&"+s;//1-idx便于统计
    vector<ll>a(n+1);//每个循环节长度下的值
    vector<ll>pw(n+1,1);//pow(10,i) mod意义下的值
    for(int i=1;i<=n;i++) {
        a[i]=(a[i-1]*10%mod+(s[i]-'0'))%mod;
        pw[i]=(pw[i-1]*10)%mod;
    }
    ll Inv2=inv(2);
    auto calc=[&](ll x) ->ll {
        ll res=(a[n]*(q_pow(pw[n],x/n)-1))%mod*inv(pw[n]-1)%mod;//等比数列求和
        ll rem=x%n;//在等比数列外的余项数量
        res=res*pw[rem]%mod;
        res=(res+a[rem])%mod;
        return res;
    };//统计[0,x]上的贡献
    ll ans=calc(r)-calc(l-1)*q_pow(10,r-l+1)%mod;//进行一个差分的统计 区间[l,r]的贡献是[0,r]-[0,l-1]的贡献
    ans=(ans%mod+mod)%mod;
    cout<<ans<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
    return 0;
}

C++

举报

收藏

赞 2

评论加载中...