目录
前言
主播这两天做了一套蓝桥杯的省赛题目（切实感受到了自己有多菜）。
握手问题
分析
填空题的第一道，很简单，不过主播第一次错了（原因是把方案数的+想成了*，被自己蠢笑了）。
这道题如果有一些排列组合的基础的话应该很容易想到答案就是从7加到49。
但这不代表没有排列组合的基础就不会，依然可以写对这道题。（枚举）
排列组合写法
#include<iostream>
using namespace std;
int l;
int main()
{
for(int i = 7; i <= 49; i++)
l += i;
cout << l;
}枚举
#include<iostream>
using namespace std;
int l;
int main()
{
for(int i = 1; i <= 50; i++)
for(int j = i + 1; j <= 50; j++)
{
if(i <= 7 && j <= 7) continue; //选定七个人不握手
l++;
}
cout << l;
}小球反弹
分析
这道题主播依旧没有写出来（）
物理题，首先将速度分解到x和y两个方向，随后整个运动过程就可以看作在x轴上来回运动的同时在y轴上来回运动。
假设在x轴上经过a个来回，在y轴上经过b个来回后回到原点，可得：
移项：
随后我们对a / b进行约分，即：
随后再根据路程和速度即可得出：
最后通过t * v求出路程。
代码
#include<iostream>
#include<cmath>
using namespace std;
int x = 343720, y = 233333;
int dx = 15, dy = 17;
int gcd(int a, int b)
{
if(b == 0) return a;
return gcd(b, a % b);
}
int main()
{
int a = y * dx, b = x * dy;
a /= gcd(a, b); //约分
double t = 2.0 * a * x / dx; //时间
printf("%.2lf", t * sqrt(dx * dx + dy * dy));
return 0;
}好数
分析
观察数据量——1e7枚举每一位的话最大是7 * 1e7，小于1e8所以直接暴力枚举计数即可。（这个主播最开始也是没有想到，去写模拟了）
代码
#include<iostream>
using namespace std;
int l, n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int j = 1, k = i;
l++;
while(k)
{
if((j & 1) != (k & 1))
{
l--;
break;
}
j++;
k /= 10;
}
}
printf("%d", l);
return 0;
}R 格式
分析
发现n很大d也很大，所以考虑高精度。
这道题主要考察了对浮点数的高精度写法，可以在最开始忽略掉小数点，随后进行累乘（高精度 * 低精度），再最后手动进位（高精度 + 低精度）。
主播最开始还去写了高精度*高精度QAQ，最后发现根本没必要，真是蠢到家了。
代码
#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int n;
string l;
vector<int> A, B;
vector<int> cur(vector<int>& A, int b)
{
int x = 0;
vector<int> C;
for(int i = 0; i < A.size(); i++)
{
x += A[i] * b;
C.push_back(x % 10);
x /= 10;
}
while(x)
{
C.push_back(x % 10);
x /= 10;
}
return C;
}
vector<int> add(vector<int>& A, vector<int> B)
{
int x = 0;
vector<int> C;
for(int i = 0; i < A.size() || i < B.size(); i++)
{
if(i < A.size()) x += A[i];
if(i < B.size()) x += B[i];
C.push_back(x % 10);
x /= 10;
}
if(x) C.push_back(1);
return C;
}
int main()
{
cin >> n >> l;
for(int i = l.size() - 1; i >= 0; i--)
{
if(l[i] == '.') continue;
A.push_back(l[i] - '0'); //先不考虑小数点
}
for(int i = 1; i <= n; i++)
A = cur(A, 2); //乘法计算.
// 四舍五入
int i = 0;
for(; i < l.size(); i++)
if(l[i] == '.') break; //找到小数点位置
int x = 0;
int d = l.size() - 1 - i; //小数部分
reverse(A.rbegin(), A.rend()); //反转
for(int k = 0; k < l.size() - 1 - i; k++)
{
x = A.back();
A.pop_back();
} //消除小数部分
reverse(A.rbegin(), A.rend()); //反转
if(x >= 5)
A = add(A, {1}); //进位
for(int i = A.size() - 1; i >= 0; i--)
printf("%d", A[i]);
return 0;
}宝石组合
分析
题意很简单，这道题的主要难点就在于公式的推导。
公式的推导有两种方法，因为主播目前只熟悉一种所以就按照这个思路来讲了。
公式推导基于算数基本定理：
我们将每一项进行质因数分解可得到
同理将Hb于Hc分解质因数可得
我们按照质数进行因式分解，取出其中的一项可得：
随后我们消掉max和min函数，设c1 > d1 > e1，可得：
又
满足最大公因数的条件，我们最后将公式整合可得：
至此我们完成了本道题的第一步
随后我们来查找max(gcd(Ha, Hb, Hc))。
显然对于本道题直接枚举的话会超时，如何来做呢？
可以发现H很小且gcd < H，所以我们可以直接枚举约数。
代码
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int x; scanf("%d", &x);
a[x]++; //存储出现次数
}
for(int i = N - 1; i; i--)
{
int l = 0;
for(int j = i; j < N; j += i)
l += a[j];
if(l >= 3)
{
l = 0;
for(int j = i; j < N && l < 3; j += i)
for(int k = 0; k < a[j] && l < 3; k++, l++)
printf("%d ", j);
break;
}
}
return 0;
}数字接龙
分析
发现数据量很小所以直接搜索就好。
对于本道题的一个细节是如何判断交叉。
主播的建议是存储一个这样的值：read[x + dx][y + dy]
数组内的两个参数是起始坐标和终止坐标。
这样写为什么是正确的呢？
因为只有斜着走的时候才有可能出现交叉的情况，所以每个方向的步长都是1。
很容易发现两个方向是一个奇数和一个偶数，和一定是一个奇数，而若将一个奇数分解为两个相差为1的数字只有两种情况（交换位置）。对于本道题来说正合适。所以写一个这样的数组就可以避免交叉。
代码
#include <iostream>
#include <cstring>
#include <vector>
#define s second
#define f first
using namespace std;
typedef pair<int, int> PII;
const int N = 15;
int n, p;
int map[N][N];
vector<int> to[N][N]; //存储能够到达哪个点，显著降低时间复杂度的小小小优化。
bool read[N][N];
bool cun[2 * N][2 * N]; //防止交叉
vector<int> vtr;
PII s[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; //八个方向
bool dfs(int x, int y, int k)
{
if(x == n && y == n && vtr.size() == n * n - 1)
{
for(int i = 0; i < vtr.size(); i++)
printf("%d", vtr[i]);
return true;
}
if(x == n && y == n) return false;
for(int i : to[x][y])
{
int dx = x + s[i].f, dy = y + s[i].s;
if(read[dx][dy] == false) //第一层筛选
{
if(i & 1 == 0 || cun[x + dx][y + dy] == false) //无交叉
{
read[dx][dy] = true;
if(i & 1) cun[x + dx][y + dy] = true;
vtr.push_back(i);
if(dfs(dx, dy, (k + 1) % p))
return true;
vtr.pop_back();
if(i & 1) cun[x + dx][y + dy] = false;
read[dx][dy] = false;
}
}
}
return false;
}
int main()
{
memset(map, 0x3f, sizeof map);
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &map[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 0; k < 8; k++)
{
int dx = i + s[k].f, dy = j + s[k].s;
if(map[dx][dy] == (map[i][j] + 1) % p)
to[i][j].push_back(k);
}
read[1][1] = true;
if(!dfs(1, 1, 1))
printf("-1");
return 0;
}拔河
分析
最开始以为是dp但是后来发现我想多了。
题目要求两个不相交的区间的差值最小，可以发现无论两个区间又无相交情况差值都是不变的，所以问题就转化成了差值最小的区间问题。
套用模板——首先求出所有区间的和，随后sort之后差值最小的必然会在相邻的两个区间上产生。当然对于本题需要考虑结果是否合法，即：一个区间不可以完全包含另一个区间。（使用区间取交集模板即可）
代码
#include<iostream>
#include<vector>
#include<algorithm>
#define s second
#define f first
using namespace std;
typedef long long LL;
typedef pair<LL, pair<int, int>> PIII;
using namespace std;
const int N = 2010;
int n;
LL s[N];
vector<PIII> vtr;
bool cmp(pair<int, int> A, pair<int, int> B)
{
int x = max(A.f, B.f);
int y = min(A.s, B.s); //查看有没有交集
return x == A.f && y == A.s || x == B.f && y == B.s;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lld", s + i);
s[i] += s[i - 1];
}
LL cnt = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
vtr.push_back({s[j] - s[i - 1], {i, j}});
sort(vtr.begin(), vtr.end());
for(int i = 1; i < vtr.size(); i++)
if(!cmp(vtr[i].s, vtr[i - 1].s))
cnt = min(cnt, vtr[i].f - vtr[i - 1].f);
printf("%lld", cnt);
return 0;
}总结
最后附上ak截图
