C. 冶煉金屬
最大值就是取 a / b a / b a/b 的最小值，最小值就是二分找到滿足 m i d ? ( b i + 1 ) ≥ a i mid * (b_i + 1) ≥ a_i mid?(bi?+1)≥ai? 的最小值
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
int l = 0, r = 1e9;
auto check = [&](int mid)
{
for (int i = 0; i < n; i++)
if (mid * (a[i].y + 1) <= a[i].x) return false;
return true;
};
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << ' ';
int minn = 1e9;
for (int i = 0; i < n; i++)
minn = min(minn, a[i].x / a[i].y);
cout << minn << '\n';
}
signed main()
{
// freopen("Sample.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
// cout << "Time:" << (double)clock() / 1000 << '\n';
return 0;
}
D. 飛機降落
全排列枚舉所有降落方案，然后判斷即可
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> t(n + 10), d(n + 10), l(n + 10);
for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];
vector<int> p(n);
for (int i = 0; i < n; i++) p[i] = i;
do {
int tt = 0;
bool flag = true;
for (int i = 0; i < n; i++)
{
int x = p[i];
if (tt > t[x] + d[x])
{
flag = false;
break;
}
tt = max(tt, t[x]);
tt += l[x];
}
if (flag)
{
cout << "YES" << '\n';
return;
}
} while (next_permutation(p.begin(), p.end()));
cout << "NO" << '\n';
}
signed main()
{
// freopen("Sample.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) solve();
// cout << "Time:" << (double)clock() / 1000 << '\n';
return 0;
}
E. 接龍數(shù)列
狀態(tài)定義： f [ i , j ] f[i, j] f[i,j] 為前 i i i 個數(shù)，以 j j j 結(jié)尾的最長合法子序列，答案就是 n ? m a x n - max n?max
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n;
cin >> n;
map<int, int> mp;
vector<int> a(n);
vector<pair<int, int>> b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
{
b[i].y = a[i] % 10;
int x = a[i];
while (x >= 10) x /= 10;
b[i].x = x;
}
int ans = 0;
for (int i = 0; i < n; i++)
{
int x = mp[b[i].x];
mp[b[i].y] = max(mp[b[i].y], x + 1);
ans = max(ans, mp[b[i].y]);
}
cout << n - ans << '\n';
}
signed main()
{
// freopen("Sample.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
// cout << "Time:" << (double)clock() / 1000 << '\n';
return 0;
}
F. 島嶼個數(shù)
考場上沒什么思路，隨便寫了個Flood Fill就潤了
G. 字串簡寫
處理 b b b 的前綴和，然后掃一遍即可
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int k;
cin >> k;
string s;
char a, b;
cin >> s >> a >> b;
int n = s.size();
s = " " + s;
vector<int> B(n + 10);
for (int i = 1; i <= n; i++)
if (s[i] == b) B[i] ++;
for (int i = 1; i <= n; i++) B[i] += B[i - 1];
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (s[i] == a)
{
if (i + k - 1 > n) continue;
ans += B[n] - B[i + k - 2];
}
}
cout << ans << '\n';
}
signed main()
{
// freopen("Sample.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
// cout << "Time:" << (double)clock() / 1000 << '\n';
return 0;
}
H. 整數(shù)刪除
首先初始化下每個數(shù)的前驅(qū)和后繼
開一個小根堆，把所有數(shù)的大小和位置都放進去
每次循環(huán)，拿到數(shù)組中最小的數(shù)，標記上位置，然后操作它和它的前驅(qū)后繼
但是可能拿到的數(shù)，已經(jīng)被改變過了，所以我們需要開一個 m a p map map ，記錄下每個位置被改變過多少次
最后把沒有被標記的數(shù)輸出即可文章來源：http://www.zghlxwxcb.cn/news/detail-410422.html
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pair<int, int>> b(n + 10);
for (int i = 1; i <= n; i++) b[i] = {i - 1, i + 1};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
for (int i = 1; i <= n; i++) heap.push({a[i], i});
map<int, int> mp;
vector<bool> st(n + 10);
for (int i = 0; i < k; i++)
{
while (mp[heap.top().y])
{
mp[heap.top().y] --;
heap.pop();
}
auto t = heap.top();
heap.pop();
st[t.y] = true;
int l = b[t.y].x, r = b[t.y].y;
b[l].y = r, b[r].x = l;
a[l] += t.x, a[r] += t.x;
mp[l] ++, mp[r] ++;
if (l) heap.push({a[l], l});
if (r <= n) heap.push({a[r], r});
}
for (int i = 1; i <= n; i++)
if (!st[i]) cout << a[i] << ' ';
}
signed main()
{
// freopen("Sample.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
// cout << "Time:" << (double)clock() / 1000 << '\n';
return 0;
}
寫在最后
剩下兩題都是LCA好像，不太會，導(dǎo)游暴力Floyd騙分，最后一題沒讀完題，輸出樣例后就選擇去檢查了，上述幾題都過了民間數(shù)據(jù)了，應(yīng)該問題不大，很好啊，好像省一穩(wěn)了？噢，原來有人賽時沒開long long沒關(guān)同步流啊，為什么沒呢？很簡單啊，怕過不了編譯，然后就真忘了，我是傻逼文章來源地址http://www.zghlxwxcb.cn/news/detail-410422.html
到了這里，關(guān)于第十四屆藍橋杯編程題部分代碼題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
