|
|
首先是后悔E2在那里用全局变量导致一直wa28，也不知道为什么改vector就过了，然后是F思路对了没写下去又或者是思路没完全对。。。这场还是能体现代码功底的吧，反正我是被折磨了，菜死了。
进入正题：
<hr/>A. Number Replacement 模拟
题意：
给定一个数组和一个字符串，每次选择数组中的一个数和一个字符，把字符串中所有的该字符都替换成该字符，求能否将数组变成该字符串。
分析：
对于无解的情况是在s中相同的位置但是在原数组中不同，用map存上一个a的位置判断在s中是否相同即可。
时间复杂度：O(n)
代码：
void solve()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a;
cin >> s;
s = &#34;?&#34; + s;
map<int, int> mp;
for(int i = 1; i <= n ; i ++ ) {
if(!mp[a]) mp[a] = i;
else {
if(s != s[mp[a]]) NO;
mp[a] = i;
}
}
YES;
}
B. Even-Odd Increments 模拟
题意：
给定一个数组，每次一个操作：让偶数元素+v或者让奇数元素+v，求每次操作后的数组总和。
分析：
统计出偶数和奇数的数量，然后在累加的时候维护其奇偶数量的变化。
时间复杂度：O(n + m)
代码：
void solve()
{
cin >> n >> m;
int sum = 0;
int aa = 0, bb = 0;
for(int i = 1 ; i <= n ; i ++ ) {
cin >> a , sum += a;
if(a & 1) bb ++ ;
}
aa = n - bb;
while(m -- ) {
int op, v;
cin >> op >> v;
if(op == 0) {
sum += aa * v;
if(v & 1) bb += aa, aa = 0;
}
else {
sum += bb * v;
if(v & 1) aa += bb, bb = 0;
}
cout << sum << endl;
}
}
C. Traffic Light 模拟
题意：
给定红绿灯的循环节，以及你初始看到的灯，求下一个绿灯等待的最长时间。
分析：
把循环节复制一遍，在2n的序列上从后往前判断最大值即可。
代码：
void solve()
{
char c;
cin >> n >> c;
cin >> s;
s = &#34;?&#34; + s + s;
int mx = 0, last = 0;
for(int i = 2 * n; i >= 1 ; i -- ) {
if(s == &#39;g&#39;) last = i;
if(s == c) mx = max(mx, last - i);
}
cout << mx << endl;
}
D. Divisibility by 2^n 贪心
题意：
给定一个数组，要求进行若干次操作，使得a乘i上的数，每个数都能最多被乘一次，求最少的操作次数使得数组的乘积能够被2^n整除。
分析：
在数组中找出2的因子个数，如果满足了n个ans就是0，否则需要通过操作来补足。操作出1-n所有数中2因子的数量，优先操作2因子数量最大的数。
时间复杂度：O(nlogn)
代码：
void solve()
{
cin >> n;
int res = 0;
vector<int> v;
for(int i = 1; i <= n ; i ++ ) {
cin >> a;
int t = a;
while(t % 2 == 0) t /= 2, res ++ ;
t = i;
int s = 0;
while(t % 2 == 0) t /= 2, s ++ ;
if(s) v.push_back(s);
}
if(res >= n) cout << 0 << endl;
else {
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
int l = 0;
int V = n - res;
// cout << V << endl;
int ans = 0;
while(l < v.size() && V) {
if(v[l] <= V) ans ++ , V -= v[l];
l ++ ;
}
if(V) cout << -1 << endl;
else cout << ans << endl;
}
}
E. Divisible Numbers 暴力枚举质因子
题意：
给定4个数，abcd，要求找到一组<x, y>使得x * y能够被 a * b整除。
分析：
abcd的范围是1e9，但是我们发现1e9的因子数量其实并不多。
我们考虑枚举a*b的所有因子，1e18的所有因子的数量大概是100000个，别问，这个数量的增加和质数的种类有很大关系，但是1e18的质数的种类不会超过20个，因此记住这个重要的结论就可以qwq。
dfs枚举出a * b的所有因子，然后开始枚举。x为第一个因子，y为第二个因子a*b/x，然后O1找到第一个大于等于a+1和b+1的位置，判断是否均小于c和d即可。
时间复杂度：O(100000)
代码：因为我的码子蜜汁离谱，还开的全局变量，贴了胶老师码子大家欣赏一下。
void init() {
for (int i = 2; i < N; i++) {
if (!st) primes[cnt++] = i;
for (int j = 0; primes[j] * i < N; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void dfs(int now, int prod) { // dfs爆搜因子
if (prod > c) return;
if (now == fs.size()) {
if (r / prod <= d) ds.push_back(prod);
return;
}
int p = fs[now].first, c = fs[now].second;
for (int i = 0; i <= c; i++) {
dfs(now + 1, prod);
prod *= p;
}
}
void solve() {
fs.clear(), ds.clear();
cin >> a >> b >> c >> d;
int bb = a;
map<int, int> mp;
for (int i = 0; primes <= bb / primes; i++) {
int p = primes;
if (bb % p == 0) {
while (bb % p == 0) mp[p]++, bb /= p;
}
}
if (bb > 1) mp[bb]++;
bb = b;
for (int i = 0; primes <= bb / primes; i++) {
int p = primes;
if (bb % p == 0) {
while (bb % p == 0) mp[p]++, bb /= p;
}
}
if (bb > 1) mp[bb]++;
for (auto [x, y] : mp) fs.push_back({x, y});
r = a * b;
dfs(0, 1);
int p = -1, q = -1;
if (ds.size()) {
for (auto x : ds) {
int y = r / x;
x = (a / x + 1) * x;
y = (b / y + 1) * y;
if (x <= c && y <= d) {
p = x, q = y;
return ;
}
}
}
cout << p << &#39; &#39; << q << &#39;\n&#39;;
}
F. MEX vs MED 统计问题
题意：
给定一个由0-n-1组成的数组，统计出这样的区间[l, r]当且仅当区间的中位数 < mex[l, r] , mex表示区间内第一个不存在的自然数。
分析：
赛时的思路有点正确的，但不是完全正确，感谢cup_pyy帮我实现了我赛时未完成的思路，大家可以看他的：
链接：
我们发现mex的特性是想要mex变大，必须在区间内包含从0开始的所有数，根据这个特性，我们可以通过限定mex来统计出在某一个mex值的情况下，有多少满足的区间。
假设我们目前的区间[L, R]的mex函数是p，那么这个在保证中位数<p的条件下，需要保证序列长度max_len <= (p + 1) * 2。因此我们每次从一个p出发开始拓展到p + 1并更新区间，在max_len的限制下去统计合法区间的数量。
每次找到下一个改变mex的位置，也就是pos[p + 1]，然后看看这个位置在左边还是在右边，统计出数量即可。 |
|
发表于 2022-11-30 13:19:43