中級
彗星撞擊
思路
模擬並逐格更新。初始化 v 為大小 n×m、每格值為 x,並用 have 標記先給定的目標格。對每一個操作(程式中第二個 k 讀入的那批查詢,參數為 a,b,s,d),計算正方形區域
(程式以 0-based 索引,遇到超出邊界的 have[i][j] == 1,則將該區域內所有 have[i][j] 設為 0(表示被移除);否則對區域內每格執行 v[i][j] -= d(扣除耐久)。此策略嚴格按照題意的「若區域內有目標則移除,否則造成傷害」執行,故最後統計最大值 mx = max(v[i][j])、最小值 mn = min(v[i][j]) 與剩餘目標數 cnt = sum(have[i][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 n, m, x;
cin >> n >> m >> x;
vector<vector<int>> v(n, vector<int>(m, x));
vector<vector<int>> have(n, vector<int>(m));
int k;
cin >> k;
while (k--) {
int a, b;
cin >> a >> b;
have[a][b]++;
}
cin >> k;
while (k--) {
int a, b, s, d;
cin >> a >> b >> s >> d;
bool flag = 0;
for (int i = a - (s - 1) / 2;i <= a + (s - 1) / 2;i++) {
for (int j = b - (s - 1) / 2;j <= b + (s - 1) / 2;j++) {
if (i < 0 or i >= n or j < 0 or j >= m) continue;
if (have[i][j]) {
have[i][j] = 0;
flag = 1;
}
}
}
if (!flag) {
for (int i = a - (s - 1) / 2;i <= a + (s - 1) / 2;i++) {
for (int j = b - (s - 1) / 2;j <= b + (s - 1) / 2;j++) {
if (i < 0 or i >= n or j < 0 or j >= m) continue;
v[i][j] -= d;
}
}
}
}
int mx = 0, mn = INF, cnt = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cnt += have[i][j];
mx = max(mx, v[i][j]);
mn = min(mn, v[i][j]);
}
}
cout << mx << ' ' << mn << ' ' << cnt;
}航空拍照圖
思路
以「對矩陣 (a) 做 90° 旋轉並比對」的思路。定義旋轉函數 (f)(將 (a) 順時針旋轉 90°):
其中原矩陣 (a) 的大小為
維護最大重合數
時間 / 空間複雜度(以原始
- 每次旋轉 (f) 建構新矩陣需
,每次相等性檢查需 。總共最多做 4 次,故時間複雜度為
- 額外空間用於儲存旋轉後的矩陣與原矩陣,空間複雜度為
程式碼
#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();
vector<vector<int>> f(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<int>> t(m, vector<int>(n));
for (int i = 0;i < m;i++) {
for (int j = 0;j < n;j++) {
t[i][j] = a[n - 1 - j][i];
}
}
return t;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> a[i][j];
}
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> b[i][j];
}
}
int s = 0;
for (int k = 0;k < 4;k++) {
if (a.size() == b.size() and a[0].size() == b[0].size()) {
int now = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (a[i][j] == b[i][j]) now++;
}
}
s = max(s, now);
}
a = f(a);
}
cout << (100 * s) / (n * m) << '%';
}商品包裝地
思路
逐筆讀入長度為 13 的字串 x,將前 12 位分成「奇數位」與「偶數位」兩組(程式以 0-based 索引,條件為 (i+1)%2 判斷奇偶),計算
將第 13 位記作
判定合法條件 if (k == 0 or k == 10),其數學意義等價於
也就是「前 12 位按奇偶位加權求和,再加上第 13 位,模 10 等於 0」時視為一筆合法資料(符合 ISBN/檢查碼類似的檢核邏輯)。當該筆合法時,把該字串的前三個字元 x.substr(0,3) 當作 key 在 map<string,int> cnt 中計數,並更新 ans = max(ans, cnt[prefix]) 作為目前觀察到的最大頻次。讀完所有輸入後,按 map 的鍵序(由小到大)掃描,遇到 y == ans 即輸出該 prefix 與 ans(程式以第一個符合者輸出,對應於字典序最小的前綴)。
時間 / 空間複雜度:
- 每筆字串固定做 (12) 次位元相加與常數次數的字串切片/
map操作:單筆時間為( M為目前不同前綴數,因map為平衡樹),整體時間為
- 空間用於
map儲存至多個不同前綴,為 。
程式碼
#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 n;
cin >> n;
map<string, int> cnt;
int ans = 0;
while (n--) {
string x;
cin >> x;
int s1 = 0, s2 = 0;
for (int i = 0;i < 12;i++) {
if ((i + 1) % 2) s1 += x[i] - '0';
else s2 += x[i] - '0';
}
int k = (s1 + 3 * s2) % 10 + (x[12] - '0');
if (k == 0 or k == 10) {
cnt[x.substr(0, 3)]++;
ans = max(ans, cnt[x.substr(0, 3)]);
}
}
for (auto [x, y] : cnt) {
if (y == ans) {
cout << x << ' ' << ans;
return 0;
}
}
}
載入留言中…