2019蓝桥杯国赛C/C++B组真题

是很简单的枚举，但是为了简化，也需要注意一些技巧

1.并不需要两层枚举去试x,y，我们只需要从比2019大的第一个数2020开始枚举x的值，然后根据2019和x的值算一下y2

2.算出y2后，一开始写错成了sqrt(y2)>x，就输出答案

正确的做法是，如果sqrt(y)是整数，才输出答案

                怎么判断y是整数？先算出y2的平方根，再把平方根平方，看是否等于原来的y2

#include
#include
using namespace std;

int main(){
	int x,y,t;  //t代表x取每个值时的y2 
	for(x=2020;;x++){
		//构成等差数列，则x2-2019 2=y2-x2
		t=x*x+(x*x-2019*2019);
		y=sqrt(t);
		if(y*y==t){
			cout< 
 
质数拆分 
 
 首先先复习一下欧拉筛法
 
bool isprime[100]; //isP[i]表示i是不是素数
int prime[100]; //已经筛出的素数列表
int n; //筛出<=n的素数
int cnt; //已经筛出的素数个数 
void euler(){
	memset(isprime,true,sizeof(isprime));
	isprime[1]=false; //1不是素数~~
	for(int i=2;i<=n;i++){
		if(isprime[i])
			prime[++cnt]=i; //如果i没有被前面的数筛掉，则i是素数
		for(int j=1;j<=cnt && i*prime[j]<=n;j++){
			//筛掉i的素数倍，也就是i的prime[j]倍
			//j循环枚举现在已经筛出的素数
			isprime[i*prime[j]]=false;
			//把prime[j]代表的这个素数的i倍筛掉
			if(i%prime[j]==0)break; 
			//这句话是关键点所在~~~~这样可以保证线性的时间复杂度 
		} 
	} 
}
 
本道题的核心思想是：先用欧拉筛法把素数筛出来，存在pre数组中
 
dp[i][pre[j]]表示满足这些额外条件的分解方案数：
 
1、被分解数为i
 
2.分解出的素数最大值恰好为pre[j]
 
那么状态转移方程就是
 
for(int k=0;k 
        dp[i][pre[j]]+=dp[i-pre[j]][pre[k]]
 
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e4+20;
const int M=2019;
int pre[N],cnt;
bool vis[N];
ll dp[N][N];
void euler()
{
	for(int i=2;i 
答案：55965365465060
 
 
求值 
 
这道题问的其实就是，含有100个约数的最小数是啥
 
答案：45360 
 
非常非常简单的暴力找一下
 
#include
using namespace std;


int main()
{
	for(int i=1;;i++){
		int sum=0;
		for(int j=1;j<=i;j++){
			if(i%j==0)
				sum++;
		}
		if(sum==100){
			cout< 
路径计数 
 
 这道题是很经典的dfs走迷宫！~
 
答案：206
 
#include
using namespace std;

//因为路径不自交，一定有一个vis数组（其实就是不走回头路）
bool vis[10][10];
//上下左右用这两个数组来试探 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int ans; 

//x,y是当前走到的位置，这道题的剪枝就在于不走超过12步，那么再有一个k来记录走过的路 
void dfs(int x,int y,int k){
	if(k>12)
		return;	//剪枝！
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];	//tx,ty是在这一步试探中，要走向的格子
		if(tx==0 && ty==0 && k+1>2 && k+1<=12)
			ans++; //如果走回了(0,0)，且走的步数>1(不是待在起点)，且走了这不不超过12，路径方案+1
		if(tx<0 || tx>7 || ty<0 || ty>7)continue; //已出界
		if(vis[tx][ty])continue; //路径自交了
		//接下来才到了“迈出这一步”的环节
		//经典的三行代码： 
		vis[tx][ty]=true;
		dfs(tx,ty,k+1);
		vis[tx][ty]=0; 
	} 
}

int main()
{
	vis[0][0]=true;  //一开始把0,0标记为走过了，所以要注意一下dfs函数里if的先后，如果先判断有没有走过，那就永远都走不到终点啦 
	dfs(0,0,0);
	cout<
 
最优包含 
 
 思路：
 
涉及字符串，本题也使用动态规划
 
T是较短的那个串，问至少S中改几个，T能成为S的子串
 
我们设dp[i][j]表示S串中前i个字符，包含有T串中前j个字符最少需要修改的字符个数。
 
因此分析得到：
 如果S[i]=T[j] ,那么T串中的最后一位要么让他和S[i]相等，要么让他和前面的相等。
 dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]);
 
如果S[i]!=T[j],那么要么是让T[j]和S串前面的字符一样，要么修改S[i]。
 dp[i][j]= min(dp[i-1][j-1]+1,dp[i-1][j])
 
并且注意的是这里动态方程中我们的i，j为个数的意思，转换为代码时由于下标从0开始，所以实际上要大一
  
 
#include
#include
#include

using namespace std;
const int N=1e3+50;
string a,b;
int dp[N][N];
int main(){
    cin>>a>>b;
    int la=a.size();
    int lb=b.size();
    memset(dp,0x3f3f3f3f,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=la;i++)
	{
        dp[i][0]=0;
        for(int j=1;j<=lb;j++)
		{
            if(a[i]==b[j]) 
				dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]);
            else 
				dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+1);
        }
    }
    cout< 
排列数 
对于一个数列中的某个数，如果这个数比两侧的数都大或比两侧的数都小，我们称这个数为这个数列的一个转折点。
 如果一个数列有t个转折点，我们称这个数列为t+1调数列。
 给定两个正整数n,k。求在1~n的全排列中，有多少个数列是k调数列。
 
 
 
用的是没有啥优化的库函数。。
 
#include
#include
#include
#include

using namespace std;

int n,k; //有k-1个转折点，n个数 
int cnt;
int a[100005];
int main(){
 	cin>>n>>k;
 	for(int i=0;ia[i-1] && a[i]>a[i+1] ) || (a[i]