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

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

程序员文章站 2022-04-06 20:58:44
...

蓝桥杯第七届(2016年)省赛软件类C++A组解题报告

Apare_xzc 2020/3/4


考生须知:

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


1.网友年龄

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

        枚举网友的年龄,从10开始到99,逐个判断,符合条件的计数即可。

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int x = 10;
	int cnt = 0;
	for(int x = 27;x<100;++x)
	{
		int y = x-27;
		int a = y%10,b = y/10;
		if(a*10+b==x) 
		{
			++cnt;
			cout<<x<<endl;
		}
	}
	cout<<"ans = "<<cnt<<endl;
	return 0;	
} 

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

答案:7

符合条件的年龄有:30,41,52,63,74,85,96 共七个。


2. 生日蜡烛

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

         这道题明显可以口算出来。我们可以选择最暴力的两重循环找答案,也可以对236分解质因数,稍加分析,口算出答案。
         通过分解质因数,我们知道236 = 2 * 2 * 2 * 59,我们不妨设这个人开始过生日party的年龄为x,今年的年龄为y,则x + (x+1) + (x+2) + ... + (y-1) + y = 236,我们用等差数列求和公式可得:(x+y) * (y-x+1) = 236
         我们稍加分析可知:x+y 和 y-x的奇偶性相同,那么x+y和y-x+1一定是一奇一偶。于是只能是一个59,一个8。于是:
x+y = 59
y-x = 7
联立可得:x = 26, y = 33

答案:26

分解质因数的代码:

#include <bits/stdc++.h>
using namespace std;
void f(int x)
{
	for(int i=2;i<=x;++i)
	{
		while(x%i==0) cout<<i<<",",x/=i;
	}
	cout<<endl;
}
int main()
{
	f(236);
	//236 = 2*2*2*59
    //(st+ed)*(ed-st+1) = 472;
	//st = 26 ed = 33
	return 0;
 } 

3. 方格填数

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

        简单dfs, 判断,剪枝。我们可以对这10个块进行如下的编号:
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
我们只需要dfs一个长度为10的序列,序列的每个位置都可以填09的某个数,然后判断是否合法即可。
        我们可以预处理出每个位置相邻的位置(上下左右对角)有哪些,存到vector中,便于我们dfs时判断。只要每个位置和比它编号小的所有位置都不相邻,那么这个填法一定合理

代码:

#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
int a[] = {0,0,0,0,1,1,1,1,2,2,3,3,3,4,4,4,4,5,5,5,6,7,8};
int b[] = {1,3,4,5,2,4,5,6,5,6,4,7,8,5,7,8,9,6,8,9,9,8,9};
int record[12]; 
vector<int> v[12];
void dfs(int x)
{
	if(x==10)
	{
		++ans;
//		for(int i=0;i<10;++i) printf("%d%c",record[i],i==9?'\n':' ');
		return;
	}
	bool vs[12] = {0};
	int len = v[x].size();
	for(int i=0;i<len;++i)
	{
		vs[record[v[x][i]]]= true;
	}
	for(int i=0;i<10;++i)
	{
		if(vs[i]) continue;
		record[x] = i;
		dfs(x+1);
		
	}
}
int main()
{
//	freopen("outC.txt","w",stdout);
	int L = sizeof(a)/sizeof(a[0]);
	for(int i=0;i<L;++i)
	{
		v[b[i]].push_back(a[i]);
	}
	ans = 0;
	dfs(0);
	cout<<ans<<endl;
//  702107280
//	fclose(stdout);
	return 0;	
} 

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


4. 快速排序

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

#include <stdio.h>

void swap(int a[], int i, int j)
{
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
	//请填空______________________;
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p<r){
        int q = partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}
    
int main()
{
	int i;
	int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
	int N = 12;
	
	quicksort(a, 0, N-1);
	
	for(i=0; i<N; i++) printf("%d ", a[i]);
	printf("\n");
	
	return 0;
}

//注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。

分析:

         快速排序可以用递归实现(也可以用循环)。对a[p],a[p+1],a[p+2], … ,a[r-1],a[r]这个序列排序,我们随机找序列中的某个数作为参考,题目选的是第一个数a[p],然后我们要实现大于x的全部放到x右边,小于x的全部放到x左边,最后返回x在数组中的下标。根据样例手动模拟一下不难得到答案。

答案:swap(a,p,j)

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


5. 消除尾一

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


#include <stdio.h>

void f(int x)
{
	int i;
	for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
	printf("   ");
	
	x = _______________________;
	
	for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
	printf("\n");	
}

int main()
{
	f(103);
	f(12);
	return 0;
}
//注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。

分析:

        显然题目要求一行代码将x末尾连续的1都消去。
        我们想到了树状数组中lowbit()这个函数。int lowbit(int x){return x&(-x);}返回的是整数x的二进制从后往前数第一个1以及后面的0的十进制数值(不懂的话百度一下吧)我们一先将x加1,变成xxxxx10000的形式,然后再x -= lowbit(x)

答案:(x+1)-((x+1)&(-x-1)) 或者 x&(x+1)

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


6. 寒假作业

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

        dfs即可。我们需要一些剪枝,减少不必要的计算。比如,加号两边都要小于13,被减数小于减数,乘号两端相乘不大于13,被除数要能被除数整除…

代码:

(由于剪枝,代码稍长,但都可复制粘贴一个case)

#include <bits/stdc++.h>
using namespace std;
int r[15];
long long ans = 0;
bool vis[15];
void dfs(int x)
{
	if(x==12)
	{
		++ans;
		for(int i=0;i<12;++i) printf("%d%c",r[i],i==11?'\n':' ');
		return;
	}
	if(x==0)
	{
		for(int i=1;i<=12;++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	}
	else if(x==1)
	{
		for(int i=1;i+r[0]<=13;++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	}
	else if(x==2)
	{
		int y = r[0]+r[1];
		if(y<=13&&!vis[y])
		{
			r[x] = y;
			vis[y] = true;
			dfs(x+1);
			vis[y] = false;
		}
	}
	else if(x==3)
	{
		for(int i=2;i<=13;++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	}
	else if(x==4)
	{
		for(int i=1;i<r[3];++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	}
	else if(x==5)
	{
		int dif = r[3]-r[4];
		if(!vis[dif])
		{
			r[x] = dif;
			vis[dif] = true;
			dfs(x+1);
			vis[dif] = false; 
		}
	}
	else if(x==7)
	{
		for(int i=1;i*r[6]<=13;++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		} 
	}
	else if(x==8)
	{
		int p = r[6]*r[7];
		if(p<=13&&!vis[p])
		{
			r[x] = p;
			vis[p] = true;
			dfs(x+1);
			vis[p] = false;
		}
	}
	else if(x==10)
	{
		for(int i=1;i<r[9];++i)
		{
			if(vis[i]||r[9]%i!=0) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	}
	else if(x==11)
	{
		int d = r[9]/r[10];
		if(!vis[d])
		{
			r[x] = d;
			vis[d] = true;
			dfs(x+1);
			vis[d] = false;
		}
	}
	else
	{
		for(int i=1;i<=13;++i)
		{
			if(vis[i]) continue;
			r[x] = i;
			vis[i] = true;
			dfs(x+1);
			vis[i] = false;
		}
	} 
}
int main()
{
	dfs(0);
	cout<<"ans = "<<ans<<endl;
	return 0;	
} 

答案为:64

所有填法如下:

1 8 9 13 6 7 2 5 10 12 3 4
1 8 9 13 6 7 2 5 10 12 4 3
1 8 9 13 6 7 3 4 12 10 2 5
1 8 9 13 6 7 3 4 12 10 5 2
1 8 9 13 6 7 4 3 12 10 2 5
1 8 9 13 6 7 4 3 12 10 5 2
1 8 9 13 6 7 5 2 10 12 3 4
1 8 9 13 6 7 5 2 10 12 4 3
1 8 9 13 7 6 2 5 10 12 3 4
1 8 9 13 7 6 2 5 10 12 4 3
1 8 9 13 7 6 3 4 12 10 2 5
1 8 9 13 7 6 3 4 12 10 5 2
1 8 9 13 7 6 4 3 12 10 2 5
1 8 9 13 7 6 4 3 12 10 5 2
1 8 9 13 7 6 5 2 10 12 3 4
1 8 9 13 7 6 5 2 10 12 4 3
6 7 13 9 1 8 2 5 10 12 3 4
6 7 13 9 1 8 2 5 10 12 4 3
6 7 13 9 1 8 3 4 12 10 2 5
6 7 13 9 1 8 3 4 12 10 5 2
6 7 13 9 1 8 4 3 12 10 2 5
6 7 13 9 1 8 4 3 12 10 5 2
6 7 13 9 1 8 5 2 10 12 3 4
6 7 13 9 1 8 5 2 10 12 4 3
6 7 13 9 8 1 2 5 10 12 3 4
6 7 13 9 8 1 2 5 10 12 4 3
6 7 13 9 8 1 3 4 12 10 2 5
6 7 13 9 8 1 3 4 12 10 5 2
6 7 13 9 8 1 4 3 12 10 2 5
6 7 13 9 8 1 4 3 12 10 5 2
6 7 13 9 8 1 5 2 10 12 3 4
6 7 13 9 8 1 5 2 10 12 4 3
7 6 13 9 1 8 2 5 10 12 3 4
7 6 13 9 1 8 2 5 10 12 4 3
7 6 13 9 1 8 3 4 12 10 2 5
7 6 13 9 1 8 3 4 12 10 5 2
7 6 13 9 1 8 4 3 12 10 2 5
7 6 13 9 1 8 4 3 12 10 5 2
7 6 13 9 1 8 5 2 10 12 3 4
7 6 13 9 1 8 5 2 10 12 4 3
7 6 13 9 8 1 2 5 10 12 3 4
7 6 13 9 8 1 2 5 10 12 4 3
7 6 13 9 8 1 3 4 12 10 2 5
7 6 13 9 8 1 3 4 12 10 5 2
7 6 13 9 8 1 4 3 12 10 2 5
7 6 13 9 8 1 4 3 12 10 5 2
7 6 13 9 8 1 5 2 10 12 3 4
7 6 13 9 8 1 5 2 10 12 4 3
8 1 9 13 6 7 2 5 10 12 3 4
8 1 9 13 6 7 2 5 10 12 4 3
8 1 9 13 6 7 3 4 12 10 2 5
8 1 9 13 6 7 3 4 12 10 5 2
8 1 9 13 6 7 4 3 12 10 2 5
8 1 9 13 6 7 4 3 12 10 5 2
8 1 9 13 6 7 5 2 10 12 3 4
8 1 9 13 6 7 5 2 10 12 4 3
8 1 9 13 7 6 2 5 10 12 3 4
8 1 9 13 7 6 2 5 10 12 4 3
8 1 9 13 7 6 3 4 12 10 2 5
8 1 9 13 7 6 3 4 12 10 5 2
8 1 9 13 7 6 4 3 12 10 2 5
8 1 9 13 7 6 4 3 12 10 5 2
8 1 9 13 7 6 5 2 10 12 3 4
8 1 9 13 7 6 5 2 10 12 4 3

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


7. 剪邮票

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

        12个里面选5个,我们可以dfs枚举所有选法,然后再判断每种选法5张邮票是否都连在一起。
        为了做到不重不漏,我们dfs枚举5个邮票的时候不妨按序号升序枚举
        判连通可以用dfs,从某个块开始dfs,如果所有块都能到达,则是合法的。

代码:

#include <bits/stdc++.h>
using namespace std;
int a[] = {1,1,2,2,3,3,4,5,5,6, 6,7, 7, 8, 9,10,11};
int b[] = {2,5,3,6,4,7,8,6,9,7,10,8,11,12,10,11,12};
int r[5];
bool vis[15];
vector<int> v[15];
int ans;
bool vs[15];
bool see[15];
void DFS(int x)
{
	see[x] = true;
	int len = v[x].size();
	for(int i=0;i<len;++i)
	{
		int to = v[x][i];
		if(!vs[to]) continue;
		if(see[to]) continue;
		DFS(to);
	}
}
void judge()
{
	memset(vs,false,sizeof(vs));
	memset(see,false,sizeof(see));
	for(int i=0;i<5;++i)
		vs[r[i]] = true;
	DFS(r[0]);
	int cnt = 0;
	for(int i=1;i<=12;++i)
	{
		if(see[i]) ++cnt;
	}
	if(cnt==5) 
	{
		++ans;
		for(int i=0;i<5;++i) printf("%2d%c",r[i],i==4?'\n':' ');
	}
}
void dfs(int x)
{
	if(x==5)
	{
		judge();
		return;	
	}	
	int down = x==0?1:r[x-1]+1;
	for(int i=down;i<=12;++i)
	{
		if(vis[i]) continue;
		r[x] = i;
		vis[i] = true;
		dfs(x+1);
		vis[i] = false; 
	}
} 
int main()
{
	int L = sizeof(a)/sizeof(a[0]);
	for(int i=0;i<L;++i)
	{
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);	
	} 
	dfs(0);
	cout<<"ans = "<<ans<<endl;
	
	return 0;
} 

答案为:116

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


8. 四平方和

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:又是dfs…

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6+10;
bool is2[maxn];
long long p2[3000];
int r[4];
bool ok;
int X;
void dfs(int x,int preSum)
{
	if(ok) return;
	if(x==3)
	{
		int remain = X-preSum;
		if(remain>=0&&is2[remain])
		{
			int y = sqrt(remain);
			if(y>=r[2]&&y*y==remain)
			{
				ok = true;
				for(int i=0;i<3;++i) 
					cout<<r[i]<<" ";
				cout<<y<<endl;
			}
		}
		return;
	}
	if(x==0)
	{
		for(int i=0;p2[i]*4<=X;++i)
		{
			r[0] = i;
			dfs(1,i*i);
		}
	}
	else
	{
		for(int i=r[x-1];p2[i]*(4-x)+preSum<=X;++i)
		{
			r[x] = i;
			dfs(x+1,preSum+p2[i]);
		}
	}
}
int main()
{
	for(int i=0;i*i<maxn;++i)	
	{
		is2[i*i] = true;
	}
	for(int i=0;i<3000;++i)
	{
		p2[i] = i*i;
	}
	while(cin>>X)
	{
		ok = false;
		dfs(0,0);
	}
	return 0;
} 

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


9. 密码脱落

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

样例输入1

ABCBA

样例输出1

0

样例输入2

ABDCDCBABC

样例输出2

3

分析:

        意思就是给一个字符串,问你最少添加几个字符就可以变成回文串。
        我们想到了编辑距离。 编辑距离是说把某个字符串增,删,改一个字符,若干次,最少几次能变成另一个字符串。编辑距离就可以用dp做。
        回文串有一个性质:如果a是回文串,那么a删掉左右两端的字符,仍是回文串(长度>=2)。同理,回文子串左右两边加上相同的字符仍是回文串。
        如果知道了子串a[L~R]变成回文串的最少操作数,那么a[L-1,R+1]也可以推出
令dp[L][R]为子串 str[L] 到 str[R] 变为回文串需要的最少操作数
则转移方程如下:

dp[L][L] = 0
dp[L][L+1] = (str[L]==str[L+1])?0:1
dp[L][R] = min(dp[L+1][R-1]+(str[L]!=str[R]),min(dp[L][R-1],dp[L+1][R])+1)

我们发现,dp时要用到长度较短的子串的信息,我们应该按字符串长度从小到大dp。所以这个题用区间DP即可。

代码:

#include<bits/stdc++.h>
using namespace std;
char s[1005];
int dp[1003][1003];
int main()
{
	
	while(scanf("%s",s)!=EOF)
	{
		int len = strlen(s);	
		memset(dp,0x3f,sizeof(dp));
		for(int i=0;i<len;++i) dp[i][i]=0;
		for(int i=0;i+1<len;++i)
		{
			dp[i][i+1] = (s[i]==s[i+1])?0:1;
		}
		for(int L=3;L<=len;++L)
		{
			for(int l=0;l+L-1<len;++l)
			{
				int r = l+L-1;
				dp[l][r] = min(dp[l+1][r],dp[l][r-1])+1;
				dp[l][r] = min(dp[l][r],dp[l+1][r-1]+(s[l]==s[r]?0:1));
			}
		}
		cout<<dp[0][len-1]<<endl;
	} 
	return 0;	
} 

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


10. 最大比例

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc

分析:

        要得到最大比例,我们要先求出现有的比例。我们先对所有分数从小到大排序。然后每个数和前一个相除,得到n-1个比例。
        我们将这n-1个比例排序,我们要求的答案ans一定是这些比例的约数,并且满足ans ^ t == 比例Ki。我们假设某个比例x可以表示为分数 up/down
up和down互质且down不为零
x = up / down,
up = P1^C1 * P2^C2 * ... * Pm^Cm,
down = Q1^D1 * Q2^D2 * ... * Qn^Dn,
(其中,Pi, Qi 都是质数)
设我们求的答案ans可以表示为U/D
我们将U和D分解得到如下的表示:
U = P1^c1 * P2^c2 * ... * Pm^cm
D = Q1^d1 * Q2^d2 * ... * Qn^dn
我们现在要求的是:最大的U/D, 使得对于每个比例K, 都存在正整数ti, 使得U^ti = K.up D^ti = K.down
即存在{t1,t2,t3… tn-1}使得对于每个得到的比例Ki,满足:
c1*ti = Ki.C1; c2*ti = Ki.C2; ... cm*ti = Ki.Cm
d1*ti = Ki.D1; d2*ti = ki.D2; ... dn*ti = Ki.Dn
我们只需要对每个质因数Pi,求再每个比例中对应的系数的最大公约数即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
bool notPrime[maxn];
int sushu[maxn/10],cntPrime; 
struct Node{
   long long up,down;
   Node(){up=0;down=1;}
   Node(long long u,long long d)
   {
   	up = u; down = d;
   }
   bool operator < (const Node& rhs)const
   {
   	return up*rhs.down < rhs.up*down;
   }
}node[200];
map<long long,int> mpu[100],mpd[100];
long long a[maxn];
long long gcd(long long x,long long y)
{
   if(y==0) return x;
   return gcd(y,x%y);
}
long long fast_pow(long long a,long long b)
{
   if(a==0) return 0;
   long long ans = 1;
   while(b)
   {
   	if(b&1) ans = ans*a;
   	a = a*a;
   	b>>=1;
   }
   return ans;
}
void solve(long long small,long long big,int i)
{
   long long g = gcd(big,small);
   small /= g;
   big /= g;
   node[i] = Node(big,small);
}
void getPrime();
void fenjie(long long x,map<long long,int>& mp)
{
   mp.clear();
   for(int i=0;i<cntPrime&&sushu[i]<=x/sushu[i];++i)
   {
   	int p = sushu[i];
   	if(x%p) continue;
   	int c = 0;
   	while(x%p==0)
   		++c, x/=p;
   	mp[p] = c;
   }
   if(x>1) mp[x] = 1;
}
int main()
{
   getPrime();
   set<long long> Set;
   int n;
   long long x;
   cin>>n;
   for(int i=1;i<=n;++i)
   {
   	scanf("%lld",&x);
   	Set.insert(x);
   }
   set<long long>::iterator it;
   int cnt = 0;
   for(it=Set.begin();it!=Set.end();++it)
   {
   	a[++cnt] = *it;
   }
   for(int i=1;i<=cnt;++i)
   for(int i=1;i<cnt;++i)
   {
   	solve(a[i],a[i+1],i-1);
   }
   --cnt;
   sort(node,node+cnt);
   bool has1 = false;
   for(int i=0;i<cnt;++i)
   {
   	fenjie(node[i].up,mpu[i]);
   	if(node[i].down!=1)
   		fenjie(node[i].down,mpd[i]);
   	else
   		has1 = true;
   }
   long long ansu = 1,ansd = 1;
   map<long long,int> mp;
   vector<long long> v;
   for(map<long long,int>::iterator it=mpu[0].begin();it!=mpu[0].end();++it)
   {
   	v.push_back(it->first);
   }
   int len = v.size();
   for(int i=0;i<len;++i)
   {
   	long long p = v[i];
   	int g = mpu[0][p];
   	for(int j=1;j<cnt;++j)
   	{
   		g = gcd(g,mpu[j][p]);
   		if(g==1) break;
   	}
   	mp[p] = g;
   }
   ansu = 1;
   for(map<long long,int>::iterator it=mp.begin();it!=mp.end();++it)
   {
   	ansu *= fast_pow(it->first,it->second);
   }
   
   if(has1) ansd = 1;
   else
   {
   	mp.clear();
   	v.clear();
   	for(map<long long,int>::iterator it=mpd[0].begin();it!=mpd[0].end();++it)
   	{
   		v.push_back(it->first);
   	}
   	int len = v.size();
   	for(int i=0;i<len;++i)
   	{
   		long long p = v[i];
   		int g = mpd[0][p];
   		for(int j=1;j<cnt;++j)
   		{
   			g = gcd(g,mpd[j][p]);
   			if(g==1) break;
   		}
   		mp[p] = g;
   	}
   	ansd = 1;
   	for(map<long long,int>::iterator it=mp.begin();it!=mp.end();++it)
   	{
   		ansd *= fast_pow(it->first,it->second);
   	}
   }
   cout<<ansu<<"/"<<ansd<<endl; 

   return 0;	
} 
void getPrime()
{
   int cnt = 0;
   int n = 1e6+2;
   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;
   	}
   }
   cntPrime = cnt;
}

[蓝桥杯解题报告]第七届蓝桥杯大赛省赛2016(软件类)真题C++A组 Apare_xzc


xzc
2020.3.4 17:36