- 浏览: 307470 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://acm.hdu.edu.cn/showproblem.php?pid=3818
Sample Input
2
1 2
2 2 4
3 2 4 6
2 2 5
Sample Output
Case 1:
1 5 //答案的第一个数表示后面跟多少个数
Case 2:
2 5 7
题意:每2行的数用输入斐波那契的表示法,例如上面第一个案例,总和就是sum=f(2)+f(2)+f(4)【第一行:2,第二行:2 4】
要求输出sum的斐波那契表示法,sum=f(2)+f(2)+f(4)=f(0)+f(1)+f(2)+f(4)=f(3)+f(4)=f(5),所以答案是1个数,就是5
再仔细观察,找规律:
①显然地:当b-a==1时,f(a)+f(b)=f(b+1),当a-b=1时,f(b)+f(a)=f(a+1)
②当a == b时,f(a) + f(b) = f(a-2) + f(a+1);
证明:
f(a) = f(a-2) + f(a-1);
又因为:f(b) = f(a);
所以f(a)+f(b)=f(a-2)+f(a-1)+f(a)=f(a-2)+f(a+1);
Sample Input
2
1 2
2 2 4
3 2 4 6
2 2 5
Sample Output
Case 1:
1 5 //答案的第一个数表示后面跟多少个数
Case 2:
2 5 7
题意:每2行的数用输入斐波那契的表示法,例如上面第一个案例,总和就是sum=f(2)+f(2)+f(4)【第一行:2,第二行:2 4】
要求输出sum的斐波那契表示法,sum=f(2)+f(2)+f(4)=f(0)+f(1)+f(2)+f(4)=f(3)+f(4)=f(5),所以答案是1个数,就是5
再仔细观察,找规律:
①显然地:当b-a==1时,f(a)+f(b)=f(b+1),当a-b=1时,f(b)+f(a)=f(a+1)
②当a == b时,f(a) + f(b) = f(a-2) + f(a+1);
证明:
f(a) = f(a-2) + f(a-1);
又因为:f(b) = f(a);
所以f(a)+f(b)=f(a-2)+f(a-1)+f(a)=f(a-2)+f(a+1);
#include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> //#include <map> #include <queue> #include <utility> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; #define inf 10000000 //定义无穷大 int ans[405]; int main() { int t, n, i, x, tt, ind, k = 1, j; bool flag; scanf ("%d", &t); while (t--) { tt = 2, ind = 0; while (tt--) { scanf ("%d", &n); for (i = 0; i < n; i++) { scanf ("%d", &x); ans[ind++] = x; //2行输入加入到数组ans } } sort (ans, ans+ind); flag = true; while (flag) //不存在可以合并的2个数则跳出 { flag = false; for (i = 0; i < ind - 1; i++) { if (ans[i] == inf) continue; for (j = i + 1; j < ind; j++) { if (ans[j] == inf) break; if (abs (ans[j] - ans[i]) > 1) continue; if (!flag) //说明存在2个数,他们的差绝对值<=1,即可以合并 flag = true; if (ans[j] - ans[i] == 1) //当b-a==1时,f(a)+f(b)=f(b+1) { ans[ind++] = ans[j] + 1; //生成"f(b+1)" ans[i] = ans[j] = inf;//把f(a)和f(b)变成无穷大,排序时就可以刷下去了 } else if (ans[i] - ans[j] == 1)//当a-b=1时,f(b)+f(a)=f(a+1),同理 { ans[ind++] = ans[i] + 1; ans[i] = ans[j] = inf; } else if (ans[i] == ans[j])//当a == b时,f(a) + f(b) = f(a-2) + f(a+1) { ans[ind++] = ans[i] - 2; //生成2个 ans[ind++] = ans[i] + 1; ans[i] = ans[j] = inf;//相当于删除f(a)和f(b),实现合并操作 } } } sort (ans, ans+ind); //排序,把无穷大刷下去 /*for (i = 0; i < ind; i++) cout << ans[i] << ' '; cout << "\n";*/ } printf ("Case %d:\n", k++); int num = 0; for (i = 0; i < ind; i++) { if (ans[i] == inf) //由于已排序,一旦扫描到无穷大,后面肯定没有合法的数 break; if (ans[i] > 0) num++; //累计结果个数,0不算入斐波那契表示法 } printf ("%d", num); for (i = 0; i < ind; i++) { if (ans[i] == inf) break; if (ans[i] > 0) printf (" %d", ans[i]); } printf ("\n"); } return 0; }
发表评论
-
HDU 4746 Mophues
2013-10-01 17:29 2968莫比乌斯函数完整定义的通俗表达: 1)莫比乌斯函数μ(n ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1646/* * [题意] * 略 * [解题方法] ... -
UVA 10168 Summation of Four Primes
2013-02-14 21:48 1773/* * [题意] * 将一个数拆成四个素数的和, ... -
UVA 10139 Factovisors
2013-02-09 22:56 2094/* * [题意] * 判断n!是否能被m整除(n ... -
UVA 10104 Euclid Problem
2013-02-09 22:50 1459新手请进:扩展欧几里德入门 /* * ... -
UVA 10006 Carmichael Numbers
2013-02-08 08:27 2414/* * [题意] * 输入n,若满足如下两个条件 ... -
UVA 10110 Light, more light
2013-02-08 08:23 1394/* * [题意本质] * 输入n,如果n的约 ... -
【polya+Euler】HDU 2239 机器人的项链
2012-08-20 13:06 1409KIDx的解题报告 题目 ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1070KIDx的解题报告 题目链接:http://ac ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2618KIDx的解题报告 题 ... -
【扩展欧几里德】SGU 106
2012-05-22 23:57 2270KIDx的解题报告 题目链接:http://acm.s ... -
【数论+容斥】POJ 1091 跳蚤
2012-05-17 13:11 3229KIDx的解题报告 题目链接:http://poj.o ... -
【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid
2012-02-10 16:22 1776KIDx的解题报告 题意:求n个数的最小公倍数,结果很大 ... -
【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
2012-01-14 12:57 2220KIDx 的解题报告 题目链接:http://ligh ... -
【快速幂取模】fzu 1752 A^B mod C
2011-11-25 23:32 3631KIDx 的解题报告 参考《算法艺术与信息学竞赛》: 题目 ... -
【高次幂取模的应用】HDU 3609 Up-up
2011-11-25 22:42 2243KIDx 的解题报告 题目很容易看懂:http://acm.h ... -
模线性方程组-非互质中国剩余定理 (更新于2012/5/18)
2011-11-18 19:03 4625KIDx 的解题报告 该专题必备知识:解模线性方程 http: ... -
【素数筛法小结】fzu 1607 + fzu 1753
2011-11-16 23:06 1662KIDx 的解题报告 http://acm.fzu.edu.c ... -
HDU 1410 PK武林盟主
2011-10-02 16:28 1092KIDx 的解题报告 题目链接: http://acm.h ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2537KIDx 的解题报告 http://acm.hdu.ed ...
相关推荐
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
acm hdu as easy as a+b
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU 1022 Train Problem I 附详细思路
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
hdu 1695 GCD(欧拉函数+容斥原理).docx
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...