藍橋杯歷年真題題解

1.軌道炮（數學+模擬）

#include <iostream>
#include <map>
using namespace std;
const int N=1010;
int x[N],y[N],v[N];
char d[N];
int main()
{int n;int ans=-100;cin>>n;for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>v[i]>>d[i];for(int t=0;t<=1000;t++){map<int,int> col,row; //col代表每一列上有幾個點，row代表每一行上有幾個點for(int i=1;i<=n;i++){if(d[i]=='R') //如果是向右移的話，只有橫坐標會發生改變，也就是不同的列，縱坐標不會隨時間的改變而改變{col[x[i]+v[i]*t]++;row[y[i]]++;}if(d[i]=='L') //左邊同理{col[x[i]-v[i]*t]++;row[y[i]]++;}if(d[i]=='U') //如果是向上移的話，只有縱坐標會發生改變，也就是不同的行，橫坐標不會隨時間的改變而改變{col[x[i]]++;row[y[i]+v[i]*t]++;}if(d[i]=='D') //向下同理{col[x[i]]++;row[y[i]-v[i]*t]++;}}for(auto item :col){ans=max(ans,item.second);}for(auto item:row){ans=max(ans,item.second); }}cout<<ans<<endl;return 0;
}

2.抓娃娃（貪心+數學）

#include <iostream>
#include <algorithm>
using namespace std;
/*
題目中提到max(ri-li)<=min(Ri-Li)，說明最小的區間長度都大于最大的線段長度，所以只要線段的中點在區間的范圍內，
這個區間就能夠包含這條線段，所以先對所有線段的中點進行排序，再找第一個大于區間左端點的線段，
然后找第一個大于區間右端點的線段，將兩個線段的下標索引相減，中間的所有線段都能夠滿足條件
*/
const int N=100010;
double c[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){float l,r;cin>>l>>r;}sort(c+1,c+n+1);for(int i=1;i<=m;i++){int l,r;cin>>l>>r;int left=lower_bound(c+1,c+n+1,l)-c;int right=upper_bound(c+1,c+n+1,r)-c;cout<<right-left<<endl;}return 0;
}

3.彈珠堆放（數學）

#include <iostream>
using namespace std;
//一定要先判斷，再++
int main()
{int n=1;long long sum=0;while(1){long long tmp=0;for(long long i=1;i<=n;i++)tmp+=i;sum+=tmp;if(sum>20230610){cout<<n-1<<endl;break;}if(sum==20230610){cout<<n<<endl;break;}n++;}return 0;
}

?4.擴散（BFS）

#include <iostream>
#include <queue>
using namespace std;
/*
一個基礎的BFS，需要通過距離長短來代替時間
同時為了防止數組下標出現負數，需要先加上2020偏移量，否則會產生越界
需要在devc++中運行得到結果，在藍橋評測系統中會報出運行錯誤（爆內存）
*/
typedef pair<int,int> PII;
const int N=7000;
bool st[N][N];
int dis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int main()
{queue<PII> q;q.push({0+2020,0+2020});q.push({2020+2020,11+2020});q.push({11+2020,14+2020});q.push({2000+2020,2000+2020});st[0+2020][0+2020]=true;st[2020+2020][11+2020]=true;st[11+2020][14+2020]=true;st[2000+2020][2000+2020]=true;while(q.size()){PII tmp=q.front();q.pop();for(int i=0;i<4;i++){int a=tmp.first+dx[i];int b=tmp.second+dy[i];if(st[a][b]==false){if(dis[tmp.first][tmp.second]<2020){dis[a][b]=dis[tmp.first][tmp.second]+1;q.push({a,b});st[a][b]=true;}}}}int count=0;for(int i=0;i<7000;i++){for(int j=0;j<7000;j++){if(st[i][j]) count++;}}cout<<count<<endl;return 0;
}

5.班級活動（貪心+分情況討論）

#include <iostream>
#include <map>
using namespace std;
/*思路：先用map統計出每個同學的id出現的次數，題目中要求任意兩個同學id相同，因此map中每個元素的值為2才符合要求因此，可以把2當作平均值，比這個平均值大的可以補給平均值小的上面，因此分三種情況（1）如果比2大的數量等于比2小的數量，那么正好可以用多的補給少的（2）如果比2小的數量多于比2大的數量，那么在多補少之后，小于2的可以任意兩兩組合湊成一對，所以只需要剩余的一半（3）如果比2大的數量多于比2小的數量，那么多補少之后，所有多的都需要移動，因此不需要除以2
*/
const int N=100010;
int a[N];
map<int,int> mp;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}int upper_count=0,lower_count=0;int ans=0;for(auto item:mp){if(item.second>2) upper_count+=(item.second-2);if(item.second==2) continue;if(item.second<2) lower_count+=(2-item.second);}//cout<<upper_count<<" "<<lower_count<<endl;if(upper_count==lower_count){ans=upper_count;}else if(upper_count>lower_count){ upper_count=upper_count-lower_count;ans=lower_count;//if(upper_count%2==0)ans+=(upper_count);//else ans+=(upper_count)/2+1;} else{lower_count=lower_count-upper_count;ans=upper_count;if(lower_count%2==0)   ans+=(lower_count)/2;else ans+=(lower_count)/2+1;}cout<<ans<<endl;return 0;
}

6.青蛙過河（前綴和+二分+貪心）

#include <iostream>
using namespace std;
/*思路：很明顯需要二分，來回走x次可以看成是走2*x次結論：如果能夠使情況成立，那么長度為y的區間[l,r]，全程需要經過這個區間2*x次反證：如果可能存在一個長度大于y的區間，使青蛙能夠不經過這個區間，那么跳躍能力至少大于y，與題意矛盾
*/
const int N=100010;
long long s[N];
int n,x;
bool check(int mid)
{for(int i=1;i<=n-mid;i++){if(s[i+mid-1]-s[i-1]<2*x) return false; //這里注意要減1，因為存在岸邊的概念，相當于從第0個位置開始跳而并非第一個}return true;
}
int main()
{cin>>n>>x;for(int i=1;i<=n;i++){int t;cin>>t;s[i]=s[i-1]+t;}int l=1,r=n;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;  //如果發現可以的話，看有沒有可能有更小的可能的解else l=mid+1;}cout<<l<<endl;return 0;
}

?7.串的處理（字符串處理）

#include <iostream>
using namespace std;
/*要點:  1.讀入有空格的字符串要用getline(cin,字符串名)的形式2. 大寫字母A的ASCII碼值比小寫字母A的ASCII碼值少32，這個關系要記得3. string中的erase函數 erase(pos,count)  從pos位置開始，刪除count個字符4. string中的insert函數 insert(pos,str)  在pos位置開始插入一個字符串
*/
int main()
{string str;getline(cin,str);for(int i=0;i<str.size();i++){if(i==0&&str[i]>='a'&&str[i]<='z') str[i]-=32;if(str[i]==' '){  //如果遇到的是空格，那么就移除，直到剩一個空格int j=i+1;while(str[j]==' ') str.erase(j,1);if(str[j]>='a'&&str[j]<='z') str[j]-=32; //如果不是空格了，說明遇到下一個單詞的首字母，要變成大寫}if(str[i]>='0'&&str[i]<='9'&&str[i+1]>='a'&&str[i+1]<='z') //如果遇到數字且下一個是字母，就需要添加下劃線str.insert(i+1,"_");if(str[i]>='0'&&str[i]<='9'&&((str[i-1]>='A'&&str[i-1]<='Z')||(str[i-1]>='a'&&str[i-1]<='z'))) //如果遇到數字且上一個是字母，就需要添加下劃線str.insert(i,"_");}cout<<str<<endl;return 0;
}

8.移動字母（BFS，八數碼簡化題）

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(string end)
{string start="ABCDE*";queue<string> q;unordered_map<string,int> mp;q.push(start);mp[start]=0;while(q.size()){auto tmp=q.front();q.pop();if(tmp==end) return 1;int pos=tmp.find('*'); //找到*在字符串中的位置int x=pos/3,y=pos%3; //還原回去的位置for(int i=0;i<4;i++){int a=x+dx[i];int b=y+dy[i];if(a>=0&&a<2&&b>=0&&b<3){swap(tmp[pos],tmp[a*3+b]);if(mp.count(tmp)==0){q.push(tmp);mp[tmp]=1;}swap(tmp[pos],tmp[a*3+b]);}}}return 0;
}
int main()
{int T;cin>>T;while(T--){string ends;cin>>ends;cout<<bfs(ends)<<endl;}  return 0;
}

9.日志統計（滑動窗口+雙指針）

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
/* 思路：滑動窗口+排序先按照時間進行排序,因為大小是固定的，所以用滑動窗口，讓i往前移，按時間順序遍歷整個數組每次移動之前判斷一下j到i的距離是否小于d如果j有不符合條件的，那么應該在滑動窗口中清除掉對應的值每次判斷當前這條記錄對應的id號的帖子是否是熱帖，根據cnt[]來判斷，cnt由于滑動窗口保證其是動態變化的
*/
const int N=100010;
typedef pair<int,int> PII;
PII a[N];
bool st[N];
int cnt[N];
int main()
{int n,d,k;cin>>n>>d>>k;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;sort(a+1,a+n+1);int j=1;for(int i=1;i<=n;i++){cnt[a[i].second]++;while(a[i].first-a[j].first>=d){cnt[a[j].second]--;j++;}if(cnt[a[i].second]>=k) st[a[i].second]=true;}for(int i=0;i<=100000;i++)if(st[i]) cout<<i<<endl;return 0;
}

?10.十進制轉換為n進制（短除法）

#include <iostream>
#include <algorithm>
using namespace std;
//十進制轉換成其他進制：短除法
//下面寫法是十進制轉換為b進制的通用寫法
char get(int x)
{if(x<=9) return x+'0';else return x-10+'A';
}
int base(int n,int b)
{string num="";while(n){num+=get(n%b);n/=b;}reverse(num.begin(),num.end());return num.size();
}
int main()
{cout<<base(2022,2)<<endl;return 0;
}

11.卡牌（二分 注意數據范圍）

#include <iostream>
using namespace std;
const int N=200010;
long long a[2*N],b[2*N];
long long n,m;
bool check(long long mid)
{long long sum=0;for(int i=1;i<=n;i++){if(a[i]<mid){long long need=mid-(long long)a[i];if(need>b[i]) return false;else sum+=(long long)need;}if(sum>m) return false;}return true;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];long long l=0,r=49000000000;while(l<r){long long mid=(long long)(l+r+1)>>1;if(check(mid)) l=mid; //如果成功，看有沒有有可能能湊成更多的牌else r=mid-1;}cout<<r<<endl;return 0;
}

12.砍竹子（大根堆，貪心，區間合并）

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
/*
預備知識：大根堆和小根堆的STL寫法需要引入頭文件#include <queue>priority_queue<int> q  //默認大根堆 堆頂元素是堆中最大的priority_queue<int,vector<int>,greater<int>> q  //默認小根堆 堆頂元素是堆中最小的
*/
/*思路：將每一個值當作一個節點，這個與正常大根堆解決問題的區別在于，這個需要判斷是不是連續區間，也就是說，需要動態記錄每一個值所在的左右區間，并且在每次操作時檢查是否有區間可以合并，如果有，這些區間需要進行合并直到最大的元素是1，說明全部的元素都被置為1了
*/
typedef long long LL;
struct node{LL val,l,r;  //節點值，區間左端點，區間右端點
};
bool operator<(node a,node b)
{return a.val==b.val?a.l<b.l:a.val<b.val; //返回值較大的那個，如果值相同，返回左端點大的那個
}
int main()
{LL n=0,ans=0;priority_queue<node> q;cin>>n;for(int i=1;i<=n;i++){LL x;cin>>x;q.push({x,i,i});  //點一開始左右區間都是自己}while(q.top().val!=1){node tmp=q.top();  //這里拿出的是值最大，而且左端點也是最大的一個點的值（相當于向從右往左進行合并）q.pop();node sd;while(!q.empty()){//接下來這個點能夠合并的前提是這個點的值相同，并且兩個點的區間能夠重疊sd=q.top();  if(sd.val==tmp.val&&sd.r>=tmp.l-1) q.pop(),tmp.l=sd.l; //更新tmp的左端點即可else break;}LL h=sqrtl(tmp.val/2+1);  q.push({h,tmp.l,tmp.r});  //新高度肯定要重新入隊，值正常計算，只是區間的左右端點有可能會發生變化ans++;}cout<<ans<<endl;return 0;
}

13.迷宮與陷阱（BFS）

#include <iostream>
#include <queue>
using namespace std;
//有無敵狀態可以隨便走，沒有無敵狀態只能往沒標記過的地方走
//而且無敵狀態不能累加，這里題目沒有明確說明
const int N=1010;
char g[N][N];
bool st[N][N];
int dis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,k;
struct node{int x,y,time;
};
int bfs(int x,int y,int time)
{queue<node> q;q.push({x,y,time});st[x][y]=true;dis[x][y]=0;while(q.size()){auto tmp=q.front();q.pop();if(tmp.x==n&&tmp.y==n) return dis[tmp.x][tmp.y];for(int i=0;i<4;i++){int a=tmp.x+dx[i];int b=tmp.y+dy[i];if(a<1&&a>n&&b<1&&b>n) continue;  //如果越界，肯定不行if(g[a][b]=='#') continue;  //如果遇到了墻，那么肯定不能走if(g[a][b]=='X'&&tmp.time==0) continue;  //如果遇到了陷阱，如果沒有無敵時間，也不能走if(g[a][b]=='%') //如果遇到了道具，只有第一次是有效的，將其變成.{int now_time=k;g[a][b]='.';st[a][b]=true;q.push({a,b,now_time});dis[a][b]=dis[tmp.x][tmp.y]+1;}else if(g[a][b]=='.'&&tmp.time>0) //如果是.并且在無敵狀態下，需要將無敵狀態的時間減1,無敵狀態下隨便走{int now_time=0;if(tmp.time>0) now_time=tmp.time-1; q.push({a,b,now_time});st[a][b]=true;dis[a][b]=dis[tmp.x][tmp.y]+1;}else if(g[a][b]=='.'&&tmp.time==0&&!st[a][b]) //如果是. 并且不是無敵狀態 那么就要看這個點是否被走過{q.push({a,b,0});st[a][b]=true;dis[a][b]=dis[tmp.x][tmp.y]+1;}else if(g[a][b]=='X'&&tmp.time>0) ///陷阱有可能被多次走，不必標記{int now_time=tmp.time-1;q.push({a,b,now_time});dis[a][b]=dis[tmp.x][tmp.y]+1;}}}return -1;
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>g[i][j];cout<<bfs(1,1,0)<<endl;return 0;
}

14.重新排序（差分）

#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
const int N=100010;
int a[N],b[N];
void insert(int l,int r)
{b[l]+=1;b[r+1]-=1;
}
int main()
{long long old_sum=0,new_sum=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>m;for(int i=1;i<=m;i++){int l,r;cin>>l>>r;insert(l,r);}for(int i=1;i<=n;i++) b[i]=b[i-1]+b[i];for(int i=1;i<=n;i++) old_sum+=(long long)a[i]*b[i];sort(b+1,b+n+1);sort(a+1,a+n+1);for(int i=1;i<=n;i++) new_sum+=(long long)a[i]*b[i];//cout<<old_sum<<" "<<new_sum<<endl;cout<<new_sum-old_sum<<endl;return 0;
}

?15.123（二分+前綴和）

#include <iostream>
using namespace std;
/*思路：右區間最多10^12，說明項數最多是10^12 數列為1  1,2  1,2,3  1,2,3,4  所以項數和可以用等差公式來求，即(n+1)*n/2<=10^12 解得數組大小開到1500000足夠a[i]代表第i個區間的項數，可以用前綴和得出a[i]=a[i-1]+is[i]為前i個區間的和，有s[i]=s[i-1]+a[i] （因為第i個區間內所有的元素和恰好可以用a[i]來表示）這里的a[i]很特殊，因為a[i]不光代表各個區間項數的前綴和，還代表每個區間內元素的前綴和所以對于任何一個位置pos，一定是在j+1這個區間內，所以可以分成兩部分來求一部分是前j個區間的元素和，還有就是pos在j+1這個區間中的相對位置得出的元素和
*/
typedef long long ll;
const int N=1414215;
ll a[N],s[N];
ll presum(ll pos)
{ll l=0,r=N;while(l<r){ll mid=(ll)(l+r+1)/2;if(a[mid]>pos) r=mid-1;else l=mid;}return s[l]+a[pos-a[l]];
}
int main()
{int T=0;cin>>T;for(ll i=1;i<=N;i++) a[i]=a[i-1]+(ll)i;for(ll i=1;i<=N;i++) s[i]=s[i-1]+(ll)a[i];while(T--){ll l,r;cin>>l>>r;cout<<presum(r)-presum(l-1)<<endl;}return 0;
}

16. 重復字符串（貪心）

#include <iostream>
#include <map>
using namespace std;
int main()
{string s;int k=0,ans=0;cin>>k;cin>>s;if(s.size()%k!=0){cout<<-1<<endl;return 0;}for(int i=0;i<s.size()/k;i++){map<char,int> mp;int start=i;while(start<s.size()){mp[s[start]]++;start+=s.size()/k;}int max_need=0;for(auto item:mp){max_need=max(max_need,item.second);}ans+=k-max_need;}cout<<ans<<endl;return 0;
}

17.挖礦（前綴和）

#include <iostream>
using namespace std;
const int N=1000010;
int l[N],r[N];
/*思路：維護兩個前綴和數組，分別表示從0點分別向左向右能挖到多少，后在分別枚舉向左向右挖的數，取max就行先向右走m以內的距離，再算能否再向左走，如果能，再加上向左走的那部分的礦石數另外一側同理
*/
int main()
{int n=0,m=0,f=0,ans=0;cin>>n>>m;for(int i=1;i<=n;i++){int pos;cin>>pos;if(pos>0) r[pos]++;else if(pos<0) l[abs(pos)]++;else if(pos==0) f=1;}for(int i=1;i<=N;i++) l[i]+=l[i-1];for(int i=1;i<=N;i++) r[i]+=r[i-1];for(int i=1;i<=m;i++){int sum=r[i];if(m-2*i>0) sum+=l[m-2*i];ans=max(ans,sum);sum=l[i];if(m-2*i>0) sum+=r[m-2*i];ans=max(ans,sum);}cout<<ans+f<<endl;return 0;
}

18.充電能量（格式化輸入）

#include <iostream>
using namespace std;
int main()
{int sum=0;int T,h,m,s,oldu,oldi,u,i,start_time,end_time;cin>>T;T--;scanf("%d:%d:%d",&h,&m,&s);scanf("%d%d",&oldu,&oldi);start_time=h*3600+m*60+s;while(T--){//以格式化的形式讀入scanf("%d:%d:%d",&h,&m,&s);scanf("%d%d",&u,&i);//都轉換成秒數end_time=h*3600+m*60+s;int length=end_time-start_time;sum+=length*oldu*oldi;oldu=u;oldi=i;start_time=end_time;}cout<<sum<<endl;return 0;
}

19.拔河（STL+前綴和+區間處理）

#include <iostream>
#include <set>
using namespace std;
/*思路：將所有區間的和記錄到multiset中，multiset中可以有重復的元素，并且是自動排序的然后遍歷每一個區間，這里遍歷第一個區間的右端點，因為后面要在multiset中找絕對值之差最小的另外一個區間和所以兩個區間不能有重疊（如果有重疊，說明這個人既在第一個隊，又在第二個隊，不符合題意）所以要刪掉以第一個區間右端點為左端點的區間接下來枚舉第一個區間的左端點，這樣能夠確定第一個區間，也就能拿出來區間和，然后去multiset中找第一個大于等于這個和的，說明找到的是離這個和最近的，當然不一定比它大，也有可能比它小所以如果找到的這個不是第一個，說明往前還有。這個和前面的元素與這個和的差的絕對值可能更小，遍歷完所有第一個區間即可這里需要注意的是，為什么只刪掉以第一個區間右端點為第二個區間左端點的第二個區間，因為除了這種情況其他情況都可以看作是這兩個區間有公共的元素，可以同時加上或減去元素，不影響絕對值的差只有這種情況會造成兩個區間共用一人的情況出現，其他情況雖然也會造成區間重疊，但本質上與都減掉相同只有這個情況需要手動處理
*/
typedef long long ll;
const int N=1010;
ll a[N],s[N];
ll ans=1e9;
multiset<ll> ms;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];for(int i=1;i<=n;i++) //將所有區間和全部放到multiset中for(int j=i;j<=n;j++)ms.insert(s[j]-s[i-1]);for(int i=1;i<=n;i++) //枚舉第一個區間的右端點{//刪掉以第一個區間右端點為左端點的區間for(int j=i;j<=n;j++){ll tmp=s[j]-s[i-1];ms.erase(ms.find(tmp));}//枚舉第一個區間的左端點，通過兩個端點來確定第一個區間for(int j=1;j<=i;j++){ll tmp=s[i]-s[j-1];auto pos=ms.lower_bound(tmp);  //lower_bound函數是找到第一個大于等于目標值元素if(pos!=ms.end()) ans=min(ans,abs(*pos-tmp));  //如果找到了if(pos!=ms.begin()){pos--;ans=min(ans,abs(*pos-tmp));}}}cout<<ans<<endl;return 0;
}

20.最大數字（DFS）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N,ans;
string s;
vector<string> vec; 
int A,B;
void dfs(int level,int a,int b)if(level==s.size()){vec.push_back(s);//cout<<s<<endl;return;}char stmp=s[level];int tmp=s[level]-'0';if(A>=a+9-tmp){s[level]='9';dfs(level+1,a+9-tmp,b);s[level]=stmp;}if(B>=b+tmp+1){s[level]='9';dfs(level+1,a,b+tmp+1);s[level]=stmp;}if(A<a+9-tmp&&B<b+tmp+1){s[level]=s[level]+A-a;dfs(level+1,A,b);s[level]=stmp;}}
int main()
{cin>>N>>A>>B;s=to_string(N);dfs(0,0,0);string max_ans="0";for(auto item:vec){if(item>=max_ans) max_ans=item;}// cout<<s<<endl;cout<<max_ans<<endl;return 0;
}

?21.掃地機器人（二分）

#include <iostream>
#include <algorithm>
using namespace std;
/*思路：二分時間，每個機器人能走的格子數是時間/2，記為cnt每個機器人先往左邊看上一個空白的位置到這個機器人所在位置是否大于機器人能走的最大格子數如果不大于的話，說明機器人往左清掃完之后，還有剩余可以往右清掃如果左邊已經沒有需要被清掃的格子，那么機器人可以直接一直往右清掃cnt個格子最后看一下是不是所有的格子都已經被清掃過
*/
const int N=100010;
int a[N];
bool st[N];
int n,k;
bool check(int mid)
{int cnt=mid/2;int blank=1;for(int i=1;i<=k;i++){if(a[i]>blank){if(a[i]-blank>cnt) return false;else {blank=a[i]+cnt-(a[i]-blank)+1;while(st[blank]) blank++;}}else if(a[i]<blank){blank=a[i]+cnt+1;while(st[blank]) blank++;}}if(blank<=n) return false;return true;
}
int main()
{cin>>n>>k;for(int i=1;i<=k;i++){cin>>a[i];st[a[i]]=true;}sort(a+1,a+k+1);int l=0,r=N*2;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;return 0;
}

22.迷宮（BFS+記錄路徑）

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;int g[30][50] = {
{0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0},
{0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1},
{0,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1},
{0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
{1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,1,1},
{0,0,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0},
{1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0},
{0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,0,1},
{1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0},
{0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1},
{1,1,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,1},
{1,0,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,0},
{1,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0},
{1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,1,0,1,0,0,1},
{0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,0,1},
{1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,1,0},
{0,0,0,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1},
{1,0,1,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1},
{0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0},
{0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0},
{1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0},
{0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,0,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1},
{1,0,0,0,0,0,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0},
};PII father[30][50];
vector<char> vec;
//上下左右方向一定要注意
int dx[4] = {1,0,0,-1},dy[4] = {0,-1,1,0};
bool st[30][50];
int dis[30][50];void bfs() {queue<PII> q;q.push({0, 0});st[0][0] = true;father[0][0] = {-1, -1}; // 起點的父節點設為無效，一定要做while (!q.empty()) {auto tmp = q.front();q.pop();if (tmp.first == 29 && tmp.second == 49) {int x = 29, y = 49;while (father[x][y].first != -1 && father[x][y].second != -1) {int fx = father[x][y].first;int fy = father[x][y].second;// 計算移動方向int delta_x = x - fx;int delta_y = y - fy;if (delta_x == 1) vec.push_back('D');else if (delta_y == -1) vec.push_back('L'); else if (delta_y == 1) vec.push_back('R');                               else if (delta_x == -1) vec.push_back('U');x = fx;y = fy;}reverse(vec.begin(), vec.end());for (auto c : vec) cout << c;return;}for (int i = 0; i < 4; ++i) {int a = tmp.first + dx[i];int b = tmp.second + dy[i];if (a >= 0 && a < 30 && b >= 0 && b < 50 && !st[a][b] && g[a][b] == 0) {st[a][b] = true;q.push({a, b});father[a][b] = tmp;dis[a][b] = dis[tmp.first][tmp.second] + 1;}}}
}int main() {bfs();return 0;
}

?23.寶石組合（推公式，數學）

?公式推導過程：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*思路：經過推導，S=gcd(Ha,Hb,Hc)，所以只需要找三個數最大公約數最大的，然后字典序最小的即可
*/
const int N=100010;
int cnt[N];  //用于記錄每個數字出現的次數
vector<int> v[N];   //用于記錄以這個數作為公約數對應的候選數
int main()
{int n,m;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;cnt[x]++;  ///記錄這個數出現了多少次m=max(m,x);}//將所有數預處理，這里取最大的，但哪怕取1e5，都不會超時for(int i=1;i<=m;i++)  //枚舉以每個數作為公約數，所有可能的候選數（一定是它的倍數）for(int j=i;j<=m;j+=i) //復雜度為1e5(1e5+1e5/2+1e5/3...)=1e5ln1e5 滿足時間復雜度if(cnt[j]) //枚舉倍數的時候，只有這個數出現過(cnt[j]>0)，才能將其作為候選數{for(int k=0;k<cnt[j];k++){v[i].push_back(j);}}for(int i=m;i;i--)  //從最大的公約數開始枚舉，只要候選數大于3 ，那么就是最大的公約數{if(v[i].size()>=3){sort(v[i].begin(),v[i].end());cout<<v[i][0]<<" "<<v[i][1]<<" "<<v[i][2]<<endl;break;}}return 0;
}

24.路徑之謎（DFS）

#include <iostream>
using namespace std;
typedef pair<int,int> PII;
const int N=22;
const int M=100010;
int g[N][N];
bool st[N][N];
int north[N],west[N];
int a[N],b[N];
PII path[M];
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y,int level)
{for(int i=1;i<=n;i++) if(b[i]>north[i]) return;for(int i=1;i<=n;i++) if(a[i]>west[i]) return;if(x==n&&y==n){for(int i=1;i<=n;i++) if(b[i]!=north[i]) return;for(int i=1;i<=n;i++)if(a[i]!=west[i]) return;for(int i=1;i<level;i++) {int tx=path[i].first;int ty=path[i].second;cout<<g[tx][ty]<<" ";}return;}for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!st[nx][ny]){path[level]={nx,ny};st[nx][ny]=true;b[nx]++,a[ny]++;dfs(nx,ny,level+1);st[nx][ny]=false;b[nx]--,a[ny]--;        path[level]={-1,-1};}}
}
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>west[i];  //自西向東for(int i=1;i<=n;i++) cin>>north[i];   //自北向南int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){g[i][j]=cnt;cnt++;}a[1]++,b[1]++;st[1][1]=true;path[1]={1,1};dfs(1,1,2);return 0;
}

?25.特殊日期（日期類問題模版題）

#include <iostream>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int year,int month,int day)
{if(year==9999&&month==12&&day==31)  return true;return false;
}
int getsum(int n)
{int res=0;while(n){int tmp=n%10;res+=tmp;n/=10;}return res;
}bool is_leap(int year)
{if((year%400==0)||(year%4==0&&year%100!=0)) return true;return false;
}
int get_days(int year,int month)
{if(month==2) return months[2]+is_leap(year);else return months[month];
}void get_next_day(int& year,int& month,int& day)
{day++;if(day>get_days(year,month)){day=1;month++;if(month>12){year++;month=1;}}
}int main()
{int cnt=0;int year=1900,month=1,day=1;while(!check(year,month,day)){get_next_day(year,month,day);if(getsum(year)==getsum(month)+getsum(day)) cnt++;}cout<<cnt<<endl;return 0;
}

26.商品庫存管理（差分+前綴和）

?

#include <iostream>
using namespace std;
/*思路：要在O(n)的時間復雜度內完成 首先先假設所有操作全部執行，計算出每個商品的庫存量然后思考，如果不執行某個操作后，商品的庫存量變為0，那么說明，這個商品的庫存量只能為1所以我們統計庫存量為1的商品，只要庫存量為1，就在st數組中將其置1，并將其用另外一個前綴和數組維護同時還會出現另外一種情況，就是某種商品從始至終庫存量一直為0，需要把這類商品單獨處理，也就是ans最后的答案就是給定區間內所有庫存量為1的商品數量加上庫存量一直為0的商品數量
*/
const int N=300010;
int a[N],b[N],l[N],r[N];
int st[N],cnt[N];
int n,m;
void insert(int l,int r)
{a[l]+=1;a[r+1]-=1;
}
int main()
{int ans=0;cin>>n>>m;for(int i=1;i<=m;i++) cin>>l[i]>>r[i];for(int i=1;i<=m;i++) insert(l[i],r[i]); for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i]; for(int i=1;i<=n;i++) if(b[i]==1) st[i]=1;for(int i=1;i<=n;i++) if(b[i]==0) ans++;for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+st[i];for(int i=1;i<=m;i++) cout<<cnt[r[i]]-cnt[l[i]-1]+ans<<endl;return 0;
}

27.迷宮（BFS 反向搜圖）

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cstring>
using namespace std;
/*思路：從終點開始反向bfs，第一次到達某點的距離就是最短的距離
*/
const int N=2010;
typedef pair<int,int> PII;
int dist[N][N];
bool st[N][N];
int n,m,ans;
vector<PII> door[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs()
{queue<PII> q;q.push({n,n});st[n][n]=true;while(q.size()){auto tmp=q.front();q.pop();for(int i=0;i<4;i++){int a=tmp.first+dx[i];int b=tmp.second+dy[i];if(a>=1&&a<=n&&b>=1&&b<=n&&!st[a][b]){q.push({a,b});st[a][b]=true;dist[a][b]=dist[tmp.first][tmp.second]+1;}}for(auto s:door[tmp.first][tmp.second]){if(!st[s.first][s.second]){q.push({s.first,s.second});st[s.first][s.second]=true;dist[s.first][s.second]=dist[tmp.first][tmp.second]+1;}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;door[x1][y1].push_back({x2,y2});door[x2][y2].push_back({x1,y1});}memset(st,0,sizeof(st));memset(dist,0,sizeof(dist));bfs();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans+=dist[i][j];cout<<fixed<<setprecision(2)<<ans*1.0/(n*n)<<endl;return 0;
}

28.最少刷題數（二分+前綴和）

#include <iostream>
using namespace std;
const int N=100010;
/*思路：用cnt數組來維護從1到N刷題數對應的學生數量當一個學生再刷題的數量大于0時，比他小的應該是s[刷題數-1]-s[0-1]-1這里s[0-1]是因為學生的刷題數有可能為0，不能把這種情況忽略掉，而s[-1]正常不存在，即為0而再減去1是因為增加刷題數變為新的刷題數后，要減去自己原來的刷題數（原來的一定比現在的小）而當一個學生再刷題的數量為0時，則不需要減這個1
*/
int a[N],cnt[N],s[N];
int n;
int max_d=-1;
bool check(int mid,int index)
{int tmp=a[index]+mid;if(mid==0){if(s[100000]-s[tmp+1-1]<=s[tmp-1]) return true;return false;}else{if(s[100000]-s[tmp+1-1]<=(s[tmp-1]-1)) return true;return false;    }
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;max_d=max(max_d,a[i]);}s[0]=cnt[0];for(int i=1;i<=N-1;i++) s[i]=s[i-1]+cnt[i];for(int i=1;i<=n;i++){int l=0,r=max_d-a[i];while(l<r){int mid=(l+r)/2;if(check(mid,i)) r=mid;else l=mid+1;}cout<<l<<" ";}return 0;
}

29.保險箱（動態規劃）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*思路：先看這道題的一些性質：操作順序不影響結果。對于某一位操作時，不會影響右邊數位的結果。對于某一位操作次數只在[-9,+9]之間，而且最多進一位，并且最多借一位。也就是說，某一位經過操作后，跟當前位要么相等，要么多10（借了一位），要么少10（進了一位） 即(-10,0,10)三種情況分析DP，用f[i][j]來表示，i代表從i到n的數位都已經相等，j表示向前一位進位，借位還是直接操作后就能得到也就是說，j代表的是對下一位進位方案是j(-1,0,1)的所有方案的集合屬性：最小操作次數從右往左是從n-1到0,0代表最高位，因此答案為f[0][-1],f[0][0],f[0][1]中的最小值但是在寫程序的時候由于下標不存在-1，所以給每個下標都加上1個單位偏移量，變為0,1,2集合劃分方法：以操作次數來劃分，將集合分成若干個子集，即從-9到+9，每個數代表一個子集對每個子集還需要枚舉上一位的進位(或者借位或者不變)是什么，想讓a[i]變成b[i]，需要讓a[i]+操作次數+進位這樣才得到最后的b[i]，每哥子集再劃分成三類，分別表示上一位的進位是1，上一位的進位是0，上一位的進位是-1(借位)所以需要滿足a[i]+操作數k+上一位的進位t-要變成的數b[i]==j*10，才說明這個集合存在,f[i][j]才會被更新更新條件就是前一位（第i+1位）進位是t的狀態f[i+1][t]+|k|(這一次的操作數)時間復雜度3n*19*3
*/
const int N=100010;
int n;
char a[N],b[N];
int f[N][3];int main()
{scanf("%d%s%s",&n,a,b);memset(f,0x3f,sizeof f);  f[n][1]=0;  //代表個位沒有進位，1這里正常是0，代表沒有進位，但由于加1個單位偏移量，所以是1for(int i=n-1;i>=0;i--)for(int j=0;j<3;j++)for(int k=-9;k<=9;k++){if(a[i]+k+t-1-b[i]==(j-1)*10)f[i][j]=min(f[i][j],f[i+1][t]+abs(k));}printf("%d",min({f[0][0],f[0][1],f[0][2]}));return 0;
}

30.求階乘（二分+數學）

#include <iostream>
using namespace std;
/*思路：由于N!數值過大，所以不可能通過計算出N!具體的值來數出末尾的0經發現可得，想湊出0，分解質因子后，只能由2和5這兩個質數來湊出一個10，包含0也就是說，每個數的因子中有可能包含2和5，只需要找出N能湊出多少對2和5，就有多少個0每個數的因子中含有2的可能性大于含有5的可能性，因此只需要找出1到N中每個數可以被拆成幾個5就行最后將所有個數相加得到總和，即為末尾有多少個0但是這樣做時間復雜度為O(N)，題中需要的時間復雜度為O(logN)，所以還需要快速判斷的方法可以通過直接統計5的個數的方式來進行判斷long long是10^19
*/
typedef long long ll;
ll k;
ll check(ll mid)
{ll res=0;while(mid){res+=mid/5;mid/=5;}return res;
}
int main()
{cin>>k;ll l=0,r=1e19;while(l<r){ll mid=(l+r)/2;if(check(mid)>=k) r=mid;else l=mid+1;}if(check(l)==k) cout<<l<<endl;else cout<<-1<<endl;return 0;
}

31.贏球票（模擬 ，DFS+隊列會超空間）

#include <iostream>
#include <cstring>
using namespace std;
/*雖然標簽寫的搜索，但就是大模擬*/
const int N=110;
int a[N];
bool st[N];
int max_ans;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){memset(st,0,sizeof st);int pos=i;  //代表數組的第幾個位置，不代表上面的數int cnt=1;  //數的數int tmp=0;  //總和int cards=0; ///卡片數while(1){if(cnt>n||cards==n) break;if(!st[pos])  //如果這個數沒被用過{if(cnt==a[pos]){cnt=1;tmp+=a[pos];cards++;st[pos]=true;pos++;if(pos==n+1) pos=1;}else{cnt++;pos++;if(pos==n+1) pos=1;}}else{pos++;if(pos==n+1) pos=1;}}max_ans=max(max_ans,tmp);}cout<<max_ans<<endl;return 0;
}

?32.修路（狀態機DP，線性DP）

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2010;
double a[N],b[N];
double f[N][N][2]; //0表示停在A這邊 1表示停在B這邊 
int n,m,d;
double dis(double a,double b)
{return sqrt((ll)(a-b)*(a-b)+(ll)d*d); //注意負負得正
}
int main()
{cin>>n>>m>>d;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];sort(a+1,a+n+1);sort(b+1,b+m+1);//初始化for(int i=1;i<=n;i++) f[i][0][0]=a[i],f[i][0][1]=0x3f3f3f3f;for(int i=1;i<=m;i++) f[0][i][0]=f[0][i][1]=0x3f3f3f3f;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){//最后停在A這邊，有兩種情況，一種是從i-1這個點過來的（一定在A這邊），另外一種是從j斜跨過來的（一定在B這邊）f[i][j][0]=min(f[i-1][j][0]+a[i]-a[i-1],f[i-1][j][1]+dis(a[i],b[j]));//最后停在B這邊，有兩種情況，一種是從j-1這個點過來的（一定在B這邊），另外一種是從i斜跨過來的（一定在A這邊）f[i][j][1]=min(f[i][j-1][1]+b[j]-b[j-1],f[i][j-1][0]+dis(a[i],b[j]));}printf("%.2lf",min(f[n][m][0],f[n][m][1]));return 0;
}

33.2022（01背包）

#include <iostream>
using namespace std;
/*思路：相當于一共有2022個物品，編號從1到2022，每個物品的價值就是它自己的編號設置三維狀態f[i][j][k]，表示從前i個物品中選重量為j的價值為k的所有方案的集合，j不超過10，每個物品的重量是1由于要求互不相同，因此屬于01背包問題，只有選和不選兩種情況如果不選的話，f[i][j][k]=f[i-1][j][k]如果選的話，f[i][j][k]=f[i-1][j-1][k-i] 因為物品的編號i就代表物品的價值，而且k要大于等于i，否則下標越界
*/
long long f[2023][11][2023];
int main()
{for(int i=0;i<=2022;i++) f[i][0][0]=1; //初始化 體積為0且選0個物品只有一種情況那就是什么也不選for(int i=1;i<=2022;i++) //枚舉每個物品{for(int j=1;j<=10;j++) //枚舉選了幾個物品{for(int k=0;k<=2022;k++) //枚舉價值{f[i][j][k]=f[i-1][j][k];if(k>=i) f[i][j][k]+=f[i-1][j-1][k-i];}}}cout<<f[2022][10][2022]<<endl;return 0;
}

34.李白打酒加強版（動態規劃）

#include <iostream>
using namespace std;
/*思路：將時間復雜度控制在O(n^3)之內f[i][j][k]代表遇到i個店，j朵花，有k斗酒的方案數的集合這里在枚舉K的時候要注意，k的值不能超過花的數量，這是這道題的關鍵，如果超過花的數量，那一定喝不完遇到店：f[i][j][k]+=f[i-1][j][k/2] 前提k要能夠整除2遇到花：f[i][j][k]+=f[i][j-1][k+1]答案為f[N][M-1][1] 因為題目中說最后一次遇到的是花且剛好把酒喝完
*/
const int N=110,MOD=1e9+7;
int f[N][N][N];
int main()
{int n,m;cin>>n>>m;f[0][0][2]=1;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=m;k++){if(i>=1&&k%2==0) f[i][j][k]=(f[i][j][k]+f[i-1][j][k/2])%MOD;if(j>=1) f[i][j][k]=(f[i][j][k]+f[i][j-1][k+1])%MOD;}}}cout<<f[n][m-1][1]<<endl;return 0;
}

35.買二贈一（貪心，STL）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
/*
思路：每個物品只能被獲得一次，需要用st數組來記錄，由于大價格的物品肯定需要被購買而不是免費獲得，所以將數組從大到小排序每買兩個物品，就檢查一次會不會免費獲得物品，這里用count來控制，然后使用lower_bound函數，找到第一個不大于P/2的元素如果這個商品已經被買過或者已經被免費獲得過一次，那么就找它的下一個元素，直到找到符合條件的未被買過的元素lower_bound函數正常是找到第一個不小于給定值的數組元素，但由于倒序排列，變成找第一個不大于給定值的數組元素
*/
const int N=500010;
int main()
{int n=0;long long sum=0;int a[N];bool st[N];int count=0;memset(st,0,sizeof st);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1,greater<int>()); //倒序排列for(int i=1;i<=n;i++){if(!st[i]){sum+=a[i];count++;if(count==2){count=0;int pos=lower_bound(a+1,a+n+1,a[i]/2,greater<int>())-a;while(st[pos]) pos++;st[pos]=1; }}}cout<<sum<<endl;return 0;
}

36.背包與魔法（01背包）

#include <iostream>
#include <cstring>
using namespace std;
/*
思路：01背包需要進行一維優化，然后用0或1來表示是否施展過魔法，這樣開f[N][2]這么大的數組就足夠正常集合劃分為選或者不選，在選這一欄里又可以分為不翻倍的選和翻倍的選0表示之前沒有施展過魔法 1表示之前施展過魔法 并且只有背包體積j大于等于v[i]+k時，這次才會有施展魔法的可能性由于01背包進行了降維，所以直接把不選的情況給優化掉了
*/
typedef long long ll;
const int N=10010;
int f[N][2];
int v[N],w[N];
int main()
{int N,M,K;cin>>N>>M>>K;for(int i=1;i<=N;i++) cin>>v[i]>>w[i];for(int i=1;i<=N;i++)for(int j=M;j>=v[i];j--){f[j][0]=max(f[j][0],f[j-v[i]][0]+w[i]);f[j][1]=max(f[j][1],f[j-v[i]][1]+w[i]);if(j>=K+v[i]) f[j][1]=max(f[j][1],f[j-v[i]-K][0]+2*w[i]);}int ans=0;ans=max(f[M][0],f[M][1]);cout<<ans<<endl;return 0;
}

37.子串簡寫（前綴和）

#include <iostream>
using namespace std;
/*
思路：用一個數組a來表示在這個字符之前有多少個開始字符，用a數組來統計然后遍歷串，如果發現當前字符是結束字符，那么只需要知道在這個字符k個單位之前有多少個開始字符，就有多少個答案由于a數組做了這樣的一個功能，所以a數組i-k+1存放的就是代表在這個字符之前有多少個開始字符，加上即可
*/
const int N=500010;
int a[N];
int main()
{int k=0,num=0;string s;char st,ed;cin>>k>>s>>st>>ed;for(int i=0;i<s.size();i++){if(s[i]==st) num++;a[i]=num;}long long ans=0;for(int i=0;i<s.size();i++){if(i>=k-1&&s[i]==ed) ans+=a[i-k+1];}cout<<ans<<endl;return 0;
}

38.最少砝碼（貪心）

#include <iostream>
#include <cmath>
using namespace std;
/*
思路: 當只有1個砝碼的時候，重量區間為[1,1] 只能表示重量為1的物品當有2個砝碼的時候，上一次表示不了的重量是2，所以這一次必須要滿足的一個條件是：選的第二個砝碼和第一個砝碼的組合能表示出來2，所以可選的有1,2,3 因為要找最小砝碼數來表示最大區間所以我們第二個砝碼選擇重量為3 ，區間為[1,4](不能選4，一旦選4，則湊不出來2了)當有三個砝碼時，上一次湊不出來的數是5，所以這一次選的數要能夠湊出來5 可選的數為1-9中任意一個數不能選10 如果選10 則湊不出來5 最小能表示的是6（10-3-1=6）因為還要選最大的區間所以第三個砝碼選9 可以表示出[1,13]內任意一個數可以看出 選砝碼的規律為 1,3,9,..,3^k..而能表示的區間的右端點正好是它們的和，也就是說 只要右端點大于目標值 就代表已經找到
*/
int main()
{long long sum=0;int n=0,cnt=0;cin>>n;while(1){if(sum>=n) break;sum+=pow(3,cnt);cnt++;}cout<<cnt<<endl;return 0;
}

?39.R格式（高精度乘法，高精度加法）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void mul(vector<int>& a,int b)
{int t=0;for(int i=0;i<a.size();i++){t=a[i]*b+t;a[i]=t%10; //因為這里低精度數b只有一位數，所以可以直接這么寫，不需要另外一個vectort/=10;}if(t) a.push_back(t);
}
void add(vector<int>& a,int pos,int b)
{int t=b;for(int i=pos;i<a.size();i++){t=t+a[i];a[i]=t%10; //同樣也是因為b只有一位數，才可以這么做 否則還需要再開一個vector處理t/=10;}if(t) a.push_back(t);
}
int main()
{int n;string d;cin>>n>>d;reverse(d.begin(),d.end());vector<int> A;int pos=d.find('.'); //記錄下小數點的位置，便于最后四舍五入時候用for(int i=0;i<d.size();i++)if(d[i]!='.') A.push_back(d[i]-'0');while(n--) mul(A,2); //這步處理d*(2^n) 將浮點數看成一個高精度數 記錄下小數點的位置 然后正常高精度乘法做if(A[pos-1]>=5) add(A,pos,1); //因為pos-1正好是小數點應該在的位置的前一位數，只需要從后面開始處理即可 所以剛好是posfor(int i=A.size()-1;i>=pos;i--) printf("%d",A[i]);return 0;
}

40.填充（貪心）

#include <iostream>
using namespace std;
/*思路：如果字符相同或者有一個為？，則直接cnt++，并跳過這個字符相當于跳著跳著找
*/
int main()
{int cnt=0;string s;cin>>s;for(int i=0;i<s.size()-1;i++){if(s[i]==s[i+1]||s[i]=='?'||s[i+1]=='?'){cnt++;i++;}}cout<<cnt<<endl;return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/71966.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/71966.shtml
英文地址，請注明出處：http://en.pswp.cn/web/71966.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Pytorch的一小步，昇騰芯片的一大步

Pytorch的一小步，昇騰芯片的一大步

Pytorch的一小步&#xff0c;昇騰芯片的一大步 相信在AI圈的人多多少少都看到了最近的信息&#xff1a;PyTorch最新2.1版本宣布支持華為昇騰芯片&#xff01; 1、 發生了什么事兒&#xff1f; 在2023年10月4日PyTorch 2.1版本的發布博客上&#xff0c;PyTorch介紹的beta版本…
閱讀更多...
嵌入式硬件篇---手柄控制控制麥克納姆輪子

嵌入式硬件篇---手柄控制控制麥克納姆輪子

文章目錄 前言1. 變量定義2. 搖桿死區設置3. 模式檢查4. 搖桿數據處理4.1 右搖桿垂直值&#xff08;psx_buf[7]&#xff09;4.2 右搖桿水平值&#xff08;psx_buf[8]&#xff09;4.3 左搖桿水平值&#xff08;psx_buf[5]&#xff09;4.4 左搖桿垂直值&#xff08;psx_buf[6]&am…
閱讀更多...
阿里千問大模型(Qwen2.5-VL-7B-Instruct)部署

阿里千問大模型(Qwen2.5-VL-7B-Instruct)部署

參考鏈接 知乎帖子 B站視頻 huggingface 鏡像網站&#xff08;不太全&#xff0c;比如 Qwen/Qwen2.5-VL-7B-Instruct就沒有&#xff09; huggingface 5種下載方式匯總 通過huggingface-cli下載模型 不一樣的部分是預訓練權重的下載和demo 首先安裝huggingface_hub pip insta…
閱讀更多...
Jenkins在Windows上的使用（二）：自動拉取、打包、部署

Jenkins在Windows上的使用（二）：自動拉取、打包、部署

&#xff08;一&#xff09;Jenkins全局配置 訪問部署好的Jenkins服務器網址localhost:8080&#xff0c;完成默認插件的安裝后&#xff0c;接下來將使用SSH登錄遠程主機以實現自動化部署。 1. 配置插件 選擇dashboard->Manage Jenkins->plugins 安裝下面兩個插件　　…
閱讀更多...
群暉DS 223 Docker：開啟私有云

群暉DS 223 Docker：開啟私有云

群暉DS 223 Docker&#xff1a;開啟私有云的無限可能 引言 在數據存儲與管理的不斷演進中&#xff0c;群暉 DS 223 憑借其出色的性能和豐富的功能&#xff0c;成為眾多用戶搭建私有云的熱門選擇。而當它與 Docker 技術相遇&#xff0c;猶如為數據管理的舞臺添上了絢麗多彩的燈…
閱讀更多...
git切換版本

git切換版本

git brach 查看本地 剛從git上下載下來 的話 可以通過 git checkout xxxx進行切換 可能一段時間沒有用 而服務器上新建了某些版本 那么需要用 git fetch origin 同步本地與git服務器的分支 然后 創建本地分支xxx 并從服務器拉取xxx git checkout -b xxx origin/xxx…
閱讀更多...
Three.js 進階(燈光陰影關系和設置、平行光、陰影相機)

Three.js 進階(燈光陰影關系和設置、平行光、陰影相機)

本篇主要學習內容 : 燈光與陰影聚光燈點光源平行光陰影相機和陰影計算投射陰影接受陰影 點贊 關注 收藏 學會了 1.燈光與陰影 1、材質要滿足能夠對光有反應 2、設置渲染器開啟陰影計算 renderer.shadowMap.enabledtrue 3、設置光照投射陰影 directionalLight.castShadow …
閱讀更多...
【 ＜一＞ 煉丹初探：JavaWeb 的起源與基礎】之 Tomcat 的工作原理：從啟動到請求處理的流程

【 ＜一＞ 煉丹初探：JavaWeb 的起源與基礎】之 Tomcat 的工作原理：從啟動到請求處理的流程

<前文回顧> 點擊此處查看 合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、Tomcat…
閱讀更多...
【GPT入門】第11課 FunctionCall調用本地代碼入門

【GPT入門】第11課 FunctionCall調用本地代碼入門

【GPT入門】第11課 FunctionCall調用代碼入門 1. 手撕FunctionCall2.代碼3.functionCall的結果 1. 手撕FunctionCall 為了了解&#xff0c;funcationCall底層&#xff0c;手寫一個functionCall多方法&#xff0c;并調用&#xff0c;體驗 思路&#xff1a; 任務&#xff1a;讓…
閱讀更多...
MySQL主從架構配合ShardingJdbc實現讀寫分離

MySQL主從架構配合ShardingJdbc實現讀寫分離

文章目錄 目錄架構搭建讀寫分離pom.xmlfdy-live-user-provider 模塊application.ymlfdy-db-sharding.yamlShardingJdbcDatasourceAutoInitConnectionConfig.java 目錄 架構搭建 基于Docker去創建MySQL的主從架構 讀寫分離 pom.xml <dependency><groupId>mysql…
閱讀更多...
計網面試準備

計網面試準備

正確理解網絡數據傳輸過程 同一路由器的不同接口屬于不同局域網&#xff0c;廣播只能在同一個局域網
閱讀更多...
NLP常見任務專題介紹（1）-關系抽取（Relation Extraction, RE）任務訓練模板

NLP常見任務專題介紹（1）-關系抽取（Relation Extraction, RE）任務訓練模板

?? 關系抽取（Relation Extraction, RE）任務訓練示例 本示例展示如何訓練一個關系抽取模型，以識別兩個實體之間的關系。 1?? 任務描述 目標：從文本中提取兩個實體之間的語義關系，例如 “人物 - 組織”、“藥物 - 疾病”、“公司 - 創始人” 等。輸入：句子 + 標注的實…
閱讀更多...
【技術白皮書】內功心法 | 第二部分 | Telnet遠程登錄的工作原理

【技術白皮書】內功心法 | 第二部分 | Telnet遠程登錄的工作原理

遠程登錄的工作原理 背景介紹遠程登錄遠程登錄的服務模式遠程登錄服務的實現基礎遠程登錄服務的運行模式Telnet服務為什么不被操作系統管理 Telnet協議的原理網絡虛終端&#xff08;NVT&#xff09;結束標示NVT的原理NVT屏蔽差異 背景介紹 絕大多數計算機都是運行多用戶操作系…
閱讀更多...
在 Spring Boot 中實現基于 TraceId 的日志鏈路追蹤

在 Spring Boot 中實現基于 TraceId 的日志鏈路追蹤

1 前言 1.1 什么是 TraceId？ TraceId 是一個唯一的標識符，用于跟蹤分布式系統中的請求。每個請求從客戶端發起到服務端處理，再到可能的多個微服務調用，都會攜帶這個 TraceId，以便在整個請求鏈路中進行追蹤和調試。 1.2 日志鏈路追蹤的意義 日志鏈路追蹤可以幫助開發者…
閱讀更多...
游戲引擎學習第150天

游戲引擎學習第150天

回顧與當天計劃 我們在這里完全不使用任何庫&#xff0c;所以我們完全是引擎和庫免疫的, 正如大家所知道的&#xff0c;我們正在編寫自己的資源處理系統&#xff0c;準確來說&#xff0c;是一個資源加載系統。過去一周我們已經完成了很多工作&#xff0c;現在只剩下最后幾步&a…
閱讀更多...
Flutter中stream學習

Flutter中stream學習

Flutter中stream學習 概述Stream的基礎概念stream的常用方法Stream.fromFuture(Future<T> future)Stream.fromFutures(Iterable<Future<T>> futures)Stream.fromIterable(Iterable<T> elements)Stream.periodic(Duration period, [T computation(int c…
閱讀更多...
基于javaweb的SSM房屋租賃管理系統設計和實現(源碼+文檔+部署講解）

基于javaweb的SSM房屋租賃管理系統設計和實現(源碼+文檔+部署講解）

技術范圍&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬蟲、數據可視化、小程序、安卓app、大數據、物聯網、機器學習等設計與開發。 主要內容&#xff1a;免費功能設計、開題報告、任務書、中期檢查PPT、系統功能實現、代碼編寫、論文編寫和輔導、論…
閱讀更多...
物聯網商業模式

物聯網商業模式

物聯網商業模式是一種戰略規劃&#xff0c;它融合了物聯網技術來創造價值并獲取收入。它與傳統商業模式的不同之處在于&#xff0c;它利用互聯設備來改善運營、提升客戶體驗以及優化服務項目。在當今由科技驅動的世界中&#xff0c;這種商業模式通過利用實時數據來提供創新服務…
閱讀更多...
從0開始的操作系統手搓教程45——實現exec

從0開始的操作系統手搓教程45——實現exec

目錄 建立抽象 實現加載 實現sys_execv &#xff01;&#xff01;&#xff01;提示&#xff1a;因為實現問題沒有測試。所以更像是筆記&#xff01; exec 函數的作用是用新的可執行文件替換當前進程的程序體。具體來說&#xff0c;exec 會將當前正在運行的用戶進程的進程體&…
閱讀更多...
【python爬蟲】酷狗音樂爬取練習

【python爬蟲】酷狗音樂爬取練習

注意&#xff1a;本次爬取的音樂僅有1分鐘試聽&#xff0c;僅作學習爬蟲的原理&#xff0c;完整音樂需要自行下載客戶端。 一、 初步分析 登陸酷狗音樂后隨機選取一首歌&#xff0c;在請求里發現一段mp3文件&#xff0c;復制網址&#xff0c;確實是我們需要的url。 復制音頻的…
閱讀更多...
最新文章

Copyright @ 2022~2023