P11048 [蓝桥杯 2024 省 Java B] 拼十字题目背景备注原题Java时间限制 3.0s空间限制 512 MB。题目描述在 LQ 国神秘的古老森林有一座被称为 “拼十字” 的神秘遗迹。据传 “拼十字” 是由古代文明建造的它是一个巨大的石头结构由两个巨大的矩形交叉叠放在一起形成了一个庄严而神秘的十字形状。这个遗迹被认为是连接人类和神灵之间的通道拥有神秘的力量和能量。现在给出NNN个矩形其中第iii个矩形的长度和宽度分别为lil_ili​wiw_iwi​并且矩形的颜色cic_ici​为红(0)(0)(0)、黄(1)(1)(1)、蓝(2)(2)(2)中的一种。现在小蓝想知道在这NNN个矩形中有多少对可以“拼十字”两个矩形可以“拼十字”的充要条件是两个矩形的颜色不同矩形111的长度严格大于矩形222的长度并且矩形111的宽度严格小于矩形222的宽度。注意矩形长度和宽度属性是固定的是不可以通过旋转矩形而发生转变的。输入格式第一行一个整数NNN表示有NNN个矩形。接下来NNN行每行输入三个整数lll、www、ccc表示一个矩形的长、宽和颜色。输出格式输出一个整数表示答案。由于答案可能会很大所以你需要将答案对109710^9 71097取模之后输出。输入输出样例 #1输入 #15 1 10 0 6 6 0 8 6 1 6 10 0 1 2 1输出 #12说明/提示【样例解释】第333个矩形可以和第111个矩形拼十字第333个矩形也可以和第444个矩形拼十字。所以一共有两对矩形可以拼十字答案为222。【数据范围】对于30%30\%30%的评测用例1≤N≤50001 \leq N \leq 50001≤N≤5000。对于100%100 \%100%的评测用例1≤N≤1051 \leq N \leq 10^51≤N≤1051≤l,w≤1051 \leq l,w \leq 10^51≤l,w≤1050≤c≤20 \leq c \leq 20≤c≤2。C实现#includebits/stdc.husingnamespacestd;constintN1e55,p1e97;inlineintlowbit(intx){returnx-x;}structnode{intl,w,c,num;}a[N];boolcmp1(node x,node y){returnx.ly.l;}boolcmp2(node x,node y){returnx.wy.w?x.numy.num:x.wy.w;}intn,tr[3][N],mp[N],cnt[3],ans,to[N];inlinevoidadd(intx,inty,intopt){while(xn)tr[opt][x](tr[opt][x]y)%p,xlowbit(x);}inlineintquery(intx,intopt){intres0;while(x)res(tr[opt][x]res)%p,x-lowbit(x);returnres;}//树状数组模板不过多赘述intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d%d%d,a[i].l,a[i].w,a[i].c);sort(a1,a1n,cmp1);//用 l 的值从小到大的排名代替逆序对中的下标for(inti1;in;i){if(a[i].la[i-1].l)to[i]to[i-1]1;if(!a[i].c){for(intji-to[i];ji;j){if(a[j].wa[i].wa[j].c)ans--;}}elseif(a[i].c1){for(intji-to[i];ji;j){if(a[j].wa[i].wa[j].c!1)ans--;}}elseif(a[i].c2){for(intji-to[i];ji;j){if(a[j].wa[i].wa[j].c!2)ans--;}}//暴力判重可能会寄如果出题人精心构造了数据a[i].numi;}sort(a1,a1n,cmp2);for(inti1;in;i)mp[a[i].num]i;for(inti1;in;i){intopta[mp[i]].c;cnt[opt],add(mp[i],1,opt);if(!opt)ans(anscnt[1]-query(mp[i],1)cnt[2]-query(mp[i],2))%p;elseif(opt1)ans(anscnt[0]-query(mp[i],0)cnt[2]-query(mp[i],2))%p;elseans(anscnt[0]-query(mp[i],0)cnt[1]-query(mp[i],1))%p;//判断颜色不同就累加答案}printf(%d,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容