题目链接
https://codeforces.com/gym/104354
A. 小水獭游河南
签到题。
初看有点吓人，跟回文串有关，会不会是PAM啥的，然后是大水题。。。
容易发现A串的约束非常强，没有重复字符，意味着A串的长度最大也就是26。我们枚举A串，同时看剩余的后缀是不是回文串就行了。
时间复杂度\(\Theta(26n)\)
代码:
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 100010
using namespace std;
char s[maxn];
int c[26];
int check(int l,int r){
int flag=1,i,j;
for(i=l,j=r;i<=j;++i,--j){
if(s[i]!=s[j]){
flag=0;
break;
}
}
return flag;
}
int main(){
int i,j,n,T,flag,k;
char last;
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%s",s);
flag=0;
for(i=0;i<26;++i) c[i]=0;
n=strlen(s);
last=s[n-1];
for(i=0;i<n;++i){
if(i>0&&s[i]==last){
if(check(i,n-1)){
flag=1;break;
}
}
c[s[i]-'a']++;
if(c[s[i]-'a']>1) break;
}
if(flag) printf("HE\n");
else printf("NaN\n");
}
return 0;
}
B. Art for Rest
实现很简单，但是感觉还是难以一眼看出做法，不知道为啥过的人这么多。
考虑暴力，我们直接枚举块长，然后对于已经分好块的数组，检验是否满足条件。
当然模拟排序过程是不可取的，我们不如考虑什么情况下不可能满足条件。
简单思考一下发现，块必须是块间“整体有序”的，也就是说，如果我们一个一个块扫过去，不能出现当前块中某个值比前面块中某个值小的情况。
然后我们只要维护前缀最大值，查询区间最小值，比较即可。
由于数据较大，推荐使用\(O(1)\) 查询的ST表实现RMQ。
等等，你外面不还有一层循环吗，总共两层循环复杂度珂以接受吗？
注意到我们内层循环的次数是\(\lfloor \frac{n}{k}\rfloor\)的，根据调和级数求和的结论知：最终复杂度是\(\Theta(n log n)\)的。
代码：
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 1000010
using namespace std;
int a[maxn];
int mx[maxn],mn[maxn][26];
int log_2[maxn];
int query(int l,int r){
int i=log_2[r-l+1];
return min(mn[l][i],mn[r-(1<<i)+1][i]);
}
int main(){
int i,j,n,m;
int ans=0;
// freopen("test.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d",&a[i]);
for(i=1;i<=n;++i) mn[i][0]=a[i];
log_2[1]=0;
for(i=2;i<=n;++i) log_2[i]=log_2[i>>1]+1;
for(i=1;i<=log_2[n];++i){
for(j=1;j+(1<<i)-1<=n;++j){
mn[j][i]=min(mn[j][i-1],mn[j+(1<<i-1)][i-1]);
}
}
for(i=1;i<=n;++i) mx[i]=max(mx[i-1],a[i]);
for(i=1;i<=n;++i){
int flag=1;
for(j=1;j<=n;j+=i){
int l=j,r=min(j+i-1,n);
int t=query(l,r);
if(t<mx[j-1]){
flag=0;
break;
}
}
ans+=flag;
}
printf("%d",ans);
return 0;
}
F. Art for Last
简单题。
注意到结果只与集合有关，与顺序无关，所以我们可以先排好序。
然后观察到最优结果必然是取连续一段（排序后的数组），最大差值就是区间头尾之差，最小差值一定在相邻两个元素间取到。
所以做下差分，在差分数组里找区间最小值即可。
至于为啥一定取连续区间，反证法很好证。
时间复杂度\(\Theta(n log n)\)。
代码：
点击查看代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 500010
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int a[maxn];
int v[maxn<<2],l[maxn<<2],r[maxn<<2];
void update(int x){
v[x]=min(v[x<<1],v[x<<1|1]);
}
void build(int x,int left,int right){
l[x]=left,r[x]=right;
if(left==right){
v[x]=abs(a[left+1]-a[left]);
return;
}
int mid=left+right>>1;
build(x<<1,left,mid);
build(x<<1|1,mid+1,right);
update(x);
}
int query(int x,int left,int right){
int r1=inf,r2=inf;
if(l[x]>=left&&r[x]<=right) return v[x];
int mid=l[x]+r[x]>>1;
if(left<=mid) r1=query(x<<1,left,right);
if(right>mid) r2=query(x<<1|1,left,right);
return min(r1,r2);
}
int main(){
int i,j,n,T,flag,k;
ll ans=-1;
// freopen("test.in","r",stdin);
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
for(i=2;i<=n;++i){
if(a[i]==a[i-1]){
printf("0");
return 0;
}
}
build(1,1,n-1);
for(i=k;i<=n;++i){
ll val=(ll)(a[i]-a[i-k+1])*(ll)query(1,i-k+1,i-1);
if(ans<0) ans=val;
ans=min(ans,val);
}
printf("%lld",ans);
return 0;
}