喵哈哈村的魔法考试 Round #5 (Div.2) 题解

老规矩有问题直接联系我：475517977@qq.com

A

直接暴力的for一遍，统计连续的有多少个就好了。模拟题。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k;
    while(cin>>k){
        string s;
        cin>>s;
        int cnt = 1;
        int mx = 1;
        for(int i=1;i<s.size();i++){
            if(s[i]==s[i-1]){
                cnt++;
                mx=max(cnt,mx);
            }else
                cnt=1;
        }
        if(mx>=k){
            cout<<"Lose"<<endl;
        }else{
            cout<<"Win"<<endl;
        }
    }
}

B

这道题是考察dfs的一道题目，dfs(int now,int a,int b)表示现在这个数是now,用了a个4，b个7，然后做下去就好了。

注意1000000000这个数据，答案会超过1e9的哦

#include<bits/stdc++.h>
using namespace std;

long long n;
int cnt = 0;
long long ten[13];
map<long long,int>H;
long long ans = 0;
void solve(int a,int b,long long c,int len){
    if(H[c])return;
    if(c>10000000000LL)return;
    if(a==b&&c>=n)ans=min(ans,c);
    H[c]=1;
    solve(a+1,b,c+ten[len]*4,len+1);
    solve(a,b+1,c+ten[len]*7,len+1);
}
void solve(){
    H.clear();
    cnt = 0;
    ans = 10000000000LL;
    solve(0,0,0,0);
    cout<<ans<<endl;
}
int main(){
    ten[0]=1;
    for(int i=1;i<13;i++)
        ten[i]=ten[i-1]*10LL;
    while(cin>>n)
        solve();
}

C

感觉上非常麻烦的一道题，实际上你非常非常小的枚举每一个数就好了嘛(x

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<string>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL __int64
#define MAX 100010
#include<iostream>
using namespace std;

double a ,b ,c ,d ,l ,r;

double cal(double x)
{
    return fabs(a * x * x *x + b * x * x + c * x + d);
}

int main()
{
    while(cin>>a>>b>>c>>d>>l>>r)
    {
        double re = l;
        double ans = cal(l);
        while(r - re >= 0.01)
        {
            ans = max(ans,cal(re));
            re += 0.01;
        }
        ans = max(ans,cal(r));
        printf("%.2f
",ans);
    }
    return 0;
}

D

简单来说，你首先把素数全部筛选出来，然后开始for素数，因为素数的数量少于n嘛，至少，大概在(logn)级别的。

然后你就可以枚举两个素数，然后再check第三个数是不是素数就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 10000;

int np, pri[maxn+5], vis[maxn+5];

void prime_table(int n) {

    np = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (vis[i])
            continue;

        pri[np++] = i;
        for (int j = i * i; j <= n; j += i)
            vis[j] = 1;
    }
}

int main () {
    int n;
    prime_table(maxn);
    while (scanf("%d", &n) == 1) {
        int ans = 0;
        for (int i = 0; i < np; i++) {
            for (int j = i; j < np; j++) {
                if (pri[i] + pri[j] >= n)
                    break;
                int t = n - pri[i] - pri[j];

                if (vis[t] == 0 && t >= pri[j])
                    ans++;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

E

原题 hdu 5106，最暴力的方法，就是强行数位dp莽过去就好了。

但是这道题，其实只需要枚举某个二进制数和Ｒ第一个１不同的位置就行了。因为如果Ｒ某个位置的１变成了０，那么以后０１就随便取变成了组合数的问题。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
#define MX 1005
#define MOD 1000000007

LL C[MX][MX], bit[MX];
int N;
char R[MX];

void init() {
    int i, j;
    bit[0] = 1LL;
    for (i = 1; i < MX; i ++) {
        bit[i] = 2 * bit[i - 1] % MOD;
    }
    C[0][0] = 1;
    for (i = 1; i < MX; i ++) {
        C[i][0] = C[i][i] = 1;
        for (j = 1; j < i; j ++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

int main(){
    init();

    int Tcase, i, one;
    while (scanf("%d %s", &N, R) == 2) {
        int len = strlen(R);
        int rlt = 0;

        long long B = 0;
        for (i = 0; i < len && N >= 0; i ++) {
            if (R[i] == '1') {
                if (N <= len - i - 1) {

                    if (N) rlt = (rlt +  (long long) (bit[len - i - 1] - 1) * C[len - i - 2][N - 1] % MOD) % MOD;
                    rlt = (rlt + B * C[len - i - 1][N] % MOD) % MOD;
                    B += bit[len - i - 1];
                    B %= MOD;
                    N --;
                }
            }
        }
        if (rlt < 0) rlt += MOD;
        printf("%d
", rlt);
    }

}