持續更新中…
7-2 小寶的幸運陣列
對于小寶來說，如果一個陣列的總和能夠整除他的幸運數字k，就是他的幸運陣列，而其他陣列小寶都很討厭，現在有一個長度為n的陣列，小寶想知道這個陣列的子陣列中，最長的幸運子陣列有多長，
對于子陣列的定義，如果可以通過從開頭和從結束分別洗掉若干個（可以為零或全部，前后洗掉個數不必相同）元素來從陣列b獲得陣列a，則稱陣列a是陣列b的子陣列，（子陣列包含原陣列，但不包含空串）
輸入格式:多組輸入，第一行包含一個整數T(1≤T≤10)，表示有T組測驗資料，
每組測驗資料包含兩行，第一行包含兩個整數n和k(1≤n≤10?5??,1≤k≤10?5??)，分別表示陣列長度和小寶的幸運數字，第二行包含n個空格分隔的整數a?1??,a?2??,…,a?n??(0≤a?i??≤10?9??)，為陣列的元素，
輸出格式:對于每組資料，輸出和能被k整除的最長子陣列的長度，如果沒有這樣的子陣列，則輸出?1，每組資料輸出一行， 輸入樣例:
在這里給出一組輸入，例如：
4 3 3 1 2 3 3 5 1 2 3 3 7 1 2 3 1 6 5
輸出樣例:
在這里給出相應的輸出，例如：
3
2
-1
-1
思路
使用前綴和sum[]預處理陣列，則從第i位到第j位的子串和為sum[j]-sum[i-1]，又因為本題尋找的是最長子陣列，所以需要從大到小列舉子樹組，找到了就輸出然后跳出回圈，這樣可以防止運行超時，
代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);//這題時間卡的緊，用scanf比較好
while(t--)
{
long long n[100005]={0},sum[100005]={0};//每組資料都要重新歸零
int a,b;
scanf("%d %d",&a,&b);
for(int i=1;i<=a;i++)
{
scanf("%d",&n[i]);
sum[i]=sum[i-1]+n[i];//前綴和預處理
}
int k=a,flag=0;
while(k!=0&&flag==0)
{
for(int i=a;i-k>=0;--i)//從最長的子陣列開始列舉
{
if((sum[i]-sum[i-k])%b==0)//前綴和相減得到子陣列的和
{
printf("%d\n",k);
flag=1;//找到了一項
break;
}
}
--k;//子陣列長度減1再次回圈
}
if(flag==0)//一項也沒有
printf("-1\n");
}
return 0;
}
7-3 上進的凡凡
凡凡是一個上進的人，他的人生沒有下坡路，他也討厭帶有”下坡路“的東西，
所以，對于凡凡來說，只有非降序的陣列才是nice的（如：1，2，2，3，4，5，5）；若陣列元素個數為1，也滿足非降序，也是nice的，
現在有一個長度為n的陣列，凡凡想知道它的子陣列中有多少個陣列是nice的，
你能幫幫他嗎？
對于子陣列的定義，如果可以通過從開頭和從結束分別洗掉若干個（可以為零或全部，前后洗掉個數不必相同）元素來從陣列b獲得陣列a，則稱陣列a是陣列b的子陣列，（子陣列包含原陣列，但不包含空串）
輸入格式:輸入共兩行，
第一行輸入一個整數n(1≤n≤10?5??)，表示陣列的長度，
第二行包含n個空格分隔的整數a?1??,a?2??,…,a?n??(0≤a?i??≤10?9??)，為陣列的元素， 輸出格式:
輸出給定陣列的子陣列中是nice陣列的個數，（注意使用long long）
輸入樣例:在這里給出一組輸入，例如：
5 1 2 3 4 5
輸出樣例:
在這里給出相應的輸出，例如：
15
思路：又是求子陣列的一題，這題應該是最簡單的一題了，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll a[maxn];
ll dp[maxn];
ll ans=0;
int main()
{
std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//這一行是為了用cin、cout也能很快輸入輸出 看不懂可以直接忽略
ll n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ll sum=1;
for(int i=1;i<n;i++)
{
if(a[i+1]>=a[i])//大于等于
{
sum++;
}
else //如果碰到下一個不遞增了，那就先計算出這一個遞增的子陣列中一共有多少個nice陣列
{
ans+=(1+sum)*sum/2;//計算nice陣列的共識 比如1 2 3 4 5中有5+4+3+2+1個nice陣列，所以可以用公式（1+5）*5/2來計算
sum=1;//這一步再把sum歸1開始尋找接下來的子陣列 因為就算子陣列只有一個 它本身也是nice陣列 所以是歸1而不是歸0
}
}
ans=(1+sum)*sum/2+ans;
cout<<ans<<endl;
}
7-4 Seek the Joker I
長達數日的春日祭終于告一段落，作為巫女的朝野芳乃在打掃完神社本決定好好享受一下久違的寧靜，然而守護了神刀數百年的叢雨難耐寂寞，希望芳乃能陪她一起玩撲克消解愁悶，
芳乃并不擅長市井的游戲，所以總是輸多贏少，而昨日被芳乃的神樂舞深深吸引，以致一早就前來建實神社希望能再睹芳華的你碰巧聽見了此事，盡管不知道為什么美麗的巫女要自言自語地為玩撲克而苦惱，但你毅然決然地毛遂自薦，希望能為芳乃一解眉間愁，
芳乃告訴了你叢雨準備了n張撲克牌作為牌堆，每人每次至多從牌堆頂部抽k張牌，至少抽1張牌，牌堆底部的最后一張牌作為烏龜，抽中的將輸掉這一輪比賽，芳乃想知道在你的幫助下，她和叢雨都采取積極策略時，她自己是否一定能獲勝，作為被叢雨邀請的一方，每輪游戲都是芳乃先抽，
因為看不見叢雨而誤認芳乃罹患精神分裂的你在不由感嘆紅顏薄命的同時，決定盡全力幫助芳乃完成她的委托，
宣告：本題中的所有角色在劇情發生時均已超過18歲，
輸入格式:第一行包含一個整數T，表示共有T組測驗資料，
每組測驗資料共一行，包含兩個正整數n和k，分別表示牌堆中有n張牌和每次抽取最多抽取k張，
資料保證，T,n,k≤10?6??，
輸出格式:對于每組測驗資料給出一行結果，
如果芳乃必勝，則輸出yo xi no forever!，
否則輸出ma la se mi no.1!，
輸入樣例:4 1 1 23 2 6 4 114 514
輸出樣例:
ma la se mi no.1!
yo xi no forever!
ma la se mi no.1!
yo xi no forever!
思路：博弈論中的巴什博弈，我的另外一篇博客中正好是講的這個
巴什博弈
可以直接記一下結論：
巴什博弈（Bash Game）
只有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m個，
最后取光者勝若n%（m+1）==0，后手必勝，反之，先手必勝，
最后取光著輸當（n-1）%（m+1）==0 時 ，后手必勝，否則先手必勝
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
if(n==1)
{
cout<<"ma la se mi no.1!"<<endl;
}
else if(k==1)
{
if(n%2==1)cout<<"ma la se mi no.1!"<<endl;
else cout<<"yo xi no forever!"<<endl;
}
else if(k>=n)
{
cout<<"yo xi no forever!"<<endl;
}
else //除去前面幾個特殊的情況
{
if((n-1)%(k+1)==0)cout<<"ma la se mi no.1!"<<endl;//直接背結論
else cout<<"yo xi no forever!"<<endl;
}
}
}
7-5 Seek the Joker II
長達數日的春日祭終于告一段落，作為巫女的朝野芳乃在打掃完神社本決定好好享受一下久違的寧靜，然而守護了神刀數百年的叢雨難耐寂寞，希望芳乃能陪她一起玩撲克消解愁悶，
芳乃并不擅長市井的游戲，所以總是輸多贏少，而昨日被芳乃的神樂舞深深吸引，以致一早就前來建實神社希望能再睹芳華的你碰巧聽見了此事，盡管不知道為什么美麗的巫女要自言自語地為玩撲克而苦惱，但你毅然決然地毛遂自薦，希望能為芳乃一解眉間愁，
芳乃告訴了你叢雨準備了n張撲克牌作為牌堆，自牌頂向下數第x張牌作為烏龜，即“烏龜”的上方有x-1張牌，“烏龜”的下方有n-x張牌，抽中“烏龜”的將輸掉這一輪比賽，每人每次可以同時在牌堆頂和牌堆底或者僅在牌堆頂或牌堆底其抽取任意張牌，至少抽1張牌，但若選擇同時在牌堆頂和牌堆底抽牌，則抽牌數量需要相同，芳乃想知道在你的幫助下，她和叢雨都采取積極策略時，她自己是否一定能獲勝，作為被叢雨邀請的一方，每輪游戲都是芳乃先抽，
因為看不見叢雨而誤認芳乃罹患精神分裂的你在不由感嘆紅顏薄命的同時，決定盡全力幫助芳乃完成她的委托，
宣告：本題中的所有角色在劇情發生時均已超過18歲，
輸入格式:第一行包含一個整數T，表示共有T組測驗資料，
每組測驗資料共一行，包含兩個正整數n和x，分別表示牌堆中有n張牌和”烏龜“的位置，
資料保證，T≤10?6?? 和 n,x≤3?10?6??，
輸出格式:對于每組測驗資料給出一行結果，
如果芳乃必勝，則輸出yo xi no forever!，
否則輸出ma la se mi no.1!，
輸入樣例:8 1 1 10 3 17 6 12 5 4 3 9 6 12 8 17 11
輸出樣例:
ma la se mi no.1! yo xi no forever! yo xi no forever! ma la se mi
no.1! ma la se mi no.1! ma la se mi no.1! ma la se mi no.1! ma la se
mi no.1!
思路：
又是一道關于博弈論的題目，這次是威佐夫博弈，
威佐夫博弈
有兩堆各若干的物品，兩人輪流從其中一堆取至少一件物品，至多不限，或從兩堆中同時取相同件物品，規定最后取完者勝利，
若兩堆物品的初始值為（x，y），且x<y，則另z=y-x；
記w=（int）[（（sqrt（5）+1）/2）*z ]；（這個正好是黃金分割率）數學就是這么的奇妙
若w=x，則先手必敗，否則先手必勝，
大家就把結論記著就行了，反正我是縷不明白
代碼：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
double mysticalConstant = (1.0+sqrt(5.0))/2.0;
int T;
cin>>T;
while(T--){
int n,x;
cin>>n>>x;
int a=x-1,b=n-x;
if(a>b) swap(a,b);
int temp = (b-a)*mysticalConstant;
if(temp!=a) cout<<"yo xi no forever!\n";
else
cout<<"ma la se mi no.1!\n";
}
return 0;
}
7-6 成績查詢ING
去年的新冠疫情爆發讓眾多大學生只能只能在家里上學，老師為了方便自己錄入成績和方便大家成績查詢，建立了一個錄入和查詢成績的系統，能完成M次兩種不同的查詢，輸入查詢次數M，查詢M次，每次首先輸入查詢的模式T，T為1時，輸入同學的姓名Name，并依次輸出同學的成績Grade(0<=Grade<=100），
學號（0~1000000}，性別（1/2），T為2時，輸入成績，輸出有具體有哪些同學考到了這個分數，輸出同學的Name，并要求按字典序輸出，當沒有同學為此分數時，則不輸出，
字典序，對于字串，先按首字符排序，如果首字符相同，再按第二個字符排序，以此類推， 輸入格式:第一行包含一個整數N，表示系統中共有N個人（1<=N<=100000），
下面N行分別輸入N個人的姓名Name，成績Grade（成績在0~100之間），性別（1或2分別表示男性、女性），學號，表示系統中成員的資訊
輸入查詢次數M(M<=10000000)，接下來M行完成M次查詢任務 輸出格式:輸出M次查詢的結果，當T為1時，輸入同學的姓名Name，并在一行中依次輸出同學的成績Grade(0<=Grade<=100），
學號（0~1000000}，性別（1/2），用空格間隔（注意行末無空格），T為2時，輸入成績，輸出有具體有哪些同學考到了這個分數，輸出同學的Name（每個Name輸出一行，無空格），并要求按字典序輸出，當沒有同學為此分數時，則不輸出，
輸入樣例:5 N 28 2 7475 UN 83 2 27550 EXF 5 2 17298 OVYNH 51 2 14827 XNV 53 1
7591 2 1 XNV 2 27輸出樣例:
53 7591 1
思路：
學長之前再三提醒，要好好學STL，自己也確實去努力學了學，但是圖靈杯的時候確實沒時間寫555
看了看官方題解，主要運用到了map和set
map我之前有做過筆記，挺好用的
map的筆記
//這是官方題解的代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
set<string> s[120];
map<string,int> mp1;
map<string,int> mp2;
map<string,int> mp3;
for(int i=1;i<=n;i++)
{
string Name;
int xb;
int xh,cj;
cin>>Name>>cj>>xb>>xh;
s[cj].insert(Name);
mp1[Name]=cj;
mp2[Name]=xh;
mp3[Name]=xb;
}
int m;
cin>>m;
while(m--){
int x;
cin>>x;
if(x==1){
string name;
cin>>name;
cout<<mp1[name]<<" "<<mp2[name]<<" "<<mp3[name]<<endl;
}else{
int y;
cin>>y;
set<string>::iterator it;//這一步不懂的朋友可以去查一下iterator的用法
it=s[y].begin();
for(;it!=s[y].end();it++){
cout<<*it<<"\n";
}
}
}
return 0;
}
7-7 貪吃的派蒙
在遙遠的提瓦特大陸上，正在籌備一年一度的羽球節，獵鹿人餐廳為犒勞認真籌備的眾人，準備了K份甜甜花釀雞供大家排隊領取，
在每一次的排隊中，編號為i的角色領取上限為Ai，這意味著他可以領取的甜甜花釀雞在[1-Ai]范圍內，當一個角色領完本次的甜甜花釀雞，他/她就會回到佇列的末尾，直到所有甜甜花釀雞都被吃完為止，當輪到一個角色領取時，如果所有的甜甜花釀雞都被領完，那么他/她就要幫大家刷盤子，
貪吃的派蒙每次都吃固定的Ax個甜甜花釀雞(如果剩下的甜甜花釀雞的數量比Ax小，那么他就把剩下的都吃完)，我們很容易找到派蒙的編號，Ax比其他所有的Ai都要大，大家都想讓派蒙最后留下來刷盤子，請你寫一個程式來判斷這是否可能，
輸入格式:多組輸入，
第一行包含一個整數T(1≤T≤100)，表示有T組測驗資料，
接下來每組測驗資料包含兩行，
第一行包含兩個整數N和K(2≤N≤105,0≤K≤108)，分別表示人數和甜甜花釀雞的數量，
第二行包含一個整數Ai(1≤Ai≤10^9)，表示佇列中編號為i的角色可以領取甜甜花釀雞的最大數量，始終只有一個最大的Ax， 輸出格式:
如果大家能找到一種方案讓派蒙刷盤子，那么輸出“YES”，否則輸出“NO”，
輸入樣例1:1 4 3 1 2 3 2
輸出樣例1:
YES
輸入樣例2:
1 5 8 1 2 3 2 1
輸出樣例2:
NO
思路：
最討厭這種題目了，我也知道用貪心寫，可是真的好難想，每次見到這種題目第一反應就是：啊？這也能編程？
看了官網題解還是沒整明白 氣死我了 看了隔壁的大佬寫的，感覺點意思了，把隔壁大佬的代碼抄過來給大家看看吧 嘻嘻
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e5+7;
const int mod=998244353;
ll num[maxn];
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n;
ll k;
scanf("%d%lld",&n,&k);
ll M=0;
int tar=0;//記錄下派蒙在第幾個
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
if(num[i]>M)
{
tar=i;
M=num[i];
}
num[i]+=num[i-1];//前綴和
}
ll yici=M+n-1;//代表一次回圈最少要吃掉多少個
if(k<tar-1) printf("NO\n");//前面的tar個人最少每個人要吃一個
else
{
ll rest=(k-tar+1)%(yici);//代表除了派蒙的人每人都只吃1個的情況，最后剩下的部分
ll cas=(k-tar+1)/yici;//在上述情況下總共有多少輪回圈(這里的回圈，派蒙是第一個人)
cas*=(num[n]-M);//每輪回圈我們最多還可以再多吃總的個數減去派蒙的個數
cas+=num[tar-1]-tar+1;//在開始回圈前，一開始就排在派蒙前面的tar-1個人，除了最基本的每人吃一個外，最多還能吃幾個
if(cas>=rest) printf("YES\n");//如果能多吃的部分大于剩余的部分，代表我們能有一種安排，使得某次回圈開始時，派蒙去吃東西的時候k已經為0
else printf("NO\n");
}
}
}
7-8 數羊
憨憨小楊晚上睡不著覺，就開始數羊，她覺得一只一只數太慢了，突發奇想出了一種新的數羊方式，羊羊數量A(n,m)由兩個整形變數n和m決定，計算方式如下:
圖片2.png
現在給出n和m的值，請你幫小楊數數一共有多少只羊， 輸入格式:
多組輸入，
第一行包含一個整數T(1≤T≤1000)，表示有T組測驗資料，
每組測驗資料包含一行，包含兩個整數n(1≤n≤10^9)和m(0≤m≤2). 輸出格式:
對每一組輸入，在一行中輸出A(n,m)的值,由于輸出的結果可能會很大，答案對998244353取模， 輸入樣例:
3 3 0 3 1 3 2
輸出樣例:
5 6 8
思路：
以后看到這種看似沒有規律的題，硬寫肯定會超時，所以要去打表找規律，這題的規律就十分簡單了，
以下是從官方題解里抄過來的嘻嘻：
暴力打表可知：
m=0時，A(n,0)=n+2;
m=1時，A(n,1)=2*n
m=2時，A(n,2)=2^n
注意取模
它官方題解里的證明反正我是看不懂，也不想看
這里還用的了一個快速冪的知識 不會的可以去洛谷做一下模版題
快速冪
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll quick_mod(ll a,ll m)//快速冪
{
ll ans=1;
while(m!=0)
{
if(m%2==1) ans=ans*a%mod;
a=a*a%mod;
m/=2;
}
return ans%mod;
}
int main()
{
cin.tie(0); ios::sync_with_stdio(false);
int t; ll n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
ll ans;
if(m==0)
{
ans=n+2;
}
else if(m==1)
{
ans=n*2;
}
else if(m==2)
{
ans=quick_mod(2,n);//呼叫快速冪函式
}
cout<<ans%mod<<endl;
}
return 0;
}
7-9 買花
情人節馬上要到了，陽陽想送出n朵花給喜歡的妹妹，他打算提前開始買，但是，因為他有強迫癥，所有的花要分k天買（k>1，即不能一天全買完）,第一天他可以買任意朵花，之后每一天買花的數量為前一天的兩倍，（如若第一天買4朵，第二天就要買8朵，以此類推），
現在離情人節還有15天（k≤15），請你告訴陽陽，他能不能剛好買到n朵花，
輸入格式:多組輸入，第一行一個正整數T（1≤T≤10?5??)，表示資料組數，
接下來T行，每行一個正整數n（1≤n≤10?9??)，表示預計買花的數量，
輸出格式:
每組資料輸出一行，共T行，
判斷能否剛好買到n朵花，可以則輸出"YE5"，否則輸出"N0"，
輸入樣例:2 21 20
輸出樣例:
YE5 N0
思路：
很簡單的一題，就是這個YE5和N0也太tmd坑了，氣死我了！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll a[maxn];
ll sum[maxn];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll i=1;
ll sum=1;
ll cnt=1;
while(1)
{
cnt++;
i=i*2;
sum+=i;
if(n%sum==0)
{
cout<<"YE5"<<endl;
break;
}
if(cnt==15)
{
cout<<"N0"<<endl;
break;
}
}
}
}
7-10 這是一道簡單的模擬
財務計劃要從家里出發，去N個城市出差，然后再回到家中，但N個出差地點之間不一定都能通車，現在他要篩選出花費最少的路徑，你能幫幫他嗎？
輸入格式:第一行為兩個正整數N和M（1≤N≤300，1≤M≤?2??N(N+1)??），分別表示有N個出差地點和這些地點之間的M條通路，其中出差地點用1到N編號，而財務的家所在城市用編號0表示，
隨后的M行，每行給出通路連接的兩個城市和這條通路上的花費，格式為：
城市A 城市B 花費
通路是雙向的，且兩個城市間最多有一條通路，不存在自環，保證所有花費大于0，
再下一行給出一個正整數K，表示現在有K條推薦路徑（注意：給出的路徑不一定能通過或可能不滿足財務的要求），
接下來K行每一行表示一個推薦路徑，第一個整數n表示途徑的城市數，后面有n個整數x?i??(1≤x?i??≤N)表示途經的城市（不包括財務的家），如：
3 1 2 3
表示實際路徑為0→1→2→3→0， 輸出格式:
請你檢驗給出的K條推薦路徑，當它滿足：
1.給出的路徑能實際通車，即路徑中相鄰城市存在通路； 2.給出的路徑恰好能都到達N個出差城市一次，即不能漏掉某個城市，也不能重復到達，則稱這條路徑是可行的，
對于給出的K條推薦路徑，請輸出其中可行路徑中最少的花費，若不存在可行路徑，請輸出"-1"，(題目保證花費和不超過int范圍） 輸入樣例:
在這里給出一組輸入，例如：
5 10 0 1 5 0 5 12 1 2 2 2 3 8 3 4 13 1 3 11 0 2 5 0 4 9 4 5 6 3 5 7 5
5 1 3 2 3 1 5 3 2 1 4 5 5 2 1 3 5 4 6 1 2 3 4 5 1 5 1 2 3 5 4輸出樣例:
在這里給出相應的輸出，例如：
37
思路：
就是一道簡單的模擬題，有幾個小點要注意：
1、通路是雙向的，
2、恰好經過每個城市一次，
這題充分暴露了自己寫代碼其實不夠熟練，一次性的正確率太低，debug了好久還好被自己找出錯誤來了，但是浪費了大量的時間，
#include<bits/stdc++.h>
using namespace std;
int dp[305][305];//二維陣列記錄兩個城市通路的費用
int vis[305];//vis來標記有沒有經過這個城市
int f[305];
const int maxn=1000000000;//記錄最大值 下面好比較
int main()
{
int n,m;//n個出差地點 m條路
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,cost;//城市A 城市B 花費
cin>>a>>b>>cost;
dp[a][b]=cost;
dp[b][a]=cost;//注意通路是雙向的 都要記錄一下
}
int k;//k條路徑
cin>>k;
int res=maxn;
for(int i=1;i<=k;i++)
{
int num;
cin>>num;//途徑的城市數量
int flag=1;
int sum=0;
memset(vis,0,sizeof(vis));//每組路徑都記得要歸零 不然會有重復
for(int j=1;j<=num;j++)
{
cin>>f[j];
vis[f[j]]++;//表示這個城市已經訪問過了
}
for(int z=1;z<=n;z++)
{
if(vis[z]==0||vis[z]>1)//訪問過了或者沒有訪問到都不行
{
flag=0;
break;
}
}
if(flag==0)
{
sum=maxn;//sum的值歸位最大值表示路徑不存在
}
else{
for(int z=1;z<=num;z++)
{
if(dp[f[z-1]][f[z]]!=0)sum+=dp[f[z-1]][f[z]];
else
{
sum=maxn;
break;
}
}
}
if(sum!=maxn&&dp[f[num]][0]!=0)//最后還要回到家不要漏了
{
sum+=dp[f[num]][0];//加上回到家的錢
if(sum<res)res=sum;//完整的路徑的需要的話費
}
}
if(res==maxn)cout<<"-1";//不存在此條路徑
else cout<<res;
}
7-11 黑洞密碼
近些日子，某科學家接受到了來自外太空的神秘訊息，在經過了一段時間的研究后，科學家發現訊息是一個由字母和數字組成的字串str，想要破譯，需要通過一定的規則將字串進行轉換，規則如下：
1.確定訊息的長度為32； 2.字串中第4n+1～4n+4的字母和第4n+1～4n+4(0≤n≤3)的數字為一組，共4組； 3.每組的第1，2，3，4個字符分別往后推每組第1，2，3，4個數字個數 例：如第一個字母為a，第一個數字為3，轉換后變為d，'z'之后是'B','Z'之后是'b'; 4.將每組內部字母的順序顛倒； 5.將四組字符合并就是最后的訊息，輸入格式:
輸入一個長度為32的字串 輸出格式:
輸出轉換后的密碼 輸入樣例:
在這里給出一組輸入，例如：
Zzc6Ltw2OD4yR640263W7G8G30HW9C71
輸出樣例:
在這里給出相應的輸出，例如：
RgCgJQwxJfYCDeQG
思路：
這題其實也是一道模擬題，但是也有點小坑，一開始要仔細研究樣例的找出變化的規律
16個字母：ZzcL twOD yRWG GHWC
16個陣列：6246 4026 3783 0971
然后按照題目的規律，這里要注意：‘z’之后是’B’,‘Z’之后是’b’，一開始沒看到這句話，還以為題目出錯了，害，真實太難了
然后順序顛倒前：gCcR xwQJ CYfJ GQeQ
發現了規律事把每組都點到顛倒了一下最終得到了答案
RgCg JQwx JfYC DeQG
代碼：
#include<iostream>
using namespace std;
int cnt1, cnt2;
char xx[36] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','B','C','D','E','F','G','H','I','J' };//我是用的打表的笨辦法，因為最多往后右移9個，也不是很難做到
char dx[36] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','b','c','d','e','f','g','h','i','j' };//區分小寫 大寫就可以了
int main()
{
string s;
cin >> s;
char a[16];//記錄下字母
int b[16];記錄下數字
cnt1=0;//數字個數
cnt2=0;//字母個數
for (int i = 0; i < 32; i++)
{
if (s[i] >= '0' && s[i] <= '9')
{
b[cnt1] = s[i]-'0';//因為開的是int型的陣列，記得減去‘0’得到數字
cnt1++;//數字個數++
}
else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
{
a[cnt2] = s[i];
cnt2++;//字母個數++
}
}
for (int i = 0; i < 16; i++)
{
if(a[i]>='a'&&a[i]<='z')
{
for(int j=0;j<35;j++)//找到表中對應的位置
{
if(a[i]==xx[j])
{
a[i]=xx[j+b[i]];//加上需要向后移動的位置就是變換成的字母了
break;
}
}
}
else if(a[i]>='A'&&a[i]<='Z')//同理
{
for(int j=0;j<35;j++)
{
if(a[i]==dx[j])
{
a[i]=dx[j+b[i]];
break;
}
}
}
}
int count=4;
while(1)
{
if(count>32)break;//一共輸出16個
for(int i=count-1;i>=count-4;i--)//每四個顛倒一次順序后再輸出
{
cout<<a[i];
}
count+=4;
}
}
7-12 建立火車站
新冠疫情，導致了各個城市之間物資輸送的障礙，假設有N個城市在一條直線上，為了物資能順利抵達各個城市，可以在路線上建立最多個數為K個暫時停靠站，由于火車在兩個站臺（城市也算站臺）之間的距離越近，需要的總花費越少，因此我們需要讓火車相鄰兩個站臺之間的最大距離最小，求出距離L,2
≤N ≤100000, 0 ≤K ≤100000，所有城市坐標小于等于10^12，且不存在負值，提醒：
城市坐標均為正整數，且停靠站只能建在整數坐標點上，
輸入格式:第一行輸入城市個數N，可建立停靠站個數K， 第二行輸入N個城市的坐標（不保證前一個城市坐標比后一個城市小），
輸出格式:
輸出L
輸入樣例:
2 2 4 106
輸出樣例:
34
思路：
是一道很好的二分答案的題目，我對二分答案的理解就是使用二分法更快的列舉出答案，
比如說這題，他是先找出一個mid，“假裝”他就是本題的解了，然后再一一和兩個車站間的距離進行比較，如果這兩個車站的距離比mid要大，那就要塞一個臨時車站進去，如果兩個車站距離小于等于mid，那就是符合條件的，繼續往后看就行了，最后，看這種情況下需要塞幾個臨時車站進去，將這個數量和題目給的最大能塞的車站數進行比較，
對于我們最后站臺之間相鄰距離的最大值L，隨著L的增大，我們需要設定的站臺數量只可能變少不可能變多，滿足二分條件，存在某一個值x，使得當L>=x時，站臺數量<=k，
可以借此寫出一個二分，
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
ll num[maxn];
ll dis[maxn];//記錄兩個相鄰車站間的距離
int n,k;//n個城市 k個暫時停靠站
bool check(ll x)//判斷mid
{
ll sum=0;
for(int i=1;i<n;i++)
{
if(dis[i])
{
ll temp=dis[i]/x;
if(dis[i]%x) temp++;//可能正好等于mid的情況 所以要特別判斷一下
sum+=temp-1;
}
}
if(sum<=k)return 1;
else return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%lld",&num[i]);
}
sort(num,num+n);//按順序排好
bool flag=1;//可能會有車站重合的情況
for(int i=1;i<n;i++)
{
dis[i]=num[i]-num[i-1];
if(dis[i]!=0) flag=0;
}
if(flag) printf("0\n");//車站重合在了一個點上
else
{
ll l=1,r=1e12;//由所有城市坐標小于等于10^12，所以令r=1e12
while(l<r)//二分法開始！
{
ll mid=(l+r)/2;//選中一個mid小朋友假裝它是答案
if(check(mid)==1) r=mid;//mid選的大了 臨時停靠站沒有用滿 所以要縮小mid再進行比較
else l=mid+1;//mid選的小了 需要更多的臨時停靠站 所以要增大mid進行比較
}
printf("%lld\n",l);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255308.html
標籤：其他
下一篇：魔改合成大西瓜