Math

uva10655题目链接 题意： # 给出a+b和ab的值，问a^n+b^n 思路： # 构造矩阵，手写一下很显然…

题目链接 题意：初始有一个锅，每t分钟可以做好k个饼，现在需要N个饼。还可以另外建一个锅，花费d时间，建好以后两个锅可以并行烙饼。问是否应该建锅？（以期减少烙饼时间） 思路：求出两种情况下的总时间，比较一下。

有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。

1800: [Ahoi2009]fly 飞行棋 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss] Description # 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

题目链接 题意：一个人有n元前，他要交的税是n的最大因子（除n外)，现在这个投机倒把者想把前分成k部分(k为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。

题目链接 题意：n个人进行淘汰赛制的比赛，输的人直接被淘汰，不进行下一轮，现在要求两个人可以比赛当且仅当两个人的胜场数相差小于等于１，现在问赢得最多场的那个人，最多可能赢多少场。

1257: [CQOI2007]余数之和sum # Time Limit: 5 Sec Memory Limit: 162 MB Submit: 3724 Solved: 1711 [Submit][Status][Discuss] Description # 给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

题目链接 题意：给出n（n<=1E3）个不同的点，问最多组成多少个平行四边形。 思路：这道题的关键是，对于平行四边形的判断条件，要利用平行四边形对角线的交点平分两条对角线的性质。

2456: mode # Time Limit: 1 Sec Memory Limit: 1 MB Submit: 3887 Solved: 1636 [Submit][Status][Discuss] Description # 给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。 Input # 第1行一个正整数n。 第2行n个正整数用空格隔开。

1968: [Ahoi2005]COMMON 约数研究 # Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1997 Solved: 1508 [Submit][Status][Discuss] Description # Input # 只有一行一个整数 N（0 < N < 1000000）。

题目链接 题意： # For every pair of triplets, Ta = (Ia, Ja, Ka) and T__b = (Ib, Jb, Kb), we define the difference value between Ta and_T__b_ as follows: D(Ta,_ Tb_) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb} Now you are given N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

题目链接 题意：求n！在k进制表示下有多少位。 思路：答案为[ log(1)+log(2)+…+log(N) ]+1 其中log的底数都是K 由于有多组数据，预处理一个log的前缀和。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Tue 13 Sep 2016 05:13:15 PM CST 4File Name :code/loj/1045.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set>-digits-of-factorial-k进制数的位 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=1E6+7; 32int n; 33int base; 34double sum[N]; 35int main() 36{ 37 #ifndef ONLINE_JUDGE 38 freopen("code/in.txt","r",stdin); 39 #endif 40 sum[0] = 0 ; 41 for ( int i = 1 ; i < N ; i++) sum[i] = sum[i-1] + log(i); 42 int T; 43 cin>>T; 44 int cas = 0 ; 45 while (T--) 46 { 47 scanf("%d%d",&n,&base); 48 double ans = sum[n]/log(base)+1; 49 printf("Case %d: %d\n",++cas,int(ans)); 50 } 51 #ifndef ONLINE_JUDGE 52 fclose(stdin); 53 #endif 54 return 0; 55}

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。 思路： 所谓勾股数，就是当组成一个直角三角形的三边长都为正整数时，我们就称这一组数为勾股数. 那么，组成一组勾股数的三个正整数之间，是否具有一定的规律可寻呢？下面我们一起来观察几组勾股数： 规律一：在勾股数（3,4,5）、（5,12,13）、（7,24,25）（9,40,41）中，我们发现 由（3,4,5）有：32=9=4+5 由（5,12,13）有：52=25=12+13 由（7,24,25）有：72=49=24+25 由（9,40,41）有：92=81=40+41. 即在一组勾股数中，当最小边为奇数时，它的平方刚好等于另外两个连续的正整数之和.因此，我们把它推广到一般，从而可得出以下公式： ∵（2n+1)²=4n²+4n+1=（2n²+2n）+（2n²+2n+1） ∴（2n+1)²+（2n²+2n)²=（2n²+2n+1)²（n为正整数） 证明（略） 勾股数公式一：（2n+1,2n²+2n,2n²+2n+1）（n为正整数） 规律二：在勾股数（6,8,10）、（8,15,17）、（10,24,26）中，我们发现 由（6,8,10）有：62=36+2×（8+10） 由（8,15,17）有：82=64=2×（15+17） 由（10,24,26）有：102=100=2×（24+26） 即在一组勾股数中，当最小边为偶数时，它的平方刚好等于两个连续整数之和的二倍，推广到一般，从而可得出另一公式： ∵（2n）2=4n2=2[（n2-1）+（n2+1）] ∴（2n）2+（n2-1）2=（n2+1）2（n≥2且n为正整数） 证明（略） 勾股数公式二：（2n,n²-1,n²+1）（n≥2且n为正整数） 利用以上两个公式，我们可以快速写出各组勾股数.

hdu 5833 题目链接 题意：n个数，保证每个数的素因子不超过2000，从中取若干个，问乘积是完全平方数的方案数。 思路： 完全平方数就是要求每个质因子的指数是偶数次。 列方程组，a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子，建立异或方程组，要求因子个数为偶数，即异或为0

hdu 2050题目链接 题意：n条折线。。最多能把平面分成几部分。。 思路：联想到m条直线，最多能把平面分成m*(m+1)/2+1部分。。 画图发现。。。 f[2*n-1]==g[n]。。

cf682A题目链接 题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。 思路：傻逼题。。。统计%5。。。然后乘法原理。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 12时32分22秒 4File Name :code/2016whust/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E6+7; 34int n,m; 35LL a[N],b[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 ms(a,0); 44 ms(b,0); 45 for ( int i = 1 ; i <= n ; i++) 46 { 47 int x = i % 5; 48 a[x]++; 49 } 50 for ( int i = 1 ; i <= m ; i++) 51 { 52 int x = i % 5; 53 b[x]++; 54 } 55 LL ans = 0; 56 ans = a[0]*b[0]+a[1]*b[4]+a[2]*b[3]+a[3]*b[2]+a[4]*b[1]; 57 cout<<ans<<endl; 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k，表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d，那么k<=d+1的时候，答案为k-1，否则答案为d+(k-d-1)*2。。。

题目链接 题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围成的封闭图形中间都是水，问有多少个危险点，使得如果在这个点忘记转弯就会掉进水里。

http://acm.hdu.edu.cn/showproblem.php?pid=5630 题意：nm的棋盘，相邻格子的颜色相反，每次可以翻转一个任意大小矩形的格子，问最少需要翻转多少次使得棋盘的nm个格子颜色相同。（翻转的意思是颜色反色） 思路：手写了下。。发现。。答案就是n/2+m/2. 对应的最优策略是。。翻偶数行和偶数列，都翻一遍，颜色就一样了。

http://acm.hdu.edu.cn/showproblem.php?pid=1205 题意：有n种糖果，第i种糖果有a[i]个，相邻两次不能吃一样的糖果，问能否有办法吃完所有糖果… 思路：如果第i种糖果有k个的话，那么其他所有种类的糖果之和至少有k-1个，才可能吃完。复杂度O(n) 看到有人说是抽屉原理…..大概。。。？不过不太明显。。直接想就好吧