2021年6月份打的比賽，現在才開始復盤。
目錄
- A: 智慧果【難度: 簽到題 / 知識點: 遞推】
- B: Xanadu【難度: 中 / 知識點: 最短路】
- C: 這是一道大難題【難度: 一般 / 知識點: 最小生成樹】
- H: 智慧數【難度: 簽到 / 知識點: 模擬】
- L: 這是一道壓軸題【難度: 一般 / 知識點: 思維 枚舉】
A: 智慧果【難度: 簽到題 / 知識點: 遞推】
http://106.75.49.226/problem/ADPC1-Z-A
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
const int mod
=1e5;
long long int f
[N
],n
;
int main(void)
{f
[1]=1,f
[2]=2,f
[3]=5;for(int i
=4;i
<=1000;i
++) f
[i
]=(f
[i
-1]*f
[i
-2]*f
[i
-3]+f
[i
-1]+f
[i
-2]+f
[i
-3])%mod
;cout
<<f
[1000];return 0;
}
B: Xanadu【難度: 中 / 知識點: 最短路】
http://106.75.49.226/problem/ADPC1-Z-B
通過每一行的點，它前面有幾個1就要走多遠。以此來建立一個圖，對于該圖求最短路即可。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e3+10;
const int inf
=0x3f3f3f3f;
int g
[N
][N
],dist
[N
],st
[N
],n
,cnt
;
int a
[N
][N
];
int Dijkstra()
{memset(dist
,0x3f,sizeof dist
);dist
[1]=0;for(int i
=0;i
<n
;i
++){int t
=-1;for(int j
=1;j
<=n
;j
++) if(!st
[j
]&&(t
==-1 || dist
[j
]<dist
[t
] )) t
=j
;st
[t
]=1;for(int j
=1;j
<=n
;j
++) dist
[j
]=min(dist
[j
],dist
[t
]+g
[t
][j
]);}return dist
[n
];
}
int main(void)
{cin
>>n
;memset(g
,0x3f,sizeof g
);for(int i
=1;i
<=n
;i
++){int t
=0;for(int j
=1;j
<=n
;j
++){cin
>>a
[i
][j
];if(a
[i
][j
]) g
[i
][j
]=t
,t
++;}}int ans
=Dijkstra();cout
<<ans
<<endl
;return 0;
}
C: 這是一道大難題【難度: 一般 / 知識點: 最小生成樹】
http://106.75.49.226/problem/ADPC1-Z-C
解析: 先將選的邊連接，再跑一下克魯斯卡爾算法即可。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5*2+10;
struct edge{int a
,b
,c
;}edges
[N
];
int n
,m
,k
,cnt
,p
[N
];
long long int res
;
int find(int x
)
{if(x
!=p
[x
]) p
[x
]=find(p
[x
]);return p
[x
];
}
bool cmp(edge a
,edge b
) {return a
.c
<b
.c
;}
void kruskal()
{for(int i
=1;i
<=n
;i
++) p
[i
]=i
;res
+=edges
[k
-1].c
;p
[find(edges
[k
-1].b
)]=find(edges
[k
-1].a
);cnt
++;sort(edges
,edges
+m
,cmp
);for(int i
=0;i
<m
;i
++){int a
=edges
[i
].a
,b
=edges
[i
].b
,c
=edges
[i
].c
;if(find(a
)!=find(b
)){res
+=c
;p
[find(b
)]=find(a
);cnt
++;}}
}
int main(void)
{cin
>>n
>>m
;for(int i
=0;i
<m
;i
++) cin
>>edges
[i
].a
>>edges
[i
].b
>>edges
[i
].c
;cin
>>k
;kruskal(); cout
<<res
;return 0;
}
H: 智慧數【難度: 簽到 / 知識點: 模擬】
http://106.75.49.226/problem/ACPC1-Z-H
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
LL cnt
;
int main(void)
{for(LL i
=2;;i
++){for(LL j
=2;j
<i
;j
++){if(i
%j
==0){LL t
=sqrt(i
*j
);if(t
*t
==i
*j
) {cnt
++;if(cnt
==3000){cout
<<i
<<endl
;return 0;}break;}}}}return 0;
}
L: 這是一道壓軸題【難度: 一般 / 知識點: 思維 枚舉】
http://106.75.49.226/problem/ADPC1-Z-L
解析: 將一串的0和1壓縮為一個數，最后枚舉中間去掉的一段。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int n
,k
,ans
;
vector
<int>ve
;
string s
;
int main(void)
{cin
>>n
; cin
>>s
;for(int i
=0;i
<n
;i
++){k
++;if((i
+1==n
) || s
[i
]!=s
[i
+1] ) ve
.push_back(k
),ans
=max(ans
,k
),k
=0;}for(int i
=1;i
<ve
.size();i
++){if(i
!=ve
.size()-1) ans
=max(ans
,ve
[i
-1]+ve
[i
+1]);}cout
<<ans
<<endl
;return 0;
}
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的2020-2021年度第二届全国大学生算法设计与编程挑战赛（春季赛）【部分题题解】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
