題干：

星際爭霸(StarCraft)單人戰役模式中有很多供人游玩的任務關卡。

tokitsukaze新開始了一關單人戰役模式下的任務。在這場戰役中，你要作為指揮官指揮克魯普星區的艾倫人類(Terran)來防御人類的敵人——邪惡異蟲(Zerg)的襲擊。

這一次，作為指揮官，你的任務目標是盡可能多的保全人類方所擁有的7個基地。你在這次任務中擁有n個人口單位的兵力。為了防御異蟲的攻擊，每個基地都有一個能夠抵擋異蟲攻擊的最小兵力需求L[i]，同時每個基地因為有固定的人口上限，分配給該基地的兵力也不得大于上限R[i]。

你需要在任務一開始就為這7個基地做好兵力分配，每個兵都應該分配給一個基地，即不應該有空閑兵力。如果任何一個基地被異蟲攻破(分配的兵力大于0，且小于最小兵力需求，導致兵力白白葬送犧牲)，或者某個基地的人口超過了人口上限，兵力大于R[i]，任務都會直接失敗。

為了避免任務失敗，tokitsukaze決定從一開始就放棄一些基地(即不對這些基地派出兵力)。

請問保證任務成功的條件下，tokitsukaze最多留下多少個基地？特別的，如果任務失敗這種情況下請輸出"0"，不含引號。

由于tokitsukaze的星際操作十分流弊，你可以認為如果能夠至少能夠保留一個基地，任務就一定能夠成功。

輸入描述:

第一行輸入一個T(T≤50000)，表示T組數據。對于每組數據： 輸入一個正整數n(1≤n≤10^9)表示需要分配的兵力總人口。 接下來7行，每行兩個正整數L,R(1≤L≤R≤10^9),分別表示該基地夠抵擋異蟲攻擊的最小兵力需求與該基地的人口上限。

輸出描述:

對于每組數據，輸出tokitsukaze最多能夠留下幾個基地，每組數據占一行。

?

示例1

輸入

復制

4 50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 50 1 1 20 30 20 30 20 30 1 1 20 30 20 30 70 19 19 10 10 10 10 10 10 10 10 10 10 1 1 2 1 1 3 3 3 3 3 3 3 3 3 3 3 3

輸出

復制

0 4 7 0

說明

第一個樣例，無論tokitsukaze怎么取舍，都不能滿足條件。在這種特殊情況下你應該輸出0。第二個樣例，tokitsukaze選擇第一個第二個第三個和第五個基地，分別分配1,20,28,1的兵力即可滿足既能完全分配兵力，同時這4個基地既能防御異蟲的攻擊，也不超過每個基地的人口上限。第三個樣例，tokitsukaze分別分配19,10,10,10,10,10,1給7個基地就能保證既能完全分配兵力，同時這7個基地既能防御異蟲的攻擊，也不超過每個基地的人口上限。第四個樣例，tokitsukaze如果只選擇1號基地，那么要么無法將所有的兵力完全分配，要么該基地的人口總數將會大于上限，所以任務會直接失敗，而如果選擇其他基地，那么由于不能達到防御的最小下界。所以也會導致任務失敗。不論怎么取舍任務都會失敗，所以這種情況下應該輸出0。

解題報告：

? ?就是個枚舉答案，，實在不行就7層循環、、然后維護一個可行的l,r，當可行的l,r包含了輸入的數的時候，就是滿足條件的，然后從所有答案中選出最大的就行。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll n; ll low[15],up[15]; bool fit(ll i,int j) {if((i>>j)&1) return 1;else return 0 ; } int get(ll i) {int cnt = 0;while(i) {if(i&1) cnt++;i>>=1; }return cnt; } int main() {int t;cin>>t;while(t--) {scanf("%lld",&n);int ans = 0;for(int i = 1; i<=7; i++) {scanf("%lld%lld",low+i,up+i);}ll minn = 0,maxx = 0;for(ll i = 0; i<(1<<7); i++) {minn=maxx=0;for(int j = 1; j<=7; j++) {if(fit(i,j-1)) minn+=low[j],maxx+=up[j];}if(minn<=n && maxx>=n) ans = max(ans,get(i));}printf("%d\n",ans);}return 0 ;}

%%%Qls：

#include<bits/stdc++.h> using namespace std;typedef long long ll;ll l[15],r[15];int main() {int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=0;i<7;i++)scanf("%lld%lld",&l[i],&r[i]);int res=0;for(int i=0;i<(1<<7);i++){ll mi=0,mx=0;for(int j=0;j<7;j++)if(i>>j&1)mi+=l[j],mx+=r[j];if(mi<=n && n<=mx)res=max(res,__builtin_popcount(i));}printf("%d\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 303D第十五届浙江大学宁波理工学院程序设计大赛（同步赛）】Campaign（二进制枚举，位运算，暴力，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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