牛客周赛 Round 12题解，欢迎加QQ号2426751794交流

小美种果树#

二分法，果树的成长公式：day* x+((day+2)/3) * y。也可以直接算。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

void my_ans(){
    long long i,j,ij,n,m,d,m1,k,t=0,k1,mi=1,ma=10000000000,mid;
    long long ans=0,x,y,z,mod=998244353;
    cin>>x>>y>>z;
    while(mi<ma){
        mid = (mi+ma)/2;
        if (mid*x+((mid+2)/3) * y >=z){
            ma = mid;
        }else{
            mi = mid+1;
        }
    }
    cout<<mi<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t=1;
    //scanf("%d",&t);
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

小美的子序列#

枚举，从第一个字符开始枚举。O(n* m)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

void my_ans(){
    long long i,j,ij,n,m,d,m1,k,t=0,k1,mi=1,ma=10000000000,mid;
    long long ans=0,x,y,z,mod=998244353;
    string s = "meituan";
    ij=0;
    cin>>n>>m;
    string s1;
    for(i=0;i<n;++i){
        cin>>s1;
        if (ij<s.size()){
            for(j=0;j<m;++j) if (s1[j] == s[ij]) break;
            if (j<m) ++ij;
        }
    }
    if (ij==s.size()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t=1;
    //scanf("%d",&t);
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

小美的游戏#

排序贪心，合并最大的k+1个数的乘积，O(nlgn)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

void my_ans(){
    long long i,j,ij,n,m,d,m1,k,t=0,k1,mi=1,ma=10000000000,mid;
    long long ans=0,x,y,z,mod=1000000007;
    cin>>n>>k;
    long long a[n];
    for(i=0;i<n;++i) cin>>a[i];
    sort(a,a+n);
    t=a[n-1];
    for(i=1;i<=k;++i){
        a[n-1] = (a[n-1]*a[n-1-i]) % mod;
        a[n-1-i] = 1;
    }
    for(i=0;i<n;++i) ans = (ans+a[i]) % mod;
    cout<<ans<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t=1;
    //scanf("%d",&t);
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

小美的区间异或和#

dp，二进制拆分，从左到右进行依次处理(i=1开始），则有:

1、a[i]的贡献次数为i，k[i] = k[i-1]+i；

2、a[i]与一组数的异或之和，实际就是把每个数拆成二进制之后，进行二进制位数关系比较,b[j]表示这组数进行二进制拆分之后第j位的数量,则有 (a[i]>>j) % 2 ==0, 则有ans[i]+=b[j]* (j<<2)；否则 ans[i]+=(k[i-1]-b[j])* (j<<2)；

3、ans[i] = ans[i]+ans[i-1]；

4、O(N* 30)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

void my_ans(){
    long long i,j,ij,n,m,k=0,t=1;
    long long ans=0,mod=1000000007;
    cin>>n;
    long long a[n+1];
    long long b[35],c[35];
    int d[35];
    for(i=0;i<35;++i){
        b[i] = 0;c[i] = (t<<i);
    }
    for(i=1;i<=n;++i){
        cin>>t;
        memset(d,0,sizeof(d));
        j=0;
        while(t>0){
            d[j] = t%2;t=t/2;++j;
        }
        a[i] = 0;
        if (i>1){
            a[i] = a[i-1];
            for(j=0;j<35;++j){
                if (d[j] ==0){
                    a[i] = (a[i]+b[j] * c[j]) % mod;
                }else{
                    a[i] = (a[i]+(k-b[j]) * c[j]) % mod;
                }
            } 
        }
        for(j=0;j<35;++j) b[j] = b[j] +d[j] * i;
        ans = (ans + a[i]) % mod;
        k=k+i;
    } 
    cout<<ans<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t=1;
    //scanf("%d",&t);
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")