SilentSpiral

WHUoj - 归档

58.Exchange

题意: 你有一张n元钱的支票, 现在你可以把它换成面值1/2/3元的硬币, 问共有多少种换法

譬如n=6的时候, 共有7种换法

1,1,1,1,1,1
2,1,1,1,1
2,2,1,1
2,2,2
3,1,1,1
3,2,1
3,3

思路:

对于每一个n, 将其组合的方式f(n)分类:
1. 只有1
2. 不含3, 必须有2
3. 至少有一个3

对于这三种情况

第一种只含1的有1种
第二种需要统计最多能够容纳的2的个数所以共$ $种
第三种至少有一个3所以拿掉这个3之后可以递归到f(n-3)

\[ f(n)=1+\lfloor \cfrac{n}{2} \rfloor+f(n-3)\\f(0)=1=1+\lfloor \cfrac{0}{2} \rfloor\\f(1)=1=1+\lfloor \cfrac{1}{2} \rfloor\\f(2)=2=1+\lfloor \cfrac{2}{2} \rfloor \]

共需递归\(\lfloor \cfrac{n}{3} \rfloor\)次, 共有\(\lfloor \cfrac{n}{3} \rfloor+1\)项

\[ f(n)=\lfloor \cfrac{n}{3} \rfloor+1+\sum_{i=0}^{\lfloor n/3 \rfloor}\lfloor {\cfrac{n\ (mod\ 3)+3i}{2} \rfloor}\\ f(n)=\lfloor \cfrac{n}{3} \rfloor+1+\sum_{i=0}^{\lfloor n/3 \rfloor}\lfloor {\cfrac{n-3i}{2} \rfloor} \]

两种写法都对, 方向是反着的, 比较麻烦的是取整问题, 否则就可以按照等差数列来求和了

考虑到 \((\lfloor \frac{n}{2} \rfloor+\lfloor \frac{n-3}{2} \rfloor)=(\lfloor \frac{n-6}{2} \rfloor+\lfloor \frac{n-9}{2} \rfloor)+6\)

采用了并项的方式, 对新的等差数列进行求和, 并单独讨论原数列项数为奇数的情况

1
2
3
4
5
6
7
8
9
10
while(1):
	n=int(input())
	if not n:
		break
	p=(n+3)//3  #项数
	m=p>>1      #并项
	ans=(((n>>1)+((n-3)>>1)+((n+6-m*6)>>1)+((n+3-m*6)>>1))*m>>1)+p
	if p&1:     #未合并项
		ans+=(n%3)//2
	print(ans)

470. A Simple Math Problem

题意: 对于给定的输入n, 将1~n连起来写成一个整数, 求这个整数模11的值
tips:
1 ≡ 1 ( mod 11)
1234567891011121314151617181920 ≡ 5 ( mod 11)
123456789101112131415161718192021 ≡ 4 ( mod 11)

易知

\[ 10^{2i}≡1\ \ (\ mod\ 11) \\ 10^{2i+1}≡10≡-1\ \ (\ mod\ 11) \]

记所求为f(n)

\(f(n)≡f(n-1)10^{\lfloor lgn \rfloor}+n\ \ (\ mod\ 11)\)

需要根据\(\lfloor lgn \rfloor\)对f(n)进行分段求解

一个思路是把每一段开始时的数保存起来作为基础偏移, 这样只需要在一个段内进行求解就可以了
base=[0,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,10]
这个偏移笔算都可以… 算错了会误差扩散
基础偏移并不能直接用,
具体来说如果段内位置与\(\lfloor lgn \rfloor\)皆为奇数, 那么基础偏移要取相反数

当\(\lfloor lgn \rfloor\)为奇数时, 段内为等差数列, 直接求和即可
当\(\lfloor lgn \rfloor\)为偶数时, 段内各项绝对值为等差数列, 且正负项交错, 需要并项求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
base=[0,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,10]
def solve():
	n=input()
	n=int(n)
	s=len(str(n))
	Bs=10**(s-1)   #段首项
	k=n+1-Bs       #段内位置
	ans=base[s-1]  #取基础偏移
	if s&1:
		if k&1:
			#ans=pow(-1,s%2)*ans+(Bs)%11+(k>>1)  #偏移取相反数,段首项(未合并项),并项和
			ans=-ans+1+(k>>1)
		else:
			ans+=(k>>1)          #并项和
	else:
		#ans+=(k*(n+Bs))//2      #等差数列求和
		ans+=(((k%22)*((n+Bs)%22))//2)    
	ans%=11
	print(ans)
	return ans

solve()

不知道为什么网上搜出来的都是矩阵快速幂…

313. K尾相等数

从键盘输入一个自然数K(K>1),若存在自然数M和N(M>N),使得KM和KN均大于或等于1000、且它们的末尾三位数相等，则称KM和KN是一对K尾相等数。请编写程序，输出M+N值最小的K尾相等数。

ax mod 1000, 又是个离散对数问题
根据在原根那里学到的性质
a的周期, 应当是\(φ {(1000)}=400\)的因子

A=[1,2,4,5,8,10,16,20,25,32,40,50,100,125,200,250,400]
但1000又没有原根, 所以至少400是取不到的

模m有原根的充要条件:
m = 1, 2, 4, p, 2p, pn
其中p是奇质数，n是任意正整数

编程寻找所有周期

1
2
3
4
5
6
7
8
A=[1,2,4,5,8,10,16,20,25,32,40,50,100,125,200,250,400]
B=set()
for i in range(2,1000):
	for d in A:
		if pow(i,500+d,1000)==pow(i,500+2*d,1000):
			B.add(d)
			break
print(B)

运行结果{1, 2, 100, 5, 4, 10, 50, 20, 25}

因为需要从头遍历寻找最小周期, 故手动排序得 [1, 2, 4, 5, 10, 20, 25, 50, 100]

同时发现有些数并不直接进入循环, 譬如2的周期为100
002和004都不在周期里
002->004->008…
752->504->008,而后才有周期
实际上周期从008开始
所以判别条件pow(i,100+d,1000)==pow(i,100+2*d,1000)
其实为了确保万无一失应该加1000的, 但是反正提交通过了就没管他

后来编程发现3次方后大于1000的所有数都能进入循环
所以其实只需要让2的幂大于1000即可
if pow(i,10+d,1000)==pow(i,10+2*d,1000):
最终代码里懒得改了

1
2
3
4
5
6
7
8
9
10
11
12
13
A=[1, 2, 4, 5, 10, 20, 25, 50, 100]
while(True):
	r=1000
	i=int(input())
	if not i:
		break
	for d in A:
		if pow(i,100+d,1000)==pow(i,100+2*d,1000):
			for j in range(100):
				if i**j>=1000 and pow(i,j,1000)==pow(i,j+d,1000):
					print(2*j+d)
					break
			break
打赏