Fork me on GitHub

「HR(HackerRank)」斯波题切题记

发表于 | 分类于
字数统计: 1,014字 | 阅读时长 ≈ 6分钟

引言

切了一波斯波题hjq素质不能更差随便玩玩,还是有点收获的吧..

K Candy Store

Links there:HR-K Candy Store

大意:有N个人,分不同的K种糖果,各个糖果可以选无数个,求方案数.

solution:典型的插板法.答案为$C(n+m-1,n-1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9; 
int T,n,m,C[5003][5003];
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
signed main(signed argc, char *argv[])
{
	for (int i = 0; i <= 5000; i++)
		for (int j = 0; j <= i; j++)
		{
			if (i == j || i == 0) C[i][j] = 1;
			else C[i][j] = (C[i-1][j-1]+C[i-1][j]) % mod;
		}
	T = read();
	while(T--)
	{
		int n = read(), m = read();
		printf("%lld\n",C[n+m-1][n-1]);
	}
	return 0;
}

Special Multiple

Links there:HR-Special Multiple

大意:给出一个N,求最小的只由0,9组成的数字串使得其为给定N的倍数.$N \leq 500$

solution: 考虑01串二进制的转换,[1,2,3,4] $->$ [1,10,11,100]当我们把右边乘9即可得到0-9串.

逐位构造即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long binar(long long n) {
	if (n == 1) return 1LL;
	if (n & 1) return 1LL * 10*binar(n/2)+1;
	else return 1LL * 10*binar(n/2);
}
signed main(signed argc, char *argv[]) {
	int t;
	cin>>t;
	while(t--) {
		long long n,a=1,b=9;
		cin>>n;
		while(b % n) {
			a++;
			b = binar(a);
			b *= 9;
		}
		cout<<b<<endl;
	}
	return 0;
}

感觉和SOJ上马三的二进制数一题很像.而且似乎加个高精就可以A掉.

当时本蒟蒻做这题还用的dp哈哈.

Matrix Racing

Links there:HR-Matrix Racing

大意:给出一个$N \times M$的矩阵,求从左上角$(1,1)$到右下角$(N,M)$的方案数

变相的杨辉三角.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7; 
int T,n,m,jc[2000010];
int quickpow(int m,int n)
{
	int b = 1;
	while(n)
	{
		if (n & 1) b = b * m % mod;
		n /= 2;
		m = m * m % mod;
	}
	return b;
}
int C(int n,int r)
{
	int i1 = quickpow(jc[n-r],mod-2);
	int i2 = quickpow(jc[r],mod-2);
	int ret = 1LL * i1 * i2 % mod * jc[n] % mod;
	return ret;
}
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
signed main(signed argc, char *argv[])
{
	jc[0] = 1;
	for (int i = 1; i <= 2000004; i++)
	jc[i] = 1LL * jc[i-1] * i % mod;
	T = read();
	while(T--)
	{
		int n = read(), m = read();
		printf("%lld\n",C(n+m-2,n-1));
	}
	return 0;
}

剩下的好像都挺傻逼的就不写题面了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//Sherlock和约数
#include<bits/stdc++.h>
using namespace std;
int t,n;
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
int main(int argc, char *argv[])
{
	t = read();
	while(t--)
	{
		n = read();
		int ans = 0;
		for (int i = 1; i <= sqrt(n+0.5); i++)
			if (!(n % i)) {if(!(i%2))++ans; if(i*i == n) continue; if(!((n/i)%2)) ++ans;}
		printf("%d\n",ans);
	}
	return 0;
}
//Diwali Lights
#include<bits/stdc++.h>
const int mod = 1e5;
const int maxn = 1e4;
using namespace std;
int T,n;
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
int main(int argc, char *argv[])
{
	int T = read();
	while(T--)
	{
		int n = read(),prod = 1;
		for (int i = 0; i < n; i++) prod *= 2,prod %= mod;
		prod = ((prod-1) % mod + mod) % mod;
		printf("%d\n",prod);
	}
	return 0;
}
//Summing N Series
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
const int mod = 1e9+7;
int main(int argc, char *argv[])
{
	cin >> T;
	while(T--)
	{
		cin >> n;
		n %= mod;
		n = n * n % mod;
		cout << n << endl;
	}
	return 0;
}