切面條-藍(lán)橋杯-基礎(chǔ)-CSDN算法技能樹https://edu.csdn.net/skill/algorithm/algorithm-530255df51be437b967cbc4524fe66ea?category=188

目錄

切面條

大衍數(shù)列

門牌制作

方陣轉(zhuǎn)置

微生物增殖

成績統(tǒng)計

星系炸彈

判斷閏年的依據(jù):

特別數(shù)的和

?*日志統(tǒng)計*（雙指針）

雙指針

?猜年齡

合并檢測

排它平方數(shù)

?*四平方和定理*

*大數(shù)乘法*

---

切面條

一根高筋拉面，中間切一刀，可以得到2根面條。

如果先對折1次，中間切一刀，可以得到3根面條。

如果連續(xù)對折2次，中間切一刀，可以得到5根面條。 那么，連續(xù)對折10次，中間切一刀，會得到多少面條呢？

想法：

找規(guī)律

1、不對折（對折零次），從中間切一刀，得到?2?根面條，?2 = 2
2、對折一次，從中間切一刀，得到?3?根面條，?3 = 2 + 2^0
3、對折兩次，從中間切一刀，得到?5?根面條，?5 = 2 + 2^0 + 2^1
4、對折三次，從中間切一刀，得到?9?根面條，?9 = 2 + 2^0 + 2^1 + 2^2
…
11、對折十次，從中間切一刀，得到?2 + 2^0 + 2^1 + 2^2 + ...... + 2^9?根面條

#include <stdio.h>int cut_noodles(int times)
{int result = 2, t = 1;for (int i = 0; i < times; i++){result += t;t = t * 2;}return result;
}int main()
{int result;int times = 0;result = cut_noodles(times);printf( "對折 %d 次從中間切一刀得到的面條數(shù)是: %d\n", times, result);return 0;
}

大衍數(shù)列

中國古代文獻(xiàn)中，曾記載過“大衍數(shù)列”, 主要用于解釋中國傳統(tǒng)文化中的太極衍生原理。

它的前幾項是：0、2、4、8、12、18、24、32、40、50 …

其規(guī)律是：對偶數(shù)項，是序號平方再除2，奇數(shù)項，是序號平方減1再除2。

以下的代碼打印出了大衍數(shù)列的前 100 項。

請?zhí)钛a空白處的內(nèi)容。

#include <stdio.h>
int main()
{int i;for (i = 1; i <= 100; i++){if (__________________)printf("%d ", i * i / 2);elseprintf("%d ", (i * i - 1) / 2);}printf("\n");
}

想法：?

其規(guī)律是：對偶數(shù)項，是序號平方再除2，奇數(shù)項，是序號平方減1再除2。?

i%2==0

門牌制作

小藍(lán)要為一條街的住戶制作門牌號。

這條街一共有 2020 位住戶，門牌號從 1 到 2020 編號。

小藍(lán)制作門牌的方法是先制作 0 到 9 這幾個數(shù)字字符，最后根據(jù)需要將字符粘貼到門牌上，例如門牌 1017 需要依次粘貼字符 1、0、1、7，即需要 1 個字符 0，2 個字符 1，1 個字符 7。

請問要制作所有的 1 到 2020 號門牌，總共需要多少個字符 2？

#include <bits/stdc++.h>
using namespace std;
int main()
{int ans = 0, x;for (int i = 1; i <= 2020; i++){x = i;while (x){________________;}}cout << ans;return 0;
}

提示：

利用循環(huán)將當(dāng)前數(shù)字的每一位求出，分別進(jìn)行判斷即可

?利用循環(huán)將當(dāng)前數(shù)字的每一位求出，分別進(jìn)行判斷即可

#include <iostream>
using namespace std;int ans;void check(int n)
{while(n){int t = n % 10;if(t == 2) ans ++;n /= 10;}
}int main()
{for (int i = 1; i <= 2020; i ++)check(i);cout << ans << endl;return 0;		
}

另一種比較笨拙 但比較好理解的方法:

雖然有點笨拙，但比較好理解。
let count = 0;
for (let i = 1; i <= 2020; i++) {
let x = i;
//個位符合的x, 并摘掉個位的2 = 符合的個數(shù);
if (x % 10 == 2) {
x -= 2;
// console.log(x);
count++;
}
//十位符合的x, 并摘掉十位的2 = 符合的個數(shù);
if (parseInt(x / 10) % 10 == 2) {
x -= 20;
// console.log(x);
count++;
}
//百位符合的x, 并摘掉百位的2 = 符合的個數(shù);
if (parseInt(x / 100) % 10 == 2) {
x -= 200;
// console.log(x);
count++;
}
//千位符合的x, 并摘掉千位的2 = 符合的個數(shù);
if (parseInt(x / 1000) % 10 == 2) {
x -= 2000;
// console.log(x);
count++;
}
}
console.log('符合個數(shù):' + count);
//結(jié)果624

?

?

方陣轉(zhuǎn)置

問題描述

給定一個n×m矩陣相乘，求它的轉(zhuǎn)置。其中1≤n≤20，1≤m≤20，矩陣中的每個元素都在整數(shù)類型（4字節(jié)）的表示范圍內(nèi)。

輸入格式

第一行兩個整數(shù)n和m；

第二行起，每行m個整數(shù)，共n行，表示n×m的矩陣。數(shù)據(jù)之間都用一個空格分隔。

輸出格式

共m行，每行n個整數(shù)，數(shù)據(jù)間用一個空格分隔，表示轉(zhuǎn)置后的矩陣。

樣例輸入

2 4
34 76 -54 7
-4 5 23 9

樣例輸出

34 -4
76 5
-54 23
7 9

請從以下四個選項中選擇正確的代碼填補空白處，實現(xiàn)方陣轉(zhuǎn)置功能。

提示：

對一個方陣轉(zhuǎn)置，就是把原來的行號變列號，原來的列號變行號

#include <bits/stdc++.h>
using namespace std;int main()
{int m, n;int a[20][20];int i, j;cin >> m >> n;for (i = 0; i < m; i++){for (j = 0; j < n; j++){cin >> a[j][i];}}__________________;return 0;

?矩陣的轉(zhuǎn)置實際就是把n行m列的矩陣 轉(zhuǎn)換為m行n列的矩陣 所以只需要改變 i ，j 位置即可

微生物增殖

假設(shè)有兩種微生物 X 和 Y

X出生后每隔3分鐘分裂一次（數(shù)目加倍），Y出生后每隔2分鐘分裂一次（數(shù)目加倍）。

一個新出生的X，半分鐘之后吃掉1個Y，并且，從此開始，每隔1分鐘吃1個Y。

現(xiàn)在已知有新出生的 X=10, Y=89，求60分鐘后Y的數(shù)目。

如果X=10，Y=90呢？

本題的要求就是寫出這兩種初始條件下，60分鐘后Y的數(shù)目。

以下程序?qū)崿F(xiàn)了這一功能，請你補全空白處內(nèi)容：

提示：

分析可知，Y分別會在0.5,1.5,2.5······時被吃，所以，把60分鐘分成120份，則在除以2余數(shù)為1時，Y的數(shù)目減少X個

#include <iostream>
using namespace std;
int main()
{int x = 10, y = 90;for (int i = 1; i <= 120; i++){________________;}cout << y << endl;
}

?思路：一般來說這種題都是找規(guī)律的題（在紙上筆算是不可能算出結(jié)果的），本體也不例外，只要找到x與y關(guān)于時間的對應(yīng)關(guān)系即可。

計算代碼：

#include<stdio.h>
#include<stdlib.h>
int main()
{int n,m;double x,y;scanf("%d%lf%lf",&n,&x,&y);m=1;while(m<=n){if(m%2!=0)y=y-x;if(m%2==0)y=(y-x)*2;if(m%3==0)x*=2;//printf("m=%d x=%.0lf y=%.0lf\n",m,x,y);m++;}printf("x=%.0lf y=%.0lf\n",x,y);system("pause");return 0;
}

成績統(tǒng)計

問題描述

編寫一個程序，建立了一條單向鏈表，每個結(jié)點包含姓名、學(xué)號、英語成績、數(shù)學(xué)成績和C++成績，并通過鏈表操作平均最高的學(xué)生和平均分最低的學(xué)生并且輸出。

輸入格式

輸入n+1行，第一行輸入一個正整數(shù)n，表示學(xué)生數(shù)量；接下來的n行每行輸入5個數(shù)據(jù)，分別表示姓名、學(xué)號、英語成績、數(shù)學(xué)成績和C++成績。注意成績有可能會有小數(shù)。

輸出格式

輸出兩行，第一行輸出平均成績最高的學(xué)生姓名。第二行輸出平均成績最低的學(xué)生姓名。

樣例輸入

2
yx1 1 45 67 87
yx2 2 88 90 99

樣例輸出

yx2
yx1

請從以下四個選項中選擇空白處的內(nèi)容。

#include <bits/stdc++.h>
using namespace std;int main()
{struct student{string xm;int xh;double yy;double sx;double cpp;};student a[1000];int n;double sum = 0, min = 301, max = 0;string mins, maxs;cin >> n;for (int i = 0; i < n; i++){cin >> a[i].xm >> a[i].xh >> a[i].yy >> a[i].sx >> a[i].cpp;sum = a[i].yy + a[i].sx + a[i].cpp;__________________;}cout << maxs << endl<< mins;return 0;
}

提示： 類似冒泡法求最大值最小值

?如果有相同成績的最高分和最低分，取序號小的還是取序號大的最高最低分。
if（sum>max)，這是取序號小的最高分。
if（sum>=max)，這是取序號大的最高分。

題解
模擬：

#include <iostream>
#include <cmath>
using namespace std;int main()
{int n;cin >> n;int a = 0, b = 0;for (int i = 0; i < n; i ++){int x;cin >> x;if(x >= 60) a ++;if(x >= 85) b ++;}cout << round(100.0 * a / n) << '%' << endl;cout << round(100.0 * b / n) << '%' << endl;return 0;
}

?

星系炸彈

在X星系的廣袤空間中漂浮著許多X星人造“炸彈”，用來作為宇宙中的路標(biāo)。

每個炸彈都可以設(shè)定多少天之后爆炸。

比如：阿爾法炸彈2015年1月1日放置，定時為15天，則它在2015年1月16日爆炸。

有一個貝塔炸彈，2014年11月9日放置，定時為1000天，請你計算它爆炸的準(zhǔn)確日期。

以下程序?qū)崿F(xiàn)了這一功能，請你填補空白處內(nèi)容：

提示：?json 先判斷是否為閏年，這會影響2月份是28還是29，如果是閏年，2月份是29，如果不是，就是28

#include <stdio.h>int main()
{int monthDays[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int days = 1000;int year = 2014, month = 11, day = 9;int i;for (i = 0; i < days; i++){day++;if (day > monthDays[month - 1]){day = 1;month++;if (month > 12){month = 1;year++;____________________;}}}printf("%d-%d-%d\n", year, month, day);getchar();return 0;
}

if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
? ? monthDays[1] = 29;
else
? ? monthDays[1] = 28;

判斷閏年的依據(jù):

　閏年的計算方法：

　?、?、普通年能被4整除且不能被100整除的為閏年。（如2004年就是閏年，1900年不是閏年）

　　②、世紀(jì)年能被400整除的是閏年。（如2000年是閏年，1900年不是閏年）

　?、?、對于數(shù)值很大的年份，這年如果能整除3200，并且能整除172800則是閏年。如172800年是閏年，86400年不是閏年（因為雖然能整除3200，但不能整除172800）? ? ? ? ? ??

閏年怎么來

　　地球繞日運行周期為365天5小時48分46秒（合365.24219天），即一回歸年（ tropical year）。公歷的平年只有365日，比回歸年短約0.2422 日，每四年累積約一天，把這一天加于2月末（即2月29日），使當(dāng)年時間長度變?yōu)?66日，這一年就為閏年。 需要注意的是，現(xiàn)在的公歷是根據(jù)羅馬人的儒略歷改編而《中華民俗萬年歷》得。由于當(dāng)時沒有了解到每年要多算出0.0078天的問題，從公元前46年，到16世紀(jì)，一共累計多出了10天。為此，當(dāng)時的教皇格列高利十三世，將1582年10月5日人為規(guī)定為10月15日。并開始了新閏年規(guī)定。即規(guī)定公歷年份是整百數(shù)的，必須是400的倍數(shù)才是閏年，不是400的倍數(shù)的就是平年。比如，1700年、1800年和1900年為平年，2000年為閏年。此后，平均每年長度為365.2425天，約4年出現(xiàn)1天的偏差。按照每四年一個閏年計算，平均每年就要多算出0.0078天，經(jīng)過四百年就會多出大約3天來，因此，每四百年中要減少三個閏年。閏年的計算，歸結(jié)起來就是通常說的：四年一閏；百年不閏,四百年再閏。

　　由于地球的自轉(zhuǎn)速度逐漸降低，而公轉(zhuǎn)速度則相對更加穩(wěn)定，所以上述的系統(tǒng)經(jīng)過更長的周期也會發(fā)生微小的誤差。據(jù)計算，每8000年會有一天的誤差，所以英國的天文學(xué)家John Herschel提議公元4000為平年，以后類推12000年，20000年亦為平年。但此提議從未被正式采納。原因是到了4000年，地球自轉(zhuǎn)的精確速度并非現(xiàn)在可以預(yù)測，所以屆時參照真實數(shù)據(jù)方可做出判斷。因此，在長遠(yuǎn)的將來，針對閏年的微小調(diào)整應(yīng)該不是由預(yù)定的系統(tǒng)決定，而是隨時不定性的。

特別數(shù)的和

題目描述

小明對數(shù)位中含有 2、0、1、9 的數(shù)字很感興趣（不包括前導(dǎo) 0），在 1 到 40 中這樣的數(shù)包括 1、2、9、10 至 32、39 和 40，共 28 個，他們的和是 574。

請問，在 1 到 n 中，所有這樣的數(shù)的和是多少？

輸入格式

共一行，包含一個整數(shù) n。

輸出格式

共一行，包含一個整數(shù)，表示滿足條件的數(shù)的和。

數(shù)據(jù)范圍

1≤n≤10000

輸入樣例：

40

輸出樣例：

574

以下代碼實現(xiàn)了這一功能，請你填補空白處的內(nèi)容：

#include <iostream>using namespace std;int ans, n;bool check(int n)
{while (n){int tmpn = n % 10;if (tmpn == 2 || tmpn == 0 || tmpn == 1 || tmpn == 9)return true;__________________;}return false;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){if (check(i))ans += i;}cout << ans << endl;return 0;
}

提示：

只要利用模除找出含有2,0,1,9的數(shù)即可

?

#include <iostream>
using namespace std;bool check(int x)
{while(x){int t = x % 10;if(t == 2 || t == 0 || t == 1 || t == 9) return true;x /= 10;}return false;
}int main()
{int n;cin >> n;int ans = 0;for (int i = 1; i <= n; i ++)if(check(i))ans += i;cout << ans << endl;return 0;		
} 

?

蛇形填數(shù)

如下圖所示，小明用從1 開始的正整數(shù)“蛇形”填充無限大的矩陣。

容易看出矩陣第二行第二列中的數(shù)是5。請你計算矩陣中第20 行第20 列的數(shù)是多少？

以下程序?qū)崿F(xiàn)了這一功能，請你補全以下空白處內(nèi)容：

提示：

當(dāng)?shù)竭_(dá)邊界時，判斷它應(yīng)該向右走還是向下走，向右走完就直接向左下走，向下走完就直接向右上走

#include <bits/stdc++.h>using namespace std;
int main()
{int i = 0;int j = 0;int cnt = 2;int a[250][250];a[0][0] = 1;while (cnt < 1000){j++;while (i != -1 && j != -1){a[i][j] = cnt++;if (j == 0)break;i++;j--;}i++;while (i != -1 && j != -1){___________;}}for (int i = 0; i < 20; i++){for (int j = 0; j < 20; j++){cout << setw(5) << a[i][j] << ' ';}cout << '\n';}cout << a[19][19];return 0;
}

我們討論?n n?n行?n n?n列位置上的數(shù)，可以發(fā)現(xiàn)要求這個?( n , n ) (n,n)?(n,n)，可以通過求?p 1 p1?p1和?p 2 p2?p2，計算它們的平均數(shù)。?p 1 p1?p1是?n n?n階三角形的最大一個數(shù)，?p 2 p2?p2是?n ? 1 n-1?n?1階三角形的最大一個數(shù)再加上1。
a n s w e r = ( f ( m ) + f ( m ? 1 ) + 1 ) / 2 answer=(f(m)+f(m-1)+1)/2?answer=(f(m)+f(m?1)+1)/2
而?p 1 > p 2 p1>p2?p1>p2，且?p 1 p1?p1和?p 2 p2?p2都可通過計算三角形底邊?m m?m得到。從1開始累加到?m m?m即可得到?n n?n階三角形中最大的數(shù)字。于是先計算底邊?m m?m。
f ( x ) = x ? ( x + 1 ) / 2 f(x)=x*(x+1)/2?f(x)=x?(x+1)/2

不是每個三角形的底邊都穿過?n n?n行?n n?n列，而是隔一個三角形才出現(xiàn)一個，由此出現(xiàn)線性關(guān)系?2 n 2n?2n。三角形最長的邊為?m m?m，代入?n = 2 n=2?n=2時，?m = 5 m=5?m=5，由此有：
m = 2 n ? 1 m=2n-1?m=2n?1

代碼

#include<iostream>
using namespace std;//計算從1累加到x的值
int f(int x){return x*(x+1)/2;
}int main(){int n;while(1){cin>>n;//計算三角形的底邊int m=2*n-1;//大三角形+小三角形加一，兩數(shù)取平均數(shù)cout<<((f(m)+f(m-1)+1)/2)<<endl;}    system("pause");return 0;
}

?

?*日志統(tǒng)計*（雙指針）

題目描述

小明維護(hù)著一個程序員論壇?，F(xiàn)在他收集了一份”點贊”日志，日志共有 N 行。

其中每一行的格式是：

ts id

表示在 ts 時刻編號 id 的帖子收到一個”贊”。

現(xiàn)在小明想統(tǒng)計有哪些帖子曾經(jīng)是”熱帖”。

如果一個帖子曾在任意一個長度為 D 的時間段內(nèi)收到不少于 K 個贊，小明就認(rèn)為這個帖子曾是”熱帖”。

具體來說，如果存在某個時刻 T 滿足該帖在 [T,T+D) 這段時間內(nèi)(注意是左閉右開區(qū)間)收到不少于 K 個贊，該帖就曾是”熱帖”。

給定日志，請你幫助小明統(tǒng)計出所有曾是”熱帖”的帖子編號。

輸入格式

第一行包含三個整數(shù) N,D,K。

以下 N 行每行一條日志，包含兩個整數(shù) ts 和 id。

輸出格式

按從小到大的順序輸出熱帖 id。

每個 id 占一行。

數(shù)據(jù)范圍

1≤K≤N≤10E5,
0≤ts,id≤10E5,
1≤D≤10000

輸入樣例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

輸出樣例：

1
3

下面的程序?qū)崿F(xiàn)了這一功能，請你補全空白處的內(nèi)容：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
PII logs[N];
bool st[N];
int cnt[N];

int main()
{
? ? int n, d, k;
? ? cin >> n >> d >> k;
? ? for (int i = 0; i < n; i++)
? ? ? ? cin >> logs[i].x >> logs[i].y;

? ? sort(logs, logs + n);

? ? for (int i = 0, j = 0; i < n; i++)
? ? {
? ? ? ? cnt[logs[i].y]++;
? ? ? ? while (logs[i].x - logs[j].x >= d)
? ? ? ? ? ? __________________;
? ? ? ? if (cnt[logs[i].y] >= k)
? ? ? ? ? ? st[logs[i].y] = true;
? ? }

? ? for (int i = 0; i < N; i++)
? ? ? ? if (st[i])
? ? ? ? ? ? cout << i << endl;
? ? return 0;
}

提示：

尺取法

雙指針

先根據(jù)時刻排序

因為序列是有序的，所以可以保證區(qū)間內(nèi)的時刻是存在單調(diào)性的

所以我們只需要枚舉每一個基準(zhǔn)點，利用雙指針基于該起始點右移，如果在范圍內(nèi)且大于等于?K K?K個點贊，就存入答案

基準(zhǔn)點右移時需要將該基準(zhǔn)點的值減一，因為已經(jīng)移除區(qū)間，不必再統(tǒng)計點贊個數(shù)。

時間復(fù)雜度

O ( n l o g n ) O(nlogn)?O(nlogn)

C++ 代碼

#include <iostream>
#include <algorithm>
using namespace std;#define x first
#define y secondtypedef pair<int,int> PII;
const int N = 100010;
PII w[N];
int cnt[N];
bool res[N];	// 存放答案
int n, d, k;int main()
{cin >> n >> d >> k;int a, b;for(int i = 0;i < n;i ++) {scanf("%d%d",&a,&b);w[i] = {a,b};}sort(w,w + n);for(int i = 0,j = 0;i < n;i ++) {while(j < n && w[j].x - w[i].x < d){cnt[w[j].y] ++;if(cnt[w[j].y] >= k) res[w[j].y] = true;j ++;}cnt[w[i].y] --;}for(int i = 0;i < N;i ++) if(res[i]) printf("%d\n",i);return 0;
}

?猜年齡

【問題描述】

? ? 美國數(shù)學(xué)家維納(N.Wiener)智力早熟，11歲就上了大學(xué)。他曾在1935~1936年應(yīng)邀來中國清華大學(xué)講學(xué)。

? ? 一次，他參加某個重要會議，年輕的臉孔引人注目。于是有人詢問他的年齡，他回答說：

? ? “我年齡的立方是個4位數(shù)。我年齡的4次方是個6位數(shù)。這10個數(shù)字正好包含了從0到9這10個數(shù)字，每個都恰好出現(xiàn)1次?！?/p>

? ? 請你推算一下，他當(dāng)時到底有多年輕。

【問題分析】

?窮舉算法：對年齡進(jìn)行窮舉，從問題描述可以將年齡窮舉范圍定義在11~30之間（1~100也可以）。在窮舉過程中對年齡進(jìn)行檢查，如果符合以下條件則輸出結(jié)果

（1）年齡的立方是個4位數(shù)

（2）年齡的4次方是個6位數(shù)

（3）10個數(shù)字不重復(fù)

【程序代碼】1 public class 藍(lán)橋杯_第四屆_猜年齡2 {3     public static void main(String[] args) {4         // TODO code application logic here5         long t3=0,t4=0;6         for(int i=11;i<30;i++)7         {8             String str="";9             t3=i*i*i;
10             t4=i*i*i*i;
11             str=String.valueOf(t3) + String.valueOf(t4);
12             if(str.length()!=10)
13                continue;
14             else if(noRepeat(str))
15             {
16                 System.out.print(i);
17                 break;
18             }
19         }
20     }
21     
22     public static boolean noRepeat(String str)
23     {
24         for(int j=0;j<str.length()-1;j++)
25         {
26             char x=str.charAt(j);
27             for(int m=j+1;m<str.length();m++)
28             {
29                 char y=str.charAt(m);
30                 if(y==x)
31                 {
32                     return false;
33                 }
34             }
35         }
36         return true;
37     }
38 }

【運行結(jié)果】

?18

【相關(guān)知識】

數(shù)值與字符串之間的轉(zhuǎn)換?

字符串重復(fù)檢測

【類似問題】

?藍(lán)橋杯/第五屆/猜年齡

轉(zhuǎn)載于:https://www.cnblogs.com/yzzdzy/p/4364675.html

合并檢測

新冠疫情由新冠病毒引起，最近在 A 國蔓延，為了盡快控制疫情，A 國準(zhǔn) 備給大量民眾進(jìn)病毒核酸檢測。

然而，用于檢測的試劑盒緊缺。為了解決這一困難，科學(xué)家想了一個辦法：合并檢測。即將從多個人（k 個）采集的標(biāo)本放到同一個試劑盒中進(jìn)行檢測。如果結(jié)果為陰性，則說明這 k 個人都是陰性，用一個試劑盒完成了 k 個人的檢測。如果結(jié)果為陽性，則說明 至少有一個人為陽性，需要將這 k 個人的樣本全部重新獨立檢測（從理論上看， 如果檢測前 k?1 個人都是陰性可以推斷出第 k 個人是陽性，但是在實際操作中 不會利用此推斷，而是將 k 個人獨立檢測），加上最開始的合并檢測，一共使用 了 k + 1 個試劑盒完成了 k 個人的檢測。

A 國估計被測的民眾的感染率大概是 1%，呈均勻分布。請問 k 取多少能最節(jié)省試劑盒？

以下程序?qū)崿F(xiàn)了這一功能，請你補全以下空白處內(nèi)容：

#include <stdio.h>
int main()
{double m = 4537;double min = 9999999;double k, sum, ans;for (k = 1; k <= 100; k++){sum = (m - k) / k + 0.01 * m * k + 1;__________________;}printf("%d\n", (int)ans);return 0;
}

提示：

設(shè)檢測人數(shù)為100人，根據(jù)概率為1%，則只有1個為陽性。k個人一組，則需要的試劑數(shù)量為：對所有分組進(jìn)行合并檢測所需要的試劑數(shù)100/k+其中1個分組陽性所需要的試劑數(shù)k+未分組人數(shù)所需的試劑數(shù)量。 

?

因為感染率是百分之一
并且感染率服從均勻分布
所以結(jié)果應(yīng)是1到99之間的一個數(shù).

為了方便計算取整
我們每次假設(shè)i個人用一個試劑盒，有100 * i個人參加了檢測

那么統(tǒng)一檢測每次需要100個試劑盒
由于呈均勻分布所以每100人都會出現(xiàn)一個病例
一個病例需要i個試劑盒
總共有i個病例
所以總共需要need = 100 + i * i 個試劑盒

最后我們在data種添加每百人平均消耗試劑盒和當(dāng)前i值
對試劑盒消耗量排序
輸出最小每百人平均消耗試劑盒對應(yīng)的人數(shù) i 即可

Code

data = []
for i in range(1, 100):need = 100 + i * idata.append([need / i, i])
data.sort(key=lambda x: x[0])
print(data[0][1])

Answer

10

排它平方數(shù)

203879 * 203879 = 41566646641

這有什么神奇呢？仔細(xì)觀察，203879 是個6位數(shù)，并且它的每個數(shù)位上的數(shù)字都是不同的，并且它平方后的所有數(shù)位上都不出現(xiàn)組成它自身的數(shù)字。

具有這樣特點的6位數(shù)還有一個，請你找出它！

再歸納一下篩選要求：

1. 6位正整數(shù)

1. 每個數(shù)位上的數(shù)字不同

1. 其平方數(shù)的每個數(shù)位不含原數(shù)字的任何組成數(shù)位

以下程序?qū)崿F(xiàn)了這一功能，請你補全以下空白處內(nèi)容：

#include <iostream>
using namespace std;int main()
{int num[10], flag;for (long long i = 123456; i <= 987654; i++){long long a = i;long long b = i * i;memset(num, 0, sizeof(num));flag = 1;while (a){_________________;}if (flag){while (b){if (num[b % 10]){flag = 0;break;}b /= 10;}if (flag)cout << i << endl;}}return 0;
}

提示：

0的平方為0
1的平方為1
5的平方為5
6的平方為6
以上這4個數(shù)字都不能作為原數(shù)字的最后一位，可以在最后一位排除
且第一位不能為0

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;int main()
{int n;cin >> n;unordered_map<int, PII> ans;for(int c = 0; c * c <= n; c ++ )//枚舉C和Dfor(int d = c; d * d + c * c <= n; d ++ ){int t = c * c + d * d; //存下來這兩個數(shù)的平方和if(ans.count(t) == 0)   ans[t] = {c, d};}for(int a = 0; a * a <= n; a ++ )for(int b = a; b * b + a * a <= n; b ++ ){int t = n - a * a - b * b;//看A和B的平方和還和目標(biāo)差多少，看看之前存的有沒有這個數(shù)if(ans.count(t) != 0){printf("%d %d %d %d\n", a, b, ans[t].x, ans[t].y);return 0;}}return 0;
}

?

問題解決的中心思想是： 通過數(shù)組num[10], 初始化后全0狀態(tài)，a的每位取數(shù)后置非0（考慮重復(fù)），然后再后面b取位時看a[X]的非零狀態(tài)，如果取到是非零那就是重復(fù)了，如果是零，那就是之前沒有置，表示不重復(fù)，flag直到B取盡后才能保證true.才證明這個數(shù)字符合要求。

所以上述代碼，窮盡法做num[a%10]++運算就行了，沒有必要考慮位數(shù)值是0情況，當(dāng)然，考慮0，1，5，6就是條件規(guī)避，場景更細(xì)致些。

題目合理利用數(shù)值置位方式表示是否取到過，這個做法不錯

?*四平方和定理*

四平方和定理，又稱為拉格朗日定理：
每個正整數(shù)都可以表示為至多 4 個正整數(shù)的平方和。
如果把 0 包括進(jìn)去，就正好可以表示為 4 個數(shù)的平方和。

比如：
5=02+02+12+22
7=12+12+12+22

對于一個給定的正整數(shù)，可能存在多種平方和的表示法。
要求你對 4 個數(shù)排序：
0≤a≤b≤c≤d
并對所有的可能表示法按 a,b,c,d 為聯(lián)合主鍵升序排列，最后輸出第一個表示法。

輸入格式
輸入一個正整數(shù) N。

輸出格式
輸出4個非負(fù)整數(shù)，按從小到大排序，中間用空格分開。

數(shù)據(jù)范圍
0<N<5?106

輸入樣例：

5

輸出樣例：

0 0 1 2

題解：
首先，三重循環(huán)枚舉a,b,c最后確定出來d，O(N3)的復(fù)雜度，大概率通過不了

這時候就用空間來換取時間
1：首先我們先枚舉C和D，將所有組合的平方和進(jìn)行一個記錄
2：然后枚舉A和B，算出來跟輸入的數(shù)字差了幾，然后看之前存放的有沒有這一項
3：找到這一個然后進(jìn)行輸出
這里又要求到了按字典序排序的問題，首先我們的A和B的枚舉方法肯定是沒有問題的，一定是A<B的，那么看C和D；C和D用的哈希表存放，也是在枚舉的時候確定了一個字典序的，如果這個數(shù)字存在了，在找到相同數(shù)字的時候是不會進(jìn)行更新操作的，所以字典序也一定是成立的。代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;int main()
{int n;cin >> n;unordered_map<int, PII> ans;for(int c = 0; c * c <= n; c ++ )//枚舉C和Dfor(int d = c; d * d + c * c <= n; d ++ ){int t = c * c + d * d; //存下來這兩個數(shù)的平方和if(ans.count(t) == 0)   ans[t] = {c, d};}for(int a = 0; a * a <= n; a ++ )for(int b = a; b * b + a * a <= n; b ++ ){int t = n - a * a - b * b;//看A和B的平方和還和目標(biāo)差多少，看看之前存的有沒有這個數(shù)if(ans.count(t) != 0){printf("%d %d %d %d\n", a, b, ans[t].x, ans[t].y);return 0;}}return 0;
}

*大數(shù)乘法*

對于32位字長的機(jī)器，大約超過20億，用int類型就無法表示了，我們可以選擇int64類型，但無論怎樣擴(kuò)展，固定的整數(shù)類型總是有表達(dá)的極限！如果對超級大整數(shù)進(jìn)行精確運算呢？一個簡單的辦法是：僅僅使用現(xiàn)有類型，但是把大整數(shù)的運算化解為若干小整數(shù)的運算，即所謂：“分塊法”。

上圖表示了分塊乘法的原理?？梢园汛髷?shù)分成多段（此處為2段）小數(shù)，然后用小數(shù)的多次運算組合表示一個大數(shù)?？梢愿鶕?jù)int的承載能力規(guī)定小塊的大小，比如要把int分成2段，則小塊可取10000為上限值。注意，小塊在進(jìn)行縱向累加后，需要進(jìn)行進(jìn)位校正。

請從以下四個選項中選擇正確答案，填補在空白處，使得代碼能運行后能產(chǎn)生正確的結(jié)果。

提示：

十進(jìn)制數(shù)的進(jìn)位問題

#include <bits/stdc++.h>
using namespace std;void bigmul(int x, int y, int r[])
{int base = 10000;int x2 = x / base;int x1 = x % base;int y2 = y / base;int y1 = y % base;int n1 = x1 * y1;int n2 = x1 * y2;int n3 = x2 * y1;int n4 = x2 * y2;r[3] = n1 % base;r[2] = n1 / base + n2 % base + n3 % base;r[1] = __________________;r[0] = n4 / base;r[1] += r[2] / base;r[2] = r[2] % base;r[0] += r[1] / base;r[1] = r[1] % base;
}int main(int argc, char *argv[])
{int x[] = {0, 0, 0, 0};bigmul(87654321, 12345678, x);printf("%d%d%d%d\n", x[0], x[1], x[2], x[3]);return 0;
}

?

?