湖南师范大学新生赛2-题解
A.简单题
思路：由于数据范围比较小，我们可以开个数组a[],用a[i]来统计i出现的次数。
代码：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int num[100005];//统计个数
int main()
{
int n;
memset(num,0,sizeof(num));
scanf("%d",&n);
int ans1=0,ans2=0;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
if(num[x]==0)ans1++;//新出现的正整数
num[x]++;
ans2=max(ans2,num[x]);//比较出现次数最多的
}
printf("%d %d\n",ans1,ans2);
//}
return 0;
}
B.数Hex
思路：对于给定的字符串，你只需要遍历一遍，并分别查看s[i],s[i+1],s[i+2]就可以判断是否包含Hex，同时统计次数。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char ch[3005];
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
scanf("%s",ch);
//printf("%s\n",ch);
int ans=0;
for(int i=0;i<n-2;){
if(ch[i]=='H'&&ch[i+1]=='e'&&ch[i+2]=='x'){//查看是否是Hex
ans++,i+=2;
}else i++;
}
printf("%d\n",ans);
}
return 0;
}
C.小摩托
思路：直接遍历上下左右的点，如果当前的悲伤值比答案小，就更新该点的悲伤值，最后输出终点的悲伤值就行。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long va[105][105],ans[105][105];
int n,m;
int dir[4][2]={1,0,-1,0,0,1,0,-1};//上、下、左、右
void dfs(int r,int c,long long w)
{
if(r<1||r>n||c<1||c>m)return;//如果超出边界就停止递归搜索
if(w<ans[r][c])ans[r][c]=w;//悲伤值比当前方块的答案小，就更新
else return;//这说明当前节点已经搜过，不能提供更优的路径不需要继续搜索。
for(int i=0;i<4;i++){
int x=r+dir[i][0],y=c+dir[i][1];
dfs(x,y,w+va[x][y]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans[i][j]=1e15;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%lld",&va[i][j]);//读入当前方块的悲伤值
}
}
dfs(1,1,va[1][1]);//开始搜索答案
printf("%lld\n",ans[n][m]);
return 0;
}
D.141877
思路：有个小结论就是1~n中，a的倍数的个数等于n/a。然后我们又发现个惊人的结论，141877=337x421,其中337和421都是质数。所以,我们先针对x为a~b中141877的倍数并符合条件的答案个数，然后针对y为c~d中141877的倍数并符合条件的个数，最后剪掉重复计算的那一部分就是第一阶段的答案。第二部我们针对141877的质数因子用同样的方法求出答案。最后统计两部分的答案之和就是题目的答案。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long cal(long long a,long long b)
{
return a/b;
}
long long n=141877,p1=337,p2=421;
long long findPairs(long long a, long long b, long long c, long long d) {
long long tmp1=cal(b,n)-cal(a-1,n),tmp2=cal(d,n)-cal(c-1,n);//统计a~b中141877的倍数的个数.......
long long ans=tmp1*(d-c+1)+tmp2*(b-a+1)-tmp1*tmp2;//分别计算并剪掉重复的。
ans+=(cal(b,p1)-cal(a-1,p1)-tmp1)*(cal(d,p2)-cal(c-1,p2)-tmp2);//同上，但由于141877的已经计算过了，所以要剪掉
ans+=(cal(b,p2)-cal(a-1,p2)-tmp1)*(cal(d,p1)-cal(c-1,p1)-tmp2);
return ans;
}
int main()
{
long long a,b,c,d;
int T;
scanf("%d",&T);
while(scanf("%lld%lld%lld%lld",&a,&b,&c,&d)!=EOF){//也可以用T来控制循环
printf("%lld\n",findPairs(a,b,c,d));
}
return 0;
}
E.找序列
思路：先去除掉找不出序列的情况，然后先给n个数都加上l，然后多余的部分从后往前尽可能的塞。
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5 + 10;
int n, s, l, r, a[Maxn];
void solve(){
scanf("%d %d %d %d", &n, &s, &l, &r);
if( 1ll*n*l > s || 1ll*n*r < s ) return void(puts("HexQwQ"));//找不大序列
int Sum = 0;
for(int i=1;i<=n;i++) a[i] = l, Sum += l;
for(int i=n;i>=1;i--)
{
if( Sum + r-l >= s ) {a[i] = s - Sum + l; break;}//加上多余的部分
else a[i] = r, Sum += r-l;//能加到上限就直接加到上限
}
for(int i=1;i<=n;i++) printf("%d ", a[i]);
puts("");
}
int main(){
int T;
scanf("%d",&T);
for(int _=1;_<=T;_++)
solve();
return 0;
}F.衣服都湿了怎么办
思路：经典二分题。我们先从l~r中判断mid((l+r)/2)是否可行，如果mid不行的话，就说明答案存在与mid+1~r中，反之就在l~mid中，通过逐步缩小搜索范围，直到找到答案。如何检查是否符合题目条件呢？我们已经假设了答案为mid，那么所有的衣服都可以自然烘干mid点湿度值，这样那些需要我们选择减少k点湿度值的衣服就和明显了，遍历一遍大于mid的求出需要选择几次烘干k点，最后与mid比较就行了。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long val[100005];
int n,k;
bool check(long long w)
{
long long tmp=0;
for(int i=0;i<n;i++){
if(val[i]-w>0){//不能自然烘干
tmp+=(val[i]-w+k-1)/k;//判断需要选择几次人工烘干，注意是向上取整
}
}
if(tmp>w)return false;//如果人工烘干的次数比时间要长，说明不符合条件
else return true;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%lld",&val[i]);
}
long long ans,l=0,r=10000000000000;//确定边界
while(l<=r){
long long mid=(l+r)/2;//取一个中间值
if(check(mid)){//检查是否符合条件
ans=mid;
r=mid-1;//去另一个区间寻找
}else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}
G.可见人数
思路：学习下欧拉函数。直接上csdn或博客园搜索欧拉函数。
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5+10;
int E[Maxn];
void euler(int n)
{
for(int i=2;i<n;i++){
if(!E[i])
for(int j=i;j<n;j+=i){
if(!E[j])E[j]=j;
E[j]=E[j]/i*(i-1);
}
}
}
int main(){
// freopen("7.in.txt","r",stdin);
// freopen("7.out.txt","w",stdout);
int t;
cin>>t;
euler(Maxn);
// t = 1;
while(t--){
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 1;i<=n-1;++i){
ans+=E[i];
}
ans*=2;
ans+=3;
if(n==1){printf("0\n");}
else printf("%d\n",ans);
}
return 0;
}
投递SHEIN等公司7个岗位 >