「雅礼集训 2017 Day1」市场
挺神仙的一题。涉及区间加、区间除、区间最小值和区间和。虽然标算就是暴力，但是复杂度是有保证的。
我们知道如果线段树上的一个结点，\(max=min\) 或者 \(max=min+1\) 并且 \(d|max\)，是可以直接剪掉的。
我们定义线段树上一个结点的势能为 \(\log(max-min)\)，那么我们每执行一次区间除，都会引起势能的减小。
但是执行区间加时我们涉及 \(\log n\) 个结点，最差情况下会将它们的势能恢复为 \(\log(max-min)\)
所以总时间复杂度就是势能总和，不难分析为 \(O(n\log d+q\log n\log d)\)
类似的，我们可以分析区间开根区间加的时间复杂度，在此就不赘述了。
\(Code\ Below:\)
#include#include #define int long long#define lson (rt<<1)#define rson (rt<<1|1)using namespace std;const int maxn=100000+10;const int inf=1e18;int n,m,a[maxn],sum[maxn<<2],Max[maxn<<2],Min[maxn<<2],add[maxn<<2];inline int read(){ register int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return (f==1)?x:-x;}inline void pushup(int rt){ sum[rt]=sum[lson]+sum[rson]; Max[rt]=max(Max[lson],Max[rson]); Min[rt]=min(Min[lson],Min[rson]);}inline void pushtag(int rt,int C,int len){ sum[rt]+=C*len; Max[rt]+=C;Min[rt]+=C;add[rt]+=C;}inline void pushdown(int rt,int len){ if(add[rt]){ pushtag(lson,add[rt],len-(len>>1)); pushtag(rson,add[rt],len>>1); add[rt]=0; }}void build(int l,int r,int rt){ if(l == r){ sum[rt]=Max[rt]=Min[rt]=a[l]; return ; } int mid=(l+r)>>1; build(l,mid,lson); build(mid+1,r,rson); pushup(rt);}void update_plu(int L,int R,int C,int l,int r,int rt){ if(L <= l && r <= R){ sum[rt]+=(r-l+1)*C; Max[rt]+=C;Min[rt]+=C;add[rt]+=C; return ; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(L <= mid) update_plu(L,R,C,l,mid,lson); if(R > mid) update_plu(L,R,C,mid+1,r,rson); pushup(rt);}void update_div(int L,int R,int C,int l,int r,int rt){ if(L <= l && r <= R){ int A,B; if(Max[rt]<0) A=(Max[rt]-C+1)/C; else A=Max[rt]/C; if(Min[rt]<0) B=(Min[rt]-C+1)/C; else B=Min[rt]/C; if(Max[rt]-A==Min[rt]-B){ pushtag(rt,A-Max[rt],r-l+1); return ; } } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(L <= mid) update_div(L,R,C,l,mid,lson); if(R > mid) update_div(L,R,C,mid+1,r,rson); pushup(rt);}int query_min(int L,int R,int l,int r,int rt){ if(L <= l && r <= R){ return Min[rt]; } pushdown(rt,r-l+1); int mid=(l+r)>>1,ans=inf; if(L <= mid) ans=min(ans,query_min(L,R,l,mid,lson)); if(R > mid) ans=min(ans,query_min(L,R,mid+1,r,rson)); return ans;}int query_sum(int L,int R,int l,int r,int rt){ if(L <= l && r <= R){ return sum[rt]; } pushdown(rt,r-l+1); int mid=(l+r)>>1,ans=0; if(L <= mid) ans+=query_sum(L,R,l,mid,lson); if(R > mid) ans+=query_sum(L,R,mid+1,r,rson); return ans;}signed main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,n,1); int op,l,r,k; for(int i=1;i<=m;i++){ op=read(),l=read(),r=read();l++;r++; if(op==1) k=read(),update_plu(l,r,k,1,n,1); if(op==2) k=read(),update_div(l,r,k,1,n,1); if(op==3) printf("%lld\n",query_min(l,r,1,n,1)); if(op==4) printf("%lld\n",query_sum(l,r,1,n,1)); } return 0;}
「雅礼集训 2017 Day1」矩阵
构造题。
发现无解的情况就是全空的情况，特判掉即可。
现在考虑怎么算出最少步数。
发现只要第 \(i\) 行有黑色，那么第 \(i\) 列会在 \(tot_{white}\) 步变成全黑，所以我们来构造一行全黑的，然后将整个棋盘染成黑色。
那么每行取个最小值即可，累加一下。
\(Code\ Below:\)
#includeusing namespace std;const int maxn=1000+10;int n,m,h[maxn],l[maxn],ans,sum;char s[maxn][maxn];int main(){ scanf("%d%d",&n,&m); int flag=0; for(int i=1;i<=n;i++){ scanf("%s",s[i]+1); for(int j=1;j<=n;j++) if(s[i][j]=='#'){ flag=1; h[i]++;l[j]++; } } if(!flag){ printf("-1\n"); return 0; } ans=n; for(int i=1;i<=n;i++) ans=min(ans,n-h[i]+!l[i]); for(int i=1;i<=n;i++) sum+=l[i]!=n; printf("%d\n",ans+sum); return 0;}