基德KID.1412
- 浏览: 309546 次
- 性别:
- 来自: 珠海
-
最新评论
-
xialluyouyue：
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294：
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412：
su1216 写道竖线代表或者，不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216：
竖线代表或者，不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu：
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
文章列表
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2648
题意很简单，不解释，用map暴力也可以，但是要1000ms左右，或者更慢
引用：各种字符串Hash函数比较
其中我用的是BKDR Hash：
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
...
KIDx 的解题报告 题目链接：http://codeforces.com/contest/136以下省略头文件
前三题是超级水题，不解释；后两题是很不错的水题，详细解释
A题
#include <iostream>
using namespace std;
#define M 105
int pre[M];
int main()
{
int n, i, x;
while (~scanf ("%d", &n))
{
for (i = 1; i <= n; i++)
scanf ("% ...
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2241
解题思路：
由题意得：【设题目所给m个点存放到点结构p[m]中】
F = n/(x^2)
设Y是第i-1个点跟第i个点连线的方程【设k是这2点连线的斜率】
则：【根据题目：i<j Xi<Xj 且 Yi<=Yj】
Y = k * (x-p[i-1].x) + p[i-1].y
设总的函数 = Z
则Z = Y + F = n/(x^2) + k * (x-p[i-1].x) + p[i-1].y
即：Z = n/(x^2) + k*x + (p[i- ...
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2141
题意很简单
很好的一道二分+降维思想的题！
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define PI 3.14159265
#define POW2(x) x*x
#define POW3(x) x*x*x
#define POW4(x) x*x*x*x
int a[505], b[505], c[5 ...
KIDx 的解题报告
题目链接：http://codeforces.com/contest/133
以下省略头文件，前三题是水题，不解释
A题
#define M 105
char s[M];
int main()
{
bool flag;
int i, len;
while (gets (s))
{
flag = false;
len = strlen (s);
for (i = 0; i < len; i++)
if (s[i] == 'H' || s[i] == 'Q' || s[i] == '9')
{
fla ...
KIDx 的解题报告
题意很简单：http://acm.hdu.edu.cn/showproblem.php?pid=2579
#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 105
int r, c, mod, step[11][M][M]; //step加维枚举余数所有状态
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
char ma ...
KIDx 的解题报告
参考《算法艺术与信息学竞赛》：
题目：http://acm.fzu.edu.cn/problem.php?pid=1752
由于(1<=A,B,C<2^63)，所以要用到mul_mod二分求a*a，不然会溢出
原来的快速幂取模简单模板：
//求(a^b)%c
int qmod (int a, int b, int c)
{
int res = 1;
for ( ; b; b >>= 1)
{
if (b & 1)
res = (LL)res * a % c;
a = (LL)a * a % c; ...
KIDx 的解题报告
题目很容易看懂：http://acm.hdu.edu.cn/showproblem.php?pid=3609
降幂公式：
这速度可以排到前10了：
#include <iostream>
using namespace std;
#define LL unsigned __int64
#define M 205
int phi[M];
int Euler (int n) //求n的欧拉值
{
int i, res = n;
for (i = 2; i * i <= n; i++)
{
if (n % i ...
KIDx 的解题报告
该专题必备知识：解模线性方程
http://972169909-qq-com.iteye.com/blog/1104538
以下原创
转载请指明作者 (KIDx) 以及 文章地址：
http://972169909-qq-com.iteye.com/blog/1266328
问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？
解：采用的是合并方程的做法。
这里将以合并第一第二个方程为例进行说明
由上图前2个方程得(设k1、k2为某一整数)：
例题： hdu 1573 X问题 【下面已给出代码】
http://ac ...
KIDx 的解题报告
http://acm.fzu.edu.cn/problem.php?pid=1607
题意：求n平均分成m份(m>1)，问有多少种分法，以及平均的分量最多可以达到多少？
多少种分法：
求n的因子的组合数即可，由于m>1所以【所有因子取0个的情况不包括】
例如：n中有3个素因子p1,2个素因子p2，p1可以取0个，1个，2个，3个【4种情况】，p2可以取0个，1个，2个【3种情况】，所以分法 = 4*3-1 = 11
平均达到最大值：
n/(n的最小素因子)
#include <iostream>
using namespace std;
...
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4082
当时比赛提交第十六次过了
注意点：
①判定三角形合法性
②理解好题意：多个相同的点只算一个
③数组大小开足够大
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define EP 1e-8
struct point{ //点
double x, y;
}p[20];
struc ...
KIDx 的解题报告
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行，为什么等于不能随便剪掉
如果剪掉就会出现下图结果：
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的，由于最多转一次弯，所以不合题意；
蓝色是后搜的，因为遇到转弯数相等所以不往下走了了，但是继续走是可以满足题意输出"yes"的
深搜：
#include <iostream>
using namespace std;
#define inf 0x3ff ...
KIDx 的解题报告
http://codeforces.com/contest/4
以下省略头文件
A题
非一般的水
int main()
{
int x;
while (~scanf ("%d", &x))
{
if ((x & 1) || x == 2)
puts ("NO");
else puts ("YES");
}
return 0;
}
B题
题意：输入n和sum，再输入n个闭区间，每个区间找一个数，使得这些数的和等于sum，能找出输出"Y ...
KIDx 的解题报告
题目链接：http://poj.org/problem?id=2142
不懂扩展欧几里得请先参照这里：
http://972169909-qq-com.iteye.com/blog/1140914
题意：输入3个数，前2个是砝码的种类，问各要多少个才能称出第三个数出来【同时要使2个答案之和最小】
#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define LL __int64
LL gcd (LL a, LL b) ...
KIDx 的解题报告
http://codeforces.com/contest/1
以下省略头文件
A题
水题
int main()
{
LL n, m, a, res;
while (~scanf ("%I64d%I64d%I64d", &n, &m, &a))
{
res = ((n+a-1) / a) * ((m+a-1) / a);
printf ("%I64d\n", res);
}
return 0;
}
B题
题意：在Excel中，一个格子的位置有2种表示：
例如第 ...