牛客小白月赛99（A,B,C,D,E,F,G）

比赛链接

不会还有人不知道官方在B站有号吧$\Rightarrow$官方题解
不过讲课的可能是随机轮的志愿者，所以质量良莠不齐，有时候可能会听不太懂。

这场题总的来说质量还是蛮高的，E是贪心，需要先缩一下块。F是不是很裸的完全背包。G是两个离散化加上 $multiset$ 和树状数组维护。G题比较难写，不过几个数据结构并没有连起来用，而是分阶段的，对于练习思维能力比较好。

最近实在是有些难受，去医院查了一下诊断是抑郁、焦虑和睡眠障碍，记忆力也下降了不少。最近可能更新题解的速度会比较慢，可能更多的是更单题，比较省时。嗯。

---

A 材料打印

思路：

$a$ 张可以彩印也可以黑白，为了省钱所以取便宜的打印，价格就是 a ∗ m i n { x , y } a*min\{x,y\} a∗min{x,y}，$b$ 张彩印价格就是 $b\ast y$。

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;int T;
ll a,b,x,y;int main(){cin>>T;while(T--){cin>>a>>b>>x>>y;cout<<a*min(x,y)+b*y<<endl;}return 0;
}

---

B %%%

思路：

因为要求取模次数最多，那么每次取模后的余数都要尽可能大，因为余数不会大于模数，所以模数也得尽量大。

我们模数取 $n$ 的一半多一点点，这样余数就是 $n$ 的余数少一点点。发现无论模数变大还是变小，得到的余数都不会更大了，这时候就是余数最大的情况。

当 $n$ 为奇数时，我们取 $\frac{n+1}{2}$ 即可，余数为 $\frac{n-1}{2}$。当 $n$ 为偶数时，我们取 $\frac{n}{2}+1$ 即可，余数为 $\frac{n}{2}-1$。因为每次 $n$ 都会变成原来的一半还要少，所以这个过程最多只有 ${\log }_{2}n$ 次。模拟一下这个过程，然后记录用了多少步即可。

记得开long long

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;int T;
ll n;int main(){cin>>T;while(T--){cin>>n;int cnt=0;while(n){cnt++;n=(n-1)/2;}cout<<cnt<<endl;}return 0;
}

---

C 迷宫

思路1（bfs）：

比较直接的思路就是我们找到所有从起点出发可以到达的格子，以及所有从终点出发可以摸到的格子和墙（如果我们破开这种墙，就能从这个位置直接走到终点了），这样如果起点到达的格子与终点到达的墙在一条线上，那么就说明是 YES。

所以 $bfs$ 两次，标记两种格子，最后再每行每列找一下就行了。

code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define pii pair<int,int>
const int maxn=1005;int n,m;
queue<pii> q;
int fx[]={0,0,1,-1},fy[]={1,-1,0,0};string mp[maxn];
bool vis[2][maxn][maxn];bool check(){for(int i=1;i<=n;i++){bool f[2]={false};for(int j=1;j<=m;j++){f[0]|=vis[0][i][j];f[1]|=vis[1][i][j];}if(f[0] && f[1])return true;}for(int j=1;j<=m;j++){bool f[2]={false};for(int i=1;i<=n;i++){f[0]|=vis[0][i][j];f[1]|=vis[1][i][j];}if(f[0] && f[1])return true;}return false;
}int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>mp[i];mp[i]=" "+mp[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='S'){q.push(pii(i,j));while(!q.empty()){auto [ux,uy]=q.front();q.pop();vis[0][ux][uy]=true;for(int i=0,x,y;i<4;i++){x=ux+fx[i];y=uy+fy[i];if(x<1 || x>n || y<1 || y>m || vis[x][y] || mp[x][y]=='#')continue;q.push(pii(x,y));}}}else if(mp[i][j]=='E'){q.push(pii(i,j));while(!q.empty()){auto [ux,uy]=q.front();q.pop();vis[1][ux][uy]=true;if(mp[ux][uy]=='#')continue;for(int i=0,x,y;i<4;i++){x=ux+fx[i];y=uy+fy[i];if(x<1 || x>n || y<1 || y>m || vis[1][x][y])continue;q.push(pii(x,y));}}}puts((check())?"YES":"NO");return 0;
}

思路2（dp）：

发现从起点到终点的路径格子上的状态也就是 $自由bfs\to 向某个方向穿墙\to 自由bfs$，我们用 $0,1,2$ 分别来表示这三个状态，我们可以设 $dp[x][y][i][0/1/2]$ 来表示能否到达 $(x,y)$ 位置上，处于某个状态（如果是 $1$ 状态，则向 $i$ 方向穿墙）的格子。然后 $bfs$ 递推就好了。

code：

队长的代码

---

D 又是一年毕业季

思路：

当某个人的眨眼频率为 $a_i$ 时，那么 $a_i$ 的倍数这个学生都会眨眼，也就都不能选做拍照的时刻，而对于 $a_i$ 的因子则无限制（至少对这个学生来说没事）。

同时呢，我们又知道一个质数肯定不是其他数的倍数，所以我们猜测答案就是最小的未出现在 $a_i$ 的质数。

因为没有一个 $a_i$ 是它的倍数，所以它一定可以选做拍照时刻，而因为它是最小的未出现过的质数，也就是说更小的质数出现过，那么这些更小的质数会筛掉它们的倍数，所以更小的范围内的数一定都被筛掉了（因为质数都出现了，合数可以拆成更小的质数的乘积，这样也一定都被筛掉了），这个数就是最小的可以选做拍照时刻的数。

因此这个题先用质数筛出大约 $2\times 10^5$ 个质数，然后从小到大一个一个验证一下是否存在即可。第一个不存在的质数即为答案。

code：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=5e4+5;int T,n;bool vis[maxn*50];
int prime[maxn*2],cnt;
void Eular(){for(int i=2;cnt<maxn*2;i++){if(!vis[i])prime[++cnt]=i;for(int j=1,p=prime[j];j<=cnt && i*p<maxn*50;p=prime[++j]){vis[i*p]=true;if(i%p==0)break;}}
}int main(){cin.tie(0)->sync_with_stdio(false);Eular();cin>>T;while(T--){cin>>n;set<int> S;for(int i=1,t;i<=n;i++){cin>>t;S.insert(t);}for(int i=1;i<=cnt;i++){if(S.find(prime[i])==S.end()){
//				printf("%d\n",prime[i]);cout<<prime[i]<<"\n";break;}}}return 0;
}

---

E 多米诺骨牌

思路：

我们想，一个骨牌倒塌有可能会连带着后面的骨牌一起倒塌，假设我们推倒第 $l$ 个骨牌会导致 $[l,r]$ 区间内的骨牌一起倒塌，那么我们选择了第 $l$ 个骨牌后再选 $(l,r]$ 范围的骨牌就是浪费，没有意义。

假设我们把这种推倒某一个骨牌能产生连锁反应的连续的段看成一个块，并将其预处理出来了。那么只要想推倒某个块就去推倒这个块的第一个骨牌就好了，既然每个块的代价都一样，那么肯定贪心地选大的块来推。

处理块可以用从前向后处理，当前一个骨牌无法推倒后一个骨牌时，就从中间断开，断点与断点之间的骨牌就是一个完整的块了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+5;int T,n,m;
pii a[maxn];int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++){auto &[pos,h]=a[i];cin>>h;}for(int i=1;i<=n;i++){auto &[pos,h]=a[i];cin>>pos;}sort(a+1,a+n+1);vector<int> t;int cnt=1;for(int i=2,lst=a[1].first+a[1].second;i<=n;i++){auto [pos,h]=a[i];if(lst>=pos){cnt++;}else {t.push_back(cnt);cnt=1;}lst=max(lst,pos+h);}t.push_back(cnt);sort(t.begin(),t.end(),greater<int>());int ans=0;for(int i=0;i<min(m,(int)t.size());i++)ans+=t[i];cout<<ans<<endl;}return 0;
}

---

F 自爆机器人

思路：

如果不建造墙的话，那么最短运动时间其实就等同是起点到终点的距离。所以如果当机器人的最大起爆时间连这个时间都等不了就说明造成不了伤害。

如果当机器人运动到某个区间时，在这个区间两端造墙，那么机器人多走的时间其实就是两倍区间长。只要我们选一次，起爆时间就会增加两倍区间长。这相当于完全背包问题了。

但是问题是端点有 $n$ 个，把所有区间都处理出来就需要 $C_n^2=\frac{n\ast (n-1)}{2}$ 个，用完全背包做就会超时。但是发现我们可以把区间拆成两端，比如 $[1,3]$ 可以拆成 $[1,2]$ 和 $[2,3]$，区间总体的两倍长不就是两端子区间两倍长之和嘛，所以我们不需要把所有区间都表示出来，只用两相邻点之间的 $n-1$ 个区间就行了（这样一个长区间就可以通过多端相邻短区间拼起来得到）。

所以这个题先处理出两相邻点之间的 $n-1$ 个区间的两倍长度，然后把它们作为完全背包的物品，之后接着完全背包来做就可以了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=2e5+5;int T,n,m,t;
int x[maxn],dp[maxn];//能否到达i时间 int main(){cin.tie(0)->sync_with_stdio(false);cin>>T;while(T--){cin>>n>>m>>t;for(int i=1;i<=t;i++)dp[i]=0;dp[n]=1;for(int i=1;i<=m;i++)cin>>x[i];sort(x+1,x+m+1);set<int> S;for(int i=2,v;i<=m;i++)S.insert((x[i]-x[i-1])*2);for(auto v:S)for(int j=v;j<=t;j++)dp[j]|=dp[j-v];int ans=0;for(int i=t;i>=0;i--)if(dp[i]){ans=i;break;}cout<<ans<<'\n';}return 0;
}

---

G 大鱼吃小鱼

思路：

我们把一个鱼出现的时间段看成一个区间，发现其实对于区间中间的部分我们是不怎么关心的，只关心区间端点处（左端点出现和右端点消失的位置）就行了。这样可以对所有区间的左右端点进行离散化，剩余的点就只有 $2\times 10^5$ 了。

枚举每个点，对每个点处，有若干条鱼存在在这个时间点上，假设我们已经处理出来这个时间点存在的所有鱼，那么我们需要在 $\log n$ 左右的时间内算出这个点处的最大重量。我们可以用二分查找到第一个吃不到的鱼，它的重量是 $y$（也就是第一个 $y>x$），我们吃掉它前面的所有鱼，然后再看能不能吃掉这条鱼，如果能就吃掉，不能就可以直接返回最大重量值了。

因为我们每次找都到 $y$ 后，如果吃掉了它，体重至少会变成 $x+\cdots +y>2x$ ，也就是体重至少翻一倍，倍增的时间复杂度是 $\log$ 的，因此我们最多找 $\log$ 次就可以了。这样找体重的时间就是 ${\log }^2$ 的，可以接受。

我们处理出某个时间点上的所有鱼，可以用 $multiset$ 来维护，把区间拆成左端点和右端点，可以存在 $vector$ 里，当看到左端点时就往集合内加入这条鱼，否则就删掉一条同重量的鱼。

而在一个时间点上二分找第一个吃不到的鱼可以直接在 $multiset$ 上完成，但是在累加前面吃掉的所有鱼的重量时不能暴力来算，这样累加时间最坏会变成 $O(n)$ 的。这里可以用树状数组来存储某个重量区间内的所有鱼重量。但是重量是 $10^9$ 的，所以鱼的重量也得离散化一下。

code：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;int T,n,x;struct BIT{int n;vector<ll> tr;int lowbit(int x){return x&-x;}void build(int _n){n=_n+1;tr.resize(n+1);}void add(int id,ll x){for(int i=id;i<=n;i+=lowbit(i))tr[i]+=x;}ll query(int id){ll ans=0;for(int i=id;i;i-=lowbit(i))ans+=tr[i];return ans;}ll query(int l,int r){return query(r)-query(l-1);}
}tr;int find(ll x,vector<int> &t){//找到x离散后的位置 return lower_bound(t.begin(),t.end(),x)-t.begin()+1;
}ll solve(){cin>>n>>x;vector<array<int,3> > a(n+1);vector<int> ta,tb;tb.emplace_back(x);for(int i=1;i<=n;i++) {auto &[l,r,y]=a[i];cin>>l>>r>>y;ta.emplace_back(l);ta.emplace_back(r);tb.emplace_back(y);}sort(ta.begin(),ta.end());ta.erase(unique(ta.begin(),ta.end()),ta.end());sort(tb.begin(),tb.end());tb.erase(unique(tb.begin(),tb.end()),tb.end());vector<vector<int> > pos(2*n+1,vector<int>());for(int i=1;i<=n;i++){auto &[l,r,y]=a[i];pos[find(l,ta)].emplace_back(y);pos[find(r,ta)].emplace_back(-y);}multiset<ll> S;//某一位置下所有鱼的重量int m=tb.size()+1;tr.build(m+1);//鱼的重量和ll ans=x;for(int i=1;i<=2*n;i++){for(auto k:pos[i]){if(k>0){S.insert(k);tr.add(find(k,tb),k);}else {k=-k;S.erase(S.find(k));tr.add(find(k,tb),-k);}}ll w=x;int t,id,lst=1;while(true){auto it=S.upper_bound(w);if(it==S.end()){w+=tr.query(lst,m);break;}t=*it;//第一个重量大于w的鱼 id=find(t,tb);if(lst>=id)break;w+=tr.query(lst,id-1);if(w>=t){w+=tr.query(id,id);lst=id+1;}else {break;}}ans=max(ans,w);}return ans;
}int main(){cin.tie(0)->sync_with_stdio(false);cin>>T;while(T--){cout<<solve()<<endl;}return 0;
}