蓝桥杯——2021第十二届CC++真题[省赛][B组]

我还看到一个特别好理解的思路:其时当发现一个重量可以得负数，再和以后的状态做加减转化时，正数减去也能代表负数，
如 有砝码 2 1 3
前俩可以拼凑出的状态 1 2 3 -1，
3 + （-1）和 3 - 1 效果是一样的，所以负的重量状态抛弃掉最后结果也是不变的

#include
using namespace std;
int dp[105][100005];
int main()
{
	int n;
    cin >> n;
	dp[0][0] = 1;
	for (int i = 1;i <= n;i++)
	{
		int a;cin >> a;
		for (int j = 0;j <= 100000;j++)
		{
			if (dp[i-1][j])
			{
				dp[i][j] = 1;
				dp[i][j + a] = 1;
				dp[i][abs(j - a)] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1;i <= 100000;i++)if (dp[n][i]) ans++;
	cout << ans;
}

 输入样例

 2
46800999
1618708103123

输出样例

13:00:00
01:08:23 

思路:读清题目说的是毫秒，/1000换成秒,因为只要求最后一天的时分秒,所以%24*60*60就是去掉除了最后一天的前面所有天数;剩下的就是求时分秒了,很简单

#include
using namespace std;

int main()
{
    long long int n;
    cin>>n;
    n=n/1000;
    n=n%86400;//去掉除了最后一天的前面的天数;24*60*60
    int h,m,s;
    h=n/3600;//求得最后一天的小时
    n=n%3600;
    m=n/60;//分钟
    s=n%60;//秒数
    printf("%02d:%02d:%02d",h,m,s); //输出时间常用的形式，不用判断了
    return 0;
}

输入样例

2
3
6 

输出样例

8
13 

思路:这题主要考数学思维;首先通过观察,杨辉三角左右对称，题目要求找到数N的最先出现的地方，所以我们只要看左边就可以了.

我们如果单单通过观察行和列这样枚举,上面给的数据是10亿,是个很庞大的数据,我们能不能斜着来分析此问题囊？ 话不多说直接上图

 我们会发现第一个斜行是1=C(0,0),第二斜行 2=C(2,1),,,,,;以此得到第i斜行的第一个数是C(2*i,i);

下面我们来确定10亿是在哪行,考试时可以用电脑自带的计算机计算，计算得出只要对其前16行进行枚举就可以。

我们从第16斜行开始枚举，出现等于n的数就返回其位置,这里n的位置我们可以这样确定:r为行，k为斜行,然后通过r*(r+1)/2计算它前面的行的总数再加上它所在行的前面的数k+1.对于查找过程中我们发现斜行是按升序来着,可以通过采用二分的方法进行查找,避免超时。

 假如我们推个20;r=6,k=3;n=6*(6+1)/2+3+1=25

代码

#include 
#include 
#include 
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b)   //计算C（a，b）
{
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++)
    {
        res = res * i / j;
        if(res > n)
            return res;     // 大于n已无意义，且防止爆LL
    }
    return res;
}
bool check(int k)
{
   
    int l = 2 * k, r = max(n,l);
    while(l < r)
    {
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n)
        return false;
    cout << 1ll*(r + 1) * r / 2 + k + 1 << endl;
    return true;
}
int main()
{
    cin >> n;
    // 从第16斜行枚举
    for(int i = 16; ; i--)
        if(check(i))
            break;
    return 0;
}

 视频版:

第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili

输入样例

3 3
0 3
1 2
0 2 

输出样例

3 1 2 

思路:感觉最后两道题都挺难的,都是考思维的,对于我这个小白真是太不友好了，只会个sort暴力排序偷几分,这个代码我就不放在这里面了.找了acw的视频看了下,条理清晰了些，视频放在这里:

第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili

下面我附上一位大佬写的博客,跟这个视频是相匹配的大家可以去看看,我就不必要再写了,总结的太详细啦.

蓝桥杯 I.双向排序_Jozky86的博客-CSDN博客_蓝桥杯双向排序

代码:

#include 
#include 
#include 
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main()
{
    scanf("%d%d", &n, &m);
    int top = 0;
    while (m -- )
    {
        int p, q;
        scanf("%d%d", &p, &q);
        if (!p)// *** 作1 
        {
            while (top && stk[top].x == 0) 
				q = max(q, stk[top -- ].y);//出现连续的 *** 作1，我们取最大 
            while (top >= 2 && stk[top - 1].y <= q) 
			//如果当前的操作1比上一次的操作1范围大，则将上一次操作1和操作2删除 
				top -= 2;
            stk[ ++ top] = {0, q};//存本次最佳操作 
        }
        else if (top)//操作2 &&且操作1已经进行过（操作二第一个用没效果） 
        {
            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;
    for (int i = 1; i <= top; i ++ )
    {
        if (stk[i].x == 0)//如果是操作1 
            while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;//移动r值 ，并赋值 
        else
            while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ; 
        if (l > r) break;
    }
    if (top % 2)
        while (l <= r) ans[l ++ ] = k -- ;
    else
        while (l <= r) ans[r -- ] = k -- ;

    for (int i = 1; i <= n; i ++ )
        printf("%d ", ans[i]);
    return 0;
}

 老样子这题还是不完全会,又是用暴搜在测试点骗了部分分。

既然咱做不出来就要去学习大佬的做法和思路。

博客:12届蓝桥杯省赛c++b组 J题 括号序列_thejohn2020的博客-CSDN博客_蓝桥杯括号序列 

视频:第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili

代码

#include 
#include 
#include 
using namespace std;
using LL=long long;
const int N = 5005;
int f[N][N];
int mod=1e9+7;
string s;
int n;
LL get(){
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='('){
            for(int j=1;j<=n;j++)
                f[i][j]=f[i-1][j-1];
        }
        else{
            f[i][0]=(f[i-1][1]+f[i-1][0])%mod;
            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++)
        if(f[n][i])
            return f[n][i];
    return -1;
}
int main(){
    cin>>s;
    n=s.size();
    LL x=get();
    reverse(s.begin(),s.end());
    for(int i=0;i