第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组
新手，乱写的，有错误和改进下面评论就行。。 先放个代码，吃完饭回来写具体的题解。
A 九进制转十进制
1478
B 顺子日期
题目有歧义，我个人偏向于14
14 (4)
C 刷题统计
我是Sb，没看数据范围，典型0分答案↓。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
signed main()
{
ios::sync_with_stdio(false);
int a, b, n; cin>>a>>b>>n;
int sum = 0, day = 0;
while(sum < n)
{
day ++;
if(day % 7 == 6 || day % 7 == 0) sum += b;
else sum += a;
}
cout<<day<<endl;
return 0;
}
D 修剪灌木
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
signed main()
{
ios::sync_with_stdio(false);
int n; cin>>n;
for(int i = 1;i <= n;i ++)
cout<<max(i - 1, n - i) * 2<<endl;
return 0;
}
E X 进制减法
数据规定了 , 每一位的进制选最小可以取的即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1000000007;
int numa[N], numb[N];
int jin[N];
signed main()
{
ios::sync_with_stdio(false);
int n; cin>>n;
int ma; cin>>ma;
for(int i = 1;i <= ma;i ++) cin>>numa[i];
for(int i = 1, j = ma;i < j;i ++, j --) swap(numa[i], numa[j]);
int mb; cin>>mb;
for(int i = 1;i <= mb;i ++) cin>>numb[i];
for(int i = 1, j = mb;i < j;i ++, j --) swap(numb[i], numb[j]);
for(int i = 1;i <= max(ma, mb);i ++)
jin[i] = max(2ll, max(numa[i], numb[i]) + 1);
int res = 0, base = 1;
for(int i = 1;i <= max(ma, mb);i ++)
{
res = (res + (numa[i] - numb[i]) * base % mod + mod) % mod;
base = base * jin[i] % mod;
}
cout<<res<<endl;
return 0;
}
F 统计子矩阵
洛谷原题，正解是前缀和+枚举+滑动窗口，时间复杂度是
下面代码是我比赛时写的非正解，前缀和+枚举+二分， 时间复杂度是，估计只能通过一半左右数据。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
ll a[N][N];
ll sum[N][N];
ll get(int x1, int y1, int x2, int y2)
{
return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
signed main()
{
ios::sync_with_stdio(false);
ll n, m, k; cin>>n>>m>>k;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin>>a[i][j];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
int res = 0;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
for(int ii = 1;ii <= i;ii ++)
{
int l = 0, r = j;
while(l < r)
{
int mid = (l + r + 1) >> 1;
int jj = j - mid + 1;
if(get(ii, jj, i, j) <= k) l = mid;
else r = mid - 1;
}
res += l;
}
}
}
cout<<res<<endl;
return 0;
}
G 积木画
我太菜辣，典型0分答案↓。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
const int mod = 1000000007;
ll f[N];
signed main()
{
ios::sync_with_stdio(false);
int n; cin>>n;
f[0] = 1;
for(int i = 0;i <= n;i ++)
{
f[i + 1] = (f[i + 1] + f[i]) % mod;
f[i + 2] = (f[i + 2] + f[i]) % mod;
f[i + 3] = (f[i + 3] + f[i] * 2) % mod;
f[i + 4] = (f[i + 4] + f[i] * 2) % mod;
}
cout<<f[n];
return 0;
}
H 扫雷
非正解，暴力枚举出相邻的炸雷 然后多端bfs
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
vector<int> e[N];
int xi[N], yi[N], ri[N];
int xj[N], yj[N], rj[N];
bool vis[N];
int dist(int x1, int y1, int x2, int y2)
{
int dx = x1 - x2;
int dy = y1 - y2;
return dx * dx + dy * dy;
}
signed main()
{
ios::sync_with_stdio(false);
int n, m; cin>>n>>m;
for(int i = 1;i <= n;i ++) cin>>xi[i]>>yi[i]>>ri[i];
for(int j = 1;j <= m;j ++) cin>>xj[j]>>yj[j]>>rj[j];
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
{
if(i == j) continue;
int dis = dist(xi[i], yi[i], xi[j], yi[j]);
if(dis <= ri[i] * ri[i]) e[i].push_back(j);
}
queue<int> que;
for(int i = 1;i <= n;i ++)
{
if(vis[i]) continue;
for(int j = 1;j <= m;j ++)
if(dist(xi[i], yi[i], xj[j], yj[j]) <= rj[j] * rj[j])
{
que.push(i);
vis[i] = true;
}
}
while(!que.empty())
{
int tot = que.front(); que.pop();
for(int i = 0;i < e[tot].size();i ++)
{
int v = e[tot][i];
if(!vis[v])
{
que.push(v);
vis[v] = true;
}
}
}
int res = 0;
for(int i = 1;i <= n;i ++)
if(vis[i]) res ++;
cout<<res<<endl;
return 0;
}
I 李白打酒加强版
简单dp，注意必须最后一次遇到的是花
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 100 + 10;
const int mod = 1000000007;
int f[N][N][N];
signed main()
{
ios::sync_with_stdio(false);
int n, m; cin>>n>>m;
f[0][0][2] = 1;
for(int i = 0;i <= n;i ++)
{
for(int j = 0;j <= m;j ++)
{
for(int k = 0;k <= 100;k ++)
{
if(k * 2 <= 100 && i < n && j < m)
f[i + 1][j][k * 2] = (f[i + 1][j][k * 2] + f[i][j][k]) % mod;
if(k > 0 && j < m)
f[i][j + 1][k - 1] = (f[i][j + 1][k - 1] + f[i][j][k]) % mod;
}
}
}
cout<<f[n][m][0]<<endl;
return 0;
}
J 砍竹子
双端链表 + 优先队列
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int pre[N], nxt[N];
int a[N];
bool vis[N];
signed main()
{
ios::sync_with_stdio(false);
int n; cin>>n;
for(int i = 1;i <= n;i ++) cin>>a[i];
for(int i = 1;i <= n;i ++)
pre[i] = i - 1, nxt[i] = i + 1;
priority_queue<pair<int, int>> heap;
for(int i = 1;i <= n;i ++)
heap.push(make_pair(a[i], i));
int res = 0;
while(!heap.empty())
{
int tot = heap.top().second, h = heap.top().first;
heap.pop();
if(vis[tot] || h <= 1) continue;
int idx = tot;
while(!vis[nxt[idx]] && a[nxt[idx]] == h)
{
idx = nxt[idx];
vis[idx] = true;
}
nxt[tot] = nxt[idx];
pre[nxt[idx]] = tot;
idx = tot;
while(!vis[pre[idx]] && a[pre[idx]] == h)
{
idx = pre[idx];
vis[idx] = true;
}
pre[tot] = pre[idx];
nxt[pre[idx]] = tot;
a[tot] = (int)(sqrt(h / 2 + 1));
res ++;
}
cout<<res<<endl;
return 0;
}
京公网安备 11010502036488号