第十四届蓝桥杯cb组
(今天蓝桥杯cb组坐牢四个小时,打完后特别想写一篇题解,蒟蒻一枚,没有作完全部题目,仅提供一些思路,若有不足,还望指出与海涵)
A: 瞪眼大法 + 暴力枚举(名字有点花哨,不喜勿喷)
思路:本题比一般的签到题目要复杂一点,由于字符串的长度只有100,因此我们完全可以暴力枚举。不过8位枚举代码量较大,所以我们可以根据题意进行简化,先看出组成年份“2023”后的数组位置,然后从那一位开始枚举。另外:本题使用了set进行去重。
#include <iostream>
#include <set>
using namespace std ;
//前面的数字用来组合出年份,且一定不会涉及到月份,因此运行程序,我们只需将下列的数字输入即可: 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
set<int> q;
int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int cnt ;
int a[20] ;
int main(){
while(cin >> a[cnt]) cnt ++ ;
for(int i =0 ; i< cnt ; i ++) cout << a[i] <<" ";
cout << endl ;
for(int i = 0 ; i < cnt ;i ++){
for(int j = i + 1 ; j < cnt ;j ++){
for(int k = j + 1 ; k < cnt ; k ++){
for(int h = k + 1 ; h < cnt ; h ++){
int m = a[i] * 10 + a[j] ;
int d = a[k] * 10 + a[h] ;
int ans = m * 100 + d ;
if(m >= 1 && m <= 12){
if(d >= 1 && d <= month[m]){
q.insert(ans) ;
}
}
}
}
}
}
for(auto c : q){
cout << c << endl ;
}
cout << q.size() << endl ;
return 0 ;
}
B. 二分
思路:这道题一开始我看错了题意,最后20分钟做回到这道题才弄清楚思路,可惜时间有些紧张,因此这道题目最后没有做出来。但总体思路就是二分,初始设置 l = 1 , r = 23333333/2 , 因为0 的数目小于1 ,函数的图像应该是对称的,所以取半边,此时有单调性,满足二分条件。下面提出一位群友的代码:
#include <iostream>
#include <cmath>
using namespace std;
const double N=11625907.5798;
const int M=23333333;
int x=23333333;
int check(int u){
double m=u*1.0/x;
double sum=0;
sum=-u*m*log2(m)-(x-u)*(1-m)*log2(1-m);
if(sum>=N) return true;
else return false;
}
int main(){
int l=1,r=x;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
C: 二元不等式求交集(数学)
思路:对于输入的每组a,b (这里以60 ,2 为例) , Vmax <= a / b (若大于,则不够) ; Vmin > a /(b + 1) , 在计算中我们可以利用整除的性质,加1得到最终结果
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std ;
int a[20] ;
int mx = 1e9 + 10 , mm = 0 ;
int main(){
int n ;
cin >> n ;
while(n --){
int a, b ;
scanf("%d%d",&a,&b) ;
mx = min(mx , a / b) ;
mm = max(mm , a / (b + 1) + 1) ;
}
cout << mm <<" " << mx;
return 0 ;
}
D: dfs + 回溯 (暴力枚举) 时间复杂度: 10!
思路: 这题基础思路有点像全排列,而额外需要思考的是如何对起止时间与当前时间进行比较。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
int n ;
int a[20],b[20],c[20] ;
bool flag ;
int st[20] ;
int d[20] ;
void dfs(int k ,int sta){
if(k >= n) {
flag = true ;
return ;
}
for(int i = 0 ; i < n ; i ++){
if(!st[i]){
if(sta >= a[i] && sta <= b[i]){
st[i] = 1 ;
d[k] = i ;
dfs(k + 1 ,sta + c[i]) ;
st[i] = 0;
}else if(sta > b[i]){
return ;
}
}
}
}
int main(){
int t ;
cin >> t ;
while(t --){
cin >> n ;
for(int i = 0 ; i < n ; i ++){
cin >> a[i] >> b[i] >> c[i] ;
b[i] += a[i] ;
}
flag = false ;
memset(st,0,sizeof st) ;
dfs(0,0) ;
if(flag) printf("YES\n") ;
else printf("NO\n") ;
}
return 0 ;
}
E: 求最长上升子序列的变题 贪心/DP 时间复杂度: n^2 / nlogn
思路:考场上只能想到用n^2级别的动态规划来解决,但数据集是10^5,因此肯定有我没有想到的地方,希望会的人能为我解惑。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
const int N = 1e5 + 10 ;
int n ;
int a[N],b[N] ;
int f[N] ;
int res ;
int main(){
cin >> n ;
for(int i = 1 ; i <= n ; i ++)
{
int x ;
cin >> x ;
b[i] = x % 10 ;
while(x / 10) x /= 10 ;
a[i] = x ;
}
for(int i = 1; i <= n ; i ++){
f[i] = 1 ;
for(int j = 1 ; j < i ; j ++){
if(a[i] == b[j])
f[i] = max(f[i],f[j] + 1) ;
}
}
cout << n - res ;
return 0;
}
F: dfs? + bfs
感想:这道题目我没有做出来,其实感觉不难,但关键问题是:如何准确判断一整趟bfs后得到的一系列点有无构成环,考场上怎么想也想不到,下方代码只能解决无环的数据
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std ;
const int N = 60;
typedef pair<int,int> PII ;
int st[N][N] ;
char e[N][N];
int dx[4] = {0,0,1,-1} , dy[4] = {1,-1,0,0} ;
int n , m ;
int sx , sy ;
bool flag ;
void bfs(int x ,int y){
queue<PII> q ;
q.push({x,y}) ;
st[x][y] = 1 ;
while(q.size()){
auto t = q.front();
q.pop() ;
for(int i = 0 ; i < 4 ; i++){
int a = t.first + dx[i] ;
int b = t.second + dy[i] ;
if(a >= 1 && a <= n && b>= 1 && b <= m && !st[a][b] && e[a][b] == '1')
{
st[a][b] = 1 ;
q.push({a,b});
}
}
}
}
void dfs(int x ,int y ){
if(x == sx && y == sy){
flag = true ;
return ;
}
st[x][y] = 1;
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i] ;
int b = y + dy[i] ;
if(a>=1 && a <= n && b >= 1&& b <= m && e[a][b] == '1' && !st2[a][b]){
dfs(a,b) ;
}
}
}
int main(){
int t ;
cin >>t ;
while(t -- ){
memset(st, 0 ,sizeof st) ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i ++){
getchar() ;
for(int j =1; j <= m ; j ++){
cin >> e[i][j] ;
}
}
int cnt = 0 ;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ;j <= m ; j ++){
if(!st[i][j] && e[i][j] == '1'){
bfs(i, j ) ;
// flag = false ;
// sx= i ;
// sy = j ;
// dfs(i,j) ;
//
// if(flag){
//
// }
cnt ++ ;
}
}
}
cout << cnt << endl;
}
return 0 ;
}
G: 数学思维?
思路:咱们可以先从后往前遍历字符串,记录c2字符数目的增加情况,并用一个数组保存。然后我们再从头遍历字符串,遇到c1字符,我们就在当前位置+k-1,此时这个位置的数组保存这后面可能碰到的所有c2字符的数目,累加即可得到最后答案。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
const int N = 5e5 + 10;
typedef long long LL ;
string a ;
int cnt[N] ;
LL res ;
int main(){
char c1,c2;
int k ;
cin >> k ;
cin >> a >> c1 >> c2 ;
int sum = 0 ;
for(int i = a.size() - 1; i >= 0 ; i --){
if(a[i] == c2) sum ++;
cnt[i] = sum ;
}
for(int i = 0 ; i < a.size() ; i ++){
if(a[i] == c1){
res = res + cnt[i + k - 1];
}
}
cout << res << endl ;
return 0 ;
}
H: 不会,只能n^2 模拟, 不像贪心,可能是什么线段树之类的??(蒟蒻还没学到)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
const int N = 5e5 + 10;
typedef long long LL ;
string a ;
int cnt[N] ;
LL res ;
int main(){
char c1,c2;
int k ;
cin >> k ;
cin >> a >> c1 >> c2 ;
int sum = 0 ;
for(int i = a.size() - 1; i >= 0 ; i --){
if(a[i] == c2) sum ++;
cnt[i] = sum ;
}
for(int i = 0 ; i < a.size() ; i ++){
if(a[i] == c1){
res = res + cnt[i + k - 1];
}
}
cout << res << endl ;
return 0 ;
}
I: LCA(考场上想到了最近公共祖先,但不会背板子,现场更推不出来),因此只能用floyd骗个基础分。
思路:本题数据集范围给到10^5 , 因此应该是nlogn算法,而通读题目,我们会发现基础的K次情况已经占掉了n,所以只剩下logn给我们去找两个点之间的距离。因为邻接矩阵+dij的板子背的不熟,所以最后只能用floyd过100以内的数据集。我们可以先求出总路径的长度sum(nlogn) ,然后对于k个站,每次去除一个点,对sum进行一定的加减,总的时间复杂度也是nlogn.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std ;
const int N = 1010;
int d[N][N] ;
int a[N] ;
const int INF = 1e5 + 10 ;
int res ;
int main(){
int n , m ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j<= n ; j ++){
if(i == j) d[i][j] = 0;
else d[i][j] = INF ;
}
}
for(int i = 0 ; i < n - 1 ; i ++){
int a, b ,c ;
cin >> a >> b >> c;
d[a][b] = c ;
d[b][a] = c ;
}
for(int k = 1; k <= n ; k ++){
for(int i = 1; i <= n ; i ++){
for(int j = 1 ; j <= n ; j ++){
d[i][j] = min(d[i][j] , d[i][k] + d[k][j]) ;
}
}
}
for(int i = 0 ; i < m ; i ++) cin >> a[i] ;
int st = a[0] ;
int sum = 0 ;
for(int i = 1 ; i < m ; i ++){
sum += d[a[i - 1]][a[i]] ;
}
for(int i = 0 ; i < m ; i++){
if(i == 0){
res = sum - d[a[0]][a[1]] ;
}else if(i == m - 1){
res = sum - d[a[i-1]][a[i]] ;
}else{
res = sum - d[a[i-1]][a[i]] - d[a[i]][a[i+1]] + d[a[i-1]][a[i + 1]] ;
}
cout << res << " " ;
}
return 0;
}
J:不会(doge)
tql
E可以从后往前dp位置i开始的j数字开头的最长cnt
dp[fir] = max(dp[fir], dp[sec] + 1), fir是当前数字的开头, sec是结尾, 滚动掉了第一维, 这样就O(n)了
然后n - 最长的 = 最少删除的
当然从前往后也一样
orz,话说佬觉得今年难度和往年相比如何
同问
C题代码原来这么简单?不是说要用什么二分吗
二分也是求 最小值里面的最大值 最大值里面的最小值
强
佬!