前言:
G用线段树挺好想的,就是大晚上的写线段树真的好容易出错。。。然后调到一点也没调出来。
中午重构了一小部分,再修了一处小bug就过了,熬夜可千万不能碰线段树。
G还是挺典的。思维难度不是很大,样例给的也很强,样例过了应该就能ac了吧。
D和E都很水,尤其是E,感觉这是做了这么久div3以来,最简单的E了。
F待会儿再补。
11.20 F补掉了,但是wa了无数发,线段的合并情况没讨论清楚。。然后wa,,后来屎山代码AC,我想改的精简一点,结果又wa,查了半小时bug,原因是重载小于号的地方写锅了。。
D.Make It Round
题意:
给定n和m,求最大的n * k,使得n * k的结果后缀0最多,且k <= m。
思路:
很明显的,与质因子2和5有关,因此统计一下n中含有几个2和含有几个5,再做分类讨论即可。
E.The Humanoid
题意:
怪兽想要吃掉太空中的宇航员,当且仅当怪兽的体力严格大于宇航员的体力时,才可以吃掉宇航员。吃掉以后,怪兽的体力 += 宇航员体力 / 2,这里是向下取整。
怪兽还有3次自动增长体力的机会,分别是 = 2, = 2, *= 3.
思路:
排完序直接贪心就好了,当前的吃不掉,以后的一定也吃不掉了。
所以一旦吃不掉的时候,就一定要用自动增长体力的机会。
显然暴力了,试试增长体力的顺序是:
2 2 3
2 3 2
3 2 2
然后这三遍跑完取max.
F. All Possible Digits
题意:
给定数字,以数组的形式给定,进制是p。每次操作可以对这个数+1,问最少操作多少次,能够使得0~p-1都出现过。
做法:
二分答案,判断当前答案是否能使得0~p-1都出现过。这个可以用线段合并来做。
int a[N], b[N];
struct node
{
int l, r;
bool operator < (const node &k) const
{
if (l != k.l) return l < k.l;
return r < k.r;
}
};
set<node> s;
int n, p;
void in(int l, int r)
{
while(1)
{
auto k = s.lower_bound({l, r});
if (k == s.end()) break;
if ((*k).l <= r)
{
s.erase(k);
r = max(r, (*k).r);
}
else break;
}
while(1)
{
auto k = s.lower_bound({l, r});
if (k == s.begin()) break;
k--;
if ((*k).r >= l)
{
l = (*k).l;
r = max(r, (*k).r);
s.erase(k);
}
else break;
}
s.insert({l, r});
}
bool check(int mid)
{
fill(b, b + 1 + n + 2, 0);
s.clear();
for (int i = n; i >= 1; i--)
{
s.insert({a[i], a[i]});
b[i] = a[i];
}
b[n] += mid;
for (int i = n; i >= 1; i--)
{
b[i - 1] += b[i] / p;
b[i] %= p;
}
for (int i = n; i >= 0; i--)
{
if (i == 0 && b[i] == 0) break;
if (b[i] >= a[i])
{
int l = a[i], r = b[i];
in(l, r);
}
else
{
int l = 0, r = b[i];
in(l, r);
l = a[i], r = p - 1;
in(l, r);
}
}
int len = 0;
for (auto &i : s)
{
len += i.r - i.l + 1;
}
return len >= p;
}
void solve()
{
cin >> n >> p;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 0, r = p - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << "\n";
}
Restore the Permutation
题意:
好繁琐的定义。。建议自己看题面捏。
思路:
首先构造一种一定合法的情况,那就是a[]中数的大小关系,和b[]中的数的大小关系全都一样,此时如果所有的a[i]都小于b[i],那这个构造一定合法。
求出a[]应该是哪些数,然后再对b[]排序,之后再修改a[]中数的位置,就可以把大小关系调成一样的了。
struct node
{
int val, pos;
bool operator < (const node &k) const
{
return val < k.val;
}
}b[N];
for (int i = 1; i <= n / 2; i++) c[i] = a[i];
sort(b + 1, b + 1 + n / 2);
for (int i = 1; i <= n / 2; i++) a[b[i].pos] = c[i];
接着考虑怎么把a[]的字典序变得尽量的小:
想要字典序小,那就是把后面的小的数换到前面来。式子是这个:
a[后] < a[i] < b[后]
这时候就该上线段树了,在[a[i] + 1, n]区间查询最小值,查到的结果val如果小于a[i],那么就可以交换了。在这个区间查询,相当于是满足了 a[i] < b[后],得到的结果val小于a[i],就满足了 a[后] < a[i]。
当a[i]不再能够变小的时候,再线段树上销毁这个点,即线段树上给这个点改成1e18.
代码很长很臭…
int a[N], c[N];
struct node
{
int val, pos;
bool operator < (const node &k) const
{
return val < k.val;
}
}b[N];
bool cmp(node &x, node &y)
{
return x.pos < y.pos;
}
int f[N];
struct SegTree
{
int ls[N * 4], rs[N * 4];
int val[N * 4];
#define l(x) ls[x]
#define r(x) rs[x]
void build(int p, int l, int r)
{
ls[p] = l, rs[p] = r;
if (l >= r)
{
val[p] = f[l];
return;
}
int mid = (l + r) >> 1;
int chl = p * 2, chr = p * 2 + 1;
build(chl, l, mid);
build(chr, mid + 1, r);
val[p] = min(val[chl], val[chr]);
}
void up(int p, int l, int r, int x)
{
if (l <= l(p) && r >= r(p))
{
val[p] = x;
return;
}
int mid = (l(p) + r(p)) >> 1;
int chl = p * 2, chr = p * 2 + 1;
if (l <= mid) up(chl, l, r, x);
if (mid < r) up(chr, l, r, x);
val[p] = min(val[chl], val[chr]);
}
int que(int p, int l, int r)
{
if (l <= l(p) && r >= r(p)) {
return val[p];
}
int mid = (l(p) + r(p)) >> 1;
int chl = p * 2, chr = p * 2 + 1;
int ret = 1e18;
if (l <= mid) ret = min(ret, que(chl, l, r));
if (mid < r) ret = min(ret, que(chr, l, r));
return ret;
}
}Seg;
int pos_tree[N], pos_a[N];
void solve()
{
int n;
cin >> n;
set<int>s;
for(int i = 1; i <= n / 2; i++)
{
cin >> c[i];
b[i] = {c[i], i};
s.insert(c[i]);
}
if ((int) s.size() < n / 2)
{
cout << "-1\n";
return;
}
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(s.count(i)) continue;
cnt++;
c[cnt] = i;
}
sort(b + 1, b + 1 + n / 2);
for (int i = 1; i <= n / 2; i++) a[b[i].pos] = c[i];
sort(b + 1, b + 1 + n / 2, cmp);
for (int i = 1; i <= n / 2; i++)
{
if (max(a[i], b[i].val) != b[i].val)
{
cout << "-1\n";
return;
}
}
// cout << "==============\n";
// for (int i = 1; i <= n / 2; i++) cout << a[i] << " ";
// cout << "\n=================\n";
for (int i = 1; i <= n / 2; i++)
{
f[b[i].val] = a[i];
pos_tree[a[i]] = b[i].val;
pos_a[a[i]] = i;
}
for (int i = 1; i <= n; i++)
{
if (f[i] == 0) f[i] = 1e18;
}
Seg.build(1, 1, n);
// cout << "=============\n";
// for (int i = 1; i <= n; i++) cout << Seg.que(1, i, i) << " ";
// cout << "\n===========\n";
for (int i = 1; i <= n / 2; i++)
{
while(1)
{
int val = Seg.que(1, a[i] + 1, n); //获取到最小值
if (val < 1 || val > 1e18) break;
if (val >= a[i])
{
Seg.up(1, pos_tree[a[i]], pos_tree[a[i]], 1e18); //销毁,防止后面的查到
break;
}
//树上换位置,a[]中也要换位置,两个映射也变了
Seg.up(1, pos_tree[val], pos_tree[val], a[i]); //val的值改成a[i]
Seg.up(1, pos_tree[a[i]], pos_tree[a[i]], val); //a[i]值改val
int p = pos_a[val];
swap(pos_a[a[i]], pos_a[val]);
swap(pos_tree[a[i]], pos_tree[val]);
swap(a[i], a[p]);
}
// for (int j = 1; j <= n / 2; j++) cout << a[j] << " ";
// cout << "---\n";
}
for (int i = 1; i <= n / 2; i++) cout << a[i] << " " << b[i].val << " ";
cout << "\n";
for (int i = 1; i <= n; i++)
{
pos_tree[i] = pos_a[i] = 0;
a[i] = c[i] = 0;
b[i] = {0, 0};
f[i] = 0;
}
}