文章目錄

• T1：數字游戲
• • 題目
  • CODE
• T2：公交換乘
• • 題目
  • CODE
• T3：紀念品
• • 題目
  • 題解
  • CODE
• T4：加工領獎
• • 題目
  • 題解
  • CODE
• 關于普及組的想法&游記

T1：數字游戲

題目

小 K 同學向小 P 同學發送了一個長度為 8 的 01 字符串來玩數字游戲，小 P 同學想 要知道字符串中究竟有多少個 1。
注意：01 字符串為每一個字符是 0 或者 1 的字符串，如“101”（不含雙引號）為一 個長度為 3 的 01 字符串。
輸入描述:
輸入文件只有一行，一個長度為 8 的 01 字符串 s。
輸出描述:
輸出文件只有一行，包含一個整數，即 01 字符串中字符 1 的個數。
示例1
輸入
00010100
輸出
2
說明
該 01 字符串中有 2 個字符 1
示例2
輸入
11111111
輸出
8
說明
該 01 字符串中有 8 個字符 1。
示例3
輸入
復制
01010101
輸出
復制
4
備注:
對于 20% 的數據，保證輸入的字符全部為 0。
對于 100% 的數據，輸入只可能包含字符 0 和字符 1，字符串長度固定為 8

CODE

有很多方法，一邊輸入一邊統計，或者存在char/string里面掃一遍即可，C++語言打卡題

#include <cstdio> char s[15]; int sum; int main() {scanf ( "%s", s );for ( int i = 0;i < 8;i ++ )if ( s[i] == '1' )sum ++;printf ( "%d", sum );return 0; }

T2：公交換乘

題目

著名旅游城市 B 市為了鼓勵大家采用公共交通方式出行，推出了一種地鐵換乘公交 車的優惠方案：
在搭乘一次地鐵后可以獲得一張優惠票，有效期為 45 分鐘，在有效期內可以 消耗這張優惠票，免費搭乘一次票價不超過地鐵票價的公交車。在有效期內指 開始乘公交車的時間與開始乘地鐵的時間之差小于等于 45 分鐘，即：$t_{bus}?t_{subway}\le 45$
搭乘地鐵獲得的優惠票可以累積，即可以連續搭乘若干次地鐵后再連續使用優惠票搭乘公交車。
搭乘公交車時，如果可以使用優惠票一定會使用優惠票；如果有多張優惠票滿 足條件，則優先消耗獲得最早的優惠票。
現在你得到了小軒最近的公共交通出行記錄，你能幫他算算他的花費嗎？

輸入描述:
輸入文件的第一行包含一個正整數 𝑛，代表乘車記錄的數量。
接下來的 𝑛 行，每行包含 3 個整數，相鄰兩數之間以一個空格分隔。第 𝑖 行的 第 1 個整數代表第 𝑖 條記錄乘坐的交通工具，0 代表地鐵，1 代表公交車；第 2 個 整數代表第 𝑖 條記錄乘車的票價$pric{e}_i$；第三個整數代表第 𝑖 條記錄開始乘車的時 間$t_i$（距 0 時刻的分鐘數）。
我們保證出行記錄是按照開始乘車的時間順序給出的，且不會有兩次乘車記錄出現 在同一分鐘

輸出描述:
輸出文件有一行，包含一個正整數，代表小軒出行的總花費
示例1
輸入
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
輸出
36
說明
第一條記錄，在第 3 分鐘花費 10 元乘坐地鐵。
第二條記錄，在第 46 分鐘乘坐公交車，可以使用第一條記錄中乘坐地鐵獲得的優 惠票，因此沒有花費。
第三條記錄，在第 50 分種花費 12 元乘坐地鐵。
第四條記錄，在第 96 分鐘乘坐公交車，由于距離第三條記錄中乘坐地鐵已超過 45 分鐘，所以優惠票已失效，花費 3 元乘坐公交車。
第五條記錄，在第 110 分鐘花費 5 元乘坐地鐵。
第六條記錄，在第 135 分鐘乘坐公交車，由于此時手中只有第五條記錄中乘坐地鐵 獲得的優惠票有效，而本次公交車的票價為 6 元，高于第五條記錄中地鐵的票價 5 元， 所以不能使用優惠票，花費 6 元乘坐公交車。
總共花費 36 元。

示例2
輸入
6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68
輸出
32
說明
第一條記錄，在第 1 分鐘花費 5 元乘坐地鐵。
第二條記錄，在第 16 分鐘花費 20 元乘坐地鐵。
第三條記錄，在第 23 分鐘花費 7 元乘坐地鐵。
第四條記錄，在第 31 分鐘乘坐公交車，此時只有第二條記錄中乘坐的地鐵票價高 于本次公交車票價，所以使用第二條記錄中乘坐地鐵獲得的優惠票。
第五條記錄，在第 38 分鐘乘坐公交車，此時第一條和第三條記錄中乘坐地鐵獲得 的優惠票都可以使用，使用獲得最早的優惠票，即第一條記錄中乘坐地鐵獲得的優惠票。
第六條記錄，在第 68 分鐘乘坐公交車，使用第三條記錄中乘坐地鐵獲得的優惠票。 總共花費 32 元。
備注:
對于 30% 的數據，$n\le 1,000，t_i\le 10^6$
另有 15% 的數據，$t_i\le 10^7$，$pric{e}_i$都相等。
另有 15% 的數據，$t_i\le 10^9$，$pric{e}_i$都相等。
對于 100% 的數據，$n\le 10^5$n，$t_i\le 10^9$，$1\le pric{e}_i\le 1,000$

CODE

普及組前面兩道題都是C++語言的打卡題，實在不知道如何錯（別打我）
這個就是根據題意唄，然后找最前面一個滿足要求的優惠票，最暴力的就是輸入一個選擇，就在之前的選擇中去遍歷尋找符合要求的答案，$O(n^2)$顯然TLE
用一個隊列或者手打隊列進行維護就是$O(n)$的復雜度了，保證隊列里面的優惠卷都是控制在時間差之內的，然后隊列的頭就是最小的了，作為一個答案選擇，彈出。。。

#include <cstdio> #define MAXN 100005 struct node {int p, t, num;node () {}node ( int Price, int Ti, int Num ) {p = Price;t = Ti;num = Num;} }Freee[MAXN]; int n, opt, price, ti; int head = 1, tail, result; bool vis[MAXN];int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ ) {scanf ( "%d %d %d", &opt, &price, &ti );for ( int j = head;j <= tail;j ++ )if ( ti - Freee[j].t > 45 )head ++;elsebreak;if ( opt == 0 ) {result += price;Freee[++ tail] = node ( price, ti, i );}else {bool flag = 1;for ( int j = head;j <= tail;j ++ )if ( ! vis[Freee[j].num] && Freee[j].p >= price ) {vis[Freee[j].num] = j;flag = 0;break;}if ( flag )result += price;}}printf ( "%d", result );return 0; }

T3：紀念品

題目

小偉突然獲得一種超能力，他知道未來 T 天 N 種紀念品每天的價格。某個紀念品 的價格是指購買一個該紀念品所需的金幣數量，以及賣出一個該紀念品換回的金幣數量。
每天，小偉可以進行以下兩種交易無限次：
任選一個紀念品，若手上有足夠金幣，以當日價格購買該紀念品；
賣出持有的任意一個紀念品，以當日價格換回金幣。
每天賣出紀念品換回的金幣可以立即用于購買紀念品，當日購買的紀念品也可以當日賣出換回金幣。當然，一直持有紀念品也是可以的。
T 天之后，小偉的超能力消失。因此他一定會在第 T 天賣出所有紀念品換回金幣。
小偉現在有 M 枚金幣，他想要在超能力消失后擁有盡可能多的金幣。

輸入描述:
第一行包含三個正整數 T,N,M，相鄰兩數之間以一個空格分開，分別代表未來天數 T，紀念品數量 N，小偉現在擁有的金幣數量 M。
接下來 T 行，每行包含 N 個正整數，相鄰兩數之間以一個空格分隔。第 𝑖 行的 N 個正整數分別為 $P_{i,1}$, $P_{i,2}$,$\dots \dots \dots \dots ,P_{i,n}$
表示第 𝑖 天第 𝑗 種紀念品的價格
輸出描述:
輸出僅一行，包含一個正整數，表示小偉在超能力消失后最多能擁有的金幣數量

示例1
輸入
6 1 100
50
20
25
20
25
50
輸出
305
說明
最佳策略是：
第二天花光所有 100 枚金幣買入 5 個紀念品 1；
第三天賣出 5 個紀念品 1，獲得金幣 125 枚；
第四天買入 6 個紀念品 1，剩余 5 枚金幣；
第六天必須賣出所有紀念品換回 300 枚金幣，第四天剩余 5 枚金幣,共 305 枚金幣。
超能力消失后，小偉最多擁有 305 枚金幣

示例2
輸入
3 3 100
10 20 15
15 17 13
15 25 16
輸出
217
說明
最佳策略是：
第一天花光所有金幣買入 10 個紀念品 1；
第二天賣出全部紀念品 1 得到 150 枚金幣并買入 8 個紀念品 2 和 1 個紀念品 3，剩 余 1 枚金幣；
第三天必須賣出所有紀念品換回216 枚金幣，第二天剩余1枚金幣，共 217 枚金幣。
超能力消失后，小偉最多擁有 217 枚金幣

備注:
對于 10% 的數據，$T=1$。
對于 30% 的數據，$T\le 4,N\le 4,M\le 100$，所有價格 $10\le P_{i,j}\le 100$。
另有 15% 的數據，$T\le 100,N=1$。
另有 15% 的數據，$T=2,N\le 100$。
對于 100% 的數據，$T\le 100,N\le 100,M\le 10^3$，所有價格 $1\le P_{i,j}\le 10^4$，數據保證任意時刻，小明手上的金幣數不可能超過$10^4$

題解

首先對于10pots，直接輸出m，讓你不至于報零，真良心
我們直接進入正解：

首先的貪心思想大家都能想到的就是：如果第i天的第j種商品在i天買進，第i+1天賣出去能產生收益，即$p[i+1][j]?p[i][j]>0$，就應該購入并在下一天賣出，這樣產生的收益一定是最大的

因此問題演變為今天買入哪些商品能在下一天獲取最大利益
再分析一下：今天的錢數m，商品價格$p[i][j]$，商品利益$p[i+1][j]?p[i][j]$，
如何用m錢買入若干種商品獲取最大利益，顯然是背包問題

又因為數據保證任意時刻，小明手上的金幣數不可能超過$10^4$，可以篤定背包不會超時

---

故在每一天都重新用一次背包轉移出用手上所擁有的錢數能產生多少利益
設$dp[k]$表示用$k$枚金幣能產生的最大利益，則$dp[m]$就是當天所賺的利益
轉移方程式如下，如果不能理解的歡迎評論或者自行學習背包
$dp[k]=max(dp[k],dp[k?p[i][j]]+p[i+1][j]?p[i][j])$

CODE

#include <cstdio> #include <iostream> using namespace std; #define MAXN 105 #define MAXM 10005 int T, n, m; int p[MAXN][MAXN]; int dp[MAXM]; int main() {scanf ( "%d %d %d", &T, &n, &m );for ( int i = 1;i <= T;i ++ )for ( int j = 1;j <= n;j ++ )scanf ( "%d", &p[i][j] );if ( T == 1 )return ! printf ( "%d", m );for ( int i = 1;i < T;i ++ ) {for ( int j = 1;j <= m;j ++ )dp[j] = 0;for ( int j = 1;j <= n;j ++ ) {if ( p[i][j] >= p[i + 1][j] )continue;for ( int k = p[i][j];k <= m;k ++ )dp[k] = max ( dp[k], dp[k - p[i][j]] + p[i + 1][j] - p[i][j] );}m += dp[m];}printf ( "%d", m );return 0; }

T4：加工領獎

題目

凱凱的工廠正在有條不紊地生產一種神奇的零件，神奇的零件的生產過程自然也很神奇。工廠里有 n 位工人，工人們從 $1～n$ 編號。某些工人之間存在雙向的零件傳送帶。保證每兩名工人之間最多只存在一條傳送帶。

如果 x 號工人想生產一個被加工到第 L $(L>1)$階段的零件，則所有與 x 號工人有傳送帶直接相連的工人，都需要生產一個被加工到第 L - 1 階段的零件（但 x 號工人自己無需生產第 L - 1 階段的零件）。
如果 x 號工人想生產一個被加工到第 1 階段的零件，則所有與 x 號工人有傳送帶直接相連的工人，都需要為 x 號工人提供一個原材料。

軒軒是 1 號工人。現在給出 q 張工單，第 i 張工單表示編號為 $a_i$的工人想生產一個第 $L_i$階段的零件。軒軒想知道對于每張工單，他是否需要給別人提供原材料。他知道聰明的你一定可以幫他計算出來！

輸入格式
第一行三個正整數 n，m 和 q，分別表示工人的數目、傳送帶的數目和工單的數目。

接下來 m 行，每行兩個正整數 u 和 v，表示編號為 u 和 v 的工人之間存在一條零件傳輸帶。保證 $u=v$
接下來 q 行，每行兩個正整數 a 和 L，表示編號為 a 的工人想生產一個第 L 階段的零件。

輸出格式
共 q 行，每行一個字符串 Yes 或者 No。如果按照第 i 張工單生產，需要編號為 1 的軒軒提供原材料，則在第 i 行輸出 Yes；否則在第 i 行輸出 No。注意輸出不含引號。

輸入輸出樣例
輸入
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2
輸出
No
Yes
No
Yes
No
Yes
輸入
5 5 5
1 2
2 3
3 4
4 5
1 5
1 1
1 2
1 3
1 4
1 5
輸出
No
Yes
No
Yes
Yes
說明/提示
【輸入輸出樣例 1 說明】

編號為 1 的工人想生產第 1 階段的零件，需要編號為 2 的工人提供原材料。
編號為 2 的工人想生產第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。
編號為 3 的工人想生產第 1 階段的零件，需要編號為 2 的工人提供原材料。
編號為 1 的工人想生產第 2 階段的零件，需要編號為 2 的工人生產第 1 階段的零 件，需要編號為 1 和 3 的工人提供原材料。
編號為 2 的工人想生產第 2 階段的零件，需要編號為 1 和 3 的工人生產第 1 階段的零件，他/她們都需要編號為 2 的工人提供原材料。
編號為 3 的工人想生產第 2 階段的零件，需要編號為 2 的工人生產第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。

【輸入輸出樣例 2 說明】

編號為 1 的工人想生產第 1 階段的零件，需要編號為 2 和 5 的工人提供原材料。
編號為 1 的工人想生產第 2 階段的零件，需要編號為 2 和 5 的工人生產第 1 階段的零件，需要編號為 1,3,4 的工人提供原材料。
編號為 1 的工人想生產第 3 階段的零件，需要編號為 2 和 5 的工人生產第 2 階段的零件，需要編號為 1,3,4 的工人生產第 1 階段的零件，需要編號為 2,3,4,5 的工人提供原材料。
編號為 1 的工人想生產第 4 階段的零件，需要編號為 2 和 5 的工人生產第 3 階段的零件，需要編號為 1,3,4 的工人生產第 2 階段的零件，需要編號為 2,3,4,5 的工人生產第 1 階段的零件，需要全部工人提供原材料。
編號為 1 的工人想生產第 5 階段的零件，需要編號為 2 和 5 的工人生產第 4 階段的零件，需要編號為 1,3,4 的工人生產第 3 階段的零件，需要編號為 2,3,4,5 的工人生產第 2 階段的零件，需要全部工人生產第 1 階段的零件，需要全部工人提供原材料。

【數據規模與約定】
共 20 個測試點。
$1\le u,v,a\le n$
測試點 1~4，$1\le n,m\le 1000$，$q=3$，$L=1$
測試點 5~8，$1\le n,m\le 1000$，$q=3$，$1\le L\le 10$
測試點 9~12，$1\le n,m,L\le 1000$，$1\le q\le 100$
測試點 13~16，$1\le n,m,L\le 1000$，$1\le q\le 10^5$
測試點 17~20，$1\le n,m,q\le 10^5$ ，$1\le L\le 10^9$

題解

首先我們要提取出題目描述中所隱含的想法，舉個栗子：假設1，2號工人之間有生產線，那么如果1號想生產第3階段的零件，那么2號工人就要生產第2階段零件，此時的1號工人必須生產第1階段零件，原材料則由2號工人提供，所以這個過程就是兩點之間不停的來回跑，

---

在此基礎上，我們提出了一個想法如果v號工人距離1號工人的距離為$x$，那么要生產$L$階段的零件，1號工人就要生產$L?x，L?x?2，L?x?4...$階段的零件，而與1號工人相鄰的生產線就要生產$L?x+1，L?x?1，L?x?3...$階段的零件，當工人需要生產0階段的零件時意味著他就是需要提供原材料的

---

于是發現我們只需要判斷是否出現$L?x?y=0(y$%$2==0)$的情況即可，存在為零的情況嗎？

只需要滿足$L$與$x$必須同奇同偶，才可能有出現為0的情況

---

但是圖可能是有環的，所以對于一個工人而言，他與1號工人的距離是可能有奇數距離也可能有偶數的距離，而且距離可能存在多條，為了在要求生產零件的階段一樣時，能讓該號工人盡可能波及到1號工人，讓1號工人有產生原材料的可能，（如果距離不夠，1號工人與該工人要生產的零件一點關系都扯不上， 這也解釋了上面加粗的可能二字）

所以我們要去尋找到最小奇距離，最小偶距離，簡單的一個bfs就可以搜出來
具體的代碼解釋在CODE里面

CODE

#include <queue> #include <cstdio> #include <vector> #include <cstring> using namespace std; #define MAXN 100005 vector < int > G[MAXN]; queue < int > q; int n, m, Q, a, L; int dis[MAXN][2]; bool vis[MAXN][2]; //dis[i][0]:i號工人距離1號工人的最小奇距離 //dis[i][1]:i號工人距離1號工人的最小偶距離 void bfs () {q.push ( 1 );vis[1][0] = 1;while ( ! q.empty() ) {int t = q.front();q.pop();for ( int i = 0;i < G[t].size();i ++ ) {int v = G[t][i];if ( dis[t][1] + 1 < dis[v][0] ) {//到父親的距離是奇數，再+1，到兒子的距離就變成了偶數dis[v][0] = dis[t][1] + 1;if ( ! vis[v][0] ) {vis[v][0] = 1;q.push ( v );}}if ( dis[t][0] + 1 < dis[v][1] ) {//到父親的距離是偶數，再+1，到兒子的距離就變成了奇數dis[v][1] = dis[t][0] + 1;if ( ! vis[v][1] ) {vis[v][1] = 1;q.push ( v );}}} } }int main() {scanf ( "%d %d %d", &n, &m, &Q );for ( int i = 1;i <= m;i ++ ) {int u, v;scanf ( "%d %d", &u, &v );G[u].push_back ( v );G[v].push_back ( u );}memset ( dis, 0x7f, sizeof ( dis ) );dis[1][0] = 0;//1號工人距離自己本身的偶距離肯定是0，奇距離就設置成為無窮大bfs ();for ( int i = 1;i <= Q;i ++ ) {scanf ( "%d %d", &a, &L );if ( L % 2 == 0 ) {//維護同奇同偶if ( L >= dis[a][0] )//距離足夠長，波及得到1號工人printf ( "Yes\n" );elseprintf ( "No\n" );}else {if ( L >= dis[a][1] )printf ( "Yes\n" );elseprintf ( "No\n" );}}return 0; }

好了，講解完畢，接下來不愿看的可以跳過了
接下來就是bb普及組的問題以及常規套路

關于普及組的想法&游記

對于第1題，近兩年都是輸入一行字符串，進行一個簡單的$if?else$判斷，數字的個數？小寫字母的個數？大寫字母的個數…所以我猜下一次多半也是這樣，畢竟打卡題只能這么考了

---

對于第2題，也是在一個大的$for$循環下面進行一些簡單的判斷操作，去年的龍虎斗，今年的公交換乘，都會把時間控制在$O(nlogn)$之內，并且不涉及高端操作或者高級算法，畢竟是個普及 ，唯獨可能會卡一卡$long$ $long$，分析好就可以了

---

對于第3題，亙古不變都是$dp$，而且是背包問題的變式，因為$dp$對于以后學習的高級算法是很有關系的，所以出題人會考察學生是否掌握$dp$，今年的紀念品比去年的擺渡車要簡單很多，但是$dp$是很考驗人的思維的，如何轉化極其重要，反正我最差的就是dp

---

對于第4題，既不能上升到提高組的難度，又不能比前面的簡單，那能考的就剩下簡單的數據結構或者圖論，最短路？最小生成樹？lca？線段樹？…但是如果考的是比較模板的題目，就會把它隱藏起來，需要我們去挖掘出來，今年的加工領獎亦是如此，只要挖掘出了是最小奇距離和最小偶距離，簡單的最短路甚至都不需要，一個bfs就搞定了。。。我明明考場上就是這么想的，也是這么打的，但是沒去推同奇同偶，所以答案輸出處理出錯，就GG了，幸好打了前面的暴力分，保住了一點小命

---

讓我們劍指2020CSP普及，不見不散

總結

以上是生活随笔為你收集整理的【2019CSP-J 普及组题解】数字游戏(number)，公交换乘(transfer)，纪念品(souvenir)，加工领奖(work) CSP普及游记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。