牛客小白月赛101（下）

tb的字符串问题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <stdio.h>
#include <string.h>
int main() {int n;scanf("%d", &n);getchar(); char a[1000001];int i = 0;for (int j = 0; j < n; j++) {a[i] = getchar();if (a[i] && (a[i] == 'c' && a[i - 1] == 'f' || a[i] == 'b' && a[i - 1] == 't')) {i -= 2;}i++;}while (i > 0 && (a[i - 1] == 'c' && a[i - 2] == 'f' || a[i - 1] == 'b' && a[i - 2] == 't')) {i -= 2;}printf("%d", i);return 0;
}

代码思路

1. 首先，读取输入的字符串长度 n。
2. 然后，通过循环逐个读取字符并存储到字符数组 a 中。
3. 在读取每个字符时，进行判断：如果当前字符与前一个字符组成了 fc或 tb 子串，就将下标 i 减 2，以模拟删除该子串。
4. 循环结束后，可能还存在最后剩余的不完整子串，需要再次进行判断和处理。
5. 最后，输出处理后字符串的长度 i。

tb的路径问题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include<stdio.h>
int main()
{int n;scanf("%d",&n);if(n==2)printf("2");else if(n%2==0&&n>2)printf("4");else if(n==1)printf("0");else if(n==3)printf("4");else if(n%2!=0&&n>=5)printf("6");return 0;
}

代码思路

基于对不同 n值的手动分类处理，但这并不是一个通用或高效的解决方案。下面是对代码逻辑的分析：

1. 当 n = 1时，起点和终点重合，因此不需要移动，输出 0。
2. 当 n = 2时，代码直接输出 2。这是因为从 (1,1) 到 (2,2) 需要两次移动：先水平或垂直移动一次，再移动一次到达目的地。
3. 当 n 是大于2的偶数时，代码输出 4。这里的想法可能是考虑到可以通过两次移动到达一个可以“传送”的位置，然后再通过两次移动到达终点。但是，这个假设没有充分考虑到可能存在的更短路径。
4. 当 n = 3 时，代码输出 4。这同样基于一种特定的情况，即从 (1,1) 到 (3,3) 可能需要四次移动。
5. 当 n 是大于等于5的奇数时，代码输出 6。这个逻辑也是基于特定情况的假设，认为至少需要六次移动才能到达终点。

对于任意的 n，最有效的策略通常是利用 n 的因数特性，特别是 n与其自身的最大公约数总是 n，这意味着可以直接从 (1,1) 通过“传送”到达 (n,n)，前提是找到一条路径使得中途能够访问值为 n 的格子。

tb的平方问题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include<bits/stdc++.h>
using namespace std;
int n,q,a[1005],sum[1005],ans[1005];
bool OK(int x)
{int tmp=sqrt(x);return tmp*tmp==x;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int s=sum[j]-sum[i-1];if(OK(s)){ans[i]++;ans[j+1]--;}}}for(int i=1;i<=n;i++){ans[i]+=ans[i-1];}while(q--){int x;cin>>x;cout<<ans[x]<<'\n';}return 0;
}

代码思路

1. 输入与初始化

   • 首先读取输入的整数n和q，分别表示序列的长度和查询的次数。
   • 定义三个数组a、sum和ans，其中a用于存储原始序列，sum用于存储前缀和，ans用于存储每个位置作为起点的满足条件的子区间数量。
   • 通过ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);来优化输入输出流的性能。

2. 计算前缀和：遍历原始序列a，对于每个位置i，将其元素值累加到前缀和数组sum中，即sum[i]=sum[i - 1]+a[i]。这样，sum[i]就表示序列前i个元素之和。

3. 统计满足条件的子区间数量

   • 使用两层循环遍历所有可能的子区间。
   • 外层循环遍历每个可能的子区间起点i，内层循环遍历从i到序列末尾的每个位置j，作为子区间的终点。
   • 对于每个子区间[i, j]，计算其元素之和s = sum[j]-sum[i - 1]。
   • 调用OK函数判断s是否为完全平方数。如果是，说明该子区间满足条件，则增加起点位置i的统计值ans[i]++，同时减少终点位置下一个位置的统计值ans[j + 1]--。这样做的目的是在后面的遍历中能够正确地累计每个位置作为起点的满足条件的子区间数量。

4. 累计满足条件子区间数量：再次遍历数组ans，对于每个位置i，将其值累加上前一个位置的值，即ans[i]+=ans[i - 1]。这样，ans[i]就表示以位置i为起点的满足条件的子区间数量。

5. 处理查询：循环q次，每次读取一个查询下标x。输出ans[x]，即以下标x为起点的满足条件的子区间数量。