一、[USACO24DEC] Roundabount Rounding B

1. 审题

题目描述

奶牛 Bessie 回到学校了！她开始做她的数学作业，在作业中她被要求将正整数四舍五入到 $10$ 的幂。
要将一个正整数 $a$ 四舍五入到最接近的 $10^b$，其中 $b$ 为正整数，Bessie 首先找到从右往左数第 $b$ 个数位。令 $x$ 为这个数位。
如果 $x\ge 5$，Bessie 将 $a$ 增加 $10^b$。
然后，Bessie 将从右侧开始直至第 $b$ 个数位的所有数位均设置为 $0$。
例如，如果 Bessie 想要将 $456$ 四舍五入到最接近的 $10^2$（百位），Bessie 会首先找到从右往左数第 $2$ 个数位 $5$。这意味着 $x=5$。然后由于 $x\ge 5$，Bessie 将 $a$ 增加 $100$。最后，Bessie 将 $a$ 中从右侧开始直至第 $2$ 个数位的所有数位设置为 $0$，结果为 $500$。
但是，如果 Bessie 将 $446$ 四舍五入到最接近的 $10^2$，她将得到 $400$。
在看了 Bessie 的作业后，Elsie 认为她已经发明了一种新的舍入方式：链式舍入。要链式舍入到最接近的 $10^b$，Elsie 将首先舍入到最接近的 $10^1$，然后舍入到最接近的 $10^2$
，以此类推，直至舍入到最接近的 $10^b$。
Bessie 认为 Elsie 是错误的，但她太忙于数学作业，无法确认她的怀疑。她请你计算出存在多少个不小于 $2$ 且不超过 $N$ 的整数 $x$（$1\le N\le 10^9$），使得将 $x$ 四舍五入到最接近的 $10^P$ 与链式舍入到最接近的 $10^P$ 的结果不同，其中 $P$ 是满足 $10^P\ge x$ 的最小整数。

输入格式

你需要回答多个测试用例。
输入的第一行包含一个整数 $T$（$1\le T\le 10^5$），为测试用例的数量。以下是 $T$ 个测试用例。
每个测试用例的输入仅有一行，包含一个整数 $N$。输入保证同一测试点中的所有 $N$ 各不相同。

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示存在多少个不小于 $2$ 且不超过 $N$ 的整数在使用两种舍入方法时会得到不同的结果。

样例 1

输入

4
1
100
4567
3366

输出

0
5
183
60

提示

样例解释
考虑样例中的第二个测试用例。$48$ 应当被计算在内，因为 $48$ 链式舍入到最接近的 $10^2$ 是 $100$（$48→50→100
$），但 $48$ 四舍五入到最接近的 $10^2$ 是 $0$。
在第三个测试用例中，$48$ 和 $480$ 是两个被计算在内的整数。$48$ 链式舍入到 $100$ 而不是 $0$，$480$ 链式舍入到 $1000$ 而不是 $0$。但是，$67$ 不被计算在内，因为它链式舍入到 $100$，与 $67$ 四舍五入到最接近的 $10^2$ 相同。
测试点性质

• 测试点 1：样例。
• 测试点 2-4：$N\le 10^3$。
• 测试点 5-7：$N\le 10^6$。
• 测试点 8-13：没有额外限制。

2. 分析

这类题目大家很容易被长题目中的各种信息迷惑，尤其是题目读完之后，大家应该还是一脸懵的状态。

所以简单概括一下题意：

有一个数 $n$，要求找到 $2\sim n$ 之间所有数字 $x$ 中，两种舍入方法（舍入到 $10^p\ge x$）不同结果的数量。

2.1 暴力模拟

其中，Bessie 的做法是：直接看最高位，如果 $\ge 5$ 则进位（结果一定是 $10^p$）否则就是 $0$；而 Elsie 的做法是：从最低位开始，如果当前数位 $\ge 5$ 则进位，否则是 $0$。

对于 Bessie 的做法，简单的分支结构就可以直接解决；对于 Elsie 的做法，可以用自带的 round(double x) 函数解决。写出代码如下，$10^3$ 内的数据已经解决：

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=2;i<=n;i++){
            //四舍五入
            int x=i,cnt=0;
            while(x>=10){
                x/=10;
                cnt++;
            }
            //运行后x变成i的最高位
            if(x>=5)x=1;
            else x=0;
            
            //链式舍入
            int y=i;
            for(int j=1;j<=cnt+1;j++)
                y=round(y/10.0);//每次舍入
            
            //判断最高位的异同
            if(x!=y)ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

2.2 预处理优化

采用二分+打表的方式进行预处理，从而骗过 $10^6$ 以内的数据。

#include<bits/stdc++.h>
using namespace std;
int t,n;
vector<int>init(int n){
    for(int i=2;i<=n;i++){
        //四舍五入
        int x=i,cnt=0;
        while(x>=10){
            x/=10;
            cnt++;
        }
        if(x>=5)x=1;
        else x=0;
        
        //链式舍入
        int y=i;
        for(int j=1;j<=cnt+1;j++)
            y=round(y/10.0);
        
        //判断异同
        if(x!=y)ans.push_back(i);//将不同的数字放入ans[]
    }
    return ans;
}
int main(){
    auto q=init(1e6);//预处理
    cin>>t;
    while(t--){
        cin>>n;
        int ans=upper_bound(q.begin(),q.end(),n)-q.begin();//找到下标相减即可获得不同的数量
        cout<<ans<<endl;
    }
    return 0;
}

2.3

优化到走投无路的时候，采用一下数学性质进行优化。我们用 2.1 的程序打一下表就会发现：

进位到	输出数字
$10$	$/$
$100$	$45\sim 49$
$1000$	$445\sim 499$
$10^4$	$4445\sim 4999$

这样我们可以直接打表：

#include<bits/stdc++.h>
using namespace std;
int t,n;
int up[]={49,499,4999,49999,49999,499999,4999999,4999999};//所有的区间上限
int down[]={45,445,4445,44445,444445,4444445,44444445,444444445};//所有的区间下限
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=0;i<8;i++){
            if(n>=up[i])ans+=up[i]-down[i]+1;//比上限大，处在区间外，整个区间所有不符合的数字都是
            else if(n>=down[i])ans+=n-down[i]+1;//比下限大，处在区间之间，那么就是下限到当前位置不符合的数字都是
            else break;//所有不符合的数字的上下限都已经遍历完成了
        }
        cout<<ans<<endl;
    }
    return 0;
}

3. 参考答案

#include<bits/stdc++.h>
using namespace std;
int t,n;
int up[]={49,499,4999,49999,49999,499999,4999999,4999999};//所有的区间上限
int down[]={45,445,4445,44445,444445,4444445,44444445,444444445};//所有的区间下限
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=0;i<8;i++){
            if(n>=up[i])ans+=up[i]-down[i]+1;//比上限大，处在区间外，整个区间所有不符合的数字都是
            else if(n>=down[i])ans+=n-down[i]+1;//比下限大，处在区间之间，那么就是下限到当前位置不符合的数字都是
            else break;//所有不符合的数字的上下限都已经遍历完成了
        }
        cout<<ans<<endl;
    }
    return 0;
}

二、[USACO24DEC] Farmer John’s Cheese Block B

1. 审题

题目描述

Farmer John 有一块立方体形状的奶酪，它位于三维坐标空间中，从 $(0,0,0)$ 延伸至 $(N,N,N)$（$2\le N\le 1000$）。Farmer John 将对他的奶酪块执行一系列 $Q$（$1\le Q\le 2\cdot 10^5$）次更新操作。
对于每次更新操作，FJ 将从整数坐标 $(x,y,z)$ 到 $(x+1,y+1,z+1)$ 处切割出一个 $1\times 1\times 1$ 的奶酪块，其中 $0\le x,y,z<N$。输入保证在 FJ 切割的位置上存在一个 $1\times 1\times 1$ 的奶酪块。由于 FJ 正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。
在每次更新后，输出 FJ 可以将一个 $1\times 1\times N$ 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 $[0,N]$。FJ 可以随意旋转砖块。

输入格式

输入的第一行包含 $N$ 和 $Q$。
以下 $Q$ 行包含 $x$，$y$ 和 $z$，为要切割的位置的坐标。

输出格式

在每次更新操作后，输出一个整数，为所求的方案数。

样例 1

输入

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

输出

0
0
1
2
5

提示

样例解释
在前三次更新操作后，$[0,1]\times [0,2]\times [0,1]$ 范围的 $1\times 2\times 1$ 砖块与剩余的奶酪不重叠，因此它贡献了答案。

测试点性质

• 测试点 1：样例。
• 测试点 2-4：$N\le 10$ 且 $Q\le 1000$。
• 测试点 5-7：$N\le 100$ 且 $Q\le 1000$。
• 测试点 8-16：没有额外限制。

2. 分析

使用三视图的方法，然后看哪些方格是完全空着的（即 $0$ 个奶酪块）。这就是所谓的"可以放一个砖块"。我们只需要开三个桶就可以了。

3. 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
int n,q,x,y,z,xy[MAXN][MAXN],xz[MAXN][MAXN],yz[MAXN][MAXN];//xy[],xz[],yz[]统计的是拿走的数量
int main(){
    cin>>n>>q;
    while(q--){
        int ans=0;
        cin>>x>>y>>z;
        if(++xy[x][y]==n)ans++;
        if(++xz[x][z]==n)ans++;
        if(++yz[y][z]==n)ans++;
        cout<<ans<<endl;
    }
    return 0;
}

三、[USACO24DEC] It’s Mooin’ Time B

题目描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个长度为 $N$（$3\le N\le 20000$）的小写字母字符串。一种哞叫一般地定义为子串 $c_i{c}_j{c}_j$，其中某字符 $c_i$ 之后紧跟着 $2$ 个某字符 $c_j$，且 $c_i\ne c_j$。根据 Farmer John 的说法，Bessie 哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 $F$（$1\le F\le N$）次，那可能就是 Bessie 发出的。
然而，Farmer John 的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。将可能的误差考虑在内，输出所有可能是 Bessie 发出的哞叫，按字典序顺序排序。

输入格式

输入的第一行包含 $N$ 和 $F$，表示字符串的长度以及 Bessie 的哞叫的频次下限。
第二行包含一个长度为 $N$ 的小写字母字符串，表示竞赛。

输出格式

输出可能是 Bessie 发出的哞叫的数量，以下是按字典序排序的哞叫列表。每行输出一种哞叫。

样例 1

输入

10 2
zzmoozzmoo

输出

1
moo

样例 2

输入

17 2
momoobaaaaaqqqcqq

输出

3
aqq
baa
cqq

样例 3

输入

3 1
ooo

输出

25 
aoo 
boo 
coo
doo 
eoo
foo 
goo 
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

提示

样例 1 解释
在这个样例中，任何字符变化都不会影响答案。唯一 Bessie 可能发出的哞叫是 $\mathtt{moo}$。
样例 2 解释
在这个样例中，位置 $8$（从零开始索引）的 $\mathtt{a}$ 可能是由 $\mathtt{b}$ 损坏导致的，这使得 $\mathtt{baa}$ 成为一种 Bessie 发出两次的可能的哞叫。此外，位置 $11$ 的 $\mathtt{q}$ 可能是由 $\mathtt{c}$ 损坏导致的，这使得 $\mathtt{cqq}$ 成为一种 Bessie 可能的哞叫。$\mathtt{aqq}$ 可以通过将 $\mathtt{c}$ 换成 $\mathtt{a}$ 来达到。
测试点性质

• 测试点 1-3：样例。
• 测试点 4-8：$N\le 100$。
• 测试点 9-13：没有额外限制。

2. 分析

枚举所有可能的叫声 $t$（形如 $xyy$），判断 $t$ 是否只在修改一个字符的情况下，出现 $f$ 次叫声。

2.1 暴力枚举

枚举 $26^2$ 个可能的叫声，再枚举 $s$ 所有排列可能的字符串，然后看 $t$ 是否在里面出现 $f$ 次。只要一种 $s$ 满足，那么 $t$ 就可以输出。
时间复杂度 $O(26^2\cdot 3n^2)$，可以过任务 1。

#include<bits/stdc++.h>
using namespace std;
int n,f,
string s;
vector<string>ans;
bool check(string &s,string &t){
    int p=0,cnt=0;
    while(p!=-1){
        p=s.find(t,p);
        cnt++;
        p++;
    }
    if(cnt>=f)return 1;
    return 0;
}
int main(){
    cin>>n>>f>>s;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++){
            if(i==j)continue;
            char x='a'+i,y='a'+j;
            string t=t+x+y+y;
            bool flag=0;
            for(int k=0;k<s.size();k++){//枚举所有可能的s对比t
                char t=s[k];
                s[k]=x;
                if(check(s,t))flag=1;
                s[k]=y;
                if(check(s,t))flag=1;
                s[k]=t;
            }
            if(flag)ans.push_back(t);
        }
    cout<<ans.size()<<endl;
    for(auto v:ans)cout<<v<<endl;
    return 0;
}

2.2 优化

找有没有子串是只有一个位置未匹配的。

#include<bits/stdc++.h>
using namespace std;
int n,f,
string s;
vector<string>ans;
bool check(string &s,string &t){
    int p=0,cnt=0;
    while(p!=-1){
        p=s.find(t,p);
        cnt++;
        p++;
    }
    if(cnt>=f)return 1;
    return 0;
}
int main(){
    cin>>n>>f>>s;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++){
            if(i==j)continue;
            char x='a'+i,y='a'+j;
            string t=t+x+y+y;
            int cnt=0;
            vector<bool>st(n+5,0);
            for(int k=0;k+2<s.size();k++){
                int c=0;
                if(s[k]==x)c++;
                if(s[k+1]==y)c++;
                if(s[k+2]==y)c++;
                if(c==3){
                    cnt++;
                    st[k]=st[k+1]=st[k+2]=1;
                }
            }
            int flag=0;
            for(int k=0;k<s.size();k++){
                //要修改的位置不能是叫声t所在的位置
                if(s[k]==x&&s[k+1]==y&&!st[k+2])flag=1;
                if(s[k]==x&&s[k+2]==y&&!st[k+1])flag=1;
                if(s[k+1]==y&&s[k+2]==y&&!st[k])flag=1;
            }
            cnt+=flag;
            if(cnt>=f)ans.push_back(t);
        }
    cout<<ans.size()<<endl;
    for(auto v:ans)cout<<v<<endl;
    return 0;
}

3. 参考答案

#include<bits/stdc++.h>
using namespace std;
int n,f,
string s;
vector<string>ans;
bool check(string &s,string &t){
    int p=0,cnt=0;
    while(p!=-1){
        p=s.find(t,p);
        cnt++;
        p++;
    }
    if(cnt>=f)return 1;
    return 0;
}
int main(){
    cin>>n>>f>>s;
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++){
            if(i==j)continue;
            char x='a'+i,y='a'+j;
            string t=t+x+y+y;
            int cnt=0;
            vector<bool>st(n+5,0);
            for(int k=0;k+2<s.size();k++){
                int c=0;
                if(s[k]==x)c++;
                if(s[k+1]==y)c++;
                if(s[k+2]==y)c++;
                if(c==3){
                    cnt++;
                    st[k]=st[k+1]=st[k+2]=1;
                }
            }
            int flag=0;
            for(int k=0;k<s.size();k++){
                //要修改的位置不能是叫声t所在的位置
                if(s[k]==x&&s[k+1]==y&&!st[k+2])flag=1;
                if(s[k]==x&&s[k+2]==y&&!st[k+1])flag=1;
                if(s[k+1]==y&&s[k+2]==y&&!st[k])flag=1;
            }
            cnt+=flag;
            if(cnt>=f)ans.push_back(t);
        }
    cout<<ans.size()<<endl;
    for(auto v:ans)cout<<v<<endl;
    return 0;
}