酷文的小站

传送门 题目大意 1234567小菜的妹妹小诗就要读小学了！正所谓计算机要从娃娃抓起，小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。　　小菜刚教完gcd即最大公约数以后，一知半解的妹妹写了如下一段代码：　　 sum:=0;　　 for i:=1 to n-1 do　　 for j:=i+1 to n do sum:=sum+gcd(i,j)　　显然这个程序的效率是很低的，小明打算写一个更强的程序，在求出sum的同时比妹妹跑的更快。 输入格式 12第一行一个整数t，即表示有t组数据　　接下来t行，每行一个整数n 输出格式 1t行，每行一个整数，表示n所对应的sum值 样例输入 123210100 样例输出 126713015 数据范围 1234【数据规模】　　20%数据t≤100,n≤100　　40%数据t≤1000,n≤2000　　100%数据t≤10000,n≤1000000 题解 题目目的是求111~nnn内任意两个数的gcdgcdgcd之和，先放着。 假设gcd(n,i)=kgcd(n,i)=kgcd(n,i)=k，则gcd(nk,ik)=1gcd(\frac{n}{k},\ ...

冬令营的各式各样的总结 2022.1.18总结 T1：一道数学思维题，想了一个上午，发现nnn特别小，二分答案后寻找以各顶点为圆心，二分出来的答案为半径，交于多边形的边的扇形，讨论一下交点数，用相似求出交点坐标，用一些奇妙的算法（叉积或者暴力）求出面积判断交点是否在多边形以内，就可以了；考场上，有一种情况没讨论对，当交点数为0时应该把交点当成扇形与两边的交点 T2：不会 T3：30′30'30′暴力BFSBFSBFS,但是考试的时候没注意到它可以移到哪里，挂0，60′60'60′二维前缀和，二维差分，100′100'100′用二维字符串通配，FFTFFTFFT优化，但是我没学 T4：用前缀异或和来求解 2022.1.19总结 T1：一道记忆化搜索，两个dfsdfsdfs轮流跳，根据最优策略，状态压缩即可。考场时以为是求DDD的最大值，所以炸零了 T2：又是一道数学思维题，观察可以发现n≤104n \le 10^4n≤104，因此n2n^2n2的算法理论上也是能过的。对一个点，若它与其他点围成了一个凸包，那么一定有一条经过它的直线使得所有的点都在它的一侧。 ...

Description 盟军司令决定采用飞机对德军设在海岸线上的机枪阵地进行定点清除。为简化模型，这里将德军防线看成一条直线。而每个阵地都是这条线上的一个点。阵地依次编号为1-N，其中第k个阵地的坐标为X~k~。此外，每个阵地还有一个防御值D~k~。 盟军飞机扔下的炸弹不是完全相同的。每颗炸弹均有一个破坏值A~i~和一个范围值B~i~，对于编号为~i~的炸弹，如果它在防线上坐标为Y~i~的点爆炸，那么它将炸毁坐标在[Y~i~-B~i~,Y~i~+B~i~]范围中所有D~k~<=A~i~的尚未被炸毁的德军阵地。而同时对其他针对不造成任何影响。 现在已知：阵地数，每个阵地的X~k~和D~k~（k=1,2,…,N），以及发射的炮弹数，和按照炮弹爆炸顺序给出的每个炸弹的A~i~，B~i~和Y~i~。（i=1,2,…,M） 你能帮助盟军计算出每颗炸弹究竟能摧毁了多少个阵地吗？ Input 输入文件包含多组输入数据。 对于每组数据，第一行是一个整数N（1<=N<=100000），接下来N行，每行两个整数X,D（0<=X，D<=10^9^），分别是其对应的阵地的坐标和 ...

Description 公园里长满了树木，为了更加美观也能更方便公园里的行人，需要砍掉一些树木，增加一些散步小路。公园可看作一个平面直角坐标系，其中所有树木都生长在图中的整点上，并且没有两棵树在同一个位置。要建造的散步小路都是长方形的回路，且长方形的四边都与x轴或y轴平行，在建造这条小路时，需要把小路长方形四边上所有树木都砍掉。当然不同的小路之间可能有交点，甚至会有重叠，但在重叠部分上树木只在建第一次小路时砍掉。现在给出所有树木的坐标，再按建造顺序给出小路的坐标，求出在建造每条小路时分别需要砍掉多少棵树。 Input 数据的第一行为两个非负整数N和M,分别表示原有树木的数量和要建造小路的数量。 下面接着的N行，每行有两个整数，分别表示每棵树木的x坐标和y坐标。 下面接着的M行，每行有四个整数，x1,y1,x2,y2(x1<x2,y1<y2)，表示小路形成的长方形的四个顶点分别是(x1,y1),(x1,y2),(x2,y2),(x2,y1)。 Output 输出M行，每行一个整数，分别表示在建造每条小路时砍掉的树木的数量。 Sample Input 123456789101 ...

Description 《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地里老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(I,j),使得他感到是最满意的，即(I,j)这条路上所有山的喜恶程度之和是所有(c,d)(a<=c<=d<=b)最大。于是老师便向你请教，你能帮助他吗？值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。 Input 输入第一行是两个数n,m,2<=n<=100000,1<=m<=100000,n表示一共有n座山，m表示老师想查询的数目。 　　第二行是n个整数，代表n座山的喜恶度，绝对值均小于10000。 　　以下m行每行有两个数，a,b,1<=a<=b<=n,表示第a座山到第b座山。 Output 一共有m行，每行有三个数I,j,s,表示从第i座山到第j座山总的喜恶度为s。显然，对于每个查询，有a<=i<=j<=b,如果 ...

Description 亚特兰蒂斯人激怒了众神，众神之王宙斯决定要好好教化他们。这时，一位居心叵测的bug魔王看准了时机，打着“教化亚特兰蒂斯人”的旗号，暗地里策划了一个极具野心的阴谋：铲平亚特兰蒂斯。善良的宙斯并没有发现他的阴谋，草率地批准了他这次“教化”行动，于是一场危机就要降临亚特兰蒂斯了。。。 幸好亚特兰蒂斯拥有一位相当优秀的先知Cubic，他发现了bug魔王的阴谋，并了解到bug魔王会派出N种怪物来入侵亚特兰蒂斯，现在就要想办法对付这N种怪物。Cubic还了解到，每一种怪物都对应一种剑术和一种法术，这种怪物可以被这对应的剑术打败，也可以被对应的法术打败。不同的怪物可能对应不同的剑术和法术，而一种剑术或法术可以击败多种怪物。只要Cubic得到某怪物的信息，他就可以知道对应的剑术和法术，不会只知其一。 亚特兰蒂斯里最优秀的剑术师是RC，最优秀的法术师是Aesop，这次为了保护亚特兰蒂斯，他们都愿意挺身而出。但问题是他们并不会这些特定的剑术和法术，必须抓紧时间学习。但由于学习新剑术或新法术需要闭关学习，为了避免bug魔王搞奇袭，必须至少留下其中一个专门看守，于是他们两个就不能同时 ...

传送门 题目描述 像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 N 个区块组成，而这些区块放在一个无限大的正方形网格上。第 x 行第 y 列的单元格由有序数对 (x,y)来标识。单元格 (0,0) 位于网格的左上角。给定一个单元格 (x,y)，与之相邻的单元格（如果存在的话）分别为：(x−1,y)，(x+1,y)，(x,y-1)，(x,y+1)。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 (x,y) 上，当且仅当 1≤x,y≤2^31−2 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件： 对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。 对于任意两个非空的单元格，至少存在一连串相邻的非空单元格连接它们。 以下 4个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 3个图不满足第二个条件，第 4个图两个条件均不满足。 当遍历理想城 ...

Description Y国向X国发动了总进攻，X国在防御方面有着非常高的科技，他们在国内建了许多防御塔（共N个），两个防御塔间可以产生保护光膜（一种力场），通常情况下，X国的防御系统设定力场只在外围产生，即若把所有防御塔看成平面上N个点的点集，则力场只在点集的凸包（边上的也算在内）上相邻顶点之间产生。防御塔产生的保护膜异常坚实，而防御塔本身却相对比较脆弱，所以Y国打算集中火力破坏防御塔，可异由于火力不足每次只能攻陷一个防御塔。当一个防御塔被摧毁时，X国的防御系统马上自动调整，后果新计算 凸包，重新建立防御力场。Y国目标是摧毁A城，Y国可以摧毁一个城，条件是这个城在凸包上。 Input 第一行，一个整数N（3<=N<=10000） 接下来N行，每行表示一个防御塔的整数坐标（第一个数是横坐标，第二个数是纵坐标，绝对值<=10000）。 最后一行给出A城的整数坐标，含2个整数，表示横坐标和纵坐标(绝对值小于等于10000)。 Output 最少要摧毁的防防御塔数。 Sample Input 1234530 010 00 122 3 Sample Output 11 题目 ...

Description 很久以前，在世界的某处有一个形状为凸多边形的小岛，岛上的居民们决定建一个祭坛，居民们任务祭坛的位置离岛的顶点处越远越好。 你的任务是求凸多边形内一点，使其与各顶点的距离中最短的距离最远，点在边上也可以。 这样的点可能有多个，你只需输出这些点与各顶点的最短距离。 Input 第一行是一个整数N(3<=N<=100)。 接下来N行按逆时针顺序给出每个顶点的坐标，每行包含2个实数，表示顶点的横坐标和纵坐标（坐标绝对值小于10000）。 Output 输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值（保留三位小数）。 Sample Input 123430 29 07 7 Sample Output 14.893 题目大意 给出一个多边形，最大化一个点到各顶点的最短的距离，求最大化的最短距离 题解 从样例入手 此时，最大化的最短距离为这个三角形的外接圆的半径 这启示我们从圆入手 看到最大，最小，想到二分答案ansansans 检验一个答案ansansans是否正确，可以以每个顶点为圆心，ansansans长为半径画弧，交多边形的边 假设 ...

TJOI2014可以说是相对比较的容易（改起来很快），给冬令营的题目写篇题解。 Day1 匹配 看了题解后一眼看出是二分图最大权匹配 用匈牙利算法或者转换成费用流模型用Dinic， 暴力枚举删边，若最优匹配发生改变，说明这条边属于交集 排序即可 （由于站长还没切，代码先咕了~） 电源插排 题目大意就是完成以下要求： 寻找最大区间（log⁡n\log nlogn） 分裂区间（log⁡n\log nlogn） 合并区间（log⁡n\log nlogn） 本题非常适合练习STL 观察到QQQ较小，于是将询问离线。 寻找最大区间可以用pairpairpair类型的优先队列priorityprioritypriority_queuequeuequeue来存区间的长和起点 的特性就是先比较第一个值再比较第二个，因此firstfirstfirst里存区间长，secondsecondsecond存起点位置 这样刚好满足了寻找最大最右区间的要求。 假设我们找到的最大最右区间为[st,st+len−1][st,st+len-1][st,st+len−1] 那么这名学生要把电源插在pos=⌊2st ...