计算几何 题意 一片真心醉红尘，两处人间皆相印。 随着时间的推移，两人的感情越发深厚，心心相印，默契非凡。但是，作为一个理科生，LFgg想要一个能够量化的模型，来测试两人的默契程度。这天，LFgg请来了他的NPY，邀请她做一个测试。两人同时报出坐标系中的两点，过NPY的两点做一条线段，同时以LFgg报出的两点做一个矩形，看它们是否存在公共点。矩形范围包括四条边及内部的所有点。LFgg和NPY记录了很多次数据（多次测量减小误差），筋疲力尽的LFgg已经难以去判断是否有公共点了，所以他将这个问题交给了你。 Input第一行包含一个整数n，代表数据组数。接下来每一行包含八个整数 x_start,y_...

递归、分治、排序、字典树 题意： 恋爱让人迷醉，却也让人苦恼。LFgg恋爱了，棉花糖般甜蜜。LFgg每天花13个小时与NPY聊天，直到期中考试，LFgg考了68分为止。LFgg终于醒悟过来，他花在聊天上的时间太多了，可是他又不愿意把NPY晾在一边。所以，LFgg决定学会时间管理，在聊天的间隙学习。为此，他决定好好***自己的输入法。 “前缀”是指一个从开头开始的字串，例如：“LOVE”的所有前缀是“L”，“LO”，“LOV”，“LOVE”。空字符串不被认为是一个前缀。LFgg希望他能只用前缀，就能唯一确定一个完整的单词，这样就能大大缩短打字所需的时间。为此，他决定交给你一个任务，给你LFgg的...

bfs、图 题意： 在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1．路径上的所有点的出边所指向的点都直接或间接与终点连通。2．在满足条件1的情况下使路径最短。注意：图G中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。输入描述:第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。输出描述:输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。...

bfs 题意 小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。 一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传...

题意 定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。比如说，47、744、4都是幸运数字而5、17、467都不是。定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。输入描述:两个整数l和r (1 <= l <= r <= 1000,000,000)。输出描述:一个数字表示答案。 并不难因为被坑了所以就记录下来，做个教训//期末考试终于考完，放暑假了，写个题解以表庆祝！！！！！！ 分析 首先这题，我们可一很容易的想到打表。把可能会用到的所有幸运数字打...

并查集 题意： 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。请问至少需要加多少个点，使得点对之间互相可以到达。输入描述:第一行一个整数n表示点数（ 1 <= n <= 100)。第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。y轴正方向为北，x轴正方形为东。输出描述:输出一个整数表示最少需要加的点的数目。 分析 这题就是考察并查集的。首先我们如果直接从上下左右去判断一个点他能连接的点，不断地进行搜索的话，是比较麻烦的。这里我们不妨这样做，我们先单看x轴和y轴。如果两个点x坐标...

并查集、01背包 题意： 小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段，当然人际关系是需要放在首位的。 小d每一个月都需要列出来一个人际关系表，表示他们搞房地产的人的一个人际关系网，但是他的精力有限，对应他只能和能够接触到的人交际。比如1认识2,2认识3，那么1就可以接触3进行交际，当然1和2也可以交际。 小d还很精明，他知道他和谁交际的深获得的利益大，接下来他根据自己的想法又列出来一个利益表，表示他和这些人交际需要耗用多少精力，能够获得的利益值为多少。 小d想知道，他在精力范围内，能够获得的利益值到底是多少。 设定小d自己的编号为1.并且对应一个人的交际次数限定为1. 输入描述:...

思维，递归 题意： Cgg特别喜欢收集特别的字符串。这天，lfgg给了cgg两个字符串，字符串A，字符串B，声称这是一对神奇的字符串，他们满足如下两个条件的其中之一：1、 A与B相等。2、 如果我们把字符串A分成两个长度相等的字符串A1,A2，并将字符串B分成两个长度相等的字符串B1,B2 然后他们满足以下的其中一项条件：（1） A1与B1是一对神奇的字符串，并且A2与B2是一对神奇的字符串。（2） A2与B1是一对神奇的字符串，并且A1与B2是一对神奇的字符串。Lfgg确信他找到了一对神奇字符串，cgg却并不相信。希望你能帮帮cgg判断，这对字符串是否是一对神奇字符串。 Input一共两行，...

二分，递归，分治！！！ 题意 集训队内的氛围是相当和谐的，如果某个问题上双方产生了争执会通过智力或是武力来解决问题。 集训队内的每个人有各自的武力值和智力值，如果一个队员x的智力值和武力值均大于等于另一个队员y，则x与y的争执中x必定获胜（保证没有两个人武力值和智力值均相同） 队长想知道队内有多少队员能恰好在争执中击败一个其他队员，又有多少队员能恰好在争执中击败两个其他队员，又有多少队员能恰好在争执中击败三个其他队员。。。。由于每个数都问一遍太麻烦了，你只需要对0-（N-1）的每一个数都输出一遍就好啦输入 输入的第一行包括了集训队成员的数量N (1<=N<=1500...

思维 题意 现在给你两个正整数a，b，每一次操作你可以让a = a-x ， b =b-2x 或者 a = a-2x ， b = b - x，每次操作的x为任意正整数，每***作的x可以不同，请问是否可以经过若干***作使得a，b同时为0。 分析 这题老实说刚拿到手上有点懵逼。没大有思路。其实这种题，我们应该去看她的本质。对于数a,b，我们不妨就令x == 1！！！！！这样我们就已经做出来了。假设，操作一用了k1次，操作二用了k2次那么a = k1+2k2 b = 2k1+k2求这个方程，能不能有非负整数k1,k2满足OK了 下面代码，注意细节： #include<iostream>...

思维、暴力枚举、遍历 题意: 给一个nm的网格，小明起初在左上角，每次可以向右或向下走一格，'#'代表不能走的格子，'.'代表能走的格子，问至少要把原先的几个'.'改成'#',可以使小明不能到达右下角(左上角和右下角起初都为'.',并且不能被改成'#')Input输入的第一行是两个整数n,m(3≤n⋅m≤1000000 )。 接下来n行是一个nm的矩阵； 具体含义见描述。Output输出改变的最小数目，使得whgg不能到达右下角。 分析： 首先我们可以非常明显的推断出最终答案再集合{0,1,2}内。因为，对于任何一个二维数组(n行m列)，记为a：下面数组中1代表'.'可走，2代表'#'不可走[...

数学 这一题我是列出一些例子后归纳猜出来的，，，，，，如果要证明的话，就我个人来说感觉还是有、难度的。下面给出我的证明，并不严谨。 题意：给定一个正整数n，请求出所有满足如下两个条件的正整数集合x[1],x[2]...x[n]:  x[1]+x[2]+...+x[n]=2n 不存在一个划分将集合划分成和相等的两部分，也就是说，集合的任意子集和均不为n。请按照集合中元素升序排序后字典序从小到大的顺序输出答案，若不存在这样的集合请不要输出任何字符  分析 我们先拿一些具体的例子试一试吧，看能不能找到突破口。n == 1 :[2]n == 2 :[1,3]n == 3 :[1,1,4] 、[2,2,...

思维 题意：大司马的重要理论成果之一即所谓正方形打野，本题恰好与正方形相关。大司马的家的地板可以看成有n×m个格子的矩形。现在他需要用一些颜色的瓷砖来铺满这个房间，每种颜色的瓷砖摆放数量不受限制，但不能在同一个格子上覆盖多块瓷砖，更不能有空格子。所有的瓷砖都是正方形的，然而这些瓷砖的边长却不一定相等，如:1×1的瓷砖可以覆盖一个格子，2×2的瓷砖可以覆盖4个格子。每一种不同的瓷砖的颜色分别为大写字母A,B,C,D,E等以此类推，本题数据保证所需颜色不会超过26种。大司马是一个有强迫症的人，他不能忍受地板上出现一个非正方形的色块，即所有同色连通块必须为正方形，这里的连通指上下左右四连通。当大司马...

单源最短路径、三分、思维 今天的我又被狠狠地教训了。。。。嘿嘿。。这道题再次告诉我细心是件多么重要的事情！！！！ 题意:安徽芜湖有n个机场，一共有m条线路在空管部门报备。每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。具体来说，设目前是第x天，那么第i条线路所需要的通行时间为k*x+b一年一共有H天，也就是说，x取[0,H]中的整数。现在大司马想从1号机场在一天内换乘任意多次航班前往n号机场，他总是选择用时最短的方式，现在他想知道哪一天需要花最长的时间。 输入格式：每个测试点仅包含一组输入数据。第一行三个整数n,m,H(1<=n,m<=114514,1<=H&l...