做網(wǎng)站的主營業(yè)務搜外網(wǎng)
目錄
題目：跑步
思路：?
題目：夏日漫步
思路：
題目：糖果促銷
思路：
題目：第五維度
?思路：
題目：公園
思路：
??新材料
思路：
?星際航行
思路：
題目：蛋糕劃分
?編輯
思路：?
????????
????????????????
題目：跑步
小度每天早上要和小貓一起跑步。小貓的位置數(shù)值越小表示越在后面，速度越小表示越慢，它們都向一個方向跑。
小貓比較喜歡一起跑，所以當速度更快的小貓遇見速度慢的小貓時，它就會放慢速度，變成一組一起跑。注意，初始位置相同的小貓直接組成一組。
請問最終不再有追趕上的情況時，最多一組有多少只小貓？
????????
? ? ? ?
思路：?
我們先來捋一下題目哈：不同位置的小貓同時以不同速度開跑，當后面的貓追上前的貓時，它們就會以低速貓速度共速，成為一組，求最終一組最多的貓個數(shù)。
正著想不太好想，因為變化因素較多。我們可以倒著想：從最前面的貓開始推導，若i-1只貓速度大于第i只貓，不管i-1貓會不會被別的貓追上，都不會影響i-1貓追上i貓這個結果。然后要注意一下剛開始在同一位置的貓會直接分成一組。
操作：
我們先對貓按位置排列，同位置的貓貓速度小優(yōu)先，然后先把同一位置的貓速度統(tǒng)一一下，此時同組的貓貓速度按最前面的貓速（最低速貓）設定速度，最后從后向前遍歷：對i貓，將i后面連續(xù)所有v大于i的貓都直接統(tǒng)計出來（這個就是此組中最終會有的貓貓數(shù)），然后從i貓?zhí)讲粷M足條件貓的位置（方便統(tǒng)計下一組的貓貓），不斷重復即可！
#include <bits/stdc++.h> //跑步：有n只小貓，出現(xiàn)在pi位置，速度為vi向前跑，不同速度小貓相遇時會共速成一組(取慢速那個),問最多一組的小貓個數(shù)
using namespace std; //貪心，
const int N=1e5+10;
struct node{int p;int v;}ar[N];
bool cmp(node x,node y){if(x.p!=y.p)return x.p<y.p;//必須這么寫，可別偷懶！else return x.v<y.v;
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&ar[i].p,&ar[i].v);}sort(ar+1,ar+1+n,cmp);for(int i=1;i<n;i++){if(ar[i].p==ar[i+1].p) ar[i+1].v=ar[i].v;//同位置的貓速度給統(tǒng)一一下}int ans=-1,cnt=1,inde=n;//cnt來統(tǒng)計當前組有幾只小貓while(1){if(inde-cnt==0)break;//遍歷結束if((ar[inde].p!=ar[inde-cnt].p&&ar[inde].v<ar[inde-cnt].v)||(ar[inde].p==ar[inde-cnt].p))cnt++;//兩個情況都要統(tǒng)計進去：兩只貓位置不同但后貓更快， 兩只貓位置相同else inde=inde-cnt,cnt=1;ans=max(ans,cnt);}cout<<ans;
}????????
????????
題目：夏日漫步
夏日夜晚，小度看著庭院中長長的走廊，萌發(fā)出想要在上面散步的欲望，小度注意到月光透過樹蔭落在地磚上，并且由于樹蔭的遮蔽度不通，所以月光的亮度不同，為了直觀地看到每個格子的亮度，小度用了一些自然數(shù)來表示它們的亮度。亮度越高則數(shù)字越大，亮度相同的數(shù)字相同。
走廊是只有一行地磚的直走廊。上面一共有?n個格子，每個格子都被小度給予了一個數(shù)字?ai??來表示它的亮度。
小度現(xiàn)在站在?1號格子，想要去到?n號格子。小度可以正向或反向移動到相鄰的格子，每次需要花費?1的體力。
同時小度還有瞬移的能力，其可以花費?1的體力來瞬移到與當前格子亮度相同的格子上。而且由于小度視野有限，只能瞬移到在當前格子后的第一次亮度相同的格子上。這也意味著不能反向瞬移。
小度想知道，到達?n號格子需要花費的最小體力是多少。以此制定一個最優(yōu)秀的散步方案。
????????
思路：
題意就是可以正向反向走一步，也能正向瞬移到相同亮度的地方。
這個題可以按照跑圖題來做，每個相鄰位置前后連起來，然后當前位置和之前同亮度位置單向連接，然后我們跑bfs，按步數(shù)進行遍歷，就可以知道到最早哪一步時候可以走到終點！
#include <bits/stdc++.h> //夏日漫步
using namespace std;
const int N=2e5;
int pos[1000000];
vector<int>v[N];
queue<int>q;
int main(){int len,ans=0,n,a;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a);if(i+1<=n)v[i].push_back(i+1),v[i+1].push_back(i);//正常建邊if(!pos[a])pos[a]=i;else v[pos[a]].push_back(i),pos[a]=i;//正向瞬移建邊}q.push(1);int p,sign=0;while(!q.empty()){ans++;//按層bfslen=q.size();while(len--){p=q.front();q.pop();for(int i=0;i<v[p].size();i++){if(v[p][i]==n){sign=1;break;}else if(p<v[p][i])q.push(v[p][i]);}if(sign)break;}if(sign)break;}cout<<ans;
}????????
????????
題目：糖果促銷
小度最喜歡吃糖啦！！！
這天商店糖果促銷，可給小度高興壞了。
促銷規(guī)則：一顆糖果有一張?zhí)羌?#xff0c;p張?zhí)羌埧梢該Q取一顆糖果。換出來糖果的包裝紙當然也能再換糖果。
小度想吃?k顆糖果，他至少需要買多少顆糖？
思路：
注意到“至少 ”，細品！就是說最后一次換糖果時恰好沒有多余的糖皮，即最終手里有一定且僅有一張?zhí)瞧?#xff08;如果手里有大于兩張?zhí)瞧さ脑?#xff0c;那就上次兌換就有多余的糖皮，也就是多買的糖）
好了，我們來分析：一共吃了k個糖，那么有k-1個糖皮被換成了糖，那么需要買的糖就是k-(k-1)/p;
最后呢！這個題其實還可以二分來做
?
#include <bits/stdc++.h> //糖果促銷：p個糖果可以換1個糖，想吃k個糖至少要買多少個糖 (1<=t<=1e6, 1<=p<=1e9, 0<=k<=1e9)
using namespace std;
int t,p,k;
int main(){cin>>t;while(t--){cin>>p>>k;if(k==0) cout<<0<<'\n';//注意題上的數(shù)據(jù)范圍else{k-=(k-1)/p;//一個式子就行cout<<k<<'\n';}}
}????????
????????
題目：第五維度
零維是點，點動成線；
一維是線，線動成面；
二維是面，面動成體；
三維是體，體動成史；
四維是史，史動????
現(xiàn)在人類企圖理解第五維度。
而小度現(xiàn)在是第五維度的一位智者。一天，小度發(fā)現(xiàn)人類的許多科學家在試圖理解第五維度，人類是四維生物，若是他們理解了第五維度，很可能也會到來第五維度的空間，這顯然是小度不愿意看到的（畢竟哪里都有人口數(shù)量的問題….）所以小度希望他們盡可能晚的理解第五維度，因此，小度用更高維度的視角把所有人類中在理解第五維的科學家都看到了，而這些科學家的智商會不一樣，所以他們的理解速度?Vi??也會不一樣；并且，他們開始理解的時間點?Si??也不一樣。理解速度?Vi??描述為每過單位時間可獲得?Vi??個單位理解力，也就是說在?Si?+1?的時間點該科學家會第一次貢獻?Vi??的理解力。我們定義理解力總數(shù)超過?m?時理解了第五維度。 小度因為維度更高，可以使用時間悖論來給人類一次重大的打擊，小度可以讓任意一位科學家在任意一個時間點消失，所以他接下來的理解不會繼續(xù)；而且人類不會記得他，所以他之前的貢獻會消失。因為小度能力有限，所以小度只能使用一次暫時悖論。
現(xiàn)在求在盡可能晚的情況下，人類理解第五維度的最早時間點。
時間點初始為0，但顯然，沒有科學家能夠在?0時刻有貢獻。
?思路：
二分答案，那么這次二分什么呢？當然是時間了！
我們只要遍歷每個二分后的時間點就行，看在有效時間內貢獻最多的人消失后還能不能理解第五維度，如果仍然可以理解，那么我們就繼續(xù)減少時間，直到不能再減少時間，那么答案就出來了。
那么怎么知道最終的二分結果究竟能不能使人理解理解第五維度呢？我們只需要再帶入一次check函數(shù)判斷即可！
?
#include <bits/stdc++.h>//第五維度：有n個科學家，在不同的時間點s出現(xiàn)，之后每天貢獻v，當人類貢獻總和大于m時，就理解了第五維度，但上帝可以隨機
using namespace std; //使一個人消失，他的所有貢獻也會消失，問人類最晚多久可以理解第五維度，如果不能輸出-1
typedef long long ll;
ll s[100000],v[100000],n,m;
bool check(ll t){ll sum=0,max_=-1;for(int i=1;i<=n;i++){if(t<=s[i])continue;//后面出現(xiàn)的人就跳過sum+=(t-s[i])*v[i];max_=max(max_,(t-s[i])*v[i]);//找最大貢獻的人}return sum-max_>m;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d %d",&s[i],&v[i]);}ll mid,l=0,r=2e9;while(l<=r){mid=(l+r)>>1;if(check(mid)) r=mid-1;else l=mid+1;}if(check(l))cout<<l;//對二分查找失敗的情況進行特判else cout<<-1;
}????????
????????
題目：公園
今天是六一節(jié)，小度去公園玩，公園一共?N?個景點，正巧看到朋友圈度度熊也在這個公園玩，于是他們約定好一塊去景點?N。 小度當前所在景點編號為?T，從一個景點到附近的景點需要消耗的體力是?TE，而度度熊所在景點編號為?F?，移動消耗為?FE。 好朋友在一塊，趕路都會開心很多，所以如果小度和度度熊一塊移動(即在相同位置向相同方向移動)，每一步他倆的總消耗將會減少?S。
求他倆到景點?N?時，所需要的總消耗最少是多少？
?????????
輸入：
4 4 3 1 2 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8
輸出：
22
思路：
其實注意到兩個人的消耗是固定的，既然不知道在哪相遇，不妨把每個點都做中間相遇點試試，(你看看，出題人就是想讓你暴力的)。
我們先對3個點找各自到其他點的最短距離，假如a點是相遇點，那么三個點(小度，小熊，終點)到此點a的最短距離×各自三個消耗(消耗怎么算？就看走了多長就行，因為每短的消耗是一樣的)，這樣的話，一種答案就出來了，然后找出最優(yōu)答案即可。
其實，從這道題，你發(fā)現(xiàn)了什么？是不是找3個點的最近距離問題！
#include <bits/stdc++.h> //公園：共n個景點，兩個人都要到n景點，兩人移動一個景點就各消耗e1,e2，一起走消耗減少e3。求最少消耗？到不了輸出-1
using namespace std; //暴力枚舉
typedef pair<int,int> pa;
const int N=40005;
int dis[3][N],head[N];
int s1,s2,n,m;
long long ans=1e17;
priority_queue<pa,vector<pa>,greater<pa>> Q;
struct node{int to;int next;}e[N*2];
void add(int u,int v){static int i=0;i++;e[i].to=v;e[i].next=head[u];head[u]=i;
}
void dijkstra(int s,int dis[]){for(int i=0;i<=n;i++)dis[i]=40000;dis[s]=0;Q.push(make_pair(0,s));while(!Q.empty()){int u=Q.top().second;int dis_=Q.top().first;Q.pop();if(dis_!=dis[u]) continue;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dis[v]>dis[u]+1)dis[v]=dis[u]+1,Q.push(make_pair(dis[v],v));}}
}
int main(){long long e1,e2,e3; //之所以ll型，是因為dis是int型，運算時方便給ll型ans賦值（類型隱式轉換）cin>>e1>>e2>>e3; //e1，e2是兩人的消耗，e3是減少的消耗：cin>>s1>>s2>>n>>m;//s1，s2是兩個人的起點，n，m是景點數(shù)和邊數(shù)int u,v;while(m--){scanf("%d %d",&u,&v);add(u,v);add(v,u); //建邊}dijkstra(s1,dis[0]); //尋找3個點到其余點的最短距離dijkstra(s2,dis[1]);dijkstra(n,dis[2]);for(int i=1;i<=n;i++){ //如果dis沒有變說明這個點到不了，標記一下if(dis[0][i]==40000)dis[0][i]=-1;if(dis[1][i]==40000)dis[1][i]=-1;if(dis[2][i]==40000)dis[2][i]=-1;}for(int i=1;i<=n;i++){ if(dis[0][i]!=-1&&dis[1][i]!=-1&&dis[2][i]!=-1) //3個點都要能到才算有效（能連起來）ans=min(ans,dis[0][i]*e1+dis[1][i]*e2+dis[2][i]*(e1+e2-e3)); //（ll*int）->ll類型}if(ans==1e17){cout<<-1;return 0;}//3個點沒有一個公共交點，即3個點連不起來cout<<ans;return 0;
}????????
??新材料
思路：
直接模擬：因為要考慮上次出現(xiàn)的位置，所以使用map映射最好，如果沒有出現(xiàn)過就建立新映射，如果出現(xiàn)過但是已經(jīng)反應過就跳過，如果出現(xiàn)過但是不足以反應，就建立新映射，如果能反應就反應，并標記。?
#include <bits/stdc++.h>
using namespace std;
map<int,int>mp;
int n,k;
int main(){scanf("%d%d",&n,&k);int ans=0;for(int i=1;i<=n;i++){int cur;scanf("%d",&cur);if(!mp.count(cur))mp[cur]=i;//有返回1無返回0，返回-1表示已經(jīng)反應過了else if(mp[cur]==-1)continue;else if(i-mp[cur]>k)mp[cur]=i;else ans^=cur,mp[cur]=-1;}cout<<ans<<'\n';
}????????
????????
?星際航行
思路：
我們的任務是把三維的一群點，變成任意兩維都相同，另一維是個差為1的等差數(shù)列，然后求最小代價。其實我們可以枚舉下哪兩維相同，然后計算代價，再計算剩下的一維變成等差數(shù)列的代價。
任務1：把一個維度上的所有點變到同一個位置的最小代價就是把所有點都挪到中間點上，你可以畫圖證明：每兩個點之間挪動的代價恰好都是兩點之間的線段距離的情況下，總代價最小。
如圖：我們只要保證更多的點分布在中間點的兩邊，且兩邊的點都恰好連成線段時候代價是最小的（這個偶數(shù)的點的情況，奇數(shù)的點的情況會更加明顯）
（上面的的是選10為中間點，下面的是選9為中間點）?
任務2：要把一個維度上所有點變成一個等差數(shù)列且代價最小，就必須不能改變它們之間原來的順序。如圖：（我們假設最終的點的起點是t，那么所有點最終坐標是t+i）
那么最終的代價是sum|xi-(t+i)|最小，然后我們再變形一下：sum|(xi-i)-t|，誒，這不就是所有點xi-i到t的代價最小嗎，我們只需要在重復一下上面任務1的做法就行了。
那么最終做法就是：先把數(shù)組排序，然后找到求每個點到中間的點的距離和，最終求出兩個度的代價，然后在求ai=ai-i，再做一遍，這樣就枚舉出了一種情況了，然后把所有情況都枚舉一下就行了。
????????
????????
題目：蛋糕劃分
小度準備切一個蛋糕。這個蛋糕的大小為?N?N，蛋糕每個部分的重量并不均勻。
小度一共可以切?K刀，每一刀都是垂直或者水平的，現(xiàn)在小度想知道在切了?K刀之后，最重的一塊蛋糕最輕的重量是多少。
思路：?
首先這個暴力dfs不行，橫刀14下，豎刀14下，共2^28*14^2會超時的
其實對最大質量的蛋糕塊二分答案即可，難在對答案判斷：
首先我們對所有的橫刀狀態(tài)模擬，用一個數(shù)的(n-1)位的表示所有狀態(tài)即可，然后根據(jù)此時橫刀狀態(tài)對豎刀進行決策，方法是：
從第一列開始，計算每列區(qū)間和，若此時橫刀區(qū)間和加上新的一列區(qū)間后值大于答案了，那就要在此列左邊切豎刀，然后在此豎刀右面重新計算新一列區(qū)間，
不斷重復。其實就是每個橫刀區(qū)間加上新一列區(qū)間后都不要大于答案，如果大于我們就要這里要切豎刀了。最后統(tǒng)計豎刀和橫刀數(shù)，返回結果即可
（另外，為了加速處理，還要用上二維前綴和）
#include <bits/stdc++.h> //蛋糕劃分：蛋糕大小N*N，每個部分質量不均，共切k刀(橫豎均可)，使最重的一塊蛋糕的質量最輕是多少。
using namespace std; //2≤N≤15，1≤K≤2N?2 ，每個位置質量W小于1000 和洛谷P1182 數(shù)列分段一樣思路
int n,k,fal,max_;//fal是答案出錯標記，方便快速結束循環(huán)
int a[20][20],sum[20][20],col[20],cnt[20],temp[20];;//col存放豎刀的位置,cnt是橫切后每個區(qū)間和，temp是新一列區(qū)間和
int get_sum(int x1,int y1,int x2,int y2){//求上下左右區(qū)間和return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
bool check(int m){if(m<max_)return false;//特判
//第一個循環(huán)是對每種橫刀狀態(tài)進行遍歷（每一個i都代表一種橫刀狀態(tài)）for(int i=0;i<(1<<(n-1));i++){fal=0;//更新此種橫刀狀態(tài)為正確，內部循環(huán)發(fā)現(xiàn)是因橫刀出錯時就一頭沖出來memset(col,0,sizeof(col));memset(cnt,0,sizeof(cnt));memset(temp,0,sizeof(temp));vector<int> v;int count=0,ans=0, tmp=i;while(tmp){count++;if(tmp&1){//獲取i中1的位置，存入這種狀態(tài)下的每個橫刀位置v.push_back(count);//v用來存橫刀位置，若v里面為1,3,4，加入n后，表示橫刀區(qū)間1-1，2-3，4-4，5-nans++;}tmp/=2;}if(ans>k)continue;//特判v.push_back(n);int p=0,top=1,down;//top是該區(qū)間最上面元素位置,down是此橫刀位置,p為當前的第幾個橫刀區(qū)間（
//第二個循環(huán)是切豎刀的，在每個豎位置遍歷列區(qū)間，一旦某個橫刀區(qū)間加上這個列超過答案就說明可以切豎刀了for(int j=1;j<=n;j++){p=0,top=1;//每切一次豎刀就重置一次
//第三個循環(huán)是遍歷橫刀區(qū)間的（我們要自上而下遍歷每個區(qū)間）for(int x:v){//用x來訪問v中的所有元素，取出每個橫刀位置down=x;int now=get_sum(top,j,down,j);//求列區(qū)間和（列寬為1）if(now>m){//如果僅列區(qū)間已經(jīng)大于答案就說明是橫刀狀態(tài)失誤了，fal標記一下，直接沖到最外面fal=1; break;}
//求新的橫刀區(qū)間（原橫刀區(qū)間加列區(qū)間）cnt[++p]+=now;//將上個區(qū)間加上這個區(qū)間if(col[j-1]){cnt[p]=now;//上個位置被切過了，就說明我們不應該加的}temp[p]=now;//temp存每個列區(qū)間和
//判斷該橫刀區(qū)間，決策是否切豎刀if(cnt[p]>m){//該區(qū)間和大于答案，說明要切豎著在j-1的位置一刀，cnt再從第j列開始計算和（你只有犯錯的時候才知道自己犯錯了）col[j-1]=1;//更新豎切的位置和區(qū)間和cnt[p]=now;for(int ii=1;ii<p;ii++)cnt[ii]=temp[ii];//之前的區(qū)間也要因此而更新了，用上temp了}top=down+1;//top是下個區(qū)間最上面位置}if(fal)break;}if(fal)continue;for(int j=1;j<=n-1;j++)if(col[j])ans++;//col存放的豎切刀if(ans<=k)return true;}return false;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++)//數(shù)據(jù)從1，1開始存，后面注意這點for(int j=1;j<=n;j++){cin>>a[i][j];max_=max(max_,a[i][j]);sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];}int l=0,r=2000*15*15;while(l<=r){int m=(l+r)>>1;if(check(m)) r=m-1;//刀數(shù)太少，說明應該再切小一點else l=m+1;}cout<<l<<'\n';return 0;
}今天的確實有點難，嗯