一套题
养花
题解
分块\主席树
这里我用的是主席树
查询分段$1-(k-1)$找最大的,能向右找就向右找
for(ll nowl=1,nowr=k-1;nowl<=maxx;nowl+=k,nowr+=k,nowr=min(nowr,maxx)) { if(ans==mod-1) break; chose(rt[r],rt[l-1],nowl,nowr,1,maxx); }
复杂度分析,调和级数$√n*log(n)$
代码
#include<bits/stdc++.h> using namespace std; #define ll int #define rs(x) tr[x].son[1] #define ls(x) tr[x].son[0] #define A 10000000 struct tree{ ll son[2],sz; }tr[A]; ll tot,n,m,ans,maxx,mod; ll a[500000],rt[500000]; void insert(ll &p,ll v,ll num,ll l,ll r){ if(!p) p=++tot; if(l==r) { tr[p].sz=tr[v].sz+1; return ; } ll mid=(l+r)>>1; ll opt=num>mid,L,R; if(opt) L=mid+1,R=r; else L=l,R=mid; tr[p].son[opt^1]=tr[v].son[opt^1]; insert(tr[p].son[opt],tr[v].son[opt],num,L,R); tr[p].sz=tr[ls(p)].sz+tr[rs(p)].sz; } void find(ll p,ll v,ll l,ll r){ if(r%mod<ans) return ; // printf("l=%d r=%d\n",l,r); if(l==r){ ans=max(ans,l%mod); return ; } ll mid=(l+r)>>1; if(tr[rs(p)].sz-tr[rs(v)].sz) find(rs(p),rs(v),mid+1,r); else if(tr[ls(p)].sz-tr[ls(v)].sz)find(ls(p),ls(v),l,mid); } void chose(ll p,ll v,ll ql,ll qr,ll l,ll r){ if(tr[p].sz-tr[v].sz==0)return ; if(l>=ql&&r<=qr){ find(p,v,l,r); return ; } ll mid=(l+r)>>1; if(mid>=ql) chose(ls(p),ls(v),ql,qr,l,mid); if(mid<qr) chose(rs(p),rs(v),ql,qr,mid+1,r); } int main(){ scanf("%d%d",&n,&m); for(ll i=1;i<=n;i++){ scanf("%d",&a[i]); maxx=max(a[i],maxx); } for(ll i=1;i<=n;i++){ insert(rt[i],rt[i-1],a[i],1,maxx); } for(ll i=1,l,r,k;i<=m;i++){ scanf("%d%d%d",&l,&r,&k); ans=0; mod=k; for(ll nowl=1,nowr=k-1;nowl<=maxx;nowl+=k,nowr+=k,nowr=min(nowr,maxx)) { if(ans==mod-1) break; chose(rt[r],rt[l-1],nowl,nowr,1,maxx); } printf("%d\n",ans); } }View Code
折射
题解
$n^2,dp$
$f[i][0/1]$表示向左延伸的光线,向右延伸的光线
按照$x$排序,然后考虑转移
枚举比当前点小的点$j$
若$j.y>i.y$
$f[j][1]+=f[i][0]$
$j.y<i.y$
$f[i][0]+=f[j][1]$
你会发现这样转移会有不和法的
不要容斥,更改枚举顺序从大到小枚举
设最上点$x$,中间点为$y$,下面点为$z$
假设这次$y$贡献要加$1$,$x$加上$f[y]$如果是逆序就没加上当前贡献
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 6100 const ll mod=1e9+7; ll f[A][2]; ll n,ans; struct node{ ll x,y; friend bool operator < (const node &a,const node &b){ return a.x<b.x; } }poi[A]; int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld",&poi[i].x,&poi[i].y); } sort(poi+1,poi+n+1); for(ll i=1;i<=n;i++){ f[i][0]=f[i][1]=1; for(ll j=i-1;j>=1;j--){ if(poi[j].y>poi[i].y) (f[j][1]+=f[i][0])%=mod; else (f[i][0]+=f[j][1])%=mod; } } for(ll i=1;i<=n;i++){ (ans+=f[i][0]+f[i][1])%=mod; } ans-=n; printf("%lld\n",ans); }View Code
画作(同bzoj2638)
题解
轮流染色
将同色方块缩点建图 枚举每个点为根求bfs树 按深度从深至浅顺序染色 树的深度-(最深叶节点为白色?1:0)为以这个点为中心染色的最少操作次数代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 55 char c[A][A]; ll dis[A*10000],head[A*10000],nxt[A*10000],ver[A*10000],col[A*10000],id[A][A]; ll n,m,tot,ide,mx=0,ans=0x7fffffffff; deque<ll >q; void add(ll x,ll y){ // printf("x=%lld y=%lld\n",x,y); nxt[++tot]=head[x],head[x]=tot,ver[tot]=y; } ll ok(ll x,ll y){ if(x>=1&&x<=n&&y>=1&&y<=m) return 1; return 0; } const ll nowx[5]={0,1,0,0,-1}; const ll nowy[5]={0,0,1,-1,0}; void dfs(ll x,ll y,ll now){ // printf("x=%lld y=%lld now=%lld c[x][y]-'0'=%lld ide=%lld\n",x,y,now,1ll*(c[x][y]-'0'),ide); if(id[x][y]||c[x][y]-'0'!=now) return ; id[x][y]=ide; // printf("n=%lld m=%lld\n",n,m); for(ll i=1;i<=4;i++){ ll xnow=nowx[i]+x,ynow=nowy[i]+y; // printf("x=%lld y=%lld xnow=%lld ynow=%lld\n",x,y,xnow,ynow); if(ok(xnow,ynow)) dfs(xnow,ynow,now); } } int main(){ scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++){ scanf("%s",c[i]+1); } for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ if(!id[i][j]){ col[++ide]=c[i][j]-'0'; dfs(i,j,c[i][j]-'0'); } } } /* for(ll i=1;i<=n;i++,puts("")){ for(ll j=1;j<=m;j++){ printf("%lld",id[i][j]); } } */ for(ll i=1;i<=n;i++) for(ll j=1;j<m;j++) if(id[i][j]!=id[i][j+1]) add(id[i][j],id[i][j+1]),add(id[i][j+1],id[i][j]); for(ll i=1;i<n;i++) for(ll j=1;j<=m;j++) if(id[i][j]!=id[i+1][j]) add(id[i][j],id[i+1][j]),add(id[i+1][j],id[i][j]); for(ll i=1;i<=ide;i++){ for(ll j=1;j<=ide;j++) dis[j]=0x7ffffffff; q.clear();mx=0; q.push_back(i); dis[i]=0; while(!q.empty()){ ll x=q.front(); q.pop_front(); // printf("x=%lld col=%lld\n",x,col[i]); if(dis[x]>mx) mx=dis[x]; for(ll k=head[x];k;k=nxt[k]){ ll y=ver[k]; // printf("x=%lld y=%lld col=%lld dis[x]=%lld dis[y]=%lld mx=%lld\n",x,y,col[i],dis[x],dis[y],mx); if(dis[y]>dis[x]+1){ dis[y]=dis[x]+1; q.push_back(y); } } } if(col[i]==1&&!(mx&1)) mx++; if(col[i]==0&&(mx&1)) mx++; if(mx<ans) ans=mx; } printf("%lld\n",ans); }View Code
蔬菜
裸二维莫队