原题链接
题意 有三堆物品,给出每一堆物品的数量,第一个人只能从第一堆和第三堆每次拿一个,第二个人只能从第二堆和第三堆每次拿一个,谁先没东西拿谁就输,问谁能赢
思路 这一题一开始脑子抽了wa了一发,都想让对方输所以都得先拿第三堆的,第三堆拿完了再看第一二堆谁多谁少,注意一下奇偶即可
代码 #include <bits/stdc++.h> using namespace std;using i64 = long long ;typedef pair<int , int > PII;void solve () { int a, b, c; cin >> a >> b >> c; if (c % 2 == 0 ) { if (a > b) cout << "First\n" ; else cout << "Second\n" ; } else { if (a >= b) cout << "First\n" ; else cout << "Second\n" ; } } int main () { ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
B. The Walkway 原题链接
题意 一条路上有几个特殊点,一个人会在以下这几种情况吃一块饼干
现在可以删除一个特殊点,问这个人最少吃多少饼干以及有多少种删除方式
思路 我是先计算出每两个特殊点中间的距离可以让这个人吃多少饼干,存储下这个数值的前缀和
之后遍历每个特殊点,计算删除掉这个特殊点之后这个人吃的饼干数量,例如当前计算第 i 个特殊点,那就单独计算第 i-1 个特殊点到第 i+1 个特殊点之间吃的饼干数量,再加上第 i-1 个点前面的饼干数量(计算前缀和时已经将这个数值存储下来了),再加上第 i+1 个点后面的饼干数量,再加上所有特殊点的数量减1
计算时顺便存储一下这个饼干数量被算出过几次
中间有一些需要注意的地方,思路清晰之后主要还是代码实现
代码 #include <bits/stdc++.h> using namespace std;using i64 = long long ;typedef pair<i64, i64> PII;void solve () { int n, m, d; cin >> n >> m >> d; vector<int > seller (m + 1 ) ; vector<int > idx (m + 1 ) ; for (int i = 0 ; i < m; i ++ ) cin >> seller[i]; seller[m] = n + 1 ; if (seller[0 ] == 1 ) idx[0 ] = 0 ; else idx[0 ] = (seller[0 ] - 2 ) / d + 1 ; for (int i = 1 ; i <= m; i ++ ) idx[i] = (seller[i] - seller[i - 1 ] - 1 ) / d + idx[i - 1 ]; vector<int > ans; unordered_map<int , int > cnt; ans.push_back (idx[m] - idx[1 ] + (seller[1 ] - 2 ) / d + m); cnt[idx[m] - idx[1 ] + (seller[1 ] - 2 ) / d + m] = 1 ; for (int i = 1 ; i < m; i ++ ) { int res = idx[i - 1 ] + idx[m] - idx[i + 1 ] + (seller[i + 1 ] - seller[i - 1 ] - 1 ) / d + m - 1 ; ans.push_back (res); if (!cnt.count (res)) cnt[res] = 1 ; else cnt[res] ++ ; } sort (ans.begin (), ans.end ()); cout << ans[0 ] << ' ' << cnt[ans[0 ]] << '\n' ; } int main () { ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }
C. Yet Another Permutation Problem 原题链接
题意 求出一种排列使得相邻两数的最小公约数数量最多
思路 从1开始,让后一个数一直是前一个数的两倍,这样可以保证出现新的最大公约数,直到两倍已经不在给定的n内就换下一个没用过的数
代码 #include <bits/stdc++.h> using namespace std;using i64 = long long ;typedef pair<int , int > PII;void solve () { int n; cin >> n; int i = 2 , j = 2 , temp; vector<bool > idx (n + 1 ) ; int k = 2 ; vector<int > ans; ans.push_back (1 ); ans.push_back (2 ); while (k < n) { temp = i * j; while (temp <= n && !idx[temp]) { ans.push_back (temp); k ++ ; idx[temp] = true ; j *= 2 ; temp = i * j; } j = 1 ; i ++ ; } for (int cnt = 0 ; cnt < ans.size (); cnt ++ ) cout << ans[cnt] << ' ' ; cout << '\n' ; } int main () { ios::sync_with_stdio (false ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t -- ) { solve (); } }