Codeforces 第 794 轮 (Div. 2) (D~E)
文章Codeforces Round #794 (Div. 2) (D~E),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C. Circular Local MiniMax
我们都知道最构造方案是啥 但要注意的是众数不能超过n/2这个条件 要是跨越了n/2这个线 就要取到等于号 所以要想等于n/2并且合法 就必须得 是最小值或者最大值
#includeusing namespace std;const int N = 1e4+10;const int M = 1<<10;const int mod = 1e9+7;#define int long long#define endl '\n'#define Endl '\n'#define yes cout<<"YES"< >T; while(T--){ int n;cin>>n; vector a(n); map mp; int flag=0,flag1=0; int cnt=-1; for(int i=0;i >a[i]; mp[a[i]]++; if(mp[a[i]]>n/2){ flag=1; }else if(mp[a[i]]==n/2){ flag1++; cnt=a[i]; } } if(n%2||flag){ no goto out; } if(flag1==1){ sort(a.begin(),a.end()); if(a[0]==cnt||a[n-1]==cnt); else { no goto out; } } yes sort(a.begin(),a.end()); for(int i=0,j=n/2;j D. Linguistics
讲一下思路吧 我们可以直接特判掉AB数目不合法的 然后我们任务就是把剩余的cntAB cntBA 合法的安排上
怎么做呢 其实就是一个贪心 我们先把cnt少的安排上去 并且尽可能的安排的地方是 比如AB AABB里的AB 我们可以排序把每个重要级 然后如果实在没办法 就只好安排到 ABA这种里面 但是这也不会引起连锁反应
也就是说 我们至少也要破坏一个BA 最后check 是否有足够多的BA即可E. Bring Balance
这道题 思维难度 真大啊!
至少我不是很会 呃呃 想了2h才想出来
首先我们先判原串是否合法这里我们可以用前缀和都>=0 就可以了 其实这种合法括号的题 前缀和都很合适
然后我们可以思考一个性质 我手动模拟了几组 猜了一个最多交换次序不会超过2(最后发现是对的
那么如何证明呢???
因为我们要尽量把左括号放前面 我们前缀和最大时我们设当前最大值为si
我们交换1到i i+1到2n(这只是一个构造的
我们值转换后就是 [ai+ai-1+...+a1] + [a2n+a2n-1+...+ai+1]
显然我们j要是小于i 前缀和就是 ai+ai-1+ai-2+...+aj=si-sj-1 因为我们si是max所以恒大于等于0
要是我们j要是大于等于i 前缀和就是 ai+ai-1+...+a1+a2n+a2n-1+...+aj=s2n-sj-1+si s2n==0 si-sj-1显然大于0
那么我们再来讨论 何时输出1就可以了
首先我们考虑要是si出现了<0的点 肯定要包括进去
那么我们维护了一个区间 让后这个区间显然不是最优的
最优的情况是 我们前面囤积了很多左括号 后面能拿到很多的左括号
而这刚好可以用这个前缀和表示 因为我们已经把不合法的区间维护好了 所以我们后面扩展时不用考虑合法性 就算翻转过后还是合法的 那我们贪心的去求l-1的max 以及 r的max 即可
其实这个si的max 也是 根据第二个证明的启发吧 也算情有可原
因为就我们单单翻转维护好的不合法区间 显然不是最优的 我们可以做一些铺垫来get最优解#includeusing namespace std;const int N = 1e4+10;const int M = 1<<10;const int mod = 1e9+7;#define int long long#define endl '\n'#define Endl '\n'#define YES cout<<"YES"< >n; vector a(n*2+1); vector s(n*2+1); int flag=0,l,r; for(int i=1;i<=n<<1;i++){ char c;cin>>c; if(c=='(')a[i]=1; else a[i]=-1; s[i]=s[i-1]+a[i]; if(s[i]<0&&flag==0)l=i; if(s[i]<0)r=i,flag=1; } if(!flag){ cout<<0< s[r])r=i; } int l1=l; for(int i=1;i<=l1;i++){ if(s[i-1]>s[l-1])l=i; } vector b=a; for(int i=l,j=r;i<=r;i++,j--)a[i]=b[j]; for(int i=0;i<=n<<1;i++)s[i]=0; for(int i=1;i<=n<<1;i++){ s[i]=s[i-1]+a[i]; if(s[i]<0){ cout<<2< >T; while(T--){ solve(); } return ~~(0^_^0);}
2. 本站积分货币获取途径以及用途的解读,想在本站混的好,请务必认真阅读!
3. 本站强烈打击盗版/破解等有损他人权益和违法作为,请各位会员支持正版!
4. 编程技术 > Codeforces 第 794 轮 (Div. 2) (D~E)