2023-10-14

题目

Little Brother

题目描述

难度&重要性(1~10):7

题目来源

CQYC

题目算法

几何，二分

解题思路

Sol

我们知道，对于两个圆，我们无非就只有三种情况：相离，相切，相交。而这道题目是不允许其他圆相交，而两个圆不相交只有两种情况：包含，不包含。

根据垂径定理得知，过线段两端的圆的圆心是一定在线段的中垂线上的。而对于每一个其他的圆，与其相交的圆心一定是在一个连续的区间之间的。那么我们就可以考虑用二分来对每一个圆判断不能存在的区间，再将这一段区间打到一个数轴上，用扫描线来找最小半径就行了。

如图，我们就需要将 \(O'O''\) 打到一个数轴上，用扫描线找到最小半径就行了。

细节比较多，请看代码。

完成状态

标签：题目,数轴,相交,扫描线,此方,校内,konata
From： https://www.cnblogs.com/OIerBoy/p/17764593.html

231011校内赛
T1树上的数题解比上一次好一些的第一题不过我还是没做出来一眼树形\(dp\)不过状态设计和转移不是很好列容易想到对于子树枚举，记录\(f_{i,j}\)表示\(i\)的子树空出了\(j\)个点时的方案数对于每一个节点的初始状态都是\(f_{i,0}=n-dep_i\\\f_{i,1}=1\)为......
231009校内赛
T1里群题解阴间第一题题目中有一个很明显的建图方法就是对于第\(i\)天入群的人在第\(j\)天退群那么就在\(i,j\)之间连一条边首先有一个结论，管理员个数不大于\(3\)对于这个结论，证明如下：首先第一次删除出现后就一定需要两个管理员了如果某次删除只删掉了某一个管理......
231007校内赛
T1karma题解首先从贪心的思路出发把所有零多的字符串放在前面，但如下一组数据便可以卡掉201100接着我们可以来思考对于贪心的更改多举几组不同的可以卡掉的样例后可以发现如下规律先将所有字符串按\(0\)的数量排一遍序对于每一个字符串的\(0\)和\(1\)的数量我......
231004校内赛
T1水管题解很简单的一道题，别想复杂了只要一边\(dfs\)即可先将当前点的所有水量给出去，如果缺水就给出去负数那么等到最后一个节点如果不是刚好合适，那么就把剩余水量回溯回来，无论正负再如此给下一个连边的点如果最后一个点刚好合适那么给下一个点的就是\(0\)实现很简单......
231002校内赛
T1数独题解十分简单的一道模拟题有sb少打了一个换行挂50分#include<bits/stdc++.h>#defineN15usingnamespacestd;structnode{ inta[N][N],be;}t[N*10];intT,n=9,q;intferror(intcnt,intx,inty,intk){ for(inti=1;i<=n;i++) if(t[cnt].a[x][i]==k)......
230930校内赛
T1洛阳怀题解首先非常容易求出的是所有的\(\gcd\)对于\(\gcd\)而言，如果它的分数是负数，那么将它除去一定会使这个数列得分变大所以只用求出所有的\(\gcd\)的分数并判断正负以及是否除过当前答案了就可以了还有一点是因为\(\gcd\)是单调不降的，所以可以从后往前查保证......
2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛)
A.AXorBProblem（计数）输入511223输出9说明点击查看代码#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false);cin.tie(0),cout.tie(0)#defineintlonglongusingnamespacestd;constintN=2e5+10;unordered_map<int,int>......
230925校内赛
T1开挂我卢本伟没有开挂题解挺简单的，不过我写的比较麻烦因为我们需要让多的尽可能多来让少的尽可能少，所以会想到用栈来存储需要更改的数，靠近栈底就需要更多次数来更改，栈顶则更少最后只用记录下来所有的次数并按从多到少依次分配从小到大的修改代价#include<bits/stdc++.h......
230927校内赛
T1集合题解很明显的一道树形\(dp\)题我也没看出来dalao们说有一道\(ddp\)的题转移方式一模一样于是都切了，就我是sb首先有一个非常明显的性质在于所有的被选的点一定是可以构成一颗连通子树的最终选取的\(k\)个点一定是从这颗子树中最远点对的一个点沿着这颗子树直......
校内互测第一周(East!XI~East!XV)总结(窝还是退役吧QAQ
==真是不想说啥了。。。像我这种沙茶蒟蒻还是早点滚粗的好。。。Day1East!XI出题人：18357打开题瞬间傻了。。。三道树上问题。。。三道。。。T1：给定一棵N个节点的无根树，求每个节点到其它的节点的∑(路径长度xorM)。M<=15TM这傻逼题我写了个0~15的Trie树。。。明明记录个0~15的数......

[校内]此方（konata）