陕西省建设厅三类人员报名网站,哪些软件可以做网页,外包软件公司,张家港手机网站202303-1 田地丈量#xff08;矩阵面积交#xff09;
矩阵面积交x轴线段交长度*y轴线段交长度
线段交长度#xff0c;相交的时候是min右端点-max左端点#xff0c;不相交的时候是0
#includebits/stdc.h
using namespace std;
int n,a,b,ans,x,y,x2,y2;
int f(in…202303-1 田地丈量矩阵面积交
矩阵面积交x轴线段交长度*y轴线段交长度
线段交长度相交的时候是min右端点-max左端点不相交的时候是0
#includebits/stdc.h
using namespace std;
int n,a,b,ans,x,y,x2,y2;
int f(int l1,int r1,int l,int r){return max(0,min(r1,r)-max(l1,l));
}
int main(){cinnab;for(int i1;in;i){cinxyx2y2;ansf(0,a,x,x2)*f(0,b,y,y2);}coutansendl;return 0;
}
202303-2 垦田计划二分
二分最终答案xxk判断降到x天资源是否够
够的话就往小里二分否则往大里二分
当然贪心也可以做排序之后把最耗时的天数逐个压低使得后缀和前面持平
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1e510;
int n,m,k,t[N],c[N],mx;
bool ok(int x){ll sum0;for(int i1;in;i){if(t[i]x)continue;sum1ll*(t[i]-x)*c[i];if(summ)return 0;}return 1;
}
int main(){cinnmk;for(int i1;in;i){cint[i]c[i];mxmax(mx,t[i]);}int lk,rmx;while(lr){int mid(lr)/2;if(ok(mid))rmid-1;else lmid1;}coutlendl;return 0;
}
202303-3 LDAP模拟栈bitset
主要是要解决表达式嵌套的问题
与栈实现计算器时维护一个符号栈、一个数值栈类似
这里维护了两个栈一个符号栈op一个bitset集合栈stk集合求交、或由bitset完成
当遇到或|时将符号压栈当遇到)时将bitset压栈()内正常读取求bitset即可
当同一个符号对应两个bitset在栈内num[c]2时将两个bitset运算为一个bitset
其余部分map乱搞q[i][j]表示DNi用户的j属性值
p(i,j)表示i属性值为j的有哪些用户has[i]表示i属性有哪些用户
i:j操作时p[i][j]即为所求i~j操作时has[i]内去掉p[i][j]即为所求
to[i]记录了第i个用户对应的DN值输出时按DN从小到大排序即可
实际耗时3s多12s绰绰有余
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef pairint,int P;
const int N2502;
int n,m,sz,id,k,c,d,x,y,num[N],to[N],f[N];
mapint,intq[N];
mapP,vectorintp;
mapint,vectorinthas;
char s[N],op[N];
bitsetNstk[N*2],res;
bitsetNcal(int l,char x,int r){bitsetNans;for(auto v:p[P(l,r)]){ans.set(v);}if(x~){for(auto v:has[l]){ans.flip(v);}}return ans;
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d%d,id,k);to[i]id;for(int j1;jk;j){scanf(%d%d,x,y);q[i][x]y;has[x].push_back(i);p[P(x,y)].push_back(i);}}scanf(%d,m);for(int i1;im;i){scanf(%s,s);szstrlen(s);cd0;for(int j0;jsz;){if(s[j] || s[j]|){op[c]s[j];}else if(s[j](){j;}else if(s[j])){num[c];if(num[c]2){d--;if(op[c])stk[d]stk[d]stk[d1];else stk[d]stk[d]|stk[d1];num[c--]0;}j;}else{int curj,l0,r0;while(cursz (s[cur]!: s[cur]!~)){ll*10(s[cur]-0);cur;}char xs[cur];while(cursz s[cur]!)){rr*10(s[cur]-0);cur;}stk[d]cal(l,x,r);jcur;}}int e0;for(int j1;jn;j){if(stk[d].test(j)){f[e]to[j];}}sort(f1,fe1);for(int j1;je;j){printf(%d%c,f[j], \n[je]);}if(!e)puts();}return 0;
}
202303-4 星际网络II线段树
线段树离散化、单点询问、区间求和、区间最值经典题了
线段树维护区间和用于记录对应区间几个值被用过
线段树维护最大最小值用于记录被哪个用户id用过
当最小值最大值时表示恰被一个用户用过 首先将最大32维的数转10进制压成长为32的array
离散化去重后找到每个ip地址对应下标映射 操作1若[l,r]是否没被用户用过或[l,r]仅被当前用户用过且没占满则可行否则不可行
线段树先查一下这段区间和等于0表示没被用过则可行
否则判一下当前区间最大最小值若最大最小值相等且区间和小于区间长度则可行 操作2单点询问查单点最大/最小值即可知道被哪个用户用过或没用过 操作3区间询问若[l,r]仅被一个用户全用过则区间和为区间长度区间最大最小值相等 注意离散化时需要给右端点1的值也离散化进去并考虑1带来的进位问题
否则可能会出现[1,2][4,5]在离散化前不相邻离散化后变为[1,2][3,4]相邻的情形
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N15e410,M5e410,K170,B32,INF0x3f3f3f3f;
struct segtree{int n;struct node{int l,r,v,c,mn,mx;}e[N2];#define l(p) e[p].l#define r(p) e[p].r#define v(p) e[p].v#define c(p) e[p].c#define mn(p) e[p].mn#define mx(p) e[p].mxvoid up(int p){v(p)v(p1)v(p1|1);mn(p)min(mn(p1),mn(p1|1));mx(p)max(mx(p1),mx(p1|1));}void bld(int p,int l,int r){l(p)l;r(p)r;c(p)0;if(lr){v(p)0;mn(p)INF;mx(p)-INF;return;}int midlr1;bld(p1,l,mid);bld(p1|1,mid1,r);up(p);}void psd(int p){if(c(p)){v(p1)r(p1)-l(p1)1;mn(p1)min(mn(p1),c(p));mx(p1)max(mx(p1),c(p));c(p1)c(p);v(p1|1)r(p1|1)-l(p1|1)1; mn(p1|1)min(mn(p1|1),c(p));mx(p1|1)max(mx(p1|1),c(p));c(p1|1)c(p);c(p)0; }}void init(int _n){n_n;bld(1,1,n);}void chg(int p,int ql,int qr,int v){if(qlqr)return;if(qll(p)r(p)qr){v(p)r(p)-l(p)1;mn(p)min(mn(p),v);mx(p)max(mx(p),v);c(p)v;return;}psd(p);int midl(p)r(p)1;if(qlmid)chg(p1,ql,qr,v);if(qrmid)chg(p1|1,ql,qr,v);up(p);}int cnt(int p,int ql,int qr){if(qll(p)r(p)qr)return v(p);int midl(p)r(p)1,res0;psd(p);if(qlmid)rescnt(p1,ql,qr);if(qrmid)rescnt(p1|1,ql,qr);return res;}int amn(int p,int ql,int qr){if(qll(p)r(p)qr)return mn(p);int midl(p)r(p)1,resINF;psd(p);if(qlmid)resmin(res,amn(p1,ql,qr));if(qrmid)resmin(res,amn(p1|1,ql,qr));return res;}int amx(int p,int ql,int qr){if(qll(p)r(p)qr)return mx(p);int midl(p)r(p)1,res-INF;psd(p);if(qlmid)resmax(res,amx(p1,ql,qr));if(qrmid)resmax(res,amx(p1|1,ql,qr));return res;}
}seg;
int n,m,q,op,c;
arrayint,Bf[N];
auto cal(string s){int d0;arrayint,Bans{0};for(auto y:s){if(y:){d;continue;}int vans[d];if(ay yf)vv*16(y-a)10;else vv*16(y-0);}return ans;
}
auto add_one(arrayint,By){y[n/16-1];for(int iB-1;i;--i){if(y[i]65536){y[i]-65536;y[i-1];}}return y;
}
int g(arrayint,Bv){int xlower_bound(f,fc,v)-f;return x1;
}
struct ask{int op,x;string s,t;void rd(){cinop;if(op1)cinx;cins;f[c]cal(s);if(op2)ts;else{cint;f[c]cal(t);f[c]add_one(f[c-1]);c;}}void sol(){int lg(cal(s)),rg(cal(t)),wseg.cnt(1,l,r);int mnseg.amn(1,l,r),mxseg.amx(1,l,r);if(op1){if(!w || (wr-l1 mnmx mnx)){seg.chg(1,l,r,x);coutYESendl;}else{coutNOendl;}}else if(op2){cout(mnINF?0:mn)endl;}else{cout(wr-l1 mnmx?mn:0)endl;}}
}e[M];
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnq;for(int i1;iq;i){e[i].rd();}sort(f,fc);cunique(f,fc)-f;seg.init(c5);for(int i1;iq;i){e[i].sol();}return 0;
}
202303-5 施肥分治线段树树状数组
n,m3000乱搞一下就ok数据范围再小的就不提了
虽然事后发现n,m3000的暴力我是用的O(nmlogn)而官解是O(n^2nm)
特殊性质的分也比较好判断这样75分就到手了然后就不会了就去嫖了官解
这个做法本质是对O(n^2nm)的暴力套了个分治
虽然出题人说两个满分分别是用李超树和分块过的感觉很神秘
理解了好久花若干时间写完代码之后交上去wa成sb
对拍拍出来问题之后交上去又T了把回收改成区间删除才过
复杂度O((nm)logm)也就是一个log但是貌似被我实现成了两个log感谢出题人不杀之恩
开了四棵线段树树状数组常数比较小最后也过了讲一下中间遇到的各个做法
60分题解O(n^2nm)暴力
按右端点增序枚举假设当前枚举到的右端点为R此时只能选右端点R的线段
记a[i]为对于i来说只能选右端点R的线段时能覆盖i的最大的左端点
那么固定右端点R时若[L,R]是一组解一定有对于任意LiRLa[i]
换言之为了覆盖[L,R]中间的值采用的线段其左端点不能比L更靠左 所以就可以一边枚举右端点一边将线段插入
插入一条线段[i,R]时涉及到一段区间a值的动态修改本质是区间[i,R]的a值和i取max 若ijRa[j]a[i]那么为了覆盖区间[i,R]实际左端点也需至少取到a[j]的位置
所以实际计算贡献的时候需要考虑后缀对当前值的影响
维护后缀最小值可以搞个单调栈也可以逐项维护
后缀的数组实际是形如1 1 1 3 3 10 10 10 10的分段阶梯数组
值即为左端点的值贡献为左端点出现的种类数
#includebits/stdc.h
using namespace std;
typedef pairint,int P;
typedef long long ll;
const int N2e510;
int n,m,l,r,a[N],suf[N];
ll ans;
vectorintf[N];
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,l,r);f[r].push_back(l);}for(int i1;in;i){for(auto v:f[i]){for(int jv;ji;j){a[j]max(a[j],v);}}suf[i]a[i];ans(suf[i]0);for(int ji-1;j1;--j){suf[j]min(suf[j1],a[j]);if(suf[j]!suf[j1] suf[j])ans;}}printf(%lld\n,ans);return 0;
}
75分题解特殊性质
特殊性质不存在区间的相互包含关系
就是一堆相交区间如果把两两相交的区间合并成一个连通块
则组成若干个连通块且连通块内是偏序的
一定可以选一段连续的区间取到左区间的左端点和右区间的右端点
所以连通块内有x个区间时对答案的贡献是x*(x1)/2
#includebits/stdc.h
using namespace std;
typedef pairint,int P;
typedef long long ll;
const int N2e510;
int n,m,c,mx;
vectorintf[N],st[N];
setintcur;
mapP,boolvis;
ll ans,now[N];
struct node{int l,r;
}e[N],x;
bool operator(node a,node b){return a.rb.r;
}
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,x.l,x.r);//e[c]x;if(!vis[P(x.l,x.r)])e[c]x;vis[P(x.l,x.r)]1;}mc;sort(e1,em1);if(n3000){for(int i1;im;){int ji,mxe[j].r;while(j1m e[j1].lmx1){j;mxmax(mx,e[j].r);}int szj-i1;ans1ll*sz*(sz1)/2;ij1;}printf(%lld\n,ans);}else{for(int i1;im;i){st[e[i].l].push_back(e[i].r);}for(int i1;in;i){if(st[i].empty())continue;cur.clear();for(auto v:st[i])cur.insert(v);for(int j1;jm;j){if(e[j].li)continue;if(cur.lower_bound(e[j].l-1)!cur.end()){int x*cur.lower_bound(e[j].l-1);if(xe[j].r)cur.insert(e[j].r);}}anscur.size();}printf(%lld\n,ans);}return 0;
}
100分题解分治线段树树状数组
官解里有提到并查集维护区间并没太想明白所以开了四棵线段树 分治之后左区间[l,mid]右区间[mid1,r]
考虑如何统计跨左右区间的答案即满足lLmid且mid1Rr的(L,R)答案
先定义点术语方便下面描述 左半区间[l,mid] 右半区间[mid1,r] 左内区间被完整包含于[l,mid]内的区间 右内区间被完整包含于[mid1,r]内的区间 跨域区间左端点位于[l,mid]右端点位于[mid1,r]的区间 从x走到y存在一个区间[x,y]或存在若干个区间覆盖在一起使得左端点是x右端点y 若(L,R)合法 换言之从左端点L走到右端点R有两种情况
1. 存在跨域区间[L,R]一步从L走到R
2. ①L通过左内区间走若干步走到[l,mid]内最靠右的位置记为a[L]
②对称后是相遇问题R通过右内区间走若干步走到[mid1,r]最靠左的位置记为a[R]
③L通过一个跨域区间跨域区间左端点在[L,a[L]1]内走到[mid1,r]内最靠左位置记为b[L]
④R通过一个跨域区间跨域区间右端点在[a[R]-1,R]内走到[l,mid]内最靠右位置记为b[R]
⑤[L,b[L]]和[b[R],R]两个区间需要满足覆盖在一起后是[L,R]
因为b[L]midmid1b[R]所以区间相交是自然满足的
还需满足b[L]R且Lb[R]这是一个静态二维数点问题可用树状数组或cdq分治解决 ①-②步用了一棵线段树seg区间查询单点更新
左半边递减遍历维护最大值右半边递增遍历维护最小值
③用了一棵线段树lseg单点更新维护左端点在[l,mid1]内右端点在右半区间的右端点最小值
④用了一棵线段树rseg单点更新维护右端点在[mid,r]内左端点在左半区间的左端点最大值
[l,mid1]是因为[L,a[L]1]比如[1,2]和[3,4]也可以覆盖[1,4][mid,r]同理
因为③④区间有交集且和①②维护的信息不同所以各开了一棵线段树 外层已经是分治了内层就不cdq分治了⑤这里采用树状数组的方式解决
形如(L,b[L])和(b[R],R)的二维点对按第一维排增序
第一维相同时先插入再查询左半边插入到b[L]位置右半边查询区间[b[R],R]
由于b[R]midb[L]恒成立所以直接查sum(R)就可以 此外注意到1和2的①②③④的情况都不一定存在所以需要分别判一下不存在的情况
当然如果用INF和-INF配合max min之后能统一写法的话最好
分治为了使复杂度正确每次使用完线段树之后需要手动回收
对树状数组手动-1撤销操作对线段树[l,r]段区间删除打标记
由于维护的是最大最小值删除后最大值为-INF最小值为INF
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define SZ(x) (int)x.size()
#define fi first
#define se second
const int N2e510,INF0x3f3f3f3f;
int n,m,l,r,a[N],b[N];
vectorintL[N],R[N];
ll ans;
struct segtree{int n;struct node{int l,r,c,mn,mx;}e[N2];#define l(p) e[p].l#define r(p) e[p].r#define c(p) e[p].c#define mn(p) e[p].mn#define mx(p) e[p].mxvoid up(int p){mn(p)min(mn(p1),mn(p1|1));mx(p)max(mx(p1),mx(p1|1));}void bld(int p,int l,int r){l(p)l;r(p)r;c(p)0;if(lr){mn(p)INF;mx(p)-INF;return;}int midlr1;bld(p1,l,mid);bld(p1|1,mid1,r);up(p);}void init(int _n){n_n;bld(1,1,n);}void chg(int p,int x,int v){if(l(p)r(p)){mn(p)min(mn(p),v);mx(p)max(mx(p),v);return;}int midl(p)r(p)1;psd(p);chg(p1|(xmid),x,v);up(p);}void psd(int p){if(c(p)){mn(p1)INF;mx(p1)-INF;c(p1)c(p);mn(p1|1)INF;mx(p1|1)-INF;c(p1|1)c(p);c(p)0; }}void del(int p,int ql,int qr){if(qll(p)r(p)qr){mn(p)INF;mx(p)-INF;c(p)1;return;}psd(p);int midl(p)r(p)1;if(qlmid)del(p1,ql,qr);if(qrmid)del(p1|1,ql,qr);up(p);}int amn(int p,int ql,int qr){if(qll(p)r(p)qr)return mn(p);int midl(p)r(p)1,resINF;psd(p);if(qlmid)resmin(res,amn(p1,ql,qr));if(qrmid)resmin(res,amn(p1|1,ql,qr));return res;}int amx(int p,int ql,int qr){if(qll(p)r(p)qr)return mx(p);int midl(p)r(p)1,res-INF;psd(p);if(qlmid)resmax(res,amx(p1,ql,qr));if(qrmid)resmax(res,amx(p1|1,ql,qr));return res;}
}seg,lseg,rseg;
struct BitPre{int n,tr[N];void init(int _n){n_n;memset(tr,0,(n1)*sizeof(*tr));}void add(int x,int v){for(int ix;in;ii-i)tr[i]v;}int ask(int x){if(x0)return 0;int ans0; for(int ix;i;i-i-i)anstr[i];return ans;}
}tr;
bool ok(int x){return x!INF x!-INF;
}
bool in(int x,int l,int r){return lx xr;
}
void cdq(int l,int r){if(lr)return;int mid(lr)/2;cdq(l,mid);cdq(mid1,r);for(int imid;il;--i){a[i]-INF;b[i]INF;for(auto v:L[i]){if(vr)continue;if(vmid)a[i]max(a[i],v);else b[i]min(b[i],v);//有无需本侧的情况if(vmid)rseg.chg(1,v,i);}if(ok(a[i])){a[i]max(a[i],seg.amx(1,i,min(mid,a[i]1)));seg.chg(1,i,a[i]);}}for(int imid1;ir;i){a[i]INF;b[i]-INF;for(auto v:R[i]){if(vl)continue;if(vmid1)a[i]min(a[i],v);else b[i]max(b[i],v);if(vmid1)lseg.chg(1,v,i);}if(ok(a[i])){a[i]min(a[i],seg.amn(1,max(mid1,a[i]-1),i));seg.chg(1,i,a[i]);}}vectorarrayint,3all;for(int imid;il;--i){if(ok(a[i])){ // [i,a[i]1]int vlseg.amn(1,i,a[i]1);if(in(v,mid1,r)){b[i]min(b[i],v);}}if(in(b[i],mid1,r))all.push_back({i,0,b[i]});}for(int imid1;ir;i){if(ok(a[i])){ // [a[i]-1,i]int vrseg.amx(1,a[i]-1,i);if(in(v,l,mid)){b[i]max(b[i],v);}}if(in(b[i],l,mid))all.push_back({b[i],1,i});}sort(all.begin(),all.end());for(auto w:all){int opw[1],ubw[2];if(op0)tr.add(ub,1);else anstr.ask(ub);//左[l,a[l]]右[a[r],r]满足la[r]a[l]1且a[r]-1a[l]ra[l]midmid1a[r]显然成立}seg.del(1,l,r);lseg.del(1,l,r);rseg.del(1,l,r);for(auto w:all){int opw[1],ubw[2];if(op0)tr.add(ub,-1);}
}
int main(){scanf(%d%d,n,m);seg.init(n);lseg.init(n);rseg.init(n);tr.init(n);for(int i1;im;i){scanf(%d%d,l,r);//重复无所谓L[l].push_back(r);R[r].push_back(l);}cdq(1,n);printf(%lld\n,ans);return 0;
}
/*
9 4
1 4
1 8
3 9
2 5
*/
写在最后
感觉数据结构有点多了写起来比较疲惫
四五题连放两个数据结构有点不太像之前csp的风格
反观之前的第三题大模拟本次变成中模拟了
anyway完结 撒花
