A - Weekly Records (abc307 A)
題目大意
給定\(n\)周每天的散步量，求每周七天的散步量的和，
解題思路
累計求和即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
while(n--){
int sum = 0;
for(int i = 0; i < 7; ++ i){
int a;
cin >> a;
sum += a;
}
cout << sum << ' ';
}
return 0;
}
B - racecar (abc307 B)
題目大意
給定\(n\)個字串 \(s\)，問能否選擇兩個 \(i,j\)，滿足 \(i \neq j\)，且 \(s_i + s_j\)是個回文串，
解題思路
只有\(100\)個串，直接 \(O(n^2)\)列舉判斷即可，
判斷回文可以將串反轉后與原先的串比較是否相同，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<string> s(n);
for(auto &i : s)
cin >> i;
auto palind = [&](int x, int y){
string l = s[x] + s[y];
string r = l;
reverse(r.begin(), r.end());
return l == r;
};
auto ok = [&](){
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (i != j && palind(i, j))
return true;
}
return false;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Ideal Sheet (abc307 C)
題目大意
給定兩個二維網格的模式圖，有一些格子是黑的，有一些格子是透明的，
問能否通過這兩個模式圖得到一個期望的模式圖，要求格子的屬性（黑或透明）相同，
操作是將這兩個模式圖分別蓋印到一個無窮大的二維網格上，僅能蓋一次，然后通過裁剪得到期望模式圖，
注意蓋印的黑色格子都必須保留，不得裁剪掉，
解題思路
因為模式圖大小只有\(10 \times 10\)，因此直接 \(O(10^4)\)列舉兩個模式圖的蓋印位置，然后判斷蓋印后的結果是否與期望模式圖相同，
注意蓋印后的黑色格子都必須在期望模式圖范圍內，所以還需統計期望模式圖范圍內的兩個模式圖的黑色格子數，不能有超出期望模式圖范圍的黑色格子，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
array<int, 3> h, w;
array<vector<string>, 3> d;
array<int, 3> blk{};
for(int i = 0; i < 3; ++ i){
cin >> h[i] >> w[i];
d[i].resize(h[i]);
for(int j = 0; j < h[i]; ++ j){
cin >> d[i][j];
blk[i] += count(d[i][j].begin(), d[i][j].end(), '#');
}
}
auto check = [&](int x1, int y1, int x2, int y2){
int tot = 0;
for(int i = 0; i < h[2]; ++ i)
for(int j = 0; j < w[2]; ++ j){
int target = (d[2][i][j] == '#');
int blk1 = (i >= x1 && j >= y1 && i - x1 < h[0] && j - y1 < w[0] && d[0][i - x1][j - y1] == '#');
int blk2 = (i >= x2 && j >= y2 && i - x2 < h[1] && j - y2 < w[1] && d[1][i - x2][j - y2] == '#');
tot += blk1 + blk2;
if (target != (blk1 || blk2))
return false;
}
return (tot == blk[0] + blk[1]);
};
auto ok = [&](){
for(int i = -10; i <= 10; ++ i)
for(int j = -10; j <= 10; ++ j)
for(int k = -10; k <= 10; ++ k)
for(int l = -10; l <= 10; ++ l){
if (check(i, j, k, l))
return true;
}
return false;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - Mismatched Parentheses (abc307 D)
題目大意
給定一個包含小寫字母、(、)的字串，每次選擇一個開頭是(，結尾是)，且中間不包含這兩個字符的子串，移除該子串，
問最終剩余的字串是怎樣的，
解題思路
每次移除的其實是一個最里面的合法的()，假設有(()())，每次移除的都是最里端的一對()，因此反復這么操作，合法的括號序列都會被移除掉，
因此我們對原字串的每個(統計與之對應的)，這樣每個()之間的內容都會被移除，
根據這個對應關系就會跳過一些字串（被移除了），剩下的就是沒被移除的了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
vector<int> r(n, -1);
stack<int> pos;
for(int i = 0; i < n; ++ i){
if (s[i] == '(')
pos.push(i);
else if (s[i] == ')' && !pos.empty()){
r[pos.top()] = i;
pos.pop();
}
}
for(int i = 0; i < n; ++ i){
if (r[i] != -1){
i = r[i];
}else {
cout << s[i];
}
}
cout << '\n';
return 0;
}
E - Distinct Adjacent (abc307 E)
題目大意
給定一個\(n\)個數的環形陣列，每個數的取值為\([1, m]\)，
問有多少種取值情況，滿足任意相鄰兩個數不相同，
解題思路
如果不是環形，答案很明顯是\(m \times (m - 1)^(n - 1)\)，但由于環形，最后一位的取值難以確定是\(n - 1\)還是 \(n - 2\)，這取決于倒數第二位是否和第一位相同，
如何解決呢？其實問題的核心上面已經指明了：倒數第二位是否和第一位相同，
- 如果相同，則最后一位可取\(n - 1\)種情況，
- 如果不相同，則最后一位可取 \(n - 2\)種情況，
由于每個數都是對稱的，我們假設第一位填的數是 \(1\)，然后設 \(dp[i][0/1]\)表示前 \(i\)位，相鄰兩數不同（不考慮首尾），且最后一位與首位數字不同/相同的方案數，轉移就看當前位是否與首位相同，
因為上述我們假定了首位取\(1\)，事實上首位取什么值情況都一樣，而它有 \(m\)種取法，因此最終答案就是\(m \times dp[n][0]\)，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
array<int, 2> dp{0, 1};
for(int i = 1; i < n; ++ i){
array<int, 2> dp2{};
dp2[0] = 1ll * dp[0] * (m - 2) % mo + 1ll * dp[1] * (m - 1) % mo;
if (dp2[0] >= mo)
dp2[0] -= mo;
dp2[1] = dp[0];
dp.swap(dp2);
}
cout << 1ll * dp[0] * m % mo << '\n';
return 0;
}
F - Virus 2 (abc307 F)
題目大意
給定一張無向圖，邊有邊權，
初始有\(a\)個點感染病毒，
持續 \(d\)天，對于第 \(i\)天，所有與已感染病毒的點距離不超過\(x_i\)的點都會被感染病毒，
問每個點第一次被感染病毒的天數，
解題思路
<++>
神奇的代碼
G - Approximate Equalization (abc307 G)
題目大意
給定一個有\(n\)個數的陣列，可進行兩種操作：
- 選定一個\(i\)，令 \(a_i = a_i - 1, a_{i + 1} = a_{i + 1} + 1\)
- 選定一個\(i\)，令 \(a_i = a_i + 1, a_{i + 1} = a_{i + 1} - 1\)
問最少進行的操作次數，使得陣列的極差不超過\(1\)，
解題思路
觀察操作，可以發現每次操作后，這個陣列的總和\(sum\)是不變的，（其實可以看成有\(sum\)個小球， \(n - 1\)個隔板，每次操作其實就是移動一個隔板到相鄰位置）
由于極差不超過\(1\)，那么最終每個數要么是 \(div = \lfloor \frac{sum}{n} \rfloor\)，要么是 \(div + 1\)，且至多有\(sum \% n\)個數是后者，問題就是讓哪些數是后者，哪些數是前者，
首先明確一點，如果給定最終的陣列，求將該陣列變成最終陣列的操作次數，其最優方案是可以在\(O(n)\)內求出來，就是依次對每個數\(a_i\)，將其變為目標值\(t_i\)，需要從后一個數 \(a_{i + 1}\)借多少次（操作二），還是給多少次（操作一），然后這個借和給的影響是持續的，
現在問題變成了讓哪些數是\(div\)，哪些是\(div+1\)，這是個分配問題，設 \(dp[i][j]\)表示前 \(i\)個數，還有 \(j\)個 \(div+1\)的未分配的最小運算元，需要第二維狀態一方面是要確保有\(mod\)個 \(div + 1\)，另一方面是需要知道由于前面的數的操作，當前數變成了多少，
對于當前數\(a_i\)，知道了 \(j\)，我們就知道前面有多少個數是 \(div+1\)，多少個數是\(div\)，進而知道，在上述求解操作的影響下， \(a_i\)變成了多少，然后就可以進一步求解 \(a_i\)變成目標數所需要的操作次數了，
注意如果\(mod = sum \% n\)是負數，則可以讓\(div = div - 1, mod = n - mod\)，這樣就變回正數了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<LL> a(n);
for(auto &i : a)
cin >> i;
LL sum = accumulate(a.begin(), a.end(), 0ll);
LL div = sum / n, mod = sum % n;
if (mod < 0){
mod = n + mod;
div --;
}
vector<LL> dp(mod + 1, inf);
dp[mod] = 0;
LL presum = 0;
LL tot = 0;
for(auto &x : a){
vector<LL> dp2(mod + 1, inf);
for(int i = 0; i <= mod; ++ i){
LL cur = x - (tot + mod - i - presum);
dp2[i] = min(dp2[i], dp[i] + abs(cur - div));
if (i)
dp2[i - 1] = min(dp2[i - 1], dp[i] + abs(cur - div - 1));
}
presum += x;
tot += div;
dp.swap(dp2);
}
cout << dp[0] << '\n';
return 0;
}
Ex - Marquee (abc307 Ex)
題目大意
<++>
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555866.html
標籤：其他
上一篇：淺談OpenCV的多物件匹配影像的實作，以及如何匹配半透明控制元件，不規則影像
下一篇：返回列表