2018年4月1日省赛第九届蓝桥杯真题c,c++(B组)

时间:2022-09-10 14:47:23

(未完待续)

虽然没参加,但尝试一下写几题,不能保证正确性,但我觉得挺对的QAQ。。。

觉得还凑合就点个关注吧,希望能成为我第一个访问量破100的博客orz 。

第一题:

2000年的1月1日,是那一年的第1天。

那么,2000年的5月4日,是那一年的第几天?

31+29+31+30+4=125

第二题:明码  

 这题意看的我眼花缭乱,答案9^9.

第三题:乘积尾零

    直接java大整数搞一下,然后数数,或者求一下max(2的因子个数,5的因子个数)就行了,答案31。

第四题:测试次数

好像是刘汝佳紫数还是白书上动态规划那章还是数学那章的一个问题。原题意是n层楼m个水球,问最少实验几次,确定水球耐摔系数。

推一下方程,假设共n层楼,我们当前有m个球,然后把一个球扔到第i层,

如果球被摔破的话,那么我们需要求i-1层楼用m-1个球最少需要仍几次才能确定耐摔系数,f[n][m]=f[i-1][m-1]+1。

如果没被摔破,那么我们需要求的就是,n-i层楼,m个球至少需要扔几次才能确定耐摔系数,f[n][m]=f[n-i][m]+1。

因为我们要球最小次数,且不管摔没摔破最终都可以求出耐摔系数,所以f[n][m]=min(max(f[i-1][m-1],f[n-i][m]))   (i=1,2,3...n)

这题答案19。

第五题:快速排序

查找第k小元素,填写代码。

quick_select(a,i+1,r,k-(i-l+1))


第六题:递增三元组

给定三个整数数组

A = [A1, A2, ... AN],

B = [B1, B2, ... BN], 
C = [C1, C2, ... CN],

请你统计有多少个三元组(i, j, k) 满足:
1. 1 <= i, j, k <= N  

2. Ai < Bj < Ck  

先说下我的思路,代码日后再补:

先从小到大排个序,离线二分处理一下c数组中比b[i]大的数有多少个存到数组m中,然后再处理一下数组m的前缀和数组sm,

然后把a数组循环一遍,二分找b数组中大于a[i]的区间[l,n],那么我们让ans+=sm[n]-sm[l-1]。最后ans即为我们求的答案。代码复杂度O(nlogn)。



第七题:思路很清晰,处理很麻烦的规律题,需要细心慢慢做。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long ll;
int main()
{
	ll x,y;
	cin>>x>>y;
	ll ans=0;
	if(abs(x)<abs(y))
	{
		ll maxn=(2*abs(y)+1)*(2*abs(y)+1)-1;
		ll minn=(2*abs(y)-1)*(2*abs(y)-1);
		if(y>0)
		{
			ans=minn+(y-2+1+y);			//左上角步数
			if(x>0)
			{
				ans+=(y+1-1)+x;
			}
			else
			{
				x=-x;
				ans+=(y-x);
			}
		}
		else
		{
			y=-y;
			ans=minn+(y-2+1+y)+y+y+y+y;		//右下角
			if(x>0)
			{
				ans+=y-x;
			}
			else
			{
				x=-x;
				ans+=y;
				ans+=x;
			}
		}
	}
	else
	{
		ll maxn=(2*abs(x)+1)*(2*abs(x)+1);
		ll minn=(2*abs(x)-1)*(2*abs(x)-1);
		if(x>0)			//右边 
		{
			if(y>0)
			{
				ans=minn+(x-1);
				ans+=x+x+x;		//右上角
				ans+=x-y; 
			}
			else
			{
				y=-y;
				ans=minn+(x-1);
				ans+=x+x+x;		//右上角
				ans+=x+y; 
			}
		}
		else			//左边 
		{
			if(y>0)
			{
				x=-x;
				ans=minn+(x-1);
				ans+=y;
			}
			else
			{
				x=-x;y=-y;
				if(x==y)
				{
					ans=maxn-1;
				}
				else
				{
					ans=minn+(x-1-y);
				}
			}
		}
	}
	cout<<ans<<endl;	

	return 0;
}


第八题:

存一下每个时间被赞的时间,然后暴力相邻k个时间的间隔是否小于D。

第九题:

深搜求连通块类似的思路瞎搞就行了,代码待补

第十题:

n个数选k个乘积最大化。

我的思路如下,代码还没写。

首先把正数负数分别存在a数组和b数组,a数组从大到小排序,b数组从小到大排序。 

我们选负数当然是尽可能选偶数个啦,这让才能保证最终结果是正数。

那么我们可以枚举从b数组从前到后选2*m个数,然后从a数组从前到后选k-2*m个数。
然后暴力搞搞,注意处理ab数组出现0的情况!!!

还有全部答案为负数的情况 :k=n,这n个数都是负数并且n是奇数,或者k是奇数,并且这n个数都是负数。