第五届合肥工业大学宣城校区程序设计大赛题解
生活随笔
收集整理的這篇文章主要介紹了
第五届合肥工业大学宣城校区程序设计大赛题解
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
問(wèn)題 A: 小問(wèn)題
時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB??Special Judge?
題目描述
林喵喵特別喜歡解決女孩子們提出的問(wèn)題.?
于是, 有一天殷老師問(wèn)了林喵喵一個(gè)小問(wèn)題. 給出一個(gè)非空有限集合A, 其中包含元素若干, 給出一個(gè)元素p, 輸出集合A的非空子集且元素p不屬于那個(gè)子集.(即要求是A的非空子集并其中不存在元素p,輸出所以符合要求的集合) 元素皆為整數(shù),且 <=231-1?
輸入
第一行T表示測(cè)試組數(shù)
第二行有一個(gè)數(shù)N, 表示集合A內(nèi)元素的數(shù)量 Card(A) N≤20
第三行有N個(gè)集合A的元素,以空格分隔
第四行有一個(gè)A的元素p
?
輸出
?
為了降低難度, 你只需要輸出每個(gè)集合內(nèi)數(shù)字的數(shù)量與總和, ?總和小于231-1
每個(gè)輸出的集合占用一行
每行兩個(gè)數(shù)字, 第一個(gè)數(shù)表示非空集合元素的數(shù)量, 第二個(gè)數(shù)表示非空集合元素的總和
集合之間的順序可隨意調(diào)整
?
?
樣例輸入
1 5 1 2 3 4 5 3樣例輸出
1 1 1 2 2 3 1 4 2 5 2 6 3 7 1 5 2 6 2 7 3 8 2 9 3 10 3 11 4 12水題之一。你可以用dfs搜索每一個(gè)位置的情況，或者用二進(jìn)制模擬。聰明的做法是把要剔除的元素剔除掉，再輸出所有可能情況。我當(dāng)初沒(méi)寫(xiě)剔除的做法就判斷了，時(shí)間復(fù)雜度較高。 二進(jìn)制模擬代碼：
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(0)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e2+10; 8 LL val[N]; 9 int T,n,m,h,p,ct,t; 10 LL sum; 11 int main() 12 { 13 scanf("%d",&T); 14 while(T--) 15 { 16 scanf("%d",&n); 17 for(int i=1;i<=n;i++) 18 scanf("%lld",&val[i]); 19 m=(1<<n)-1; 20 scanf("%d",&p); 21 for(int i=1;i<=n;i++) 22 if(p==val[i]) 23 { 24 p=i; 25 break; 26 } 27 for(int i=1;i<=m;i++) 28 if(((i>>(p-1))&1)==0) 29 { 30 ct=0; 31 t=0; 32 sum=0; 33 h=i; 34 while(h) 35 { 36 t++; 37 if(h&1) 38 { 39 sum+=val[t]; 40 ct++; 41 } 42 h>>=1; 43 } 44 printf("%d %lld\n",ct,sum); 45 } 46 } 47 return 0; 48 } 49View Code
?
問(wèn)題 B: 統(tǒng)計(jì)詞頻
時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB提交:?359??解決:?22
?
題目描述
給出一段英文文字, 統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的次數(shù)(忽略大小寫(xiě))
單詞字母范圍為( a~z 或 A~Z ),沒(méi)有奇怪的字符
?
輸入
第一行組數(shù)T
第二行單詞數(shù)N (N<=10000)
后面N行有N個(gè)非空的單詞
?
輸出
輸出小寫(xiě)單詞和數(shù)量,單詞按照字典序排序輸出
一個(gè)單詞占一行
?
樣例輸入
1 4 hello world hello icpc樣例輸出
hello 2 icpc 1 world 1水題之二。寫(xiě)個(gè)map對(duì)每個(gè)string進(jìn)行映射，然后用迭代器從頭到尾輸出就好了。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(0)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e5+10; 8 int T,n,m,h,p,ct,t; 9 string s; 10 map<string,LL>::iterator it; 11 int main() 12 { 13 scanf("%d",&T); 14 while(T--) 15 { 16 scanf("%d",&n); 17 map<string,LL> num; 18 for(int i=1;i<=n;i++) 19 { 20 cin>>s; 21 for(int j=0;j<s.size();j++) 22 s[j]=tolower(s[j]); 23 num[s]++; 24 } 25 for(it=num.begin();it!=num.end();it++) 26 printf("%s %lld\n",(it->first).c_str(),it->second); 27 } 28 return 0; 29 }View Code
?
問(wèn)題 C: 機(jī)房問(wèn)題
時(shí)間限制:?2 Sec??內(nèi)存限制:?128 MB提交:?214??解決:?18
?
題目描述
在你們寫(xiě)題的時(shí)候,萌萌的林喵喵同學(xué)其實(shí)在暗中觀察你們(Big Miao is watching you!)
其中觀察的一項(xiàng)就是要統(tǒng)計(jì)出一段時(shí)間內(nèi)哪個(gè)時(shí)刻上機(jī)人數(shù)最多。
你能否比林喵喵更快地統(tǒng)計(jì)出來(lái)呢？
?
輸入
T表示組數(shù)
N表示數(shù)據(jù)數(shù)量
接下來(lái)N行每行三個(gè)整數(shù)t1,t2,n
表示n個(gè)學(xué)生在t1到t2使用了機(jī)房電腦(包含t1,t2)
0<t1<t2<=10000000
0<n<=10000000
?
輸出
輸出一個(gè)時(shí)間t, 這個(gè)時(shí)刻上機(jī)人數(shù)最多
若有多個(gè)最大值則輸出最小的t
?
樣例輸入
1 3 1 2 1 1 3 1 2 5 2樣例輸出
2?
水題之三。數(shù)據(jù)范圍給的這么大，一看就不能瞎暴力。 我們只需要遍歷訪問(wèn)過(guò)的時(shí)間點(diǎn)就行了。這相當(dāng)于一個(gè)離散化的過(guò)程。 那么這個(gè)東西可以用map來(lái)快速存儲(chǔ)，因?yàn)閙ap是有序的。而不用寫(xiě)離散化代碼（雖然也是兩行的事）。這個(gè)看看輸入范圍nlogn一看就知道不會(huì)超時(shí)啦。 然后對(duì)于k人在一段時(shí)間[l,r]上機(jī),在l點(diǎn)+k，r+1點(diǎn)-k。求一個(gè)前綴和，就能得出所有時(shí)間的上機(jī)人數(shù)了。 而相同人數(shù)的最靠前的時(shí)間也是在這些點(diǎn)中產(chǎn)生的。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(0)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e5+10; 8 int T,n,h,p,ct; 9 LL t1,t2,m,sum,maxn,pt; 10 string s; 11 map<LL,LL>::iterator it; 12 int main() 13 { 14 scanf("%d",&T); 15 while(T--) 16 { 17 scanf("%d",&n); 18 map<LL,LL> num; 19 for(int i=1;i<=n;i++) 20 { 21 scanf("%lld%lld%lld",&t1,&t2,&m); 22 num[t1]+=m; 23 num[t2+1]-=m; 24 } 25 num[0]=0; 26 maxn=0; 27 pt=0; 28 sum=0; 29 for(it=num.begin();it!=num.end();it++) 30 { 31 sum+=it->second; 32 if(sum>maxn) 33 { 34 maxn=sum; 35 pt=it->first; 36 } 37 } 38 printf("%lld\n",pt); 39 } 40 return 0; 41 }View Code
?
問(wèn)題 D: 帥寶寶的xor
時(shí)間限制:?2 Sec??內(nèi)存限制:?128 MB提交:?43??解決:?10
?
題目描述
眾所周知，帥寶寶精通圖論。這一天他剛學(xué)習(xí)了一個(gè)新操作-異或（^）。這時(shí)候林喵喵給他出了一道異或題： 起初林喵喵給出了一些數(shù)字，這些數(shù)字均不超過(guò)109。 然后林喵喵有以下兩種操作： 1 x:在這些數(shù)中加入數(shù)字x。 2 x:從所有數(shù)中找出一個(gè)數(shù)字y，使得x^y最大，并輸出這個(gè)y的值。 帥寶寶頓時(shí)感到為難，你能幫帥寶寶解決這個(gè)問(wèn)題嗎？?
輸入
多組數(shù)據(jù)(1≤T≤10)，對(duì)于每組數(shù)據(jù)： 第一行有一個(gè)整數(shù)n（0≤n≤105），代表起初的數(shù)字個(gè)數(shù)。 第二行包含n個(gè)整數(shù)ai（0≤ai≤109)，即起初給出的數(shù)字個(gè)數(shù)。 第三行有一個(gè)整數(shù)q（0≤q≤105）,代表接下來(lái)的操作個(gè)數(shù)。 第3+i行的格式如題，其中0≤x≤109。 所有n+q≤2×105。?
輸出
對(duì)于每個(gè)2操作輸出對(duì)應(yīng)的y。 每組數(shù)據(jù)后空一行。?
樣例輸入
3 1 2 3 5 2 1024 1 100 2 1021 2 1022 2 1024樣例輸出
3 2 1 100?
01型字典樹(shù)模板題。
寫(xiě)過(guò)字典樹(shù)的應(yīng)該都會(huì)，稍難題。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e5+10; 8 struct Node 9 { 10 int next[2]; 11 }; 12 struct Trie 13 { 14 Node node[N*33]; 15 int cnt; 16 void init() 17 { 18 cnt=0; 19 clr_1(node); 20 } 21 void add(LL x) 22 { 23 int t,u=0; 24 for(int i=31;i>=0;i--) 25 { 26 t=(x>>i)&1; 27 if(node[u].next[t]==-1) 28 { 29 node[u].next[t]=++cnt; 30 } 31 u=node[u].next[t]; 32 } 33 return ; 34 } 35 LL query(LL x) 36 { 37 int t,u=0; 38 LL ans=0; 39 for(int i=31;i>=0;i--) 40 { 41 t=(x>>i)&1; 42 ans<<=1; 43 if(node[u].next[t^1]==-1) 44 { 45 ans|=t; 46 u=node[u].next[t]; 47 } 48 else 49 { 50 ans|=(t^1); 51 u=node[u].next[(t^1)]; 52 } 53 } 54 return ans; 55 } 56 }trie; 57 int n,m,k,t,q; 58 int main() 59 { 60 while(scanf("%d",&n)!=EOF) 61 { 62 trie.init(); 63 for(int i=1;i<=n;i++) 64 { 65 scanf("%d",&k); 66 trie.add((LL)k); 67 } 68 scanf("%d",&q); 69 for(int i=1;i<=q;i++) 70 { 71 scanf("%d%d",&t,&k); 72 if(t==1) 73 trie.add((LL)k); 74 else 75 printf("%lld\n",trie.query((LL)k)); 76 } 77 printf("\n"); 78 } 79 return 0; 80 }View Code
?
問(wèn)題 E: N馬問(wèn)題
時(shí)間限制:?2 Sec??內(nèi)存限制:?128 MB提交:?23??解決:?4
?
題目描述
林喵喵和冬冬下象棋的時(shí)候突然異想天開(kāi),由N數(shù)碼問(wèn)題想出了一個(gè)N馬問(wèn)題 給出一個(gè)n*m的棋盤(pán), 請(qǐng)問(wèn)至多能放多少個(gè)馬并使他們無(wú)法互相攻擊到對(duì)方 馬可以攻擊的地方為所在的坐標(biāo)橫著走一步,豎著走兩步,或者橫著走兩步,豎著走兩步 不考慮象棋中馬被絆到不能走的規(guī)則,即任意馬可以走到八個(gè)地方(只要那個(gè)地方在棋盤(pán)內(nèi))?
輸入
多組數(shù)據(jù),請(qǐng)使用讀取多組數(shù)據(jù)的寫(xiě)法
接下來(lái)有若干行,每組數(shù)據(jù)有一行,m和n,表示棋盤(pán)是m行n列的,1<=n,m<=1000
?
輸出
輸出一個(gè)數(shù)字,表示m*n棋盤(pán)最多擺放馬的數(shù)量
?
樣例輸入
1 1 5 5 2 3 4 7樣例輸出
1 13 4 14找規(guī)律題。中等難度題。怎樣擺馬數(shù)量最多？很容易發(fā)現(xiàn)一個(gè)大棋盤(pán)上從左上角擺起，按照2*2放馬，2*2不放馬，2*2放馬.....即（1,1）~（2,2）這個(gè)正方形放馬，然后其他無(wú)論往下還是往右每隔2*2個(gè)格子放2*2的馬，這樣的情況馬是最多的。數(shù)量為（n*m+1）/2。然而你會(huì)發(fā)現(xiàn)只有1行和2行的時(shí)候（或1列和2列）的時(shí)候情況是特殊的，因?yàn)樗麄冏疃嘁恍姓叫位蛞涣姓叫?#xff0c;沒(méi)有和下一列（下一行）共享跳躍到達(dá)點(diǎn)。這樣的情況需要特殊判斷輸出相應(yīng)的答案。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int solve(int n, int m) { 6 if (n < m) return solve(m, n); 7 else if (m==1) return n; 8 else if (m==2) { 9 return (n/4)*4+((n%4>1)?2:n%4)*2; 10 } 11 else return (n*m+1)/2; 12 } 13 14 int main() { 15 16 int r,c; 17 while (scanf("%d%d", &r, &c)!=EOF) { 18 printf("%d\n", solve(r, c)); 19 } 20 return 0; 21 }View Code
?
問(wèn)題 F: xor game
時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB提交:?26??解決:?7
?
題目描述
帥寶寶覺(jué)得你們太菜啦，于是帥寶寶用他熟悉的xor操作發(fā)明了一個(gè)簡(jiǎn)單的游戲讓你們簽到，不要辜負(fù)他的期望啊。 游戲雙方寫(xiě)出他們各自長(zhǎng)度為n由互不相同的數(shù)字組成的序列(A方）x1,x2,x3……xn和（B方）y1,y2,y3……yn。然后雙方同時(shí)亮出他們寫(xiě)下的數(shù)字序列。如果所有這2n個(gè)數(shù)字中有相同的數(shù)字，則兩人進(jìn)行多次以上步驟，直到這2n個(gè)數(shù)字中的數(shù)字互不相同。這時(shí)的數(shù)字序列才是游戲所需要的數(shù)字序列。 將調(diào)整過(guò)后的x序列和y序列陳列出來(lái)。計(jì)算其中滿足條件的數(shù)字對(duì)(i,j)(1≤i,j≤n)的對(duì)數(shù)。其條件為：計(jì)算xi^yj=num后，若num是這2n個(gè)數(shù)中的一個(gè)，則滿足條件。 若這樣的數(shù)字對(duì)數(shù)為偶數(shù)則游戲A方贏，否則B方贏。 現(xiàn)在帥寶寶充當(dāng)游戲B方，林喵喵充當(dāng)游戲A方，請(qǐng)你確定在一盤(pán)xor游戲中誰(shuí)會(huì)獲勝。?
輸入
多組數(shù)據(jù)(1≤T≤10)，對(duì)于每組數(shù)據(jù)： 第一行有一個(gè)整數(shù)n（1≤n≤105），代表數(shù)字序列數(shù)字個(gè)數(shù)。 第二行含n個(gè)整數(shù)xi（1≤xi≤1017）。 第三行含n個(gè)整數(shù)yi（1≤yi≤1017）。 保證以上x(chóng)i和yi這2n個(gè)數(shù)字互不相等。?
輸出
若帥寶寶獲勝輸出"shuaibaobao"否則輸出"linmiaomiao"。
?
樣例輸入
3 10 233 322 1234567 7654321 12345678987654321 987654321 23 1 9 10 2 3 4 5 6 7 8 11 12 34 5 1 2 3 4 5 6 7 8 9 10 2 101 10 111 5樣例輸出
linmiaomiao linmiaomiao linmiaomiao提示
?
?xor自反性，b^a^b=a。
?
?
cf上的題，稍難的思維題吧。（畢竟已經(jīng)寫(xiě)了提示了）。
只不過(guò)我把范圍改大了，防止你們瞎暴力23333。
首先兩個(gè)數(shù)列內(nèi)的數(shù)都完全不相同。那么任意兩個(gè)數(shù)異或的結(jié)果數(shù)列內(nèi)最多只有一個(gè)數(shù)是對(duì)應(yīng)的。
然后考慮異或的自反性。
如果我們xi^yj==ci（c表示x、y中任意一個(gè)數(shù)列），那么肯定有xi^ci==yj或者yj^ci==xi。這取決于c是哪個(gè)數(shù)列。
因此這樣的數(shù)對(duì)是成對(duì)出現(xiàn)的，有偶數(shù)個(gè)。linmiaomiao一定贏。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e5+10; 8 int n,m,k,t,q,T; 9 LL x[N],y[N]; 10 int main() 11 { 12 // freopen("10.in","r",stdin); 13 // freopen("10.out","w",stdout); 14 scanf("%d",&T); 15 while(T--) 16 { 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++) 19 scanf("%lld",&x[i]); 20 for(int i=1;i<=n;i++) 21 scanf("%lld",&y[i]); 22 printf("linmiaomiao\n"); 23 } 24 return 0; 25 } 26View Code
?
問(wèn)題G: 旺財(cái)?shù)募]策略
時(shí)間限制:?2 Sec??內(nèi)存限制:?128 MB提交:?53??解決:?3
?
題目描述
倉(cāng)鼠旺財(cái)有N種不同面值的郵票(如:1 分,3 分)，每種郵票都有無(wú)限多張。現(xiàn)在旺財(cái)想給林喵喵寄信，郵局提供的信封最大只能貼K張郵票。現(xiàn)在旺財(cái)想知道它能夠從1到M最大可連續(xù)貼出的郵資是多少。 例如:假設(shè)旺財(cái)有1分和3分兩種郵票;郵局的信封最多可以貼5張郵票。很容易貼出1到5分的郵資(用1分郵票貼就行了)接下來(lái)的郵資也不難： 6 = 3 + 3? 7 = 3 + 3 + 1? 8 = 3 + 3 + 1 + 1? 9 = 3 + 3 + 3? 10 = 3 + 3 + 3 + 1? 11 = 3 + 3 + 3 + 1 + 1? 12 = 3 + 3 + 3 + 3? 13 = 3 + 3 + 3 + 3 + 1 然而，無(wú)論如何讓5枚1分或者3分的郵票組合，根本不可能貼出14分的郵資。因此，對(duì)于這兩種不同面值的郵票在最大可以張貼5張的情況下，我們可以最大連續(xù)貼出的郵資就是13。 Note:因?yàn)?4貼不出來(lái),所以最高上限是13而不是15。 我們相信聰明的你一定可以幫助旺財(cái)解決問(wèn)題?
輸入
第1行: 兩個(gè)整數(shù)，K和N，分別表示最大可以張貼的郵票數(shù)量和不同面值的郵票種數(shù)。其中K(1 <= K <= 200)，N（1 <= N <= 50) 第 2 行：? N個(gè)整數(shù)，分別表示N個(gè)不同郵票的面值，每張郵票的面值不超過(guò)10000。?
輸出
? ? ? ?一個(gè)整數(shù)，表示在不超過(guò)K張郵票的情況下從1分開(kāi)始能夠最大連續(xù)可貼出的郵資是多少。
?
樣例輸入
5 2 1 3樣例輸出
13背包經(jīng)典問(wèn)題。開(kāi)場(chǎng)那兩個(gè)人太兇殘了直接過(guò)了。。。 稍難題。
1 //wanghan's code 2 #include "iostream" 3 #include "cstdio" 4 #include "cstring" 5 #include "string" 6 using namespace std; 7 const int maxn=2e6+100; 8 const int INF=1<<30; 9 int K,n; 10 int dp[maxn],v[100]; 11 int main() 12 { 13 cin>>K>>n; 14 int ans=0; 15 for(int i=1;i<=n;i++){ 16 cin>>v[i]; 17 ans=max(ans,v[i]); 18 } 19 int m=2e6; 20 for(int i=1;i<=m;i++) 21 dp[i]=INF; 22 for(int i=1;i<=n;i++){ 23 for(int j=v[i];j<=m;j++){ 24 dp[j]=min(dp[j],dp[j-v[i]]+1); 25 } 26 } 27 int res=1; 28 for(int i=1;i<=m;i++){ 29 if(dp[i]>K){ 30 res=i; break; 31 } 32 } 33 cout<<res-1<<endl; 34 }View Code
?
問(wèn)題 H: 網(wǎng)絡(luò)收費(fèi)
時(shí)間限制:?1 Sec??內(nèi)存限制:?64 MB提交:?30??解決:?3
題目描述
網(wǎng)絡(luò)已經(jīng)成為當(dāng)今世界不可或缺的一部分。每天都有數(shù)以億計(jì)的人使用網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)、科研、娛樂(lè)等活動(dòng)。然而，不可忽視的一點(diǎn)就是網(wǎng)絡(luò)本身有著龐大的運(yùn)行費(fèi)用。所以，向使用網(wǎng)絡(luò)的人進(jìn)行適當(dāng)?shù)氖召M(fèi)是必須的，也是合理的。 假設(shè)有這樣一個(gè)網(wǎng)絡(luò)：網(wǎng)絡(luò)中的用戶一共有2N個(gè)，編號(hào)依次為1, 2, 3, …, 2N。這些用戶之間是用路由點(diǎn)和網(wǎng)線組成的。用戶、路由點(diǎn)與網(wǎng)線共同構(gòu)成一個(gè)滿二叉樹(shù)結(jié)構(gòu)。樹(shù)中的每一個(gè)葉子結(jié)點(diǎn)都是一個(gè)用戶，每一個(gè)非葉子結(jié)點(diǎn)（灰色）都是一個(gè)路由點(diǎn)，而每一條邊都是一條網(wǎng)線。 而網(wǎng)絡(luò)公司對(duì)應(yīng)該網(wǎng)絡(luò)的收費(fèi)方式比較奇特，稱為“配對(duì)收費(fèi)”。即對(duì)于每?jī)蓚€(gè)用戶i, j (1≤i < j ≤2N?) 進(jìn)行收費(fèi)。 由于用戶可以自行選擇兩種付費(fèi)方式A、B中的一種，所以網(wǎng)絡(luò)公司向?qū)W校收取的費(fèi)用與每一位用戶的付費(fèi)方式有關(guān)。該費(fèi)用等于每?jī)晌徊煌脩襞鋵?duì)產(chǎn)生費(fèi)用之和。 為了描述方便，首先定義這棵網(wǎng)絡(luò)樹(shù)上的一些概念： 祖先：根結(jié)點(diǎn)沒(méi)有祖先，非根結(jié)點(diǎn)的祖先包括它的父親以及它的父親的祖先； 管轄葉結(jié)點(diǎn)：葉結(jié)點(diǎn)本身不管轄任何葉結(jié)點(diǎn)，非葉結(jié)點(diǎn)管轄它的左兒子所管轄的葉結(jié)點(diǎn)與它的右兒子所管轄的葉結(jié)點(diǎn)； 距離：在樹(shù)上連接兩個(gè)點(diǎn)之間的用邊最少的路徑所含的邊數(shù)。 對(duì)于任兩個(gè)用戶i, j (1≤i)： 如果他們最近公共祖先下選擇A的人數(shù)大于B的人數(shù)，那么只對(duì)選擇A的用戶收費(fèi)，費(fèi)用為Fi，j(即兩人中選擇A的有k人，則兩人配對(duì)收費(fèi)為k*Fi,j)，否則只對(duì)選擇B的用戶收費(fèi)，費(fèi)用仍為Fi，j。 由于最終所付費(fèi)用與付費(fèi)方式有關(guān)，所以用戶們希望能夠自行改變自己的付費(fèi)方式以減少總付費(fèi)（所有人的付費(fèi)和）。然而，由于網(wǎng)絡(luò)公司已經(jīng)將每個(gè)用戶注冊(cè)時(shí)所選擇的付費(fèi)方式記錄在案，所以對(duì)于用戶i，如果他/她想改變付費(fèi)方式（由A改為B或由B改為A），就必須支付Ci元給網(wǎng)絡(luò)公司以修改檔案（修改付費(fèi)方式記錄）。 現(xiàn)在的問(wèn)題是，給定每個(gè)用戶注冊(cè)時(shí)所選擇的付費(fèi)方式以及Ci，試求這些用戶應(yīng)該如何選擇自己的付費(fèi)方式以使得在支付給網(wǎng)絡(luò)公司的總費(fèi)用最少（更改付費(fèi)方式費(fèi)用+配對(duì)收費(fèi)的費(fèi)用）。 注：配對(duì)收費(fèi)并不是說(shuō)對(duì)i結(jié)點(diǎn)只選擇一個(gè)結(jié)點(diǎn)與其配對(duì)收費(fèi)，而是對(duì)i和所有其他結(jié)點(diǎn)都進(jìn)行配對(duì)收費(fèi)。?
輸入
輸入第一行有一個(gè)正整數(shù)N。 第二行有2N個(gè)整數(shù)，依次表示1號(hào)，2號(hào)，…，2N號(hào)用戶注冊(cè)時(shí)的付費(fèi)方式，每一個(gè)數(shù)字若為0，則表示對(duì)應(yīng)用戶的初始付費(fèi)方式為A，否則該數(shù)字為1，表示付費(fèi)方式為B。 第三行有2N個(gè)整數(shù)，表示每一個(gè)用戶修改付費(fèi)方式需要支付的費(fèi)用，依次為C1, C2, …,CM?。( M=2N?) 以下2N-1行描述給定的兩兩用戶之間的流量表F，總第(i + 3)行第j列的整數(shù)為Fi, j+i?。（1≤ i < 2N，1 ≤ j ≤ 2N-i） 所有變量的含義可以參見(jiàn)題目描述。N≤10，0≤Fi, j≤500，0≤Ci≤500 000?
輸出
你的程序只需要向輸出文件輸出一個(gè)整數(shù)，表示支付給網(wǎng)絡(luò)公司的最小總費(fèi)用。（單位：元）
?
樣例輸入
2 1 0 1 0 2 2 10 9 10 1 2 2 1 3樣例輸出
8noi2006的原題，某位陳瑜希的論文題。詳見(jiàn)我樹(shù)形dp系列題解。 一道樹(shù)上背包，也可以多叉轉(zhuǎn)二叉去做。 陳瑜希《多角度思考 創(chuàng)造型思維》。 防ak題，高難度題。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define clrmax(x) memset(x,0x3f3f3f3f,sizeof(x)) 5 #define mod 1000000007 6 #define LL long long 7 using namespace std; 8 const int maxN=5e3+10; 9 int f[maxN][maxN]; 10 int flow[maxN][maxN]; 11 int c[maxN]; 12 int cost[maxN][20],fa[maxN][20]; 13 bool chose[maxN]; 14 int N,n,m,k,ans,p; 15 int dfs(int u,int dep,int sta)//sta前從右往左第dep+1位開(kāi)始是該結(jié)點(diǎn)分配的B方式的數(shù)量，1~dep位為其祖先結(jié)點(diǎn)na和nb的大小相對(duì)關(guān)系，表現(xiàn)為B收費(fèi)為1，A收費(fèi)為0。 16 { 17 if(f[u][sta]!=0x3f3f3f3f) return f[u][sta]; 18 int num=sta>>dep; 19 int fasta=sta^(num<<dep); 20 //該結(jié)點(diǎn)的收費(fèi)選擇chos 21 int chos=(1<<(N-dep))-num>=num?1:0; 22 //葉子結(jié)點(diǎn)處理返回 23 if(dep==N) 24 { 25 int v=u-(n-1); 26 fasta<<=1; 27 fasta|=chos; 28 if(num^chose[v]) 29 f[u][sta]=c[v]; 30 else 31 f[u][sta]=0; 32 for(int i=N;i>=0;i--) 33 { 34 if(!((fasta&1)^num)) 35 f[u][sta]+=cost[v][i]; 36 fasta>>=1; 37 } 38 return f[u][sta]; 39 } 40 //約束左右結(jié)點(diǎn)取B的數(shù)量在合理范圍內(nèi)，并選擇其中最小的一個(gè)和。 41 int minx=max(0,num-(1<<N-dep-1)); 42 int maxx=min(num,1<<N-dep-1); 43 for(int i=minx;i<=maxx;i++) 44 f[u][sta]=min(dfs(u<<1,dep+1,(i<<dep+1)|(fasta<<1|chos))+dfs(u<<1|1,dep+1,(num-i<<dep+1)|(fasta<<1|chos)),f[u][sta]); 45 return f[u][sta]; 46 } 47 int main() 48 { 49 scanf("%d",&N); 50 n=1<<N; 51 for(int i=1;i<=n;i++) 52 { 53 scanf("%d",&p); 54 chose[i]=p; 55 } 56 for(int i=1;i<=n;i++) 57 scanf("%d",&c[i]); 58 for(int i=1;i<=n;i++) 59 for(int j=i+1;j<=n;j++) 60 scanf("%d",&flow[i][j]); 61 //計(jì)算子結(jié)點(diǎn)i（樹(shù)上編號(hào)為i+n-1)在深度為j的祖先 62 for(int i=1;i<=n;i++) 63 { 64 k=i+n-1; 65 for(int j=N;j>=0;j--) 66 { 67 fa[i][j]=k; 68 k>>=1; 69 } 70 } 71 clr(cost); 72 //若i，j在深度為k處祖先相同，那末將流量費(fèi)用flow[i,j]加到i和j在深度k所需要的費(fèi)用中。 73 for(int i=1;i<=n;i++) 74 for(int j=i+1;j<=n;j++) 75 for(int k=N;k>=0;k--) 76 if(fa[i][k]==fa[j][k]) 77 { 78 cost[i][k]+=flow[i][j]; 79 cost[j][k]+=flow[i][j]; 80 break; 81 } 82 clrmax(f); 83 ans=0x3f3f3f3f; 84 for(int i=0;i<=n;i++) 85 ans=min(ans,k=dfs(1,0,i)); 86 printf("%d\n",ans); 87 return 0; 88 }View Code
?
問(wèn)題 I: 簽到題
時(shí)間限制:?5 Sec??內(nèi)存限制:?16 MB提交:?241??解決:?18
?
題目描述
眾所周知，冬學(xué)姐人見(jiàn)人愛(ài)，因此他的仰慕者們分布在世界各地。有一天冬學(xué)姐心血來(lái)潮想要去見(jiàn)他的所有仰慕者。 假設(shè)冬學(xué)姐所有仰慕者所在城市排成一條直線，總共有n座城市，編號(hào)為0,1,2......n-1，從城市i到城市j飛機(jī)票所需要的費(fèi)用為(i+j)%n。而冬學(xué)姐剛開(kāi)始在0號(hào)城市中。 因?yàn)槎瑢W(xué)姐特別喜歡飛機(jī)，所以非飛機(jī)不搭乘。可是冬學(xué)姐囊中羞澀，希望以最少的費(fèi)用見(jiàn)到他的所有仰慕者。你能幫冬學(xué)姐設(shè)計(jì)一個(gè)方案，使得他見(jiàn)到所有仰慕者所需費(fèi)用最少嗎？?
輸入
多組數(shù)據(jù),數(shù)據(jù)不超過(guò)1000000組。對(duì)于每組數(shù)據(jù)包含一個(gè)整數(shù)，代表冬學(xué)姐的仰慕者所在城市個(gè)數(shù)n(0≤n≤1018)。
?
輸出
對(duì)于每組數(shù)據(jù)，輸出它的數(shù)據(jù)編號(hào)（從1開(kāi)始），以及冬學(xué)姐最少需要的費(fèi)用。
?
樣例輸入
0 1 2樣例輸出
Case 1: 0 Case 2: 0 Case 3: 1來(lái)源
水題之四。cf上的題。 0號(hào)結(jié)點(diǎn)獨(dú)立一組。1和n-1號(hào)結(jié)點(diǎn)一組，之間建一條邊這條邊是權(quán)值為0（不收費(fèi)）的。然后是2和n-2，3和n-3....(n+1)/2-1和(n+1)/2(n為奇數(shù)）或n/2（n為偶數(shù)）.這樣一共有n/2組之間是不需要收費(fèi)的。然后0和1,建邊，2和n-1建邊，3和n-2建邊。。這樣建n/2條權(quán)值為1的邊修構(gòu)成了最終的圖。我們只需要花費(fèi)n/2的費(fèi)用就能從結(jié)點(diǎn)0遍歷整個(gè)圖。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 int main() 8 { 9 int kase=0; 10 LL n; 11 while(scanf("%lld",&n)!=EOF) 12 printf("Case %d: %lld\n",++kase,n>>1); 13 return 0; 14 }View Code
?
問(wèn)題 J: 水題
時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB提交:?11??解決:?2
?
題目描述
是的，這是一道有關(guān)流的問(wèn)題。 給出一個(gè)由n個(gè)結(jié)點(diǎn)組成的有向圖，這n個(gè)結(jié)點(diǎn)標(biāo)號(hào)為0~n-1。 對(duì)于任意滿足(0≤i<j<n)的結(jié)點(diǎn)對(duì)(i,j)，都存在一條從結(jié)點(diǎn)i連向結(jié)點(diǎn)j的有向邊，其容量為i^j(i異或j)。 請(qǐng)你構(gòu)建從結(jié)點(diǎn)0到結(jié)點(diǎn)n-1的最大流網(wǎng)絡(luò)，并輸出其最大流。為簡(jiǎn)化輸出，輸出答案 mod 109+7。?
輸入
多組數(shù)據(jù),數(shù)據(jù)不超過(guò)10000組。每組數(shù)據(jù)包含一個(gè)整數(shù)n，代表有向圖結(jié)點(diǎn)個(gè)數(shù)(2≤n≤1018)。
?
輸出
對(duì)于每組數(shù)據(jù)，輸出它的最大流 mod 109+7后的答案。
?
樣例輸入
2樣例輸出
1某網(wǎng)絡(luò)賽題目。較難難度的找規(guī)律題。 運(yùn)用最大流最小割定理可以推出其規(guī)律。當(dāng)然我當(dāng)初是打表硬找規(guī)律的233333。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define LL long long 4 #define mod 1000000007 5 using namespace std; 6 LL quick_pow(LL x, LL n) { 7 LL res = 1; 8 x=(x%mod+mod)%mod; 9 while(n) { 10 if(n&1) 11 res=res*x% mod; 12 n >>=1; 13 x =x*x% mod; 14 } 15 return res; 16 } 17 int main() 18 { 19 LL n,m,q,l,ans,k,kk; 20 int t; 21 while(scanf("%lld",&n)!=EOF) 22 { 23 t=0; 24 n--; 25 m=n; 26 while(m) 27 { 28 t++; 29 m>>=1; 30 } 31 q=1; 32 m=(q<<(t-1)); 33 ans=(m%mod)*((1+m)%mod)%mod; 34 ans=ans*quick_pow(2,mod-2)%mod; 35 n-=m; 36 kk=1; 37 k=2; 38 while(k<=n+kk) 39 { 40 ans=(ans%mod+(((n+kk)/k)%mod)*((kk%mod)*(kk%mod)%mod+1)%mod)%mod; 41 if(k==LLONG_MAX) 42 break; 43 kk=k; 44 k<<=1; 45 } 46 printf("%lld\n",ans); 47 } 48 return 0; 49 }View Code
?
問(wèn)題 K: 臨界區(qū)資源問(wèn)題
時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB提交:?404??解決:?53
?
題目描述
15級(jí)有一位李軒大佬，對(duì)你沒(méi)看錯(cuò)就是坐在第二機(jī)房的那個(gè)。最近正在學(xué)操作系統(tǒng)，他遇到了一個(gè)問(wèn)題。可是他今天得來(lái)比賽啊，所以沒(méi)時(shí)間解決這個(gè)問(wèn)題，希望你能幫他解決： 在操作系統(tǒng)中，多個(gè)進(jìn)程必須互斥地訪問(wèn)臨界區(qū)的資源。 簡(jiǎn)單地說(shuō)，就是當(dāng)一個(gè)進(jìn)程A在訪問(wèn)一個(gè)臨界區(qū)資源時(shí)，另外一個(gè)進(jìn)程B是不能訪問(wèn)該資源的。 考慮有n個(gè)臨界區(qū)資源，編號(hào)為0~n-1。剛開(kāi)始都處于沒(méi)有進(jìn)程占用（訪問(wèn)）的空閑狀態(tài)。 現(xiàn)在順序地給出m條訪問(wèn)指令，編號(hào)1~m（沒(méi)有退出訪問(wèn)指令，即一旦訪問(wèn)就一直處于訪問(wèn)狀態(tài)）,每個(gè)指令只包含一個(gè)數(shù)k，代表訪問(wèn)的臨界區(qū)資源編號(hào)，并且發(fā)出每條指令的進(jìn)程都互不相同。 如果有某條指令是無(wú)效的，即在它之前有其它指令訪問(wèn)該資源，則跳過(guò)該條指令，并輸出該指令編號(hào)。 例如： n=10,m=10。 m條指令分別是：2 3 5 4 1 2 3 4 5 6。第六條指令訪問(wèn)的2號(hào)資源在第一條指令時(shí)就被其他進(jìn)程占用了,同理第七條請(qǐng)求訪問(wèn)的3號(hào)資源第二條指令時(shí)已經(jīng)被占用。相同地第八條第九條指令也是無(wú)效的。 因此輸出6 7 8 9。 好吧說(shuō)了這么多，其實(shí)題意就是： 給出一個(gè)長(zhǎng)度為m的數(shù)列，該數(shù)列中數(shù)字的取值范圍是0~n-1。對(duì)于某個(gè)位置i有數(shù)字ai，如果在i之前出現(xiàn)了和i位置數(shù)字ai值相等的數(shù)字，則需要輸出i。?
輸入
一組數(shù)據(jù)。 第一行有兩個(gè)正整數(shù)n、m（1≤n,m≤100)。代表資源個(gè)數(shù)和訪問(wèn)指令個(gè)數(shù)。 第二行包含m個(gè)整數(shù)，代表第i條指令訪問(wèn)的資源ai。?
輸出
輸出一行,按上升順序輸出無(wú)效指令編號(hào)。
?
樣例輸入
10 10 2 3 5 4 1 2 3 4 5 6樣例輸出
6 7 8 9?
?
?
真簽到題，比以上水題還水。
就是題目很忽悠23333，然而這是連兩個(gè)for都能過(guò)的題。當(dāng)初預(yù)期是所有寫(xiě)題的人都能過(guò)。
然而還是有人糾結(jié)前面問(wèn)題而沒(méi)看后面問(wèn)題。導(dǎo)致過(guò)題人數(shù)只有一半。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define LL long long 5 #define mod 1000000007 6 using namespace std; 7 const int N=1e2+10; 8 int n,m; 9 int a[N],b[N]; 10 int main() 11 { 12 scanf("%d%d",&n,&m); 13 clr(b); 14 for(int i=1;i<=m;i++) 15 { 16 scanf("%d",&a[i]); 17 if(b[a[i]]) 18 { 19 printf("%d ",i); 20 } 21 else 22 { 23 b[a[i]]=1; 24 } 25 } 26 printf("\n"); 27 return 0; 28 }View Code
?
轉(zhuǎn)載于:https://www.cnblogs.com/wujiechao/p/7712029.html
總結(jié)
以上是生活随笔為你收集整理的第五届合肥工业大学宣城校区程序设计大赛题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 多囊卵巢综合症会排卵吗
- 下一篇： 尝试插入cctv视频