标签：

[AHOI2014/JSOI2014]宅男打算

标题问题链接

可以发明买来食物可以维持的天数关于叫外卖的次数是一个单峰函数，这个可以打表或是另写一个措施判断。所以使用三分法寻找峰值。按照三分出来的次数计算天数可以使用贪心计谋，如果在保质期内就买最自制的食品，一些细节也需要特判。

#include <cstdio> #include <algorithm> typedef long long ll; inline ll rd(){ ll x=0,p=1; char a=getchar(); while((a<48||a>57)&&a!='-')a=getchar(); if(a=='-')p=-p,a=getchar(); while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar(); return x*p; } inline ll min(ll x,ll y){return x<y?x:y;} const int N=202; int n,top; ll m,f,ans; struct node{ ll p,s; bool operator < (const node &y)const{ return s<y.s; } }a[N],b[N]; inline ll calc(ll t){ ll res=m-f*t,now=0,x,ans=0; if(res<0)return 0; for(int i=1;i<=n;i++){ x=min(b[i].s-now,res/(b[i].p*t)); now+=x,ans+=x*t,res-=t*x*b[i].p; if(now<b[i].s){ ans+=res/b[i].p; break; } } return ans; } int main(){ m=rd(),f=rd(),n=rd(); for(int i=1;i<=n;i++)a[i].p=rd(),a[i].s=rd()+1; std::sort(a+1,a+n+1); for(int i=1;i<=n;i++){ while(top&&a[i].p<=b[top].p)top--; b[++top]=a[i]; } n=top; ll l=1,r=m/(f+b[1].p); while(l<=r){ ll lmid=l+(r-l)/3,rmid=r-(r-l)/3; ll lx=calc(lmid),rx=calc(rmid); if(lx<rx)ans=rx,l=lmid+1; else ans=lx,r=rmid-1; } printf("%lld\n",ans); return 0; } [AHOI2014/JSOI2014]骑士游戏

标题问题链接

有两种要领彻底杀死一个怪兽，即直接用术数打击，或者用普通打击，并杀死它死后孕育产生的所有怪兽。设 \(f_i\) 为杀死一个怪兽的最小体力，\(D_i\) 为使用普通打击后孕育产生怪兽的调集，则：

\[f_i=\min\{s_i,k_i+\sum\limits_{j\in D_i}f_j\}\]

但是直接 \(dp\) 显然是不行的，因为标题问题所给的关系是可能存在环的。所以我们借助 \(SPFA\) 的废弛的形式，从 \(i\) 向 \(j\in D_i\) 连边去跑 \(SPFA\)，使得一个点可以反复进入行列队伍，从而可以得到最优解。

转移的话可以建反边便利计算。

#include <cstdio> #include <queue> typedef long long ll; inline ll rd(){ ll x=0,p=1; char a=getchar(); while((a<48||a>57)&&a!='-')a=getchar(); if(a=='-')p=-p,a=getchar(); while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar(); return x*p; } const int N=1000002; int n; ll a[N],dis[N]; struct Edge{ int to,next; }edge[N],redge[N]; int head[N],cnt,rhead[N],rcnt; inline void add(int f,int t){ edge[++cnt].next=head[f]; edge[cnt].to=t; head[f]=cnt; } inline void radd(int f,int t){ redge[++rcnt].next=rhead[f]; redge[cnt].to=t; rhead[f]=rcnt; } int vis[N]; inline void spfa(){ std::queue<int> q; for(int i=1;i<=n;i++) q.push(i),vis[i]=1; while(!q.empty()){ int u=q.front();q.pop(),vis[u]=0; ll tmp=a[u]; for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to; tmp+=dis[v]; } if(tmp<dis[u]){ dis[u]=tmp; for(int i=rhead[u];i;i=redge[i].next){ int v=redge[i].to; if(!vis[v])vis[v]=1,q.push(v); } } } } int main(){ n=rd(); for(int i=1;i<=n;i++){ a[i]=rd(),dis[i]=rd();int k=rd(),x; while(k--){ x=rd(),add(i,x),radd(x,i); } } spfa(); printf("%lld\n",dis[1]); return 0; } [AHOI2014/JSOI2014]奇怪的计算器

标题问题链接

显然是把所有数读入后对整个序列进行操纵后一起输出。本题涉及 \(5\) 种操纵：区间加（减法被包孕在内），区间乘，区间加 \(a_i*X\)，区间对 \(L\) 取 \(\min\) 和区间对 \(R\) 取 \(\max\)。后两种操纵可以转化为将原序列排序，易知序列的单调性是不乱的，用线段树维护最大最小值，，在应该措置惩罚惩罚的时候进行区间赋值。

固然可以对付每一个操纵维护懒符号在线段树上直接搞。但还是有越发简便的一种措置惩罚惩罚方法：界说一种操纵为 \(f(k1,k2,k3)\)，需要更新数值时把线段树上的数值 \(val_i\) 酿成 \(val_i*k1+a_i*k2+k3\)，就可以用它撑持所有的操纵了。

区间加 \(c\) : \(f(1,0,c)\)

区间乘 \(c\) : \(f(c,0,0)\)

区间加 \(a_i*c\) : \(f(1,c,0)\)

区间赋值为 \(c\) : \(f(0,0,c)\)

于是维护 \(3\) 个符号，统一下传。

#include <cstdio> #include <algorithm> #define int ll typedef long long ll; inline int rd(){ int x=0,p=1; char a=getchar(); while((a<48||a>57)&&a!='-')a=getchar(); if(a=='-')p=-p,a=getchar(); while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar(); return x*p; } const int N=100002; int q,n,L,R; int op[N],x[N]; struct node{ int val,id; bool operator < (const node &y)const{ return val<y.val; } }a[N]; ll tmax[N<<2],tmin[N<<2]; ll k1[N<<2],k2[N<<2],k3[N<<2]; int ans[N]; inline void pushup(int rt){ tmin[rt]=tmin[rt<<1]; tmax[rt]=tmax[rt<<1|1]; } inline void pushtag(int l,int r,int rt,int x,int y,int z){//tree[rt]=tree[rt]*k1+val*k2+k3; k1[rt]*=x,k2[rt]=k2[rt]*x+y,k3[rt]=k3[rt]*x+z; tmin[rt]=tmin[rt]*x+a[l].val*y+z; tmax[rt]=tmax[rt]*x+a[r].val*y+z; } inline void pushdown(int rt,int l,int r){ int mid=(l+r)>>1; pushtag(l,mid,rt<<1,k1[rt],k2[rt],k3[rt]); pushtag(mid+1,r,rt<<1|1,k1[rt],k2[rt],k3[rt]); k1[rt]=1,k2[rt]=k3[rt]=0; } inline void build(int l,int r,int rt){ k1[rt]=1,k2[rt]=k3[rt]=0; if(l==r){ tmin[rt]=tmax[rt]=a[l].val; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } inline void update(int l,int r,int rt,int op){ if(l==r){ if(!op)pushtag(l,r,rt,0,0,L); else pushtag(l,r,rt,0,0,R); return; } int mid=(l+r)>>1; pushdown(rt,l,r); if(!op){ if(tmin[rt<<1|1]<L)pushtag(l,mid,rt<<1,0,0,L),update(mid+1,r,rt<<1|1,op); else update(l,mid,rt<<1,op); } else{ if(tmax[rt<<1]>R)pushtag(mid+1,r,rt<<1|1,0,0,R),update(l,mid,rt<<1,op); else update(mid+1,r,rt<<1|1,op); } pushup(rt); } inline void dfs(int l,int r,int rt){ if(l==r){ ans[a[l].id]=tmin[rt]; return; } int mid=(l+r)>>1; pushdown(rt,l,r); dfs(l,mid,rt<<1); dfs(mid+1,r,rt<<1|1); pushup(rt); } signed main(){ q=rd(),L=rd(),R=rd(); for(int i=1;i<=q;i++){ char s[3];scanf("%s",s); if(s[0]=='+')op[i]=1; else if(s[0]=='-')op[i]=2; else if(s[0]=='*')op[i]=3; else op[i]=4; x[i]=rd(); } n=rd(); for(int i=1;i<=n;i++)a[i].val=rd(),a[i].id=i; std::sort(a+1,a+n+1); build(1,n,1); for(int i=1;i<=q;i++){ if(op[i]==1)pushtag(1,n,1,1,0,x[i]); else if(op[i]==2)pushtag(1,n,1,1,0,-x[i]); else if(op[i]==3)pushtag(1,n,1,x[i],0,0); else pushtag(1,n,1,1,x[i],0); if(tmin[1]<L)update(1,n,1,0); if(tmax[1]>R)update(1,n,1,1); } dfs(1,n,1); for(int i=1;i<=n;i++)printf("%lld\n",ans[i]); return 0; } [JSOI2014]支线剧情2

标题问题链接