当前位置：首页 > news >正文

夏令营集训7月14日模拟赛④

news 2025/7/15 11:12:12

· 概况

共4题，2道AC（正确），1道MLE（内存超限），1道未完成

· 过程

本次比赛难度前期偏简单，T2与T4仅对于个人而言难度偏高，T3由于思考步骤繁琐导致思考时间过长而延迟完成，T4没有思路，故未完成

· 题目

1.开门 (door)

原分数：100

补题分数：100

情况：AC

题意：给两个字符串，判断是否相等，需注意忽略大小写和输出格式。

题解：判断两个字符串的长度是否相等，如果不相等的话，那么这两个字符串必然不相等。再判断长度相等的情况，从左到右判断每一个字符是否在忽略大小写之后一样，当有一个不一样的时候，那么这两个字符串就不相等。

AC代码：

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int main()
{while(cin>>s1>>s2){if(s1.size()!=s2.size()){cout<<"Different."<<endl;continue;}if(s1==s2){cout<<"Same."<<endl;continue;}bool flag=true;for(int i=0;i<s1.size();i++){if(s1[i]>='A'&&s1[i]<='Z'){s1[i]=(char)s1[i]+32;}if(s2[i]>='A'&&s2[i]<='Z'){s2[i]=(char)s2[i]+32;}if(s1[i]!=s2[i]){flag=false;break;}}if(flag)cout<<"Same."<<endl;else cout<<"Different."<<endl;}return 0;
}

2.数数 (number)

原分数：60➯70

补题分数：100

情况：WA➯TLE➯MLE

题意：给定 $n$ ，问从 $1$ 到 $n$ 里面有多少个Mars 数，即一个数为 $y^k$ 并且 $k > 1$ 。

题解：枚举 $k$ ，那么 $y$ 属于区间 $[2,\sqrt[n]{k}]$ 内，又因为 $2^{60}>10^{18}$ ，所以 $k$ 最高为 $60$ 。可这样枚举会重复的，可以用以下方法解决：如果一个Mars数字 $x$ 能被表示成多个 $y^k$ 的形式，那么我们只在枚举到最大的 $k$ 时计算一次，其他情况直接跳出。设 $f(k)$ 能被 $k$ 枚举到的Mars数的个数，则有： $f(k)=\left \lfloor \sqrt [k]{n} \right \rfloor-\sum_{k|t}{(f(t)-1)}$ ，其中（ $k|t$ 表示 $k$ 能整除 $t$ ），式子中减去 $1$ 是因为任何 $f(t)$ 都包含 $1$ 。最终结果为 $\textstyle \sum_{i=k}^{\left \lfloor {\log_{2}{n} } \right \rfloor}{(\mathrm{f(k)}\mathrm{-1+1})}$

，其中式子中减 $1$ 也是因为任何 $f(k)$ 都包含 $1$ 。最后的加 $1$ 是要在答案中算上 $1$ 。

未AC原因：枚举 $y$ ，那么枚举 $k$ （ $k\in \left \lfloor 2,\log_{y}{n} \right \rfloor$ ），但由于会出现重复，所以要保证不是Mars数，这样每个Mars数最多只被枚举到一次，而一共最多有个Mars数，所以时间复杂度为 $O(\sqrt n)$ ，在测试点8~10时会出现时间超限的情况。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const long double N=1e-8;
long long n,m,f[101],ans;
int main()
{cin>>n;m=(long long)(log2(n)+N);for(int i=m;i>1;i--){f[i]=(long long)(pow((long double)n,(long double)1/i)+N);for(int j=i+i;j<=m;j+=i)f[i]-=(f[j]-1);ans+=f[i]-1;}cout<<ans+1;
}

3.送礼 (gift)

原分数：60➯100

补题分数：100

情况：TLE➯AC

题意：给定 $n$ 和 $k$ ，还有一个长度为n的字符串，字符串包含'a'和'b'两种字符，最多可以进行 $k$ 次操作，操作是可以让一个'a'变成'b'，或者让一个'b'变成'a'，求最长的全'a'子串或者最长的全'b'子串的长度。

题解：如果 $l_1<l_2$ ，那么必有 $r_1\leqslant r_2$ 。因此，固定起点为 $l$ 时，如果最终遍历的终点是 $r$ ，那么固定起点为 $l+1$ 时，不必从头开始遍历，从 $r$ 开始遍历即可。 $l$ 和 $r$ 都最多移动 $n$ 次。

AC代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int solve(string s,int k,char c){int l=0,ans=0,cnt=0;for(int i=0;i<s.size();i++){if(s[i]!=c)cnt++;while(cnt>k){if(s[l]!=c)cnt--;l++;}ans=max(ans,i-l+1);}return ans;
}
int main()
{int n,k;string s;cin>>n>>k>>s;int mxa=solve(s,k,'a');int mxb=solve(s,k,'b');cout<<max(mxa,mxb)<<endl;return 0;
}

4.阅兵 (parade)

原分数：0

补题分数：100

情况：--

题意：给一个数字串，包含 $0$ 到 $9$ ，最多选择四个，把选择的相加，得到一个数字 $x$ ，再把 $x$ 上的每位数字相加，得到 $y$ ，如果说 $y=9$ 的话，国王就会开心，问我们有多少种方案可以让国王开心，结果对 $10^9+7$ 取模。

题解：本题中 $x$ 和 $y$ 均和顺序无关，则先统计每种数字的个数。预处理组合数， $c_j^i$ 即表示从 $i$ 个相同数字的士兵中选出 $j$ 个士兵的方案数。表示选了 $f[i][j]$ 个士兵，数字和为 $j$ 的方案数。

未AC原因：读不懂题目意思，但无从下手，剩下的时间全都在研究T2，没有多余时间，只能放弃此题。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[5][45],c[10005][5],cnt[15],t,n;
char s[10005];
int main()
{c[0][0]=1;for(int i=1;i<=10000;i++){c[i][0]=1;for(int j=1;j<5;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}cin>>t;while(t--){cin>>s;n=strlen(s); long long num,ans=0;memset(cnt,0,sizeof(cnt));memset(f,0,sizeof(f));for(int i=0;i<n;i++)cnt[s[i]-48]++;f[0][0]=1;for(int i=0;i<=9;i++){for(int j=3;j>=0;j--){for(int k=0;k<=36;k++){if(num=f[j][k]){for(int m=1;j+m<5;m++)f[j+m][k+i*m]=(num*c[cnt[i]][m]+f[j+m][k+i*m])%mod;}}}}for(int j=1;j<5;j++){for(int k=9;k<=36;k+=9)ans=(ans+f[j][k])%mod;}cout<<ans<<endl;}return 0;
}

· 总结

~~偶遇天赋型选手，拼尽全力无法战胜~~

查看全文

http://www.lryc.cn/news/588219.html