[数据结构与算法]第十届蓝桥杯C++B组题解

A 平方序列

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int x, y;
    for (int i = 2020; i; i ++ )
    {
        x = i;
        int t = 2 * x * x - 2019 * 2019;
        y = sqrt(t);
        if (y * y == t)
            break;
    }
    
    cout << x + y << endl;
    return 0;
}

B 质数拆分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
const int N = 2022;
typedef long long LL;
vector<int> res;
LL f[N];

bool is_prime(int x)  // 判定质数
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    for (int i = 2; i <= 2019; i ++ )
        if (is_prime(i))
            res.push_back(i);
    
    f[0] = 1;
    for (int i = 0; i < res.size(); i ++ )
    {
        for (int j = 2019; j >= res[i]; j -- )
            f[j] += f[j - res[i]];
    }
    cout << f[2019] << endl;
    return 0;
}

C 拼接

// C拼接  找规律  然后dfs求解 
// 边界情况较多 分析较难
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10; 

long long res;
bool st[N][N];  //标记有无访问过 
vector<pair<int, int >> ans;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


void dfs(int x, int y)
{
    if (x == 7)  // x == 7 到达右边界 切割完毕 
    {
        res ++;
        return;
    }
    
    // 四个方向 搜索 
    for (int i = 0; i < 4; i ++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        //四个不合法判断条件依次是
        //当y=0时y不可加，否则必不合法（边上形成锯齿形） -- 会导致左部方块不连通 
        //已超出边界
        //在当前路径被访问过  -- 此时切割路径可能原路返回 或者 形成一个空心矩形导致部分方块划分不清 造成不连通 
        //走到了对角线上及其上方，无需继续下去：这等于说在中间挖了个洞
        // 注意了  不要照着平时dfs的向上 这里的向上是 x不变 y + 1
        // 照着数组坐标系向上会错误 数组坐标系形如迷宫的向上在这道题目里实际上是向左 
        if ( (y == 0 && i == 1) || yy < 0 || st[xx][yy] || xx <= yy)
            continue;
//        ans.push_back(make_pair(xx, yy));
        st[xx][yy] = true;
        dfs(xx, yy);
        st[xx][yy] = false;
//        ans.pop_back();
    } 
}



int main()
{
    // 本题 考察对称性 切出来 的右边的木块实际上是要关于对角线对称才可旋转拼接
    // 另外要保证左边方块内部连通  这是一个大坑点 
    // 从对角线出发切割  减少搜索量
    // 因为关于对角线堆成 所以模拟从对角线出发在右边区域内的切割切割
    // 对角线左部的切割线是关于 右部对称的 可以通过图片加强理解 
    for (int i = 1; i < 7; i ++)   
    {
        st[i][i] = true;
        dfs(i, i);
        st[i][i] = false;
    }
    
    // 没有深搜左下角和右上角  左下角只能向右切割  右上角直接切割完毕 、
    // 分别代表都是右边和都是左边  各一种切法 
    cout << res + 2 << endl;      
    return 0;
} 

D 求值

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

using namespace std;

int count(int x)
{
    int cnt = 1;
    for (int i = 2; i <= x / i; i ++ )
    {
        int s = 0;
        while (x % i == 0)
        {
            x /= i;
            s ++ ;
        }
        cnt *= 1 + s;
    }
    
    if (x > 1) cnt *= 2;
    return cnt;
}

int main()
{
    for (int i = 100; i; i ++ )
    {
        if (count(i) == 100)
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

E 路径计数

这道题官网答案有误，比赛时是按照206这个答案几分的

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;

using namespace std;
const int N = 10;

LL ans;
bool st[N][N];
int n = 6;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool check(int x)
{
    return x > 1 && x <= 11;
}

void dfs(int x, int y, int step)
{
    if (x == 0 && y == 0 && check(step))
    {
        ans ++ ;
        return ;
    }
    
    st[x][y] = true;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= n) continue;
        if (st[a][b]) continue;
        
        dfs(a, b, step + 1);
    }
    st[x][y] = false;
}

int main()
{
    dfs(0, 1, 0);
    cout << ans * 2 << endl;
    
    return 0;
}

F 最优包含

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

using namespace std;
const int N = 1010;

char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%s%s", a + 1, b + 1);
    
    int n = strlen(a + 1), m = strlen(b + 1);
    memset(f, 0x3f, sizeof f);
    
    for (int i = 0; i <= n; i ++ )
        f[i][0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
        {
            if (a[i] == b[j])
            {
                f[i][j] = f[i - 1][j - 1];
            }
            else f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m] << endl;
    return 0;
}

G 排列数

#include <iostream>
using namespace std;
#define mod 123456
#define N 505
int dp[N][N];
int main()
{
    int n, k;
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i = 2; i <= n; i++){//第i个数前面有j个折点
        dp[i][0] = 2;
        for(int j = 0; j <= i-2; j++){
            dp[i][j] %= mod;
            dp[i+1][j] += dp[i][j] * (j+1);
            dp[i+1][j+1] += dp[i][j] * 2;
            dp[i+1][j+2] += dp[i][j] * (i-j-2);
        }
    }
    cout << dp[n][k-1] % mod << endl;
    return 0;
}

H 解谜游戏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    string a, b, c;
    int T;
    scanf("%d", &T);
    
    while (T -- )
    {
        cin >> c >> b >> a;
        bool flag = true;
        for (int i = 0; i < 4; i ++ )
        {
            map<char, int> mp;
            
            mp[a[i]] ++ ;
            
            mp[b[i]] ++ ;
            mp[b[i + 4]] ++ ;
            
            mp[c[i]] ++ ;
            mp[c[i + 4]] ++ ;
            mp[c[i + 8]] ++ ;
            
            if (mp['Y'] != 1 || mp['R'] != 2 || mp['G'] != 3)
            {
                flag = false;
                break;
            }
        }
        
        if (flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

I 第八大奇迹

线段树模板题，比较简单但是没有学过，学完后更

在这里插入代码片

H 燃烧权杖

不会，抱歉

在这里插入代码片