C. Balance the Bits
C. Balance the Bits
題目大意：
給你一個含有0和1字符的字串，根據這個字串構造兩個不一樣但是都合法的數學運算式，例如()()()合法而(()這種則不合法，字串中的0代表兩個數學運算式中不一樣的括號，而1代表一樣的括號
解法分析
- 首先，合法的數學運算式，必須在第一個括號為（和最后一個括號為），所以說給你的這個字串的第一個和最后一個必須是1
- 由于0代表的是不同的括號，而1是相同的括號，且括號是有匹配性的，一個（必須匹配一個），所以，字串中0的個數和1的個數應該都是偶數
- 滿足以上條件，最后一步就是構造了，其中最簡單的構造方法就是：字串1和0分開構造，（和）分別有n/2個，對于1，假設有n1個，那么我們就把前n1/2個輸出為（，后n1/2個輸出為）；對于0，我們就按照奇偶進行輸出，第一種是為奇數個時，輸出（，偶數個時輸出），第二種只需和第一種在0是的輸出正好相反就行了，
代碼環節
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
char a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t,n;
int n1,n0;///不同的個數
cin>>t;
while(t--){
cin>>n;
cin>>a;
n0=0;
for(int i=0;i<n;i++)
if(a[i]=='0')
n0++;
int n1=n-n0;
if(n0%2==1||a[0]=='0'||a[n-1]=='0')
{
printf("NO\n");
continue;
}
printf("YES\n");
int n0p=0;
int n1p=0;
for(int i=0;i<n;i++){
if(a[i]=='0')
{
n0p++;
if(n0p%2==1)
printf("(");
else
printf(
")");
}
else
{
if(n1p<n1/2)
printf("(");
else
printf(")");
n1p++;
}
}
printf("\n");
n0p=0;
n1p=0;
for(int i=0;i<n;i++){
if(a[i]=='0')
{
n0p++;
if(n0p%2==1)
printf(")");
else
printf(
"(");
}
else
{
if(n1p<n1/2)
printf("(");
else
printf(")");
n1p++;
}
}
printf("\n");
}
return 0;
}
共勉
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274130.html
標籤：其他
上一篇：python硬幣游戲悖論