考慮到各位同學可能還沒學過函式，所以先說明，以下題解不用函式也能解決（其實是我懶），
1.放輕松
這是一道簽到題，非常簡單，因為每個選手中間隔一個位置，所以，有兩種情況：
- 座位數為偶數，可坐人數即為座位數的一半；
- 座位數為奇數，可坐人數為（座位數 - 1）/ 2 + 1；
難度：1
#include<stdio.h>
int main()
{
int n, count;//座位數n
scanf("%d", &n);
if(n % 2 == 0) count = n / 2;//座位數為偶數，可坐人數即為座位數的一半
else count = n / 2 + 1;//座位數為奇數，可坐人數為（座位數 - 1）/ 2 + 1(此段代碼也可表示相同意思)
printf("%d", count);
return 0;
}
2.小軒愛吃素
此題考察大家判斷素數的掌握能力，我們只需要判斷a*b是否為素數即可（方法2，其實這也考大家腦靜急轉彎，兩個不為一的正整數相乘必定不是素數，此處只給優化后的版本）
難度：2
#include<stdio.h>
//素數判斷函式優化版
bool check(int k)
{
if(k < 2) return false;
for(int i = 2; i * i <= k; i++)
if(k % i == 0) return false;
return true;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
if(check(a * b)) printf("Yes");//如果是素數輸出Yes
else printf("No");//否則輸出No
return 0;
}
3.樂樂買瓜
此題考察大家思維，我們已知有n個人在排隊，有不少于a個人在樂樂前面，有不多于b個人在樂樂后面，所以我們只需要判斷每一個位置是否滿足條件即可，
難度：2
#include<stdio.h>
int main()
{
int n, a, b, count = 0;
scanf("%d%d%d", &n, &a, &b);
for(int i = 1; i <= n; i++)
{
if(a <= i - 1 && n - i <= b) count++;//判斷每個位置是否滿足條件,并記錄滿足條件的位置的數量
}
//更簡潔的方法有沒有呢?當然有,自己想想為什么這種思路可以
//if(n - a > b + 1) count = b + 1;
//else count = n - a;
printf("%d", count);
return 0;
}
4.What's up
簡單排序問題，涉及到陣列的使用，第一次從待排序的資料元素中選出最小的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小元素，然后放到已排序的序列的末尾，以此類推，直到全部待排序的資料元素的個數為零，
難度：4
#include<stdio.h>
int a[1010];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n - 1; i++){
int k = i;
//尋找到i~n-1中最小值對應的下標
for(int j = i; j < n; j++){
if(a[k] > a[j]) k = j;
}
//將從i到n的最小值與i位置交換
int temp = a[k];
a[k] = a[i];
a[i] = temp;
}
for(int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
5.小軒的魔爪
這題看似和第二題一樣，但是資料范圍已經增強，a和b的范圍達到1^11，如果依舊使用第二題的方法的話，即便是優化后的也會運行超時，所以，我們不難發現一個很直觀的性質：兩個不為1正整數相乘其結果必不是素數，
推論：
如果兩個正整數相乘依是素數，它一定滿足其中一個是1，另一個是素數，
難度：3
#include<stdio.h>
//優化版素數判斷函式
bool check(long long k)
{
if(k < 2) return false;
for(long long i = 2; i * i <= k; i++)
if(k % i == 0) return false;
return true;
}
int main()
{
int n;
scanf("%d", &n);
int count = 0, m = n;
//回圈判斷每一組數
while(n--){
long long a, b;
scanf("%lld%lld", &a, &b);
//如果兩個正整數相乘依是素數，它一定滿足其中一個是1，另一個是素數
if((a == 1 && check(b)) || (b == 1 && check(a)) ) count++;
}
printf("%d", m - count);
return 0;
}
6.你是個好人
兩個人在兩邊同時吃糖，我們可以使用 l 和 r 來模擬女生吃的糖的位置和男生吃的糖的位置，用 tl 和 tr 模擬女生和男生吃完上一顆糖經歷的總時間：
- 女生吃下當前這顆糖的時間 <= 男生吃下當前這顆糖的時間時，女生吃完這顆糖（為什么是小于等于而不是小于呢，因為當兩人同時開始吃一顆糖時，男生會把糖讓給女生）;
- 女生吃下當前這顆糖的時間 > 男生吃下當前這顆糖的時間時，男生吃完這顆糖;
難度：4
#include<stdio.h>
int a[100010];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 1, r = n;
int tl = 0, tr = 0;
while(l < r)
{
//女生吃下當前這顆糖的時間 <= 男生吃下當前這顆糖的時間時，女生吃完這顆糖
if(tl + a[l] <= tr + a[r]) tl += a[l++];
//女生吃下當前這顆糖的時間 > 男生吃下這顆糖的時間時，男生吃完這顆糖
else tr += a[r--];
}
//由于最后l和r可能在同一位置,所以需要特判一下誰先吃這個糖的
if(tl > tr) l--;
printf("%d %d", l, n - l);
return 0;
}7.三角形
四根棒子，共有四種組合，用一個值（max）一直去記錄每個組合能構成的三角形的最大周長即可
難度：3
#include<stdio.h>
int max = 0;
//判斷是否能構成三角形,如果能,則更新最大周長
void check(int x, int y, int z){
if(x + y > z && x + z > y && y + z > x && x + y + z > max) max = x + y + z;
}
int main()
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
//分別計算四個不同的組合能否構成三角形
check(a, b, c);
check(a, b, d);
check(a, c, d);
check(b, c, d);
if(max != 0) printf("Yes\n%d", max);
else printf("No");
return 0;
} 8.過山車
這題題解雖然連回圈都沒涉及到，但是思維如果不靈敏點可能想不出來，首先呢我們分為三種情況：
- n = k 或 k = 0 時，此時已經坐滿或者沒人坐，都滿足不了條件，所以最大值和最小值都為0
- n < k 時，最小值都是1，最大值：
- 3k <= n時，我們進行模擬，到底一個人的旁邊最多能坐多少個人首先從k==1開始，（010），最多2個k==2（010010），最多4個；k=t，最多2t個然后，我們就需要考慮了，在最多能坐2k的情況下，必須有3k<=n(每一組為010)，同時我們也得到了，一個隔著一個坐的方法能得到最大值
- 3k > n時，依舊使用一個隔一個的方法，當不能往下進行時，可以將剩下的人隨機分配到空的座位上（因為無論如何分配都是等效的）這種方法得到的最大值為n - k
難度：3
#include<stdio.h>
int main()
{
int n, k;
scanf("%d%d", &n, &k);
int x, y;
if(n == k || k == 0) x = 0, y = 0;
else if(3 * k <= n) x = 1, y = 2 * k;
else x = 1, y = n - k;
printf("%d %d", x, y);
return 0;
}
9.爬山
此題是防ak題，可以直接跳過，有興趣的可以鉆研其奧妙的演算法，
此題涉及到以下三種問題:
- 01背包問題
- 完全背包問題
- 多重背包問題
由于完全背包都是一種特殊的多重背包問題，所以可以轉換成多重背包問題，再將多重背包問題通過二進制優化轉換為01背包問題，
難度：5
#include<stdio.h>
const int N=20000;
int f[N],v[N],w[N];
int main()
{
int n, m, j = 1;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
int a, b, q, s;
scanf("%d%d%d", &a, &b, &q);
//等效物品數量-轉化為多重背包
if(q == -1) s = 1;
else if(q == 0) s = m / a;
else if(q > 0) s = q;
//多重背包二進制優化-轉化為01背包
int k = 1;
while(s - k >= 0)
{
v[j] = k * a;
w[j] = k * b;
s = s - k;
j++;
k = k<<1;
}
if(s > 0){
v[j] = s * a;
w[j] = s * b;
j++;
}
}
n = j - 1;
//01背包-動態規劃,以區域最優求全域最優
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= v[i]; j--)
{
if(f[j] < f[j- v[i]] + w[i]) f[j] = f[j- v[i]] + w[i];
}
}
printf("%d", f[m]);
return 0;
}
10.可莉要炸魚
另一道簽到題，沒想到吧，在最后一題，題目也很簡單，只要判斷第八號炸彈的認可度是否不低于百分之八十即可，
難度：2
#include<stdio.h>
int main()
{
int n, m, x;
bool f = false;//定義一個bool型變數表示其受認可度是否不低于80%
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &x);
if(i == 8 && (1.0 * x) / m >= 0.8) f = true;//如果第八號炸彈認可度不低于80%,f為true,表示認可度是否不低于80%
}
if(f) printf("Boom!!!");
else printf("Next");
return 0;
} 轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/335225.html
標籤：其他