洛谷CSP-J/S2020初賽模擬部分題解-有解無憂

說明

試題來源于洛谷CSP-J/S2020初賽模擬試題，

選擇題

T1. 十進制數114的相反數的8位二進制補碼是：（10001110）

【決議】整數的二進制表示的最高位為符號位，用0表示“正”，用1表示“負”

正整數的補碼是其二進制表示，與原碼相同，
負整數的補碼是將其原碼除符號位外的所有位取反（0變1，1變0，符號位為1不變）后加1，
所以，114的二進制表示為 ( 01110010 ) 2 (01110010)_2 (01110010)2?，-114的補碼表示為 ( 10001110 ) 2 (10001110)_2 (10001110)2?，

T3. 小A用字母 A A A表示 1 1 1， B B B表示 2 2 2，以此類推，用 26 26 26表示 Z Z Z，對于27以上的數字，可以用兩位或者更長的字符來對應，例加 A A AA AA對應 27 27 27， A B AB AB對應 28 28 28， A Z AZ AZ對應 52 52 52， A A A AAA AAA對應 703 703 703，…，那么 B Y T BYT BYT字串對應的數字是（2022）

【決議】可將字串看做26進制數， A ? Z A-Z A?Z分別對應 1 ? 26 1-26 1?26， A A AA AA按照權值展開就是 1 × 2 6 1 + 1 × 2 6 0 = 27 1\times26^1+1\times26^0=27 1×261+1×260=27， A Z = 1 × 2 6 1 + 26 × 2 6 0 = 26 + 27 = 52 AZ=1\times26^1+26\times26^0=26+27=52 AZ=1×261+26×260=26+27=52， A A A = 1 × 2 6 2 + 1 × 2 6 1 + 1 × 2 6 0 = 703 AAA=1\times26^2+1\times26^1+1\times26^0=703 AAA=1×262+1×261+1×260=703，那么 B Y T = 2 × 2 6 2 + 25 × 2 6 1 + 20 × 2 6 0 = 2022 BYT=2\times26^2+25\times26^1+20\times26^0=2022 BYT=2×262+25×261+20×260=2022

T5. 在一個長度為 n n n的陣列中找到第 k k k大的數字，平均的演算法時間復雜度最低的是： O ( n ) O(n) O(n)

【決議】使用快速排序的思想實作，因為每次磁區完只需要繼續操作一邊，所以該演算法的平均時間復雜度是 O ( n ) O(n) O(n)，
用 T ( n ) T(n) T(n)表示元素的比較次數，那么平均情況下：

第一次劃分： T ( n ) = T ( n 2 ) + n T(n) = T(\frac{n}{2}) + n T(n)=T(2n?)+n
第二次劃分： T ( n ) = T ( n 4 ) + n 2 + n T(n) = T(\frac{n}{4}) + \frac{n}{2} + n T(n)=T(4n?)+2n?+n
第三次劃分： T ( n ) = T ( n 8 ) + n 4 + n 2 + n T(n) = T(\frac{n}{8}) + \frac{n}{4}+\frac{n}{2} + n T(n)=T(8n?)+4n?+2n?+n
. . . ... ...
最終： T ( n ) = T ( n n ) + 2 + 4 + . . . + n 4 + n 2 + n = 1 + 2 + 4 + . . . + n T(n) = T(\frac{n}{n}) + 2 + 4 +...+ \frac{n}{4}+\frac{n}{2} + n = 1 + 2 + 4 + ... + n T(n)=T(nn?)+2+4+...+4n?+2n?+n=1+2+4+...+n

上式是一個等比數列求和，公比為2，最終結果為： T ( n ) = 1 ? 2 × n 1 ? 2 = 2 n T(n) = \frac{1-2 \times n}{1-2}=2n T(n)=1?21?2×n?=2n，

T6. 對于樹這種資料結構，正確的有：②③
①一個有n個頂點、n-1條邊的圖是樹，
②一個樹中的兩個頂點之間有且只有一條簡單路徑
③樹中一定存在度數不大于1的頂點
④樹可能存在環

【決議】
①錯誤，n-1條邊的圖可能不連通，也可能存在環，樹中不能有環，
④錯誤，
正確答案為：②③

T7. 博艾中學進行了一次資訊學會考測驗，其優、良、及格、不及格的試卷數里分別為10、13、14、5張，現在這些卷子混在一起，要將這些卷子按照等級分為4疊，分卷子的方法是，每次將一疊有不同等級答卷的卷子分為兩堆，使得這兩堆中沒有相同等級的卷子，然后可以再分，直到分為4疊，要分完這些卷子，至少需要（84）次“分卷子“的操作，注意：將一堆數量為n的卷子分成兩堆，就會產生n次“分卷子”的操作，

【決議】類似于將42張撲克牌按花色分成4堆，每張牌至少被分了兩次，所以答案為 42 × 2 = 84 42\times2 = 84 42×2=84

T10. 在一個初始長度為 n n n的鏈表中連續進行k次操作，每次操作是讀入兩個數字 a i a_i ai?和 b i b_i bi?，在鏈表中找到元素為 a i a_i ai?的結點（假設一定可以找到），然后將 b i b_i bi?這個元素插入到這個結點前面，在最理想的情況下，鏈表訪問的結點數量最少可能是（k）(不算將要插入的結點)，

【決議】最理想的情況就是每次都在第一個結點前插入 b i b_i bi?，此時鏈表表訪問的總的結點數量為k，

T11. A班有5名風紀委員，B班有4名風紀委員，C班有3名風紀委員，現在需要這些同學中選取6名風紀委員巡邏，如果只關注各班派出的風紀委員人數，有（18）種不同的方案？

【決議】題目要求只關注各班派出的風紀委員人數，可以分情況討論：

C班派出0名風紀委員，那么A班派出的人數有4種可能， 2 ? 5 2-5 2?5
C班派出1名風紀委員，那么A班派出的人數有5種可能， 1 ? 5 1-5 1?5
C班派出2名風紀委員，那么A班派出的人數有5種可能， 0 ? 4 0-4 0?4
C班派出3名風紀委員，那么A班派出的人數有4種可能， 0 ? 3 0-3 0?3

所以一共有18種不同的方案

T13. 已知rand()可以生成一個0到32767的隨機整數，如果希望得到一個范圍在 [ a , b ) [a,b) [a,b)的隨機整數， a a a別 b b b均是不超過100的正整數且 a < b a<b a<b，那么可行的運算式是什么?

【決議】舉例驗證即可，例如要生成的是 [ 1 , 10 ) [1,10) [1,10)的隨機整數，可以通過 r a n d ( ) % 9 + 1 rand()\%9+1 rand()%9+1得到，即 r a n d ( ) % ( b ? a ) + a rand()\%(b -a)+a rand()%(b?a)+a

T14. 一個7個頂點的完全圖需要至少刪掉（15）條邊才能變為森林?

【決議】一棵樹也可以成為森林，所以將完全圖變為一棵樹，最少刪掉 21 ? 6 = 15 21-6=15 21?6=15條邊，

T15. 2020年8月，第（37）屆全國青少年資訊學奧林匹克競賽在（長沙）舉行，

【決議】常識題，NOI從1984年開始舉辦全國性競賽，所以到2020年應該是第37屆，

閱讀程式

T1.

#include <iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if(n <= 1 || m < 2)
        return 1;
    if(gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for(int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < MAXN; i ++)
        for(int j = 0; j < MAXN; j ++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
}

luo函式中，m的值不可能是奇數，（錯誤）
將第11行的 < < <改為 < = <= <=，程式的輸出結果可能會改變，（正確）

【決議】i <= m會導致for回圈中多一次遞回呼叫，而當n <= 1 || m < 2時，luo函式回傳1，從而導致結果發生改變，

若將第8、9、13行洗掉，程式的運行的結果不變，（正確）

【決議】第8、9、13行去掉，也就是不會記憶gu[i][j]，相當于沒有記憶化的深度優先搜索，效率降低了，但不影響最后結果，

在添加合適的頭檔案后，將第19到21行替換為memset(gu, 255, sizeof(gu));可以起到相同的作用，（正確）

【決議】 255 = ( 11111111 ) 2 = 0 x F F 255 = (11111111)_2=0xFF 255=(11111111)2?=0xFF，相當于將gu陣列初始化為-1，

輸入資料為4 8，則輸出為（8），

【決議】畫遞回樹模擬即可，

最壞情況下，此程式的時間復雜度是（ O ( m 2 n ) O(m^2n) O(m2n)），

【決議】本題深度優先搜索的遞回樹的高度為 n n n，每層的呼叫次數和 m m m有關：

m = 2，呼叫1次
m = 4，呼叫2次
m = 8，呼叫3次
…
總的呼叫次數 = 1 + 2 + 3... =1+2+3... =1+2+3...，近似于 m 2 m^2 m2，所以時間復雜度是 O ( m 2 n ) O(m^2n) O(m2n)，

T2.

#include <cstdio>
using namespace std;
int n, m;
int f[101][101];
int F[101][101];
int main() {
    scanf("%d%d", &n, &m); //n的值在1到100之間
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= m; i ++) {
        int u, v, w; //w的值在0到10000之間
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = f[v][u] = w;
    }
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                if(f[i][k] != -1 && f[k][j] != -1)
                    if(f[i][j] == -1 || f[i][j] > f[k][j] + f[i][k])
                        f[i][j] = f[i][k] + f[k][j];
    int ans = 2147483647;
    for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++) {
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        F[x][y] = f[x][y];
                F[i][j] = F[j][i] = 0;
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        if(F[x][y] == -1 || F[x][y] > F[x][i] + F[i][y])
                            F[x][y] = F[x][i] + F[i][y];
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        if(F[x][y] == -1 || F[x][y] > F[x][j] + F[j][y])
                            F[x][y] = F[x][j] + F[j][y];
                int res = 0;
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        res += F[x][y];
                ans = min(res, ans);
            }
    printf("%d\n", ans);    
    return 0;
}

14到16行，將外層則內層的回圈變數依次訓整為i、j、k，程式的運行的結果不變，（錯誤）

【決議】Floyd多源匯最短路演算法是利用動態規劃的思想，列舉每一個點作為中轉點，來松弛任意兩點的路徑，所以第一重回圈是列舉中轉點，回圈變數依次訓整為i、j、k后，19行代碼也要隨之修改，

這個程式的時間復雜度和m無關，（錯誤）

【決議】難道輸入也算？

20行的ans如果初始化為 1 0 7 10^7 107時,可能無法得到正確結果，（正確）

【決議】 ans為任意兩點最短距離之和的最小值，一共有 ( n ? 1 ) × n 2 \frac{(n-1)\times n}{2} 2(n?1)×n?條邊，每條邊的權值最大為10000，所以最大值可能超過 1 0 7 10^7 107

若將第27到30行的部分和31到34行的兩個部分互換，程式的運行的結果不變，（正確）

【決議】程式的第26行F[i][j] = F[j][i] = 0;，作用是將i、j兩點用權值為0的邊連接起來，相當于合并了兩點，然后使用i、j兩點嘗試松弛其它點之間的最短路徑，所以，先使用i點或是j點對最終結果沒有影響，

若資料如資料為下面的值，則輸出結果為（14），

【決議】如下圖所示，在1、4之間連接一條權值為0的邊，此時個點之間的最短距離：

f[1][2] = 3
f[1][3] = 2，經過4點中轉，
f[1][4] = 0
f[2][3] = 4
f[2][4] = 3 ，經過1點中轉
f[3][4] = 2

最短距離之和為14

T3.

#include <iostream>
using namespace std;
#define MOD 19260817
#define MAXN 1005
long long A[MAXN][MAXN] = {0}, sum[MAXN][MAXN] = {0};
int n, m, q;
int main() {
    A[1][1] = A[1][0] = 1;
    for(int i = 2; i <= 1000; i ++) {
        A[i][0] = 1;
        for(int j = 1; j <= i; j ++)
            A[i][j] = (A[i - 1][j] + A[i - 1][j - 1]) % MOD;
    }
    for(int i = 1; i <= 1000; i ++)
        for(int j = 1; j <= 1000; j ++)
            sum[i][j] = (sum[i - 1][j] + sum[i][j - 1]
                - sum[i - 1][j - 1] + A[i][j] + MOD) % MOD;
    int q;
    cin >> q;
    while(q --) {
        int n, m;
        cin >> n >> m;
        cout << sum[n][m] << endl;
    }
    return 0;
}

當i<=j時，A[i][j]的值是0，（錯誤）

【決議】當i == j時，A[i][j] = 1，

當i>j時，A[i][j]的值相當于從i個不同元素中取出j個元素的排列數，（錯誤）

【決議】楊輝三角（帕斯卡三角）求組合數，

sum[i][j]的值（ 1 < j ≤ 1000 1<j\le1000 1<j≤1000）不小于sum[i-1][j-1]的值，(錯誤)

【決議】sum[i][j]為矩陣的前綴和，但是，因為在計算程序中需要對MOD求余數，所以sum[i][j]的值不一定大于sum[i-1][j-1]的值，

若將第12行改為A[i][j]=(A[i-1][j] + A[i-1][j-1] + MOD) % MOD;，程式的運行結果不變，（正確）

【決議】加法的同余性質，

A[i][j]（ 1 ≤ i ≤ 10 , 1 ≤ j ≤ 10 1\le i\le10,1\le j\le10 1≤i≤10,1≤j≤10）的所有元素中，最大值為是（），

【決議】最大值為 C 10 5 = 252 C_{10}^5=252 C105?=252，

若輸入下列資料，則輸出為（50）

1
5 3

【決議】求楊輝三角前5行3列的子矩陣的和，答案為50，

完善程式

T1. （封禁xxs）現有 n n n個xxs（編號為1到n），每個xxs都有一個關注者，第 i i i個xxs的關注者是 a i a_i ai?，現在管理員要將其小的一些xxs的賬號封禁，但需要注意的是如果封禁了第 i i i個人，那么為了不打草驚蛇，就不能封禁他的關注者 a i a_i ai?，現在想知道最多可以封禁多少個xxs，

輸入第一行是一個不超過300000的整數 n n n，第二行是 n n n個 1 1 1到 n n n的整數表示 a i a_i ai?，

輸出一行，一個整數表示答案，

#include <cstdio>
using namespace std;
#define MAXN 300005
int n, ans = 0, a[MAXN], in[MAXN] = {0};
bool vis[MAXN] = {0};
void dfs(int cur, int w) {
    if(vis[cur])
        return;
    vis[cur] = true;
    if(w == 1) ans ++;
    ①
    if(②)
        dfs(a[cur], ③);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
       scanf("%d", &a[i]);
       in[a[i]] ++;
    }
    for(int i = 1; i <= n; i ++)
        if(!in[i]) ④;
    for(int i = 1; i <= n; i ++)
        if(⑤) dfs(i, 0);
    printf("%d\n", ans);
   return 0;
}

【決議】題目中提示每個xxs只有一個關注者，a[i]表示第i個xxs的關注者，即a[i]是i的粉絲，in[a[i]]表示a[i]的入度，可以理解為a[i]的粉絲個數，那么如果in[a[i]]不為0，為了不打草驚蛇，就不能封禁a[i]，

空①，分析第10行，if(w == 1) ans ++;，表示封禁一個xxs，封禁后，這個xxs的關注者（a[cur]）的粉絲數量應該減少一個，所以應填入in[a[cur]]--，
空②，封禁cur后，如果cur的關注者的粉絲為0，或者cur的粉絲數量為0，那么繼續對cur的關注者進行處理，所以此空應判斷in[a[cur]] == 0 || w == 1，
空③，如果w == 1，那么對cur的關注者不能夠直接封禁，那么遞回處理時，w = 0；如果w == 0 && in[a[cur]] == 0，此時對a[cur]可以封禁，w = 1，所以此空應填入1 - w，
空④，如果i的粉絲為0，可以直接封禁，此空應填dfs(i, 1)，
空⑤，如果i還沒有處理，即vis[i]為0，所以此空應填!vis[i]，

T2. 大水

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/170314.html

標籤：其他

上一篇：CPU 執行程式的秘密，藏在了這 15 張圖里

下一篇：Vue中組件的遞回使用方法