小心陷阱
思路
採直接模擬並嚴格遵循「先移動、後扣血」。初始化 now = k 表示從位置 0 以步長 k 跳到第一個落點;在 while (k > 0) 的每輪,先依 now 是否分別為 x1、x2 的倍數扣除 y1、y2(可同時扣),若仍 k>0,則續行 now += k 進入下一輪。形式化遞推為
當 now 等於上一輪完成跳躍的落點」,據此流程與題意等價;時間複雜度為回合數的線性時間。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
int k, x1, y1, x2, y2;
cin >> k >> x1 >> y1 >> x2 >> y2;
int now = k;
while (k > 0) {
if (now % x1 == 0) k -= y1;
if (now % x2 == 0) k -= y2;
now += max(0, k);
}
cout << now;
}轉盤得分
思路
以 pos[j] 表示第 j 個輪盤的總旋轉量;每回合讀入位移 x 後做 pos[j] -= x。對每個直欄 i=0..n-1,以安全索引
取得 s[j][idx(i,j)],用陣列 a[26] 統計該欄 m 個字元的頻率,取最大值 MAX 累加至 ans。本質為將每個 s[j] 旋轉 pos[j] 後逐欄取眾數;單回合成本
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
int m, n, k;
cin >> m >> n >> k;
vector<string> s(m);
for (auto &x : s) cin >> x;
vector<int> pos(m, 0);
int ans = 0;
while (k--) {
for (int i = 0; i < m; i++) {
int x; cin >> x;
pos[i] -= x;
}
for (int i = 0; i < n; i++) {
int a[26] = {}, MAX = 0;
for (int j = 0; j < m; j++) {
MAX = max(MAX, ++a[s[j][(((i + pos[j]) % n) + n) % n] - 'a']);
}
ans += MAX;
}
}
cout << ans;
}貪心闖關
思路
以嚴格遞減單調棧 st 模擬「較小堆優先被搬空並併入較大堆」:讀入一堆 x 時,只要 st.back() ≤ x,即將 st.back() 全量加到 ans,並合併至 x(x += st.back())後彈出,直到棧頂 > x 才停止;合併完若 x ≤ t 則把 x 推回 st。全部處理後,再把 st 內殘餘總和加進 ans 即為答案。交換論證可證「先處理較小堆」不劣於任何合法搬運序;每堆至多入棧、出棧各一次,時間複雜度
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
IO
int n, t; cin >> n >> t;
vector<int> st;
long long ans = 0;
for (int i = 0; i < n; i++) {
long long x; cin >> x;
while (!st.empty() && st.back() <= x) {
ans += st.back();
x += st.back();
st.pop_back();
}
if (x <= t) st.push_back(x);
}
for (auto x : st) ans += x;
cout << ans;
}分組遊戲
思路
二分門檻 m。對固定 m,在鄰接表 v 上僅沿「權重 < m」的邊用 vis + BFS/DFS 計算連通塊數 cnt:任兩點若距離 < m 則必須同組,而不同連通塊間距離皆
在距離值域以 l..r 二分最大可行 m:若 f(m) 成立則更新 ans=m, l=m+1,否則 r=m-1。單次檢查 V 為距離值域或不同距離數)。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int n, k;
vector<vector<pair<int,int>>> v;
bool f(int m) {
bitset<505> vis;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
cnt++;
queue<int> q; q.push(i); vis[i] = 1;
while (!q.empty()) {
int t = q.front(); q.pop();
for (auto [nt, x] : v[t]) {
if (vis[nt] || x >= m) continue;
vis[nt] = 1;
q.push(nt);
}
}
}
return cnt >= k;
}
int main() {
IO
cin >> n >> k;
v.resize(n + 1);
int l = INF, r = 0, ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x; cin >> x;
if (i != j) v[i].push_back({j, x});
r = max(r, x);
l = min(l, x);
}
}
while (l <= r) {
int m = (l + r) / 2;
if (f(m)) { ans = m; l = m + 1; }
else r = m - 1;
}
cout << ans;
}
載入留言中…