111qqz的小窝

老年咸鱼冲锋!

uva 10655 – Contemplation! Algebra (构造矩阵,快速幂)

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)

 

 

 

codeforces #413 A. Carrot Cakes (模拟)

题目链接

题意:初始有一个锅,每t分钟可以做好k个饼,现在需要N个饼。还可以另外建一个锅,花费d时间,建好以后两个锅可以并行烙饼。问是否应该建锅?(以期减少烙饼时间)

思路:求出两种情况下的总时间,比较一下。

只有一个锅的情况很好求。

两个锅的情况比较麻烦,不如模拟时间流逝?

反正最多也就1E6的时间。。。模拟一下。。。稳。。

 

 

今日头条笔试题-木棒拼图(数学)

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

初始集合是空的,有两种操作,要么给集合添加一个长度为 L 的木棒,要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。

 

输入描述:

每组测试用例仅包含一组数据,每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) , 接下来有n行,每行第一个整数为操作类型 i (i ∈ {1,2}),第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒,如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒,且任意操作后集合都是非空的。

 

输出描述:

对于每一次操作结束有一次输出,如果集合内的木棒可以构成简单多边形,输出 “Yes” ,否则输出 “No”。

 

输入例子:

 

输出例子:

能组成n边形的条件可以由三角形推广而来..(虽然只是猜想…
也就是n-1条较小边的和大于最大边…事实证明这结论是对的orz..
然后就是multiset就好…

 

BZOJ 1800: [Ahoi2009]fly 飞行棋 (尺取+数学)

 

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<= 20

思路:一开始的想法是枚举四条边,如果a==c&&b==d,就认为是找到了一个矩形。

重点在于判重,非常不好判断。一开始想要根绝四条边的长度hash一下,但是设想一个所有弧长都相等,且弧长较多的情况。

此时所有矩形的边长长度都相同,但是显然是不同的矩形,因此这种判断方法是错误的。

比较棒的思路是:矩形的对角线一定是外接圆的直径。

因此只需要找有多少条执行,假设为c,那么答案就是c*(c-1)/2(因为任意两条对角线就可以构成一个矩形)

这种做法的好处很明显,不需要判重。

至于如何找直径,直径是把圆周等分的弦,所以尺取找一下就好了。

复杂度O(n)

 

codeforces #382 div2 D. Taxes(哥德巴赫猜想)

题目链接

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

思路:要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想

内容是:任何一个大于2的偶数可以写成两个素数的和。

(虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的2333

那么任何大于2的偶数,答案就是2

奇数可以分成一个3和一个偶数,答案为3.

不过这可能还不够优,这也是这道题的两个trick所在:

如果该数本身为素数,那么不用分(k取1),答案为1

如果该数减去2为素数,那么答案为2.

 

codeforces #382 div2 C. Tennis Championship(打表找规律)

题目链接

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

思路:打表找规律。。。麻蛋。。手算错了n=8。。。结果达成了f[1] = 2,fib[2] =4 的奇怪的fib数列。。。卡了一个多小时。。。气哭了。。。

 

 

bzoj 1257: [CQOI2007]余数之和sum (数学)

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

输出仅一行,即j(n, k)。

Sample Input

5 3

Sample Output

7

HINT

50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9

思路:一开始的想法。。。很容易想到当n>k的部分。。时可以是可以O(1)出来的。。。

然后对于n<k的部分。。。对于大于i/2的部分。。。是递减的等差数列。。也可以O(1)出来。。。

剩下的一半没时间好想法。。。现在复杂度仍然有5E8…gg\

打了很多表。。。也看出规律2333

于是看了题解。。

正解:k%i可以写成 k-k/i*i

而k/i一共有sqrt(k)种,相同的k/i位置相邻,他们的k%i的值是一个等差数列。。。

这道题就是求Σ(kk/ii)i=1..n简化一下是nkΣ(k/ii)i=1..n,显然我们可以发现⌊k/i⌋的取值是一个不上升序列,且有很多取值相同(事实上,⌊k/i⌋的取值只有√k个),那么我们就可以对i中的一段区间求和(这段区间内⌊k/i⌋取值相同),⌊k/i⌋相同且i单调增加1,可以直接算出来,时间复杂度O(√k)

 

 

 

poj 1971 Parallelogram Counting

题目链接

题意:给出n(n<=1E3)个不同的点,问最多组成多少个平行四边形。

思路:这道题的关键是,对于平行四边形的判断条件,要利用平行四边形对角线的交点平分两条对角线的性质。

也就是说,如果两条线段的对角线重合,那么一定可以组成一个平行四边形。

因此统计中点的位置即可,复杂度n*n*lg(n*n)

 

 

bzoj 2456: mode (O(1)找到出现次数大于n/2的数)

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 Frequent Number

思路:一开始没注意空间限制…不过为毛是TLE。。。以至于最后什么都不干也TLE,我才意识到问题并没有辣么简单。。。

%e9%80%89%e5%8c%ba_001

 

感觉这道题好神奇。

用到了抵消的思想,对于众数来说,不是众数的数是“非我族类其心必异”

因为众数出现大于n/2次,所以最后剩下的数一定是众数。

具体见代码。

 

bzoj 1968: [Ahoi2005]COMMON 约数研究 (思维题)

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

思路:如果跟着题目的意思走。。。求每个数的约束个数。。。复杂度是不资瓷的。。。

然而因为是求和,我们可以直接考虑,每个因子对答案的贡献。

容易知道,因子x对答案的贡献为n/x

x的范围为1..n

 

【叉姐的魔法训练第一课_初级魔法练习】poj 3244 Difference between Triplets (数学)

题目链接

题意:

For every pair of triplets, Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb, Kb), we define the difference value between Ta andTb as follows:

D(Ta, Tb) = max {IaIb, JaJb, KaKb} − min {IaIb, JaJb, KaKb}

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?

思路:转化要求的式子,如果把IaIb, JaJb, KaKb 看成数轴上的点,所求的式子就变成了求三个点构成的线段的距离。

设X=IaIb,Y=JaJb,Z=KaKb,那么该距离D = (|X-Y| + |Y-Z| + |Z-X|  )/2(该式子是此题最关键的一部,可以通过画图直观得到)  

D=|(ia-ja)-(ib-jb)| + |(ja-ka)-(jb-kb)| + | (ka-za)+(kb-zb) |

设a = ia-ja,b =ja-ka,c = ka-ia,然后分别排序类似于bzoj1604_拆点求曼哈顿距离

考虑第i个a,对于其他的n-1个a,有i-1个比它小,n-i个比它大,因此对答案的贡献为(i-1)个a[i]和 (n-i)个-a[i]

b,c同理。

 

 

 

light oj 1045 Digits of Factorial (k进制数的位数)

题目链接
题意:求n!在k进制表示下有多少位。
思路:答案为[ log(1)+log(2)+…+log(N) ]+1  其中log的底数都是K

由于有多组数据,预处理一个log的前缀和。

 

 

codeforces #368 div 2 C. Pythagorean Triples (构造,数学)

题目链接

题意:给出一个数,问包含这个数三个数组成的勾股数,输出另外两个数。

思路:

所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数.
那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数:
规律一:在勾股数(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为正整数)
利用以上两个公式,我们可以快速写出各组勾股数.

结论是:  n<=2无解。

n为奇数用公式1构造。

n为偶数用公式2构造。

 

 

 

 

hdu 5833 || ccpc 2016 网络赛 1002 Zhu and 772002 (高斯消元)

hdu 5833 题目链接

题意:n个数,保证每个数的素因子不超过2000,从中取若干个,问乘积是完全平方数的方案数。

思路: 完全平方数就是要求每个质因子的指数是偶数次。

列方程组,a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0

然后得到自由元的个数为num,答案为2^num-1 (减去空集)

 

hdu 2050 折线分割平面 (找规律,递推)

hdu 2050题目链接

题意:n条折线。。最多能把平面分成几部分。。
思路:联想到m条直线,最多能把平面分成m*(m+1)/2+1部分。。

画图发现。。。 f[2*n-1]==g[n]。。