第十四届蓝桥杯C/C++大学A组题解（部分）

喜报！块有了！

蒟蒻喜提组烂尾巴省一。总体来说，今年的填空貌似没有组难，虽然我也写错了一道就是了。后面的板子题也是越来越少了（相比去年三道线段树这种神奇操作），虽然还是可以暴力骗很多分。

下面就讲讲我过了的和部分没过的题叭！

原题

填空题

两道填空题都还比较简单，都是暴力搜索或者枚举就可以了，这里就只讲一波思路。

题：幸运数

答案：

小小模拟罢了，写出计算位数和判断前后位数的函数，暴力跑一遍就过了。（无思维量

题：有奖问答

答案：

这题考场上写错了，曲解题意了，以为小蓝答完题才会润，按照题目的意思应该是小蓝随时可能会润。

写个爆搜就可以跑过啦！

#include<iostream>
using namespace std;
int ans;
void dfs(int step, int score) {
    // == 70要放在==100和return;前
    if(score == 70) ans++; //此时不需要return;
    //30题答完或分数达到100
    if(step == 31 || score == 100) return;
    //分治递归
    dfs(step + 1, score + 10); //答对
    dfs(step + 1, 0); //答错
}
int main(void) {
    dfs(1, 0); //第1题, 分数0开始
    cout << ans << endl;
    return 0;
}

编程题

题：平方差

思路：

不戳的一道数论基础题，不难但没动脑的肯定写不出来，其实就是保留奇数和的倍数。

看数据范围一眼就知道正解应该是的。

证明一波：

相邻两数的平方差为奇数：

空一个数的两数平方差为的倍数：

剩余数都包含在上面两种数中：（）

当，均为偶数时，与必定均为的倍数，此时结果必为的倍数。

当，为一奇一偶时，此时结果必为奇数。

当，均为奇数时，设，，此时有：

结果必为的倍数

（应该没错吧）

因此，我们只需要统计中，奇数与的倍数的个数即可。

代码：

#include<iostream>
using namespace std;
typedef long long LL;
LL L, R;
LL f(LL x) {
    return x - x / 4 - (x % 4 >= 2);
}
int main(void) {
    cin >> L >> R;
    cout << f(R) - f(L - 1) << endl;
    return 0;
}

题：更小的数

思路：

一眼区间，状态定义：为第个字符到第个字符是否可以翻转。

状态转移方程：

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 5010;
int dp[N][N], ans;
char str[N];
int main(void) {
    cin >> (str + 1);
    int n = strlen(str + 1);
    for (int len = 1; len < n; len++) {
        for (int i = 1; i + len <= n; i++) {
            int j = i + len;
            if (str[i] < str[j]) dp[i][j] = 0;
            else if (str[i] > str[j]) dp[i][j] = 1;
            else dp[i][j] = dp[i + 1][j - 1];
            ans += dp[i][j];
        }
    }
    cout << ans << endl;
    return 0;
}

题：颜色平衡树（考场%）

思路：

考场上写了个后序遍历，骗了%的分。

当为叶子节点时，必定是颜色平衡树。

当不为叶子节点时，统计左子树和右子树的各颜色数量，加上当前节点颜色，遍历一次判断是否为颜色平衡树。

时间复杂度：

水了%的分。

题：买瓜（搜索：我也不确定考场上能不能全过）

思路：

搜索剪枝，剪枝策略如下：

1. 剩余的瓜全买也不足
2. 当前的重量大于
3. 当前的瓜数大于等于答案
4. 当前状态如果取到 和目前最优解一样的瓜数 也达不到重量

代码：

代码就不写了，爆搜剪枝慢慢调试罢了。

题：异或和之和（考场%）

思路：

这题也是骗了%，理解了题意就能骗，说白了就是一个前缀异或和，轻松水分。

异或前缀和公式：

求解：

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define debug(a) cout << #a << " = " << a << endl
#define PI acos(-1)
#define lowbit(x) (x&-x)

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;

const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

const int N = 1e5 + 10;

int T, n, a[N], s[N], ans;

void solve(void) {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = a[i] ^ s[i - 1];
	}
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			ans += s[r] ^ s[l - 1];
		}
	}
	cout << ans << endl;
}

signed main(void) {

	IOS;
	T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}