csp-s模拟测试99「淘淘摘苹果,开心的金明,笨小猴」
rtrt
3月 14, 2025
归档于 2019-11-05 15:04
淘淘摘苹果
题解
分块大法好!
每一个块内维护单调上升序列
然后块之间暴力lower_bound
复杂度$n*\sqrt n log(\sqrt n)$
代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define A 100005
ll t,n,m,t2;
ll bl[A],h[A],mx[410],sz[410];
ll st[410][410];//但是复杂度不对啊!
int main(){
freopen("TaoPApp.in","r",stdin);
freopen("TaoPApp.out","w",stdout);
scanf("%d%d",&n,&m);
t=sqrt(n);
for(ll i=1;i<=n;i++){
scanf("%d",&h[i]);
bl[i]=(i-1)/t+1;
t2=max(t2,bl[i]);
}
for(ll i=1;i<=n;i++){
ll belong=bl[i];
mx[belong]=max(mx[belong],h[i]);
if(!sz[belong]){
sz[belong]++;
st[belong][sz[belong]]=h[i];
continue ;
}
else if(h[i]>st[belong][sz[belong]]){
sz[belong]++;
st[belong][sz[belong]]=h[i];
}
}
for(ll i=1;i<=m;i++){
ll pla,hnow,lst;
scanf("%d%d",&pla,&hnow);
ll belong=bl[pla],maxnow=0,cnt=0;
lst=h[pla];h[pla]=hnow;
for(ll j=1;j<=t2;j++){
if(j==belong){
for(ll k=(j-1)*t+1;k<=min(j*t,n);k++){
if(h[k]>maxnow){
maxnow=h[k];
cnt++;
}
}
}
else {
if(mx[j]>maxnow){
cnt+=(sz[j]-(upper_bound(st[j]+1,st[j]+sz[j]+1,maxnow)-st[j])+1);
maxnow=mx[j];
}
}
}
h[pla]=lst;
printf("%d\n",cnt);
}
}
View Code
或者可以线段树
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 5555555
struct node{
ll l,r,max,val;
}tr[A];
ll a[A];
ll n,m,lst;
void built(ll x,ll l,ll r){
tr[x].l=l,tr[x].r=r;
if(l==r){
return ;
}
ll mid=(l+r)>>1;
built(x<<1,l,mid);
built(x<<1|1,mid+1,r);
}
ll ask(ll x,ll val){
if(tr[x].l==tr[x].r) return tr[x].max>val;
ll mid=(tr[x].l+tr[x].r)>>1;
if(tr[x<<1].max<=val) return ask(x<<1|1,val);
else return ask(x<<1,val)+tr[x].val-tr[x<<1].val;
}
void up(ll x){
tr[x].max=max(tr[x<<1].max,tr[x<<1|1].max);
tr[x].val=tr[x<<1].val+ask(x<<1|1,tr[x<<1].max);
}
void change(ll x,ll pla,ll val){
if(tr[x].l==tr[x].r){
tr[x].val=1;
tr[x].max=a[pla];
return ;
}
ll mid=(tr[x].l+tr[x].r)>>1;
if(mid>=pla) change(x<<1,pla,val);
else change(x<<1|1,pla,val);
up(x);
}
int main(){
freopen("TaoPApp.in","r",stdin);
freopen("TaoPApp.out","w",stdout);
scanf("%lld%lld",&n,&m);
built(1,1,n);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
change(1,i,a[i]);
}
for(ll i=1;i<=m;i++){
ll p,h;
scanf("%lld%lld",&p,&h);
lst=a[p];
a[p]=h;
change(1,p,a[p]);
printf("%lld\n",tr[1].val);
a[p]=lst;
change(1,p,a[p]);
}
}
View Code
然而分块比线段树快的多
开心的金明
题解
dp不可做就要往贪心\二分上想了
贪心考虑每原材料
val[1]=s1[1].c;
for(ll i=2;i<=k;i++){
val[i]=min(val[i-1]+s2[i-1].R,s1[i].c);
}
我们先把所有电脑生产出来,等卖出时再计算生产消耗,能生产就生产
贪心卖就是卖出生产代价最小的
证明:如果最后生产代价大生产代价小都卖出去了,那么和先卖生产代价小再卖生产代价大,情况一样
如果生产代价小没卖出去,而卖出生产代价大的肯定不优
于是拿个堆维护一下
这种费用滞后计算思想还是要见一见
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 111111
ll read(){
ll x;scanf("%lld",&x);return x;
}
ll tot,n,k,tot2,ans;
ll val[A];
struct node{
ll val,sum;
node(){}
node(const ll &a,const ll &b){val=a;sum=b;}
friend bool operator < (const node &a,const node &b){
return a.val<b.val;
}
}tmp[A],now[A];
struct some{
ll c;//原材料价格
ll d;//至少d个电脑
ll m;//生产电脑费用
ll p;//可以生产p台
ll e;//最多储存e台
ll R;//储存消耗R
ll E;//储存电脑消耗
}s1[A],s2[A];
int main(){
freopen("happy.in","r",stdin);
freopen("happy.out","w",stdout);
scanf("%lld",&k);
for(ll i=1;i<=k;i++){
scanf("%lld%lld%lld%lld",&s1[i].c,&s1[i].d,&s1[i].m,&s1[i].p);
}
for(ll i=1;i<=k-1;i++){
scanf("%lld%lld%lld",&s2[i].e,&s2[i].R,&s2[i].E);
}
val[1]=s1[1].c;
for(ll i=2;i<=k;i++){
val[i]=min(val[i-1]+s2[i-1].R,s1[i].c);
}
for(ll i=1;i<=k;i++){
for(ll j=1;j<=tot;j++)
tmp[j].val+=s2[i-1].E;
tmp[++tot]=node(val[i]+s1[i].m,s1[i].p);
// printf("s1.d=%lld\n",s1[i].d);
sort(tmp+1,tmp+tot+1);
ll ned=s1[i].d,cun=s2[i].e;
for(ll j=1;j<=tot;j++){
if(tmp[j].sum<=ned){
ans+=tmp[j].sum*tmp[j].val;
// printf("i=%lld val=%lld sum=%lld\n",i,tmp[j].val,tmp[j].sum);
ned-=tmp[j].sum;
tmp[j].sum=0;
}
else {
ans+=ned*tmp[j].val;
// printf("val=%lld ned=%lld\n",tmp[j].val,ned);
tmp[j].sum-=ned;
ned=0;
}
}
if(ned){
puts("-1");
return 0;
}
// printf("ans=%lld\n",ans);
tot2=0;
for(ll j=1;j<=tot;j++){
if(tmp[j].sum==0) continue ;
if(tmp[j].sum<=cun){
now[++tot2]=tmp[j];
cun-=tmp[j].sum;
}
else {
now[++tot2]=node(tmp[j].val,cun);
cun=0;
}
}
tot=tot2;
for(ll j=1;j<=tot;j++)
tmp[j]=now[j];
}
printf("%lld\n",ans);
}
View Code
笨小猴
题解
发现check是O1的(维护前缀和)然而可能初始给定序列根本组不成
然后可以每random_shuffle1次再check500000次
进行上述操作50次就AC了
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1111111
struct node{
ll a,b,id;
}c[A];
ll suma[A],sumb[A],sa,sb,n;
ll random(ll x){
return rand()%x;
}
int main(){
freopen("grandmaster.in","r",stdin);
freopen("grandmaster.out","w",stdout);
srand((unsigned)time(0));
scanf("%lld",&n);
for(ll i=1;i<=2*n+1;i++){
scanf("%lld%lld",&c[i].a,&c[i].b);
c[i].id=i;
sa+=c[i].a,sb+=c[i].b;
}
for(ll i=1;i*n<=1000000;i++){
random_shuffle(c+1,c+2*n+2);
for(ll j=1;j<=2*n+1;j++)
suma[j]=suma[j-1]+c[j].a,
sumb[j]=sumb[j-1]+c[j].b;
for(ll j=1;j<=n;j++){
ll l=random(n+1)+1;
if(suma[l+n]-suma[l-1]>sa-(suma[l+n]-suma[l-1]))
if(sumb[l+n]-sumb[l-1]>sb-(sumb[l+n]-sumb[l-1])){
for(ll k=l;k<=l+n;k++)
printf("%lld\n",c[k].id);
return 0;
}
}
if(clock()>990000){
printf("-1\n");
return 0;
}
}
}
View Code