Educational Codeforces Round 166

Dashboard - Educational Codeforces Round 166

Problem - A - Codeforces

签到(写的有点烦…)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
void solve()
{int n;cin>>n;string s;cin>>s;vector<int>a;vector<char>b;vector<int>c;vector<char>d;s+='a';for(int i=0;i<n;i++){if(s[i]>='0'&&s[i]<='9'){a.push_back(int(s[i]-'0'));c.push_back(s[i]-'0');}else if(s[i]>='a'&&s[i]<='z'){b.push_back(s[i]);d.push_back(s[i]);if(s[i+1]>='0'&&s[i+1]<='9'){cout<<"NO"<<endl;return ;}}else {cout<<"NO"<<endl;return ;}}sort(a.begin(),a.end());sort(b.begin(),b.end());for(int i=0;i<int(a.size());i++){if(a[i]!=c[i]){cout<<"NO"<<endl;return ;}}for(int i=0;i<b.size();i++){if(b[i]!=d[i]){cout<<"NO"<<endl;return ;}}cout<<"YES"<<endl;
}
int main()
{int t;cin>>t;while(t--)solve();
}

Problem - B - Codeforces

遍历 $1\leq i\leq n$ ，

显然初始答案为 $1+\sum_{1\leq i\leq n}abs(a[i]-b[i])$

如果存在一个 $i$ 使得 $b [n + 1]$ 在 $a [i]$ 和 $b [i]$ 之间,那么答案就是上述和

否则还要加上 $min(min(abs(b[n+1]-a[i]),abs(b[n+1]-b[i]))1\leq i\leq n)$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int b[N];
void solve()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n+1;i++)scanf("%d",&b[i]);long long ans=0;int f=2e9;for(int i=1;i<=n;i++){ans+=abs(a[i]-b[i]);int x=min(a[i],b[i]);int y=max(a[i],b[i]);if(b[n+1]>=x&&b[n+1]<=y)f=0;else{if(f){int p=min(abs(x-b[n+1]),abs(y-b[n+1]));f=min(f,p);}}}cout<<ans+1+f<<endl;
}
int main()
{int t;cin>>t;while(t--)solve();
}

数学前缀和

感觉好烦，我写的也好烦…

一个公司要招聘 $n$ 个A职位和 $m$ 个B职位，共有 $n + m + 1$ 人来应聘

一个人的能力值由 $a [i], b [i]$ 构成, $a [i]! = b [i]$

面试到第 $i$ 人时候，除去 $i$ ，其余人从前往后遍历，若 $a [i] > b [i]$ 且A职位有空余则将该人设为A职位，否则便是B职位

求出此时所有人的对应能力之和(为A职位则加 $a [i]$ )

由于是从前往后遍历的，所以想到可以用前缀和来处理

开两个数组 $aa, bb$ 分别存储 $a [i] > b [i]$ 和 $a [i] < b [i]$ 的下标

然后分别计算这两个数组的 $a_i$ 的前缀和与 $b_i$ 的前缀和

开始遍历职员，遍历到 $i$ 时,设 $x, y$ 为除去 $i$ 之外的 $a [i] > b [i], a [i] < b [i]$ 的人数，设 $sum=\sum max(a[i],b[i])$

$x = aa . s i ze () - (a [i] > b [i]? 1 : 0)$

$ y=bb.size()-(b[i]>a[i]?1:0)$

先判断职位是否会出现不平衡，如果 $x == n$ 则不会出现不平衡， $an s = s u m - ma x (a [i], b [i])$

否则，分为两种情况，处理方法相同，这里就说下 $x > n$

由于是顺序遍历，所以会有 $x - n$ 个原本 $a [i] > b [i]$ 的人要分配到B职位

$p = aa [aa . s i ze () - (x - n)]$ ,即为这个分界线，要将 $p$ (包含 $p$ )右边的人的和换成 $b [i]$

此处还要讨论一下，如果 $a [i] > b [i]$ 的话，可能目前的这个 $i$ 还包含在 $p$ 的右边，要特判一下，包含的话要将 $p$ 再左移一位

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int b[N];
int n,m;
long long l[N],r[N],ll[N],rr[N];
void solve()
{scanf("%d%d",&n,&m);for(int i=1;i<=n+m+1;i++){scanf("%d",&a[i]);}for(int i=1;i<=n+m+1;i++){scanf("%d",&b[i]);}vector<int>aa;vector<int>bb;long long sum=0;aa.push_back(11);bb.push_back(11);//处理前缀和下标最好从1开始for(int i=1;i<=n+m+1;i++){if(a[i]>b[i]){aa.push_back(i);}else bb.push_back(i);sum+=max(a[i],b[i]);}for(int i=1;i<=aa.size()-1;i++){ll[i]=ll[i-1]+a[aa[i]];l[i]=l[i-1]+b[aa[i]];}for(int i=1;i<=bb.size()-1;i++){rr[i]=rr[i-1]+b[bb[i]];r[i]=r[i-1]+a[bb[i]];}for(int i=1;i<=n+m+1;i++){int x=aa.size()-1,y=bb.size()-1;if(a[i]>b[i])x--;else y--;if(x==n){cout<<sum-max(a[i],b[i])<<' ';}else{if(x>n){int f=x-n;int p=aa.size()-1-f;if(a[i]>b[i]){if(aa[p]<i){p--;cout<<sum-(ll[aa.size()-1]-ll[p])+l[aa.size()-1]-l[p]-b[i]<<' ';}elsecout<<sum-(ll[aa.size()-1]-ll[p])+l[aa.size()-1]-l[p]-a[i]<<' ';}elsecout<<sum-max(a[i],b[i])-(ll[aa.size()-1]-ll[p])+l[aa.size()-1]-l[p]<<' ';}else{int f=y-m;int p=bb.size()-1-f;if(a[i]<b[i]){if(bb[p]<i){p--;cout<<sum-(rr[bb.size()-1]-rr[p])+r[bb.size()-1]-r[p]-a[i]<<' ';}elsecout<<sum-(rr[bb.size()-1]-rr[p])+r[bb.size()-1]-r[p]-b[i]<<' ';}elsecout<<sum-max(a[i],b[i])-(rr[bb.size()-1]-rr[p])+r[bb.size()-1]-r[p]<<' ';}}}cout<<endl;
}
int main()
{int t;cin>>t;while(t--)solve()

Problem - D - Codeforces

好难…

栈 RMQ 前缀和

对于一段括号序列(只包含"()"),

有一个小 $t r i c k$ 就是将 $^{'} (^{'},^{'})^{'}$ 设为 $1, - 1$ ,设 $pre[i]=\sum_{1\leq k \leq i}(s[i]=='('? 1:-1)$

如果这段序列满足

$\forall i \in [1,n] ，pre[i]\geq 0$

$s [n] == 0$

则这段序列为一个有效匹配

现在给出一个有效匹配序列，找出所有的 $1\leq l\leq r\leq n$ ,将 $[l, r]$ 内的序列翻转,‘(‘变为’)’,‘(‘变为’)’,使得翻转后的序列仍然为一个有效匹配

按照套路，可以枚举左端点(左右都可以),看看右边有哪些可以和它匹配的

对于一个左端点 $l$ ，假设找到一个右端点 $k$ ，首先肯定要满足翻转之后左右括号的数量仍然相等，即 $pre_{k}-pre_{l-1}=0,pre_{k}=pre_{l-1}$

固定左端点，找到满足这个条件的 $k$ 可以开一个 $ma p < in t, v ec t or < in t >>$ ,存储每个前缀和对应的下标，二分出大于等于 $l$ 的最小下标 $x$ 即可

但是这样只满足了第二个条件，在翻转过程中可能出现 $pre_i<0$ 的情况

$pre_{l-1}$ 是不会变化的，而 $pre_{k}=pre_{l-1}-(pre_k-pre_{l-1})=2*pre_{l-1}-pre_k$

要满足 $[l, k]$ 内的所有的前缀和都大于等于零，有 $\forall j \in [l,k],2*pre_{l-1}-pre_j\geq 0,2*pre_{l-1}\geq max(pre_j)$

由于固定了 $l$ ,这里的 $max(pre_k),l\leq k \leq n$ 是单调不减的，可以先利用 $ST$ 表处理每段区间的最大值，然后二分出满足 $max(pre_k)\leq 2*pre_{l-1}，l\leq k\leq r$ 的最大的 $r$ ,这样的话 $[l, r]$ 内的值便都满足了第一个条件，再二分出小于等于 $r$ 的最大下标 $y$ ,让答案加上 $y - x + 1$ 即可

这里不用特判一下 $y\geq x$ ，因为只存在一种 $y < x$ ,就是 $x, y$ 都返回了 $e n d$ ，此时 $y = x - 1 ， y - x + 1 = 0$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int f[N][20],lg[N];
int n;
string s;
int query(int l,int r)
{int k=lg[r-l+1];return max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{cin>>s;s=' '+s;int n=s.length()-1;long long ans=0;map<int,vector<int>>mp;for(int i=1;i<=n;i++){f[i][0]=f[i-1][0]+(s[i]=='('? 1:-1);mp[f[i][0]].push_back(i);}for(int j=1;j<=lg[n];j++){for(int i=1;i<=n-(1<<j)+1;i++){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=n-1;i++){int l=i,r=n;while(l<r){int mid=(l+r+1)>>1;if(query(i,mid)<=2*f[i-1][0])l=mid;else r=mid-1;}if(query(i,l)>2*f[i-1][0])continue;int x=lower_bound(mp[f[i-1][0]].begin(),mp[f[i-1][0]].end(),i)-mp[f[i-1][0]].begin();int y=upper_bound(mp[f[i-1][0]].begin(),mp[f[i-1][0]].end(),r)-mp[f[i-1][0]].begin()-1;//小于等于ans+=(y-x+1);}cout<<ans<<endl;
}
int main()
{for(int i=2;i<=N-10;i++)lg[i]=lg[i>>1]+1;int t;cin>>t;while(t--)solve();
}