C語言算法題

c語言算法題

題目一

加速度計是測量加速度的儀表。加速度測量是工程技術提出的重要課題。

要知道各瞬時飛機、火箭和艦艇所在的空間位置，可通過慣性導航系統連續地測出其加速度，然後經過積分運算得到速度分量，再次積分得到一個方向的位置坐标信号，而三個坐标方向的儀器測量結果就綜合出運動曲線并給出每瞬時航行器所在的空間位置。

再如某些控制系統中，常需要加速度信号作為産生控制作用所需的資訊的一部分，這裡也出現連續地測量加速度的問題。能連續地給出加速度信号的裝置稱為加速度傳感器。

但是，加速度計并非每一次傳回的數值都是準确且穩定的，我們需要進行"濾波”，即人為地過濾掉顯然錯誤的資料。

給定一個長度為n的數組，即加速度計周期性發出的連續的n組資料。已知加速度計發出的每一個資料都可正可負。你的任務是:在這組資料中找出一個子列(即從長度為n的數組中任意截取連續的一段作為新的數組)，使得這個子列的和最大。

第一行是一個整數n表示加速度計發出的資料長度第二行是n個用空格分開的整數，表示加速度計的資料

一行一個整數，表示最大子列和

5

1 -1 1 -1 1

1

6

-1 3 -2 4 5 -6

10

對于50%的資料，1<=n<=500

對于70%的資料，1<=n<=5000

對于100%的資料，1<=n<=500000、1<=|a[i] <=100

對于第一個樣例:

最大子列和為1或1+(-1)+1=1或1+(-1)+1+(-1)+1=1對于第二個樣例:

最大子列和為3+(-2)+4+5=10

沒有其他的方案能産生更大的子列和

題目二

東道主讓現場所有的n名步兵圍成一個圓圈，并聲明以下規則:1号位置的步兵擊殺2号位置的步兵，3号位置的步兵擊殺4号位置的步兵，5号位置的步兵擊殺6号位置的步兵....以此類推,直到最後隻剩下一名步兵。

然而自诩南航長空禦風戰隊最優秀的機器人，我們的步兵将這次的遊戲看成了對他的一次試煉。他并不想被任何步兵所殺死，因為這樣會讓他感到丢臉，以至于當場爆炸。長空禦風的隊員們并不想在上賽場之前就失去這樣一名優秀的戰鬥力，是以我們需要在步兵圍成圓圈之前，為他找到一個合适的位置，使得我們的步兵能夠成為最後一個剩下的步兵。

一個整數n,表示前來交流的步兵數目。

一個整數p，表示最後一個剩下的步兵的位置。

128

對于70%的資料，1<=n<=1000000對于30%的資料，1<=n<=1000000000

對于第一個樣例，每次剩下的步兵的位置編号應發生如下變化:

1 2 3 4 5 6

1 3456

1 3 56

1 3 5

1 5

是以輸出為5

題目3

2021 robomaster機甲大師超級對抗賽中部區域賽比賽場地設立在浙江省杭州市湖州街51号浙江大學城市學院。

比賽現場共設定有把長椅，題目假設每把長椅上可以坐下的人數無上限。由于一部分觀衆就是城市學院的學生，是以在校外觀衆入場之前，第i把長椅上已經坐下了a[1]個人。現在，會新來m位校外觀衆，這m個人每人都會随機找一把長椅并坐下。

由于新冠疫情的影響，舉辦方并不希望存在一把長椅坐下了太多的人。是以，舉辦方找到了你，希望你幫忙求出:在已經就坐的人不改變座位的條件下，新來了m個人之後，人數最多的那把長椅上最少可能會有多少人?最多可能會有多少人?

第一行為1個整數n，表示有n把長椅第二行為1個整數m，表示會新來m個人

第三行為用空格隔開的a[2]，表示第i把長椅上最初有a[i]個人

一行兩個整數，分别表示來了m個人之後，人數最多的那把長椅上最少會有的人數、最多會有的人數。

4

1 1 1 1

3 7

7612410 5 183

10 20

對于40%的資料，1<=n,m<=5000

對于20%的資料，1<=n,m<=50000

對于40%的資料，1<=n,m<=500000

對于100%的資料，1<=a[i]<=500

對于第一個樣例，如下是所有的不考慮椅子順序讓人數最多的椅子上人數最少的座位方案:

3331

3322

不會再有其他的方案使得人數最多的那把椅子上人數最少。

題目4

第一行為兩個用空格隔開的整數n m

接下來n行，每行m個數字，用空格隔開，僅為0(白色)或1(黑色)。

一行一個整數，為最大黑色正方形的邊長。

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

2

6 9

1 0 1 1 1 1 1 1 1

1 1 0 0 0 0 1 1 1

0 0 0 1 1 1 1 1 1

0 0 0 1 1 1 0 0 0

1 0 0 1 1 1 1 1 1

0 0 0 1 1 1 1 0 0

3