这次手慢了一点AC前3题只有+20。或者说一个重要原因是第一题看错了题 WA 了两发。
A. XXXXX
这题我和许多人一样把 Subarray 看成了 Subsequence，于是惨遭两发 WA。它要求求出连续子序列。我们分类讨论。答案是 -1 当且仅当里面全部都是 x 的倍数。如果 (sum a_i) 不是 (x) 的倍数，那么直接输出 (n)。如果是，题面已经给了提示，我们需要从左往右或从右往左删除一些数使得 (sum a_i) 减去删除的数的和不是 (x) 的倍数，也就是需要找到从左往右和从右往左的第一个非 (x) 倍数的数即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100009],cnt[10009];
signed main(){
int T; cin>>T;
while(T--){
memset(cnt,0,sizeof(cnt));
int n,x,sum=0; cin>>n>>x;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),cnt[a[i]%x]++,sum+=a[i]%x;
if(cnt[0]==n){puts("-1");continue;}
else if(sum%x!=0){printf("%lld
",n);continue;}
int l=1,r=n;
for(;l<=n;l++) if(a[l]%x!=0) break;
for(;r>=1;r--) if(a[r]%x!=0) break;
printf("%lld
",max(n-l,r-1));
}
return 0;
}
B. Most socially-distanced subsequence
显然要使答案最大肯定是全选。所以我们考虑怎么选出最少的数。
对于一个单调区间 ([l,r])，(sumlimits_{i=l+1}^{r} |a_i-a_{i-1}|=a_r-a_l)，所以对于每个单调区间选头尾即可。
#include<bits/stdc++.h>
using namespace std;
int a[100009];
int main(){
int T; cin>>T;
while(T--){
int n; scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int cnt=0;
cnt++;
for(int i=2;i<n;i++) if((a[i]-a[i-1]>0)!=(a[i+1]-a[i]>0)) cnt++;
cnt++; printf("%d
",cnt);
printf("%d ",a[1]);
for(int i=2;i<n;i++) if((a[i]-a[i-1]>0)!=(a[i+1]-a[i]>0)) printf("%d ",a[i]);
printf("%d
",a[n]);
}
return 0;
}
C. Ehab and Prefix MEXs
由于这个 Mex 不大于 1e6，而且是单调不降的，所以我们对于 (1le ile n)，枚举这个要取的 Mex。又因为不可能有-1，所以直接填数即可。
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int cnt[1000009],a[100009],b[1000000],mex,s[N],t;
int main(){
int n; cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=1000000;
for(int i=1;i<=1000000;i++) b[i]=-114514;
for(int i=1;i<=n;i++){
s[++t]=i;
for(int j=max(mex,0);j<=a[n+1];j++){
if(cnt[j]==0&&j<a[i]){
if(t!=0) cnt[b[s[t--]]=j]++;
else{return puts("-1"),0;} //其实这是不会发生的
}else if(cnt[j]==0&&j>=a[i]){mex=j;break;}
}
}
for(int i=1;i<=n;i++) printf("%d ",(b[i]==-114514)?n+1:b[i]);
return 0;
}
D. Ehab's Last Corollary
对于 (k=n) 的情况很显然。如果 (m=n-1) 那么就是棵树，做树的最大独立集即可。如果不是树就意味着一定有一个环，找环即可。
对于 (k<n) 的情况，善于阅读的你一定发现了题目中有一段作者的话：
I have a proof that for any graph you can always solve at least one of these problems, but it's left as an exercise for the reader.
首先我根本不会证明这玩意儿…… 这说明什么？我们取一个大小为 (k) 的连通子图，我们也可以得到解！所以我们只需要取一个大小为 (k) 的连通子图然后做 (k=n) 的情况即可。