简单题解，有什么问题可以直接跟我反馈，谢谢！
A - Unsupported Type
solution
遍历一遍就行了
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define pll pair<int , int>
#define x first
#define y secondvoid solve()
{int n;cin >> n;vector<int> a(n);for(int i = 0 ; i < n ; i ++) cin >> a[i];int x;cin >> x;for(int i = 0 ; i < n ; i ++)if(a[i] == x){cout << "Yes";return;}cout << "No";
}signed main()
{ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);int _ = 1;// cin >> _;while(_ --) solve();
}
B - Pick Two
solution
直接遍历贪心，只要遇到 # 就输出。用flag记录当前遇到的 # 是奇数个还是偶数个，根据不同的情况输出不同的格式就可以了。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define pll pair<int , int>
#define x first
#define y secondvoid solve()
{string s;cin >> s;int cnt = 0;for(int i = 0 ; i < s.size() ; i ++) if(s[i] == '#'){if(cnt == 0) {cnt ^= 1;cout << i + 1 << ',';}else {cnt ^= 1;cout << i + 1 << '\n';}}
}signed main()
{ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);int _ = 1;// cin >> _;while(_ --) solve();
}
C - Mixture
solution
赛时读题读了半个小时看不懂题目意思QAQ
题目大意就是当前有N个化学品，并尝试将N个化学品混合在一起，用数字的二进制表达记录N个化学品的混合状态，0表示没加当前化学品，1就表示加了。例如：当前有三个化学平，数字5表示的状态就是指先将5转换成二进制为101，就表示现在加了1号和3号，2号没加。
现在将所有状态用字符串列出来（除了状态0），0表示安全，1表示危险，问能否从没有化学品添加到所有化学品混合进去。
可以直接将问题转化成图论，每个状态就是一个节点，如果能从状态A转移到状态B就从A连接一个单向边到B，最后问题就可以转换为能否从节点0 走到 节点 $2^n - 1$。
不难发现当A和B满足以下条件时可以从A转移到B：
$$\begin{cases}
A < B \
A ^ B = 2 ^ k
\end{cases}$$
所以这道题就先建图，再用dfs或者bfs遍历一遍能不能走通就行了
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define pll pair<int , int>
#define x first
#define y secondconst int N = 262149;
vector<int> g[N];
bitset<N> vis;
int ans = 0;void dfs(int st)
{ans = max(ans , st);vis[st] = 1;for(auto &i : g[st])if(!vis[i]) dfs(i);
}void solve()
{int n;cin >> n;string s;cin >> s;int cnt = pow(2 , n);ans = 0;for(int i = 0 ; i < cnt ; i ++) {vis[i] = 0;g[i].clear();}for(int i = 0 ; i < cnt ; i ++){if(i != 0 && s[i - 1] == '1') continue;for(int j = 0 ; j < n ; j++){int t = (1 << j) ^ i;if(t > i && s[t - 1] != '1') g[i].push_back(t);}}dfs(0);// for(auto &i : g[0]) cout << i << ' ';// cout << '\n';// cout << ans << '\n';if(ans == cnt - 1) cout << "Yes\n";else cout << "No\n";
}signed main()
{ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);int _ = 1;cin >> _;while(_ --) solve();
}
D - Get Many Stickers
solution
为什么D比C简单这么多。。。
这道题思路很简单，不要想复杂了，直接贪心就行了。
每一组操作添加一个数据表示消耗的可乐和返回的可乐的差值，每次贪心选择差最小的就行了。
因为每一组操作都能一次完成，所以时间复杂度是$O(M)$。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define pll pair<int , int>
#define x first
#define y secondvoid solve()
{int n , m;cin >> n >> m;vector<array<int , 3>> a(m);int judge = 2e18;for(int i = 0 ; i < m ; i ++){cin >> a[i][0] >> a[i][1];a[i][2] = a[i][0] - a[i][1];judge = min(judge , a[i][0]);}stable_sort(all(a) , [&](array<int , 3> a , array<int , 3> b) -> bool{return a[2] <= b[2];});int ans = 0;for(int i = 0 ; i < m ; i ++){if(n < judge) break;if(n < a[i][0]) continue;int cnt = 1 + (n - a[i][0]) / a[i][2];ans += cnt;n -= cnt * a[i][2];}cout << ans;
}signed main()
{ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);int _ = 1;// cin >> _;while(_ --) solve();
}
E - Hungry Takahashi
solution
这种单调性 + 最大套最小，或者最小套最大一眼顶针，基本上都是二分虽然驻波太菜了赛时没有顶针出来
其实就是一个二分 + dp，二分一下初始拥有的硬币，check函数用dp判断会不会饿死。
$$\begin{cases}
dp[i][j] \to dp[i + 1][j] + g[i + 1][j] - p[i + j - 1] \
dp[i][j] \to dp[i][j + 1] + g[i][j + 1] - p[i + j - 1]
\end{cases}$$
code
因为在一初始输入的时候就减去了$p[i + j - 1]$所以在转移的时候就没有再减了
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define pll pair<int , int>
#define x first
#define y secondvoid solve()
{int h , w;cin >> h >> w;vector<vector<int>> g(h + 1 , vector<int> (w + 1));for(int i = 1 ; i <= h ; i ++)for(int j = 1 ; j <= w ; j ++) cin >> g[i][j];vector<int> p(h + w); int sum = 0;for(int i = 1 ; i <= h + w - 1 ; i ++) {cin >> p[i];sum += p[i];}for(int i = 1 ; i <= h ; i ++)for(int j = 1 ; j <= w ; j ++) g[i][j] -= p[i + j - 1];auto check = [&](int mid){vector<vector<int>> dp(h + 1 , vector<int> (w + 1 , -1));dp[1][1] = mid + g[1][1];for(int i = 1 ; i <= h ; i ++)for(int j = 1 ; j <= w ; j ++){if(dp[i][j] < 0) continue;if(i + 1 <= h) dp[i + 1][j] = max(dp[i + 1][j] , dp[i][j] + g[i + 1][j]);if(j + 1 <= w) dp[i][j + 1] = max(dp[i][j + 1] , dp[i][j] + g[i][j + 1]);}return dp[h][w] >= 0;};int l = -1 , r = sum + 1;while(l + 1 != r){int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid;}cout << r << '\n';
} signed main()
{ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);int _ = 1;// cin >> _;while(_ --) solve();
}