題意：有兩場(chǎng)表演，n個(gè)藝術(shù)家，根據(jù)規(guī)則找出我們要挑選的人的編號(hào)，輸出編號(hào)。

規(guī)則1 保證每個(gè)人只能參加一場(chǎng)表演，也就是同一個(gè)藝術(shù)家不能出現(xiàn)在兩場(chǎng)表演中

規(guī)則2 兩場(chǎng)表演參演的藝術(shù)家的數(shù)量是相同的

規(guī)則3 第一場(chǎng)可以演小丑的藝術(shù)家的數(shù)量要和第二場(chǎng)表演雜技的藝術(shù)家數(shù)量保持相同

分析：

很久沒(méi)擼代碼看到這題有點(diǎn)蒙，按說(shuō)應(yīng)該挺簡(jiǎn)單的。。。結(jié)果還是很久沒(méi)想明白。。。
首先我們發(fā)現(xiàn)輸入是兩行數(shù)據(jù)，一行表示第i個(gè)人能不能演小丑，一行表示第i個(gè)人能不能演雜技，那么也就是說(shuō)，把整個(gè)藝術(shù)家群體看做一個(gè)集合，可知為了計(jì)算方便不出錯(cuò)，可以分為四個(gè)小集合，分別是兩種都不能演的藝術(shù)家數(shù)量A，只能演雜技的藝術(shù)家數(shù)量B，只能演小丑的藝術(shù)家數(shù)量C，以及兩種都能演的藝術(shù)家數(shù)量D。

前兩個(gè)規(guī)則都好搞定，就是第三個(gè)規(guī)則不好保證，而把藝術(shù)家分集合設(shè)未知數(shù)就可以巧妙地構(gòu)造恒等關(guān)系，從而列出一下兩個(gè)方程。

我們?cè)O(shè)a,b,c,d為第一場(chǎng)表演在四個(gè)集合中所選藝術(shù)家的數(shù)量。

那么可知
$a+b+c+d=n/2$ (規(guī)則二)
$c+d=B?b+D?d$(規(guī)則三：第一組小丑可演小丑數(shù)量 = 第二組雜技數(shù)量)
發(fā)現(xiàn)：兩個(gè)方程四個(gè)未知數(shù)
枚舉任意兩個(gè)那么就可以根據(jù)這兩個(gè)等式把剩下兩個(gè)未知數(shù)求出來(lái)，根據(jù)求出的未知數(shù)就可以把對(duì)應(yīng)集合的藝術(shù)家下標(biāo)輸出出來(lái)，由于任意滿足條件的答案皆可。
這道題就是一個(gè)數(shù)學(xué)題，沒(méi)有啥編程難點(diǎn)可言，只要邏輯清晰，還是能很快AC的- -…
所以關(guān)于問(wèn)題中有明顯數(shù)量關(guān)系約束的題目，不妨設(shè)未知數(shù)解方程組解決。
復(fù)雜度：O（$N^2$）$N<5000$

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn = 5010; vector<int>c,s,com,none; int bokc[maxn],boks[maxn]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%1d",&bokc[i]);}for(int i=1;i<=n;i++){scanf("%1d",&boks[i]);}for(int i=1;i<=n;i++){if(boks[i]==bokc[i]){if(boks[i])com.push_back(i);else none.push_back(i);}if(boks[i]!=bokc[i]){if(bokc[i])c.push_back(i);if(boks[i])s.push_back(i);}}int a,b,C,d;bool yes = 0;for(int i=0;i<=min((int)none.size(),n/2);i++){////枚舉aa = i;//a = 0d = s.size()+com.size()-n/2 + a; //d = 0if(d<0)continue;int bc = n/2-a-d;// bc = 2if(bc<0)continue;for(int j = 0;j<=min((int)c.size(),n/2);j++){//枚舉CC = j;b = bc-C;if(a+b+C+d!=n/2)continue;if(C+d!=s.size()-b+com.size()-d)continue;bool f=0;//所有continue都是非法的情況 這里注意就算是前面合法，數(shù)量超過(guò)實(shí)際情況也是非法if(a>none.size())continue;if(b>s.size())continue;if(C>c.size())continue;if(d>com.size())continue;for(int o = 0;o<a;o++){if(!f)printf("%d",none[o]),f=1;else printf(" %d",none[o]);}for(int o = 0;o<b;o++){if(!f)printf("%d",s[o]),f=1;else printf(" %d",s[o]);}for(int o = 0;o<C;o++){if(!f)printf("%d",c[o]),f=1;else printf(" %d",c[o]);}for(int o = 0;o<d;o++){if(!f)printf("%d",com[o]),f=1;else printf(" %d",com[o]);}yes = 1;break;}if(yes)break;}if(!yes)puts("-1");return 0; }

總結(jié)

以上是生活随笔為你收集整理的[CodeForces-1138B] *Circus 解方程|数学的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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