\[\text{NOIP模拟赛-2023.11.6} \]
T1 视频监控
简单题，写复杂了
#include<bits/stdc++.h>
#define LL long long
using namespace std;
bool Mbe;
const int N=1e5+10;
int row,col,n,ansr,cntr,ansc,cntc;
int b[N<<1],rev[N<<1],tr[N<<1],sumr[N<<1],tc[N<<1],sumc[N<<1];
struct node{int x,y;}a[N<<1];
void solver()
{
for(int i=1; i<=n; i++)
b[i]=a[i].y,b[i+n]=a[i].y+col;
sort(b+1,b+1+2*n);
int nn=unique(b+1,b+1+2*n)-(b+1);
for(int i=1; i<=n; i++)
{
int x=lower_bound(b+1,b+1+nn,a[i].y)-b;
int y=lower_bound(b+1,b+1+nn,a[i].y+col)-b;
tr[x]++; tr[y]++;
rev[x]=a[i].y; rev[y]=a[i].y+col;
// cout<<x<<" "<<y<<endl;
}
ansr=cntr=1e9;
for(int i=1; i<=nn; i++)
sumr[i]=sumr[i-1]+tr[i];
for(int i=1; i<=nn; i++)
{
if(sumr[i]<n)
continue;
int j=upper_bound(sumr+1,sumr+1+nn,sumr[i]-n)-sumr;
// cout<<"kkk"<<rev[i]<<" "<<rev[j]<<endl;
if(rev[i]-rev[j]+1<ansr)
{
ansr=rev[i]-rev[j]+1;
if(rev[i]<=col || rev[j]>col)
cntr=0;
else
cntr=min(rev[i]-col,col-rev[j]+1);
// cout<<cntr<<endl;
}
else if(ansr==rev[i]-rev[j]+1)
{
if(rev[i]<=col || rev[j]>col)
cntr=0;
else
cntr=min(cntr,min(rev[i]-col,col-rev[j]+1));
}
}
}
void solvec()
{
for(int i=1; i<=n; i++)
b[i]=a[i].x,b[i+n]=a[i].x+row,rev[i]=rev[i+n]=0;
sort(b+1,b+1+2*n);
int nn=unique(b+1,b+1+2*n)-(b+1);
for(int i=1; i<=n; i++)
{
int x=lower_bound(b+1,b+1+nn,a[i].x)-b;
int y=lower_bound(b+1,b+1+nn,a[i].x+row)-b;
tc[x]++; tc[y]++;
rev[x]=a[i].x; rev[y]=a[i].x+row;
// cout<<x<<" "<<y<<endl;
}
ansc=cntc=1e9;
for(int i=1; i<=nn; i++)
sumc[i]=sumc[i-1]+tc[i];
for(int i=1; i<=nn; i++)
{
if(sumc[i]<n)
continue;
int j=upper_bound(sumc+1,sumc+1+nn,sumc[i]-n)-sumc;
// cout<<"kkk"<<rev[i]<<" "<<rev[j]<<endl;
if(rev[i]-rev[j]+1<ansc)
{
ansc=rev[i]-rev[j]+1;
if(rev[i]<=row || rev[j]>row)
cntc=0;
else
cntc=min(rev[i]-row,row-rev[j]+1);
}
else if(ansc==rev[i]-rev[j]+1)
{
if(rev[i]<=row || rev[j]>row)
cntc=0;
else
cntc=min(cntc,min(rev[i]-row,row-rev[j]+1));
}
}
}
bool Med;
int main()
{
freopen("watch.in","r",stdin);
freopen("watch.out","w",stdout);
// fprintf(stderr, "%.3lfMB",(&Med-&Mbe)/1048576.0);
scanf("%d%d%d",&row,&col,&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&a[i].x,&a[i].y);
solver();
solvec();
// cout<<ansr<<" "<<cntr<<endl;
LL ans=1LL*ansr*ansc;
printf("%lld %d",ans,cntr+cntc);
// cout<<"\n"<<cntr<<" "<<cntc<<endl;
return 0;
}
T2 会议
有 \(n\) 个活动，每个活动有开始时间 \(l_i\) 和结束时间 \(r_i\)。称一个活动集合为共享集合，如果集合中的任意两个活动都不重叠。假设会议的最大集合为 \(m\)
现在需要选择 \(n/2\) 个活动来进行，要求举行的活动的最大共享集合为 \(m/2\)，保证 \(n,m\) 为偶数，请给出一种方案
\(T\leq 5\times 10^4\)，\(n\leq 10^5\)，\(l_i,r_i\leq 10^9\)
构造题，一点不会好吧
首先初始的 \(m\) 可以通过排序右端点贪心地求出。问题是我们应该选择哪 \(m/2\) 个来作为最后的活动
一开始想隔着删，发现不行，然后打摆……
其实我们可以直接考虑要前 \(m/2\) 个或者后 \(m/2\) 个。考虑哪些非共享集合的活动也要选择。这里有个非常重要的思想：分类，剩下的 \(m-n\) 个活动，我们应该寻找一种分类方法，使得选择更加明晰
这里的方法是，我们将剩下的活动分为两类，一类是与前 \(m/2\) 个活动有交的活动，另一类是其它活动，分别记为集合 \(L,R\)，将共享集合里的活动也分别放进 \(L,R\) 里。这样分类有 \(|L|+|R|=n\)，所以必然有一个集合的大小大于等于 \(n/2\)，我们从中选择即可。将共享集合的选择了，剩下的随便选
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,in[N];
bool isans[N];
struct node{int l,r,id;}a[N];
vector <int> L,R,ans;
void init()
{
m=0;
memset(isans,0,sizeof(isans));
memset(in,0,sizeof(in));
L.clear(); R.clear(); ans.clear();
}
void mian()
{
init();
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
sort(a+1,a+1+n,[](const node &A,const node &B){return A.r<B.r;});
int lastR=0,mid=0;
for(int i=1; i<=n; i++)
{
if(a[i].l>lastR)
isans[i]=1,lastR=a[i].r,m++;
}
int cnt=0;
for(int i=1; i<=n; i++)
{
if(isans[i])
{
cnt++;
if(cnt==m/2)
{
mid=i; break;
}
}
}
// cout<<"kk"<<m<<endl;
for(int i=1; i<=n; i++)
{
if(a[i].l<=a[mid].r)
in[i]=0,L.push_back(i);
else
in[i]=1,R.push_back(i);
}
if(L.size()>=n/2)
{
cnt=0;
for(auto v:L)
{
if(isans[v])
ans.push_back(a[v].id),cnt++;
}
// cout<<cnt<<endl;
for(auto v:L)
{
if(cnt>=n/2)
break;
if(!isans[v])
ans.push_back(a[v].id),cnt++;
// cout<<cnt<<endl;
}
}
else
{
cnt=0;
for(auto v:R)
{
if(isans[v])
ans.push_back(a[v].id),cnt++;
}
for(auto v:R)
{
if(cnt>=n/2)
break;
if(!isans[v])
ans.push_back(a[v].id),cnt++;
}
}
// cout<<cnt<<endl;
for(auto v:ans)
printf("%d ",v);
puts("");
}
int main()
{
freopen("meet.in","r",stdin);
freopen("meet.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
mian();
return 0;
}