《下载试题小区划分》由会员分享，可在线阅读，更多相关《下载试题小区划分（39页珍藏版）》请在金锄头文库上搜索。
1、小区划分一条街道的两侧各连续坐落着NN座单元楼。现在要为这些单元楼划分居民校区。规则如下：1.每个小区只能由同一侧连续的若干座单元楼组成。且两侧都恰有KK个小区（每个小区至少有一栋楼）。2.3.两侧的小区划分规则应该相同，比如，若左边的房子被分成1,2,31,2,3这两个小区，那么右边也应该如此。4.这样两边合计一共有KK对小区。用a_i,b_iai,bi表示左右两边每座楼的人口在同侧所有单元楼总人口中所占的百分比，定义一个小区的相对拥挤程度为其人口百分比之和（左边就是对应a_iai的和，右边是对应b_ibi的和)。定义这条街道的总拥挤程度为左右两边KK对小区的相对拥挤程度之差的绝对值之和。现
2、在，请你求出可能的最大拥挤程度。输入格式第一行两个整数NN和kk。第二行NN个实数，第ii个数为a_iai。第三行NN个实数，第ii个数位b_ibi。输出格式一个实数，表示这条街道的最大相对拥挤程度，保留到小数点后六位。数据范围与约定对于30%30%的数据：n le 20n20。对于100%100%的数据：n le 800,k le 80,k le nn800,k80,kn。保证sum a_i=1, sum b_i=1ai=1,bi=1。样例解释11号楼一个小区，(2,3)(2,3)号楼11个小区。这样相对拥挤程度最大为abs(0.1 - 0.4) + abs(0.75 + 0.15 - (0
3、.3 + 0.3)=0.6abs(0.10.4)+abs(0.75+0.15(0.3+0.3)=0.6。样例输入3 20.1 0.75 0.150.4 0.3 0.3样例输出0.600000题目来源2017 NOIP 提高组模拟赛（三）Day2直线的交点伦伦刚刚在高中学习了解析几何，学会了计算两条直线的交点。这天，老师给她布置了一道作业。在平面上有nn条直线，他们之间有若干交点。给定一对平板（两条平行的直线），问这有多少对直线，他们的交点在这一对平板之间（注意 (i, j) 和 (j, i) 只算一对）。输入格式第一行三个整数k,a,bk,a,b表示平板的两条平行直线的方程为y=kx+ay=k
4、x+a和y=kx+by=kx+b，保证abab。第二行一个整数nn。接下来nn行每行两个整数k_i,b_iki,bi表示第ii条直线的方程y=k_ix+b_iy=kix+bi。输出格式一个整数，表示有多少对直线，他们的交点在平板之间。数据范围与约定对于30%30%的数据，nle 5000n5000。对于100%100%的数据，n le 100000n100000。为了简单起见，输入数据保证，没有直线和平板平行，没有两条直线的交点在平板上。样例解释只有y=-x+10y=x+10这条直线和y=x,y=2x,y=-2xy=x,y=2x,y=2x这三条直线的交点在区域内。样例输入0 3 5051 02
5、 0-1 0-2 0-1 10样例输出3题目来源2017 NOIP 提高组模拟赛（三）Day2数三角形刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图GG，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说，GG中每有一个三边颜色都互不同的三角形（异色三角形）可以得33分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉66分，其它三角形不得分也不扣分。现在，请你写一个程序来计算GG的多样性分数。输入格式第一行两个正整数nn和mm，其中n
6、n表示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 fracn(n-1)2n500,m2n(n1)。对于40%40%的数据，n le 2000,m le fracn(n-1)2n2000,m2n(n1)。对于100%100%的数据，n le 100000, m le min(fracn(n-1)2,200000)n100000,mmin(2n(n1)
7、,200000)。样例解释 1(1, 2, 3)(1,2,3)能组成一个同色三角形，找不到异色三角形，得分为-66。样例解释 2(1, 2, 3)(1,2,3)能组成一个同色三角形，(1,2,4),(1,3,4)(1,2,4),(1,3,4)能组成两个异色三角形，得分为2*3-6=0236=0。样例输入14 31 2 11 3 12 3 1样例输出1-6样例输入24 41 2 11 3 12 3 11 4 2样例输出20题目来源2017 NOIP 提高组模拟赛（三）Day2火山喷发火山喷发对所有附近的生物具有毁灭性的影响。在本题中，我们希望用数值来模拟这一过程。在环境里有nn个生物分别具有A_
8、1,A_2,cdots,A_nA1,A2,An点生命值，一次火山喷发总计MM轮，每轮造成11点伤害，等概率地分给所有存活的生物，即如果目前有KK个活着的生物，每个生物受到这点伤害的概率是frac1KK1。如果一个生物的生命值减为00，它会立即死去，此后都不会再占用受到伤害的概率。如果没有生物存活，那么将没有生物会受到伤害。现在你的任务是，给定n,Mn,M和全部生物的生命值，问每个生物火山喷发后依然存活的概率。输入格式第一行两个正整数nn和MM。第二行nn个正整数A_1,.,A_nA1,.,An。输出格式nn行，第ii行一个数表示第ii个生物存活下来的概率，保留小数点后六位。数据范围与约定对于1
9、0%10%的数据N=1N=1。对于30%30%的数据N=2N=2。对于全部数据N le 4N4，M le 120,A_ile50M120,Ai50。样例输入11 21样例输出10.000000样例输入23 152 12 2样例输出20.0016840.9966320.001684题目来源2017 NOIP 提高组模拟赛（三）Day1信息传递一个数据包在一个无向网络中传递。在时刻00，该数据包将依照特定的概率随机抵达网络中的某个节点。网络可以看做一张完全带权无向图，包含NN个节点，若tt时刻数据包在节点ii，则在t+1t+1时刻，数据包被传递到节点jj的概率是displaystyle fracd
10、(i,j)displaystyle sum_k ne id(i,k)kid(i,k)d(i,j)其中d(i,j)d(i,j)表示节点ii到节点jj的最短路径的长度。在传递到下一个节点后，该数据包会自动删除在当前节点的备份。现在，给定数据包00时刻在每个节点的概率和网络的每条边权。求TT时刻数据包在每个节点的概率。输入格式第一行两个整数NN和TT。第二行NN个实数，表示00时刻数据包在每个节点的概率（保证概率加起来为11）。接下来NN行每行NN个整数，第ii行第jj个数表示节点ii和节点jj之间的边权。保证第ii行第ii个数为00且第ii行第jj个数等于第jj行第ii个数。输出格式输出共NN行，
11、第ii行表示TT时刻数据包在节点ii的概率，保留六位小数。数据范围与约定对于50%50%的数据，T le 20T20。对于100%100%的数据，N le 200,T le 109N200,T109。保证对于每个点dd的和值在 int 范围。样例输入3 20 1 00 1 41 0 24 2 0样例输出0.4000000.3500000.250000题目来源2017 NOIP 提高组模拟赛（三）Day1任性的国王X 国的地图可以被看作一个两行nn列的网格状图。现在 X 国需要修建铁路，然而该国的国王非常小气，他只想保证位于某两列之间的所有城市互相可以到达就行了，在此基础上，他希望所花费的代价最
12、小。铁路可以建在任何两个相邻的点之间，使他们可以互相到达。可以作为工作人员，你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。对于(i,j)(i,j)：当前情况下，使第ii列到第jj列之间的所有城市连通的最小代价是多少（列下标从11开始）？注意不能用其他列的城市。然而你还有更大的困难，随着时间变化，使用某些边作为铁路的代价会发生改变，你必须有效率地处理这些变化。输入格式第一行两个正整数n,mn,m，表示该国有22行nn列以及mm个询问或者操作。第二行3n-23n2个数，前n-1n1个数依次表示在第一行的n-1n1条边上修建铁路的代价。接下来n-1n1个数，
13、依次表示在第二行的n-1n1条边上修建铁路的代价。最后nn个数，依次表示在第11列到第nn列的边上修建铁路的代价。接下来mm行的输入具有如下形式，K,S,TK,S,T，其中1.若K=1K=1，则表示询问当前状态下，使所有第SS列到第TT列之间的城市连通需要的最小代价。2.3.若K=2K=2，则表示位于第11行第SS列的点到第11行第S+1S+1列的点之间的边上修建铁路的代价变为TT。4.5.若K=3K=3，则表示位于第22行第SS列的点和第22行第S+1S+1列的点之间的边上修建铁路的代价变为TT。6.7.若K=4K=4，则表示第SS列的边上修建铁路的代价变为TT。8.输出格式依次对每个询问，用一行输出相应的答案。数据范围与约定对于30%30%的数据：n,mle 2000n,m2000。另有30%30%的数据：所有竖边的代价为00且永不改变。对于全部数据：n,m le 105n,m105。所有输入和输出数据保证合法，且不超过231-12311。样例输入4 142 3 4 3 1 1 1 5 4 71 1 21 2 31 1 31 2 42 1 51 1 44 2 11 1 31 2
