第十届蓝桥杯题解

第十届蓝桥杯题解(个人向)

第一题 平方和

算$1 ​$到$2019​$中含有$2,0,1,9​$的数的平方和。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

bool check(int x){
    while(x){
        int t = x % 10;
        x /= 10;
        if(t == 1 || t == 0 || t == 9 || t == 2) return true;
    }
    return false;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    ll ans = 0;

    rep(i,1,2019+1){
        if(check(i)) ans += 1ll * i*i;
    }
    printf("%lld\n",ans);
    return 0;
}

第二题 数列求值

求类似斐波那契数列$f[i] = f[i-1] + f[i-2] + f[i-3]$ ，求$f[20190324]%10000$。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int a[10];
const int mod = 1e4;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    a[0] = 1;
    a[1] = 1;
    a[2] = 1;
    rep(i,3,20190324){
        a[3] = (a[0] + a[1] + a[2]) % mod;
        rep(j,0,3) a[j] = a[j+1];
    }
    printf("%d\n",a[2]);
    return 0;
}

第三题 最大降雨量

答案34.贪心即可。注意中位数的中位数

第四题 迷宫

第九题 糖果

题意

有n袋糖，里面有m种糖，每袋糖有k个，问至少取几包才能攒够所有种类的糖。

$n \leq 100;m,k\leq 20​$

题解

状压dp。我场上直接上暴力了。但是场下经过队友提示，发现就是个简单的状压dp。

因为他的$m$低于20所以我们可以用二进制位来表示。总的复杂度$O(2^m *n)$

状态转移方程 $dp[S|i] = min(dp[S|i],dp[i]+1)$

可能ac的代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m,k;
const int maxm = 21;
const int maxn = 110;
int dp[1<<maxm];
int sta[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    rep(i,0,n){
        rep(j,0,k){
            int x; scanf("%d",&x);
            dp[i] |= (1<<(x-1));
        }
    }
    rep(i,0,(1<<m)) dp[i] = INF;
    dp[0] = 0;
    for(int i = 0;i<(1<<m);i++){
        rep(j,0,n){
            dp[i|sta[j]] = min(dp[i]+1,dp[i|sta[j]]);
        }
    }
    printf("%d\n",dp[(1<<m)-1]!=INF?dp[(1<<m)-1]:-1);
    return 0;
}