2024 首个 AK 的比赛，祭。
Water
分析
注意到答案一定是 \(b\) 的倍数，那么究竟是多少倍呢？如果 \(\lfloor\frac{a}{b}\rfloor<n\) 那么可以达到的就是比 \(a\) 小的最大 \(b\) 的倍数，否则是 \(n\times b\)。
Line
分析
注意到本题答案 \(ans \in\{0,1,2\}\)，且如果 \(x_c\in\{x_a,x_b\}\)，把 \(CD\) 向上平移就可以相交，平移 \(AB\) 同理。
如果两个条件，即 \(x_c\in\{x_a,x_b\}\) 与 \(y_a\in\{y_c,y_d\}\)，都成立，两线段相交，答案为 \(0\)。
假如都不成立，需要移动两次，直到两条线段都过同一个点。
代码就不放了。
Reverse and Rotate
分析
2024 第一场 AK 的比赛，祭。
不难发现一点，不管如何操作，最终得到的串一定可以表示为原串翻转或不翻转后向右移动若干位。考虑维护是否翻转，与最后移动多少位。
是否翻转直接用 rev 的数量统计。移动的位数也好分析，我们提出以下几个结论：
- 向右移动 \(m\) 位相当于向右移动 \(m \bmod |S|\) 位。
- 向左移动 \(m\) 位（\(0\le m\le |S|\)）相当于向右移动 \(m-|S|\) 位。
- 翻转后向右移动 \(m\) 位相当于向左移动 \(m\) 位再翻转。
前两个非常好证，至于最后一个，我们考虑把 \(S\) 扩展为一个无限长的串，以 abcde 为例，那么把它看成串 ...abcdeabcdeabcde... 中间的 \(5\) 个字母，如果你翻转后再向右移动 \(m\) 位，其实你从背面（感性理解一下）看就是向左移动了 \(m\) 位，从背面看本质上是翻转操作，因此结论 \(3\) 是成立的。
那么这就非常好办了，引入变量 \(p\) 表示向右移动多少位，遇到 rev 就 \(p\leftarrow |S|-p\)，否则按照结论 \(1,2\) 的来做。
AC Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
int n,flag=0,p=0;
cin>>s>>n;
while(n--)
{
string opt;
cin>>opt;
if(opt=="rev") flag^=1,p=s.size()-p;
else if(opt=="<")
{
int m;
cin>>m;
m%=s.size();
p+=s.size()-m;
p%=s.size();
}
else
{
int m;
cin>>m;
m%=s.size();
p+=m;
p%=s.size();
}
}
if(flag) for(int i=0;i<s.size()/2;i++) swap(s[i],s[s.size()-1-i]);
if(!p) cout<<s;
else
cout<<s.substr(s.size()-p,p)+s.substr(0,s.size()-p);
return 0;
}
Choose
分析
2024 第一场 AK 的比赛，祭。
我们首先很容易发现一点，当子段长度为 \(L_0\) 时，必定不比长度小于 \(L_0\) 时的最小极差小，因此如果我们想最大化这个最小极差 \(X\)，我们需要找到最大子段长度 \(L_0\)，由于有子段数量限制 \(k\)，因此 \(L_0=n+1-k\)。所以，取每一个长度为 \(L_0\) 的子段的极差的最小值，就是我们要求的最大 \(X\)。实现的话，可以使用 \(O(1)\) 查询的 ST 表。
下一步考虑如何求 \(L\)。由于求的是最小的 \(L\)，且没有什么好的线性求法（至少我没想到），所以应该是二分。二分（不加 check）的复杂度为 \(O(\log n)\)（最大的长度仅有 \(L_0=n+1-k\)），因此 \(O(n)\) 的 check 是可以的。枚举所有长为 \(L\) 的子段，判断是否有 \(k\) 个子段的极差大于等于 \(X\) 即可。
赛时代码比较乱，加点注释。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int lg[100010],st[100010][22],st2[100010][22],n,k,x;
int check(int len,int jc)
{
int tp=0;
for(int i=1;i+len-1<=n;i++)
{
if(max(st[i][lg[len]],st[i+len-1-(1<<lg[len])+1][lg[len]])-min(st2[i][lg[len]],st2[i+len-1-(1<<lg[len])+1][lg[len]])>=jc) tp++;
//ST表求出最大值减去最小值，tp是极差大于X的子段数量
}
if(tp>=k) return 1;
return 0;
}
void solve()
{
mp.clear();
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>st[i][0],st2[i][0]=st[i][0];
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
//ST表预处理
x=2e9;
for(int i=1;i<=k;i++) x=min(x,max(st[i][lg[n-k+1]],st[i+n-k-(1<<lg[n-k+1])+1][lg[n-k+1]])-min(st2[i][lg[n-k+1]],st2[i+n-k-(1<<lg[n-k+1])+1][lg[n-k+1]]));
//X为每个长度为L0=n-k+1的子段的极差最小值
cout<<x<<' ';
int l=1,r=n+1-k,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid,x))
{
r=mid;
}
else l=mid+1;
}//二分
cout<<l<<endl;
}
signed main()
{
lg[1]=0;lg[2]=1;
for(int i=3;i<=1e5;i++) lg[i]=lg[i/2]+1;
//ST表预处理
int t;
cin>>t;
while(t--) solve();
return 0;
}