下载的试题 小区划分.doc

小区划分 一条街道的两侧各连续坐落着?NN?座单元楼。现在要为这些单元楼划分居民校区。 规则如下： 每个小区只能由同一侧连续的若干座单元楼组成。且两侧都恰有?KK?个小区（每个小区至少有一栋楼）。 两侧的小区划分规则应该相同，比如，若左边的房子被分成?\{1,2\},\{3\}{1,2},{3}?这两个小区，那么右边也应该如此。 这样两边合计一共有?KK?对小区。 用?a_i,b_ia?i??,b?i???表示左右两边每座楼的人口在同侧所有单元楼总人口中所占的百分比，定义一个小区的相对拥挤程度为其人口百分比之和（左边就是对应?a_ia?i???的和，右边是对应?b_ib?i???的和)。定义这条街道的总拥挤程度为左右两边?KK?对小区的相对拥挤程度之差的绝对值之和。 现在，请你求出可能的最大拥挤程度。 输入格式 第一行两个整数?NN?和?kk。 第二行?NN?个实数，第?ii?个数为?a_ia?i??。 第三行?NN?个实数，第?ii?个数位?b_ib?i??。 输出格式 一个实数，表示这条街道的最大相对拥挤程度，保留到小数点后六位。 数据范围与约定 对于?30\%30%?的数据：n \le 20n≤20。 对于?100\%100%?的数据：n \le 800,k \le 80,k \le nn≤800,k≤80,k≤n。 保证?\sum a_i=1, \sum b_i=1∑a?i??=1,∑b?i??=1。 样例解释 11?号楼一个小区，(2,3)(2,3)?号楼?11?个小区。 这样相对拥挤程度最大为?abs(0.1 - 0.4) + abs(0.75 + 0.15 - (0.3 + 0.3))=0.6abs(0.1?0.4)+abs(0.75+0.15?(0.3+0.3))=0.6。 样例输入 3 2 0.1 0.75 0.15 0.4 0.3 0.3 样例输出 0.600000 题目来源2017 NOIP 提高组模拟赛（三）Day2 直线的交点 伦伦刚刚在高中学习了解析几何，学会了计算两条直线的交点。这天，老师给她布置了一道作业。在平面上有?nn条直线，他们之间有若干交点。给定一对平板（两条平行的直线），问这有多少对直线，他们的交点在这一对平板之间（注意 (i, j) 和 (j, i) 只算一对）。 输入格式 第一行三个整数?k,a,bk,a,b?表示平板的两条平行直线的方程为?y=kx+ay=kx+a?和?y=kx+by=kx+b，保证?abab。 第二行一个整数?nn。 接下来?nn?行每行两个整数?k_i,b_ik?i??,b?i???表示第?ii?条直线的方程?y=k_ix+b_iy=k?i??x+b?i??。 输出格式 一个整数，表示有多少对直线，他们的交点在平板之间。 数据范围与约定 对于?30\%30%?的数据，n\le 5000n≤5000。 对于?100\%100%?的数据，n \le 100000n≤100000。 为了简单起见，输入数据保证，没有直线和平板平行，没有两条直线的交点在平板上。 样例解释 只有?y=-x+10y=?x+10?这条直线和?y=x,y=2x,y=-2xy=x,y=2x,y=?2x?这三条直线的交点在区域内。 样例输入 0 3 50 5 1 0 2 0 -1 0 -2 0 -1 10 样例输出 3 题目来源2017 NOIP 提高组模拟赛（三）Day2 数三角形 刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图?GG，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说，GG?中每有一个三边颜色都互不同的三角形（异色三角形）可以得?33?分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉?66?分，其它三角形不得分也不扣分。 现在，请你写一个程序来计算?GG?的多样性分数。 输入格式 第一行两个正整数?nn?和?mm，其中?nn?表示?GG?中顶点的个数，mm?表示?GG?中红色或者绿色的边的条数。 接下来?mm?行每行包括三个整数?a,b,ca,b,c，代表连接顶点?aa?和顶点?bb?的边颜色为红色?(c=1)(c=1)?或者绿色?(c=2)(c=2)。 输出格式 一行，GG?的多样性得分。 数据范围与约定 对于?20\%20%?的数据，n \le 500,m \le \frac{n(n-1)}{2}n≤500,m≤?2??n(n?1)??。 对于?40\%40%?的数据，n \le 2000,m \le \frac{n(n-1)}{2}n≤2000,m≤?2??n(n?1)??。 对于?100\%100%?的数据，