算法-Day04

今天還是給大家分享幾道題目,希望大家可以好好理解。

第一題

問題描述

小藍有一天誤入了一個混境之地。

好消息是:他誤打誤撞拿到了一張地圖,并從中獲取到以下信息:

  1. 混境之地是一個?n?m大小的矩陣,這個地圖中一共有四種磁場,記為?ABCD?。
  2. 他現在所在位置的坐標為?(x1,y1)而這個混境之地出口的坐標為?(x2?,y2?)?。

壞消息是:

  1. 當你站在磁場為?A?的方塊上時,你下一步只能走到磁場為?B?的方塊上。
  2. 當你站在磁場為?B?的方塊上時,你下一步只能走到磁場為?C?的方塊上。
  3. 當你站在磁場為?C?的方塊上時,你下一步只能走到磁場為?D?的方塊上。
  4. 當你站在磁場為?D?的方塊上時,你下一步只能走到磁場為?A?的方塊上。

小藍可以往上下左右四個方向行走。

小藍想知道他能否逃離這個混境之地,如果可以逃離這里,輸出?Yes?,反之輸出?No?。

輸入格式

第一行輸入兩個正整數?n,m表示矩陣的大小。

第二行輸入四個正整數?x1,y1,x2,y2,表示小藍當前所在位置的坐標,以及混境之地出口的坐標。

接下來?n?行?m列為混境之地的矩陣,其中?ABCD?代表不同磁場,僅包含?ABCD?四種字符。

輸出格式

輸出數據共一行一個字符串:

  • 若小藍可以逃離混境之地,則輸出?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×qp, q為質數),則k本身必須是質數或 1。
  • 證明
    k2 = p×q,其中p ≤ q為質數。
    • k=1,則12=1×1,但 1 不是質數,不成立。
    • k是質數p,則k2 = p×p(兩個相同質數的乘積),成立。
    • k是合數,設k = m×nm,n>1),則k2 = m2×n2,此時m2n2至少有一個不是質數(因平方數除 1 外非質數)。

好了,今天的分享就到這里,希望大家多多關注。

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

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

相關文章

Git版本控制詳細資料

Git安裝基本配置 下載安裝(一路next) 打開bash終端&#xff08;git專用&#xff09; 命令: git -v(查看版本號) 配置: 用戶名和郵箱,應用在每次提交代碼版本時表明自己身份 命令: git config --global user.name "FT" git config --global user.email "F…

利用井云平臺把Coze工作流接入小程序/網站封裝變現 | 詳細步驟→

今天來看看怎么把Coze工作流接入井云生成你的專屬網站/小程序&#xff01; 當前已支持三大模塊接入&#xff1a;? 工作流 ? 智能體 ? 外部網頁 本文所用工具 1、扣子&#xff1a;www.coze.cn 2、井云智能體&#xff1a;jingyun.center 為什么選擇井云平臺&#xff1f; …

linux weston flutter remote desktop

參考:Outputs — weston 14.0.90 documentation Weston 14.0: DRM-backend, color management, and output mirroring Weston 14.0: DRM-backend, color management, and output mirroring ??? 3. DRM 輸出可鏡像至遠程輸出(RDP、VNC、PipeWire) 這次更新還帶來了一個…

GitHub Copilot 是什么,怎么使用

GitHub Copilot 是一個由 GitHub 和 OpenAI 聯合開發的 AI 編程助手&#xff0c;它可以在你寫代碼的時候自動給出建議、補全代碼&#xff0c;甚至生成整個函數或算法。它就像一個“聰明的副駕駛”&#xff0c;時刻在你旁邊協助你寫代碼。 簡單解釋&#xff1a; GitHub Copilot …

Android系統及應用QUIC協議支持詳解

QUIC協議在Android中的全面支持與實踐指南 本文深入探討QUIC協議在Android中的實現細節&#xff0c;涵蓋基礎原理、開發技巧、性能優化及前沿擴展&#xff0c;提供完整的Kotlin代碼示例和工程實踐指南。 1. QUIC協議核心優勢 QUIC&#xff08;Quick UDP Internet Connections&…

.NET基于類名約定的自動依賴注入完整指南

&#x1f680; .NET基于類名約定的自動依賴注入完整指南 基于類名約定的自動依賴注入可大幅減少手動注冊服務的工作量&#xff0c;本文將通過清晰的結構、美觀的排版和豐富的示例&#xff0c;幫助你快速掌握這一實用技術。 &#x1f308; 核心特性概覽 特性說明類名約定自動…

Redis各數據結構的詳細使用和使用場景

Redis各數據結構的詳細使用 大家好&#xff01;今天我們來聊聊Redis這個強大的內存數據庫。就像我們生活中的工具箱一樣&#xff0c;Redis提供了多種"工具"&#xff08;數據結構&#xff09;來幫助我們解決不同的問題。有些工具像螺絲刀&#xff08;字符串&#xff…

MSYS2 環境下 Python 開發配置(結合 PyCharm)使用筆記

【筆記】MSYS2 的 MinGW64 環境中正確安裝 Python 相關環境管理工具 &#xff08;Poetry、Virtualenv、Pipenv 和 UV&#xff09;-CSDN博客 MSYS2 環境配置與 Python 項目依賴管理筆記_msys更新python-CSDN博客 【技術筆記】MSYS2 指定 Python 版本安裝方案_pacman -u 安裝指定…

Python爬蟲實戰:研究Splinter相關技術

1. 引言 1.1 研究背景與意義 隨著 Web 2.0 技術的發展,現代網頁越來越多地采用 JavaScript 動態生成內容。傳統爬蟲通過直接請求 HTML 頁面的方式,無法獲取這些動態渲染的內容,導致爬取數據不完整。據統計,全球前 1000 名網站中,超過 70% 的頁面包含動態加載內容 。Spli…

大氣商務工作匯報總結PPT模版分享

藍色商務工作總結PPT模版&#xff0c;莫蘭迪工作總結PPT模版&#xff0c;年中工作匯報PPT模版&#xff0c;簡約工作匯報PPT模版&#xff0c;上半年工作總結PPT模版&#xff0c;極簡工作匯報PPT模版&#xff0c;歐美簡約PPT模版&#xff0c;大氣商務通用PPT模版&#xff0c;團隊…

5G modem開發

鏈接文章&#xff1a;https://zhuanlan.zhihu.com/p/709130546 OpenHarmony RIL架構 鏈接文章&#xff1a;https://blog.csdn.net/weixin_42571280/article/details/148566029 在移動通信設備中&#xff0c;無線接口層&#xff08;Radio Interface Layer&#xff0c;簡稱RIL&…

Gartner《AI-Driven Methods for Cost-Efficiency》學習心得

一、背景介紹 在當前經濟形勢下,企業面臨著成本上升與收入增長放緩的雙重壓力。Gartner 的這份報告指出,大多數企業對 AI 的投資主要集中在提升用戶生產力方面,但短期內投資回報率有限。鑒于經濟的不確定性以及成本壓力,尤其是生成式 AI(GenAI)技術,若應用于財務效率和…

人臉識別技術是自動化還是智能化?

人臉識別技術兼具自動化與智能化的雙重特性。它通過自動采集圖像、預處理圖像、提取特征以及進行識別比對等操作&#xff0c;實現了高效且無需人工干預的識別流程&#xff0c;展現出強大的自動化能力。同時&#xff0c;它還具備自適應學習能力&#xff0c;能夠根據新的數據和場…

樹結構的實際應用之堆排序

樹結構的實際應用之堆排序 基本介紹 堆排序是利用堆這種數據結構設計而成的一種排序算法&#xff0c;堆排序是一種選擇排序&#xff0c;它的最壞&#xff0c;最好&#xff0c;平均時間復雜度為O(logn)&#xff0c;它也是不穩定排序。堆是具有以下性質的完全二叉樹&#xff1a;…

用OBS Studio錄制WAV音頻,玩轉語音克隆和文本轉語音!

言簡意賅的講解OBS Studio解決的痛點 隨著AI技術的快速發展&#xff0c;語音克隆與文本生成語音技術越來越受歡迎。無論你想要制作個人虛擬主播&#xff0c;還是給自媒體視頻配音&#xff0c;擁有高質量的原始音頻都是關鍵。本文詳細教你使用免費且功能強大的軟件——OBS Stud…

LangChain-5-agent

概述 Agent 是一種能夠基于接收到的輸入&#xff0c;利用自身的決策邏輯和可用的工具&#xff0c;動態地規劃并執行一系列操作&#xff0c;以達成特定任務的程序或系統。它在與外界交互過程中&#xff0c;會根據實時情況靈活調整策略&#xff0c;而不是按照固定的預設流程執行…

操作系統進程與線程核心知識全覽

本博客&#xff0c;根據王道所學。以下為第二章節知識點&#xff1a; 進程的概念、組成、狀態與其轉換、進程間通信、信號&#xff1b; 單/多線程模型、線程管理、調度時機的切換、調度的目標、調度算法、多處理機調度&#xff1b; 同步與互斥、進程互斥的軟硬件實現方法、信號…

C++中類型轉換操作符知識介紹

文章目錄 **一、類型轉換操作符的語法與定義****二、工作原理****三、示例&#xff1a;基本類型轉換****四、示例&#xff1a;轉換為自定義類型****五、與構造函數的對比****六、注意事項****七、應用場景****八、與 C 其他類型轉換的關系****九、總結** 在C中&#xff0c;類型…

2048小游戲C++板來啦!

個人主頁&#xff1a;PingdiGuo_guo 收錄專欄&#xff1a;C干貨專欄 大家好呀&#xff0c;我是PingdiGuo_guo&#xff0c;今天我們來學習如何用C編寫一個2048小游戲。 文章目錄 1.2048的規則 2.步驟實現 2.1: 初始化游戲界面 2.1.1知識點 2.1.2: 創建游戲界面 2.2: 隨機…

TensorFlow深度學習實戰——Transformer變體模型

TensorFlow深度學習實戰——Transformer變體模型 0. 前言1. BERT2. GPT-23. GPT-34. Reformer5. BigBird6. Transformer-XL7. XLNet8. RoBERTa9. ALBERT10. StructBERT11. T5 和 MUM12. ELECTRA13. DeBERTa14. 進化 Transformer 和 MEENA15. LaMDA16. Switch Transformer17. RE…