【补题系列】2020USST算法竞赛练习场1
题解
题意：给你一个数$n$，要求输出$n!$的位数
算法：由数学知识可知，一个数$x$的位数是$[lgx]+1$，所以有
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
long double ans=0;
for(int i=1;i<=x;i++){
ans+=log10(i);
}
ans=floor(ans)+1;
cout<<fixed<<setprecision(0)<<ans<<endl;
}
return 0;
}
|
题解
题意：要求$(A/B)\%9973$，给出$n(n=A\%9973)$和$B$，且$gcd(B,9973)=1$
算法：
- 扩展欧几里得
- 答案就是$n*(b对9973的逆元)\%9973$，然后用快速幂算这个逆元，即$b^{9973-2}\%9973$
AC代码
扩展欧几里得
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
| #include<bits/stdc++.h>
using namespace std;
const int mod=9973;
int x,y;
void exgcd(int a,int b){
int t;
if(b==0){
x=1;
y=0;
return;
}else{
exgcd(b,a%b);
t=x;
x=y;
y=t-(a/b)*y;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n,b;
cin>>n>>b;
exgcd(b,mod);
if(x<0) x+=mod;
x*=n;
printf("%d\n",x%mod);
}
return 0;
}
|
快速幂求逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod=9973;
int main() {
ll k,x,ans;
int t,n,b;
scanf("%d",&t);
while (t--) {
scanf("%d%d",&n,&b);
k=b; x=mod-2; ans=1;
while (x) {
if (x&1) ans=ans*k%mod;
k=k*k%mod;
x>>=1; }
ans=ans*n%mod;
printf("%lld\n",ans);
}return 0;
}
|
题解
题意：不说了，算是裸的分组背包（见分组背包模板题）
算法套路：依次枚举 数据组数、背包容量、每组数据内的单位数据（包括体积和价值）动态规划求解
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
int a[105][105];
int dp[100005];
int main(){
int n,m;
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
if(n==0&&m==0) break;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=1;k<=j;k++){
dp[j]=max(dp[j],dp[j-k]+a[i][k]);
}
}
}
cout<<dp[m]<<endl;
}
return 0;
}
|
题解
题意：给出$n,a$，要求你求出满足$a^n+b^n=c^n$中的$b$和$c$
算法：根据费马大定理，$n=0或n>2$都是无解的，对于$n=1$时，随便枚举；对于$n=2$时，有勾股奇偶构造公式如下
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,a;
scanf("%d %d",&n,&a);
if(n>2||n==0){
printf("-1 -1\n");
}
else if(n==1){
printf("1 %d\n",a+1);
}
else if(n==2){
if(a&1){
int n=(a-1)>>1;
int b=n*n+(n+1)*(n+1)-1;
int c=b+1;
printf("%d %d\n",b,c);
continue;
}else{
int n=a>>1;
int b=n*n-1;
int c=b+2;
printf("%d %d\n",b,c);
}
}
}
return 0;
}
|
题解
题意：裸的KMP算法模板，因为昨天刚学，所以记录一下
算法套路：模式串自己匹配自己构造出kmp数组，文本串用kmp数组去匹配
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
int a[1000015],b[1000015];
int kmp[1000015];
bool f=0;
int main(){
int t;
scanf("%d",&t);
while(t--){
f=0;
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int j=1;j<=m;j++){
scanf("%d",&b[j]);
}
int j=0;
for(int i=2;i<=m;i++){
while(j&&b[i]!=b[j+1]) j=kmp[j];
if(b[j+1]==b[i]) j++;
kmp[i]=j;
}
j=0;
for(int i=1;i<=n;i++){
while(j&&b[j+1]!=a[i]) j=kmp[j];
if(b[j+1]==a[i]) j++;
if(j==m){
printf("%d\n",i-m+1);
f=1;
break;
}
}
if(!f) printf("-1\n");
}
return 0;
}
|
题解
题意：给一个无向无权图，求出其中节点数为$k$个的完全图的个数
完全图：$k$个定点的完全图定义为任意一个节点都与其余$k-1$个节点相连
算法：暴力DFS搜索，前向星存边，注意两点
- 存单向边（小 指向 大），满足枚举时递增枚举，防止重复计算
- 每次枚举邻接点，减少枚举数
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
struct Edge{
int v,next;
}e[2005];
int t,n,m,head[10005],cnt,s,ans,size;
bool mm[105][105];
int a[1005];
inline void addedge(int u,int v){
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
inline bool check(int u){
for(int i=1;i<=size;i++){
if(!mm[a[i]][u]) return false;
}
return true;
}
inline void dfs(int x){
if(size==s){
ans++;
return;
}
for(int i=head[x];i;i=e[i].next){
int v=e[i].v;
if(check(v)){
a[++size]=v;
dfs(v);
--size;
}
}
}
int main(){
scanf("%d",&t);
while(t--){
cnt=0;
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
memset(a,0,sizeof(a));
memset(mm,false,sizeof(mm));
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u>v) swap(u,v);
addedge(u,v);
mm[u][v]=1;
mm[v][u]=1;
}
size=1;
ans=0;
for(int i=1;i<=n;i++){
size=0;
a[++size]=i;
dfs(i);
}
printf("%d\n",ans);
}
return 0;
}
|
题解
题意：分别给出$n$种卡片在一包零食中出现的概率，求集齐这$n$种卡片需要买的零食数量的期望
算法：概率论知识，举个例子，有两种卡片，出现概率分别为$P_1,P_2$，那么买到第1种卡片所需零食包数期望为$\frac{1}{P_1}$，同理，买到第2种卡片所需零食包数期望为$\frac{1}{P_2}$，而买到第1种或第2种卡片所需零食包数期望为$\frac{1}{P_1+P_2}$，
那么集齐这两种卡片所需的零食数量（根据容斥原理）为：
同理三种情况的结果如下：
以此类推，这就是容斥原理，于是考虑可以利用二进制枚举$n$的所有状态（共$2^n-1$种），然后枚举$P_i$（利用位运算和&运算符）计算出上方公式中的每一项，分母中有奇数个P就加上这个项，偶数个P就减去这个项
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
double p[25];
int main(){
int n;
while(cin>>n){
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++){
scanf("%lf",&p[i]);
}
double ans=0;
for(int i=1;i<(1<<n);i++){
int cnt=0;
double sum=0;
for(int j=1;j<=n;j++){
if(i&(1<<(j-1))){
cnt++;
sum+=p[j];
}
}
if(cnt&1) ans+=1/sum;
else ans-=1/sum;
}
printf("%.4lf\n",ans);
}
return 0;
}
|
以上几题让我学到了新姿势！