今天還是給大家分享幾道題目,希望大家可以好好理解。
第一題
問題描述
小藍有一天誤入了一個混境之地。
好消息是:他誤打誤撞拿到了一張地圖,并從中獲取到以下信息:
- 混境之地是一個?n?m大小的矩陣,這個地圖中一共有四種磁場,記為?
A
,B
,C
,D
?。 - 他現在所在位置的坐標為?(x1,y1)而這個混境之地出口的坐標為?(x2?,y2?)?。
壞消息是:
- 當你站在磁場為?
A
?的方塊上時,你下一步只能走到磁場為?B
?的方塊上。 - 當你站在磁場為?
B
?的方塊上時,你下一步只能走到磁場為?C
?的方塊上。 - 當你站在磁場為?
C
?的方塊上時,你下一步只能走到磁場為?D
?的方塊上。 - 當你站在磁場為?
D
?的方塊上時,你下一步只能走到磁場為?A
?的方塊上。
小藍可以往上下左右四個方向行走。
小藍想知道他能否逃離這個混境之地,如果可以逃離這里,輸出?Yes
?,反之輸出?No
?。
輸入格式
第一行輸入兩個正整數?n,m表示矩陣的大小。
第二行輸入四個正整數?x1,y1,x2,y2,表示小藍當前所在位置的坐標,以及混境之地出口的坐標。
接下來?n?行?m列為混境之地的矩陣,其中?A
,B
,C
,D
?代表不同磁場,僅包含?A
,B
,C
,D
?四種字符。
輸出格式
輸出數據共一行一個字符串:
- 若小藍可以逃離混境之地,則輸出?
Yes
?。 - 若小藍無法逃離混境之地,則輸出?
No
?。
輸入案例:
5 5
1 1 5 5
ABCDA
ABCDB
ABCDC
ABCDD
ABCDA
輸出案例:
Yes
代碼部分:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
bool vis[N][N];
char c[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
ll n,m,sx,sy,fx,fy;
bool check(ll x,ll y,ll nx,ll ny){if(c[x][y]=='A'&&c[nx][ny]=='B')return true;if(c[x][y]=='B'&&c[nx][ny]=='C')return true;if(c[x][y]=='C'&&c[nx][ny]=='D')return true;if(c[x][y]=='D'&&c[nx][ny]=='A')return true;else return false;
}
bool bfs(int x,int y){
if(x==fx&&y==fy)return true;
vis[x][y]=true;
for(int j=0;j<4;j++){int nx=x+dx[j];int ny=y+dy[j];if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])continue;if(check(x,y,nx,ny)){if(bfs(nx,ny))return true;}
}
return false;
}
int main()
{cin>>n>>m>>sx>>sy>>fx>>fy;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];}}bool flag=bfs(sx,sy);if(flag==true)cout<<"Yes";else cout<<"No";return 0;
}
這是一道經典的bfs問題,是一道比較傳統的bfs問題。
這道題要注意調用bfs過程中返回true,來終止遞歸,要理解出口的意思。
第二題:
問題描述
小藍現在有一個長度為?n僅由小寫字母組成的的字符串?s?,小藍可以對字符串進行任意次操作,每次操作小藍可以選擇一個整數?i?,其中 i∈[1,n?1]?,然后選擇如下兩種操作之一:
- 將?si變為其字典序加一的小寫字母,si+1??變為其字典序減一的小寫字母。
- 將?si??變為其字典序減一的小寫字母,si+1變為其字典序加一的小寫字母。
小藍想知道通過操作?s可以變成的最小字典序字符串是什么,但是小藍不擅長字符串問題,請你幫小藍解決這個問題。
注意:操作過程中要保證?s始終是由小寫字母組成的字符串。
輸入格式
第一行輸入一個整數,代表?n?。
第二行輸入一個長度為?n僅由小寫字母構成的字符串,代表?s?。
輸出格式
輸出一行一個字符串,代表?s?可以變成的字典序最小的字符串。
輸入案例:
2
cb
輸出案例:
ad
代碼部分:
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
long long sum;
int main()
{cin>>n>>s;for(int i=0;i<n;i++){sum+=s[i]-'a';s[i]='a';}for(int i=n-1;i>=0;i--){if(sum>=25){s[i]='z';sum-=25;}else{s[i]='a'+sum;sum=0;}}cout<<s;return 0;
}
注意這類題目有一個特點就是可以將數組中的或者字符串中的內容變成同一個數,然后統計變化量,再根據題意來做后面處理。
第三題:
問題描述
小藍面臨一個數學問題:給定一個整數?S,他需要構造出一個長度為?n?的序列,其中每個數都在?[l,r]范圍內,并且整個序列的和值為?S。
當然,這樣的結果會有很多,小藍希望你幫助他構造出字典序最小的滿足條件的序列。
輸入格式
輸入包含四個整數?S、n、l和?r,分別表示目標和值,序列的長度,以及每個數的取值范圍。
輸出格式
輸出一個長度為?n?的序列,每兩個數之間用空格分隔,如果無法構造,輸出??1。
輸入案例:
10 3 2 5
輸出案例:
2 3 5
代碼部分:
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int main()
{vector<int>num(N);long long s,n,l,r;cin>>s>>n>>l>>r;if(n*r<s||n*l>s){cout<<-1;return 0;}for(int i=0;i<n;i++){num[i]=l;}int sum=s-n*l;for(int i=n-1;i>=0;i--){if(sum>=r-l){num[i]=r;sum=sum-r+l;}else{num[i]=l+sum;break;}}for (int i = 0; i < n; i++) {if (i > 0) {cout << " ";}cout << num[i];}return 0;
}
這道題和第二題是類似的,思路相同。
第四題:
題目背景
在一個神奇的魔法世界中,有一座古老的迷幻之城。迷幻之城被分成?n?個島嶼,編號從?1?到?n,共有?m?座橋。迷幻之城的居民們希望能夠建立起緊密的聯系,每個島嶼上的居民都想知道自己最多能到達多少個島嶼。
請你編寫程序解決這個問題。
輸入格式
第一行包含兩個整數?n和?mm(1≤n≤105,0≤m≤min105,2n(n?1)?),表示島嶼的數量和橋的數量。
接下來?m行,每行包含兩個整數 ui?,vi? (1≤ui?,vi?≤n),表示編號為?ui和?vi??的島嶼之間有一座橋。
輸出格式
輸出一行包含?n個以空格分隔的整數,第?i?個整數表示編號為?i的島嶼上的居民最多能到達的島嶼個數。
代碼部分:
#include <bits/stdc++.h>
using namespace std;
int a[100005],pre[100005],siz[100005],n,m;void init(){for(int i=1;i<=n;++i)pre[i]=i,siz[i]=1;
}int root(int x){return pre[x]==x?x:root(pre[x]);
}void merge(int x, int y)
{int rx = root(x), ry = root(y);if(rx == ry)return;//已經連通,無需處理//如果rx更大,則交換,可以保證siz[rx] <= siz[ry]if(siz[rx] > siz[ry])swap(rx, ry);//此時有siz[rx] <= siz[ry],所以一定是rx -> rypre[rx] = ry;siz[ry] += siz[rx];//操作完成后rx將不再作為根,于是它的siz也沒有意義了,也不會再變化了
}int main()
{cin>>n>>m;init();for(int i=1;i<=m;++i){int x,y;cin>>x>>y;merge(x,y);}for(int i=1;i<=n;i++){cout<<siz[root(i)]<<" ";}return 0;
}
這道題用的是合并集的思想,這種問題是模版問題,大家可以看看理解理解。
第五題:
問題描述
在接下來的?N天里(編號從1到?N),坤坤計劃烹飪披薩或西蘭花。他寫下了一個長度為?N?的字符串?A,對于每個有效的?i,如果字符?Ai?是 '1',那么他將在第?ii?天做披薩,如果?Ai是 '0',他將在這一天做西蘭花。
坤坤的兒子小沸,就像大多數孩子一樣,喜歡披薩但討厭西蘭花。他想選擇一個?A?的長度為?K?的子串,并將這個子串中的每個字符 '0' 改為 '1'。然后,讓我們定義披薩時間為坤坤連續做披薩的最大天數。請找出小沸可以達到的最大披薩時間。
輸入格式
第一行包含兩個用空格分隔的整數?N和?K(1≤K≤N≤103)。
第二行包含一個長度為?N的只包含?0
?和?1
?的字符串?A。
輸出格式
打印一行,其中包含一個整數——最大的披薩時間。
輸入案例:
13 2
0101110000101
輸出案例:
5
代碼部分:
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int prefix[N],suff[N];
char s[N];
int ans;
int main()
{int n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>s+1;for(int i=1;i<=n;i++){if(s[i]=='0')prefix[i]=0;else{prefix[i]=prefix[i-1]+1;}}for(int i=n;i>=1;i--){if(s[i]=='0')suff[i]=0;else{suff[i]=suff[i+1]+1;}}for(int i=k;i<=n;i++){int j=i-k+1;ans=max(ans,k+prefix[j-1]+suff[i+1]);}cout<<ans;return 0;
}
這道題巧妙用了前綴和以及后綴和的思想,對于這個問題大家要注意題目一般會要求讓你求解某一段連續數字,然后可以更改某一部分的值。這類問題可以以更改部分的長度為兩端點,然后向兩端延伸。
第六題:
問題描述
依依有個長度為?n的序列?a,下標從?1開始。
她有?m次查詢操作,每次她會查詢下標區間在?[li?,ri?]?的?a中元素和。她想知道你可以重新排序序列?a,使得這?m次查詢的總和最小。
求你求出?mm?次查詢總和的最小值。
輸入格式
第一行輸入兩個整數?n,m(1≤n,m≤105),表示序列?a?的長度以及查詢次數。
第二行輸入?n個整數?ai?(1≤ai≤105),表示序列?a?中的元素。
接下來?m行,每行輸入兩個整數?li,ri(1≤li?≤ri?≤n),表示詢問的下標區間。
輸出格式
輸出僅一行,包含一個整數,表示?m?次查詢總和的最小值。
輸入案例:
3 2
1 2 3
1 2
2 3
輸出案例:
7
代碼部分:
#include <bits/stdc++.h>
using namespace std;
long long sum;
const int N=1e5+10;
int a[N],diff[N],cnt[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);while(m--){int l,r;cin>>l>>r;diff[l]++;diff[r+1]--;}for(int i=1;i<=n;i++){cnt[i]=diff[i-1]+cnt[i-1];}sort(cnt+1,cnt+1+n,greater<int>());for(int i=1;i<=n;i++){sum+=a[i]*cnt[i];}cout<<sum;return 0;
}
這道題是前綴差的標準題目,大家可以記住這種題目的模版。統計某一區間數的個數,這一區間的長度發生變化,用數組來記錄這個統計的個數。
第七題:
問題描述
小藍現在有一個長度為?n僅由小寫字母組成的的字符串?s?,小藍可以對字符串進行任意次操作,每次操作小藍可以選擇一個整數?i,其中 i∈[1,n?1]?,然后選擇如下兩種操作之一:
- 將?si??變為其字典序加一的小寫字母,si+1??變為其字典序減一的小寫字母。
- 將?si變為其字典序減一的小寫字母,si+1??變為其字典序加一的小寫字母。
小藍想知道通過操作,?s最終可以變成多少種不同的字符串,但是小藍不擅長計數問題,請你幫小藍解決這個問題。
注意:操作過程中要保證?s始終是由小寫字母組成的字符串。
輸入格式
第一行輸入一個整數,代表?n?。
第二行輸入一個長度為?n僅由小寫字母構成的字符串,代表?s?。
輸出格式
輸出一個數字,表示能夠產生的字符串的種類數(結果對 1e9+7 取模)。
輸入案例:
2
cb
輸出案例:
4
代碼部分:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int sum,dp[202][5004];
int main() {int n;cin>>n;for(int i=1;i<=n;i++){char x;cin>>x;sum+=x-'a';}dp[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=sum;j++)for(int k=0;k<=min(j,25);k++)dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;cout<<dp[n][sum];return 0;
}
這道題難度其實很大的,發現很難解決,可以看看能不能用動態規劃解決,前一部分對于后一部分的影響。
第八題:
問題描述
小藍非常熱愛數學,一天老師給小藍出了一道數學題,想鍛煉鍛煉小藍的思維能力。題目是這樣的:給定兩個數?a?和?b,在?a?到?b(包括?a,b)之間所有數的平方當中,試問有幾個數能夠表示為?x×y?的形式,其中?x?和?y?是質數。你能幫助小藍一起來解決這個問題嗎?
輸入格式
第一行兩個正整數?a,b,含義同題目所示。
輸出格式
輸出共一行,輸出一個整數,代表那些能夠表示為題目描述的形式的平方數的數量。
輸入案例:
1 5
輸出案例:
3
代碼部分:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int prime[N];
int ans;
void isprime(int n){for(int i=1;i<=n;i++)prime[i]=1;prime[0]=0;prime[1]=0;for(int i=2;i<=n;i++){for(int j=2*i;j<=n;j+=i){prime[j]=0;}}
}
int main()
{int a,b;cin>>a>>b;int x=1e5+5;isprime(x);for(int i=1;i<=x;i++){if(prime[i]&&i>=a&&i<=b)ans++;}cout<<ans;return 0;
}
這道題肯定有疑問,為什么說是要等于平方,但是只統計了一個質數的個數,這是因為對于一個完全平方數。
- 若
k2 = p×q
(p, q
為質數),則k
本身必須是質數或 1。 - 證明:
設k2 = p×q
,其中p ≤ q
為質數。- 若
k=1
,則12=1×1
,但 1 不是質數,不成立。 - 若
k
是質數p
,則k2 = p×p
(兩個相同質數的乘積),成立。 - 若
k
是合數,設k = m×n
(m,n>1
),則k2 = m2×n2
,此時m2
和n2
至少有一個不是質數(因平方數除 1 外非質數)。
- 若
好了,今天的分享就到這里,希望大家多多關注。