基德KID.1412
- 浏览: 308880 次
- 性别:
- 来自: 珠海
-
最新评论
-
xialluyouyue：
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294：
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412：
su1216 写道竖线代表或者，不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216：
竖线代表或者，不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu：
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
文章列表
KIDx的解题报告
题意：给出n个点，给出R，两点距离不大于R而且两点之间没其他点阻碍，就可以建一条边，问可以形成多少棵生成树，如果没有，输出-1，否则，输出（生成树个数 mod 10007）
典型的生成树计数：
①求出 ...
KIDx的解题报告
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=106
题意：求ax + by + c = 0在[x1, x2], [y1, y2]区间内有多少组解？
KIDx的解题报告
题目链接：http://poj.org/problem?id=1091
假设卡片上标号分别是a1, a2, ..., an, M，跳蚤跳对应号的次数分别为x1, x2, ..., xn，跳M个单位长度的次数是xn+1，那么要满足已知条件只需满足方程：
a1x1+a2x2+...+anxn+Mxn+1 = 1 有解，即：
gcd (a1, a2, ..., an, M) = 1，接下来对M进行素因子分解，然后排除公因子非1的情况即可。
如代码所示：
设g为公因子非1的情况数，f(i)表示有i个公因子的情况数，由容斥原理得：g = f(1) - ...
KIDx的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4109
题意：输入点数n[编号0到n-1]和关系数，输入a，b，c，表示a操作做完后第c纳秒可以做b，问所有操作搞完至少花多长时间？
Sample Input
5 2
1 2 1
3 4 1
KIDx的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2845
题意：在图中取数，例如取了81之后，同一行的相邻两个不能取，还有81的上面那行和下面那行也不能取，问能取到的最大和是多少？
解析：对于一行来说，相邻的数不可同时取，
容易得到状态转移方程：sum[i] = max (sum[i-2]+sum[i], sum[i-1])（i>=2,注意i从1开始,i-2=0时不存在sum[i-2]相当于只取sum[i]），初始时sum[0] = 0, sum[i]就是第i个数
而对于一列来说，显然的也是相邻的不 ...
KIDx的解题报告
好久没写博客了，来题数学提提神
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1719
题意：
①1,2都是friend数
②如果a，b都是friend数，那么ab+a+b也是friend数
任务：判断一个数n是不是friend数 (0<=n<=2^30)
设a, b都是friend数，
那么可以生成一个friend数 x = ab+a+b = (a+1)(b+1)-1
设c, d都是friend数，
那么可以生成一个friend数 y = (c+1)(d+1)-1
由x，y ...
KIDx的解题报告
题意：求n个数的最小公倍数，结果很大，得用高精度
题目链接：http://lightoj.com/volume_showproblem.php?problem=1024
找出每个数的素因子p，p必为最小公倍数的因子，最小公倍数中p的个数就是每个数的p的个数的最大值，最后，最小公倍数的因子及其个数都知道了，用高精度乘起来就是结果了，我这里用的是10000进制计算
#include <iostream>
#include <fstream>
#include <algorithm>
#inclu ...
KIDx的解题报告
题目链接：http://lightoj.com/volume_showproblem.php?problem=1164
题意：区间内初始时全部为0
命令1：0 x y v； 从x到y全部+v
命令2：1 x y； 输出x到y的值的总和
典型lazy的应用
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map> ...
KIDx的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027
加了输入外挂之后，排第二，还不错！
下面的代码没加外挂，运行时间是：375ms，还可以
#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define Max 26
#define LL __int64
struct Node{
int l, r;
LL ...
KIDx的解题报告
进入USACO要注册才能看题: http://train.usaco.org/usacogate 题目：【翻译版、是别处的网站】
http://www.wzoi.org/usaco/11%5C304.asp
/*
ID: 1006100071
LANG: C++
TASK: barn1
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define M 205
int a[M];
struct point{
int d, i ...
KIDx的解题报告
进入USACO要注册才能看题: http://train.usaco.org/usacogate 题目：【翻译版、是别处的网站】http://www.wzoi.org/usaco/12%5C211.asp SAMPLE INPUT (file milk2.in) 3 300 1000 700 1200 1500 2100 SAMPLE OUTPUT (file milk2.out) 900 300
/*
ID: 1006100071
LANG: C++
TASK: milk2
*/
#include <iostream>
#include & ...
KIDx 的解题报告
题目链接：http://lightoj.com/volume_showproblem.php?problem=1170
题意：给a, b (1 <= a <= b <= 10^10)，设a，b之间有n个完全数[x>1,y>1，使得m=x^y，则m为完全数]，用这n个数作为结点，求这n个结点能形成多少种二叉树？
预处理：
i=1~10^5生成所有m放到dp[M]数组，然后从小到大排序，再去重复放到x[M]数组
卡特兰数：
生成后发现最多有d=10万多个完全数，那么只要生成n<=d个卡特兰数列存到ans[M]数组 ...
KIDx 的解题报告
题目链接：http://lightoj.com/volume_showproblem.php?problem=1048
题意：给n+1个数，要你通过合并使其变成k+1个数，要求令这k+1个数的最大值最小，另外输出时尽量让前面的大
#include <iostream>
using namespace std;
#define M 1005
int n, a[M], k;
bool judge (int key) //暴力检验
{
int i = 0, num = 0;
while (i < n)
{
...
KIDx的解题报告
题目链接：http://lightoj.com/volume_showproblem.php?problem=1174
题意：无限支军队从起点出发，最少要多长时间路过所有城市并且到达终点？
利用folyd 插点法的思想即可解决
找到dist[s][i] + dist[i][t]的最大值即为所求最小值
#include <iostream>
using namespace std;
#define M 105
#define inf 0x3fffffff
int dist[M][M], n;
void init ...
KIDx 的解题报告
题目链接：http://lightoj.com/volume_showproblem.php?problem=1088
题意：给一串单调递增的数，输入x, y，问>=x且<=y的数有多少个？
二分要点：设初始下界为l，上界为r 二分进行条件：while (l < r)
①要找单调区间中尽量小的符合条件的量，则mid的可达范围应该是右开区间[l, r)；
若符合，令r = mid；否则令l = mid + 1推进，因此mid = (l+r) / 2，这是导致区间右开的根本原因
r 即为二分结果
②要找单调区间中尽量大的符合条 ...