BearChild's Blog

异色弧 Time Limit: 20 Sec Memory Limit: 256 MB Description Input Output 仅一行一个整数表示答案。 Sample Input 8 　　1 2 3 1 2 3 2 1 Sample Output 8 HINT Main idea 给定若干个点，每个点有一个颜色，颜色一样的可以组成一个区间，询问有几个交。 Solution BearChild只会70分的做法，记录N表示区间个数，效率为O(Nlog(N))。这里介绍一下。 我们基于将所有区间提取出来计算，可以用一个vector存一下记录相同颜色的，然后相同颜色的任意组合即可组成可行的区间。 首先我们考虑容斥：颜色不同的相交个数 = 不考虑颜色的总相交个数 - 颜色相同的相交个数。然后我们分段来解： 1. 不考虑颜色的总相交个数： 　　　　我们考虑带log的算法，先将所有区间按照右端点（细节：若相同则将左端点大的放在前面，保证不会算入答案）排序，然后顺序往后做，每次用树状数组在区间左端点+1，区间(右端点-1)处-1（细节：右端点-1处是为了处理前一个的右端点=这一个的左端 ...

开锁 Time Limit: 10 Sec Memory Limit: 256 MB Description A君有n个盒子，每个盒子被一把锁锁着，每个盒子内都有一把钥匙。 对于每个盒子而言有且仅有一把钥匙能打开锁着它的锁，而打开它后便能拿着放置在这个盒子内的钥匙去开启其他盒子。 现在A君打算随机选择k个盒子并用魔法将它们打开，并用所得到的钥匙去尝试开启其他所有的盒子(开启一个盒子后，新得到的钥匙还能继续尝试使用)。 A君想知道：最终他能打开所有盒子的概率是多少，请你帮助他。 Input Output Sample Input 4 　　5 1 　　2 5 4 3 1 　　5 2 　　2 5 4 3 1 　　5 3 　　2 5 4 3 1 　　5 4 　　2 5 4 3 1 Sample Output 0.000000000 　　0.600000000 　　0.900000000 　　1.000000000 HINT Main idea 一个宝箱内有一个可以开启别的宝箱的钥匙，可以选择k个宝箱，询问能开启所有宝箱的概率。 Solution 我们一看就知道这是一道概率DP的题目。 我 ...

吊打XXX Time Limit: 10 Sec Memory Limit: 128 MB Description gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。 　　gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。 　　蒟蒻们将n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。 　　吊好gty后蒟蒻们发现由于每个gty重力不同，绳结x在移动。 　　蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 　　不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。 Input 输入第一行为一个正整数n，表示gty的数目。 　　接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。 　　对于20%的数据，gty排列成一条直线。 Output 输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。 Sample Input 3 　0 0 1 　0 2 1 　1 1 1 Sample Output 0.577 1.000 HINT 对于50%的数据，1<=n&l ...

宅男小C Time Limit: 10 Sec Memory Limit: 256 MB Description 众所周知，小C是个宅男，所以他的每天的食物要靠外卖来解决。小C现在有M元钱，他想知道这些钱他最多可以吃多少天。 餐厅提供N种食物，每种食物有两个属性，单价Pi和保质期Si，表示小C需要花Pi元才能买到足够一天吃的这种食物，并且需要在送到Si天内吃完，否则食物会变质，就不能吃了，若Si为0则意味着必须在送到当天吃完。另外，每次送餐需要额外F元送餐费。 Input 每个测试点包含多组测试数据； 每个测试数据第一行三个整数M,F,N，如题目描述中所述； 以下N行，每行两个整数，分别表示Pi和*Si。* Output 对于每个测试数据输出一行，表示最多可以吃的天数。 Sample Input 32 5 2 　5 0 　10 2 　10 10 1 　10 10 　10 1 1 　1 5 Sample Output 3 　　0 　　8 HINT 对于40%的数据，M,Si <= 2*10^6； 　对于100%的数据，1 ≤ N ≤ 200，M, Si<= 10^18，1 ≤ ...

咏叹 Time Limit: 100 Sec Memory Limit: 256 MB Description 有n根木棍，第i根长度为ai。你要贴着墙围出一个矩形区域，木棍围成的矩形边缘必须平行或垂直于墙，且又一边必须利用墙。你可以把至多1根木棍劈成两根(不一定要在整数位置)。最大化矩形面积。 Input 包含多组数据。每组数据第一行一个整数n，第二行n个整数ai。 Output 输出面积最大的矩形与墙壁平行的那条边的长度(显然是一个整数)，若有多个最优解输出与墙壁平行的那条边最长的。 Sample Input 3 3 3 3 4 4 4 4 4 Sample Output 6 　　8 HINT 对于10%的数据，n=2。 　　对于30%的数据，n<=15。 　　对于50%的数据，n<=32。 　　对于另外20%的数据，ai<=100。 　　对于100%的数据，2<=n<=40，1<=ai<=10^9，数据不超过10组。 Solution 首先，必然是全部木棍都用上的时候最优，对于n=2的时候，显然就是分三种情况讨论一下就好了。 然后我们从n ...

小Y的地铁 Time Limit: 50 Sec Memory Limit: 256 MB Description Input Output 对于每组输入数据，输出一行一个整数，表示除掉这 n 个换乘站之外，最少有几个换乘站。 Sample Input 4 　　4 　　1 2 1 2 　　8 　　1 2 3 4 1 2 3 4 　　5 　　5 4 3 3 5 　　8 　　1 2 3 4 1 3 2 4 Sample Output 0 　　0 　　0 　　1 HINT n <= 44 Solution 首先，答案显然只和几个区域的连通状态有关，那么我们可以写出四种本质不同的方案。（即下图中被线分开的六块）。 我们可以考虑，对于一条线，其他线（显然仅有 部分相交 与 完全相交 两种）造成的贡献。打出表来，上图是不会造成交点的线段种类。 既然知道了这个，我们的复杂度显然可以做到 O(4 ^ (n / 2))。还是不足以通过，怎么办呢？ 模拟退火大法好！ Code 12345678910111213141516171819202122232425262728293031323334 ...

瞭望塔 Time Limit: 10 Sec Memory Limit: 162 MB Description 致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。 我们将H村抽象为一维的轮廓。如下图所示 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。 瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。 可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。 为了节省开支，dadzhi村长希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。 Input 第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。 Output 仅包含一个实数，为塔的最小高度，精确到小数点后三位。 Sample Input 4 　10 20 49 59 　0 10 10 0 Sample Output 14 ...

Uria Time Limit: 20 Sec Memory Limit: 512 MB Description 从前有个正整数 n。 对于一个正整数对 (a,b)，如果满足 a + b ≤ n 且 a + b 是 a * b 的因子，则成为神奇的数对。 求神奇的数对的个数。 Input 一行一个正整数 n。 Output 一行一个整数表示答案，保证不会超过 64 位有符号整数类型的范围。 Sample Input 21 Sample Output 11 HINT n ≤ 1e14 Solution Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;typedef long long s64;typedef unsigned int u32;const int ONE = 1e7 + 5;const u32 MOD = 20000116;s ...

外星人 Time Limit: 3 Sec Memory Limit: 128 MB Description Input Output 输出test行，每行一个整数，表示答案。 Sample Input 1 　2 　2 2 　3 1 Sample Output 3 HINT Test<=50 Pi<=10^5,1<=Q1<=10^9 Main idea 给定一个数，用Πp[i]^qi的形式表示，问最少需要对这个数字x进行几次x=Φ(x)操作使得x=1。 Solution 这显然是一道数论题。 　　首先想到了只有Φ(2)=1，所以最后答案必然需要转成带2的形式，我们先考虑一个数字，由欧拉函数的推导公式Φ(Πp[i]^q[i])=Π(p[i]-1)*p[i]^(q[i]-1)可以发现每次求Φ会消去一个质因数2，并且产生若干个2（产生的2是有上限的）。 　　这句话是什么意思呢？ 　　我们举个例子：讨论一个偶数180=2^2 * 3^2 * 5，Φ(180)=2^1 * (3-1)*3 * (5-1)=48，这里产生了3个2，消去了1个2。 　　所以我们只要求出产 ...

点组计数 Time Limit: 20 Sec Memory Limit: 128 MB Description 平面上摆放着一个nm的点阵（下图所示是一个34的点阵）。Curimit想知道有多少三点组(a，b，c)满足以a，b，c三点共线。这里a，b，c是不同的3个点，其顺序无关紧要。(即(a，b，c)和(b，c，a)被认为是相同的）。由于答案很大，故你只需要输出答案对1，000，000，007的余数就可以了。 Input 有且仅有一行，两个用空格隔开的整数n和m。 Output 有且仅有一行，一个整数，表示三点组的数目对1，000，000，007的余数。（1，000。000。007是质数） Sample Input 3 4 Sample Output 2 0 HINT 对于100%的数据，1< =N．m< =50000 Main idea 给定一个点阵，问有多少组三点共线。 Solution 其实我也不知道原式怎么来的，我可能只会推式子啊？QAQ Code 123456789101112131415161718192021222324252627282930313 ...