提醒：篇幅可能有點(diǎn)長(zhǎng)，為了方便，大家可以直接看目錄快速查找想要的內(nèi)容
1.新生【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
思路：上屆小橋獲得了第14屆總冠軍，那么這屆是第15屆，直接輸出15就是答案
2.鋪地板【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
4
7 6
2 2
12 8
1 12output:
Yes
No
Yes
No
思路：思維/數(shù)學(xué)
1.對(duì)于每一塊地板，如果能被湊出來(lái)，那么一定是2*3地磚組合出來(lái)的，無(wú)論2*3地磚怎么放都為6的倍數(shù)，故長(zhǎng)為n,寬為m的地板，n*m%6==0一定成立
2.這里還要注意一個(gè)特判，就是如果長(zhǎng)或?qū)挒?（例如n=6,m=1），那么是6的倍數(shù)也無(wú)法滿足要求（不能切割地磚）
Ac_code：java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
int n=sc.nextInt(),m=sc.nextInt();
if(n==1||m==1) System.out.println("No");
else if(n*m%6==0) System.out.println("Yes");
else System.out.println("No");
}
}
}
3.擺玩具【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
5 2
2 5 7 10 13output:
8
思路：思維/貪心
簡(jiǎn)述題意：給一個(gè)長(zhǎng)度為n的不下降數(shù)組,分成k個(gè)子數(shù)組，使子數(shù)組的極差的總和最小
1.對(duì)數(shù)組中相鄰兩數(shù)的差記為 f[0],f[1],f[2],f[3]....f[n-2],并對(duì)其累加記為sum（這里注意數(shù)組是不下降的），故f數(shù)組中的元素是>=0的。
2.此時(shí)可以發(fā)現(xiàn)sum就是將長(zhǎng)度為n的數(shù)組的極差值。
3.但是題目有一個(gè)限制條件分成k個(gè)子數(shù)組，k等于1時(shí),sum就是答案，k>=2時(shí)，此時(shí)貪心的想讓相差大的分開(kāi)多開(kāi)一個(gè)子數(shù)組，以滿足極差總和最小
舉個(gè)栗子：
????????h數(shù)組: 2 5 7 10 13
? ? ? ??f數(shù)組:3 2 3 3
? ? ? ? k等于2時(shí),刪除一個(gè)最大的數(shù)3，有3個(gè)3，故有三種情況分子數(shù)組的情況都滿足條件，
????????刪除第一個(gè)3為：子數(shù)組分為 [2],?[5 7 10 13],極差和為：0+8
????????刪除第二個(gè)3 為：子數(shù)組分為[2,5,7], [10,13]，極差和為：5+3
????????刪除第三個(gè)3為：子數(shù)組分為[2,5,7,10],[13]，極差和為：8+0
4.實(shí)現(xiàn)時(shí)對(duì)f數(shù)組排序，用總和減去f中（k-1)個(gè)最大的數(shù)
Ac_code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,k;
int a[N];
int f[N];
void solve(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",a+i);
LL sum=0; //累加差值
for(int i=1;i<n;i++) f[i-1]=a[i]-a[i-1],sum+=f[i-1];
sort(f,f+n-1);
for(int i=n-2;i>=0&&--k;i--) sum-=f[i]; //減去(k-1)個(gè)最大的數(shù)
cout<<sum<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}4.通關(guān)【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
4 5
0 3 5
1 2 8
1 3 9
3 1 15output:
3
思路：bfs+堆優(yōu)化
簡(jiǎn)述題意：給一個(gè)以1為根的有向樹(shù)和初始的經(jīng)驗(yàn)，問(wèn)最多能覆蓋的結(jié)點(diǎn)為多少個(gè)
設(shè)與1相連且小于已有經(jīng)驗(yàn)的結(jié)點(diǎn)集合記為S
1.,很容易想到一個(gè)暴力做法，就是對(duì)所有小于當(dāng)前經(jīng)驗(yàn)值的遍歷一遍，看是否可以擴(kuò)展樹(shù)的大小，沒(méi)有一個(gè)結(jié)點(diǎn)可以更新，直接輸出答案，有一個(gè)結(jié)點(diǎn)可以更新，就可以再次進(jìn)入循環(huán)遍歷一遍S集合中的所有元素，但是這個(gè)方法會(huì)tle,故要優(yōu)化。
2.我們換一個(gè)思考方式，把與1相連的結(jié)點(diǎn)但是還沒(méi)有加入到集合S中的集合，記錄到一個(gè)小根堆中，每次從小根堆中取出最小的闖關(guān)所需要經(jīng)驗(yàn)值，看是否可以加入到集合中，可以加入集合中接著循環(huán)判斷，不可以直接跳出循環(huán)輸出答案
Ac_code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
//v[i]:通過(guò)第i關(guān)所需要的最低經(jīng)驗(yàn)值
//w[i]:通過(guò)第i關(guān)可以獲得的經(jīng)驗(yàn)值
int w[N],v[N];
vector<int>g[N]; //g[x]:x結(jié)點(diǎn)可以到達(dá)的所有結(jié)點(diǎn)
int bfs(){
//first：通過(guò)第second關(guān)的最低經(jīng)驗(yàn)值
//second:結(jié)點(diǎn)編號(hào)
priority_queue<PII,vector<PII>,greater<PII>>heap; //小根堆
heap.push({v[1],1});
int res=0;
LL W=m; //一開(kāi)始的經(jīng)驗(yàn)值
while(heap.size()){
PII temp=heap.top(); heap.pop();
int id=temp.y,min_v=temp.x;
if(min_v>W) break; //最低經(jīng)驗(yàn)值都比已有經(jīng)驗(yàn)值大，直接break
W+=w[id]; //累加經(jīng)驗(yàn)
res++; //闖關(guān)++
for(int y:g[id]) heap.push({v[y],y}); //代表挑戰(zhàn)的關(guān)入堆
}
return res;
}
void solve(){
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++){
int fa; scanf("%d%d%d",&fa,w+i,v+i);
g[fa].push_back(i);
}
cout<<bfs()<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}5.串門(mén)【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
4
1 2 3
1 3 4
1 4 5output:
15
思路：dfs求樹(shù)的直徑
簡(jiǎn)述題意：n個(gè)節(jié)點(diǎn)，n-1條邊，選擇一個(gè)結(jié)點(diǎn)為起點(diǎn)，輸出訪問(wèn)所有結(jié)點(diǎn)的最小值
1.直接求很難，那么換個(gè)思路，每個(gè)結(jié)點(diǎn)必須遍歷一次，那么每條邊至少加一次，每條邊加一次的總和記為sum,我們的目的就是讓一些邊遍歷兩次或者兩次以上的可能盡量小，那么找出最長(zhǎng)第一條路徑max_len（注意是權(quán)值最大），讓它只遍歷一次,就能保證答案最小，那么sum-max_len就是遍歷兩次的邊權(quán)值，答案就是sum+sum-max_len。
2.那么這么求sum,max_len呢？sum很好求，直接累加邊權(quán)值即可，max_len其實(shí)是最大的一條路徑(樹(shù)的直徑)，那么就轉(zhuǎn)化求樹(shù)的直徑即可。
3.求樹(shù)的直徑（最大的一條路徑），這里有通解，就是隨便找一個(gè)點(diǎn)，dfs一遍記錄最大路徑的值與結(jié)點(diǎn)編號(hào)，在用第一次記錄的結(jié)點(diǎn)編號(hào)第二次dfs,更新最大的max_len即可。（這里感興趣證明的可以查樹(shù)的直徑，還有注意一點(diǎn)就是樹(shù)的直徑不能有負(fù)權(quán)邊，不然不能用此方法求解，要數(shù)形dp才能求解）
Ac_code：C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
vector<PII>g[N]; //first:結(jié)點(diǎn)編號(hào)，second:權(quán)值
int start; //起始結(jié)點(diǎn)
LL max_len; //最長(zhǎng)的一條路徑
//dfs代碼較短，第一次接觸可能有點(diǎn)難，不過(guò)可以慢慢理解
void dfs(int x,int fa,LL val){
if(max_len<val) max_len=val,start=x; //全局更新答案
for(PII k:g[x]){
if(k.x==fa) continue; //不要往回更新
dfs(k.x,x,val+k.y);
}
}
void solve(){
scanf("%d", &n);
LL sum=0;
for(int i=1;i<n;i++){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
g[a].push_back({b,c});
g[b].push_back({a,c});
sum+=c;
}
dfs(1,-1,0); //找起點(diǎn)
dfs(start,-1,0); //用起點(diǎn)找到最長(zhǎng)的路徑
cout<<sum+sum-max_len<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}6.神奇數(shù)【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
100
130output:
5思路：數(shù)位dp
簡(jiǎn)述題意：求[l,r]中神奇樹(shù)的個(gè)數(shù)，神奇數(shù)的定義假設(shè)有n（n>=2）位數(shù) s1,s2..sn,對(duì)數(shù)位s1+s2+..+sn-1的總和為sum,sum%sn==0則為神奇數(shù)，10<=-l<=r<=1e200
數(shù)位初學(xué)者入門(mén)這里推薦靈神：2376. 統(tǒng)計(jì)特殊整數(shù) - 力扣（LeetCode）
1.數(shù)位dp的一般求法[1,x]中合法的數(shù)，但是我們要求的是[l,r],這里采用前綴和思想pre[r]-pre[l-1]
2.這里采用記憶化搜索，一般用4個(gè)參數(shù)，本題的4個(gè)參數(shù)為枚舉到了第pos位,前面總和為sum,是否有限制limit，是否有前導(dǎo)0用num
3.枚舉到最后一位時(shí)，枚舉最后一位可以填那些數(shù)，滿足記錄合法數(shù)返回即可
Ac_code:C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,m;
int a[N];
string s;
//f[pos][sum]:枚舉到了第pos位，前pos-1位的總和為sum,且沒(méi)有限制的合法數(shù)
//200個(gè)9=200*9，這里多開(kāi)7個(gè)
int f[207][1807];
int dfs(int pos,int sum,bool limit,bool num){
int up=limit?s[pos]-'0':9;
if(pos==(int)s.size()-1){
int cnt=0; //記錄合法數(shù)
for(int i=1;i<=up;i++) //枚舉最后一位填什么
cnt+=sum%i==0;
return cnt;
}
if(num&&!limit&&f[pos][sum]!=-1) return f[pos][sum];
int res=0;
//只有兩位數(shù)了，就不能刪除了
//要不然可以刪除最高一位
if(pos<(int)s.size()-2&&!num) res=dfs(pos+1,0,false,false);
for(int i=num?0:1;i<=up;i++)
res=(res+dfs(pos+1,sum+i,limit&&i==up,true))%mod1;
if(num&&!limit) f[pos][sum]=res; //記憶化
return res;
}
int check(string s){
int sum=0,last=s.back()-'0';
if(last==0) return 0; //最后一位不能為0
for(int i=0;i<s.size()-1;i++) sum+=s[i]-'0';
return sum%last==0?1:0;
}
void solve(){
string l,r; cin>>l>>r;
s=l;
memset(f,-1,sizeof f);
int left=dfs(0,0,true,false);
s=r;
memset(f,-1,sizeof f);
int right=dfs(0,0,true,false);
//前綴和思想，但是多減了一個(gè)l,故要加上check(l)
int ans=((right-left+check(l))%mod1+mod1)%mod1;
cout<<ans<<endl;
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}7.小藍(lán)的疑問(wèn)【算法賽】 - 藍(lán)橋云課 (lanqiao.cn)
題面：
input:
7 4
2 9 8 7 8 6 4
1 2
1 3
2 4
2 6
3 5
3 7
1 2
1 1
3 1
2 1output:
8
9
8
7思路：
簡(jiǎn)述題意：給你一顆以1為根的有向樹(shù)，q個(gè)詢問(wèn)，對(duì)于每個(gè)詢問(wèn)x,k,輸出x結(jié)點(diǎn)為根x記為第0層，輸出所有第k層結(jié)點(diǎn)的最大值
1，一個(gè)簡(jiǎn)單暴力的方法就是，對(duì)每個(gè)詢問(wèn)bfs求除第k層結(jié)點(diǎn)的值，取max輸出即可
TLE_code:C++(超時(shí)代碼，過(guò)了60%的樣例)
打藍(lán)橋杯的話，可以獲得60%的分，也建議學(xué)一學(xué)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
int const mod1=998244353;
int const mod2=1e9+7;
int const N=2e5+7;
int const INF=0x3f3f3f3f;
int T;
int n,q;
int w[N];
vector<int>g[N];
//求以k為根的第k層結(jié)點(diǎn)的最大值
int bfs(int start,int k){
int res=-1;
queue<PII>q; //first:結(jié)點(diǎn)編號(hào)，second:層數(shù)
q.push({start,0});
while(q.size()){
PII temp=q.front(); q.pop();
int id=temp.x,depth=temp.y;
for(int y:g[id]){
if(depth==k-1) res=max(res,w[y]);
else q.push({y,depth+1});
}
}
return res;
}
void solve(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",w+i);
for(int i=1;i<n;i++){
int a,b; scanf("%d%d",&a,&b);
g[a].push_back(b);
}
while(q--){
int a,b; scanf("%d%d",&a,&b);
printf("%d\n",bfs(a,b));
}
}
void init(){
}
int main()
{
//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
T=1;
//cin>>T;
//scanf("%d",&T);
init();
while(T--){
solve();
}
return 0;
}最后一題正解后續(xù)更新.....感覺(jué)寫(xiě)不出正解了（更改博客時(shí)間2023/10/29）
描述有誤，或者描述不好理解，歡迎指正文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-737615.html
希望對(duì)你有用，歡迎關(guān)注，點(diǎn)贊，收藏文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-737615.html
到了這里，關(guān)于藍(lán)橋杯1024第 2 場(chǎng)算法雙周賽題解+Ac代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[LeetCode周賽復(fù)盤(pán)] 第 111 場(chǎng)雙周賽20230819](https://imgs.yssmx.com/Uploads/2024/02/672417-1.png)
![[LeetCode周賽復(fù)盤(pán)] 第 102 場(chǎng)雙周賽20230415](https://imgs.yssmx.com/Uploads/2024/01/415268-1.png)
