AtCoder Beginner Contest 427(A~E)
AtCoder Beginner Contest 427(A~E)
寫在前面
賽時 \(A — E\)
\(A\) : 模擬
\(B\) : 模擬，暴力，前綴和
\(C\) : \(dfs\)/狀態壓縮，二分圖概念，思維
\(D\) : 博弈論(\(P/N\)態)
\(E\) : 思維，\(BFS\)
A - ABC -> AC
思路
按題意模擬就好了
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
void solve()
{
std::string s; std::cin >> s;
int tar = s.size() / 2;
for (int i = 0; i < (int)s.size(); i++)
{
if (i == tar) continue;
std::cout << s[i];
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr); std::cin.tie(nullptr);
int _t = 1;
// std::cin >> _t;
while(_t--) solve();
return 0;
}
B - Sum of Digits Sequence
思路
\(n\)很小，暴力計算即可
可以維護一個\(f\)數組的前綴和
這個過程就是，對于第\(i\)個數，此時我們應該是已經知道了前\(i - 1\)個元素的\(f\)前綴和
那么此時就可以這樣處理
\[ A_i = pref_{i - 1}
\]
\[ pref_i = pref_{i - 1} + f[A_i]
\]
而至于\(f[A_i]\)我們暴力求解就好
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
int f[110];
int a[110];
int pre[110];
void solve()
{
f[0] = 1; f[1] = 1; f[2] = 2; f[3] = 4; f[4] = 8;
a[0] = 1; a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 8;
int n = 0; std::cin >> n;
if (n <= 4)
{
std::cout << a[n] << endl;
return;
}
pre[0] = f[0];
for (int i = 1; i <= 4; i++) pre[i] = pre[i - 1] + f[i];
for (int i = 5; i <= n; i++)
{
a[i] = pre[i - 1];
int tmp = a[i]; int val = 0;
while(tmp)
{
val += tmp % 10;
tmp /= 10;
}
f[i] = val;
pre[i] = pre[i - 1] + f[i];
}
// std::cout << f[5] << endl;
std::cout << a[n] << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr); std::cin.tie(nullptr);
int _t = 1;
// std::cin >> _t;
while(_t--) solve();
return 0;
}
C - Bipartize
思路
首先怎么判斷二分圖 \(\rightarrow\) 染色法，但是我們這里是要對其操作使之變成二分圖，染色法似乎不行. 但是我們可以注意到\(N\)很小，我們可以以\(O(2^n)\)去枚舉二分圖左集合有哪些元素，剩下的放到右集合。
那么分配完后如何操作使之成為二分圖呢，因為二分圖只有左右集合點之間的連邊，集合內部是不能連邊的，所以分別對左右集合內部枚舉點對，有邊就計數一次，然后每一次枚舉左右集合的點時我們就更新最小值即可
這里實現可以\(dfs\)，也可以狀態壓縮
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
int n, m;
int mat[20][20];
int vis[20];
int ans = INT_MAX;
void dfs(int step)
{
if (step == n + 1)
{
std::vector<int> left, right;
for (int i = 1; i <= n; i++)
{
if (vis[i]) left.push_back(i);
if (!vis[i]) right.push_back(i);
}
int tmp = 0;
for (int i = 0; i < (int)left.size(); i++)
{
for (int j = i + 1; j < (int)left.size(); j++)
{
if (mat[left[i]][left[j]]) tmp++;
}
}
for (int i = 0; i < (int)right.size(); i++)
{
for (int j = i + 1; j < (int)right.size(); j++)
{
if (mat[right[i]][right[j]]) tmp++;
}
}
ans = std::min(ans, tmp);
return;
}
vis[step] = 1;
dfs(step + 1);
vis[step] = 0;
dfs(step + 1);
}
void solve()
{
std::cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v; std::cin >> u >> v;
mat[u][v] = mat[v][u] = 1;
}
dfs(1);
std::cout << ans << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr); std::cin.tie(nullptr);
int _t = 1;
// std::cin >> _t;
while(_t--) solve();
return 0;
}
D - The Simple Game
思路
對P、N態的理解
-
\(N\)態 (N-position): Next player winning position，即“下一個”玩家（輪到他/她行動的玩家）有必勝策略的位置。可以理解為“必勝態”。
-
\(P\)態 (P-position): Previous player winning position，即“上一個”玩家（剛剛行動完的那個玩家）有必勝策略的位置。對于當前玩家來說，這是一個無論怎么走，對方都有辦法贏的局面。可以理解為“必敗態”。
-
無法移動的狀態為\(P\)態
-
可以移動到\(P\)的狀態為\(N\)態
-
只能移動到\(N\)的狀態為\(P\)態
這個題目我們代入Alice的視角去考慮
我們考慮游戲結束時，也就是剩余步數為0時，當前落在A,就是必勝態(也就是N態); 當前落在B,就是必敗態(也就是P態)
那么當游戲剩余1步時，此時該Bob走了，如果它能走到剩余0步時的P態，那此時Alice必敗，那么就是P態; 如果Bob不管怎么走都只能走到N態，那么Alice必勝，那么就是N態
\(\dots\)
我們可以按照步數把圖分層做\(dp\)
\(dp[i][j]\) : 剩余\(j\)步時，在節點\(i\)的\(P\)、\(N\)態，\(P\)態為\(1\), \(N態\)為\(0\)，那么最后我們判斷\(dp[1][2k]\)就好了
當\(j\)為奇數，也就是該Bob走時
\[ dp[i][j] = \begin{cases}
0 & \exists v|i \space can \space go \space to \space v \space \space \ \ \ \ \ dp[v][j - 1] = 0\\
1 & \forall v|i \space can \space go \space to \space v \space \space \ \ \ \ \ dp[v][j - 1] = 1
\end{cases}
\]
當\(j\)為偶數時，也就是該Alice走時
\[ dp[i][j] = \begin{cases}
1 & \exists v|i \space can \space go \space to \space v \space \space \ \ \ \ \ dp[v][j - 1] = 1\\
0 & \forall v|i \space can \space go \space to \space v \space \space \ \ \ \ \ dp[v][j - 1] = 0
\end{cases}
\]
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
struct Edge
{
int u, v, nxt;
};
void solve()
{
int n = 0, m = 0, k = 0;
std::cin >> n >> m >> k;
std::vector<char> s(2 * n + 1);
for (int i = 1; i <= n; i++) std::cin >> s[i];
std::vector<Edge> g(2 * m + 1);
std::vector<int> head(3 * n + 1, 0);
int tot = 1;
auto Add = [&](int u, int v) -> void
{
g[++tot] = {u, v, head[u]};
head[u] = tot;
};
for (int i = 1; i <= m; i++)
{
int tu, tv; std::cin >> tu >> tv;
Add(tu, tv);
}
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2 * k + 1, 0));
for (int i = 1; i <= n; i++)
{
if (s[i] == 'A') dp[i][0] = 1;
}
for (int i = 1; i <= 2 * k; i++)
{
for (int i = 1; i <= 2 * k; i++)
{
if (i % 2 != 0)
{
for (int j = 1; j <= n; j++)
{
bool ok = true;
for (int u = head[j]; u; u = g[u].nxt)
{
int v = g[u].v;
if (dp[v][i - 1] == 0)
{
ok = false;
break;
}
}
if (ok) dp[j][i] = 1;
}
}
else
{
for (int j = 1; j <= n; j++)
{
bool ok = false;
for (int u = head[j]; u; u = g[u].nxt)
{
int v = g[u].v;
if (dp[v][i - 1] == 1)
{
ok = true;
break;
}
}
if (ok) dp[j][i] = 1;
}
}
}
}
if (dp[1][2 * k] == 1)
{
std::cout << "Alice" << endl;
}
else
{
std::cout << "Bob" << endl;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr); std::cin.tie(nullptr);
int _t = 1;
std::cin >> _t;
while(_t--) solve();
return 0;
}
E - Wind Cleaning
思路
因為數據很小，我們可以把所有垃圾的位置視為一個狀態，但是有可能因為遍歷順序不同導致可能有相同的垃圾位置集合，最后的狀態表示不一樣，怎么辦呢? \(\rightarrow\) 排序，按照一個統一的標準來就好了
接下來的流程就和\(bfs\)一樣了
- 我們用一個隊列來記錄
垃圾狀態和移動的步數 - 用一個
set記錄有沒有訪問過一個狀態 - 每次先從隊列中取出一個狀態，然后將這個狀態出隊，如果這個狀態已經遍歷過，\(continue\)掉繼續遍歷，記這個狀態為
cur - 如果
cur狀態已經合法，結束輸出答案 - 因為所有垃圾都要移動，所以我們按照方向來遍歷，對每一個方向移動后的新狀態記為
nxt- 檢查狀態合法性，不合法立即放棄這個方向
- 如果有垃圾超出了邊界，不在加入后續狀態中
- 隊列為空時還沒有找到答案就輸出
-1
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
std::vector<std::pair<int, int>> trash;
std::queue<std::pair<std::vector<std::pair<int, int>>, int>> q;
std::set<std::vector<std::pair<int, int>>> vis;
int tx, ty;
int h, w;
void solve()
{
std::cin >> h >> w;
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= w; j++)
{
char tmp; std::cin >> tmp;
if (tmp == 'T') {tx = i; ty = j;}
if (tmp == '#') trash.push_back({i, j});
}
}
std::sort(trash.begin(), trash.end());
q.push({trash, 0});
while(!q.empty())
{
auto [arr, dis] = q.front(); q.pop();
if (vis.find(arr) != vis.end()) continue;
if (arr.empty()) {std::cout << dis << endl; return;}
vis.insert(arr);
for (int i = 0; i < 4; i++)
{
std::vector<std::pair<int, int>> nxt;
bool ok = true;
for (auto p : arr)
{
int nx = p.first + dir[i][0];
int ny = p.second + dir[i][1];
if (nx == tx && ny == ty)
{
ok = false;
break;
}
if (nx < 1 || nx > h || ny < 1 || ny > w) continue;
nxt.push_back({nx, ny});
}
if (ok == false) continue;
std::sort(nxt.begin(), nxt.end());
q.push({nxt, dis + 1});
}
}
std::cout << -1 << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr); std::cin.tie(nullptr);
int _t = 1;
// std::cin >> _t;
while(_t--) solve();
return 0;
}
浙公網安備 33010602011771號