CSP-J第二次模拟赛补题报告-S06731

小葵花妈妈课堂开课啦！

 老师节目换了

老师，开头节目奉上！换了，请看这里！一定要看！求求了。（点请看这里）

​

本次模拟赛情况，一题对3个样例，2,3题错，4题对3个样例

比赛过程中，看了1-4题，觉得第二题简单，先做了第二题，思路是用循环枚举从最小的数到最大的数，依次判断每一个数是否符合条件，我看考完了评测记录大部分都是超时，在我的预期之内，但是那几个答案错误是真的没想到，然后看了第三题，一点思路没有，留在后面做，最后蒙了个奇数次输出ok，偶数次输出no（我真是个天才），第四题属于我罕见有把握的题，但是但是只对了3组样例，6；第一题写了个算是半个暴力吧，样例过了，过了3组测试，就这样了。

第一题：(smooth.cpp/c）  平整

1.1 问题描述

小可喜欢平整的数列，做题时遇到数列就会去研究一下是否平整。

平整的含义为：对于数列中的所有数字 a​i​​ ，会存在至少一个数字 x，满足x−a​i​​∣≤1。

请聪明的你帮助小可计算一下，对于给定的数列，存在多少 x 满足题意。

1.2 输入格式

第一行一个数字 T ，表示多组输入。

对于每组数据，第一行输入一个整数 N，表示数列长度，第二行输入 N 个数字，表示一个数列。

1.3 输出格式

对于每组数据，输出一行，表示有多少满足条件的 x。

这题我看了没啥思路，我推不出来，只好打了个暴力，得了30分

推理：

这一道题是推规律的题，我们举几个例子

1、1 2 3 4 5 6，这个式子找不到一个x满足

2、1 2 1 2 1 2 1，这个式子有两个x可以满足，分别是1和2

3、1 2 3 3 2 1，这个式子有一个x可以满足，是2

4、1 1 1 1 1 1 ，这个式子有三个x可以满足，是0,2,1

得出规律：用数列的最大值和最小值减出来就是答案，当差的绝对值为0时，有3种可能；当差的绝对值为1时，有2种可能；当差的绝对值为2时，有1种可能；

综合上，代码实现如下

#include
using namespace std;
typedef long long ll;
void solve(){
ll n;
cin>>n;
ll a[n];
for(ll i=0;i>a[i];
sort(a,a+n);
ll delta=a[n-1]-a[0];
if(delta>2){
cout<<"0\n";
return;
}
if(delta==2){
cout<<"1\n";
return;
}
if(delta==1){
cout<<"2\n";
return ;
}
if(!delta){
cout<<"3\n";
return ;
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int
_
;
cin>>
_
;
while(_--){
solve();
}
}

第二题：(statistic.cpp/c)
字符串统计

2.1 问题描述
一个序列由 N个字符串构成，然后查询M次。
对于每一次查询，我们给定两个数值 l，r，表示查询序列下标在l，r 范围内且以元音字符（ a,e,i,o,u ）开头和结尾的的字符串数量 ，然后将 cnt打印，每个打印占一行。
2.2 输入格式
第一行输入一个整数 ，含义如题所示
第二行输入 N个字符串，以空格隔开，构成序列
第三行输入一个 M，表示进行 M次查询
然后输入M，每行输入两个整数 l，r，以空格隔开
2.3 输出格式
对于每组查询进行一个输出，输出对应的答案（若不存在符合要求的字符串，则输出0 表示没有）

这个题我一开始的思路是定义string数组，要对于每次输入，循环遍历每一个string，找到第0下标和size-1下标都符合的字符串，然后cnt++，样例对了我记得好像这题是对3组还是错误来着，反正那几个时间超限朕是已经想到了，因为我写的也算暴力，每次都要循环。

这题目其实是前缀和的题目，我们用一个计数数组，再输入询问之前，我们需要先把每一个字符串是否是头尾元音的状况记录下来，再建一个数组专门计算前缀和，计算i之前有多少个字符串满足要求，最后输出cnt[r]-cnt[l]即可；

给你们看看我的代码（我不是不要脸）

//字符串统计
#include
#include 
using namespace std;
int main(){freopen("statistic.in","r",stdin);freopen("statistic.out","w",stdout);string s[100005];int n,m;cin>>n;for(int i=0;i>s[i];}cin>>m;int l,r;int cnt=0;for(int i=0;i0;scanf("%d%d",&l,&r);for(int j=l;j<=r;j++){if((s[j][0]=='a'||s[j][0]=='e'||s[j][0]=='i'||s[j][0]=='o'||s[j][0]=='u')&&(s[j][s[j].size()-1]=='a'||s[j][s[j].size()-1]=='e'||s[j][s[j].size()-1]=='i'||s[j][s[j].size()-1]=='o'||s[j][s[j].size()-1]=='u')){cnt++;}}printf("%d\n",cnt);}fclose(stdin);fclose(stdout);return 0;
} 

再来看看正解代码：

#include 
#include 
using namespace std;
bool isVowelLetter(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
bool isVowelString(string word) {return isVowelLetter(word[0]) && isVowelLetter(word[word.length() - 1]);
}
vector<int> vowelStrings(vector& words, vectorint>>& queries) {int n = words.size();vector<int> prefixSums(n + 1, 0);for (int i = 0; i < n; i++) {int value = (isVowelString(words[i])) ? 1 : 0;prefixSums[i + 1] = prefixSums[i] + value;}int q = queries.size();vector<int> ans(q, 0);for (int i = 0; i < q; i++) {int start = queries[i][0], end = queries[i][1];ans[i] = prefixSums[end + 1] - prefixSums[start];}return ans;
}
signed main() {int n;cin >> n;vector words(n);for (int i = 0; i < n; i++) {cin >> words[i];}int m;cin >> m;vectorint>> queries(m, vector<int>(2));for (int i = 0; i < m; i++) {cin >> queries[i][0] >> queries[i][1];}vector<int> result = vowelStrings(words, queries);for (int i = 0; i < m; i++) {cout << result[i] << endl;}return 0;
}

第三题：(reach.cpp/c)
从a到b

3.1 问题描述
小可最近的算法水平突飞猛进，他已经不满足仅仅做算法题，他要出一个题，并想用这个题难倒你！
给定两个整数a 和 b（ 仅由0 和 1构成）， 两个整数的长度均为n ，现在想把整数a 转变成整数 b，请问仅进行下列操作（不限次数）的情况下能否完成？
操作：选择两个不同的下标 i,j，然后将a[i] 修改为a[i]|a[j]（按位或操作），将a[j] 修改为a[i]^a[j]
（异或操作）
你会被这道题难道吗？
3.2 输入格式
第一行一个 表示多组输入。
对于每组数据第一行输入一个 ，表示整数长度，第二行输入整数 ，第三行输入整数
3.3 输出格式
每组数据输出占一行，若可以将 变成 则输出 OK ，否则输出 No 。

这个题目我赛中一直没有思路，最后就是写了个蒙的。

这道题目其实是可以分类讨论的，比如以下几个情况：

1、a==b,两个字符串相等，一定可以互相转换

2、如果b全部是0，因为a现在不等于b，所以a无论如何都会有至少一个1，我们对1进行按位或操作，不可能变成0，所以一定不行

3、如果b不是全为0，则b至少有一个1，这时候我们分类讨论：

4、如果a全是0，同样，对0或，不可能得到1，所以不行

5、如果a不全为0，则至少有一个1，a一定可以变为b，就是ok

对于以上特别判断，代码如下：

if(a == b) cout << "OK" << endl;
else
{
if(a.find("1") != a.npos && b.find("1") != b.npos) cout << "OK" << endl;
else cout << "No" << endl;
}

综合一下，代码如下：

#include 
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1e5 + 10, M = N, mod = 1e9 + 7;
using namespace std;
int main() {int T;cin >> T;while(T --) {string a, b;int n;cin >> n >> a >> b;if(a == b) cout << "OK" << endl;else {if(a.find("1") != a.npos && b.find("1") != b.npos) cout << "OK" << endl;else cout << "No" << endl;}}return 0;
}

第四题：粉刷栅栏

4.1 问题描述
达达非常喜欢花，他每天都在精心照料自己的小花园。达达的花园已经很漂亮了，可是颜色单调的栅栏显得
花园十分老气，达达想用颜料把栅栏粉刷一下。他想知道把栅栏粉刷成想要的颜色，最少需要几次？
注意：达达比较懒，所以他每次粉刷，都会把连续的若干栅栏涂成一个颜色。
4.2 输入格式
输入一行，一个字符串，表示想把栅栏涂成的最终颜色
字符串都是由大写字母组成，不同的字母表示不同的颜色
4.3 输出格式
输出一行一个整数，表示达达完成粉刷所需的最少涂色次数

这道题我的思路是建一个桶，标记每一个颜色是否被遍历过，初始化否，然后输入string，遍历每一位，如果这一位和上一位不一样而且这个字母对应的桶为否，那么这个颜色就需要刷，cnt++，最后输出cnt。

给大家看看我的代码（超级不要脸）

//粉刷栅栏
#include
#include 
using namespace std;
bool cnt[26]={0};
int main(){freopen("color.in","r",stdin);freopen("color.out","w",stdout);string s;cin>>s;int ans=0;cnt[s[0]-'A']=true;for(int i=1;i

#include
using namespace std;
int f[55][55];
string s;
int main(){memset(f,0x3f,sizeof(f));string s;cin>>s;int lens=s.size();//下标从一开始 //初始化，考虑：谁一定是最小的刷的次数，从i到i的次数一定是1 s=" "+s;for(int i=1;i<=lens;i++){f[i][i]=1;}for(int len=2;len<=lens;len++){for(int l=1;l+len-1<=lens;l++){int r=l+len-1;if(s[l]==s[r]) f[l][r]=min(f[l][r],f[l][r-1]);//枚举分割点，从i到j总共多少个分割点 for(int k=l;k

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！