当前位置: 代码迷 >> 综合 >> Codeforces Round #306 (Div. 2) E. Brackets in Implications (构造)
  详细解决方案

Codeforces Round #306 (Div. 2) E. Brackets in Implications (构造)

热度:15   发布时间:2023-12-17 03:37:43.0

题意:

给你n个数,数字仅为0和1,现在定义一种运算方式”->”,运算满足

0->0=1

0->1=1

1->0=0

1->1=1

现在让你将这n个数字通过->运算符和’(’ ‘)’连接起来(括号优先级大于->),使得运算结果为0

思路:

观察四个等式,发现,如果要让结果为0,必须变成1->0的情况,那么最后一位必定为0,最后一位不是0,怎么计算都没法让等式最终结果变成0,这个时候,问题我们的问题变成了让前n-1个数字运行结果为1即可。
然后,我们又能发现,只要式子最后一位为1,那么不论前面是什么,结果必定为1,
那么这个时候我们分类讨论一下倒数第二个数,如果倒数第二个数为1,那么我们都不需要加任何括号,就能让结果为0,如果倒数第二个数为0,那么我们要向前找到一个0,然后加两个括号,将式子变成….->(0->(1->1->…..->0))的形式,就能让结果变成1了

错误及反思:

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int arr[maxn];
int k[maxn];
int h[maxn];
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&arr[i]);if(n==1){if(arr[0]==0) printf("YES\n0\n");else printf("NO\n");}else if(arr[n-1])printf("NO\n");else{if(arr[n-2]==1){printf("YES\n");for(int i=0;i<n;i++)if(i==0) printf("%d",arr[i]);else printf("->%d",arr[i]);puts("");}else{h[n-2]+=2;int temp=n-3;while(temp>=0){if(arr[temp]==0){k[temp]++;k[temp+1]++;break;}temp--;}if(temp<0)printf("NO\n");else{printf("YES\n");for(int i=0;i<n;i++){while(k[i]>0){printf("(");k[i]--;}printf("%d",arr[i]);while(h[i]>0){printf(")");h[i]--;}if(i!=n-1) printf("->");}puts("");}}}
}
  相关解决方案