A.P2587 [ZJOI2008]泡泡堂
- 好家伙，久违的贪心
所以说挂了；
Solution
-
但实际上这道题和田忌赛马有所区别，已知有一种比较优的方法是用己方最鶸的换掉敌方最强的，那么为了得分最大，就有如下策略：
- 当己方最强比敌方最强强时，得 \(2\) 分；
- 否则，如果己方最弱比敌方最弱强，得 \(2\) 分；
- 否则，用己方最弱换掉敌方最强。如果刚好平局，按平局计算；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
int n;
int a[N],b[N];
int count(int x[],int y[]){
int ans=0;
int lx=1,ly=1,rx=n,ry=n;
while(lx<=rx && ly<=ry){
if(x[lx]>y[ly]){
ans+=2;
++lx,++ly;
}
else if(x[rx]>y[ry]){
ans+=2;
--rx,--ry;
}
else{
ans+=(x[lx]==y[ry]);
++lx;
--ry;
}
}
return ans;
}
int main(){
// freopen("bubble.in","r",stdin);
// freopen("bubble.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
b[i]=read();
sort(a+1,a+n+1);
sort(b+1,b+n+1);
printf("%d %d",count(a,b),(n<<1)-count(b,a));
return 0;
}
D.P4344 [SHOI2015]脑洞治疗仪
-
为什么这人的脑洞越治越大，这真的不是脑洞制造仪吗 -
线段树，但考试时不知道为什么挂了；
Solution
- 线段树，具体存储方法类比用线段树求一个序列答案；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=2e5+10;
const int Inf=0x3f3f3f3f;
int n,m;
struct memr{
int l,r,siz;
int sum,tg;
int mx,lmx,rmx;
}tr[N<<4];
void pushup(int p){
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
tr[p].mx=max(tr[p].mx,tr[p<<1].rmx+tr[p<<1|1].lmx);
tr[p].lmx=tr[p<<1].lmx;
tr[p].rmx=tr[p<<1|1].rmx;
if(tr[p<<1].mx==tr[p<<1].siz)
tr[p].lmx=max(tr[p].lmx,tr[p<<1].siz+tr[p<<1|1].lmx);
if(tr[p<<1|1].mx==tr[p<<1|1].siz)
tr[p].rmx=max(tr[p].rmx,tr[p<<1|1].siz+tr[p<<1].rmx);
return ;
}
void push(int p,int tg){
if(tg==1){
tr[p].sum=tr[p].siz;
tr[p].lmx=tr[p].mx=tr[p].rmx=0;
}
else if(tg==-1){
tr[p].sum=0;
tr[p].lmx=tr[p].mx=tr[p].rmx=tr[p].siz;
}
return ;
}
void pushdown(int p){
if(tr[p].tg){
push(p<<1,tr[p].tg);
push(p<<1|1,tr[p].tg);
tr[p<<1].tg=tr[p].tg;
tr[p<<1|1].tg=tr[p].tg;
tr[p].tg=0;
}
return ;
}
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
tr[p].siz=r-l+1;
tr[p].tg=0;
tr[p].lmx=tr[p].mx=tr[p].rmx=0;
if(l==r){
tr[p].sum=1;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void change(int p,int l,int r,int v){
if(l<=tr[p].l && tr[p].r<=r){
push(p,v);
tr[p].tg=v;
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) change(p<<1,l,r,v);
if(mid<r) change(p<<1|1,l,r,v);
pushup(p);
return ;
}
memr ask_hole(int p,int l,int r){
if(l<=tr[p].l && tr[p].r<=r)
return tr[p];
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
memr L,R,cnt;
bool sl=0,sr=0;
if(l<=mid)
L=ask_hole(p<<1,l,r),sl=1;
if(mid<r)
R=ask_hole(p<<1|1,l,r),sr=1;
pushup(p);
if(sl && !sr)
return L;
if(!sl && sr)
return R;
if(sl && sr){
cnt.sum=L.sum+R.sum;
cnt.siz=L.siz+R.siz;
cnt.mx=max(L.rmx+R.lmx,max(L.mx,R.mx));
cnt.lmx=L.lmx,cnt.rmx=R.rmx;
if(L.mx==L.siz)
cnt.lmx=max(cnt.lmx,L.mx+R.lmx);
if(R.mx==R.siz)
cnt.rmx=max(cnt.rmx,R.mx+L.rmx);
}
return cnt;
}
int ask_num(int p,int l,int r){
if(l<=tr[p].l && tr[p].r<=r)
return tr[p].sum;
pushdown(p);
int cnt=0;
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) cnt+=ask_num(p<<1,l,r);
if(mid<r) cnt+=ask_num(p<<1|1,l,r);
pushup(p);
return cnt;
}
int Fill(int p,int l,int r,int x){
if(!x) return 0;
if(l<=tr[p].l && tr[p].r<=r && tr[p].siz-tr[p].sum<=x){
int s=tr[p].siz-tr[p].sum;
push(p,1);
tr[p].tg=1;
return x-s;
}
pushdown(p);
int cnt;
if(tr[p<<1].r<l) cnt=Fill(p<<1|1,l,r,x);
else if(tr[p<<1|1].l>r) cnt=Fill(p<<1,l,r,x);
else cnt=Fill(p<<1|1,l,r,Fill(p<<1,l,r,x));
pushup(p);
return cnt;
}
int main(){
// freopen("head.in","r",stdin);
// freopen("head.out","w",stdout);
n=read(),m=read();
build(1,1,n+1);
int opt,l,r,x,y;
while(m--){
opt=read(),l=read(),r=read();
if(opt==1){
x=read(),y=read();
int len=ask_num(1,l,r);
if(!len) continue;
change(1,l,r,-1);
Fill(1,l,r,len);
}
else{
if(opt==0)
change(1,l,r,-1);
else{
memr ans=ask_hole(1,l,r);
printf("%d\n",ans.mx);
}
}
}
return 0;
}