第十二届蓝桥杯省赛第二场 C/C++ 组题解

蓝桥杯

字数统计: 2.1k阅读时长: 8 min

 2022/04/11  137

题面

求余

送分题

答案： $1$

双阶乘

只需要维护最后 $5$ 位即可，于是一个 for 搞定，边乘边对 ${10}^5$ 取模

答案： $59375$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int mul = 1;
    for(int i=3;i<=2021;i+=2)
        mul = mul * i % 100000;
    cout<<mul<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

格点

两重 for 遍历 $x,y$ 值然后加一个判断计数即可

答案： $15698$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int cnt = 0;
    for(int i=1;i<=2021;i++)
        for(int j=1;j<=2021;j++)
            if(i*j<=2021) ++cnt;
    cout<<cnt<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

整数分解

注意到所求为方案数，求方案数常见两种方法：组合数学或动态规划

本题两种方法均可

组合数学

显然题目即为在 $2021$ 个 $1$ 的 $2020$ 个空隙中插入 $4$ 个隔板的方案数

故答案为： $\binom{2020}{4}=691677274345$

动态规划

状态设计： $dp[i][j]$ 表示 $i$ 分成 $j$ 个正整数之和的方案数
初始状态： $dp[i][1] = 1$
转移方程： $dp[i][j] = \sum_{k=1}^{i-1} dp[k][j-1]$
所求结果： $dp[2021][5] = 691677274345$

答案： $691677274345$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
const int maxn = 2025;
typedef long long ll;
//? 做法一：组合数学
//* 即在 2021 个 1 的 2020 个空隙中插入 4 个隔板
//* 答案：\binom{2020}{4}
ll solve1()
    ll mul = 1;
    for(int i=2020;i>2016;i--)
        mul *= i/(i-2016);
    return mul;
//* 状态设计：dp[i][j] i 分成 j 个正整数之和的方案数
//* 初始状态：dp[i][1] = 1
//* 转移方程：dp[i][j] = \sum_{k=1}^{i-1} dp[k][j-1]
//* 答案：dp[2021][5]
ll dp[maxn][maxn];
ll solve2()
    int n=2021, m=5;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=min(i,m);j++)
            if(j==1) dp[i][j]=1;
            else 
                ll sum = 0;
                for(int k=1;k<i;k++)
                    sum += dp[k][j-1];
                dp[i][j]=sum;
    return dp[n][m];
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    cout<<"Method 1:"<<solve1()<<endl;
    cout<<"Method 2:"<<solve2()<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

城邦

显然最小生成树裸题，下一道

答案： $4046$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <numeric>
#include <tuple>
#include <algorithm>
#include <string>
#include <vector>
const int maxn = 2025;
int fa[maxn];
int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
inline void merge(int x,int y) { fa[find(x)]=find(y); }
vector<tuple<int,int,int>> edge;
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int n = 2021;
    iota(fa+1, fa+1+n, 1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            string s1=to_string(i), s2=to_string(j);
            if(s1.length()<s2.length())
                s1 = string(s2.length()-s1.length(), '0') + s1;
            else if(s2.length()<s1.length())
                s2 = string(s1.length()-s2.length(), '0') + s2;
            int sum = 0;
            for(int i=0;i<s1.length();i++)
                if(s1[i]!=s2[i])
                    sum += s1[i]-'0'+s2[i]-'0';
            edge.emplace_back(sum,i,j);
    sort(edge.begin(), edge.end());
    int ans=0, cnt=0;
    for(auto [w,u,v] : edge)
        if(find(u)!=find(v))
            ans += w;
            merge(u,v);
            if(++cnt==n-1) break;
    cout<<ans<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

游戏

又是求方案数，发现这回不能用组合数学了，于是思路转向 DP

状态设计： $dp[i]$ 表示从 $i$ 开始写的方案数
初始状态： $dp[1] = 1$
转移方程： $dp[i] = \sum_{d|i} dp[d]$
所求结果： $\sum_{i=1}^{n} dp[i]$

发现直接递推的话，对于每个数都需要 $O(\sqrt n)$ 找约数，时间复杂度是 $O(n \sqrt n)$ 的，有些慢。于是我们采用刷表法优化，用前向状态去更新后继状态，即用每个数的 DP 值去更新其倍数的 DP 值。时间复杂度 $O(n \log n)$

答案： $1352184317599$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <numeric>
const int maxn = 20210511;
typedef long long ll;
ll dp[maxn] = {0, 1};
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int n = 20210509;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
            dp[i*j] += dp[i];
    cout<<accumulate(dp+1, dp+1+n, 0LL)<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

特殊年份

模拟即可

使用 std::string 可以非常简单地写出程序

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <string>
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int cnt = 0;
    for(int i=0;i<5;i++)
        string s;
        cin>>s;
        if(s[0]==s[2]&&s[1]+1==s[3])
            ++cnt;
    cout<<cnt<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

小平方

模拟……开个 for 循环即可

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    cin>>n;
    int cnt = 0;
    for(int i=1;i<n;i++)
        if(i*i%n<n/2.0) ++cnt;
    cout<<cnt<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

完全平方数

设 $A$ 为完全平方数，有： $A=x \times x$

设 $x$ 的标准质因数分解式为：

$x={p_1}^{\alpha_1}{p_2}^{\alpha_2} \cdots {p_s}^{\alpha_s}$

则 $A$ 的标准质因数分解式为：

$A={p_1}^{2\alpha_1}{p_2}^{2\alpha_2} \cdots {p_s}^{2\alpha_s}$

即 $A$ 的所有质因数都一定出现偶数次，故我们只需要对 $n$ 进行质因数分解，然后将所有出现了奇数次方的质因数乘在一起即为答案（将奇数补成偶数）。时间复杂度： $O(\sqrt n)$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <map>
#include <algorithm>
typedef long long ll;
map<ll, int> fac(ll n)
    map<ll, int> ret;
    for(ll i=2;i*i<=n;i++)
        while(n%i==0)
            n/=i;
            ++ret[i];
    if(n!=1) ++ret[n];
    return ret;
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    cin>>n;
    auto facts = fac(n);
    ll mul = 1;
    for(auto [x,y] : facts)
        if(y%2) mul *= x;
    cout<<mul<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

负载均衡

可以把分配任务想象成向计算机借了一些算力，时间到了后再还回去

于是我们开一个堆来维护要还回去的算力，对于每次操作先把时间到了的需要还回去的算力还回去，再判断此次能否借来算力，若能借来算力，把计算机的算力扣除了借走的算力后，在堆中打一个欠条。重复此流程即可，时间复杂度： $O(n \log n)$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <queue>
#include <tuple>
const int maxn = 2e5+5;
typedef tuple<int,int,int> tp3;
int v[maxn];
priority_queue<tp3, vector<tp3>, greater<tp3>> pq;
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    while(m--)
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        while(!pq.empty()&&get<0>(pq.top())<=a)
            auto [_,j,k] = pq.top();
            pq.pop();
            v[j]+=k;
        if(v[b]>=d)
            v[b]-=d;
            cout<<v[b]<<'\n';
            pq.emplace(a+c, b, d);
        else cout<<-1<<'\n';
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

国际象棋

发现此题即 [SCOI2005] 互不侵犯的加强版。把王换成马，即会跟上两行有关系罢了

状压 DP，把每行棋子放法用 01 串来表示，放了马为 1，没放为 0：

状态设计： $dp[i][p][q][j]$ 代表当前放到第 $i$ 行，放法为 $p$ ，上一行放法为 $q$ ，已经放了 $j$ 个马的方案数
初始状态： $dp[1][p][0][popcount(p)] = 1,p \in [0, 2^n-1]$ （同一行的马不会互相攻击所以可以随便放）
转移方程： $dp[i][p][q][j] = \sum_{a} dp[i-1][q][a][j-popcount(p)],j \in [popcount(p),k],(q,p) \And (a,p) \text{不冲突}$
所求结果： $\sum_{p=0}^{2^n-1} \sum_{q=0}^{2^n-1} dp[m][p][q][k]$

注意数据范围 $n<=6,~m<=100$ ，即 $2^m >> 2^n$ ，故我们把 $m$ 当做行来处理可以极大地缩小空间时间复杂度，最终时间复杂度： $O(m \times 2^n \times 2^n \times 2^n \times k) = O(8^nmk)$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
const int maxn = (1<<6)+5;
const int mod = 1e9+7;
int pc[maxn];
int dp[105][maxn][maxn][25];
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<(1<<n);i++)
        pc[i]=__builtin_popcount(i);
        if(pc[i]>k) continue;
        dp[1][i][0][pc[i]]=1;
    for(int i=2;i<=m;i++)
        for(int p=0;p<(1<<n);p++)
            for(int q=0;q<(1<<n);q++)
                if(p<<2&q || p>>2&q) continue;
                for(int a=0;a<(1<<n);a++)
                    if(p<<1&a || p>>1&a) continue;
                    for(int j=pc[p];j<=k;j++)
                        dp[i][p][q][j] += dp[i-1][q][a][j-pc[p]];
                        dp[i][p][q][j] %= mod;
    int sum = 0;
    for(int p=0;p<(1<<n);p++)
        for(int q=0;q<(1<<n);q++)
            sum = (sum + dp[m][p][q][k]) % mod;
    cout<<sum<<endl;
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

完美序列

鸣谢：感谢 @Tifa 大佬提供的主要思路

读完题目，我们可以轻松获取如下三个结论（以下简称“ $1$ 至 $n$ 的所有排列中长度正好为 $n$ 阶最大完美长度的最长完美子序列”为“最长完美子序列”：

$n$ 阶最大完美长度为 $\lfloor \log_2 n \rfloor + 1$
每个“最长完美子序列”一定以 $1$ 为结尾
每个“最长完美子序列”中一定只存在前一个数是后一个数的 $2$ 倍或 $3$ 倍，且 $3$ 倍只出现一次

第一个结论是显然的，因为下降最慢的完美序列为等比数列 $2^k,2^{k-1},\cdots,1$ ，故一个最大值为 $n$ 的完美序列的最大长度为 $\lfloor \log_2 n \rfloor + 1$

第二个结论采取反证法：若存在一个“最长完美子序列” $P$ 不以 $1$ 为结尾，那么一定存在一个完美子序列 $Q=(P,1)$ 比 $P$ 长，那么 $P$ 必然不是最长的，矛盾

第三个结论采取反证法：首先，若出现了 $3$ 倍以上，即以长度 $2$ 出现了 $3$ 倍以上（例： $5,1$ ），但我们至少可以用长度 $3$ 来出现 $4$ 倍（ $4,2,1$ ），也就说说若出现了 $3$ 倍以上，那么此“最长完美子序列”必然不是最长的，矛盾；其次，若出现了两个 $3$ 倍，即以长度 $3$ 出现了 $9$ 倍（例： $9,3,1$ ），但我们可以用长度 $4$ 来出现 $8$ 倍（ $8,4,2,1$ ），也就是说若出现了 $9$ 倍，那么此“最长完美子序列”必然不是最长的，矛盾

有了如上三个结论，我们就可以开始考虑如何解决这个问题了。设 $n$ 阶最大完美长度为 $len=\lfloor \log_2 n \rfloor + 1$ ，我们分情况讨论：

“最长完美子序列”中不存在 $3$ 倍，即“最长完美子序列”为： $2^{len-1} \rightarrow 1$

此时“最长完美子序列”为等比数列 $2^{len-1},2^{len-2},\cdots,1$ ，由等比数列求和公式 $S_n=\cfrac{a_1-a_{n}q}{1-q}$ ，此情况下“最长完美子序列”的和为：

$\cfrac{2^{len-1}-1 \times \frac{1}{2}}{1-\frac{1}{2}}=2^{len}-1$

“最长完美子序列”中存在 $3$ 倍，即“最长完美子序列”为： $3 \cdot 2^{len-2} \rightarrow 1$

注意：只有当 $n \geq 3 \cdot 2^{len-2}$ 时才会出现此情况

设 $S_{len}$ 为存在 $3$ 倍情况下所有长度为 $len$ 的“最长完美子序列”的和，则有：

递推预处理即可。以 $len=5$ 为例，上式的各部分如下：

当然，也可以使用此递推式的通项公式 $S_{len}=2^{len-1}(3len-4) - len + 2$ 直接算出结果

于是对于一个给定的 $n$ ，我们只需要判断一下是否可能出现第二种情况，根据上文所述即可获取所有“最长完美子序列”的和

注意“最长完美子序列”是 $1$ 至 $n$ 的所有排列的子序列，也就是说每个“最长完美子序列”会出现多次，其出现次数为 $\cfrac{A_n^n}{A_{len}^{len}}=\cfrac{n!}{len!}$ ，在计算答案时需要乘进去

为什么是 $\cfrac{A_n^n}{A_{len}^{len}}$ 呢？ $1$ 至 $n$ 的所有排列共有 $A_n^n$ 个，而其中“最长完美子序列”的相对位置是不变的，所以除掉“最长完美子序列”的排列数 $A_{len}^{len}$

注意到出现了有理数取余，需要预处理阶乘及其逆元 $\left[ \cfrac{n!}{len!} \equiv n! \times (len!)^{-1} \pmod p \right]$ 。数据规模 $n \leq {10}^6$ 不是很大，采用 $O(n + \log p)$ 或者 $O(n \log n)$ 求逆元都可以。

若采用 $O(n \log n)$ 求逆元则总时间复杂度为 $O(n \log n + T)$ ；若采用 $O(n + \log p)$ 求逆元则总时间复杂度为 $O(n + \log p + T)$

Code

#include <iostream>
#include <ctime>
using namespace std;
//==========================================
#include <cmath>
const int maxn = 1e6+5;
const int mod = 1e9+7;
typedef long long ll;
ll qpow(ll a,ll k)
    ll res = 1;
    for(;k;k>>=1,a=a*a%mod)
        if(k&1) res=res*a%mod;
    return res;
ll fct[maxn]={0,1}, inv[maxn]={0,1};
inline void inv1()  //? 快速幂 O(nlogn) 求逆元
    for(int i=2;i<=1e6;i++) inv[i]=qpow(fct[i], mod-2);
ll s[maxn], sv[maxn];
inline void inv2()  //? 线性求任意 n 个数的逆元
    int n = 1e6;
    s[1]=1;
    for(int i=2;i<=n;i++) s[i]=s[i-1]*fct[i]%mod;
    sv[n]=qpow(s[n], mod-2);
    for(int i=n-1;i>=1;i--) sv[i]=sv[i+1]*fct[i+1]%mod;
    for(int i=2;i<=n;i++) inv[i]=sv[i]*s[i-1]%mod;
signed main(signed argc, char const *argv[])
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    clock_t c1 = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //======================================
    for(int i=2;i<=1e6;i++) fct[i]=fct[i-1]*i%mod;
    inv2();  // 使用线性求任意 n 个数的逆元
    cin>>t;
    while(t--)
        int n;
        cin>>n;
        if(n==1) cout<<1<<endl;
        else 
            ll len = (ll)log2(n)+1;
            ll a = fct[n]*inv[len]%mod;
            ll c1 = a*((1<<len)-1)%mod;
            if(n<3*(1<<(len-2))) cout<<c1<<'\n';
            else cout<<(c1+a*((1<<(len-1))*(3*len-4)-len+2))%mod<<'\n';
    //======================================
#ifdef LOCAL
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;

原文作者：AgOH

原文链接：https://stagoh.com/2022/04/11/LQ12province2-C/

发表日期：April 11th 2022, 8:13:18 pm

更新日期：December 17th 2023, 5:08:54 pm

Next Post

第十二届蓝桥杯省赛第一场 C/C++ 组题解

CATALOG

1. 求余
2. 双阶乘
3. 格点
4. 整数分解
1. 4.1. 组合数学
2. 4.2. 动态规划
5. 城邦
6. 游戏
7. 特殊年份
8. 小平方
9. 完全平方数
10. 负载均衡
11. 国际象棋
12. 完美序列
1. 12.1. “最长完美子序列”中不存在 $3$ 倍，即“最长完美子序列”为： $2^{len-1} \rightarrow 1$
2. 12.2. “最长完美子序列”中存在 $3$ 倍，即“最长完美子序列”为： $3 \cdot 2^{len-2} \rightarrow 1$

	#include <iostream>
	#include <ctime>
	using namespace std;
	//==========================================
	signed main(signed argc, char const *argv[])
	{
	#ifdef LOCAL
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
	clock_t c1 = clock();
	#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//======================================
	int mul = 1;
	for(int i=3;i<=2021;i+=2)
	mul = mul * i % 100000;
	cout<<mul<<endl;
	//======================================
	#ifdef LOCAL
	cerr << "Time Used:" << clock() - c1 << "ms" << endl;
	#endif
	return 0;
	}

第十二届蓝桥杯省赛第二场 C/C++ 组题解

求余

双阶乘

格点

整数分解

组合数学

动态规划

城邦

游戏

特殊年份

小平方

完全平方数

负载均衡

国际象棋

完美序列

“最长完美子序列”中不存在 333 倍，即“最长完美子序列”为：2len−1→12^{len-1} \rightarrow 12len−1→1

“最长完美子序列”中存在 333 倍，即“最长完美子序列”为：3⋅2len−2→13 \cdot 2^{len-2} \rightarrow 13⋅2len−2→1

“最长完美子序列”中不存在 $3$ 倍，即“最长完美子序列”为： $2^{len-1} \rightarrow 1$

“最长完美子序列”中存在 $3$ 倍，即“最长完美子序列”为： $3 \cdot 2^{len-2} \rightarrow 1$