2020十一屆藍橋杯B 第一場 C/C++-有解無憂

文章目錄

- 題目A：跑步訓練
- 題目B：紀念日
- 題目C：合并檢測
- 題目D：REPEAT程式
- 題目E：矩陣
- 題目F：整數序列
- 題目G：解碼
- 題目H：走方格
- 題目I：整數拼接
- 題目J：網路分析

題目A：跑步訓練

本題總分：5 分
【問題描述】
小明要做一個跑步訓練，
初始時，小明充滿體力，體力值計為 10000 ，如果小明跑步，每分鐘損耗 600 的體力，如果小明休息，每分鐘增加 300 的體力，體力的損耗和增加都是均勻變化的，
小明打算跑一分鐘、休息一分鐘、再跑一分鐘、再休息一分鐘……如此回圈，如果某個時刻小明的體力到達 0 ，他就停止鍛煉，
請問小明在多久后停止鍛煉，為了使答案為整數，請以秒為單位輸出答案，答案中只填寫數，不填寫單位，

#include<bits/stdc++.h>
int solve() {
  int x = 10000, res = 0;
  while(1) {
    for(int i=0;i<60;i++) {
      x -= 10; ++res;     
      if(x <= 0) return res;
    }
    x += 300; res += 60;
  }
}
int main() {
  cout << solve();
  return 0;
}

題目B：紀念日

本題總分：5 分
【問題描述】
2020 年 7 月 1 日是中國共產黨成立 99 周年紀念日，
中國共產黨成立于 1921 年 7 月 23 日，
請問從 1921 年 7 月 23 日中午 12 時到 2020 年 7 月 1 日中午 12 時一共包含多少分鐘？

電腦計算機計算

在這里插入圖片描述

題目C：合并檢測

本題總分：10 分
【問題描述】
新冠疫情由新冠病毒引起，最近在 A 國蔓延，為了盡快控制疫情， A 國準備給大量民眾進病毒核酸檢測，
然而，用于檢測的試劑盒緊缺，
為了解決這一困難，科學家想了一個辦法：合并檢測，即將從多個人（ k 個）采集的標本放到同一個試劑盒中進行檢測，如果結果為陰性，則說明這 k 個人都是陰性，用一個試劑盒完成了 k 個人的檢測，如果結果為陽性，則說明至少有一個人為陽性，需要將這 k 個人的樣本全部重新獨立檢測（從理論上看，如果檢測前 k?1 個人都是陰性可以推斷出第 k 個人是陽性，但是在實際操作中不會利用此推斷，而是將 k 個人獨立檢測），加上最開始的合并檢測，一共使用了 k+1 個試劑盒完成了 k 個人的檢測，
A 國估計被測的民眾的感染率大概是 1，呈均勻分布，請問 k 取多少能最節省試劑盒？

設A國共有100人，那么合并檢測需要用的試劑為 100/k 個，均勻分布可以認為100個人里面就有一個人感染，所以，對于這一個人還需要個試劑，結果就是 100 /k + k ，根據基本不等式，當 100/ k = k 時，等式取到最小值，這時k=10，

題目D：REPEAT程式

附件 prog.txt 中是一個用某種語言寫的程式，
其中 REPEAT k 表示一個次數為 k 的回圈，回圈控制的范圍由縮進表達，從次行開始連續的縮進比該行多的（前面的空白更長的）為回圈包含的內容，
例如如下片段：
REPEAT 2:
?A = A + 4
?REPEAT 5:
??REPEAT 6:
???A = A + 5
??A = A + 7
?A = A + 8
A = A + 9
該片段中從 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的回圈兩次中，
REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 回圈中，
A = A + 5 實際總共的回圈次數是 2 × 5 × 6 = 60 次，
請問該程式執行完畢之后，A 的值是多少？

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 2020;
char s[MAXN];
// a[i] -> 第 i 層回圈的縮進，b[i] -> 第 i 層回圈的回圈次數
int a[MAXN], b[MAXN];
int main() {
    freopen("prog.txt", "r", stdin);
    int pos = 0, ans = 0, w = 1;
    gets(s); // 讀走第一行的 A = 0
    a[pos] = -1, b[pos] = 1; // 防止在堆疊空的時候彈堆疊
    while (gets(s)) {
        int n = strlen(s), p = 0;
        while (s[p] == ' ') p++; // 統計縮進
        while (a[pos] >= p) w /= b[pos--];// 彈掉堆疊里縮進大于等于當前行的
        if (s[n - 1] == ':') { // 當前行是回圈，壓堆疊
            int k = s[n - 2] - '0';
            pos = pos + 1;
            w *= k;
            a[pos] = p, b[pos] = k;
        } else {
            int k = s[n - 1] - '0';
            ans += k * w;
        }
    }
    printf("%d\n", ans);
    return 0;
}

或者看成python程式也可計算
在這里插入圖片描述

題目E：矩陣

本題總分：15 分
【問題描述】
把 1～2020 放在 2×1010 的矩陣里，要求同一行中右邊的比左邊大，同一列中下邊的比上邊的大，一共有多少種方案？
答案很大，你只需要給出方案數除以 2020 的余數即可，

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 2030;
const int MOD = 2020;
int dp[MAXN][MAXN];
int main() {
    int n = 2020;
    dp[1][1] = 1; // 1必然放在第一行
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] += dp[i - 1][j - 1]; // 將第i個數放第一行
            if (i - j <= j) {
                /*
                  因為是正向列舉，后面的數只會越來越大
                  要隨時保持第一行的個數不能比第二行的少
                  否則必然出現這一列第二行比第一行小的情況
                */
                dp[i][j] += dp[i - 1][j];
            }
            dp[i][j] %= MOD;
        }
    }
    printf("%d\n", dp[2020][1010]);
    return 0;
}

題目F：整數序列

時間限制: 1.0s??記憶體限制: 256.0MB??本題總分：15 分
【問題描述】
有一個序列，序列的第一個數是 n，后面的每個數是前一個數整除 2，請輸出這個序列中值為正數的項，
【輸入格式】
輸入一行包含一個整數 n，
【輸出格式】
輸出一行，包含多個整數，相鄰的整數之間用一個空格分隔，表示答案，
【評測用例規模與約定】
對于 80% 的評測用例，1≤n≤109，
對于所有評測用例，1≤n≤1018，

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main() {
    long long n;
    for (cin >> n; n != 0; n >>= 1) {
        cout << n;
        if (n != 1) putchar(' ');
        else putchar('\n');
    }
    return 0;
}

題目G：解碼

時間限制: 1.0s??記憶體限制: 256.0MB??本題總分：20 分
【問題描述】
小明有一串很長的英文字母，可能包含大寫和小寫，
在這串字母中，有很多連續的是重復的，小明想了一個辦法將這串字母表達得更短：將連續的幾個相同字母寫成字母 + 出現次數的形式，
例如，連續的 $5 個 a，即 aaaaa，小明可以簡寫成 a5（也可能簡寫成 a4a、aa3a 等），對于這個例子：HHHellllloo，小明可以簡寫成 H3el5o2，為了方便表
達，小明不會將連續的超過 9 個相同的字符寫成簡寫的形式，
現在給出簡寫后的字串，請幫助小明還原成原來的串，
【輸入格式】
輸入一行包含一個字串，
【輸出格式】
輸出一個字串，表示還原后的串，
【評測用例規模與約定】
對于所有評測用例，字串由大小寫英文字母和數字組成，長度不超過 100，
請注意原來的串長度可能超過 100，

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 110;
char s[MAXN];
int main() {
    scanf("%s", s);
    for (int i = 0; s[i]; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') {
            putchar(s[i]);
        } else if (s[i] >= 'A' && s[i] <= 'Z') {
            putchar(s[i]);
        } else {
            int k = s[i] - '0' - 1;
            while (k--) putchar(s[i - 1]);
        }
    }
    puts("");
    return 0;
}

題目H：走方格

時間限制: 1.0s??記憶體限制: 256.0MB??本題總分：20 分
【問題描述】
在平面上有一些二維的點陣，
這些點的編號就像二維陣列的編號一樣，從上到下依次為第 1 至第 n 行，從左到右依次為第 1 至第 m 列，每一個點可以用行號和列號來表示，
現在有個人站在第 1 行第 1 列，要走到第 n 行第 m 列，只能向右或者向下走，
注意，如果行號和列數都是偶數，不能走入這一格中，
問有多少種方案，
【輸入格式】
輸入一行包含兩個整數 n, m，
【輸出格式】
輸出一個整數，表示答案，
【評測用例規模與約定】
對于所有評測用例，1≤n≤30,1≤m≤30，

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 40;
int dp[MAXN][MAXN];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                dp[i][j] = 1;
                continue;
            }
            if ((i & 1) || (j & 1)) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

題目I：整數拼接

時間限制: 1.0s??記憶體限制: 256.0MB??本題總分：25 分
【問題描述】
給定義個長度為 n 的陣列 A1,A2,???,An，你可以從中選出兩個數 Ai 和 Aj ( i 不等于 j )，然后將 Ai 和 Aj 一前一后拼成一個新的整數，例如 12 和 345 可以拼成 12345 或 34512，注意交換 Ai 和 Aj 的順序總是被視為 2 種拼法，即便是 Ai=Aj 時，
請你計算有多少種拼法滿足拼出的整數是 K 的倍數，
【輸入格式】
第一行包含 2 個整數 n 和 K，
第二行包含 n 個整數 A1,A2,???,An，
【輸出格式】
一個整數代表答案，
【評測用例規模與約定】
對于 30% 的評測用例，1≤n≤1000,1≤K≤20,1≤Ai≤104，
對于所有評測用例，1≤n≤105，1≤K≤105，1≤Ai≤109，

做法：正解就是把所有數擴大幾倍后存起來，再用map找，要理解到，對于這些存起來的數字取膜k以后，只有兩個數字加起來%k等于0才算一對，后面就能暴力了，用陣列存每個數擴大10倍、100倍…十的十次方倍，存入a陣列，再用一個vis充當map的作用，順勢記錄這個數有多少位，

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N][11], x, mid;
int vis[N][11], n, k;
int cw(LL x) {
	int res = 0;
	while(x) {
		++res; x /= 10;
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; ++i) {
		scanf("%lld", &x);
		++vis[x%k][cw(x)]; a[i][0] = x;
		for(int j = 1; j <= 10; ++j) a[i][j] = a[i][j-1] * 10 % k;
	}
	LL res = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = 1; j <= 10; ++j) {
			mid = k - a[i][j]; mid %= k;
			if(vis[mid][j]) {
				res += vis[mid][j];
				if(a[i][0]%k == mid && cw(a[i][0]) == j) --res;
			}
		}
	}
	
	printf("%lld\n", res);
	return 0;
}

題目J：網路分析

時間限制: 1.0s??記憶體限制: 256.0MB??本題總分：25 分
【問題描述】
小明正在做一個網路實驗，
他設定了 n 臺電腦，稱為節點，用于收發和存盤資料，
初始時，所有節點都是獨立的，不存在任何連接，
小明可以通過網線將兩個節點連接起來，連接后兩個節點就可以互相通信了，兩個節點如果存在網線連接，稱為相鄰，
小明有時會測驗當時的網路，他會在某個節點發送一條資訊，資訊會發送到每個相鄰的節點，之后這些節點又會轉發到自己相鄰的節點，直到所有直接或間接相鄰的節點都收到了資訊，所有發送和接收的節點都會將資訊存盤下來，一條資訊只存盤一次，
給出小明連接和測驗的程序，請計算出每個節點存盤資訊的大小，
【輸入格式】
輸入的第一行包含兩個整數 n,m，分別表示節點數量和運算元量，節點從
1 至 n 編號，
接下來 m 行，每行三個整數，表示一個操作，
如果操作為 1 a b，表示將節點 a 和節點 b 通過網線連接起來，當 a=b 時，表示連接了一個自環，對網路沒有實質影響，
如果操作為 2 p t，表示在節點 p 上發送一條大小為 t 的資訊，
【輸出格式】
輸出一行，包含 n 個整數，相鄰整數之間用一個空格分割，依次表示進行
完上述操作后節點 1 至節點 n 上存盤資訊的大小，
【評測用例規模與約定】
對于 30% 的評測用例，1≤n≤20，1≤m≤100，
對于 50% 的評測用例，1≤n≤100，1≤m≤1000，
對于 70% 的評測用例，1≤n≤1000，1≤m≤10000，
對于所有評測用例，1≤n≤10000，1≤m≤100000，1≤t≤100，

做法：用w陣列記錄該點所有子孫都需要+的權值，每次合并都下傳標記，復雜度n^2，極限卡常

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int w[N], fa[N], res[N];
int Find(int x) {
  return fa[x] == x ? x : fa[x] = Find(fa[x]);
} 
int n, m;
void Merg(int x, int y) {
  int fx = Find(x), fy = Find(y);
  if(fx != fy) {
    for(register int i = 1; i <= n; ++i) res[i] += w[Find(i)];
    memset(w, 0, sizeof w);
    fa[fx] = fy;
  }
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; ++i) fa[i] = i;
  int opt, a, b;
  while(m--) {
    scanf("%d%d%d", &opt, &a, &b);
    if(opt == 1) Merg(a, b);
    else w[Find(a)] += b;
  }
  for(int i = 1; i <= n; ++i) printf("%d%c", res[i]+w[Find(i)], i==n?'\n':' ');
  return 0;
}

連接兩個連通塊，很容易想到并查集，但是比賽的時候沒有想到如何比較好的解決整個連通塊加上一個 t，所以就暴力列舉所有節點，如果和 p 屬于一個連通塊就加 t，對標70分的做法，賽后好像想明白怎么解決整個連通塊的修改了，還是類似線段樹懶標記先把修改存到連通塊的根上面之后再往下傳遞，

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 10010;
int dsu[MAXN], mark[MAXN];
int find(int u) {
    if (dsu[u] == 0) return u;
    int fu = find(dsu[u]);
    if (dsu[u] != fu) { // 沒有直接連在根上
        mark[u] += mark[dsu[u]]; // 把父親那的資料懶標記下傳
        dsu[u] = fu; // 把根設為父親， 狀態壓縮
    }
    return fu;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        if (op == 1) {
            int fa = find(a);
            int fb = find(b);
            if (fa != fb) {
                dsu[fa] = fb;
                /*
                由于fa接到了fb上，fb的mark之后會傳遞給fa
                但是這部分資料是fb獨有的，不該傳給fa
                所以事先在fa里減掉一個mark[fb]
                之后mark[fb]傳回來才能保持不受影響
                */
                mark[fa] -= mark[fb];
            }
        } else {
            int fa = find(a);
            mark[fa] += b;
        }
    }
    for (int i = 1; i <= n; i++) {
        int res = mark[i];
        int fi = find(i);
        if (fi != i) res += mark[fi]; // 自己不是根，就說明有部分資料在根上還沒傳下來
        printf("%d%c", res, " \n"[i == n]);
    }
    return 0;
}

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

標籤：區塊鏈

上一篇：【2020 電設G題影像題解】

下一篇：Matlab數值剔除