标签: 蓝桥杯 - CheaSim Blog
发表更新蓝桥杯4 分钟读完 (大约543个字)

第十届蓝桥杯题解

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

第一题 平方和

算$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;
}
发表更新蓝桥杯3 分钟读完 (大约509个字)

蓝桥杯历届题目

还有6天蓝桥杯了

开始刷历届练习题了。

小计算器

题意

实现一个直接的计算器。没有四则运算规则优先级。并且能够有进制转换

题解

数字转换字符串的时候,$0$是关键点。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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;
typedef  long long ull;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxchar = 100;
const int maxn = 100;
char s[maxn];
int k;
char ans[maxn];
void solve(ull x){
    memset(ans,0,sizeof(ans));
    ull t = k;
    int cnt = 0;
    if(x==0) ans[0] = '0';
    while(x){
        if(x%t < 10){
            ans[cnt++] = x%t+'0';
        }else{
            ans[cnt++] = x%t+'A'-10;
        }
        x/=t;
    }
    int len = strlen(ans);
    rep(i,0,len/2) swap(ans[i],ans[len-1-i]);
}
char tt[maxn];
ull real_num(){
    int len = strlen(tt);
    ull t = 0;
    ull cnt = 1;
    per(i,0,len){
        if(tt[i]>='A' && tt[i]<='Z'){
            t += cnt * (tt[i] - 'A' +10);
        }else{
            t += cnt * (tt[i] - '0');
        }
        cnt*= k;
    }
    return t;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    cin>>n;
    ull now = 0;
    int sign = 0;
    k = 10;
    bool init = false;
    rep(i,0,n){
        cin>>s;
        if(s[0] == 'C' && s[1] == 'L') {
            now = 0;
            init = true;
        }else if(s[0] == 'N'){
            cin>>tt;
            ull temp = real_num();
            if(init){
                now = temp;
                init = false;
                continue;
            }
            if(sign == 1) now += temp;
            else if(sign == 2) now -= temp;
            else if(sign == 3) now *= temp;
            else if(sign == 4) now /= temp;
            else now %= temp;
        }else if(s[0] == 'A'){
            sign = 1;
        }else if(s[0] == 'S'){
            sign = 2;
        }else if(s[0] == 'M' && s[1] == 'U'){
            sign = 3;
        }else if(s[0] == 'D'){
            sign = 4;
        }else if(s[0] == 'M'){
            sign = 5;
        }else if(s[0] == 'E'){
            solve(now);
            cout<<ans<<'\n';
        }else{
            cin>>k;
        }
    }
    return 0;
}

合根植物

题意

并查集

数组开小了。

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
37
38
#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

const int maxn = 2e3+10;
int fa[maxn*maxn];
int Find(int x){
    if(fa[x] == x) return x;
    else return fa[x] = Find(fa[x]);
}
int Union(int x,int y){
    int i = Find(x);int j = Find(y);
    if(i!=j) fa[j] = i;
}
int n,m;
int k;
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,n*m+1) fa[i] = i;
    rep(i,0,k){
        int x,y; scanf("%d%d",&x,&y);
        Union(x,y);
    }
    int ans = 0;
    rep(i,1,n*m+1) if(fa[i] == i) ans++;
    printf("%d\n",ans);
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×