知識點：貪心。
注意到 \(m\geq n\) 時，不存在某一行或列空著，於是不能移動。
而 \(m<n\) 時，一定存在，可以移動。
時間複雜度 \(O(1)\)
空間複雜度 \(O(1)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int x, y;
cin >> x >> y;
}
if (m >= n) return false;
else cout << "YES" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
知識點：貪心。
每次幹掉兩端 \(b\) 最小的即可，能保證最大的 \(b\) 沒有增加花費，其他 \(b\) 只增加花費一次。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007], b[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) cin >> b[i];
ll sum = 0;
for (int i = 1;i <= n;i++) sum += a[i];
int l = 1, r = n;
while (l < r) {
if (b[l] <= b[r]) sum += b[l++];
else sum += b[r--];
}
cout << sum << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點：博弈論，貪心，二分。
本來資料範圍能暴力，但執著找規律推結論，結果推假了wwwwwwwwww，不如直接暴力QAQ。
顯然二分 \(k\) 可以，$k \in[1,\lceil \frac{n}{2} \rceil] $。二者選取的貪心策略也很明顯，A儘量取大的，B取最小的，推到這一步可以直接模擬了。
但進一步可以推出，A取後 \(k\) 個之後，B一定取了前 \(k-1\) 個，那麼我們把前 \(k-1\) 個空出來，讓A直接從 \(k\) 開始取是最優的，正著取的第 \(i\) 個是第 \(k-i+1\) 回合，只要小於等於 \(i\) 即可。
時間複雜度 \(O(n \log n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[107];
bool check(int mid) {
bool ok = 1;
for (int i = 1;i <= mid;i++) {
ok &= a[mid + i - 1] <= i;
}
return ok;
}
bool solve() {
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = n + 1 >> 1;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << r << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知識點：數論，篩法。
注意到，我們要求的是每個元素不超過 \(m\) 的正整數，長度 \([1,n]\) 的每個長度的不明確的序列個數之和。我們先考慮長度為 \(n\) 的情況，其他長度可以同理。
所有序列天生有一組 \([1,1,1,1,\cdots]\) 的刪除序列，這代表只要序列有一個元素能在 \(1\) 以外的位置刪除，就能產生新的刪除序列，則原序列就是不明確的。
因為可以通過移除第一項，讓 \(a[i]\) 往前挪，必然會經過 \([2,i]\) 的所有位置，所以若要使 \(a[i]\) 可在 \(1\) 以外的位置刪除，需要 \(a[i]\) 存在 \([2,i]\) 內的數與其沒有公共質因子，更進一步，即不包含所有字首素數（\([2,i]\) 所有數的質因子種類，即其中所有素數），這樣就一定存在 \(2\leq j\leq i\) 使 \(gcd(j,a[i]) = 1\) 。
注意到，計算在 \(a[i]\) 位置上 \([1,m]\) 中符合條件的數的個數很困難，但計算包含所有字首質因子的情況很容易， \(\frac{m}{mul_i}\) 就是 \([1,m]\) 所有字首質因子都存在的數的個數，其中 \(mul_i\) 是位置 \(i\) 的字首質因子乘積。
我們計算出 \([1,n]\) 每個位置的 \(\frac{m}{mul_i}\) ，即每個位置其字首質因子都存在數的個數，把他們乘法原理乘在一起，就代表長度為 \(n\) 明確的數列的個數 \(\prod_{i=1}^n \frac{m}{mul_i}\) ，因為每個位置組合的都是包含所有字首質因子，除了在 \(1\) 處刪除，其他地方 \(gcd(i,a[i]) \neq 1\) 不能刪。
最後對於長度 \(n\) 的數列，所有情況一共 \(m^n\) 種，所以最後不明確的數列個數為 \(m^n - \prod_{i=1}^n \frac{m}{mul_i}\) 。
我們對 \([1,n]\) 所有長度的答案求和，有 \(ans = \sum_{i=1}^n (m^i - \prod_{j=1}^i \frac{m}{mul_j})\) ，注意到 \(m^i\) 、 \(mul_i\) 以及 \(\prod_{j=1}^i \frac{m}{mul_j}\) 可以從 \(1\) 遞推，過程中加到答案裡即可。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int cnt;
int vis[300007];
int prime[300007] = { 1 };
void euler_screen(int n) {
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime[++cnt] = i;
for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
ll m;
cin >> n >> m;
euler_screen(n);
int base = 1, mul = 1, ans = 0;
ll fact = 1;
for (int i = 1;i <= n;i++) {
if (!vis[i] && fact <= m) fact *= i;
base = 1LL * m % mod * base % mod;
mul = 1LL * m / fact % mod * mul % mod;
ans = ((ans + base) % mod - mul + mod) % mod;
}
cout << ans << '\n';
return 0;
}
知識點：bfs。
思考明白了就是一個很簡單的01bfs。
注意到我們需要讓從第一行到第 \(n\) 行不存在路徑，反過來想就是需要一條從第一列到第 \(m\) 列連續的橫向仙人掌路徑，才能阻擋所有豎向路徑，這個路徑要求花費最少，於是問題轉化問從第一列出發到第 \(m\) 列的仙人掌最短路，起點是第一列所有點，有仙人掌的格子花費為 \(0\) ，沒有的花費是 \(1\) 。
搜尋過程中用一個 map 記錄前驅座標即可復原路徑。
這道題主要在這個思考和轉化的過程。
時間複雜度 \(O(nm)\)
空間複雜度 \(O(nm)\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int dir[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };
const int dir2[4][2] = { {1,0},{0,1},{0,-1},{-1,0} };
bool solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> dt(n + 1, vector<char>(m + 1));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> dt[i][j];
auto check = [&](int x, int y) {
bool ok = 1;
for (int i = 0;i < 4;i++) {
int xx = x + dir2[i][0];
int yy = y + dir2[i][1];
if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue;
ok &= dt[xx][yy] != '#';
}
return ok;
};
deque<pair<int, int>> dq;
vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));
map<pair<int, int>, pair<int, int>> pre;
pair<int, int> p = { 0,0 };
for (int i = 1;i <= n;i++) {
if (dt[i][1] == '#') dq.push_front({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 };
else if (check(i, 1)) dq.push_back({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 };
}
while (!dq.empty()) {
auto [x, y] = dq.front();
dq.pop_front();
if (y == m) {
p = { x,y };
break;
}
for (int i = 0;i < 4;i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if (xx <= 0 || xx > n || yy <= 0 || yy > m || vis[xx][yy]) continue;
if (dt[xx][yy] == '#') dq.push_front({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };
else if (check(xx, yy)) dq.push_back({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };
}
}
auto &[px, py] = p;
if (!px && !py) return false;
cout << "YES" << '\n';
while (px || py) {
dt[px][py] = '#';
p = pre[{px, py}];
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cout << dt[i][j];
}
cout << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
本文來自部落格園，作者：空白菌，轉載請註明原文連結：https://www.cnblogs.com/BlankYang/p/16815158.html