第十二届蓝桥杯软件类 C/C++ A组 个人解答（基本完结）
|
蓝桥杯

2276 字
|
33 分钟

A：卡片

题目
在这里插入图片描述
答案：3181

#include <iostream>

using namespace std;

const int N=100;

int n;
int st[N];

int split(int n)
{
    while(n)
    {
        if(--st[n%10]<0) return false;
        n/=10;
    }
    return true;
}

int main()
{
    n=2021;
    for(int i=0;i<10;i++) st[i]=n;

    int i=1;
    while(split(i)) i++;

    cout<<i-1<<endl;

    return 0;
}

B：直线

题目
在这里插入图片描述
题解

  • 常规思路用斜率，但这里斜率相同的可能也是不同的直线，由此我们可以存一下该斜率在 y 轴上的截距，就能唯一判断了
  • 特殊处理 $x1-x2=0$ 的点（斜率为无穷）：直接加上竖线条数即可
  • 也可以先弄出所有直线，排个序方便去重一些，这里就不写了

答案： 40257

#include <iostream>
#include <cmath>

using namespace std;

const int N=1000010;
const double eps=1e-6;

int n,m;
double st[N],d[N];
int cnt;

bool check(double k,double t)
{
    for(int i=0;i<cnt;i++)
    {
        if(abs(st[i]-k)<eps&&abs(d[i]-t)<eps) return false;
    }
    d[cnt]=t;
    st[cnt++]=k;
    return true;
}

int main()
{
    //n=20,m=21;
    //n=3,m=4; //35
    //n=2,m=3; //11
    cin>>n;
    m=n+1;

    int res=0;
    for(int x1=0;x1<n;x1++)
        for(int y1=0;y1<m;y1++)
            for(int x2=0;x2<n;x2++)
                for(int y2=0;y2<m;y2++)
                {
                    if(x1==x2) continue;
                    double dx=x1-x2,dy=y1-y2;
                    double k=dy/dx;
                    if(check(k,y1-k*x1)) res++;
                }
    cout<<res+n<<endl;
    return 0;
}

C：货物摆放

在这里插入图片描述
答案：2430

算法1： 枚举约数法，因为乘积等于 n 只可能是 n 的约数，因此我们可以先预处理出所有的约数，最后 n^3 枚举即可（只有128个约数）

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

LL n;

int main()
{
    n=2021041820210418;
    vector<LL> a;

    for(LL i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            a.push_back(i);
            a.push_back(n/i);
        }
    }

    int res=0;
    for(auto i:a)
        for(auto j:a)
            for(auto k:a)
                if(i*j*k==n) res++;

    cout<<res<<endl;

    return 0;
}

算法2： 直接暴力法（也就4s而已）

#include <iostream>

using namespace std;

typedef long long LL;

LL n;

int main()
{
    n=2021041820210418;

    int res=0;
    for(LL i=1;i*i*i<=n;i++)
        if(n%i==0)
            for(LL j=i;i*j*j<=n;j++) //j=i开始，保持递增
                if(n/i%j==0)
                {
                    LL k=n/i/j;
                    if(i==j&&i==k) res++;
                    else if(i==j||i==k||j==k) res+=3;
                    else res+=6;
                }

    cout<<res<<endl;

    return 0;
}

算法3： 筛质因子+手算排列组合比较快，也可以 dfs，但是要处理一下重复

筛质因子代码就不展示了
质因子及个数如下：
5882353 1
2857 1
131 1
2 1
17 1
3 3

D：路径

在这里插入图片描述
题解
知识点：最短路，dijkstra

  • 最短路问题，涉及到求最小公倍数 $lcm(a,b)=a*b/gcd(a,b)$
  • 听一些大佬说dp也可以，但是不清楚正确性，即是否一定从前往后走。
  • 由于本题数据范围很小加上是填空题，直接最暴力的 $O(n^2)$ 迪杰即可。如果边过多或者 n^2 超时可以考虑堆优化迪杰

答案：10266837

#include <iostream>
#include <cstring>

using namespace std;

const int N=2050;

int g[N][N],n;
bool st[N];
int dis[N];

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

void djs()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int k=0;k<n;k++)
    {
        int u=0;
        for(int i=1;i<=n;i++)
        {
            if(!st[i]&&dis[i]<dis[u]) u=i;
        }
        st[u]=true;
        if(u==2021) break;
        for(int i=1;i<=n;i++) dis[i]=min(dis[i],dis[u]+g[u][i]);
    }
}

int main()
{
    n=2021;
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j++)
        {
            if(j-i>21) g[i][j]=g[j][i]=0x3f3f3f3f;
            else g[i][j]=g[j][i]=i*j/gcd(i,j);
        }

    djs();

    cout<<dis[n]<<endl;

    return 0;
}

E：回路计数

在这里插入图片描述
题解

  • 直接爆搜时间复杂度是阶乘级别的，即 $O(n!)$，大概只能搜到15就不行了，原因在于每个点搜索顺序可以不一样，近似看成 n 的全排列就是阶乘级别了。
  • 仔细分析题目会发现每个点的状态我们都要处理到位，且要经过每个点，20是非常nice的一个数字，会想到什么：状态压缩，我们不妨用 $(1<<21)-1$内的每个数字来表示所有状态，但是会发现如果只这样是不好处理的，因此再加入一维。
  • 状态表示：$dp[state][j]$ 表示当前经过了的点状态为 state 且最后一次经过的点为 j 的方案数。
  • 状态转移：$$dp[state][j]= \sum_{i=0}^{20}dp[state-2^i][k]$$
    转移条件：state 的第 j 位是 1 并且 state 的第 k 位也是 1，$j!=k，gcd(i+1,k+1)==1$。
  • 结果表示：$$res=\sum_{i=0}^{20}dp[(1<<21)-1][i]$$。有的小伙伴可能会问原因：$dp[(1<<21)-1][i]$ 表示的是经过了所有点且最后在第 i 个位置上的方案数，现在并没有回到源点，也就是说最后的所有结尾点为 i 的方案中就是最后倒数第2个点，再往前走一步就是终点（原点）了，而最后的状态是由所有倒数第2的状态转移过来，所以将所有 $dp[(1<<21)-1][i]$ 加起来就是最终回到原点的方案数，也就是哈密顿回路的方案数。

答案：881012367360

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)

using namespace std;

const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=22,M=400010;

int n=21;
long long dp[1<<21][21];
bool g[N][N];

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    rep(i,1,n)
        rep(j,i+1,n)
            if(gcd(i,j)==1) g[i][j]=g[j][i]=true;

    dp[1][0]=1;
    rep(i,2,1<<n)
        rep(j,0,20)
            if(i>>j&1)
                rep(k,0,20)
                    if(j!=k&&g[j+1][k+1]&&(i>>k&1))
                        dp[i][j]+=dp[i-(1<<j)][k];

    long long res=0;
    rep(i,0,20) res+=dp[(1<<21)-1][i];

    cout<<res<<endl;

    return 0;
}

F：砝码称重

在这里插入图片描述
在这里插入图片描述
题解
dp 可以做，枚举每一个砝码，再枚举所有已经存在的重量，加减当前重量 a[i] 即可，复杂度 $O(nm)$
状态方程：$$t[j]=t[j-a[i]]=true,t[j+a[i]]=true$$ 用前面轮的结果标记这一轮。
众所周知：一维肯定快点（滚动数组）
一维：

#include <iostream>
#include <cstring>

using namespace std;

const int N=110,M=200010,B=M/2;

int a[N],n;
bool f[M],t[M];

int main()
{
    cin>>n;
    int m=0;
    for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];

    f[B]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=-m;j<=m;j++)
            if(f[j+B]) 
            {
                t[j+B]=true;
                t[j+a[i]+B]=t[j-a[i]+B]=true;
            }
        memcpy(f,t,sizeof t);
    }

    int res=0;
    for(int i=1;i<=m;i++) res+=f[i+B];
    cout<<res<<endl;

    return 0;
}

二维：

#include <iostream>

using namespace std;

const int N=110,M=200010,B=M/2;

bool f[N][M];
int a[N],n;

int main()
{
    cin>>n;
    int m=0;
    for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];

    f[0][B]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=-m;j<=m;j++)
        {
            if(f[i-1][j+B]) f[i][j+B]=true; //不选
            if(f[i-1][j+B])
                f[i][j+a[i]+B]=f[i][j-a[i]+B]=true;
        }
    }

    int res=0;
    for(int i=1;i<=m;i++) res+=f[n][i+B];
    cout<<res<<endl;

    return 0;
}

G：异或数列

在这里插入图片描述
在这里插入图片描述
题解
知识点：博弈论
首先这类题咱们自己可以比划比划，可以找到一些性质

  • 如果所有数的异或和为 0，那么所有位的值都为偶数，每个数不管怎么选，双方的数最终都会相等，必然是平局
  • 不是平局，必然异或和有一个 1，我们找到最高位的 1，统计数列中这位为 1 的数量 cnt1，它必定是奇数。如果如果 Alice(先手) 想赢，必然要使最高位掌握在自己手中，这里还有一个点就是这一位为0的元素数量 cnt0，如果打不赢的时候，使用这一位为 0 的数可以使得攻防反转，最终我们要统计的就是 cnt1+cnt0 的数量，如果是奇数，则 Alice 必胜，反之 Bob 必胜
  • 值得注意的最后一点就是如果该异或值的最高位只有一位1，那么选了这个1后无论后面怎么选都是选了这个1的最大，因此如果 cnt1=0，则 Alice 必胜，这个情况要先判。
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PIII;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=200010,M=200010;

int n;
int w[N];

int main()
{
    int T; cin>>T;
    while(T--)
    {
        scanf("%d",&n);

        int res=0;
        rep(i,1,n)
        {
            scanf("%d",&w[i]);
            res^=w[i];
        }
        if(res==0) puts("0");
        else
        {
            int k=30,cnt1=0,cnt0=0;
            while(!(res>>k&1)) k--;
            rep(i,1,n)
            {
                if(w[i]>>k&1) cnt1++;
                else cnt0++;
            }

            if(cnt1==1) puts("1");
            else if(n&1) puts("1");
            else puts("-1");
        }
    }

    return 0;
}

H：左孩子右兄弟

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
题解
知识点：树的遍历，树形DP
这题是给定一棵树，问怎么转可以使得树的深度最大

  • 首先孩子可以任意选，那么对于任意一个树上的结点，我们找到它的所有的子树中最深的一个孩子，然后统计它的孩子数量，把最深的这个孩子结点依次接到它所有孩子后面就可以了。例如：有三个子树，深度分别是 2，3，4，那么我们答案就是 4+1(接在2孩子上)+1(再接在3孩子上) = 6
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PIII;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=200010;

int n;
int h[N],e[M],ne[M],idx;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int cnt=0,maxv=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        cnt++;
        maxv=max(maxv,dfs(j));
    }

    return maxv+cnt;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    rep(i,2,n)
    {
        int x; scanf("%d",&x);
        add(x,i);
    }

    cout<<dfs(1)<<endl;

    return 0;
}

I：括号序列

在这里插入图片描述
在这里插入图片描述
题解
这题才发现是个原题，可惜当时没写出来

  • 分别计算插左右括号的方案数
  • 计算另一种括号数的时候直接翻转再翻转符号就行了
  • 最后计算总方案数，其实就是插空法，分别插左右括号，最后相乘即可

DP分析：
状态表示：$f[i][j]$：只考虑前i个括号并且左括号比右括号多 $j$ 的方案数
状态转移：
当 s[i]='(‘ ，$f[i][j]=f[i-1][j-1]$;
反之 $f[i][j]=f[i-1][j+1]+f[i][j-1]$;（推导过程与完全背包类似）

  • 这里有个小问题就是有可能最终的答案刚好取模后 =0 造成返回值错误，但是这种情况十分罕见，可以忽略不计，也可以在官网通过，如果要避免这种情况可以参考代码2，通过计算最少需要添加的括号数 cnt，然后再计算出答案是需要返回几
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N=5010,MOD=1e9+7;

LL f[N][N];
int n;
char s[N];

LL get()
{
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='(')
        {
            for(int j=1;j<=n;j++)
                f[i][j]=f[i-1][j-1];
        }
        else
        {
            f[i][0]=(f[i-1][1]+f[i-1][0])%MOD;
            for(int j=1;j<=n;j++)
                f[i][j]=(f[i-1][j+1]+f[i][j-1])%MOD;
        }
    }
    for(int i=0;i<=n;i++)
        if(f[n][i]) return f[n][i];
    return -1;
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);

    LL a=get();

    reverse(s+1,s+n+1);
    for(int i=1;i<=n;i++)
        if(s[i]=='(') s[i]=')';
        else s[i]='(';

    LL b=get();

    cout<<a*b%MOD<<endl;

    return 0;
}

代码2：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=5010,M=2*N;

char s[N]; 
int n;
LL f[N][N];

LL calc()
{
    int cnt=0, k=0, l=0, r=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]==')') 
        {
            r++, k++;
            if(k>0) k=0,cnt++;
        }
        else l++,k--;
    }

    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='(') 
        {
            for(int j=1;j<=n;j++)
                f[i][j]=f[i-1][j-1];
        }
        else
        {
            f[i][0]=(f[i-1][1]+f[i-1][0])%MOD;
            for(int j=1;j<=n;j++)
                f[i][j]=(f[i-1][j+1]+f[i][j-1])%MOD;
        }
    }

    return f[n][cnt+l-r]; //直接返回答案
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);

    LL l=calc();
    reverse(s+1,s+n+1);
    for(int i=1;i<=n;i++) 
        if(s[i]==')') s[i]='(';
        else s[i]=')';

    LL r=calc();
    cout<<l*r%MOD<<endl;

    return 0;
}

J：分果果（题目）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

后续待官网题更新后再更新…心态爆炸

c++动态规划博弈论图论数据结构算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
GPLT 2021CCCC天梯赛题解

							
							

							
PAT 最大子序和