Portal：https://www.luogu.com.cn/contest/200833
A - もしも
容易发现可以构造\(1,x\)或\(x,1\)让序列如\(\dots,1,x,1,x,1,x,\dots\)这样循环。只需要关注\(n\)的奇偶性即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,an;
signed main(){
cin>>t;
while(t--){
cin>>n>>an;
if(n&1) cout<<an<<" "<<1<<"\n";
else cout<<1<<" "<<an<<"\n";
}
return 0;
}
B - さよならワンダーランド
根据题意，我们找到的\(j\)需要满足：
- \(j\ge 1-i\)
- \(j\le n-i\)
- \(j\ge a_i\)
- \(j\le a_{i+j}\)
其中前\(3\)项都是静态的，与\(j\)无关的，所以我们在前\(3\)项限制的范围\([l,r]\)内寻找\(j\)使得\(j\le a_{i+j}\)即可，这也是此题的关键点。
我们记\(b_i=a_i-i\)，那么
\(a_{i+j}\ge j\)
\(\iff [\max\limits_{j\in [l,r]}a_{i+j}-j]\ge 0\)
\(\iff [\max\limits_{j\in [l,r]}a_{i+j}-(i+j)]\ge (-i)\)
\(\iff \max\limits_{j\in [l,r]}b_{i+j} \ge (-i)\)
因此我们仅需用ST表维护出\(b\)的区间最大值，然后查找是否存在就直接看最后那个式子是否成立；查找具体位置我直接用的二分，如果\([l,mid]\)成立，那么左边一定存在合法的\(j\)（不是说右边没有），否则\(j\)一定在右边。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 300010
using namespace std;
int n,a[N],f[N][30],lg[N];
void init(){
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
for(int i=1;i<=lg[n];i++){
for(int j=1;j+(1<<i)-1<=n;j++){
f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
}
int query(int l,int r){
if(r<l) return LLONG_MIN;
int len=lg[r-l+1];
return max(f[l][len],f[r-(1<<len)+1][len]);
}
int modi(int a){
return min(max(1ll,a),n);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][0]=a[i]-i;
}
init();
for(int i=1;i<=n;i++){
int l=max(a[i],1-i),r=n-i;
if(query(i+l,i+r)>=-i){
while(l<r){
int mid=(l+r)>>1;
if(query(i+l,i+mid)>=-i) r=mid;
else l=mid+1;
}
cout<<"1 "<<l<<"\n";
}else cout<<"0\n";
}
return 0;
}