10.31_CF_刷题
B. Kar Salesman
思路
一个顾客一种型号的车只能买一个，所以\(a_i\)号车需要\(a_i\)个顾客，所以至少需要\(max(a_i)\)个顾客，把所有车买完至少\(\frac{sum}{x}\)个顾客，所以取两者最大值就好
也就是说，先用比较少的去消耗比较多的，避免最后只剩下比较多的那种车
如果最多的那个被消耗完刚好全都完了,那正好
不然的话过程中一定会有\(x\)种车数量相同的情况，这样它们就可以一起被减少了，相当于\(\frac{sum}{x}\)
代码
神奇的代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int maxn = 5e5 + 5;
const int inf = 0x7f7f7f7f;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (uint64_t x) const
{
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
return splitmix64(x + FIXED_RANDOM);
}
};
int nums[maxn], tot[maxn];
void solve()
{
int n = 0, x = 0, s = 0, mx = 0;
std::cin >> n >> x;
for (int i = 1; i <= n; i++)
{
std::cin >> nums[i];
mx = std::max(mx, nums[i]);
s += nums[i];
}
std::cout << std::max(mx, s / x + (s % x != 0)) << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
//freopen("out.txt", "w", stdout);
int t = 1;
std::cin >> t;
while(t--)
{
solve();
}
return 0;
}
E. Alternating String
思路
只能进行两种操作
-
删除一个字符，这个操作最多一次
-
替换一个字符
如果字符串长度为奇数就进行操作1，否则不进行
字符串长度为偶数时：我们想把位置奇偶性相同的变成相同的字符，可以分开看，维护统计替换成每个字符需要改多少个，可以用前缀和维护每个字符多少个，需要改几个可以直接算出来
难点时长度为奇数时需要删除哪一个呢，删除不同位置会影响这个字符后面位置的奇偶性，那么可以枚举删除哪一个
用前缀和维护奇数位和偶数位的字符有哪些，有几个
代码
神奇的代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int maxn = 2e5 + 5;
const int inf = 0x7f7f7f7f;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (uint64_t x) const
{
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
return splitmix64(x + FIXED_RANDOM);
}
};
void solve()
{
int n = 0, ans = 0;
std::string s;
std::cin >> n >> s;
if (n == 1)
{
std::cout << 1 << endl;
return;
}
std::vector<std::vector<int>> odd(n + 1, std::vector<int> (26, 0)), even(n + 1, std::vector<int> (26, 0));
for (int i = 1; i <= s.size(); i++)
{
for (int j = 0; j < 26; j++)
{
odd[i][j] += odd[i - 1][j];
even[i][j] += even[i - 1][j];
}
if (i & 1)
{
odd[i][s[i - 1] - 'a'] += 1;
}
else
{
even[i][s[i - 1] - 'a'] += 1;
}
}
if (n & 1)
{
int tmpans1 = inf, tmpans2 = inf;
ans = inf;
for (int i = 1; i <= s.size(); i++)
{
tmpans1 = inf, tmpans2 = inf;
int s1 = i / 2 + (n / 2 - i / 2);
int s2 = i / 2 - (i % 2 == 0) + (n / 2 - i / 2) + 1 - (i & 1);
for (int j = 0; j < 26; j++)
{
int t1 = odd[i - 1][j] + even[n][j] - even[i][j];
int t2 = even[i - 1][j] + odd[n][j] - odd[i][j];
tmpans1 = std::min(tmpans1, s1 - t1), tmpans2 = std::min(tmpans2, s2 - t2);
}
ans = std::min(ans, tmpans1 + tmpans2 + 1);
}
}
else
{
int tmp = inf;
for (int j = 0; j <= 25; j++)
{
tmp = std::min(tmp, n / 2 - odd[n - 1][j]);
}
ans += tmp;
tmp = inf;
for (int j = 0; j <= 25; j++)
{
tmp = std::min(tmp, n / 2 - even[n][j]);
}
ans += tmp;
}
std::cout << ans << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
//freopen("out.txt", "w", stdout);
int t = 1;
std::cin >> t;
while(t--)
{
solve();
}
return 0;
}
A. Everything Nim
思路
相同的堆可以看成是同一堆
如果最小的堆为1，先手没得选
如果最小的堆不是1，先手可以全都取走，也能留一个，也就是说，先手这时候可以转移先手权，也可以保留先手权
能掌握先手权的必胜
神奇的代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int maxn = 2e5 + 5;
const int inf = 0x7f7f7f7f;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
size_t operator () (uint64_t x) const
{
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
return splitmix64(x + FIXED_RANDOM);
}
};
void solve()
{
int n = 0;
std::cin >> n;
std::vector<int> nums;
std::unordered_map<int, int, custom_hash> mp;
int tmp = 0;
for (int i = 1; i <= n; i++)
{
std::cin >> tmp;
if (!mp[tmp])
{
nums.push_back(tmp);
mp[tmp] = 1;
}
}
std::sort(nums.begin(), nums.end());
int sz = nums.size();
if (nums[0] != 1)
{
std::cout << "Alice" << endl;
return;
}
for (int i = 0; i < sz - 1; i++)
{
if (nums[i + 1] != nums[i] + 1)
{
if (i & 1)
{
std::cout << "Alice" << endl;
}
else
{
std::cout << "Bob" << endl;
}
return;
}
}
if (nums.size() & 1)
{
std::cout << "Alice" << endl;
}
else
{
std::cout << "Bob" << endl;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
//freopen("out.txt", "w", stdout);
int t = 1;
std::cin >> t;
while(t--)
{
solve();
}
return 0;
}