uva10655题目链接 题意： 给出a+b和ab的值，问a^n+b^n 思路： 构造矩阵,手写一下很显然... 转移矩阵M=[0 , 1] [-q,p ] 初始矩阵M1=[p ] [p^2-2*q] 快速幂即可。 有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。 如果用p=0&&q=0作为终止条件，那么就会将三个输入，但p==0&&q==0的情况错误得终止... 正确的做法是 while (~scanf("%lld%lld%lld",&p,&q,&n)==3) /* …

题目链接 题意：初始有一个锅，每t分钟可以做好k个饼，现在需要N个饼。还可以另外建一个锅，花费d时间，建好以后两个锅可以并行烙饼。问是否应该建锅？（以期减少烙饼时间） 思路：求出两种情况下的总时间，比较一下。 只有一个锅的情况很好求。 两个锅的情况比较麻烦，不如模拟时间流逝？ 反正最多也就1E6的时间。。。模拟一下。。。稳。。 /* *********************************************** Author :111qqz Created Time :2017年05月11日 星期四 15时29分43秒 File Name :A.cpp …

有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。 初始集合是空的，有两种操作，要么给集合添加一个长度为 L 的木棒，要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。 输入描述: 每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) ， 接下来有n行，每行第一个整数为操作类型 i (i ∈ {1,2})，第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插 …

1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss] Description 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。 Input 第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度 Output 所构成不重复矩形的个数 Sample Input 8 1 2 2 3 1 1 3 3 Sample Output 3 HINT …

题目链接 题意：一个人有n元前，他要交的税是n的最大因子（除n外)，现在这个投机倒把者想把前分成k部分(k为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。 思路：要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想 内容是：任何一个大于２的偶数可以写成两个素数的和。 （虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的２３３３ 那么任何大于２的偶数，答案就是２ 奇数可以分成一个３和一个偶数，答案为３． 不过这可能还不够优，这也是这道题的两个trick所在： 如果该数本身为素数，那么不用分（k取１），答案为１ 如果该数减去２为素数，那么答案为２． /* …

题目链接 题意：n个人进行淘汰赛制的比赛，输的人直接被淘汰，不进行下一轮，现在要求两个人可以比赛当且仅当两个人的胜场数相差小于等于１，现在问赢得最多场的那个人，最多可能赢多少场。 思路：打表找规律。。。麻蛋。。手算错了n=8。。。结果达成了f[1] = 2,fib[2] =4 的奇怪的fib数列。。。卡了一个多小时。。。气哭了。。。 /* *********************************************** Author :111qqz Created Time :2016年11月29日 星期二 10时16分50秒 File Name :code/cf/#382/C.cpp …

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 Input 输入仅一行，包含两个整数n, k。 Output 输出仅一行， …

题目链接 题意：给出n（n<=1E3）个不同的点，问最多组成多少个平行四边形。 思路：这道题的关键是，对于平行四边形的判断条件，要利用平行四边形对角线的交点平分两条对角线的性质。 也就是说，如果两条线段的对角线重合，那么一定可以组成一个平行四边形。 因此统计中点的位置即可，复杂度nnlg(n*n) /* *********************************************** Author :111qqz Created Time :2016年11月22日 星期二 22时43分26秒 File Name :code/poj/1971.cpp …

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个正整数用空格隔开。 Output  一行一个正整数表示那个众数。 Sample Input 5 3 2 3 1 3 Sample Output 3 HINT 100%的数据，n<=500000，数列中每个数<=maxlongint。 zju2132 The Most …

1968: [Ahoi2005]COMMON 约数研究 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1997 Solved: 1508 [Submit][Status][Discuss] Description Input 只有一行一个整数 N（0 < N < 1000000）。 Output 只有一行输出，为整数M，即f(1)到f(N)的累加和。 Sample Input 3 Sample Output 5 HINT Source Day2 思路：如果跟着题目的意思走。。。求每个数的约束个数。。。复杂度是不资瓷的。。。 然而因为是求和，我们可以直接考虑，每个因子对答案的 …