今天的后两题不会也是真不会
1 Longest K-good Segment{
-
题意：我们规定，如果一个数组中的某一个区间内满足不同的数的个数超过k个，则称这个区间为K-good区间。请你求出最长的k-good区间，并保证区间内不同个数的数字不超过m个
-
思路：我们需要定义两个指针来维护最大区间长度。定义一个cnt数组，如果出现不同数字，则
cnt[num[i]]++,如果一开始时cnt[num[i]]==0,说明是第一次出现，那么区间长度加1，当区间内不同数字超过m时，cnt[num[m]]--,如果等于0则长度减1，当区间长度大于原始长度时：r-l+1>ansr-ansl+1时，更新答案
}
核心代码：
while(r<n){
r++;
if(cnt[sam[r]]==0) dist++;//如果第一次出现更新不同数的个数
cnt[sam[r]]++;
while(dist>m){
cnt[sam[l]]--;//长度超限移动左端点
if(cnt[sam[l]]==0) dist--;//如果出现次数已经减到不能再减那么个数减一
l++;
}
if(r-l+1>ansr-ansl+1){//更新区间长度
ansr=r;//更新答案
ansl=l;
}
}
2 Range Update Point query{
-
题意：有一个数组，长度为n,你可以对给定区间内的数进行两种操作，1：将原区间中的数变成其所有位数之和。2：输出原数组中的某一项。对于每一次操作2，你需要输出正确的值
-
思路：这题需要我们将原数组中的项变成数的位数之和，因此我们可以将大于等于10的项先用集合set标记。
为什么是用集合？因为我们之后要在遇到经过操作后小于10的数进行删除，而只有set能做到O(1)的添加与删除
然后我们就可以用it指针指向区间内的第一个数，并进行sum运算
- 算法：动态数据结构
}
核心代码：
while(q--){
int op; cin>>op;
if(op==1){
int l,r;
cin >> l >> r;
auto it=st.lower_bound(l);//找到第一个需要更新的区间位置
while(it!=st.end()&&*it<=r){
int idx=*it;
a[idx]=sum(a[idx]);//更新数值
if(a[idx]<10) it=st.erase(it);
else it++;
}
}
3 Tracking Segment{
-
题意：有一组初始时全是0的数组，你可以对给定的项赋值为1。现在给定一组区间，要求如果这个区间内0的个数严格小于1的个数，则这个区间是美丽的。求第一次使得至少有一个给定区间为美丽区间的修改编号
-
思路：对于这道题的赋值我们可以用一个数组将每次赋值的下标存起来，这样方便我们下一步的进行。题目要求我们求出第一次使得至少有一个给定区间为美丽区间的修改编号，而这题中的数组一旦经过赋值便不能再改变，因此答案具有单调性，所以我们可以二分查找第一个修改编号。同时我们可以利用前缀和数组快速查找出给定区间内1的个数，判定条件为：
(pre[r]-pre[l-1])*2>len(只要1的个数大于整个区间的1/2，则这个区间一定为美丽区间) -
算法：二分，前缀和
}
核心代码：
bool check(int mid){
memset(a,0,sizeof(a));
for(int i=1;i<=mid;i++){
a[qu[i]]=1;//模拟赋值过程
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];//计算1的个数
}
for(int i=1;i<=m;i++){
int len=r[i]-l[i]+1;
int sum=pre[r[i]]-pre[l[i]-1];//计算区间内1的个数
if(sum*2>len){//如果1的个数严格大于0的个数
return true;
}
}
return false;
}
4 Fountains{
-
题意：你需要两个喷泉，喷泉需要用金币或钻石去购买。给定初始时你有几个金币和钻石，以及每个喷泉的美丽值，所需的金币数或钻石数。对于每个喷泉，你需要买两个使得这两个喷泉的美丽值最大
-
思路：这题我们分三种情况讨论：
1 两个都用金币买：当我们的钻石数过少以至于一个要花钻石买的喷泉都买不起时，我们可以用金币来买自己能买的起并且美丽值尽可能大的喷泉
2 两个都用钻石买：思路与用金币买一致
3 一个用金币，一个用钻石：当我们钱数足够时，可以考虑买自己能花费的最大代价并且两个都取美丽值最大
讨论完上述三种情况以后，我们就可以贪心。两个喷泉都用不同货币买的情况只需要遍历一下整个数组查找最大美丽值即可。对于其余两种情况，我们可以在遍历数组时将只包含一种货币的喷泉都集中在一起并按货币大小升序排序。
为什么按货币升序排？是因为我们需要在满足美丽值尽可能大的同时能付得起价格。因此第一遍遍历时我们倒着查找最大美丽值，直到付不起价格为止，正序遍历时同样也是如此。
计算过程：
1 构造前缀最大值pref[i]=max(pref[i-1],coin[i-1])
2 倒序遍历数组直到prize>bugdet ，更新美丽值最大
3 再正序查找最多能付的起的喷泉，最终答案就是ans=max(ans,s[i].second+pref[p])//s[i]的第二项表示倒序遍历时得到的美丽值，pref[p]表示正序遍历时得到的最大美丽值
}
核心代码，主要是两个只用金币或钻石购买的部分：
int solve(vector<pair<int,int>>& s,int h){
sort(s.begin(),s.end());
int n=s.size();
vector<int> maxbeauty(n+1,0);
for(int i=1;i<=n;i++){
maxbeauty[i]=max(maxbeauty[i-1],s[i-1].second);
}
int ans=0,p=0;
for(int i=n-1;i>=0;i--){
int re=h-s[i].first;
if(re<=0) continue;//不能超过预算
while(p<i&&s[p].first<=re){//找前面能满足不超过预算的
p++;
}
p=min(p,i);
if(p>0){
ans=max(ans,s[i].second+maxbeauty[p]);//经过排序后的美丽值最大为当前能到达的不超过预算的美丽值
}
}
return ans;
}
5 Rescue Nibal{
-
题意：有一组灯以及灯亮的时间区间，求选择k盏灯同时亮的方案数
-
思路：
问题转化：有一组线段，求有重合部分的k个线段的组数
这题我虽然知道要用组合数学，但毕竟不熟悉，所以代码不会写，只能匆匆忙忙写个暴搜拿点暴力分，这里也提供一下暴力思路： dfs寻找最多的线段组数 当选到k时更新答案最大值
正解：组合数学+排序
我们可以假设当前已有重叠部分的线段数为c个,则我们对于总数k个灯泡可以有 error 个总方案数。但是如果直接相加会引发严重的数据重复，因为不同线段之间可能会有同一重复区间。因此我们可以令当前还选择初始时的线段，所以此时的c和k就变成了c-1和k-1,公式简化：error
知晓答案如何计算以后我们还要对其进行排序，以左端点越靠前或长度越短的线段为排序标准，然后每次遇到线段左端点时c++,遇到右端点c--,代入公式计算就行
- 算法：组合数学，排序
}
AC代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=6e5+10;
const int Mod=998244353;
struct Event{
int time,type;
}e[N];
ll f[N],inf[N];
bool cmp(const Event &a, const Event &b){//按时间大小排序，时间相同的优先左端点更靠前的
if (a.time!=b.time) return a.time<b.time;
return a.type>b.type;
}
ll qpow(ll a,ll b,ll q){//快速幂
ll ans=1;
while(b){
if (b&1) ans=(ans*a)%q;
a=(a*a)%q;
b>>=1;
}
return ans;
}
void init(int n) {
f[0]=inf[0]=1;
for (int i=1;i<=n;i++){//预处理逆元
f[i]=f[i-1]*i%Mod;
inf[i]=inf[i-1]*qpow(i,Mod-2,Mod)%Mod;
}
}
ll C(int n,int m){//对应上述公式
if (m<0||m>n) return 0;
return f[n]*inf[m]%Mod*inf[n-m]%Mod;
}
int main() {
int n,k;
cin >> n >> k;
init(n);
int tot=0;
for (int i=1;i<=n;i++){
int l,r;
cin >> l >> r;
e[++tot]={l,1};
e[++tot]={r,-1};
}
sort(e+1,e+tot+1,cmp);
ll cnt=0,ans=0;
for (int i=1;i<=tot;i++){
if(e[i].type==1){
cnt++;
ans=(ans+C(cnt-1,k-1))%Mod;
} else{
cnt--;
}
}
cout<<ans;
}
6 Too many segments{
-
题意：有一组线段，规定：如果一个整数点满足其被超过k条线段覆盖，那么则称这个点为坏点，求一个最少的删除次数使得删除若干条线段后的区间内无坏点
-
思路：这题的思路其实跟上题差不多，都是区间重合问题。问题就在于上一题针对找，这题针对删。我们可以简单头脑风暴一下，如果当我们遍历数组时遍历到了第x个点，且当前节点被若干条线段覆盖，那么先删哪一条？是删最长的？最靠右的？最靠左的？最靠中间的？重合集最多的？
答案是：最靠右的。
为什么是最靠右的？我们设想一下，我们遍历数组是从左往右遍历，如果放着这样一个最靠右的线段不删，那么这个线段会一直影响我们之后的节点的答案统计。虽然这题删其他的线段如最长线段同样会使得答案计算的影响最小，但删除最靠右的线段会保证我们的决策不会比上一步更差
因此我们可以利用大根堆维护以右端点的直更大的线段在前，取一个右端点的最大值，以免不必要的遍历。遍历数组时，当堆顶右端点已经小于当前端点时，直接弹出。当当前端点的线段覆盖的个数超限时，不断的弹出并更新删除个数
- 算法：优先队列，贪心
}
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<pair<int,int>> head[N];
set<pair<int,int>> s;
int ans[N],ans_cnt=0;
int main(){
int n,k;
cin >> n >> k;
int maxr=0;
for(int i=1;i<=n;i++){
int l,r;
cin >> l >> r;
head[l].push_back({r, i});
maxr=max(maxr,r);
}
for(int i=1;i<=maxr;i++){
for(auto &item:head[i]){
s.insert(item);
}
while(!s.empty() &s.begin()->first<i){
s.erase(s.begin());//没有价值的，右端点小于当前端点的删除
}
while(s.size()>k){//超出限制
auto it=prev(s.end());
ans[++ans_cnt]=it->second;//表示要删除的线段标号
s.erase(it);
}
}
cout<<ans_cnt<<endl;
for (int i=ans_cnt;i>=1;i--){
cout<<ans[i]<<" ";
}
}
评论
0