牛客挑战赛74题解
前言
本场比赛由 北京第二外国语成都附属中学 信息竞赛团队出题。
本场比赛是由 练习赛 升为 挑战赛，所以题目会更加简单，并不是完全的挑战赛难度。
谢罪 题数据疑似放过非正解做法，导致于难度大大降低。
A：
对于任意偶数前缀 ，可以发现
中一定已经选择了
个糖果，所以对于
中一定需要选择一个，贪心的一定选择最大的，即可保证对于任意前缀均满足选择于没选择的个数差值在
以内。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> s(n + 2);
for(int i = 1;i <= n; i ++)
cin >> s[i];
long long ans = 0;
for(int i = 1;i <= n ;i += 2){
ans += max(s[i],s[i + 1]);
}
cout << ans <<"\n";
}
B：
贪心的考虑，对于任意斧子肯定会选择没有被砍的最大的树木进行劈砍，实现方式很多，可以考虑双指针/set 等方式直接进行计算。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for (int i = 1; i <= n ; i ++)
cin >> a[i];
for (int i = 1; i <= m ; i ++)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int ans = 0;
for (int i = n, j = m; i; i--) {
if (b[j] >= a[i])ans++, j--;
}
cout << ans << "\n";
}
C：
究极分类讨论题
对于该问题需要考虑所有可能的情况在注释中，可针对注释进行细品。
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;cin >> T;
while(T--){
long long a, b, c, d;
cin >> a >> b >> c >> d;
long long ans = max(a + b, c + d);
// A D
ans = min({ans, max(max(a, d) + b / 2, max(a, d) + c / 2)});
// B C
ans = min({ans, max(max(b, c) + a / 2, max(b, c) + d / 2)});
// A B
ans = min(ans, a + max(c / 2, b) + d / 2);
ans = min(ans, b + max(d / 2, a) + c / 2);
// C D
ans = min(ans, c + max(a / 2, d) + b / 2);
ans = min(ans, d + max(b / 2, c) + a / 2);
ans = min(ans, max(a + b, max(a, d) + c / 2));
ans = min(ans, max(a + b, max(c, b) + d / 2));
ans = min(ans, max(c + d, max(b, c) + a / 2));
ans = min(ans, max(c + d, max(a, d) + b / 2));
cout << ans << "\n";
}
}
D:
一个比较小思维的暴力维护题，核心思想在于每个员工最多死一次，且每次治疗均为一个员工，所以实际上存在一个对员工进行操作的势能。
如果使用线段树/分块等等操作也是能实现的，甚至能完成更多操作。
对于本题而言，考虑需要一个数据结构，可以维护当前最小生命的员工，当该员工的生命小于历史攻击总计伤害，那么代表该角色死亡。
同时该结构最好还满足插入，删除等操作，最终可选择的结果依据实现简单程度排序有 set / 堆 / 优先队列...，std采用set来暴力维护。
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
i64 n,m,k;
cin >> n >> m >> k;
vector<i64> a(n + 1),b(n + 1),hp(n + 1);
set<pair<i64,i64>> se;
i64 sum = 0,old = 0;
for(int i = 1;i <= n; i ++)
cin >> a[i];
for(int i = 1;i <= n ;i ++)
cin >> b[i];
int cnt = n;
for(int i = 1;i <= n; i ++){
hp[i] = b[i];
se.insert({b[i],i});
sum += a[i];
}
while(k --){
int op;cin >> op;
if(op == 1){
int x;cin >> x;
sum += a[x];
se.insert({hp[x] = old + b[x],x});
}else if(op == 2){
int x;cin >> x;
sum -= a[x];
se.erase({hp[x],x});
}else if(op == 3){
int y;cin >> y;
old += y;
while(se.size() && se.begin() -> first <= old){
cnt --;
sum -= a[se.begin()->second];
se.erase(se.begin());
}
}else{
int x,h;
cin >> x >> h;
se.erase({hp[x],x});
se.insert({hp[x] = min(old + b[x],hp[x] + h),x});
}
m -= sum;
if(m <= 0)break;
}
if(m > 0){
cout <<"NO\n";
}else {
cout <<"YES\n";
cout << cnt <<"\n";
}
}
E:
题意
给定可快速求和的分段函数，求
，这个题目和
是什么并不关键，它可以是任意的可
计算值或者前缀和的函数。
求解思路
为什么是这个题意，需要一步差分转化。
设表示差分函数。
则有
说人话就是本来有一个对于的整除分块求和，假设是
，那么显然从
到
，
种只有枚举到
的因子时，才会有值发生变化。
所以题目里面每天升级因子相关的贸易站，实际上就是在加整除分块的差分，转化后就是
的标准形式。
然后和式变形有个老生常谈的问题。
对于二维求和，要么计算
要么计算
。看哪个好算。
发现如果先枚举，虽然能用整除分块计算里面的
部分，但是外面的求和不好搞。
所以换个思路，把当成变量，固定
计算，发现贸易等级和剩余贸易点数都是好计算的，如果
是定值
，最终的贸易等级就是
，并且每个贸易等级出现
次，还剩余
点贸易点数，对这个东西整除分块，剩下的交给等差数列求和。
如果你没懂，我建议不要使用纯数学方法推导，这个东西一定要数形结合。
如图，是的函数表，如果去掉
的部分，我们发现第
列函数值每
个一循环，假设求到第
行，一共循环了
次，还剩下
个，借助整除分块，我们知道分块后
是一个定值，
是一个等差数列，例如上图中绿的大方块中的小绿色矩形部分，它就表示首项为
，公差为
的等差数列。
对于分段函数，可以借助双指针合并，或者离线出来每一段的查询进行处理。
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009;
namespace chino {
template<int mod>
class ModInt {
private:
const static int MD = mod;
int x{};
public:
ModInt(long long x = 0) : x(x % MD)
{}
int get() {
return x;
}
ModInt operator+(const ModInt& that) const {
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt& that) const {
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt& that) const {
return ModInt((long long) x * that.x % MD);
}
ModInt operator/(const ModInt& that) const {
return *this * that.inverse();
}
ModInt operator+=(const ModInt& that) {
x += that.x;
if (x >= MD)
x -= MD;
return x;
}
ModInt operator-=(const ModInt& that) {
x -= that.x;
if (x < 0)
x += MD;
return x;
}
ModInt operator*=(const ModInt& that) {
return x = (long long) x * that.x % MD;
}
ModInt operator/=(const ModInt& that) {
return *this = *this / that;
}
ModInt inverse() const {
int a = x, b = MD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u += MD;
return u;
}
};
} // namespace chino
using Int = chino::ModInt<mod>;
using i64 = long long;
const Int inv2 = Int(2).inverse();
class F {
private:
Int _base_v{};
Int _A, _B;
i64 _base{};
public:
i64 L{};
F(i64 A, i64 B) : _A(Int(A)), _B(Int(B)) {
}
i64 get_next() const {
return _base + L + 1;
}
Int operator()(i64 x) const {
x -= _base;
return _A * L * L + _B * x;
}
Int operator[](i64 x) const {
Int begin = this->operator()(_base);
Int end = this->operator()(x);
return _base_v + (begin + end) * (x - _base + 1) * inv2;
}
void next() {
_base_v = this->operator[](get_next() - 1);
_base = get_next();
L++;
}
};
Int s(i64 n, i64 m, i64 A, i64 B, i64 C) {
Int ret = Int(n) * m * C;
if (m > n) {
m = n;
}
F f(A, B);
vector<i64> pos;
vector<Int> ans[2];
for (i64 l = 1, r; l <= m; l = r + 1) {
r = min(m, n / (n / l));
pos.push_back(n / l);
}
std::reverse(pos.begin(), pos.end());
ans[0].resize(pos.size());
ans[1].resize(pos.size());
for (auto i = 0; i < pos.size(); ++i) {
while (f.get_next() <= pos[i])f.next();
ans[0][i] = f(pos[i]);
ans[1][i] = f[pos[i]];
}
std::reverse(ans[0].begin(), ans[0].end());
std::reverse(ans[1].begin(), ans[1].end());
auto cur = 0;
for (i64 l = 1, r; l <= m; l = r + 1) {
r = min(m, n / (n / l));
Int val = n / l;
Int len = (r - l + 1);
Int a = n % r + 1;
ret += ((len * len - len) * val * inv2 + a * len) * ans[0][cur];
ret += (len * (l + r) * inv2) * (ans[1][cur] - ans[0][cur]);
cur++;
}
return ret;
}
int main() {
i64 n, m, A, B, C;
cin >> n >> m >> A >> B >> C;
cout << s(n, m, A, B, C).get() << endl;
return 0;
}
F:
根据题面可以发现，实际上齿轮转一圈，等价于数字进位一次，由于齿轮齿数的不同，可以形似于一个不同进制的数字。
考虑数位DP，由于数位DP本身就需要将数字进行分解，所以使用数位DP维护一个上下界数位DP，DP中维护一个最大可伤害生命值，此时二分最大时间，即可查询区间 中的最大生命，来判断该时间内是否拥有能击杀果酱的伤害。
考虑不维护上届，直接二分左边界，可以通过数位DP找到对应能击杀果酱的大于等于 的最小时刻，如果该时刻小于等于
，那么也可以击杀果酱。
由于二分该过程实际上和倍增十分类似，考虑倍增数位DP，每次增加来判断出大于等于 的最小时刻，此时复杂度不变。
如果一开始预处理出对于每个时刻后的最大可造成伤害，那么可以将倍增过程和数位DP的枚举过程进行融合，此时倍增的复杂度将被消掉，即体现出，对数位DP进行剪枝。总体复杂度为 。
#include<bits/stdc++.h>
using namespace std;
long long b[110][55],H[110][55],a[110],pp[110],p[110];
long long check(long long a,long long b){
if(b == 0)return 0;
if(a == -1)return 2e18;
if(a >= (long long)2e18 / b)return 2e18;
return a * b;
};
int cnt = 0;
long long h,l,r;
long long dfs(int u,int lim,long long res){
if(u == 0)return 0;
long long ans = 2e18;
cnt ++;
for(int i = (lim ? p[u] : 0);i < a[u];i ++){
if(H[u][i] >= res){
if(check(pp[u - 1],i) > r)return 2e18;
ans = min(ans,dfs(u - 1,(i == p[u]) ? lim : 0,res - b[u][i]) + check(pp[u - 1],i));
if(i != p[u] || lim == 0 || ans < (long long)2e18){
return ans;
}
assert((i == p[u]) ? lim : 0);
}
}
return ans;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,q;
cin >> n >> q;
for(int i = 1;i <= n ;i ++){
cin >> a[i];
for(int j =0 ;j < a[i]; j ++){
cin >> b[i][j];
H[i][j] = b[i][j];
}
}
for(int i = 2;i <= n ;i ++){
long long res = *max_element(H[i - 1],H[i - 1] + a[i - 1]);
for(int j = 0 ;j < a[i];j ++){
H[i][j] += res;
}
}
pp[0] = 1;
for(int i = 1;i <= n;i ++){
if(pp[i - 1] == - 1 || pp[i - 1] >= (long long)2e18 / a[i])pp[i] = -1;
else pp[i] = pp[i - 1] * a[i];
}
while(q--){
cin >> h >> l >> r;
long long L = l;
for(int i = 1;i <= n; i ++){
p[i] = L % a[i];
L /= a[i];
}
cnt = 0;
long long R = dfs(n,1,h);
assert(cnt <= 4 * n);
if(R > r)cout <<"-1\n";
else cout << R <<"\n";
}
}
G:
首先，对于该问题的区间查询，可以先利用莫队将区间查找变成每次增删 数组中一个点。
整个问题转变为可重集合中有多少个点能和 数组匹配。
对于该匹配问题，可以对 数组进行排序，可以证明排序之后不影响匹配结果。
假设存在一个数组 代表剩余斧子的数目。
首先初始状态一定全为 。
对于加入进来一个为 的树，那么需要找到至少需要多少数值的斧子，才能砍伐该树。
假设找到一个值为第 小的斧子才能砍伐该
的树木，可以将
。即代表至少需要该斧子一把。
可以发现，这样处理会让 数组中存在负数，但是对于更大的斧子，是可以平替小斧子的，所以只要
数组的后缀和不是负数，那么均可以完美匹配。如果该数组的后缀和出现负数
，那么代表却缺少
把斧子来填补该位置的负数。
考虑一个树木填充进来对后缀数组的影响，那么对于 则该数组的后缀和数组的前缀
均减
，同理不管是对于补充一个斧子
还是减少一棵需要斧子
的树木，均会使该数组的后缀和数组的前缀
加
。
则对于该数组的后缀和数组出现负数，则需要至少 吧斧子才能将无法砍伐的树木填充至完美匹配，则可以通过区间修改，区间查询最小值的线段树来解决该方案中缺少多少。
时间复杂度为 。
考虑该方案在 情况下，需要运行至少
。
考虑优化，将莫队删除。
考虑将查询存于右端点处，从左往右不断的添加树木进来。
对于添加进树木之后该方案是否合理，可以通过线段树来判断当前情况下是否需要添加斧子进来匹配。
所以只要出现负数，那么说明当前匹配方案不合理。后缀中第一个出现负数的地方即为多出来的需要的斧子的大小。
所以如果想要保留当前进来的该树木，则至少需要腾出一个占用需要斧子的大小的树木才行。
下面考虑两种问题：
Q:对于多出来的树木如果不低于该树木，应该砍伐哪一个树木？
A:对于多出来的树木，需要使得腾出一把斧子，能够满足当前树木的需求，所以可以寻找所有不等于该树木的树木成为多出来的树木。由于对于两棵树木而言，该腾出那颗树木，考虑由于已经固定右端点，每次询问时均询问的左端点右边的保留树木，所以对于两颗树木而言，如果选择删除靠右的树木，则会导致可能少匹配一把斧子，对于选择删除左边的树木，则能保证在当前状态下最优。
Q:对于多出来的树木如果低于当前树木，是否会存在一种情况，使得不选择当前树木更优。
A:如果存在多出来的树木低于该树木，则说明该数组的后缀和中位于该树木所需的斧子数不为负数，则一定为小的树木过多，导致占用了该树木相对于的最小的斧子。由于该树木更靠右端，所以不存在某种情况会选择低的树木而不选择该树木。
得证，在转移过程中如果需要删除斧子与树的匹配关系，可以挑选出唯一的树木，来使得当前局面一定最优。
所以可以使用线段树1，来计算是否存在斧子不够用的情况。
可以通过线段树2，来寻找替换哪个树木。
对于线段树3，可以用来记录区间保留了多少个树木。
DX 的理解
由于DX验题的适合，提出了一个与出题人完全不同的理解，但是最终写出了完全相同的代码，所以将DX的理解也放出来。
离线扫描线。
考虑每棵树 会被哪个斧子砍掉，肯定尽可能选择
最小的斧子。
对于单组询问的情况，将所有树挂在对应的斧子上，前缀和扫一遍就可以了。
（这里有一张图，图在下方）
注意一个事实：树之间是本质相同的，它们的区别只有“位置”，两棵不同位置的树在后移到同一个位置之后是无须区分的，只需随意保留一个即可。
所以对于每个斧子维护它会砍掉哪个树 ，初始
。加入一个新的树的时候，我们可以直接从加入的位置向后扫一遍，如果
小于当前的树的
，则交换
即可。由于我们的贪心告诉我们只需要让一个位置有一棵树被保留就可以，所以优先保留更可能在询问区间里的树是优的。
（这里有一张图，图在下方）
这里显然就可以用回转寿司 Trick 做到 了，能不能更优呢？
我们注意到虽然我们维护了新的序列 ，但是这个序列仍然是从最后留在序列里的若干个树所在的初始位置生成而成，并且我们只关心有哪些数留在序列里，所以我们可以继续维护生成
的信息。
此时，如果我们加入一个数，可以删除另一个数当且仅当删完之后，生成的 仍然可以让每个位置都有一个数，对这部分的维护就是平凡的。
所以加入一个数的过程可以被刻画为以下四步：
- 加入一个数
- 找到能删数的位置
- 找到最小需要被删掉的数
- 删掉这个数
用线段树和堆维护一下就愉快地做完啦！
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N],b[N];
int n,m,q;
#define lson o << 1
#define rson o << 1 | 1
#define mid (l + r >> 1)
struct Seg1{
int tr[N * 4],lazy[N * 4];
void up(int o){
tr[o] = min(tr[lson],tr[rson]);
}
void add(int o,int x){
tr[o] += x;
lazy[o] += x;
}
void down(int o){
int &x = lazy[o];
if(x){
add(lson,x);
add(rson,x);
x = 0;
}
}
void build(int o = 1,int l = 1,int r = m + 1){
if(l == r){
tr[o] = m + 1 - l;
return ;
}
build(lson,l,mid);
build(rson,mid+1,r);
up(o);
}
void fixed(int o,int l,int r,int L,int R,int x){
if(L <= l && r <= R){
add(o,x);
return ;
}
down(o);
if(L <= mid)fixed(lson,l,mid,L,R,x);
if(mid < R)fixed(rson,mid+1,r,L,R,x);
up(o);
}
int Qurey(int o = 1,int l = 1,int r = m + 1){
if(l == r)return l;
down(o);
int ans = 1e9;
if(tr[rson] < 0)ans = Qurey(rson,mid+1,r);
else ans = Qurey(lson,l,mid);
up(o);
return ans;
}
void add(int x){
fixed(1,1,m + 1,1,x,-1);
}
void del(int x){
fixed(1,1,m + 1,1,x,1);
}
}seg1;
struct Seg2{
int tr[N * 4];
queue<int> qe[N];
void up(int o){
tr[o] = min(tr[lson],tr[rson]);
}
void build(int o = 1,int l = 1,int r = m){
if(l == r){
tr[o] = 1e9;
return ;
}
build(lson,l,mid);
build(rson,mid+1,r);
up(o);
}
void add(int o,int l,int r,int x,int c){
if(l == r){
qe[l].push(c);
tr[o] = qe[l].front();
return ;
}
if(x <= mid) add(lson,l,mid,x,c);
else add(rson,mid + 1,r,x,c);
up(o);
}
void del(int o,int l,int r,int x){
if(l == r){
qe[l].pop();
if(qe[l].size())tr[o] = qe[l].front();
else tr[o] = 1e9;
return ;
}
if(x <= mid)del(lson,l,mid,x);
else del(rson,mid+1,r,x);
up(o);
}
void add(int x,int c){
add(1,1,m,x,c);
}
void del(int x){
del(1,1,m,x);
}
int ask(int o,int l,int r,int L,int R){
if(L <= l && r <= R)return tr[o];
int ans = 1e9;
if(L <= mid)ans = min(ans,ask(lson,l,mid,L,R));
if(mid < R)ans = min(ans,ask(rson,mid+1,r,L,R));
return ans;
}
int ask(int l,int r){
return ask(1,1,m,l,r);
}
}seg2;
struct tree{
int tr[N];
int lowit(int x){return x & -x;}
void add(int x,int c){
for(;x<N;x+=lowit(x))
tr[x] += c;
}
int ask(int x){
int ans = 0;
for(;x;x-=lowit(x))
ans += tr[x];
return ans;
}
}tr;
int ans[N];
vector<pair<int,int>> Q[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;q = 1;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i<= m; i ++)
cin >> b[i];
sort(b + 1,b + m + 1);
seg1.build();
seg2.build();
for(int i = 1; i <= n ;i ++){
int x = lower_bound(b + 1,b + m + 1,a[i]) - b;
a[i] = x;
}
for(int i = 1;i <= q;i ++){
int l,r;
cin >> l >> r;
Q[r].push_back({l,i});
}
for(int i = 1;i <= n ;i ++){
int x = a[i];
if(x != m + 1){
seg1.add(x);
seg2.add(x,i);
tr.add(i,1);
if(seg1.tr[1] < 0){
int L = seg1.Qurey();
int y = seg2.ask(L,m);
int c = a[y];
seg1.del(c);
seg2.del(c);
tr.add(y,-1);
}
}
for(auto [l,id]:Q[i]){
ans[id] = (tr.ask(i) - tr.ask(l - 1));
}
}
for(int i = 1; i <= q;i ++)
cout << ans[i] <<"\n";
}
京公网安备 11010502036488号