第十四届蓝桥杯cb组国赛分享
吐槽部分:出题样例错了好几个，考试过程中修改多次，甚至有一题好像是”抓娃娃”改了两次样例，看不懂
心得:本次考试做填空题的时候稍微有点慌，因为对时间复杂度有着较高的要求，导致我不屑于写很暴力的做法。然后上来两道填空，数据量看上去都不小，楞是磨了半个小时，才有一些思路。后面的题做的马马虎虎，但是最后一道题目自己感觉做出来了，回校在车上突然想到自己忘记给概率p了，直接贴了样例的0.8，郁闷到吐血，原本信心满满，突然又有点绝望……
A:提取2，0，3数字（我是倒序提取，因此从大到小遍历），然后翻转，最后三重循环加前缀后解决，答案:5484660609
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std ;
const int N = 1e6 + 10;
int dx[]= {0 ,0 ,1 ,-1};
int dy[] = {1, -1 , 0 , 0 } ;
int cnt ;
int a[N] , b[N] ,s[N];
int res ;
signed main(){
int n ;
for(int i = 2023 ;i >= 1 ; i --){
int k = i ;
while(k){
int m = k % 10 ;
if(m == 2 || m == 0 || m == 3){
a[++ cnt] = m ;
}
k /= 10;
}
}
for(int i =1 ;i <= cnt ;i ++)
{
b[i] = a[cnt + 1 -i ] ;
//cout<< b[i] ;
}
for(int i = 1; i <= cnt ; i ++){
if(b[i] == 3){
s[i] = 1;
}
s[i] += s[i - 1] ;
}
for(int i =1 ; i<= cnt ; i++){
if(b[i] == 2){
for(int j = i + 1; j <= cnt ; j ++){
if(b[j] == 0){
for(int k = j + 1 ; k <= cnt ; k ++){
if(b[k] == 2){
res += s[cnt] - s[k] ;
}
}
}
}
}
}
cout << res ;
return 0 ;
}
B:
这道题的话，我们可以采用先筛素数后枚举的方法来解决。根据数据范围，我们可以推出最大的范围内最大的质数为2415230，平方乘以四要小于23333333333333.然后我们找出小于这个数的所有质数，开n^2枚举，判断范围，如果超过了最大值则直接break(优化时间复杂度)。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <cmath>
#define int long long
using namespace std ;
const int N = 1e7 + 10;
int dx[]= {0 ,0 ,1 ,-1};
int dy[] = {1, -1 , 0 , 0 } ;
int cnt ;
int a[N] , b[N] ,s[N];
int res ;
int M = 23333333333333 ;
int mx = sqrt(M / 4) + 1;
bool st[N] ;
int prime[N] ;
void init(){
for(int i = 2 ; i < mx ; i ++){
if(!st[i]){
prime[cnt ++] = i ;
}
for(int j = 0 ; prime[j] * i < mx ; j ++){
st[i * prime[j]] = true ;
if(i % prime[j] == 0 ) break ;
}
}
}
signed main(){
int n ;
//cout << mx << endl ;
init() ;
//cout<< cnt << endl ;
//cin >> n ;
int res = 0 ;
for(int i = 0 ; i < cnt ; i ++){
for(int j = 0 ; j < cnt; j ++){
if(i != j){
int ans = prime[i] * prime[i] * prime[j] * prime[j ] ;
if(ans >= 2333 && ans <= M){
res ++ ;
}else if(ans > M){
break ;
}
}
}
}
cout << res ;
return 0 ;
}
C.
这道题是一道一般的思维题。解题的关键在于区分id个数 <2 和 >= 2 的 id号，前者可以直接累加，后者则需要减去2后累加，两者需要分别进行累加。（原因？这里举个例子：4，4，4，4，8，8，8，8，读者可以自己推一下就明白分开累加的必要性了）。然后比较两者的大小，若前者大于后者，则相加除2，否则，取后者大小。（id比较小，可以用数组存储，不然就用map）
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <cmath>
#define int long long
using namespace std ;
const int N = 1e5 + 10;
int dx[]= {0 ,0 ,1 ,-1};
int dy[] = {1, -1 , 0 , 0 } ;
int cnt ;
int a[N] , b[N] ,s[N];
int res ;
signed main(){
int n ;
cin >> n ;
for(int i = 0 ; i< n ; i ++){
int x ;
cin >> x ;
s[x] ++ ;
}
int ans1 = 0 ;
int ans2 = 0 ;
for(int i = 1 ;i <= n ; i ++){
if(s[i] >= 2){
ans2 += s[i] - 2 ;
}else{
ans1 += s[i] ;
}
}
if(ans1 >= ans2 ){
cout << (ans1 + ans2) / 2 ;
}else{
cout << ans2 ;
}
return 0 ;
}
D: 合并数列
思路：模拟题，抓住顺序相等的关键，我们可以从一头模拟到另一头，把当前位置数值小的数组进行累加，反复操作直至最后
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <cmath>
#define int long long
using namespace std ;
const int N = 1e5 + 10;
int dx[]= {0 ,0 ,1 ,-1};
int dy[] = {1, -1 , 0 , 0 } ;
int cnt ;
int a[N] , b[N] ,s[N];
int res ;
signed main(){
int n , m ;
cin >> n >> m ;
for(int i = 1; i<= n ; i ++) cin >> a[i] ;
for(int i = 1; i <= m ; i ++) cin >>b[i] ;
int i = 1 , j = 1 ;
while(i <= n && j <=m){
if(a[i] == b[j]){
i ++ ;
j ++ ;
}else if(a[i] < b[j]){
int k = 0 ;
do{
a[i + 1] += a[i] ;
k ++ ;
i ++ ;
}while(i <= n && a[i] < b[j]) ;
res += k ;
}else{
int k = 0 ;
do{
b[j + 1] += b[j] ;
k ++ ;
j ++ ;
}while(j <= m && a[i] > b[j]) ;
res += k ;
}
}
cout << res << endl ;
return 0 ;
}
E: 数三角（个人感觉做到的比较繁琐的一道题目，如果没有熟练掌握stl可能比较难受,得用好set 和 map）
思路： 我的选择是枚举每个点，然后遍历这个点的所有彼，用map来存取每种长度边的个数（2条以上，即可构建等腰三角形），注意：这里面会存在共线的情况，我们需要将其特判掉——我的做法是，用中点公式反推另一个点是否存在，若存在则记录。最后我们先用组合数的公式C几取2累加，然后减去 （记录的个数/ 2） 即可。
后续更新
F: 删边问题
思路：这道题目我不会做，好像是什么tarjan算法
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
int main(){
cout << "i can't do it " << endl ;
}
G: AB路线(bfs)
思路：
……后续再更新
H: 抓娃娃（感觉像线段树），但我只会暴力 O(n^2)
枚举每一个区间，判断在区间内的线段长度
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <cmath>
#define x first
#define y second
#define int long long
using namespace std ;
const int N = 1e5 + 10;
typedef pair<int,int> PII ;
PII a[N] ;
int ans[N] ;
int res;
signed main(){
int n , m ;
cin >> n >> m ;
for(int i =1 ; i<= n ; i ++){
int l ,r ;
cin >> l >> r ;
a[i] = {l ,r } ;
}
for(int i = 1 ;i <= m ; i ++){
int l ,r ;
cin >> l>> r ;
for(int j = 1 ; j <= n ; j ++){
int dd = a[j].y - a[j].x ;
int ll = max(a[j].x , l) ;
int rr= min(a[j].y , r) ;
if((rr - ll)* 2 >= dd) ans[i] ++ ;
}
}
for(int i =1 ; i<= m; i ++)
cout << ans[i] << endl ;
return 0 ;
}
I: 拼数字 – 不会， 只能dfs一下，不知道有没有分 ,dfs只能到long long范围，但是题目20%最大是24位
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <cmath>
#define int long long
using namespace std ;
const int N = 1e5 + 10;
unordered_set<int> s ;
int res ;
void dfs(int cnt , int n , int m){
if(n == 0 && m == 0 ){
if(cnt % 2023 == 0 )
res = max(res, cnt) ;
return ;
}
if(n) dfs(cnt * 10 + 2 , n - 1 , m ) ;
if(m) dfs(cnt * 10 + 3 , n , m -1) ;
}
signed main(){
int n , m ;
cin >> n >> m ;
dfs(0 , n , m );
cout << res << endl ;
return 0 ;
}
J:树形dp(推公式) – 可恶， 然而， 生气
AB路线 的 代码 啥时候跟新？
I题用__int128骗分
感觉自己就拿了50分
好多
倒数第二题 对字符串边转化为整数边取模可以避免爆long long，最后输出字符串即可
第二个填空应该还要 / 2
最后一题我是dfs一遍求每个点的最近跳板，然后宽搜处理距离，如果没有跳板则距离就是层数，有跳板就是起点到跳板的距离+1和层数取个概率平均。
第一个填空原来是这么做，整场比赛我就正解做出来了C题， 看到差距了，刷的题太少了
第二个填空我想的是筛质数，然后循环，我记得bfs那个有个注意点，是按照层次来搜索
ｄ题原来这么简单我想太复杂了
d题我感觉你想复杂了，其实只要保持两个指针从前到后遍历即可
D我用前缀和做的，不会寄了吧emm
哥们知道三等要做多少分吗