2022牛客寒假算法基础集训营2 签到题7题

1、C 小沙的杀球

• 如果你能够杀球但不杀球，虽然回复了体力，但你后续可能会没有机会继续杀球，并且杀球次数相同，那么回复的体力是相同的，所以在同等条件下，我们应该尽可能多的杀球。
• 不开long long 会爆炸

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL x, a, b;  cin>>x>>a>>b;
    string s;  cin>>s;
    LL cnt = 0;
    for(char ch : s){
        if(ch=='1' && x>=a){
            x -= a;  cnt++;
        }else{
            x += b;
        }
    }
    cout<<cnt<<"\n";
    return 0;
}


  

2、K-小沙的步伐

• 依照题意，如果是5就不动，不是5的话对非5以外的点添加一次次数的同时对5添加一次即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[200];
int main(){
    string s;  cin>>s;
    for(char ch : s){
        if(ch!='5')a[ch-'0']++, a[5]++;
    }
    for(int i = 1; i <= 9; i++){
        printf("%d ", a[i]);
    }
    return 0;
}


  

3、E-小沙的长路

• 对于最长路的最小值，我们考虑，如果图上有环，那么我们肯定能尽可能多的走环，这样的话我一定会比我不走环更长，所以我们构造的图要尽可能的没环。在没环的情况下，我们只会经过每个点各一次，所以总长度是n-1。
• 对于最长路的最大值，我们考虑尽可能的将每一条路都走遍，我们可以理解为对一个完全图进行删边，我们需要删尽可能少的边，从而使他能够从头走到尾，也就是构造出一个欧拉回路。
  又由欧拉回路的定义可知，我们需要将每个点的出入度控制为偶数即可组成欧拉回路，所以奇偶特判即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;  cin>>n;
    cout<<n-1<<" "<<(n%2==1? n*(n-1)/2 : n*(n-1)/2-n/2+1);
    return 0;
}


  

4、H-小沙的数数

• 由于在二进制拆位最后同位情况下如果存在不止一个一，那么异或之后的贡献一定小于我们的费用，所以我们要保证对于每一位的个数要么是0，要么是1，这样的话才能保证a[^]=a[+]
• 随后我们发现对于每一位来说，他们均不相互干扰，那么他们可能产生的情况便都是n种，所以我们只需要求二进制下m有多少个1，随后求𝑛^x次方即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
//LL ksm(LL a, LL b){if(b==0)return 1;LL ns=ksm(a,b>>1);ns=ns*ns%mod;if(b&1)ns=ns*a%mod;return ns;}
LL qmi(LL a, LL b){ a %= mod; LL res = 1;  for(; b; b>>=1, a=1ll*a*a%mod) if(b&1)res = res*a%mod; return res;}
int main(){
    LL n, m;  cin>>n>>m;
    cout<<qmi(n, __builtin_popcountll(m));
    return 0;
}


  

5、I-小沙的构造

• 针对奇数和偶数区分一下写法，还要注意边界的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s="<\\[{(!'*+-.08:=^_WTYUIOAHXVM|\"", t=">/]})!'*+-.08:=^_WTYUIOAHXVM|\"";
char ans[10010];
set<char>ft;
int main(){
    int n, m;  cin>>n>>m;
    if(m==1){while(n--)putchar('-'); return 0;}
    if(n%2==1) ans[n+1>>1]= 34, ft.insert(34);
    for(int i=1,ii=n,j=n/2,k=0; j; ++i,--ii,--j){
        if(ft.size()+1==m) k = max(k, 5);
        ans[i]=s[k], ans[ii]=t[k];
        ft.insert(s[k]), ft.insert(t[k]);
        if(ft.size() < m)++k;
        k%=30;
    }
    cout<<(ft.size()!=m?"-1":ans+1)<<"\n";
    return 0;
}


  

6、A-小沙的炉石

• 题解
  
  

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n, m;  cin>>n>>m;
    n = min(n, m+1);
    LL T;  cin>>T;
    while(T--){
        LL x;  cin>>x;
        LL mi = min(n, (LL)sqrt(x));
        if(x<=(mi+1)*mi/2+m*mi)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}


  

7、F-小沙的算数

• 由于运算是有优先级的，且我们发现每一个+会区分开一段区间，每个区间的值互不相互干扰，所以我们可以提前将每一个区间的信息整合到一个值里面，然后进行计算即可。
• 注意修改的数需要用逆元处理除法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10, mod = 1e9+7;
LL pows(LL a, LL x, LL p){if(x==0)return 1; LL t = pows(a, x>>1,p);if(x%2==0)return t*t%p;return t*t%p*a%p;}
LL inv(LL x, LL p){ return pows(x,p-2,p);}

LL a[maxn], f[maxn], id[maxn], it=1;

int main(){
    int n, q;  cin>>n>>q;
    string s;  cin>>s;  s="X"+s;
    for(int i = 1; i <= n; i++)cin>>a[i], f[i] = 1;
    //根据+号分块
    for(int i = 1; i <= n; i++){
        f[it] = f[it]*a[i]%mod;
        id[i] = it;
        if(s[i]=='+')it++;
    }
    //初始答案
    LL res = 0;
    for(int i = 1; i <= it; i++){
        res = (res+f[i])%mod;
    }
    //每次询问
    while(q--){
        int x, y;  cin>>x>>y;
        res = (res-f[id[x]]+mod)%mod;
        f[id[x]] = f[id[x]]*inv(a[x],mod)%mod;//WA3
        f[id[x]] = f[id[x]]*y%mod;
        a[x] = y;
        res = (res+f[id[x]])%mod;
        cout<<res<<"\n";
    }
    return 0;
}


  

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/123239744