?

假期歡樂(lè)賽，確實(shí)挺輕松的，被逼迫寫(xiě)了題解。

A.推數(shù)
按列觀察，有的列有多個(gè)格子，看起來(lái)好復(fù)雜啊，先放一放。
按行觀察，黑色格子在 i 行 j 列：
當(dāng) i 是奇數(shù)，對(duì)應(yīng)數(shù)字第 i 位是 j-1
當(dāng) i 是偶數(shù)，對(duì)應(yīng)數(shù)字第 i 位是 9-j

B.體重
某位同學(xué)不是中間體重的充要條件是，比他重的人數(shù) >= mid 或 比他輕的人數(shù) >= mid
x 比 y 重，則 x, y 有單向連通關(guān)系，G[x][y] = true 。比 y 重的人數(shù)就是滿(mǎn)足 G[i][y] = true 的 i 的數(shù)量。
比 y 輕的人數(shù)類(lèi)似。
用 Floyd 跑一遍，再統(tǒng)計(jì)一下就好啦。

C.采蘑菇
觀察一下是一道動(dòng)規(guī)，狀態(tài)是這個(gè)：f[t][i] 時(shí)間 t 時(shí)在 i 位置能采摘的最大蘑菇數(shù)量。
f[t][i] = max(f[t-1][i-1], f[t-1][i], f[t-1][i+1]) + v[i]
注意邊界條件，f[0][k] = 0，其它的 f[0][i] = -INF (1 <= i <= n, i != k)
答案是 f[n][i] (1 <= i <= n)。考慮到第一維每次只用到了上一次的值(f[t-1]...)，可以加一個(gè)滾動(dòng)數(shù)組。

D.摘桃子
每棵樹(shù)都有桃子就是說(shuō)，只要走過(guò)一條小路就可以獲得 D 個(gè)桃子，這樣權(quán)值就從 點(diǎn) 上變到了 邊 上，考慮一下圖論。
電動(dòng)車(chē)線路等價(jià)于獲得 D-V 個(gè)桃子。建圖，求從 S 出發(fā)的最長(zhǎng)路即可。
能夠摘到無(wú)限桃子的情況就是圖中存在“正權(quán)回路”的情況，即有某個(gè)點(diǎn)在 SPFA 過(guò)程中的入隊(duì)次數(shù) > 總點(diǎn)數(shù)。不知道是不是這么叫，就是 SPFA 里面的負(fù)權(quán)回路那種東西……

E.數(shù)列
初看像貪心，有點(diǎn)像最長(zhǎng)公共子序列的樣子……不過(guò)仔細(xì)想想，怎么可能？（其實(shí)是看數(shù)據(jù)2000覺(jué)得不對(duì)勁才換思路的，逃
是一道動(dòng)規(guī)。用 f[i][j] 表示 X 數(shù)列前 i 個(gè)項(xiàng)要變成 Y 數(shù)列前 j 個(gè)項(xiàng)最少的操作次數(shù)。
當(dāng) X[i] = Y[j]
f[i][j] = f[i-1][j-1]
當(dāng) X[i] != Y[j]
f[i][j] = min(
f[i-1][j] + 1 (刪去 X 的第 i 項(xiàng))
f[i][j-1] + 1 (把 X 變成 Y 的前 j-1 項(xiàng)后在 X 末尾插入和 Y 的第 j 項(xiàng)相同的數(shù))
f[i-1][j-1] + 1 (把 X 的第 i 項(xiàng)改為 Y 的第 j 項(xiàng))
)
當(dāng) i 或 j 是 0 時(shí)，顯然 f[i][j] = abs(i - j)，即直接全部插入或全部刪除。這道題也可以滾動(dòng)一下優(yōu)化空間。

1 #include <stdio.h> 2 3 char A[15]; 4 5 int main() 6 { 7 int i, j; 8 for (i = 1; i <= 10; ++i) { 9 scanf("%s", A); 10 for (j = 0; j < 10; ++j) 11 if (A[j] == 'B') break; 12 printf("%d", i & 1 ? j : 9-j); 13 } 14 return 0; 15 } A 1 #include <stdio.h> 2 3 int G[150][150]; 4 5 int main() 6 { 7 int N, M, i, j, k; 8 bool flag = false; 9 scanf("%d%d", &N, &M); 10 for (i = 1; i <= M; ++i) { 11 int t1, t2; 12 scanf("%d%d", &t1, &t2); 13 if (t1 != t2) G[t1][t2] = true; 14 } 15 16 for (k = 1; k <= N; ++k) 17 for (i = 1; i <= N; ++i) 18 for (j = 1; j <= N; ++j) 19 if (!G[i][j] && G[i][k] && G[k][j]) G[i][j] = true; 20 21 for (i = 1; i <= N; ++i) { 22 int cnt1 = 0, cnt2 = 0; 23 for (j = 1; j <= N; ++j) { 24 if (G[j][i]) ++cnt1; 25 if (G[i][j]) ++cnt2; 26 } 27 if (cnt1 >= (N+1)/2 || cnt2 >= (N+1)/2) { 28 printf("%d ", i); 29 if (!flag) flag = true; 30 } 31 } 32 if (!flag) printf("0\n"); 33 return 0; 34 } B 1 #include <stdio.h> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int INF = 1e9; 7 8 int f[1200][150]; 9 10 int main() 11 { 12 int N, T, K, ans = 0, i, t; 13 scanf("%d%d%d", &N, &T, &K); 14 for (i = 1; i <= N; ++i) f[0][i] = -INF; 15 f[0][K] = 0; 16 for (t = 1; t <= T; ++t) { 17 for (i = 1; i <= N; ++i) { 18 int val; 19 scanf("%d", &val); 20 f[t&1][i] = -INF; 21 22 if (i > 1) f[t&1][i] = max(f[t&1][i], f[t&1^1][i-1]); 23 if (i < N) f[t&1][i] = max(f[t&1][i], f[t&1^1][i+1]); 24 f[t&1][i] = max(f[t&1][i], f[t&1^1][i]); 25 f[t&1][i] += val; 26 } 27 } 28 for (i = 1; i <= N; ++i) ans = max(ans, f[T&1][i]); 29 printf("%d\n", ans); 30 return 0; 31 } C 1 #include <stdio.h> 2 #include <queue> 3 #include <vector> 4 5 typedef long long LL; 6 7 using namespace std; 8 9 const int _N = 1200; 10 const LL INF = 99999999999999LL; 11 12 13 LL n, m; 14 LL dis[_N], cnt[_N]; 15 bool book[_N]; 16 bool flag; 17 18 struct node { 19 LL v, w; 20 node(LL _v, LL _w): 21 v(_v), w(_w) { } 22 }; 23 24 queue<LL> Q; 25 vector<node> G[_N]; 26 27 void SPFA(LL beg) 28 { 29 LL i, p; 30 for (i = 1; i <= n; ++i) 31 dis[i] = INF, book[i] = false, cnt[i] = 0; 32 dis[beg] = 0, Q.push(beg), book[beg] = true, cnt[beg] = 1; 33 while (!Q.empty()) { 34 int p = Q.front(); 35 Q.pop(), book[p] = false; 36 vector<node>::iterator it; 37 for (it = G[p].begin(); it != G[p].end(); ++it) { 38 if (dis[it->v] > dis[p] + it->w) { 39 dis[it->v] = dis[p] + it->w; 40 if (!book[it->v]) { 41 Q.push(it->v), book[it->v] = true; 42 if (++cnt[it->v] == n+1) { flag = true; break; } 43 } 44 } 45 } 46 if (flag) break; 47 } 48 return ; 49 } 50 51 int main() 52 { 53 LL i, t1, t2, t3, d, t, s; 54 scanf("%lld%lld%lld%lld%lld", &d, &m, &n, &t, &s); 55 for (i = 1; i <= m; ++i) { 56 scanf("%lld%lld", &t1, &t2); 57 G[t1].push_back(node(t2, -d)); 58 } 59 for (i = 1; i <= t; ++i) { 60 scanf("%lld%lld%lld", &t1, &t2, &t3); 61 G[t1].push_back(node(t2, t3-d)); 62 } 63 SPFA(s); 64 if (flag) { printf("Poor boss he\n"); return 0; } 65 LL ans = INF; 66 for (i = 1; i <= n; ++i) ans = min(ans, dis[i]); 67 printf("%lld\n", d-ans); 68 return 0; 69 } D 1 #include <stdio.h> 2 #include <algorithm> 3 4 using namespace std; 5 6 7 int x[2300], y[2300], f[2][2300]; 8 9 int main() 10 { 11 int n, m, i, j; 12 scanf("%d%d", &n, &m); 13 for (i = 1; i <= n; ++i) scanf("%d", &x[i]); 14 for (j = 1; j <= m; ++j) scanf("%d", &y[j]); 15 for (i = 0; i <= n; ++i) 16 for (j = 0; j <= m; ++j) { 17 if (!i || !j) { f[i&1][j] = abs(i - j); continue; } 18 if (x[i] == y[j]) { 19 f[i&1][j] = f[i&1^1][j-1]; 20 } else { 21 f[i&1][j] = min(f[i&1^1][j-1], min(f[i&1^1][j], f[i&1][j-1])) + 1; 22 } 23 } 24 printf("%d\n", f[n&1][m]); 25 return 0; 26 } E

題目 NKOJ 考試 118

?

A推數(shù)

時(shí)間限制 :?10000?MS???空間限制 :?65536?KB

問(wèn)題描述

　　　何老板在玩一個(gè)推理游戲，但他遇到了一點(diǎn)麻煩，需要你幫忙！請(qǐng)根據(jù)A,B兩幅圖，推導(dǎo)出C圖代表的數(shù)字！

輸入格式

一個(gè)由大寫(xiě)字母'B'和'W'構(gòu)成的10*10的矩陣，表示圖C，
其中'B'表示黑色方塊，'W'白色方塊

輸出格式

一行，一個(gè)數(shù)字，表示推導(dǎo)出的C代表的數(shù)字。

樣例輸入

BWWWWWWWWW
WWWWWWBWWW
WWWWBWWWWW
BWWWWWWWWW
WWWBWWWWWW
WWWWWWWWBW
WWWWBWWWWW
WWBWWWWWWW
WWWWWBWWWW
WWWWWWWBWW

樣例輸出

034931

?

B體重

時(shí)間限制 :?10000?MS???空間限制 :?65536?KB

問(wèn)題描述

近日，信競(jìng)班有人在散布謠言，說(shuō)何老板體重超重，這有損何老板在同學(xué)們心中的完美形象，讓何老板很是頭疼。何老板還了解到，散布該謠言的人號(hào)稱(chēng)自己擁有最合適的體重，體重值位于所有人的正中間，何老板決心找出這個(gè)家伙。

信競(jìng)班有n名同學(xué)，編號(hào)1到n，已知每名同學(xué)的體重都不相同。何老板想知道，哪個(gè)同學(xué)的體重位于正中間。也就是如果將n名同學(xué)按體重由輕到重排序后，該名同學(xué)位于第(n+1)/2名，這名同學(xué)一定是謠言散布者。

但是同學(xué)們都不肯準(zhǔn)確告訴何老板他的體重，何老板只好在暗中收集信息。

例如：n=5時(shí)，何老板搜集到了如下信息：

????1號(hào)同學(xué)比2號(hào)同學(xué)輕

????3號(hào)同學(xué)比4號(hào)同學(xué)輕　　

????1號(hào)同學(xué)比5號(hào)同學(xué)輕　　

????2號(hào)同學(xué)比4號(hào)同學(xué)輕　　

根據(jù)上面的情報(bào)，雖然何老板不能準(zhǔn)確得出哪個(gè)同學(xué)具有中間體重，但他可以肯定4號(hào)和1號(hào)不可能具有中間體重，因?yàn)?#xff0c;1、2、3比4輕，而2、4、5比1重，所以他可以排除到這兩名同學(xué)。

寫(xiě)一個(gè)程序統(tǒng)計(jì)出目前我們最多能排除掉多少個(gè)同學(xué)。也就是確定有多少個(gè)同學(xué)肯定不會(huì)是中間體重。

輸入格式

第一行:兩個(gè)整數(shù)n和m，其中n為奇數(shù)表示學(xué)生總數(shù)，m表示何老板搜集到的信息條數(shù)。

接下來(lái)的m行,每行兩個(gè)整數(shù)x和y，表示x號(hào)同學(xué)比y號(hào)同學(xué)重。

輸出格式

若干個(gè)整數(shù)，按從小到大的順序輸出不可能是中間重量的學(xué)生的編號(hào)。
若一個(gè)也找不出來(lái)，輸出0。

樣例輸入 1

5?4
2?1
4?3
5?1
4?2

樣例輸出 1

1?4

樣例輸入 2

11?5
1?2
3?4
5?6
7?8
9?10

樣例輸出 2

0

樣例輸入 3

31?29
2?1
3?1
4?1
5?1
6?1
7?1
8?1
9?1
10?1
11?1
12?1
13?1
14?1
15?1
16?1
17?1
18?1
19?1
20?1
21?1
22?1
23?1
24?1
25?1
26?1
27?1
28?1
29?1
30?1

樣例輸出 3

1

提示

?

1<=n<=100

1<=m<=5000

C采蘑菇

時(shí)間限制 :?10000?MS???空間限制 :?65536?KB

問(wèn)題描述

最近，何老板玩一款名叫“采蘑菇”的有趣手機(jī)游戲。
游戲地圖由水平放置的n塊磚(編號(hào)1到n)構(gòu)成，每一秒鐘，每塊磚上會(huì)新長(zhǎng)出一些蘑菇，蘑菇的生命時(shí)間只有1秒鐘，1秒鐘后蘑菇就消失了。游戲玩家操控的游戲角色“馬里奧”一開(kāi)始位于第k塊磚上，每一秒鐘，馬里奧有三種移動(dòng)方式可以選擇：
1.原地不動(dòng)，并采摘該磚上的蘑菇；
2.移動(dòng)到左邊一塊磚，并采摘該磚上的蘑菇；
3.移動(dòng)到右邊一塊磚，并采摘該磚上的蘑菇；
游戲一共持續(xù)t秒鐘，問(wèn)馬里奧最多能采集到多少顆蘑菇。

輸入格式

第一行，四個(gè)整數(shù)n,t,k，分別表示磚塊的數(shù)量，游戲的持續(xù)時(shí)間和一開(kāi)始馬里奧所處的位置。
接下來(lái)一個(gè)t*n的整數(shù)矩陣，其中第i行描述第i秒鐘的情況，第i行第j個(gè)數(shù)表示第i秒第j塊磚上長(zhǎng)出的蘑菇數(shù)。

輸出格式

一行，一個(gè)整數(shù)，表示能夠采摘到的最多蘑菇數(shù)。

樣例輸入

樣例輸入1：
4?3?2
3?1?1?1
2?1?1?1
1?5?4?1

樣例輸入2：
5?3?3
3?1?3?3?2?
5?6?5?1?6?
7?4?3?4?4?

樣例輸入3:
6?4?2
3?7?1?3?1?5?
4?2?6?6?3?6?
2?2?2?4?7?7?
2?7?6?2?4?6?

樣例輸出

樣例輸出1：
10

樣例輸出2：
16

樣例輸出3：
23

提示

對(duì)于30%的數(shù)據(jù) 1<=n<=10, 1<=t<=5;
對(duì)于100%的數(shù)據(jù) 1<=n<=100, 1<=t<=1000 ，1<=每塊磚上長(zhǎng)出的蘑菇數(shù)<=10000

樣例1說(shuō)明：
第一秒由2號(hào)磚移動(dòng)到1號(hào)磚，采3顆蘑菇
第二秒呆在1號(hào)磚不動(dòng)，采2顆蘑菇
第三秒由1號(hào)磚移動(dòng)到2號(hào)磚，采5顆蘑菇

?

D摘桃子

時(shí)間限制 :?-?MS???空間限制 :?165536?KB? 評(píng)測(cè)說(shuō)明 :?1s

問(wèn)題描述

又到了桃子成熟的季節(jié)，何老板的果園推出了摘桃子的活動(dòng)。
何老板的果園有N棵桃樹(shù)，編號(hào)1到N。果園里有M條單向小路，將一些桃樹(shù)連接起來(lái)，其中第i條小路連接Ai和Bi兩棵桃樹(shù)。何老板為了盈利，費(fèi)勁心機(jī)做了以下規(guī)定：
1.顧客一開(kāi)始從第S號(hào)桃樹(shù)開(kāi)始摘桃活動(dòng)；
2.每棵桃樹(shù)上有無(wú)限多個(gè)桃子，但是顧客一次在一棵桃樹(shù)上最多只能摘D個(gè)桃子，然后他必須到其它桃樹(shù)去摘桃。當(dāng)然，顧客也可以在其他地方摘桃后又回到原來(lái)摘過(guò)桃的桃樹(shù)，再摘D個(gè)桃子。而且這樣往返摘桃的次數(shù)是沒(méi)有限制的；
3.為方便顧客摘桃，何老板還提供電動(dòng)車(chē)服務(wù)，電動(dòng)車(chē)總共有T條單向線路，每條線路連接兩棵桃樹(shù)，其中第i條電動(dòng)車(chē)線路連接X(jué)i和Yi兩棵桃樹(shù)，乘坐一次的需要支付給何老板Vi個(gè)桃子。如果顧客手中沒(méi)有桃子，也可以乘坐電動(dòng)車(chē)，用以后摘取得桃子來(lái)支付就行；
4.顧客可以選在在任何時(shí)刻，任何桃樹(shù)處結(jié)束他的摘桃活動(dòng)；
?

今天你來(lái)到何老板的果園，你想知道，最多可以摘到多少個(gè)桃子呢？如果可以摘到無(wú)限度個(gè)桃子，輸出"Poor boss he"

輸入格式

第一行，5個(gè)整數(shù)，分別是D,M,N,T,S
接下來(lái)M行，每行兩個(gè)整數(shù)Ai和Bi，表示從Ai號(hào)桃樹(shù)到第Bi號(hào)桃樹(shù)有條單向小路
接下來(lái)T行，每行三個(gè)空格間隔的整數(shù)Xi,Yi,Vi,表示有一條從Xi號(hào)桃樹(shù)到Y(jié)i號(hào)桃樹(shù)的單向電動(dòng)車(chē)線路，乘坐一次的花費(fèi)為Vi個(gè)桃子

輸出格式

一個(gè)整數(shù)，表示最多能摘到的桃子個(gè)數(shù)。
若個(gè)數(shù)無(wú)限，輸出"Poor boss he"

樣例輸入 1

100?3?5?2?1
1?5
2?3
1?4
5?2?150
2?5?120

樣例輸出 1

250

樣例輸入 2

100?7?10?9?1
1?2
4?5
5?6
5?8
6?8
7?9
8?9
1?3?2
2?3?2
3?4?5
3?5?95
3?6?13
5?7?95
6?7?11
7?8?69
7?10?66

樣例輸出 2

813

提示

2 <= N <= 1000
1 <= M <= 1000
1 <= T <= 1000
1 <= D <= 1,000
1 <= Vi <= 50,000

E數(shù)列

時(shí)間限制 :?10000?MS???空間限制 :?65536?KB

問(wèn)題描述

有X,Y兩個(gè)整數(shù)數(shù)列，現(xiàn)在需要我們用最小的操作次數(shù)，將X數(shù)列轉(zhuǎn)換成與Y相同的數(shù)列。
對(duì)于X數(shù)列，我們有以下三種操作：
1.刪除一個(gè)數(shù)字；
2.插入一個(gè)數(shù)字；
3.將一個(gè)數(shù)字改為另一個(gè)數(shù)字；
請(qǐng)你計(jì)算出完成轉(zhuǎn)換所需的最小操作數(shù)。

輸入格式

第一行，兩個(gè)整數(shù)n和m,分別代表X,Y兩個(gè)數(shù)列的長(zhǎng)度。
第二行，n個(gè)空格間隔的整數(shù)，表示X數(shù)列
第三行，m個(gè)空格間隔的整數(shù)，表示Y數(shù)列

輸出格式

一行，一個(gè)整數(shù)，表示最少所需的操作數(shù)。

樣例輸入 1

7?5
1?2?3?4?5?6?7
8?2?3?8?7

樣例輸出 1

4

樣例輸入 2

8?7
1?8?2?7?6?1?2?6?
2?1?7?8?7?6?8?

樣例輸出 2

6

樣例輸入 3

10?8
1?1?3?3?1?2?2?2?1?1?
1?1?3?3?2?1?3?3?

樣例輸出 3

5

提示

1<=n,m<=2000, 0<=數(shù)列中的數(shù)字<=1000

樣例1說(shuō)明：
第一步：將數(shù)字1修改為8
8 2 3 4 5 6 7
8 2 3 8 7
第二步：將數(shù)字4刪掉
8 2 3 5 6 7
8 2 3 8 7
第三步：將數(shù)字5刪掉
8 2 3 6 7
8 2 3 8 7
第四部：將數(shù)字6修改為8
8 2 3 8 7
8 2 3 8 7

轉(zhuǎn)載于:https://www.cnblogs.com/ghcred/p/8724809.html

總結(jié)

以上是生活随笔為你收集整理的综合-某假期欢乐赛 (Apri, 2018)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。