牛客周賽Round112
牛客周賽 Round 112
寫在前面
A. 模擬
B. 思維
C. 思維
D. 位運算貪心
E. 計數原理
F. 狀壓DP
A. ICPC Regionals
思路
按照題意模擬即可
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
void solve()
{
int n = 0, k = 0;
std::cin >> n >> k;
int g = (n / 10) + (n % 10 != 0);
if (k <= g) {std::cout << "Gold Medal"; return;}
if (k <= 3 * g) {std::cout << "Silver Medal"; return;}
if (k <= 6 * g) {std::cout << "Bronze Medal"; return;}
std::cout << "Da Tie";
}
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. Card Game
思路
只能出一張牌
- 丟牌，丟幾張牌獲得點數為幾的牌，肯定丟完能獲得最大的點數
- 不丟牌，就取最大的那一個
- 兩者取最大即可
代碼
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
void solve()
{
int n = 0; std::cin >> n;
int mx = -1;
for (int i = 1; i <= n; i++)
{
int tmp; std::cin >> tmp;
mx = std::max(mx, tmp);
}
std::cout << std::max(mx, 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. Palindrome Coloring
思路
首先我們能注意到：最多操作兩次
- 如果本身就是回文串，就操作一次就行
- 如果本身不是回文串，第一次把所有
1染成紅色， 第二次把所有0染成紅色，因為相同的數組成的序列一定回文
做條件判斷即可
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
void solve()
{
std::string s; std::cin >> s;
int len = s.size();
int i = 0, j = len - 1;
while(i < j)
{
if (s[i] != s[j])
{
std::cout << 2 << endl;
return;
}
i++; j--;
}
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;
}
D. Digital Pairing
思路
按位貪心
在當前可選的數字中，從高位開始，如果位為1的數字 \(\geq n\)的話，這一位就選上，并把這一位為1的數字加入候選數字中參與下一輪篩選就好了，為0的就不用管了
代碼
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
void solve()
{
int n = 0; std::cin >> n;
std::vector<int> num(n * 2 + 1, 0);
std::vector<std::vector<int>> bit(n * 2 + 1, std::vector<int>(40, 0));
for (int i = 1; i <= n * 2; i++)
{
int tmp; std::cin >> tmp;
num[i] = tmp;
for (int j = 35; j >= 0; j--)
{
if ((1LL << j) & tmp) bit[i][j] = 1;
}
}
int ans = 0;
std::vector<int> id;
for (int i = 1; i <= n * 2; i++) id.push_back(i);
for (int i = 35; i >= 0; i--)
{
ans <<= 1;
std::vector<int> tmp;
int cnt = 0;
for (int j = 0; j < (int)id.size(); j++)
{
if (bit[id[j]][i] == 1) {tmp.push_back(id[j]); cnt++;}
}
if (cnt < n) continue;
ans += 1;
id = tmp;
}
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;
}
E. Beautiful Sequence
思路
正難則反，題目要求美麗序列的個數，我們可以求不美麗序列的個數
不美麗序列就是序列中有序列的gcd，我們可以枚舉gcd, 序列中一旦有gcd的倍數就一定是不美麗的
對于一個gcd, 加入有\(a\)個\(gcd\), \(b\)個它的倍數, 那么產生的不美麗序列個數就是
\[ cnt_{gcd} = (2^a - 1) \times 2^b
\]
因為我們枚舉的是gcd，所以gcd一定有，所以\(-1\)減掉一個gcd都沒有的情況，那么此時它的倍數就可以有也可以沒有了
至于枚舉gcd的復雜度
\(gcd\)從\(1~n\)是\(O(n)\)的，枚舉倍數是\(O(n + \frac{n}{2} + \frac{n}{3} + \dots + 1)\)
調和級數是\(log\)數量級的，總體時間復雜度\(O(nlogn)\)
代碼
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;
int power(int y, int x)
{
int res = 1;
while(x)
{
if (x & 1)
{
res = res * y % mod;
}
x >>= 1;
y = y * y % mod;
}
return res;
}
void solve()
{
int ans = 0;
int n = 0; std::cin >> n;
int mp[200010]{};
for (int i = 1; i <= n; i++)
{
int tmp; std::cin >> tmp;
mp[tmp]++;
}
for (int i = 1; i <= n; i++)
{
int g = i; int cnt = 0;
for (; g <= n; g += i)
{
cnt += mp[g];
}
if (mp[i] == 0 || cnt == 0) continue;
int tmp = (power(2, mp[i]) - 1 + mod) % mod;
tmp = tmp * power(2, cnt - mp[i]) % mod;
ans += tmp;
ans %= mod;
}
// std::cout << ans << endl;
int tot = power(2, n) - 1;
tot = (tot + mod) % mod;
std::cout << (tot - ans + mod) % mod << 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;
}
F. Bracket Counting
思路
注意一個合法序列在任意位置左括號數一定大于等于右括號數
找時間再寫吧QAQ
代碼
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 1e9 + 7;
void solve()
{
int n = 0; std::cin >> n;
std::vector<int> bal(n);
std::vector<int> min_bal(n);
int tot = 0;
for (int i = 0; i < n; i++)
{
std::string s;
std::cin >> s;
int val = 0;
int current_min = 0;
for (char c : s)
{
if (c == '(') val++;
else val--;
current_min = std::min(current_min, val);
}
bal[i] = val;
min_bal[i] = current_min;
tot += val;
}
if (tot != 0) {
std::cout << 0 << endl;
return;
}
std::vector<std::map<int, int>> dp(1 << n);
dp[0][0] = 1;
for (int mask = 0; mask < (1 << n); mask++)
{
if (dp[mask].empty()) continue;
for (auto [x, y] : dp[mask])
{
for (int j = 0; j < n; j++)
{
if (!(mask & (1 << j)))
{
if (x + min_bal[j] >= 0)
{
int new_mask = mask | (1 << j);
int new_bal = x + bal[j];
dp[new_mask][new_bal] = (dp[new_mask][new_bal] + y) % mod;
}
}
}
}
}
std::cout << dp[(1 << n) - 1][0] << 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號