首页 / 更多教程 / 【UOJ Round #8】
【UOJ Round #8】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【UOJ Round #8】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4585字,纯文字阅读大概需要7分钟。
内容图文
![【UOJ Round #8】](/upload/InfoBanner/zyjiaocheng/1257/0582b5cfc6854b08a8b4018cb74981a8.jpg)
A
一道不错的题,虽然大家都觉得是水题,然而蒟蒻我想出来的好慢……Orz alpq
发现其实就是一个网格图,每一个大块都是同一颜色……横纵坐标互不干扰……
![技术分享](/upload/getfiles/default/2022/11/14/20221114061734959.jpg)
![技术分享](/upload/getfiles/default/2022/11/14/20221114061734982.jpg)
1 // UOJ Round #8 A 2 #include<vector> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<iostream> 7 #include<algorithm> 8#define rep(i,n) for(int i=0;i<n;++i) 9#define F(i,j,n) for(int i=j;i<=n;++i) 10#define D(i,j,n) for(int i=j;i>=n;--i) 11usingnamespace std; 12 typedef longlong LL; 13 inline int getint(){ 14int r=1,v=0; char ch=getchar(); 15for(;!isdigit(ch);ch=getchar()) if (ch==‘-‘) r=-1; 16for(; isdigit(ch);ch=getchar()) v=v*10-‘0‘+ch; 17return r*v; 18} 19constint N=1e5+10; 20/*******************template********************/2122int n,m,x[N],y[N]; 23int bel1[N],bel2[N],cnt1,cnt2; 24int main(){ 25#ifndef ONLINE_JUDGE 26 freopen("A.in","r",stdin); 27 freopen("A.out","w",stdout); 28#endif29 n=getint(); m=getint(); 30 F(i,1,n) x[i]=getint(); 31 F(i,1,m) y[i]=getint(); 32int now=x[1]; 33 bel1[1]=1; cnt1=1; 34 F(i,2,n){ 35if (x[i]!=now){ 36 cnt1++; 37 now=x[i]; 38 } 39 bel1[i]=cnt1; 40 } 41 now=y[1]; bel2[1]=1; cnt2=1; 42 F(i,2,m){ 43if (y[i]!=now){ 44 cnt2++; 45 now=y[i]; 46 } 47 bel2[i]=cnt2; 48 } 4950int Q=getint(); 51 F(i,1,Q){ 52int x1=getint(),y1=getint(),x2=getint(),y2=getint(); 53if (x2<x1) swap(x1,x2); if (y2<y1) swap(y1,y2); 54int t1=min(bel1[x2]-bel1[x1],cnt1-bel1[x2]+bel1[x1]-(x[1]==x[n])); 55int t2=min(bel2[y2]-bel2[y1],cnt2-bel2[y2]+bel2[y1]-(y[1]==y[m])); 56 printf("%d\n",t1+t2); 57 } 58return0; 59 }
B
线段树的好题!(话说为什么我感觉那么像KD-Tree……
前两个操作就是普通线段树维护就可以……
查询的时候,感觉就是将n个点的横坐标固定成1~n了……然后用KD-Tree的估价函数来判断是否进入子树查询……
我一开始query写的逗比了,膜了一下vfk的姿势……
然后这题我TLE了好久……
重点是题解里说的:先判断右子树,再判断左子树!!!(就像KD-Tree的时候,要先像估价值较大的那一侧走啊!我怎么给忘了……sad
![技术分享](/upload/getfiles/default/2022/11/14/20221114061734959.jpg)
![技术分享](/upload/getfiles/default/2022/11/14/20221114061734982.jpg)
1 // UOJ Round #8 B 2 #include<vector> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<iostream> 7 #include<algorithm> 8#define rep(i,n) for(int i=0;i<n;++i) 9#define F(i,j,n) for(int i=j;i<=n;++i) 10#define D(i,j,n) for(int i=j;i>=n;--i) 11usingnamespace std; 12 typedef longlong LL; 13 inline int getint(){ 14int r=1,v=0; char ch=getchar(); 15for(;!isdigit(ch);ch=getchar()) if (ch==‘-‘) r=-1; 16for(; isdigit(ch);ch=getchar()) v=v*10-‘0‘+ch; 17return r*v; 18} 19constint N=1e5+10; 20/*******************template********************/ 21 22int n,m,x0,v[N],mn[N<<2],mx[N<<2]; 23bool rev[N<<2]; 24 inline int ran(){ 25 x0=((LL)x0*100000005+20150609)%998244353; 26return x0/100; 27} 28#define mid (l+r>>1) 29#define L (o<<1) 30#define R (o<<1|1) 31void maintain(int o,int l,int r){ 32 mn[o]=min(mn[L],mn[R]); 33 mx[o]=max(mx[L],mx[R]); 34} 35void change(int o){ 36 rev[o]^=1; 37 mn[o]=100000-mn[o]; mx[o]=100000-mx[o]; 38 swap(mn[o],mx[o]); 39} 40void Push_down(int o,int l,int r){ 41if (rev[o]){ 42 change(L); change(R); 43 rev[o]=0; 44 } 45} 46void build(int o,int l,int r){ 47if (l==r){ 48 mn[o]=mx[o]=ran()%100001; 49 }else{ 50 build(L,l,mid); 51 build(R,mid+1,r); 52 maintain(o,l,r); 53 } 54} 55void update(int o,int l,int r,int p,int val){ 56if (l==r){ 57 mn[o]=mx[o]=val; 58 }else{ 59 Push_down(o,l,r); 60if (p<=mid) update(L,l,mid,p,val); 61else update(R,mid+1,r,p,val); 62 maintain(o,l,r); 63 } 64} 65void modify(int o,int l,int r,int ql,int qr){ 66if (ql<=l && qr>=r){ 67 change(o); 68 }else{ 69 Push_down(o,l,r); 70if (ql<=mid) modify(L,l,mid,ql,qr); 71if (qr>mid) modify(R,mid+1,r,ql,qr); 72 maintain(o,l,r); 73 } 74} 75 76 LL ans=0; 77int a,b,c; 78 inline LL calc(int x,int y){return (LL)a*x+(LL)b*y+(LL)c*x*y;} 79void query(int o,int l,int r,int ql,int qr){ 80if (calc(min(r,qr),mx[o])<=ans) return; 81if (l==r){ 82 ans=calc(l,mx[o]); 83return; 84 } 85 Push_down(o,l,r); 86if (qr>mid) query(R,mid+1,r,ql,qr); 87if (ql<=mid) query(L,l,mid,ql,qr); 88} 89 90int main(){ 91#ifndef ONLINE_JUDGE 92 freopen("B.in","r",stdin); 93 freopen("B.out","w",stdout); 94#endif 95 n=getint(); m=getint(); x0=getint(); 96// F(i,1,n) v[i]=ran()%100001; 97 build(1,1,n); 98char cmd; 99 F(i,1,m){ 100while(cmd=getchar(),cmd!=‘C‘ && cmd!=‘R‘ && cmd!=‘Q‘); 101if (cmd==‘C‘){ 102int p=ran()%n+1,y=ran()%100001; 103 update(1,1,n,p,y); 104 }elseif (cmd==‘R‘){ 105int ql=ran()%n+1,qr=ran()%n+1; 106if (qr<ql) swap(ql,qr); 107 modify(1,1,n,ql,qr); 108 }elseif (cmd==‘Q‘){ 109 a=getint(),b=getint(),c=getint(); 110int ql=ran()%n+1,qr=ran()%n+1; 111if (qr<ql) swap(ql,qr); 112 ans=0; 113 query(1,1,n,ql,qr); 114 printf("%lld\n",ans); 115 } 116 } 117return0; 118 }
原文:http://www.cnblogs.com/Tunix/p/4567728.html
内容总结
以上是互联网集市为您收集整理的【UOJ Round #8】全部内容,希望文章能够帮你解决【UOJ Round #8】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。