欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

程序员文章站 2024-03-17 18:06:58
...

蓝桥杯第十届省赛软件类C++A组解题报告

Apare_xzc 2020/2/13

考生须知 [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

A. 平方和（5分） [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        这个题就是简单的模拟。只要循环一遍，判断每个数是否含有2019，然后平方相加即可。注意，答案大概在2019^3这个范围，要用long long或者__int64。
        判断2019的时候我们可以进行十进制的数位分解。如145这个数，个位是：145%10 = 5。十位是(145/10)%10 = 14%10=4。百位是：(145/100)%10 = 1%10 = 1。循环取模，每次x除以10，便可以得到从个位到最高位的值。

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool ok(int x)
{
    int y;
    while(x)
    {
        y = x%10;
        if(y==2||y==0||y==1||y==9) return true;
        x /= 10;
    }
    return false;
}
//2658417853
int main()
{
    LL sum = 0;
    for(int i=1;i<=2019;++i)
    {
        if(ok(i)) sum += 1ll*i*i;
    }
    cout<<sum<<endl;
    return 0; 
}

我觉得用python更好写

附赠一份python代码：

ans = 0
for x in range(1,2020):
    for c in str(x):
        if c in '2019':
            ans += x * x;break
print(ans)

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

答案为(右上角可复制)：

2658417853

B. 数列求值（5分） [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        这也是个简单的模拟题，只要按题意模拟即可。但是存在两个要注意的地方：

  • 第一，这个数比斐波那契增长还迅速，我们要一边计算一边取模。由于题目只求后四位，所以我们可以对10000取模
  • 第二，20190324这个数比较大，我们没必要开这么大的数组，可能可用的内存也没这么大，每个数只和前面3个数有关，开4个整型变量足矣。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    a = b = 1; c = 3; //初始化 
    for(int i=4;i<=20190324;++i)
    {
        d = (a+b+c)%10000;
        a = b; //相当于滚动数组  
        b = c;
        c = d;
    }
   // 6293
    cout<<d<<endl;
    return 0; 
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

附赠一份Python代码：

a,b,c = 1,1,1
for i in range(4,20190325):
    a,b,c = b,c,(a+b+c)%10000
print(c)

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

答案为：

4659

C. 最大降雨量（10分） [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        这个题我们都不需要写代码，分析即可口算。
        我们把每周降雨量从小到大排列，再按每周的中位数从小到大排列，可以得到一个7*7的矩阵。
        这个矩阵我们很熟悉，他有一个很好的性质，就是在任意一行，从左到右递增；在任意一列从上到下递增。
        所以，矩阵中某个位置的元素，一定比它右方，下方，右下方的元素要小。我们可以看下面这个图：
[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

我们可以看到，要求的这个中位数的中位数在矩阵的中心(4,4), 算上它自己，右边下边一共16个元素，最大的为49，最小的是我们要求的答案。49-16+1 = 34。
白色的数字是某一种合理的填法

答案为：

34

口算即可~

D. 迷宫 [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

输入文本如下(右上角可复制)：

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

分析：

         首先我们要知道几行几列。我们可以手动数，但是太费眼睛了。

#include <bits/stdc++.h>
using namespace std;
char a[1000][1000];
int main()
{
  freopen("maze.txt","r",stdin);
  int row = 0;
  while(cin>>a[row])
  {
     ++row;
  }
  int col = strlen(a[0]);
  cout<<row<<"行"<<strlen(a[0])<<"列\n"; 
  for(int i=0;i<row;++i)
  cout<<a[i]<<'\n';
  return 0;
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

我们得到了，输入的迷宫矩阵为30行50列

    接下来，我们就可以开始正儿八经地BFS了。bfs的同时要注意两点：

  • 第一，要保证字典序，按照D,L,R,U的顺序入队
  • 第二，要记录路径，可以记录每个点的前驱节点到它的方向，逆推回去即可。

代码：

#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
char a[32][52];
bool vis[32][52];
char s[] = "DLRU";
int dx[] = { 1, 0, 0,-1};
int dy[] = { 0,-1, 1, 0};
bool ok(int x,int y)
{
   return x>=0&&x<30&&y>=0&&y<50&&!vis[x][y]&&a[x][y]=='0'; 
} 
int r[32][52];
void bfs()
{
   memset(vis,false,sizeof(vis));
   queue<pair<int,int> > Q;
   Q.push(MP(0,0));
   vis[0][0] = true;
   int x,y,xx,yy;
   while(!Q.empty())
   {
   	x = Q.front().first, 
   	y = Q.front().second;
    	Q.pop();
   	for(int i=0;i<4;++i)
   	{
   	    xx = x+dx[i];
               yy = y+dy[i];
   	    if(ok(xx,yy)) 
   	   {
   	       vis[xx][yy] = true;
   	       Q.push(MP(xx,yy));
   	       r[xx][yy] = i;
   	   }
    }
   }
   stack<char> St;
   x = 29,y=49;
   while(1)
   {
   	St.push(s[r[x][y]]);
    	xx = x - dx[r[x][y]];
    	yy = y - dy[r[x][y]];
   	x = xx, y = yy;
           if(x==0&&y==0) break;
   } 
   while(!St.empty())
       putchar(St.top()),St.pop();
   puts("");
}
int main()
{
   freopen("maze.txt","r",stdin);
   int n = 0,m;
   for(int i=0;i<30;++i)
    cin>>a[i];
   bfs();
   return 0; 
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

路线图如下： [蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

E. RSA解密（15分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

先上一篇去年写的专属题解：RSA解密 Apare_xzc <–

题目数据：

n = 1001733993063167141
d = 212353
c = 20190324

分析：

           之前那篇题解写得很详细了。我忘记去年怎么写的了，直接开始算。

  • 第一步，我们要对n分解质因数
    (n的数量级为10^18 次那么大，可能两个指数都是10^9左右):
    技术操作：先欧拉筛线性晒出1E7之内的素数，用这些素数去试除n,看看有没有好运气可以得到p,q
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+10;
#define LL long long
int cnt; //记录素数的个数 
int sushu[maxn/10]; //得到的素数表 
bool notPrime[maxn]; //记录是不是素数 
const LL n = 1001733993063167141ll;
void getPrime();
void fenjie(LL); 
int main()
{
 getPrime(); 
 //欧拉筛线性筛出1E7之内质数 
 fenjie(n); //分解质因数 
 return 0; 
} 
void getPrime() //欧拉线筛 
{
 int n = maxn-2;
 cnt = 0;
 for(int i=2;i<=n;++i)
 {
  if(!notPrime[i]) sushu[cnt++] = i;
  for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
  {
   notPrime[i*sushu[j]] = true;
   if(i%sushu[j]==0) break;  
  }
 } 
}
void fenjie(LL x) //分解质因数 
{
 cout<<x<<" = 1";
 for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
 {
  if(x%sushu[i]) continue;
  while(x%sushu[i]==0)
  {
   x/=sushu[i];
   cout<<" * "<<sushu[i];
  } 
 } 
 if(x!=1) cout<<" * "<<x;
 cout<<endl;
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc
很遗憾，没有得到p,q,看来p和q都大于10,000,000
我们暴力分解吧

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e7+10;
const LL n = 1001733993063167141ll;
int main()
{
// getPrime();
// fenjie(n);
 cout<<"1001733993063167141 = 1";
 LL x = n;
 for(LL i=1e7+1;i<=x/i;i+=2)
 {
  while(x%i==0)
   x/=i,cout<<" * "<<i;
 }
 if(x>1) cout<<" * "<<x;
 cout<<endl;
    //1001733993063167141 = 891234941 * 1123984201
 return 0;
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

我们得到了分解质因数的结果：
1001733993063167141 = 891234941 * 1123984201
p = 891234941
q = 1123984201
我们令m = (p-1) * (q-1) = 1001733991047948000
根据欧拉函数的性质，我们可知m就是n的欧拉函数
接下来我们求d关于m的乘法逆元e，即 e * d % m = 1

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL n = 1001733993063167141ll;
void exgcd(LL a,LL b,LL &d,LL&x,LL&y)
{
 if(b==0){d = a; x = 1; y = 0;return;} 
 exgcd(b,a%b,d,y,x);
 y -= (a/b)*x;
}  
LL getNi(LL a,LL b)
{
 LL x,y,d;
 exgcd(a,b,d,x,y);
 return (x%b+b)%b;
}
int main()
{
 LL d = 212353;
 LL m = 1001733991047948000ll; 
 LL e = getNi(d,m);
 cout<<"e = "<<e<<endl;
// cout<<d<<" * "<<e<<" % "<<m<<" = "<<fast_add(e,d,m)<<endl;
 return 0; 
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

如果你不相信拓展欧几里得算法求乘法逆元的话，我们可以验证一下。

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc
恐怕会令你诧异，为什么e*d%m 不是1呢？因为：溢出了(乘爆long long了)
这个时候，我们就要用到快速乘(也叫俄罗斯农民乘法)，和快速幂原理相同。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL n = 1001733993063167141ll;
void exgcd(LL a,LL b,LL &d,LL&x,LL&y)
{
 if(b==0){d = a; x = 1; y = 0;return;} 
 exgcd(b,a%b,d,y,x);
 y -= (a/b)*x;
}  
LL getNi(LL a,LL b)
{
 LL x,y,d;
 exgcd(a,b,d,x,y);
 return (x%b+b)%b;
}
LL fast_add(LL a,LL b,LL mod)
{
 if(a==0||b==0) return 0;
 if(a<b) swap(a,b);
 LL ans = 0;
 while(b)
 {
  if(b&1) ans = (ans+a)%mod;
  a = (a<<1)%mod;
  b>>=1; 
 } 
 return ans;
} 
int main()
{
    LL d = 212353,m = 1001733991047948000ll; 
    LL e = getNi(d,m);
    cout<<"e = "<<e<<endl;
    cout<<d<<" * "<<e<<" % "<<m<<" = "<<fast_add(e,d,m)<<endl;
    
    return 0;
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc
通过快乘，我们验证了之前求的逆元e是正确的。e = 823816093931522017

           接下来，我们只需要求C^e % n即可，就是求：20190324^823816093931522017 % 1001733993063167141

  • 由于e很大，我们想到了费马小定理，我们上文中提到，n的欧拉函数Fai(n) = m, 我们可以先令指数e对m取模，减少计算量。但是，我们求逆元的过程已经对m取模了。所以这道题，出题人不考费马小定理，不知道这个定理也没关系。
  • 然后就是个快速幂
    但是，这个快速幂还要注意，这个模数太大，依旧会爆long long，还要用快乘。
//快乘：
#define LL long long
LL fast_Mul(LL a,LL b,LL mod)
{
	if(b==0||a==0) return 0;
 	if(a<b) swap(a,b);
	LL sum = 0;
	while(b)
	{
		if(b&1) sum = (sum+a)%mod;
		a = (a<<1)%mod;
		b>>=1;
	}
	return sum;
}

计算答案：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const 	LL n = 1001733993063167141ll;
LL fast_Mul(LL a,LL b,LL mod)
{
	if(b==0||a==0) return 0;
 	if(a<b) swap(a,b);
	LL sum = 0;
	while(b)
	{
		if(b&1) sum = (sum+a)%mod;
		a = (a<<1)%mod;
		b>>=1;
	}
	return sum;
}
LL fast_pow(LL a,LL b,LL mod)
{
	if(a==0) return 0;
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_Mul(ans,a,mod);
		a = fast_Mul(a,a,mod);
		b>>=1;
	}
	return ans;
} 
int main()
{
	LL c = 20190324, e = 823816093931522017ll;
	cout<<"密文c为："<<c<<endl;
	LL X = fast_pow(c,e,n);
	cout<<"原文为X：c^e = "<<c<<"^"<<e<<" % "<<n<<" = "<<X<<endl; 
//	答案为：579706994112328949
	return 0;	
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc
完整代码：

///Author: xzc
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e8+10;
const LL n = 1001733993063167141ll;
const LL p = 891234941ll;
const LL q = 1123984201ll;
const LL d = 212353;
const LL c = 20190324;
int a[maxn];
int sushu[maxn/10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数 
int cnt;
void getPrime(int n)
{
   for(int i=2;i<=n;++i)
   {
   	if(!notPrime[i]) sushu[cnt++] = i;
   	for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
   	{
   		notPrime[i*sushu[j]] = true;
   		if(i%sushu[j]==0) break; 
   	} 
   }
   for(int i=0;i<20;++i) cout<<sushu[i]<<" ";cout<<endl;
}
void fenjie(LL x)
{
   cout<<x<<" = 1";
   for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
   {
   	while(x%sushu[i]==0)
   	{
   		cout<<" * "<<sushu[i];
   		x /= sushu[i];
   	}
   }
   if(x>1) cout<<" * "<<x;
   cout<<endl;
}
void BF(LL x)
{
   cout<<x<<" = "; 
   for(LL i=1e8+1;i<x;i+=2)
   {
   	if(x%i==0)
   		cout<<i<<" * ",x/=i;
   }
   cout<<x<<endl;
}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
   if(b==0)
   {
   	d = a; x = 1; y = 0; return;
   }
   exgcd(b,a%b,d,y,x);
   y -= (a/b)*x;
}
LL rev(LL t,LL m)
{
   LL d,x,y;
   exgcd(t,m,d,x,y);
   return (x%m+m)%m;
}
LL fast_product(LL a,LL b,LL mod)
{
   LL ans = 0;
   while(b)
   {
   	if(b&1) ans = (ans+a)%mod;
   	a = (a+a)%mod;
   	b>>=1;
   }
   return ans;
} 
LL fast_pow(LL a,LL b,LL mod)
{
   LL ans = 1;
   while(b)
   {
   	if(b&1) ans = fast_product(ans,a,mod);
   	a = fast_product(a,a,mod);
   	b>>=1;		
   } 
   return ans;
}
int main()
{
   //getPrime(maxn-5);
   //fenjie(n);
   BF(n);
   LL y = (p-1)*(q-1);
   LL e = rev(d,y);
   LL answer = fast_pow(c,e,n);
   cout<<answer<<endl;

   return 0;
}

所以，E题的答案为： 579706994112328949

F. 完全二叉树的权值（15分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc
[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        我们只要计算出每层的和，然后更新答案即可。完全二叉树每一层的最后一个节点的序号为：2^i -1。见代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
	int n,x;
	cin>>n;
	int deep = 1;
	map<int,int> mp;
	for(int i=1;i<=30;++i)
	{
		mp[(1<<i)-1] = i;
	} 
	LL sum = 0;
	LL MaxSum = -100000000000000000ll;
	int ans;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		sum += x;
		if(mp.count(i)) //到达mp[i]这层的末尾 
		{
			if(sum>MaxSum) MaxSum = sum,ans = mp[i]; 
			sum = 0;	
		}
	} 
	cout<<ans<<endl;
	return 0;	
}

虽然只是过样例，还是挂个图
[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

G. 外卖店优先级（20分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        如果从时间的维度上，按秒更新或者按点单的节点对所有商店优先级更新，时间复杂度是N^2的，不明智。我们可以从商店的角度来看。
        先把所有操作按时间排序，然后对于每个商店的订单，可以维护一个列表。同时计算出这些商店最后优先级的值。
        如果大于5，一定在队列中，如果小于3，一定不在队列中，如果在中间，就要判断一下。
        我们从后往前推。发现这个列表用栈维护比较好。
        又发现，对于某个商店来说，时刻T在不在队列只和最后一个订单的时间有关。

  • 如果最后一个订单的时刻优先级为v[i[, 时间为last, 那么到第T秒，下降了 T-last[i]个，T时刻的优先级即为 v[i] - (T-last)
  • 如果大于3 小于等于5，那么我们要知道它之前的状态，在不在队列中。如果之前在队列中，说明虽然在下降，但是没有被踢出队列。只需要维护一个in数组即可。
  • 具体见代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int Last[maxn];
int val[maxn];
bool in[maxn];
int main()
{
	int n,m,T;
	vector<pair<int,int> > vii;
	int pt,id;
	scanf("%d%d%d",&n,&m,&T);
	while(m--)
	{
		scanf("%d%d",&pt,&id);
		vii.push_back(make_pair(pt,id));	
	} 
	sort(vii.begin(),vii.end());
	for(auto x:vii) 
	{
		id = x.second;
		pt = x.first;
		if(Last[id])
		{
			val[id] = max(0,val[id]-(pt-Last[id])+1);
		}
		val[id] += 2;
		if(val[id]>5) in[id] = true;
		Last[id] = pt;
	}
	int cnt = 0;
	for(int i=1;i<=n;++i)
	{
		if(!Last[i]||!in[i]) continue;
		val[i] -= (T-Last[i]);
		if(val[i]>3) ++cnt;
	}
	printf("%d\n",cnt);
		
}

样例是一定过了
[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

H. 修改数组（20分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        这个题，题意很简单，暴力大家都会，复杂度n^2, 根据给的数据范围看，暴力可以拿80分。
        但是如果想拿全分，就要好好思考一番。
        暴力模拟的问题在于每次不知道改往哪里放，试错的次数太多。我们如果可以维护之前出现的所有值之中某个值x后面最后一个不连续的数即可。比如之前出现过2,3,4,5,8,9, a[7]为2， 我们查询，2之后连续出现了2.3.4.5，查到了最后一个不连续的是6。于是a[7] 就是6.

  • 思路一：用线段树维护。线段树。插入后，如果a[i]+1也出现过，那么与后面合并，如果a[i]-1出现过，与前面合并，如果都出现过，正好合并前中后。
  • 思路二：我们线段树查询和更新的复杂度都是logn, 而且要维护的是一个值，这个值代表了出现过的连续的一串数字的最大值。相当于集合的代表。那么，我们自然而然可以想到并查集。
    并查集我们不妨把连续的这串数最小的当代表，最大的当作集合的权值。这就是一个非常简单的，维护最大值的带权并查集。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1100000+100;
int a[maxn]; //每个数在数组中连续的长度
int b[maxn]; 
//void insert(int x,int left,int right ) 
int father[maxn]; //并查集的代表元素 
int last[maxn]; //每个集合中值最大的元素 
bool vis[maxn]; //vis[i]表示i是否在之前的数列中出现过 
void initUFset(int n) //初始化并查集 
{
	for(int i=0;i<=n;++i)
		father[i] = i,last[i]=i; 
}
int getFa(int x)
{
	if(x==father[x]) return x;
	int y = father[x];
	int grandfa = getFa(father[x]); //爷爷	 
	last[grandfa] = max(last[y],last[x]);
	return father[x] = grandfa;
}
void join(int x,int y)
{
	int fx = getFa(x), fy = getFa(y);
	if(fx==fy) return;
	father[fy] = fx;
	last[fx] = max(last[fx],last[fy]);
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,x,fx,Max=-1000000;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),Max = max(Max,a[i]);
	initUFset(Max+n);
	for(int i=1;i<=n;++i)
	{
		x = a[i];
		if(vis[x]) x = last[getFa(x)]+1;
		a[i] = x;
		vis[a[i]] = true;
		if(vis[x+1]) join(x,x+1); 
		if(vis[x-1]) join(x-1,x);
	} 
	printf("%d",a[1]);
	for(int i=2;i<=n;++i)
		printf(" %d",a[i]);
	puts("");
	return 0;	
}

I. 糖果（25分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

去年写的题解：糖果题 状压dp Apare_xzc

分析：

        最暴力的方法，就是枚举出2^n种情况。每件物品，选的话为1，不选的话为0。我们可以dfs出2^n个零一串，每个串代表一个方案。然后用set之类的判断有没有m中，可以水一些分。但是这不是正解。正解是二进制状态压缩DP。dp[i]表示要达到i的二进制这种状态需要的最少袋数。这次我用了滚动数组，开的是char型，节省内存。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[101];
char dp[2][1<<20];
int getKind(int y)
{
	int ans = 0;
	while(y)
	{
		if(y&1) ++ans;
		y>>=1;
	}
	return ans;
}
int main()
{
//	freopen("in.txt","r",stdin);
	int m,n,k,x,b;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		x = 0;
		for(int j=1;j<=k;++j)
			scanf("%d",&b),x|=(1<<(b-1));
		a[i] = x;			
	} 
	int N = 1<<m, y;
	for(int i=0;i<2;++i)
	{
		for(int j=0;j<N;++j)
			dp[i][j] = n+1;
	}
	dp[0][0] = dp[1][0] = 0; //初始化 
	for(int i=1;i<=n;++i)
	{ 
		for(int j=0;j<N;++j)
		{
			if(dp[0][j]==n+1) continue;
			y = j|a[i];
			dp[1][y] = min((int)dp[1][y],dp[0][j]+1);	
		}  
		for(int j=0;j<N;++j) dp[0][j] = dp[1][j]; //滚动数组 
	}
	int ans = dp[1][N-1];
	if(ans==n+1) ans = -1;
	printf("%d\n",ans);
	
	return 0;	
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

J. 组合数问题（25分）

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

分析：

        求组合数%k==0的个数。组合数2000之内的可以n^2递推。因为：C[x][y] = C[x-1][y-1]+C[x-1][y] 然后，我们维护矩阵的二维前缀和就可以O(1)查询了。这样就可以拿到40分。后面大的数据暂时没什么好办法。希望有高人不啬赐教，欢迎在评论区留言。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2001;
int a[maxn][maxn],k,mod=1000000007;
int b[maxn][maxn];
int main()
{
	int m,n,t;
	scanf("%d%d",&t,&k);
	a[0][0] = 1;
	for(int i=1;i<=2000;++i)
	{
		a[i][0] = a[i][i] = 1;
		for(int j=1;j<i;++j) a[i][j]= (a[i-1][j-1]+a[i-1][j])%k;
	}
	for(int i=1;i<=2000;++i)
	{
		for(int j=1;j<=i;++j)
			b[i][j] = b[i][j-1]+((a[i][j]==0)?1:0);
		for(int j=i+1;j<=2000;++j)
			b[i][j] = b[i][j-1];
	}
	for(int j=1;j<=2000;++j)
	{
		for(int i=2;i<=2000;++i)
			b[i][j] += b[i-1][j]; //二维前缀和 
	}
	while(t--)
	{
		scanf("%d%d",&n,&m);
		if(n<=2000&&m<=2000) 
		{
			printf("%d\n",b[n][m]);	
		} 
		else //不会 
		{
			printf("1000000\n"); ///大数先不算了 
 		}
	}
	return 0;	
}

[蓝桥杯解题报告]第十届蓝桥杯大赛省赛（软件类）真题C++A组 Apare_xzc

写给读者的话：工程量巨大，写的匆匆忙忙，但真的是在用心写。如果有错误和纰漏，欢迎大家在评论区指正。
作者：xzc
QQ : 1363581749 （快乐的xzc）
2020/2/13 20:36

相关标签： Apare_xzc 解题报告 蓝桥杯 第十届蓝桥杯 蓝桥杯A组 蓝桥杯真题解题报告

上一篇： 026:编程填空：统计动物数量

下一篇： Java编程思想习题2.12：提取注释文档并产生HTML文件

推荐阅读