【蓝桥杯】极少部分填空题真题

数学找规律
1、从1拼到多少卡片数够用
#include
using namespace std;
int cnt[10]; 

int main() {
	int n=2021,i,x,k=1;
	for(i=0;i<10;i++)cnt[i]=n;//存0-9剩余的个数 
	while(1){//k为此时的数字 
		x=k;
		while(x){
			if(cnt[x%10]>0){
				cnt[x%10]--,x/=10;//看x每一位的数字是什么 
			}
			else break;
		}
		//跳出有两种情况：x=0或cnt[x%10]=0 
		if(x)break;
		else k++;
	}
	cout< 
2、这些点确定了多少条不同直线？ 
#include 
#define N 20
#define M 21
#define eps 0.00001
using namespace std;
struct Line { double x,y,xl; };
vector v;
int main() {
	for (int i=0;i 
3、首先不能死算，要看质因数 求出来后可用dfs 或者用排列组合规律 
排列组合规律：若质因数不同，都是3种情况；若质因数相同，（n+1）*（n+2）/2 挡板法并去重 
#include
using namespace std;

using namespace std;
#define ll long long
mapq;
int main() {
	ll n= 2021041820210418,i;
	for(i=2;i*i<=n;i++){
		while(n%i==0){
			q[i]++;
			n/=i;
		}
	}
	if(n!=1)q[n]++;//5882353这种太大的超界限了 
	for(map::iterator it=q.begin();it!=q.end();it++){
		cout<first<<" :"<second< 
#include 
#define ll long long
#define MAXN 1000007
using namespace std;
ll n,x=1,y=1,z=1; int vis[9]={0,2,3,3,3,17,131,2857,5882353};
struct node { 
	ll a,b,c;
	bool operator == (const node &T) const {
		return a==T.a && b==T.b && c==T.c;
	}	
};
vector s;
void dfs(int now) {
	if (now==9) {//说明x*y*z==目标值 
		bool fl=true;
		node tp=(node){x,y,z};
		for (int i=0;i<(int)s.size();i++) {//看是否有这个node 如果没有就加入 
			if (s[i]==tp) { fl=false; break; }
		}
		if (fl) s.push_back(tp);
		return;
	}
	x*=vis[now],dfs(now+1),x/=vis[now];
	y*=vis[now],dfs(now+1),y/=vis[now];
	z*=vis[now],dfs(now+1),z/=vis[now];
}
int main() {
	dfs(1);
	cout<<(int)s.size()<<'n';
	return 0;
}
 
1、通过毫秒数求当前的时、分、秒 利用取余 
#include 
#define ll unsigned long long
using namespace std;
ll ms,s,m,h;

int main() {
	cin>>ms;
	s=ms/1000,m=ms/(1000*60),h=ms/(1000*60*60);//分别求出总秒数，总分钟数，总小时数 
	s%=60,m%=60,h%=24;//通过求余得到数 
	if (h<10) cout<<"0";
	cout< 
2、蛇形填数：逆时针旋转45°找规律 
3、求年 注意判断闰年和二月份的处理 
#include 
#include 
using namespace std;

int month[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };//表示月份 

bool isLeap(int y) {//表示闰年 
	return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}

string pin(int y, int m, int d) {//将3个数字变成8个字符的字符串 
	string s, s1;
	s1 = to_string(y);
	s += s1;
	s1 = to_string(m);
	if (s1.size() == 1) {
		s1 = "0" + s1;
	}
	s += s1;
	s1 = to_string(d);
	if (s1.size() == 1) {
		s1 = "0" + s1;
	}
	s += s1;
	return s;
}

bool huiwen(int y,int m,int d) {//判断是不是回文数字 
	string s = pin(y, m, d);
	for (int i = 0; i < 4; i++) {
		if (s[i] != s[7 - i])
			return false;
	}
	return true;
}

bool AB(int y, int m, int d) {//ABABBABA型回文数字 
	string s = pin(y, m, d);
	int A = s[0];
	int B = s[1];
	if (s[2] == A && s[3] == B && s[4] == B && s[5] == A && s[6] == B && s[7] == A) {
		return true;
	}
	return false;
}

int main() {
	int n;
	cin >> n;
	int y = n / 10000, m = n % 10000 / 100, d = n % 100;//获得年 y 月 m 日 d 
	int f1 = 0, f2 = 0;
	while (true) {	
		d++;
		if (isLeap(y))
			month[2] = 29;
		else
			month[2] = 28;
		if (d > month[m]) {//月份+1 
			m++;
			d = 1;
		}
		if (m > 12) {//年份+1 
			y++;
			m = 1;
		}
		if (f1 == 0) {
			if (huiwen(y, m, d)) {
				string s = pin(y, m, d);
				int time = stoi(s);//string->int stoi
				cout << time << endl;
				f1 = 1;
			}
		}
		if (f2 == 0) {
			if (AB(y, m, d)) {
				string s = pin(y, m, d);
				int time = stoi(s);
				cout << time << endl;
				f2 = 1;
			}
		}
		if (f1 && f2) {
			break;
		}
	}

	return 0;
}
 
DFS 
1、亮灯的种数 注意去重根据数组ans记录 
#include
#include
#include
using namespace std;
int book[8][8];
int bookk[10];
int ans[9999999];
int sum=0;
void dfs(int x){ 
	int i,k,n,p;
	for(i=1;i<=7;i++){ 
		if(bookk[i]==0&&book[x][i]==1){ 
			bookk[i]=1;
			n=0;
			p=0;
			for(k=7;k>=1;k--){ //判断该数有没有出现过 
				if(bookk[k]==1){ 
					p+=k*pow(10,n);
					n++;
				}
			}
			if(ans[p]==0){ //如若没出现过，存入数组 
				ans[p]=1;
                sum++;
//				cout< 
动态规划 
4、求最短路径 
用Floyed：先全赋正无穷，再赋0和lcm长度 再Floyed 
#include 
#define MAXN 3007
#define ll long long
using namespace std;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll d[MAXN][MAXN];
vector G[MAXN]; 
int main() {
	memset(d,0x3f,sizeof(d));//按字节赋值 很大又不会爆栈 
	for (int i=1;i<=2021;i++) d[i][i]=0;
	for (ll i=1;i<=2021;i++)
		for (ll j=1;j<=2021;j++)
			if (abs(i-j)<=21) d[i][j]=d[j][i]=i*j/gcd(i,j);
	for (ll k=1;k<=2021;k++)//Floyed算法 
		for (ll i=1;i<=2021;i++)
			for (ll j=1;j<=2021;j++)
				if (d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
	cout< 
也可通过找规律，取点1,21,42,63,84，… ，2016,2021 最后ans+=2016*2021即可 
二分法 
1、杨辉三角第一个出现的数：看一半，然后看两个组合数之间的数 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n;

LL C(int a, int b){//求Cab 
	LL res = 1;
	for(int i = a, j = 1; j <= b; i--, j++){
		res = res * i / j;
		if(res > n) return res;
	}
	return res;
}

bool check(int k){//将n约束在两个组合数中间，然后和之间的数字比较 
	LL l = k * 2, r = n + 1;// Cab b=k a的下限为2k，上限为n(a也是所在行数) 
	while(l < r){
		LL mid = l + r >> 1;
		if(C(mid, k) >= n){//行数要前移 
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	if(C(r, k) != n) return false;
	
	cout << r * (r + 1) / 2 + k + 1 << endl;
	
	return true; 
}
int main()
{
    cin >> n;//读入第一次出现在杨辉三角中的数
	for(int k = 16; ; k--){//经计算 C2kk 当k=16时已经超过1e9 
		if(check(k)){//二分法  
			break;
		}
	} 
    
    return 0;
}
 
思维难度大 
1、翻转数组 看左右端点的最值 太难了 
#include
#include
#include
using namespace std;
#define x first 
#define y second 
typedef pair PII;
const int N=100010;
int n,m;
PII stk[N];//第一个参数为0或者1表示进行前缀操作还是后缀操作，第二个参数存下标值 从1开始存，因为0相当于一个升序（后缀） 
int res[N];

int main()
{
    scanf("%d%d",&n,&m);
    int top=0;
    while(m--){
        int p,q;
        scanf("%d%d",&p,&q);
        if(!p){//进行前缀操作 即降序 
            while(top&&stk[top].x==0) q=max(q,stk[top--].y);//如果是连续的前缀操作，只需要保留最长的前缀
            while(top>=2&&stk[top-1].y<=q) top-=2;//如果有一段前缀一段后缀连续，且比当前的前缀操作短，可直接删去两段
            stk[++top]={0,q};
        }
        else if(top){//当栈不空再进行后缀，因为后缀是正序，如果第一个操作是后缀操作没有意义
            while(top&&stk[top].x==1) q=min(q,stk[top--].y);//连续后缀 
            while(top>=2&&stk[top-1].y>=q) top-=2;//如果有一段前缀一段后缀连续，且比当前的后缀操作短，可直接删去两段
            stk[++top]={1,q};
        }
    }
    int k=n,l=1,r=n;//k用来表示要填的数1~n，l，r是枚举的左右端点，根据栈里的操作填数
    for(int i=1;i<=top;i++){
        
        if(stk[i].x==0)
            while(stk[i].yl&&l<=r) res[l++]=k--;//如果是后缀，就是将后半段正序，但是前半段不变，可直接填数
    
        if(l>r) break;
    }
    if(top%2)// 若l < r, 表示中间还有些数没有填上，操作次数为奇数，则下一次操作为前缀操作
        while(l<=r) res[l++]=k--;
    else 
        while(l<=r) res[r--]=k--;
    for(int i=1;i<=n;i++) printf("%d ",res[i]);
    return 0;
}
 
2、括号匹配 
#include
#include
#include
#include
using namespace std;
typedef long long LL;

const int N=5010,mod=1e9+7;
char str[N];
LL f[N][N];//表示只考虑前i个括号，左括号比右括号多j个元素的集合 
int n;
int cal()
{
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        if(str[i]=='('){//如果是左括号，无须添加
            for(int j=1;j<=n;j++)
                f[i][j]=f[i-1][j-1];
        }else{//如果是右括号
            f[i][0]=(f[i-1][0]+f[i-1][1])%mod;//为了防止j-1得到-1越界，特别处理一下
            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++)//f[n][j]，j从0到n，找到第一个值不为零的数就是答案
        if(f[n][i]) return f[n][i];
    return -1;
}
int main(){
    scanf("%s",str+1);
    n=strlen(str+1);//字符串长度 
    LL l=cal();//左括号位置 
    
//    将字符串进行了对称，相当于选择180° 
    reverse(str+1,str+n+1);
    for(int i=1;i<=n;i++){
        if(str[i]=='(') str[i]=')';
        else str[i]='(';
    }
    
    LL r=cal();
//    先计算左括号有多少种添加方案，再计算右括号有多少种添加方案，两个结果相乘
    printf("%lld",l*r%mod);
    return 0;
}
 
3、子串分值 首先要想到记录前后字符的位置 然后用sum+=(i-pre[i])*(next[i]-i); 每次只看1个字符 
#include        
#include
#define N 100002
int main()
{
    char s[N];
    int last[26];    //记录 a~z中每个字符最后被扫描的位置，即下标 
    int pre[N];        //记录前面与第i个字符相同的字符的位置，即下标 
    int next[N];    //记录后面与第i个字符相同的字符的位置，即下标 
    
    gets(s);//获得字符串s 
    int k,i,l;
    int sum=0;        //sum=sum+(i-pre[i])*(next[i]-i)  
    l=strlen(s);    //字符串长度
    for(i=0; i<26; i++)    //由于下标从0开始，所有字符在没出现第一次前都是 -1 
        last[i]=-1;
        
    for(i=0; i=0; i--)
    {
        k=s[i]-'a';
        next[i]=last[k];    //后面与第i个字符相同的字符的位置
        last[k]=i;    //更新字符的位置 
    }
    
    for(i=0; i
【蓝桥杯】极少部分填空题真题

C/C++/C#相关栏目本月热门文章
