第十届蓝桥杯题解

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

第一题 平方和

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}