蓝桥杯练习 Day2题解 - dblank

蓝桥杯练习 Day2题解

作者为萌萌哒的灿灿

A - Prime Path

题意: 给出两个四位的素数n, m,每次可以变动n中的一位数,且要求变动后新得到的数字也是4位的素数,求最少变动多少次可以得到m

思路:

可以用bfs来解决这道题。初始把n入队,每次从队列中取出一个数字a,求出以a为基础所有符合变动要求的数字,入队,且记录得到此数字经过多少次变动,最后即可得到答案

代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 10000000;

int d[10000];
bool prime(int n)
{
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

void bfs(int n, int m)
{
    queue <int> que;
    fill(d, d + 10000, INF);
    que.push(n);
    d[n] = 0;

    while(! que.empty())
    {
        int p = que.front(); que.pop();

        if(p == m)
        {
            printf("%d\n", d[p]); return;
        }

        int a, b;
        a = p % 1000;
        for(int i = 1; i <= 9; i++)//变动千位数,注意千位数字不能为0
            if(prime(i*1000+a) && d[i*1000+a] == INF)
            {
                d[i*1000+a] = d[p] + 1;
                que.push(i * 1000 + a);
            }

        a = p / 1000, b = p % 100;
        for(int i = 0; i <= 9; i++) //变动百位数,以下同
            if(prime(a*1000+i*100+b) && d[a*1000+i*100+b] == INF)
            {
                d[a*1000+i*100+b] = d[p] + 1;
                que.push(a * 1000 + i * 100 + b);
            }

        a = p / 100, b = p % 10;
        for(int i = 0; i <= 9; i++)
            if(prime(a*100+i*10+b) && d[a*100+i*10+b] == INF)
            {
                d[a*100+i*10+b] = d[p] + 1;
                que.push(a * 100 + i * 10 + b);
            }
        a = p / 10;
        for(int i = 0; i <= 9; i++)
            if(prime(a*10+i) && d[a*10+i] == INF)
            {
                d[a*10+i] = d[p] + 1;
                que.push(a*10+i);
            }
    }
}
int main()
{
    int t, n, m;

    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        bfs(n, m);
    }
    return 0;
}

B - Red and Black

题意:在n*m的地图中,'.'代表黑瓷砖,'#'代表红瓷砖,'@'代表起点且是黑瓷砖,可以从起点向上下左右四个方向走,但不能走红瓷砖,问最多能走多少块黑瓷砖

思路:dfs或者bfs搜索一遍,对能到达的地方做标记,最后统计标记的个数即可

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

using namespace std;

const int N = 30;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
char mpa[N][N];
int n, m, cnt;

void dfs(int x, int y)
{
    mpa[x][y] = '#';
    cnt++;
    for(int i = 0; i < 4; i++)
    {
        int nx = dx[i] + x, ny = dy[i] + y;
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && mpa[nx][ny] != '#')
            dfs(nx, ny);
    }
}

int main()
{
    while(scanf("%d%d", &m, &n), n || m)
    {
        int x, y;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", mpa[i]);
            for(int j = 0; mpa[i][j]; j++)
                if(mpa[i][j] == '@') x = i, y = j;
        }
        cnt = 0;
        dfs(x, y);
        printf("%d\n", cnt);
    }
    return 0;
}

C - 进制转换

题意:

输入一个十进制数N,将它转换成R进制数输出。

思路:直接模拟就好了

代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
char a[N]="0123456789ABCDEF";

void work(int n,int r,int f)
{
    char str[N];
    int len = 0;
    memset(str, 0, sizeof str);
    while(n)
        str[len++] = a[n%r], n /= r;
    reverse(str, str+len);//字符串倒置

    if(f == -1) printf("-");
    printf("%s\n", str);
}
int main()
{
    int n, r;
    while(~scanf("%d%d", &n, &r))
    {
        if(n < 0) work(-n, r, -1);
        else work(n, r, 1);
    }
    return 0;
}

D - 分数矩阵

题意:求矩阵的和

思路:从主对角线开始(不包括主对角线),对于每一个斜线,可以发现元素个数是依次递减的,可以计算出这条斜线上的和,再考虑到关于主对角线对称的还有一条相同的斜线,故把之前的和乘以2。最后求出总和即可

代码:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;

    while(scanf("%d", &n), n != 0)
    {
        double sum = n;
        int k = 1;
        for(int i = n - 1; i >= 1; i--)
            sum += 2 * 1.0 * i / ++k;
        printf("%.2f\n", sum);
    }
    return 0;
}

E - Prime Ring Problem

题意:给出一个n,要求用从1到n这n个数字组成一个环,以1为起点,且相邻数字的和为素数。求出满足条件的所有环,首先按顺时针输出满足条件的所有环,然后按逆时针输出满足条件的所有环

思路:dfs直接搜索,每次判断一下相邻数字的和是否为素数即可

代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int cas = 0;
int arr[N];
bool vis[N];

bool check(int m)
{
    if(m == 2 || m == 3 || m == 5 || m == 7 || m == 11 || m == 13 || m == 17 || m == 19) return true;
    else if(m == 23 || m == 29 || m == 31 || m == 37 || m == 41) return true;
    else return false;
}

void dfs(int cnt, int n)
{
    if(cnt == n+1 && check(arr[1] + arr[cnt-1]))
    {
        for(int i = 1; i <= cnt-1; i++)
            printf("%d%c", arr[i], i == cnt-1 ? '\n' : ' ');
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(! vis[i])
        {
            arr[cnt] = i;
            vis[i] = true;
            if(cnt != 1)//不是第一个数字,判断和它之前的数字和是否为素数
            {
                if(check(arr[cnt] + arr[cnt-1])) dfs(cnt+1, n);
            }
            else dfs(cnt+1, n);//第一个数字不用判断和是否为素数
            vis[i] = false;
        }
        if(cnt == 1) return;
    }
}

int main()
{
    int n;
    while(~ scanf("%d", &n))
    {
        memset(vis, 0, sizeof vis);
        printf("Case %d:\n", ++cas);
        dfs(1, n);
        printf("\n");
    }
    return 0;
}

F - 猜数字

题意:中文题,大概不用复述了

思路:已知答案是4位数,不到10000个,故可以直接枚举所有4位数字,判断满足所有条件的数字是否恰好只有一个,若恰好有一个,则输出,否则输出"Not sure"

代码:


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

const int N = 110;

int a[N], b[N], c[N];

void solve(int arr[], int n)
{
    for(int i = 0; i < 4; i++) arr[i] = n % 10, n /= 10;
    reverse(arr, arr + 4);
}
bool work(int t, int n)
{
    int arr[4], brr[4], numa[10], numb[10];
    solve(arr, t);
    for(int i = 0; i < n; i++)
    {
        solve(brr, a[i]);
        int t1 = 0, t2 = 0;
        memset(numa, 0, sizeof numa);
        memset(numb, 0, sizeof numb);
        for(int j = 0; j < 4; j++) numa[arr[j]]++;
        for(int j = 0; j < 4; j++) numb[brr[j]]++;
        for(int j = 0; j <= 9; j++) t1 += min(numa[j], numb[j]);
        for(int j = 0; j < 4; j++)
            if(arr[j] == brr[j]) t2++;
        if(t1 != b[i] || t2 != c[i]) return false;
    }
    return true;
}
int main()
{
    int n;
    while(scanf("%d", &n), n)
    {
        for(int i = 0; i < n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
        int num = 0, res;
        for(int i = 0; i <= 9999; i++)
        {
            if(work(i, n)) num++, res = i;
            if(num > 1) break;
        }
        if(num == 1) printf("%d\n", res);
        else printf("Not sure\n");
    }
    return 0;
}

G - Subset Sums

题意:给出一个集合S,求S所有的子集和落在区间[A,B]的个数

思路:

直接枚举所有子集和的复杂度是O(2^n),肯定会超时,可以用折半枚举。首先计算出前(n/2)个元素所有的子集和(设为s1),再计算出剩余元素所有的子集和(设为s2),复杂度最大为O(2^17),之后,考虑s1中的元素与s2中的元素相加落在[A,B]的个数,对于s1中的元素a,与a相加落在的[A,B]中的元素必然在区间[A-a,B-a]中,因此对s2进行排序后,可以用二分查找可以在log的复杂度内确定区间[A-a,B-a]中元素的个数,累加到答案中,这样枚举不会漏掉任何情况。最后输出答案即可

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 50, M = 1<<18;

ll arr[M+10], brr[M+10];

//计算集合所有子集的和,可以用dfs计算,也可以用如下的方法
int work(ll *arr, int *tm, int m, int len)
{
    int k = 0;
    for(int i = 0; i < (1<<m); i++)//m个元素的子集共有2^m个,可以从1循环到m, 用二进制位上的1或0代表取或不取某个元素
    {
        for(int j = 0; j < m; j++)
            if(i & (1<<j)) arr[k] += tm[len-1-j];//位运算判断i的左起第j个二进制位
        k++;
    }
    return k;
}

int main()
{
    int n;
    ll a, b;
    int tm[N];
    scanf("%d%lld%lld", &n, &a, &b);
    for(int i = 0; i < n; i++)
        scanf("%d", &tm[i]);

    int len = n/2;
    int k1 = work(arr, tm, len, len);
    int k2 = work(brr, tm, n-len, n);
    sort(arr, arr + k1);//对子集和的集合排序
    sort(brr, brr + k2);

    ll res = 0;

    for(int i = 0; i < k1; i++)
    {//upper_bound函数寻找第一个大于b-arr[i]的位置,lower_bound函数寻找第一个等于或大于a-arr[i]的位置,两者相减,就是在[A-a,B-a]中元素的个数
        res += upper_bound(brr, brr + k2, b-arr[i]) - lower_bound(brr, brr + k2, a-arr[i]);
    }
    printf("%lld\n", res);

    return 0;
}

H - Simple String Problem

题意:

给你一个串和两个整数n和k,n表示串的长度,k表示串只有前k个小写字母,问你两个不含相同元素的连续子串的长度的最大乘积。

思路:

二进制状态压缩,每位的状态表示第i个字母存在状态,n^2的时可以枚举出所有子串的状态和长度。然后每次与(1<<k - 1)异或就是不含相同的子串
状态。但是我开始想直接对每一种状态枚举他的子集和异或值,不过这太大了,肯定会超时,不过我们可以用dp[t]表示t状态所有子集的最大长度
先状态转移一下,最后之间遍历所有状态和其异或状态就可以更新出答案。

代码:

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<queue>  
#include<map>  
#include<vector>  
#include<cstring>  
#include<cmath>  
#define eps 1e-12  
using namespace std;  
typedef long long ll;  
const ll mo = 1000000007, N = 2*1e3+10;  
char s[N];  
int dp[(1<<16)+100];  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        int n, m;  
        scanf("%d%d", &n, &m);  
        scanf("%s", s);  
        memset(dp, 0, sizeof(dp));  
        for(int i = 0; i<n; i++)  
        {  
            int t = 0;  
            for(int j = i; j<n; j++)  
            {  
                t |= 1<<(s[j] - 'a');  
                dp[t] = max(dp[t], j - i + 1);  
            }  
        }  
        int s = 1<<m;  
        for(int i = 0; i<s; i++)  
        {  
            for(int j = 0; j<m; j++)  
            {  
                if((1<<j) & i)  
                    dp[i] = max(dp[i], dp[i^(1<<j)]);  
            }  
        }  
        int ans = 0;  
        for(int i = 0; i<s; i++)  
        {  
            ans = max(ans, dp[i]*dp[(s-1)^i]);  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}  

发表新评论