生活随笔
收集整理的這篇文章主要介紹了
CodeForces 1138B暴力+剪枝
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
【題目鏈接】Circus
【題目分析】理解題意以后發現并沒有什么思路，沒有什么算法能用，這個時候就應該想到計算機解題的本質——暴力求解。相應的就要想到剪枝的條件，肯定不能盲目的暴力求解。
總共有四種人：00,01,10,11，分別統計出數目c1,c2,c3,c4，設第一個團體a1,a2,a3,a4,按照a3和a4進行暴力，相應的可以求出b4,b2,a2,a1,分別判斷是否合理，一旦合理直接輸出
代碼：
#include
<cstdio>
#include
<cstring>
#include
<algorithm>
#include
<iostream>
using namespace std
;const int MAXN
=6000;
char a
[MAXN
],c
[MAXN
];
int n
;
int cnt
[10][10];int main()
{ios
::sync_with_stdio(0);cin
.tie(0); cout
.tie(0);scanf("%d",&n
);scanf("%s%s",c
,a
);memset(cnt
,0,sizeof(cnt
));for(int i
=0;i
<n
;i
++){cnt
[c
[i
]-'0'][a
[i
]-'0']++;}int a1
,a2
,a3
,a4
;int b1
,b2
,b3
,b4
;int flag
=0;for(a4
=0;a4
<=cnt
[1][1];a4
++){for(a3
=0;a3
<=cnt
[1][0];a3
++){b4
=cnt
[1][1]-a4
;b2
=a3
+a4
-b4
;if(b2
<0 || b2
>cnt
[0][1]) continue;a2
=cnt
[0][1]-b2
;a1
=n
/2-a4
-a3
-a2
;if(a1
<0 || a1
>cnt
[0][0]) continue;flag
=1;break;}if(flag
==1) break;}if(!flag
){printf("-1");return 0;}for(int i
=0;i
<n
;i
++){if(a1
&& c
[i
]=='0' && a
[i
]=='0') printf("%d ",i
+1),a1
--;if(a2
&& c
[i
]=='0' && a
[i
]=='1') printf("%d ",i
+1),a2
--;if(a3
&& c
[i
]=='1' && a
[i
]=='0') printf("%d ",i
+1),a3
--;if(a4
&& c
[i
]=='1' && a
[i
]=='1') printf("%d ",i
+1),a4
--;}return 0;
}
總結
以上是生活随笔為你收集整理的CodeForces 1138B暴力+剪枝的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
