題意：

給你兩個01串，要你選n/2個位置，使得選的位置在s1中"1"的數量等于未選的s2中"1"的數量

n<=5000,1s

思路：

設兩個串中出現"00""01""10""11"的總數是A,B,C,D，我們選的個數分別是a,b,c,d

數據最多能承受n^2的暴力

根據題意，有a+b+c+d=n/2? ? ?①

c+d=B-b+D-d? ? ②

聯立得d=B+D+a-n/2

于是我們暴力a，可以得到d

然后將a,d帶入①可得b+c=n/2-a-d

暴力b可得c

最后只要a,b,c,d是否全部合法，輸出方案即可

代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<stack> #include<queue> #include<deque> #include<set> #include<vector> #include<map> #include<functional> #include<cmath>#define fst first #define sc second #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define lc root<<1 //#define rc root<<1|1 #define lowbit(x) ((x)&(-x)) using namespace std;typedef double db; typedef long double ldb; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PI; typedef pair<ll,ll> PLL;const db eps = 1e-6; const int mod = 1e9+7; const int maxn = 2e6+100; const int maxm = 2e6+100; const int inf = 0x3f3f3f3f;int n; char s1[maxn]; char s2[maxn]; int A,a,B,b,C,c,D,d; int main(){scanf("%d", &n);scanf("%s", s1+1);scanf("%s", s2+1);for(int i = 1; i <= n; i++){if(s1[i]=='0'){if((s2[i]=='0'))A++;else B++;}else{if(s2[i]=='0')C++;else D++;}}int mm = min(A, n/2);a = b = c = d = -1;int ys = 0;for(a = 0; a <= A && a <= n/2; a++){if(B+D-n/2+a<=D&&B+D-n/2+a>=0){d = B+D-n/2+a;//int m = min(min(n/2-a-d,B),n/2);//printf("%d %d\n",a,d);for(b = 0; b <= B&&b<=n/2-a-d; b++){//printf(" %d\n",b);if(n/2-a-b-d<=C&&n/2-a-b-d>=0){c = n/2-a-b-d;ys=1;break;}}if(ys)break;}}//printf("%d %d %d %d\n", a,b,c,d);if(!ys){return printf("-1"),0;}for(int i = 1; i <= n; i++){if(s1[i]=='0'){if(s2[i]=='0'&&a){a--;printf("%d ",i);}else if(s2[i]=='1'&&b){b--;printf("%d ",i);}}else if(s1[i]=='1'){if(s2[i]=='0'&&c){c--;printf("%d ",i);}else if(s2[i]=='1'&&d){d--;printf("%d ",i);}}}return 0; }

?

轉載于:https://www.cnblogs.com/wrjlinkkkkkk/p/10505395.html

總結

以上是生活随笔為你收集整理的Codeforces 1138B Circus (构造方程+暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

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