蓝桥杯の旅

[蓝桥杯 2023 省 A] 平方差

题目描述

给定 \(L,R\)，问 \(L \leq x \leq R\) 中有多少个数 \(x\) 满足存在整数 \(y,z\) 使得 \(x=y^2-z^2\)。

输入格式

输入一行包含两个整数 \(L,R\)，用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 \(x\) 的数量。

样例 #1

样例输入 #1

1
1 5

样例输出 #1

1
4

提示

【样例说明】

  • \(1=1^2-0^2\)
  • \(3=2^2-1^2\)
  • \(4=2^2-0^2\)
  • \(5=3^2-2^2\)

【评测用例规模与约定】

对于 \(40 \%\) 的评测用例，\(L,R \leq 5000\)；

对于所有评测用例，\(1 \leq L \leq R \leq 10^9\)。

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C

如果是奇数，直接拆成 \(1\) 和它本身即可。

如果是偶数，因为要拆成 \(2\) 个偶数，所以应是 \(4\) 的倍数，此时一种拆分为拆成 \(2\) 和 \(x\) 除以 \(2\)。

至此，答案为 \(l\) 到 \(r\) 中奇数和 \(4\) 的倍数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
signed main()
{
    int l,r;
    cin>>l>>r;
    cout<<(r+1)/2-(l)/2+r/4-(l-1)/4<<'\n';
    return 0;
}

[蓝桥杯 2023 省 A] 更小的数

题目描述

image

小蓝有一个长度均为 \(n\) 且仅由数字字符 \(0 \sim 9\) 组成的字符串，下标从 \(0\) 到 \(n-1\)，你可以将其视作是一个具有 \(n\) 位的十进制数字 \(num\)，小蓝可以从 \(num\) 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 \(num_{new}\) 满足条件 \(num_{new}<num\)，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 \(num\) 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 \(0\)，这是合法的。

输入格式

输入一行包含一个长度为 \(n\) 的字符串表示 \(num\)（仅包含数字字符 \(0 \sim 9\)），从左至右下标依次为 \(0 \sim n-1\)。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

1
210102

样例输出 #1

1
8

提示

【样例说明】

一共有 \(8\) 种不同的方案：

  1. 所选择的子串下标为 \(0\sim1\)，反转后的 \(num_{new} = 120102 < 210102\)；
  2. 所选择的子串下标为 \(0\sim2\)，反转后的 \(num_{new} = 012102 < 210102\)；
  3. 所选择的子串下标为 \(0\sim3\)，反转后的 \(num_{new} = 101202 < 210102\)；
  4. 所选择的子串下标为 \(0\sim4\)，反转后的 \(num_{new} = 010122 < 210102\)；
  5. 所选择的子串下标为 \(0\sim5\)，反转后的 \(num_{new} = 201012 < 210102\)；
  6. 所选择的子串下标为 \(1\sim2\)，反转后的 \(num_{new} = 201102 < 210102\)；
  7. 所选择的子串下标为 \(1\sim4\)，反转后的 \(num_{new} = 201012 < 210102\)；
  8. 所选择的子串下标为 \(3\sim4\)，反转后的 \(num_{new} = 210012 < 210102\)。

【评测用例规模与约定】

对于 \(20\%\) 的评测用例，\(1 \le n \le 100\)；

对于 \(40\%\) 的评测用例，\(1 \le n \le 1000\)；

对于所有评测用例，\(1 \le n \le 5000\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=5050;
bool dp[N][N];
int ans;
signed main()
{
//直接动态规划就可以
//这题很像最长公共子序列的
string s;
cin>>s;
frep(i,s.length()-1,0)
{
    rep(j,i,s.length()-1)
    {
if(s[i]>s[j])
{
    dp[i][j]=1;
}
else if(s[i]<s[j])
{
    dp[i][j]=0;
}
else
{
    dp[i][j]=dp[i+1][j-1];
}
if(dp[i][j])
{
    ans++;

    }
}
}
cout<<ans<<'\n';
return 0;
}

[蓝桥杯 2023 省 A] 异或和之和

题目描述

给定一个数组 \(A_i\)，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 \(1 \leq L \leq R \leq n\) 的 \(L,R\)，求出数组中第 \(L\) 至第 \(R\) 个元素的异或和。然后输出每组 \(L,R\) 得到的结果加起来的值。

输入格式

输入的第一行包含一个整数 \(n\) 。

第二行包含 \(n\) 个整数 \(A_i\)，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

1
2
5
1 2 3 4 5

样例输出 #1

1
39

提示

【评测用例规模与约定】

对于 \(30 \%\) 的评测用例，\(n \leq 300\)；

对于 \(60 \%\) 的评测用例，\(n \leq 5000\);

对于所有评测用例，\(1 \leq n \leq 10^5\)，\(0 \leq A_i \leq 2^{20}\)。

这里套一下第一篇题解

首先，异或有一个重要的性质：

\[a\oplus b \oplus b=a\]

因为 \(b\) 的二进制位一定与自己一样，根据异或的定义，得出 \(b\oplus b=0\)，进而推出这个式子。

有了这个式子，区间异或和就可以像前缀和一样处理了。

我们可以求出每一项的前缀异或和，记作 \(q_i\)，根据上面那条性质，可以仿照前缀和的形式写出区间 \([l,r]\) 的异或和（记作 \(S_{l,r}\)）的 \(O(1)\) 求法式子：（下标均从 \(1\) 开始）

\[S_{l,r}=p_r\oplus p_{l-1}\]

所以，我们用这个式子来求解每个区间的异或和，可以把每个子段的异或和的和转变为下面式子：（这里 \(p_0\) 默认取 \(0\) 值，因为还需要查询类似 \([1,i]\) 这种区间的值）

\[\sum_{i=1}^{n}\sum_{j=0}^{i-1}p_i\oplus p_j\]

但这个做法的复杂度是 \(O(n^2)\)，不够通过本题的数据范围，所以我们还需要在这个基础上继续优化。

在这个式子中，我们可以观察到，对于每一对 \(i,j\) 不相等的有序数对 \((i,j)\)，\(p_i,p_j\) 都恰好只互相异或了一次。所以，问题又转化为了 \(n\) 个数，其中两两异或的求和。

这个时候会发现推式子已经到达尽头了，再怎么推也不会得到新的结论。必须从其他方面考虑问题，比如异或运算的计算原理的方面。可以考虑把每个数按二进制拆分，在每一位上统计该位的贡献。由于最后是两两异或的求和，所以二进制拆分后打乱不会影响结果。

由于异或的运算法则是如果同位数字不同，那么运算结果的这一位为 \(1\)。我们知道，只有二进制位为 \(1\) 对最终的结果（加和）有贡献，所以我们可以统计二进制结果为 \(1\) 的情况。

对于每一个 \(p_i\)，我们将其按位拆分，并将结果存入计数数组 \(w_{i,j}\) 中。其中 \(i\) 表示第 \(i\) 个二进制位，\(j\) 表示这一位上为 \(j\)（只能为 \(0\) 或 \(1\)），\(w_{i,j}\) 表示在所有数中，第 \(i\) 个二进制位上为 \(j\) 的有 \(w_{i,j}\) 个。

由于这些数中必定两两异或，所以可以直接用乘法原理，求出该位最终为 \(1\) 的个数，最后乘上该位的权值就可以了。所以最后的答案为：（公式中 \(i\) 的范围上界到 \(20\) 是因为题目中说 \(A_i\le2^{20}\)，最多只有 \(21\) 个二进制位）

\[\sum_{i=0}^{20}w_{i,0}\times w_{i,1}\times 2^i\]

时间复杂度 \(O(n)\)，可以通过本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=3e6+200;
int a[N];
int sum[N];
int cnt[2];
int ans;
signed main()
{
//第一眼肯定是前缀异或和
//感觉绝对是正解
//加上二进制拆分，更加稳健了 
//因为只是两两异或，因此每一位都是没有任何影响的
int n;
cin>>n;
rep(i,1,n)
{
    cin>>a[i];
}
rep(i,0,20)
{
rep(j,1,n)
{
    if((a[j]>>i)&1)
    {
        sum[j]=sum[j-1]^1;
    }
    else
    {
        sum[j]=sum[j-1];
    }
}
cnt[1]=cnt[0]=0;
rep(j,0,n)
{
cnt[sum[j]]++;
}
ans+=(1<<i)*cnt[0]*cnt[1];
}
cout<<ans<<'\n';
    return 0;
}

[蓝桥杯 2023 国 B] 抓娃娃

题目描述

小明拿了 \(n\) 条线段练习抓娃娃。他将所有线段铺在数轴上，第 \(i\) 条线段的左端点在 \(l_i\)，右端点在 \(r_i\)。小明用 \(m\) 个区间去框这些线段，第 \(i\) 个区间的范围是 \([L_i, R_i]\)。如果一个线段有 至少一半 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？

输入格式

输入共 \(n + m + 1\) 行。

第一行为两个正整数 \(n, m\)。

后面 \(n\) 行，每行两个整数 \(l_i, r_i\)。

后面 \(m\) 行，每行两个整数 \(L_i, R_i\)。

输出格式

输出共 \(m\) 行，每行一个整数。

样例 #1

样例输入 #1

1
2
3
4
5
6
3 2
1 2
1 3
3 4
1 4
2 3

样例输出 #1

1
2
3
2

提示

评测用例规模与约定

  • 对于 \(20\%\) 的数据，保证 \(n, m \le 10^3\)。
  • 对于 \(100\%\) 的数据，保证 \(n, m ≤ 10^5\)，\(l_i < r_i\)，\(0 < l_i, r_i, L_i, R_i \le 10^6\)，\(\max \{r_i − l_i\} \le \min \{R_i − L_i\}\)。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 H 题

如果过一半，很显然一定过中点，答案合理性显然。但是我们还可以防止小数出现，就是所有坐标乘2，这样就可以避免小数

然后做前缀和加差分即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=2e6+5;
int n,m;
int mp[N];
signed main()
{
    cin>>n>>m;
	int l,r;
	rep(i,1,n)
	{
		cin>>l>>r;
		mp[l+r]++;
	}
    rep(i,1,N)
	{
		mp[i]+=mp[i-1];
	}
	rep(i,1,m)
	{
		cin>>l>>r;
		l*=2;
		r*=2;
		cout<<mp[r]-mp[l-1]<<endl;
	}
    return 0;
}

[蓝桥杯 2022 省 A] 求和

题目描述

给定 \(n\) 个整数 \(a_{1}, a_{2}, \cdots, a_{n}\), 求它们两两相乘再相加的和，即

\[ S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n} \]

输入格式

输入的第一行包含一个整数 \(n\) 。

第二行包含 \(n\) 个整数 \(a_{1}, a_{2}, \cdots a_{n}\) 。

输出格式

输出一个整数 \(S\)，表示所求的和。请使用合适的数据类型进行运算。

样例 #1

样例输入 #1

1
2
4
1 3 6 9

样例输出 #1

1
117

提示

对于 \(30 \%\) 的数据, \(1 \leq n \leq 1000,1 \leq a_{i} \leq 100\) 。

对于所有评测用例, \(1 \leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000\) 。

蓝桥杯 2022 省赛 A 组 C 题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
long long a[100000000];
long long sum[10000000];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	long long ans = 0;
	for ( int i = 1; i <=n ; i++)
	{
		cin >> a[i];
		sum[i] = a[i] + sum[i - 1];
	}

	for (int i = 1; i <n; i++)
	{
		ans += a[i] * (sum[n] - sum[i]);

	}
	cout << ans;



	return 0;
}

[蓝桥杯 2020 省 AB1] 解码

题目描述

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。 例如，连续的 \(5\) 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、aa3a 等）。

对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。为了方便表达，小明不会将连续的超过9个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

输入格式

输入一行包含一个字符串。

输出格式

输出一个字符串，表示还原后的串。

样例 #1

样例输入 #1

1
H3el5o2

样例输出 #1

1
HHHellllloo

提示

对于所有评测用例，字符串由大小写英文字母和数字组成，长度不超过 \(100\)。请注意原来的串长度可能超过 \(100\)。

蓝桥杯 2020 第一轮省赛 A 组 F 题（B 组 G 题）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=2e6+5;
string s;
signed main()
{
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] < '0' || s[i] > '9') {
            if(s[i + 1] < '0' || s[i + 1] > '9') {
                cout << s[i];
                continue;
            }
            for(int j = 1; j <= s[i + 1] - '0'; j++) {
                cout << s[i];
            }
        }
    }
    return 0;
}

[蓝桥杯 2013 省 B] 带分数

题目描述

\(100\) 可以表示为带分数的形式：\(100 = 3 + \frac{69258}{714}\)。

还可以表示为：\(100 = 82 + \frac{3546}{197}\)。

注意特征：带分数中，数字 \(1\) ~ \(9\) 分别出现且只出现一次（不包含 \(0\)）。

类似这样的带分数，\(100\) 有 \(11\) 种表示法。

输入格式

从标准输入读入一个正整数 \(N(N<10^6)\)。

输出格式

程序输出数字 \(N\) 用数码 \(1\) ~ \(9\) 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例 #1

样例输入 #1

1
100

样例输出 #1

1
11

样例 #2

样例输入 #2

1
105

样例输出 #2

1
6

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

我们不如这样想：将 \(a,b,c\) 中的所有数字连在一起，就是一个 \(1\) ~ \(9\) 的全排列？

这样，我们去枚举 \(1\) ~ \(9\) 的全排列

当我们生成一个排列时，只需要枚举两个断点 \(i\) 和 \(j\)，此时下标 \(1\) ~ \(i\) 的就是 \(a\)；\(i+1\) ~ \(j\) 的就是 \(b\)；\(j+1\) 到 \(9\) 的就是 \(c\)。最后判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int t,n,a[10]={0,1,2,3,4,5,6,7,8,9},ans;
signed main()
{
	cin>>n;
	while(1)
    {
		int x=0;
		rep(i,1,7){
			x=x*10+a[i];
			int y=0;
			rep(j,i+1,8){//枚举断点 
				y=y*10+a[j];
				int z=0;
				rep(k,j+1,9){
					z=z*10+a[k];
				} 
				if(y%z==0&&x+y/z==n){//判断是否满足条件 
					ans++;//满足则答案+1 
				}
			}
		}
		next_permutation(a+1,a+9+1);
		//检查，如果此时的全排列又回到第一次的，则跳出循环 
		bool ok=0;
		rep(i,1,9)
        {
			if(a[i]!=i){
				ok=1;
				break;
			}
		}
		if(!ok) break;
	}
	cout<<ans;
	return 0;
}