湖南师范大学新生赛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;
}