之前的游记过于花里胡哨,省赛题解的话另开一个好了 :-)

不知道什么时候能写完以及会写到哪里。

佛系小仙女(其实真相是太菜了,难题是既会写又不会写的~

HBCPC河北省赛解题报告

封面图是省赛穿的小裙裙QWQ

“女装”参赛然后被捶得有点难过。G、K too easy,我就直接跳了。

H.天神的密码 199/528

这题也很水。(因为题目给了k的限定,不然就涉及到大整数快速幂)啥也不说了,放个代码。

注意不要使用pow函数计算,pow返回的是double类型,会掉精度。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
int sum=0;
if(k==2)
n*=n;
while(n)
{
sum+=n%10;
n/=10;
}
while(sum>=10)
{
int sum1=sum;
sum=0;
while(sum1)
{
sum+=sum1%10;
sum1/=10;
}
}
cout<<sum<<endl;
}
return 0;
}

 

时:

因为只有4500位,使用高精度乘法模拟即可。

 

时:

考虑这个过程的性质,设某个数的第个数位的数字为,可以知道:

也就是说,对于某个数字来说,他的所有的数位上的和对9取模等于数字对9取模。

设第次操作后的值为,我们可以知道

由此,可以得知:题目中对于数字进行变换的过程等价于令对9取模,使用快速幂计算即可。

B.icebound and sequence 27/720

简单想法直接模拟,复杂度 太大会 TLE

solution 1

考虑等比数列的性质,如果我们想要计算,我们可以先计算,然后整体乘上,即

利用这个性质,我们使用递归分治法解题。假设递归的这一层我们需要计算,我们先递归计算,将得到的结果乘上,则得到。因为最后一项为向下取整再乘二,如果为奇数的时候还需要再加一个。全程注意取模!

对于每一层我们都像上面那样递归,每一层都需要使用快速幂计算,共有层,总复杂度为,如果我们每层都记录一个参数,,则无需快速幂,总复杂度为

solution 2

表示等比数列前项的和,则,这是一个线性常系数递推式,可以使用矩阵快速幂处理递推。

solution 3

根据等比数列求和公式:当时,

由于 可能为合数,在模 意义下可能不存在逆元

所以要改变一下模数,先将模数改为 ,计算模 意义下的答案

,由于 能被 整除, 故 能被 整除,就可以不用求逆元

我直接套了邝斌巨巨的板子,快速幂+递归

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,MOD,q;

ll pow_m(ll a,ll n)
{
ll ret=1;
ll tmp=a%MOD;
while(n)
{
if(n&1)
ret=(ret*tmp)%MOD;
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}

ll sum(ll p,ll n)
{
if(p==0)
return 0;
if(n==0)
return 1;
if(n&1)
return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2)%MOD)%MOD;
else
return ((1+pow_m(p,n/2+1))%MOD*sum(p,n/2-1)+pow_m(p,n/2)%MOD)%MOD;
}

int main()
{
int t;
cin>>t;
while(t--)
{
cin>>q>>n>>MOD;
if(sum(q,n)==0)
cout<<MOD-1<<endl;
else
cout<<sum(q,n)-1<<endl;
}
return 0;
}

C.分治 25/171

区间

表示攻打完第 个国家到第 个国家共 个国家需要的最小花费
第一层循环枚举区间长度,第二层循环枚举区间左断点,第三层循环枚举最先攻打区间 内的城市k。则状态转移为

复杂度是

 

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int dp[105][105];
int cost[105],n;

int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>cost[i];
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int len=2;len<=n;len++)
{
for(int l=1;l+len<=n+1;l++)
{
int r=l+len-1;
for(int i=l+1;i<=r-1;i++)
{
dp[l][r]=min(dp[l][r],dp[l][i-1]+dp[i+1][r]+(r-l)*cost[i]);
}
dp[l][r]=min(dp[l][r],dp[l][l]+dp[l+1][r]+(r-l)*cost[l]);
dp[l][r]=min(dp[l][r],dp[r][r]+dp[l][r-1]+(r-l)*cost[r]);
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}

最后更新: 2019年08月05日 09:51

原始链接: http://yisin.top/2019/05/27/HBCPC河北省赛解题报告/

× 请我吃糖~
打赏二维码