资讯详情

Educational Codeforces Round 185 (Rated for Div. 2) 记录

糖丸的一场，早早三个题但是没把D的啥比错误看出来，赛后B因为不开long long 见祖宗了。

A

可以贪心地取右下的几个可能作为答案的点，但是由于数据范围较小，暴力求解也可以通过。

B

由于需要求的是 \(r-l+1\) 的最大值，所以我们只需要关心第一步操作最大能是多少。

而假设第一步操作对一个长度为 \(len\) 的区间合法操作，那么后续可以通过恰好 \(n-1\) 步操作把 \(a\) 变成 \(b\) 等价于 \(\sum{b_i}-len \ge n-1\)

将数组 \(b\) 排序并去 \(0\) 后枚举第一步操作的长度即可。

C

注意到题目中其实给出了一个标准的带余除法的形式，稍加转化即可变为：

\[x=yq_i+r_j \]

其中 \(1 \le y \le x \le k\) ，那么我们保证 \(y < r_j\) 的情况下 \(x\) 尽量小是比较优的。因此取 \(y=r_j-1\) ，那么一组 \(q_i,r_j\)合法等价于:

\[(r_j-1)q_i+r_j \le k \]

注意到左边式子的值随 \(r_j,q_i\) 的增大而增大，所以贪心地对于每个较大的 \(r_j\) 匹配较小的 \(q_i\) 即可，使用双指针维护，时间复杂度 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int N=2e5+10;
int n,k;
int q[N],rr[N];
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>q[i];}for(int i=1;i<=n;i++){cin>>rr[i];}sort(q+1,q+n+1);sort(rr+1,rr+n+1);int l,r;l=1,r=n;int ans=0;while(l<=n && r>=1){if(q[l]*(rr[r]+1)+rr[r]<=k){l++;r--;ans++;}else{r--;}}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;for(int i=1;i<=T;i++){solve();}return 0;
}

D

注意到当有 \(\text{I}\) 的时候填 \(\text{I}\) 是优的，所以可以先假设所有 \(\text{?}\) 处都被填为了 \(\text{I}\) ，那么就需要考虑在 \(\text{I}\) 不够用的时候将其替换为 \(\text{X,V}\) 即可。这里 \(\text{X,V}\) 除了值不一样没有本质不同，所以可以放在一起考虑，有 \(\text{V}\) 的时候优先填 \(\text{V}\) ，没了再填上 \(\text{X}\)。

接下来再考虑怎么填比较优。这里我们可以把这个串中各个连续的问号段拉出来一个个单独考虑，因为 \(\text{I}\) 的值只受其后面一个字符影响，各个被非问号字符隔开的连续问号段并不能相互影响。此时观察一下可以发现每一个问号存在三类情况：

\(case1: III\) (中间的 \(\text{I}\) ，下同)

$case2: IIX $ 或 \(XII\)

\(case3: XIX\)

其中的 \(\text{X}\) 均可以由 \(\text{V}\) 替代。

对于第一类点，假设将其值变为 \(x\) ，对答案的影响为 \(x-1-2=x-3\)

同理第二类为 \(x-1\) ,第三类为 \(x+1\) 。

因此转换顺序为一类点-二类点-三类点。

此时则会出现一个问题，在转化过程中点的类型可能会发生变化。这个只需先将一类点标记完再考虑二类点，剩下的均化为三类点即可。

而对于各个连续问号段，我们还需要讨论它两边字符的值才能计算其中各类点的数量。

\(case1:\) 两边均为 \(\text{I}\)：此时一类点为从第一个问号开始隔一个取一个，若长度为偶数则最后一个点位二类点，其余为三类点，各个类型的点的数量即为：

\[s_1= \lceil \frac{len}{2} \rceil \]

\[s_2= [len \mod 2=0] \]

\[s_3=len-s_1-s_2 \]

其余情况也同理。

\(case2:\) 两边其中一个不为 \(\text{I}\), 此时

\[s_1= \lfloor \frac{len}{2} \rfloor \]

\[s_2= [len \mod 2=1] \]

\[s_3=len-s_1-s_2 \]

\(case3:\) 两边均不为 \(\text{I}\), 此时

\[s_1= \begin{cases} \lfloor \frac{len}{2} \rfloor & len \mod 2=1 \\ \frac{len}{2}-1 & len \mod 2=0 \end{cases} \]

\[s_2= [len \mod 2=0] \]

\[s_3=len-s_1-s_2 \]

先预处理出各种点的数量，询问时将多出的被 \(\text{I}\) 覆盖的问号点分配给 \(\text{X,V}\) 即可，时间复杂度 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int T;
int n,q;
char s[N];
void solve(){cin>>n>>q;for(int i=1;i<=n;i++)   cin>>s[i];int s1=0;int s2=0;int s3=0;int res=0;int ss=0;for(int i=1;i<=n;i++){if(s[i]=='X')   res+=10;else if(s[i]=='V')  res+=5;else{if(i+1<=n && (s[i+1]=='X' || s[i+1]=='V'))  res--;else    res++;}if(s[i]=='?')   ss++;}s[n+1]='I';s[0]='X';int ss1,ss2,ss3;for(int i=1;i<=n;i++){if(s[i]=='?'){int j=i;while(s[j]=='?')    j++;j--;int len=j-i+1;ss1=ss2=ss3=0;// cout<<i<<" "<<j<<'\n';if(s[i-1]=='I' && s[j+1]=='I'){ss1+=len/2+((len&1)?1:0);ss2+=(len&1)?0:1;ss3+=len-ss1-ss2;}else if(s[i-1]=='I'){ss1+=len/2;ss2+=(len&1);ss3=len-ss1-ss2;}else if(s[j+1]=='I'){ss1+=len/2;ss2+=(len&1);ss3+=len-ss1-ss2;}else{if(len&1){ss1=len/2;ss3=len-ss1;}else{ss1=len/2-1;ss2=1;ss3=len-ss1-ss2;}}// cout<<ss1<<" "<<ss2<<" "<<ss3<<'\n';s1+=ss1;s2+=ss2;s3+=ss3;// cout<<s1<<" "<<s2<<" "<<s3<<'\n';i=j;}}// cout<<s1<<" "<<s2<<" "<<s3<<'\n';// cout<<res<<'\n';ss1=s1,ss2=s2,ss3=s3;while(q--){int cx,cy,cz;cin>>cx>>cy>>cz;int ans=res;if(cz>=ss){cout<<ans<<'\n';continue;}s1=ss1,s2=ss2,s3=ss3;int now=ss-cz;if(cy<=now){now-=cy;if(cy>=s1){cy-=s1;ans+=s1*2;s1=0;}else{ans+=cy*2;s1-=cy;cy=0;}if(cy>=s2){cy-=s2;ans+=s2*4;s2=0;}else{ans+=cy*4;s2-=cy;cy=0;}if(cy>=s3){cy-=s3;ans+=s3*6;s3=0;}else{ans+=cy*6;s3-=cy;cy=0;}// cout<<"ok "<<ans<<'\n';if(now>=s1){now-=s1;ans+=s1*7;s1=0;}else{ans+=now*7;now-=s1;now=0;}if(now>=s2){now-=s2;ans+=s2*9;s2=0;}else{ans+=now*9;s2-=now;now=0;}if(now>=s3){now-=s3;ans+=s3*11;s3=0;}else{ans+=now*11;s3-=now;now=0;}cout<<ans<<'\n';}else{if(now>=s1){now-=s1;ans+=s1*2;s1=0;}else{ans+=now*2;s1-=now;now=0;}if(now>=s2){now-=s2;ans+=s2*4;s2=0;}else{ans+=now*4;s2-=now;now=0;}if(now>=s3){now-=s3;ans+=s3*6;s3=0;}else{ans+=now*6;s3-=now;now=0;}cout<<ans<<'\n';}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;for(int i=1;i<=T;i++){solve();}return 0;
}