BearChild's Blog

吊打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 ...

上帝与集合的正确用法 Time Limit: 5 Sec Memory Limit: 128 MB Description Input 第一行一个T，接下来T行，每行一个正整数p，代表你需要取模的值。 Output T行，每行一个正整数，为答案对p取模后的值。 Sample Input 3 　2 　3 　6 Sample Output 0 　1 　4 HINT 对于100%的数据，T<=1000，p<=10^7 Solution 我们运用欧拉定理： 然后还有一个定理：一个数在执行log次操作后，值不会改变。 然后就可以直接求了。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE ...

Tree Time Limit: 10 Sec Memory Limit: 64 MB Description 给你一棵TREE，以及这棵树上边的距离，问有多少对点它们两者间的距离小于等于K。 Input 第一行一个n，接下来n-1行边描述管道，按照题目中写的输入，接下来是一个k。 Output 仅包括一个整数，表示有多少对点之间的距离小于等于k。 Sample Input 7 　1 6 13 　6 3 9 　3 5 7 　4 1 3 　2 4 20 　4 7 2 　10 Sample Output 5 HINT n<=40000 Solution 树上路径统计问题，运用点分。 　　每次处理与重心相关的路径，发现如果直接处理两点之间比较困难，我们想到了将所有点加入一个数组，用指针判断加起来<=K的个数，这样的话不一定全是简单路径，但是我们只要减去每个子树中这样操作的条数就一定只剩下简单路径了。 　　点分大概的步骤： 　　1.找出重心； 　　2.计算经过该重心的路径相关需要求的； 　　3.去掉重心对于每棵子树继续做以上过程。 Code 12345678910111213141 ...