Preface
明天的CF一定打啊（绝对不咕），今天白天补现代作业，英语作业到哭，而且还要准备四六级，每天逼着自己背单词
A. Mainak and Array
不难发现换中间的数不会影响答案，因此操作的区间只可能是\([1,k],[k,n](k\in [1,n])\)，讨论一下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
int ans=-2000; for (a[n+1]=a[1],i=1;i<=n;++i) ans=max(ans,a[i]-a[i+1]);
int cur=0; for (i=2;i<=n;++i) cur=max(cur,a[i]); ans=max(ans,cur-a[1]);
for (cur=1000,i=1;i<n;++i) cur=min(cur,a[i]); ans=max(ans,a[n]-cur);
printf("%d\n",ans);
}
return 0;
}
B. Mainak and Interesting Sequence
考虑以下构造法，设\(p=\lfloor\frac{m}{n}\rfloor,q=m\bmod n\)，开始时先把所有数赋值成\(p\)，然后分类讨论：
- \(n\)为奇数，则此时我们可以任选一个\(a_i\)将其加上\(q\)以满足题意
- \(n\)为偶数且\(q\)为偶数，则此时我们可以任选两个\(a_i\)，将其各加上\(\frac{q}{2}\)以满足题意
- \(n\)为偶数且\(q\)为奇数，不难发现此时无解
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,m,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%d%d",&n,&m); int p=m/n,q=m%n;
if (n>m||((n&1)==0&&(q&1))) { puts("No"); continue; }
for (puts("Yes"),i=1;i<=n;++i) a[i]=p;
if (n&1) a[n]+=q; else a[n-1]+=q/2,a[n]+=q/2;
for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
}
return 0;
}
C. Jatayu's Balanced Bracket Sequence
看到括号序列先来个前缀和，把(看作1，)看作-1，设其前缀和为\(pfx_i\)
考虑一个区间\([l,r]\)时合法的括号序列当且仅当：
- \(a_l\)是左括号，\(a_r\)是右括号
- \(pfx_{l-1}=pfx_r\)且\([l,r]\)中没有比\(pfx_r\)小的元素
考虑到后面一个条件较难满足，我们考虑每次对于一个右括号\(a_i\)找出距它最近的且\(pfx_{j-1}=pfx_i\)的左括号\(a_j\)
不难发现此时\(pfx_k,k\in[j,i]\)中一定没有小于\(pfx_j\)的元素，否则\(j\)就不是最近的了
但是配对的时候不能仅仅把\(i,j\)配对了，我们还要考虑检查\(a_{j-1}\)是不是一个合法的右括号
若是，因为\(pfx_{j-1}=pfx_i\)，因此\(a_{j-1}\)可配对的括号\(a_i\)也一定可以配对，因此直接把\(i,j-1\)配对即可
用并查集维护连通块信息即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],fa[N],cur,pre[N],ans; bool vis[N];
inline int getfa(CI x)
{
return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; char ch;for (scanf("%d",&n),n<<=1,i=0;i<=n;++i) fa[i]=i,pre[i]=-1,vis[i]=0;
for (cur=0,i=1;i<=n;++i)
{
while (ch=getchar(),ch!='('&&ch!=')'); a[i]=ch=='('?1:-1;
if (a[i]==1) pre[cur]=i,cur+=a[i]; else
{
cur+=a[i]; if (~pre[cur])
{
vis[i]=1; fa[getfa(i)]=getfa(pre[cur]);
if (pre[cur]&&vis[pre[cur]-1]) fa[getfa(i)]=getfa(pre[cur]-1);
}
}
}
for (ans=0,i=1;i<=n;++i) ans+=getfa(i)==i; printf("%d\n",ans);
}
return 0;
}