第十二届蓝桥杯省赛第二场C/C++大学B组编程题题目及解析

目录

 试题F：特殊年份

试题G：小平方 

 试题H：完全平方数

 试题I：负载平衡

试题J：国际象棋 

 试题F：特殊年份

#include <iostream>

using namespace std;

const int N = 5;

int res;

int a[N];

int main()
{
    for(int i = 0; i < 5; i ++)
    {
        int x;
        cin >> x;
        for(int j = 0; j < 5; j ++)
        {
            a[j] = x % 10; //a 0,1,2,3 分表表示个十百千位
            x /= 10;
        }
        if(a[1] == a[3] && a[0] - a[2] == 1)
            res ++;
    }
    cout << res;
    return 0;
}

试题G：小平方 

枚举 

#include <iostream>

using namespace std;

const int N = 10010;

int res;

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i < (int)n; i ++)
    {
        if((i * i) % n < (double)n / 2)
            res ++;
    }
    cout << res;
    return 0;
}

 试题H：完全平方数

#include <iostream>

using namespace std;

typedef long long LL;

int main()
{
    LL n;
    LL res = 1;
    cin >> n;
    for(LL i = 2; i * i <= n; i ++)
    {
        LL s = 0;
        while(n % i == 0)
        {
            n /= i;
            s ++;
        }
        if(s % 2)  res *= i;
    }
    if(n > 1)   res *= n;
    cout << res;
    return 0;
}
    

 试题I：负载平衡

 模拟 + 优先队列

#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;// <结束时间,任务算力>
const int N = 200010;

int n, m;
int s[N]; // 剩余算力
priority_queue<PII, vector<PII>, greater<PII>> q[N]; // <类型,存储方式,比较函数>,结构体小根堆比较结构体的第一个变量

int main()
{
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d",&s[i]);
    while (m --)
    {
        int a, b, c, d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        while(q[b].size() && q[b].top().x <= a)
        {
            s[b] += q[b].top().y;
            q[b].pop();
        }
        if (s[b] < d) printf("-1\n");
        else
        {
            q[b].push({a + c, d});
            s[b] -= d;
            printf("%d\n",s[b]);
        }
    }
    return 0;
}

试题J：国际象棋 

状态压缩DP

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

using namespace std;

const int N = 110, M = 1 << 6, K = 21, MOD = 1e9 + 7;

int n, m, k;
int f[N][M][M][K];

int get_count(int x)
{
    int res = 0;
    while (x)
    {
        res ++ ;
        x -= x & -x;
    }
    return res;
}

int main()
{
    cin >> n >> m >> k;
    f[0][0][0][0] = 1;

    int cnt = 0;
    for (int i = 1; i <= m; i ++ )
        for (int a = 0; a < 1 << n; a ++ )
            for (int b = 0; b < 1 << n; b ++ )
            {
                if (a & (b << 2) || b & (a << 2)) continue;
                for (int c = 0; c < 1 << n; c ++ )
                {
                    if (c & (b << 2) || b & (c << 2)) continue;
                    if (c & (a << 1) || a & (c << 1)) continue;
                    int t = get_count(c);
                    for (int u = t; u <= k; u ++, cnt ++ )
                        f[i][b][c][u] = (f[i][b][c][u] + f[i - 1][a][b][u - t]) % MOD;
                }
            }

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < 1 << n; j ++ )
            res = (res + f[m][i][j][k]) % MOD;

    cout << res << endl;
    return 0;
}