?

假期歡樂賽，確實挺輕松的，被逼迫寫了題解。

A.推數
按列觀察，有的列有多個格子，看起來好復雜啊，先放一放。
按行觀察，黑色格子在 i 行 j 列：
當 i 是奇數，對應數字第 i 位是 j-1
當 i 是偶數，對應數字第 i 位是 9-j

B.體重
某位同學不是中間體重的充要條件是，比他重的人數 >= mid 或 比他輕的人數 >= mid
x 比 y 重，則 x, y 有單向連通關系，G[x][y] = true 。比 y 重的人數就是滿足 G[i][y] = true 的 i 的數量。
比 y 輕的人數類似。
用 Floyd 跑一遍，再統計一下就好啦。

C.采蘑菇
觀察一下是一道動規，狀態是這個：f[t][i] 時間 t 時在 i 位置能采摘的最大蘑菇數量。
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]...)，可以加一個滾動數組。

D.摘桃子
每棵樹都有桃子就是說，只要走過一條小路就可以獲得 D 個桃子，這樣權值就從 點 上變到了 邊 上，考慮一下圖論。
電動車線路等價于獲得 D-V 個桃子。建圖，求從 S 出發的最長路即可。
能夠摘到無限桃子的情況就是圖中存在“正權回路”的情況，即有某個點在 SPFA 過程中的入隊次數 > 總點數。不知道是不是這么叫，就是 SPFA 里面的負權回路那種東西……

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

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推數

時間限制 :?10000?MS???空間限制 :?65536?KB

問題描述

　　　何老板在玩一個推理游戲，但他遇到了一點麻煩，需要你幫忙！請根據A,B兩幅圖，推導出C圖代表的數字！

輸入格式

一個由大寫字母'B'和'W'構成的10*10的矩陣，表示圖C，
其中'B'表示黑色方塊，'W'白色方塊

輸出格式

一行，一個數字，表示推導出的C代表的數字。

樣例輸入

BWWWWWWWWW
WWWWWWBWWW
WWWWBWWWWW
BWWWWWWWWW
WWWBWWWWWW
WWWWWWWWBW
WWWWBWWWWW
WWBWWWWWWW
WWWWWBWWWW
WWWWWWWBWW

樣例輸出

034931

?

B體重

時間限制 :?10000?MS???空間限制 :?65536?KB

問題描述

近日，信競班有人在散布謠言，說何老板體重超重，這有損何老板在同學們心中的完美形象，讓何老板很是頭疼。何老板還了解到，散布該謠言的人號稱自己擁有最合適的體重，體重值位于所有人的正中間，何老板決心找出這個家伙。

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

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

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

????1號同學比2號同學輕

????3號同學比4號同學輕　　

????1號同學比5號同學輕　　

????2號同學比4號同學輕　　

根據上面的情報，雖然何老板不能準確得出哪個同學具有中間體重，但他可以肯定4號和1號不可能具有中間體重，因為，1、2、3比4輕，而2、4、5比1重，所以他可以排除到這兩名同學。

寫一個程序統計出目前我們最多能排除掉多少個同學。也就是確定有多少個同學肯定不會是中間體重。

輸入格式

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

接下來的m行,每行兩個整數x和y，表示x號同學比y號同學重。

輸出格式

若干個整數，按從小到大的順序輸出不可能是中間重量的學生的編號。
若一個也找不出來，輸出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采蘑菇

時間限制 :?10000?MS???空間限制 :?65536?KB

問題描述

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

輸入格式

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

輸出格式

一行，一個整數，表示能夠采摘到的最多蘑菇數。

樣例輸入

樣例輸入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

提示

對于30%的數據 1<=n<=10, 1<=t<=5;
對于100%的數據 1<=n<=100, 1<=t<=1000 ，1<=每塊磚上長出的蘑菇數<=10000

樣例1說明：
第一秒由2號磚移動到1號磚，采3顆蘑菇
第二秒呆在1號磚不動，采2顆蘑菇
第三秒由1號磚移動到2號磚，采5顆蘑菇

?

D摘桃子

時間限制 :?-?MS???空間限制 :?165536?KB? 評測說明 :?1s

問題描述

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

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

輸入格式

第一行，5個整數，分別是D,M,N,T,S
接下來M行，每行兩個整數Ai和Bi，表示從Ai號桃樹到第Bi號桃樹有條單向小路
接下來T行，每行三個空格間隔的整數Xi,Yi,Vi,表示有一條從Xi號桃樹到Yi號桃樹的單向電動車線路，乘坐一次的花費為Vi個桃子

輸出格式

一個整數，表示最多能摘到的桃子個數。
若個數無限，輸出"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數列

時間限制 :?10000?MS???空間限制 :?65536?KB

問題描述

有X,Y兩個整數數列，現在需要我們用最小的操作次數，將X數列轉換成與Y相同的數列。
對于X數列，我們有以下三種操作：
1.刪除一個數字；
2.插入一個數字；
3.將一個數字改為另一個數字；
請你計算出完成轉換所需的最小操作數。

輸入格式

第一行，兩個整數n和m,分別代表X,Y兩個數列的長度。
第二行，n個空格間隔的整數，表示X數列
第三行，m個空格間隔的整數，表示Y數列

輸出格式

一行，一個整數，表示最少所需的操作數。

樣例輸入 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<=數列中的數字<=1000

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

轉載于:https://www.cnblogs.com/ghcred/p/8724809.html

總結

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

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