校內(nèi)訓(xùn)練賽題解

• 人氣估值
• • 解題思路
• 腦力訓(xùn)練計(jì)劃 （模擬 + 字符串）
• • 解題思路
• 大暑賽期（貪心 + 思維）

人氣估值

題目描述
你是某動畫制作公司的企劃部長。如今動畫制作公司制作的東西，已經(jīng)不僅僅局限于動畫本身。相關(guān)商品，例如登場人物的手辦和人物歌曲CD等，也是重要的收益來源。這個收益能提高到什么程度，完全取決于作為企劃部長的你。
這是理所當(dāng)然的，但這些相關(guān)產(chǎn)品并不是隨便推出就可以的。因?yàn)殚_發(fā)商品需要大量的時間和預(yù)算。即使要發(fā)售動畫中登場人物的手辦，也必須限定于銷售額高、人氣高的人物。
衡量角色人氣度的手段之一，就是人氣投票。到目前為止，你也策劃了幾場人氣投票，看來觀眾已經(jīng)逐漸對這個策劃不滿了。當(dāng)務(wù)之急是建立其他衡量受歡迎程度的方法。
所以你提出了一個假設(shè)。一個角色的受歡迎程度，與其在動畫正編中的登場時間的總和成正比。為了驗(yàn)證這個假設(shè)，你決定編寫一個程序來統(tǒng)計(jì)每個角色的出場時間。

輸入
輸入由多個情況組成。每個情況以以下格式給出。

n
name0 m0 d0,0 … d0,m0-1
name1 m1 d1,0 … d1,m1-1
.
.
.
namen-1 mn-1 dn-1,0 … dn-1,mn-1-1
n表示角色的人數(shù)。name
i
?
表示角色的名字。
m
i
?
表示人物出現(xiàn)的時間次數(shù)。m
i
?
后面是m
i
?
個整數(shù)d
i，j
?
。
d
i，j
?
表示人物出現(xiàn)的時間。

輸入的結(jié)尾由n=0的行給出

如果在某一時刻只有一個角色出現(xiàn)在屏幕上，則該角色可以獲得n點(diǎn)。
在同一時間出現(xiàn)的角色每增加一個，在該時間出現(xiàn)的角色所獲得的點(diǎn)數(shù)減少1。
如果有n個角色在同一時間出現(xiàn)，則n個角色分別加1分。
輸入滿足以下條件。
2≤n≤20
0≤m
i
?
≤30
0≤d
i，j
?
<30
第i個字符的d
i,j
?
都不一樣。
name
i
?
只包含大寫或小寫字母，長度不超過10。（小于等于10）

輸出
把點(diǎn)數(shù)最小的角色的點(diǎn)數(shù)和那個名字用一個空白隔開輸出。
如果有多個角色的點(diǎn)數(shù)最小，名字按字典順序選擇最小的人。

解題思路

看清題目。。。。 這題思路很簡單，我們用一個map數(shù)組記錄一下每一個數(shù)字出現(xiàn)的次數(shù)。那么對于第i個人我們在計(jì)算第j天的時候就加上 n - cd[a[j]] + 1 即可

代碼:

#include <iostream> #include <algorithm> #include <cstring> #include <map> #include <string> using namespace std; const int N = 110;int n ; struct node {string name;int a[N], cnt;int pot;bool operator < (const node &w)const {if (pot == w.pot)return name < w.name;return pot < w.pot;} };int main() {while (cin >> n, n) {map<int, int>cd;node p[N];for (int i = 1 ; i <= n ; ++i) {cin >> p[i].name >> p[i].cnt;for (int j = 0 ; j < p[i].cnt; ++j) {cin >> p[i].a[j];cd[p[i].a[j]]++;}}for (int i = 1 ; i <= n ; ++i) {int c = 0 ;for (int j = 0 ; j < p[i].cnt ; ++j) {int x = n - cd[p[i].a[j]];c += ++x;}p[i].pot = c;}sort(p + 1, p + 1 + n);cout << p[1].pot << ' ' << p[1].name << endl;}return 0; }

腦力訓(xùn)練計(jì)劃 （模擬 + 字符串）

題面
她很煩惱。成績不好。雖然她勉強(qiáng)要求父母讓自己上了全寄宿制學(xué)校，但她的才華卻絲毫沒有綻放。也許他本來就沒有天賦，但這是她盡可能不愿意去想的可能。
于是，她依賴在網(wǎng)上找到的詭異腦力訓(xùn)練教材。訓(xùn)練教材上說，通過用手解決類似補(bǔ)充可能性問題的實(shí)例，計(jì)算力得到提高，進(jìn)而邏輯性思考力、直覺力、想象力也變得豐富，社團(tuán)活動也活躍起來，戀愛也順利進(jìn)行。這誘惑著她學(xué)習(xí)這個教材。
根據(jù)教材描述，必須對加法范式表示的邏輯表達(dá)式的各個變量進(jìn)行適當(dāng)分配，判斷邏輯表達(dá)式的值是否可以為真。順便提一下，一個以上的變量（或者，其否定）的邏輯積稱為從句（clause），只有幾個從句的邏輯和表示的邏輯表達(dá)式遵循加法標(biāo)準(zhǔn)形式。一般說到補(bǔ)充可能性問題，邏輯表達(dá)式用乘法標(biāo)準(zhǔn)形來表示，但要注意，訓(xùn)練計(jì)劃是加法標(biāo)準(zhǔn)形態(tài)。
她想研究一下訓(xùn)練計(jì)劃的問題集，然后突然改變了主意。與其花錢買一本習(xí)題，不如請一個擅長編程的好朋友吃一頓凍糕，讓他生成訓(xùn)練計(jì)劃問題，并編寫一個解決問題的程序。這樣豈不是就可以得到很多問題和答案了嗎。就這樣，作為她最好的朋友，請你寫一個解決訓(xùn)練計(jì)劃的程序。

輸入
輸入由多個數(shù)據(jù)組成。每個情況以以下格式給出。

表達(dá)式字符串
輸入的結(jié)尾由“#”組成的行給出
表達(dá)式遵循以下規(guī)則：

::= “(”")" | “(”")|("")"
::= “&”"&"
::= | “~”
::= [a-z]|[A-z]
（在這里，字符串文本用雙引號括了起來。實(shí)際輸入不包含雙引號。）
此外，輸入中沒有多余的空格。
注意，從句由三個字面量組成。
表達(dá)式的長度不得超過500個字符。
測試用例的數(shù)量不超過1100個。

輸出
如果存在使給定表達(dá)式的值為真的變量分配，則輸出yes，否則輸出no。

解題思路

難點(diǎn)一: 讀入的問題: 判斷結(jié)束每一個數(shù)據(jù)的標(biāo)志，我們用pre記錄當(dāng)前字符的前一個字符。如果前一個字符是)而當(dāng)前字符不是|就表明到了數(shù)據(jù)的結(jié)尾，那么就應(yīng)該輸出一個結(jié)果出來。

難點(diǎn)二：判斷表達(dá)式。由于是或運(yùn)算，因此我們記錄在所有的子表達(dá)式中(括號中)如果能會真那么整個結(jié)果就可以為真。那么什么時候子表達(dá)式不能會真呢？就是對于同一個字符它的否和它本身同時存在。(因?yàn)槔ㄌ杻?nèi)是與運(yùn)算)有一個為假就肯定會假。因此我們在一個子表達(dá)式結(jié)束的時候(字符為)）的時候，看如果沒有上面說的情況說明至少有一個為真，那么就滿足條件了。那么如何實(shí)現(xiàn)呢？

我們以一個子表達(dá)式為單位，對于每一個字符統(tǒng)計(jì)其出現(xiàn)的次數(shù)，如果是重復(fù)出現(xiàn)的，那么與第一次的前一個字符進(jìn)行對比。

代碼：

#include <iostream> #include <algorithm> #include <cstring> #include <map> #include <string> using namespace std; const int N = 1e4 + 10; char st[N]; // 記錄子表達(dá)式中同一個字符的第一個前字符int main() {char ch, pre = ' ' ;bool flag = false, key = true;int c = 0;map<char, int>cnt; // 統(tǒng)計(jì)字符出現(xiàn)的次數(shù)while (cin >> ch, pre != '#') {if (pre == ')' && ch != '|') {if (c)cout << "yes" << endl;elsecout << "no" << endl;cnt.clear();c = 0;}if (isalpha(ch)) {if (cnt.count(ch) && (pre == '~' && st[ch] != '~') || (pre != '~' && st[ch] == '~')) {key = false;} else if (cnt.count(ch) == 0)cnt[ch]++, st[ch] = pre;}if (ch == ')') {if (key)c ++;key = true;memset(st, 0, sizeof st);cnt.clear();}pre = ch;}return 0; }

大暑賽期（貪心 + 思維）

題目描述
目前，人們的娛樂僅限于編程競賽。教練一直在征集試題，這些試題分為|Math|Greedy|Geometry|DP|Graph|Other|六類。
好在收集到了很多問題，教練就想多開幾場比賽。比賽由三道題組成，為了讓比賽更具教育意義，教練決定舉辦以下四種比賽。
1、數(shù)學(xué)競賽：Math試題和DP試題共3道題
2、算法游戲大賽：Greedy題和Graph題共3道題
3、實(shí)現(xiàn)游戲競賽：Geometry問題和Other問題共3道題
4、均衡競賽：一套三道題：1道來自Math或DP，1道來自Greedy或Graph，1道來自Geometry或Other

當(dāng)然，在某項(xiàng)比賽中出題的題目是不能在其他比賽中出題的。教練的愿望是舉辦盡可能多的比賽。我們知道6類試題的數(shù)量，那么，最多能開幾次競賽呢？

輸入
輸入由多個情況組成。每個情況以以下格式給出。
n
Math
?
n
Greedy
?
n
Geometry
?
n
DP
?
n
Graph
?
n
Other
?

各輸入值表示各類型問題的庫存數(shù)量。
當(dāng)輸為0 0 0 0 0 0時，表示樣例數(shù)據(jù)結(jié)束。

每個值滿足以下條件
n
Math
?
+n
Greedy
?
+n
Geometry
?
+n
DP
?
+n
Graph
?
+n
Other
?
≤10
8

此外，測試用例的數(shù)量不超過20,000個。

輸出
在一行中輸出可能的最大競賽數(shù)。

解題思路：

對于兩種方法。我們發(fā)現(xiàn)0與3,1與4和2與5 是可以合在一起看的(數(shù)據(jù)從下標(biāo)0開始算的話)

合并完，那么對于這三個數(shù)，我們有兩種方式，一個是前各自除以3，然后再進(jìn)行另一種方式，一組挑一個數(shù)。對于這個方法，在經(jīng)過n多次的找規(guī)律的時候，發(fā)現(xiàn)：如果這三個數(shù)有兩個數(shù)能整除3，另外一個數(shù)求余三的結(jié)果<= 1那么使用這個方法是最優(yōu)的。如6 4 6如果我們先減去最小值。那么變?yōu)? 0 2那么最終次數(shù)就是4 ，不過如果我們先除以3，變?yōu)? 1 0結(jié)果是5.之所以另外一個數(shù)余3結(jié)果是<= 1是因?yàn)槿绻?的話，肯定是先除以三，對于余1這個很關(guān)鍵，這個1的作用是好比上面的例子減去4后變?yōu)? 0 2那么如果我們返回一次，每個數(shù)都加上1變?yōu)? 1 3那么兩個三各自除以3，就從1次變成了兩次。明顯更優(yōu)。

對于另外一種方式。先減去最小值，再各次除以三。提供剩余的有出現(xiàn)2 0 2的情況我們就用類似上面的方式回一次。加上一。（這個的條件是減去的最小值不能是0）如2 0 2

代碼：

#include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int N = 1e6 + 10; LL a[7];int main() {while (cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5], a[0] || a[4] || a[1] || a[2] || a[3] || a[5] ) {LL res = 0;LL n1 = a[0] + a[3], n2 = a[1] + a[4], n3 = a[2] + a[5];LL minx = min(n1, min(n2, n3));if ((n1 % 3 == 0 && (n2 % 3 ) <= 1 && n3 % 3 == 0) || (n2 % 3 == 0 && (n1 % 3 ) && n3 % 3 == 0) || (n1 % 3 == 0&& (n3 % 3 ) <= 1 && n2 % 3 == 0) ) {res += n1 / 3 + n2 / 3 + n3 / 3;n1 %= 3, n2 %= 3, n3 %= 3;while (n1 && n2 && n3) {res ++ ;n1 --, n2--, n3--;}} else {bool flag = true;if (minx == 0)flag = false;res += minx;n1 -= minx, n2 -= minx, n3 -= minx;res += n1 / 3 + n2 / 3 + n3 / 3;n1 %= 3, n2 %= 3, n3 %= 3;if (flag && ((n1 == 2 && n2 == 2) || (n1 == 2 && n3 == 2) || (n2 == 2 && n3 == 2)))res ++;}cout << res << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的校内训练赛题解第三篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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