专业网站制作软件,德阳建设公司网站,宁波网站建设与维护,网络规划设计师报名入口一套题 养花 题解 分块\主席树 这里我用的是主席树 查询分段$1-(k-1)$找最大的,能向右找就向右找 for(ll nowl1,nowrk-1;nowlmaxx;nowlk,nowrk,nowrmin(nowr,maxx)){if(ansmod-1) break;chose(rt[r],rt[l-1],nowl,nowr,1,maxx);} 复杂度分析,调和级数$√n*log(n)$ 代码 #in… 一套题 养花 题解 分块\主席树 这里我用的是主席树 查询分段$1-(k-1)$找最大的,能向右找就向右找 for(ll nowl1,nowrk-1;nowlmaxx;nowlk,nowrk,nowrmin(nowr,maxx)){if(ansmod-1) break;chose(rt[r],rt[l-1],nowl,nowr,1,maxx);} 复杂度分析,调和级数$√n*log(n)$ 代码 #includebits/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) ptot;if(lr) {tr[p].sztr[v].sz1;return ;}ll mid(lr)1;ll optnummid,L,R;if(opt) Lmid1,Rr;else Ll,Rmid;tr[p].son[opt^1]tr[v].son[opt^1];insert(tr[p].son[opt],tr[v].son[opt],num,L,R);tr[p].sztr[ls(p)].sztr[rs(p)].sz;
}
void find(ll p,ll v,ll l,ll r){if(r%modans) return ;
// printf(l%d r%d\n,l,r);if(lr){ansmax(ans,l%mod);return ;}ll mid(lr)1;if(tr[rs(p)].sz-tr[rs(v)].sz) find(rs(p),rs(v),mid1,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].sz0)return ;if(lqlrqr){find(p,v,l,r);return ;}ll mid(lr)1;if(midql) chose(ls(p),ls(v),ql,qr,l,mid);if(midqr) chose(rs(p),rs(v),ql,qr,mid1,r);
}
int main(){scanf(%d%d,n,m);for(ll i1;in;i){scanf(%d,a[i]);maxxmax(a[i],maxx);}for(ll i1;in;i){insert(rt[i],rt[i-1],a[i],1,maxx);}for(ll i1,l,r,k;im;i){scanf(%d%d%d,l,r,k);ans0;modk;for(ll nowl1,nowrk-1;nowlmaxx;nowlk,nowrk,nowrmin(nowr,maxx)){if(ansmod-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.yi.y$ $f[j][1]f[i][0]$ $j.yi.y$ $f[i][0]f[j][1]$ 你会发现这样转移会有不和法的 不要容斥,更改枚举顺序从大到小枚举 设最上点$x$,中间点为$y$,下面点为$z$ 假设这次$y$贡献要加$1$,$x$加上$f[y]$如果是逆序就没加上当前贡献 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 6100
const ll mod1e97;
ll f[A][2];
ll n,ans;
struct node{ll x,y;friend bool operator (const node a,const node b){return a.xb.x;}
}poi[A];
int main(){scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,poi[i].x,poi[i].y);}sort(poi1,poin1);for(ll i1;in;i){f[i][0]f[i][1]1;for(ll ji-1;j1;j--){if(poi[j].ypoi[i].y)(f[j][1]f[i][0])%mod;else (f[i][0]f[j][1])%mod;}}for(ll i1;in;i){(ansf[i][0]f[i][1])%mod;}ans-n;printf(%lld\n,ans);
} View Code 画作(同bzoj2638) 题解 轮流染色 将同色方块缩点建图 枚举每个点为根求bfs树 按深度从深至浅顺序染色 树的深度-(最深叶节点为白色?1:0)为以这个点为中心染色的最少操作次数 代码 #includebits/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,mx0,ans0x7fffffffff;
dequell 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(x1xny1ym) 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 i1;i4;i){ll xnownowx[i]x,ynownowy[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 i1;in;i){scanf(%s,c[i]1);}for(ll i1;in;i){for(ll j1;jm;j){if(!id[i][j]){col[ide]c[i][j]-0;dfs(i,j,c[i][j]-0);}}}
/* for(ll i1;in;i,puts()){for(ll j1;jm;j){printf(%lld,id[i][j]);}}
*/ for(ll i1;in;i)for(ll j1;jm;j)if(id[i][j]!id[i][j1]) add(id[i][j],id[i][j1]),add(id[i][j1],id[i][j]);for(ll i1;in;i)for(ll j1;jm;j)if(id[i][j]!id[i1][j])add(id[i][j],id[i1][j]),add(id[i1][j],id[i][j]);for(ll i1;iide;i){for(ll j1;jide;j) dis[j]0x7ffffffff;q.clear();mx0;q.push_back(i);dis[i]0;while(!q.empty()){ll xq.front();q.pop_front();
// printf(x%lld col%lld\n,x,col[i]);if(dis[x]mx) mxdis[x];for(ll khead[x];k;knxt[k]){ll yver[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!(mx1)) mx;if(col[i]0(mx1)) mx;if(mxans) ansmx;}printf(%lld\n,ans);
} View Code 蔬菜 裸二维莫队 施工 题解 模拟\dp 这个dp真是神仙 联盟 题解 首先题目要求得就是 转载于:https://www.cnblogs.com/znsbc-13/p/11579647.html
