函數(shù)

如同我們數(shù)學(xué)中學(xué)的 f(x) = ax + b ，函數(shù)就是把一個(gè)東西丟進(jìn)去，然后進(jìn)行類似的操作變化，最終得到的可以是一個(gè)數(shù)，也可能什么都得不到而只是進(jìn)行一項(xiàng)操作。

如sqrt() ， max() 和 swap() 這樣的其實(shí)都是函數(shù)，我們寫的 int main() 其實(shí)也是函數(shù)，名為 主函數(shù) 。這里主要講的是手寫函數(shù)。

題目描述

給出平面坐標(biāo)上不在一條直線上三個(gè)點(diǎn)坐標(biāo) $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，坐標(biāo)值是實(shí)數(shù)，且絕對(duì)值不超過 100.00，求圍成的三角形周長(zhǎng)。保留兩位小數(shù)。

對(duì)于平面上的兩個(gè)點(diǎn) $(x_1,y_1),(x_2,y_2)$，則這兩個(gè)點(diǎn)之間的距離 $dis=\sqrt{(x_2?x_1{)}^2+(y_2?y_1{)}^2}$

輸入格式

輸入三行，第 $i$ 行表示坐標(biāo) $(x_i,y_i)$，以一個(gè)空格隔開。

輸出格式

輸出一個(gè)兩位小數(shù)，表示由這三個(gè)坐標(biāo)圍成的三角形的周長(zhǎng)。

樣例輸入

0 0
0 3
4 0

樣例輸出

12.00

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

數(shù)據(jù)保證，坐標(biāo)均為實(shí)數(shù)且絕對(duì)值不超過 $100$，小數(shù)點(diǎn)后最多僅有 $3$ 位。

直接寫出來的話就是：

#include<bits/stdc++.h>
using namespace std;
int main()
{double x1 , y1 , x2 , y2 , x3 , y3 , ans = 0 ;scanf("%lf%lf%lf%lf%lf%lf" ,&x1 ,&y1 ,&x2 ,&y2 ,&x3 ,&y3) ;ans += sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) ; ans += sqrt((x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2)) ;ans += sqrt((x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1)) ;printf("%.2lf" ,ans) ;return 0 ;
}

看起來非常丑陋，但是我們可以通過手寫函數(shù)的方法來解決代碼操作重復(fù)的問題。

#include<bits/stdc++.h>
using namespace std;
double dis(double a1 ,double b1 ,double a2 ,double b2)
{return sqrt((a2 - a1) * (a2 - a1) + (b2 - b1) * (b2 - b1)) ;
}
int main()
{double x1 , y1 , x2 , y2 , x3 , y3 , ans = 0 ;scanf("%lf%lf%lf%lf%lf%lf" ,&x1 ,&y1 ,&x2 ,&y2 ,&x3 ,&y3) ;ans += dis(x2 ,y2 ,x1 ,y1) ;ans += dis(x3 ,y3 ,x2 ,y2) ;ans += dis(x3 ,y3 ,x1 ,y1) ;printf("%.2lf" ,ans) ;return 0 ;
}

這樣是不是就簡(jiǎn)短多了，類比我們的 f(x) = ax + b ，那么此時(shí)的 f(1) 是不是就等價(jià)于 a + b 了，同理當(dāng)我們定義 dis 為

double dis(double a1 ,double b1 ,double a2 ,double b2)
{return sqrt((a2 - a1) * (a2 - a1) + (b2 - b1) * (b2 - b1)) ;
}

時(shí)，dis(x2 ,y2 ,x1 ,y1) ; 就等價(jià)于 sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) ，相當(dāng)于把 x2 ,y2 ,x1 ,y1 代入到了這個(gè)函數(shù)里，得到其中return 的結(jié)果，此時(shí)我們用 double 聲明這個(gè)函數(shù)，因此返還的結(jié)果為 浮點(diǎn)型 ，若使用 int 聲明函數(shù)，則返回值為 整形 。

題目描述

輸入 $n$ 個(gè)不大于 $10^5$ 的正整數(shù)。要求全部?jī)?chǔ)存在數(shù)組中，去除掉不是質(zhì)數(shù)的數(shù)字，依次輸出剩余的質(zhì)數(shù)。

輸入格式

第一行輸入一個(gè)正整數(shù) $n$，表示整數(shù)個(gè)數(shù)。

第二行輸入 $n$ 個(gè)正整數(shù) $a_i$，以空格隔開。

輸出格式

輸出一行，依次輸出 $a_i$ 中剩余的質(zhì)數(shù)，以空格隔開。

樣例輸入

5
3 4 5 6 7

樣例輸出

3 5 7

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

數(shù)據(jù)保證，$1\le n\le 100$，$1\le a_i\le 10^5$。

#include<bits/stdc++.h>
using namespace std;
bool panduan(int x)
{if(x == 1) return 0 ;//對(duì)1進(jìn)行特判 for(int i = 2 ; i <= sqrt(x) ; i ++)if(x % i == 0) return 0 ;//判斷從2到根號(hào)x有無x的因子 return 1 ;
}
int main()
{int n , a ;scanf("%d" ,&n) ;for(int i = 1 ; i <= n ; i ++){scanf("%d" ,&a) ;if(panduan(a)) printf("%d " ,a) ;}return 0 ;
}

這里使用了 bool 型的函數(shù)， bool 在這里可以改為用 int ， bool 聲明的變量只能存 $0$ 和 $1$ ，可以理解為存儲(chǔ)范圍為 $0$ 到 $1$ 的一個(gè)整型，在 bool 聲明的函數(shù)中 return 0 并不像主函數(shù)里那樣意味著程序的結(jié)束運(yùn)行，而是表示返還 $0$ ，這里的 $0$ 和 $1$ 改成 $false$ 和 $true$ 也是可以的，就像：

bool panduan(int x)
{if(x == 1) return false ;//對(duì)1進(jìn)行特判 for(int i = 2 ; i <= sqrt(x) ; i ++)if(x % i == 0) return false ;//判斷從2到根號(hào)x有無x的因子 return true ;
}

這里我沒有搞一個(gè)數(shù)組先把 $a[i]$ 存下來，而是每次讀入一個(gè) $a$ 就判斷是否為質(zhì)數(shù)，要理解評(píng)測(cè)機(jī)的運(yùn)行規(guī)則，可以把輸入和輸出當(dāng)成兩個(gè)文件，對(duì)于一組測(cè)試數(shù)據(jù)，所有的輸入都放在一起，所有的輸出也都放在一起，輸入輸出是分開的，所以一遍輸入一邊輸出是非?？尚械?#xff0c;最后將你的輸出結(jié)果和標(biāo)準(zhǔn)答案進(jìn)行對(duì)比，如果一樣則結(jié)果正確。

另外一點(diǎn)很重要的是這里判斷是否為素?cái)?shù)時(shí)，利用 試除法 ，即對(duì)一個(gè)數(shù) $i$ 進(jìn)行取余運(yùn)算，若沒有余數(shù)，則說明 $i$ 是這個(gè)數(shù)的因數(shù)，既然有因數(shù)了，就說明不是素?cái)?shù)。

理解為什么 試除法 是從 $2$ 判斷到 $\sqrt{n}$ ，舉例對(duì)于 $16$ ，$\sqrt{16}=4$ ，$16$ 的因子有 $1,2,4,8,16$ ，既然是因子，就一定是至少需要兩個(gè)數(shù)相乘（本身除外），比如你知道了 $1$ 是 $16$ 的因子，那么就可以想到另一個(gè)因子是 $16/1=16$ ；知道 $2$ 是 $16$ 的一個(gè)因子，就可以知道 $16/2=8$ 是 $16$ 的一個(gè)因子，不難看出，對(duì)于一個(gè)數(shù) $n$ ，它的因子總在 $\sqrt{n}$ 成一個(gè)一個(gè)對(duì)應(yīng)，還以 $16$ 為例子就是 $1$ 對(duì)應(yīng) $16$ ，$2$ 對(duì)應(yīng) $8$ ，$4$ 對(duì)應(yīng) $4$ 。

這樣我們?cè)谂袛嗍欠裼幸蜃拥臅r(shí)候就可以將時(shí)間復(fù)雜度從 $O(n)$ 降低到 $O(\sqrt{n})$ ，大大縮短運(yùn)行時(shí)間，減少 $TLE$ 的出現(xiàn)。

bool 函數(shù)的其他用法

#include<bits/stdc++.h>
using namespace std;
int main()
{int a[10] ;for(int i = 1 ; i <= 5 ; i ++)scanf("%d" ,&a[i]) ;sort(a + 1 , a + 1 + 5) ;for(int i = 1 ; i <= 5 ; i ++)printf("%d " ,a[i]) ;return 0 ;
}

在 c++ 中有一個(gè)內(nèi)置函數(shù) sort ，其作用是將數(shù)組按照從小到大排序，如上格式，將數(shù)組從 $a[1]$ 到 $a[5]$ 進(jìn)行排序，可以寫成 sort(a + 1 , a + 1 + 5) ; ，理解的話就理解為對(duì)于數(shù)組 $a$ ，使用時(shí)候下標(biāo)是從 $0$ 開始的，因此想排序從 $1$ 到 $N$ 要寫成 sort(a + 1 , a + 1 + N) ; 這樣的形式。

如果希望從小到大排序，可以聲明一個(gè) $bool$ 型變量：

bool mycmp(int x , int y)
{return x > y ;
}

使用時(shí)寫成：

#include<bits/stdc++.h>
using namespace std;
bool mycmp(int x , int y)
{return x > y ;
}
int main()
{int a[10] ;for(int i = 1 ; i <= 5 ; i ++)scanf("%d" ,&a[i]) ;sort(a + 1 , a + 1 + 5 , mycmp) ;for(int i = 1 ; i <= 5 ; i ++)printf("%d " ,a[i]) ;return 0 ;
}

void 聲明的函數(shù)

$void$ 聲明的函數(shù)沒有返回值，但還是要寫 return ; 。

題目描述

因?yàn)?$151$ 既是一個(gè)質(zhì)數(shù)又是一個(gè)回文數(shù)（從左到右和從右到左是看一樣的），所以 $151$ 是回文質(zhì)數(shù)。

寫一個(gè)程序來找出范圍 $[a,b](5\le a<b\le 100,000,000)$（一億）間的所有回文質(zhì)數(shù)。

輸入格式

第一行輸入兩個(gè)正整數(shù) $a$ 和 $b$。

輸出格式

輸出一個(gè)回文質(zhì)數(shù)的列表，一行一個(gè)。

樣例輸入

5 500

樣例輸出

5
7
11
101
131
151
181
191
313
353
373
383

提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文數(shù)再判斷它們是不是質(zhì)數(shù)（素?cái)?shù)）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要產(chǎn)生正確的回文數(shù)，你可能需要幾個(gè)像下面這樣的循環(huán)。

題目翻譯來自NOCOW。

USACO Training Section 1.5

產(chǎn)生長(zhǎng)度為 $5$ 的回文數(shù)：

for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇數(shù)才會(huì)是素?cái)?shù)for (d2 = 0; d2 <= 9; d2++) {for (d3 = 0; d3 <= 9; d3++) {palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(處理回文數(shù)...)}}}

這里分享一個(gè)洛谷 $88$ 分的做法：

#include<bits/stdc++.h>
using namespace std;
int v[10000010] , pri[10000010] , a[20] , tot , n , m ;
void primes(int x)
{memset(v , 0 , sizeof(v)) ;//v[i]所存的數(shù)表示i的最小質(zhì)因子 tot = 0 ; //記錄質(zhì)數(shù)的數(shù)量，對(duì)于數(shù)組來說相當(dāng)于一個(gè)箭頭 for(int i = 2 ; i <= x ; i ++){if(v[i] == 0)//v[i]為0說明在這之前i沒有因子，即i為質(zhì)數(shù) {v[i] = i ;pri[++ tot] = i ;}for(int j = 1 ; j <= tot ; j ++){if(pri[j] > v[i] || pri[j] > x / i) break ;//如果i有比pri[j]更小的質(zhì)因子或超出n的范圍，則停止循環(huán) v[i * pri[j]] = pri[j] ;//pri[j]是i * pri[j] 的最小質(zhì)因子 }}return ;
}
bool huiwen(int x)
{int len = 0 ;while(x){a[++ len] = x % 10 ;x /= 10 ;}for(int i = 1 , j = len ; i < j ; i ++ , j --)if(a[i] != a[j]) return false ;return true ;
}
int main()
{scanf("%d%d" ,&n ,&m) ;primes(m) ;for(int i = 1 ; i <= tot ; i ++){if(pri[i] > m) break ;if(pri[i] >= n && huiwen(pri[i])) printf("%d\n" ,pri[i]) ;}return 0 ;
}

由于題中數(shù)據(jù)范圍到 $10^8$ ，數(shù)組 $v$ 也至少聲明這么大，但是會(huì)導(dǎo)致爆空間 $MLE$ ，但不開這么大則會(huì)造成運(yùn)行時(shí)錯(cuò)誤 $RE$ 。

結(jié)構(gòu)體

題目描述

有 $n$ 名同學(xué)，每名同學(xué)有語文、數(shù)學(xué)、英語三科成績(jī)，你需要按照如下規(guī)則對(duì)所有同學(xué)的成績(jī)從高到低排序：

1. 比較總分，高者靠前；
2. 如果總分相同，則比較語文和數(shù)學(xué)兩科的總分，高者靠前；
3. 如果仍相同，則比較語文和數(shù)學(xué)兩科的最高分，高者靠前；
4. 如果仍相同，則二人并列。

你需要輸出每位同學(xué)的排名，如遇 $x$ 人并列，則他們排名相同，并留空后面的 $x?1$ 個(gè)名次。例如，有 $3$ 名同學(xué)并列第 $1$，則后一名同學(xué)自動(dòng)成為第 $4$ 名。

輸入格式

第一行一個(gè)整數(shù) $N$，表示同學(xué)的人數(shù)。
接下來 $N$ 行，每行三個(gè)非負(fù)整數(shù) $c_i,m_i,e_i$ 分別表示該名同學(xué)的語文、數(shù)學(xué)、英語成績(jī)。

輸出格式

輸出 $N$ 行，按輸入同學(xué)的順序，輸出他們的排名。
注意：請(qǐng)不要按排名輸出同學(xué)的序號(hào)，而是按同學(xué)的順序輸出他們各自的排名。

樣例輸入

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0

樣例輸出

1
3
4
4
2
6

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

• 對(duì) $30\%$ 的數(shù)據(jù)，$N\le 100$，且所有同學(xué)總分各不相同。
• 對(duì)全部的測(cè)試數(shù)據(jù)，保證 $2\le N\le 10^4$，$0\le c_i,m_i,e_i\le 150$。

#include<bits/stdc++.h>
using namespace std;
int n ;
struct stu
{int c , z , e , m , zg , cm , id , rank ;
}t[100010];
bool mycmp1(stu x , stu y)
{if(x.z != y.z) return x.z > y.z ;else if(x.cm != y.cm) return x.cm > y.cm ;else if(x.zg != y.zg) return x.zg > y.zg ;else return x.id < y.id ;
}
bool mycmp2(stu x , stu y)
{return x.id < y.id ;
}
int main()
{scanf("%d" ,&n) ;for(int i = 1 ; i <= n ; i ++){scanf("%d%d%d" ,&t[i].c ,&t[i].m ,&t[i].e) ;t[i].z = t[i].c + t[i].m + t[i].e ;t[i].cm = t[i].c + t[i].m ;t[i].zg = max(t[i].c , t[i].m) ;t[i].id = i ;}sort(t + 1 , t + 1 + n , mycmp1) ;t[1].rank = 1 ;for(int i = 2 ; i <= n ; i ++){if(t[i].z == t[i - 1].z && t[i].cm == t[i - 1].cm && t[i].zg == t[i - 1].zg)t[i].rank = t[i - 1].rank ;else t[i].rank = i ;}sort(t + 1 , t + 1 + n , mycmp2) ;for(int i = 1 ; i <= n ; i ++)printf("%d\n" ,t[i].rank) ;return 0 ;
}

類比我們用 int 和 double 等聲明不同類型的變量，結(jié)構(gòu)體 也可理解為我們新定義了一種新的數(shù)據(jù)類型，可以用 stu 聲明這個(gè)變量，其中包含了 c , z ,m ... 這樣的元素，因此 結(jié)構(gòu)體 的聲明也可以寫成：

struct stu
{int c , z , e , m , zg , cm , id , rank ;
};stu t[100010] ;