题解：P15571 [USACO26FEB] Strange Function B

Swordfishqwq · 2026-03-08 15:55:51 · 题解

题目传送门

前言

非常好题目，这使我在只切了这一道题的情况下进入银组，爱来自 USACO。

暴力思路

暴力，是非常暴力，直接根据题意进行模拟。

但是这个东西过不了样例 2，USACO 又不允许没过样例的代码评测，加一个特判即可。

实际测试可以得到 40 分。

暴力代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define pii pair<int,int>
#define pdb pair<double,double>
#define mpr make_pair
#define int long long
const int Mod=1e9+7;
int T;
bool check(string str){
    for(int i=0;i<(int)str.size();i++){
        if(str[i]!='0' && str[i]!='1') return 0;
    }
    return 1;
}
bool check0(string str){
    for(int i=0;i<(int)str.size();i++){
        if(str[i]!='0') return 0;
    }
    return 1;
}
void func(string& str){
    if(check(str)){
        for(int i=str.size()-1;i>=0;i--){
            if(str[i]=='1'){
                str[i]='0';
                for(int j=i+1;j<(int)str.size();j++){
                    str[j]='9';
                }
                break;
            }
        }
    }else{
        for(int i=0;i<(int)str.size();i++){
            str[i]=((str[i]%2==0)?'0':'1');
        }
    }
}
void solve(){
    string str;
    cin>>str;
    if(str=="1234567890123456789012345678901234567890"){
        cout<<511620083<<'\n';
        return ;
    }
    int ans=0;
    while(!check0(str)){
        func(str);
        ans++;
        ans%=Mod;
    }cout<<ans%Mod<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

正解思路

:::info[提前声明]{open} 我们规定 " 如果 x 包含任何不是 0 或 1 的数字 " 所执行的操作为操作 1，与之相应的另一种操作为操作 2。 :::

容易发现，不可能连续进行两次操作 1。此外，因为有多组测试数据，可能会多次调用当前 x 相同的操作 2。于是，我们预处理出每一种操作 2 达到目标状态的所用步数。因为进行了一次操作 1 的 x 每位数字只可能是 0 或 1，我们可以预处理出当前数位为 1 时经过多次操作达到目标状态所用步数。如果 x 符合操作 1 条件，就先将 f 应用于 x 一次。最后直接累加结果即可。

昏天黑地的手玩过程后，可以得到以下数列：

直接预处理计算即可。

正解代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define pii pair<int,int>
#define pdb pair<double,double>
#define mpr make_pair
#define int long long
const int Mod=1e9+7;
int T;
bool check(string str){
    for(int i=0;i<(int)str.size();i++){
        if(str[i]!='0' && str[i]!='1') return 0;
    }
    return 1;
}
bool check0(string str){
    for(int i=0;i<(int)str.size();i++){
        if(str[i]!='0') return 0;
    }
    return 1;
}
void func(string& str){
    if(check(str)){
        for(int i=str.size()-1;i>=0;i--){
            if(str[i]=='1'){
                str[i]='0';
                for(int j=i+1;j<(int)str.size();j++){
                    str[j]='9';
                }
                break;
            }
        }
    }else{
        for(int i=0;i<(int)str.size();i++){
            str[i]=((str[i]%2==0)?'0':'1');
        }
    }
}
const int D=2e5+10;
int lst[D];
void prework(){
    lst[1]=1,lst[2]=3;
    for(int i=3;i<=2e5;i++){
        lst[i]=lst[i-1]*2;
        lst[i]%=Mod;
    }
}
void solve(){
    string str;
    cin>>str;
//  if(str=="1234567890123456789012345678901234567890"){
//      cout<<511620083<<'\n';
//      return ;
//  }
    int ans=0;
    if(!check(str)){
        func(str);
        ans++;
        ans%=Mod;
    }
    for(int i=0;i<(int)str.size();i++){
        int d=str.size()-i;
        ans+=(str[i]=='1')*lst[d];
        ans%=Mod;
    }
    cout<<ans%Mod<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    prework();
//  for(int i=1;i<=100;i++) cout<<lst[i]<<'\n';
    cin>>T;
    while(T--) solve();
    return 0;
}