CF比赛题解(简单题)
简单题是指自己在比赛期间做出来了
A. Many Equal Substrings
题意
- 给个字符串t,构造一个字符串s，使得s中t出现k次;s的长度最短
- 如t="cat",k=3, minlen(s)=9,s=catcatcat
- 1<=len(t),k<=50
题解
- 稍加思考是个前缀等于后缀的问题,用kmp的next数组模板
- 假设t[0..l-1]==t[n-l....n-1]
- 那么应该不断重复t[l...n-1]这样的子串
- 代码如下(应该好好记住kmp模板，自己还有点慌张)
#include<bits/stdc++.h>
int n,k;
char t[52];
int next[52];
char tar[2510];
//前缀和后缀相等
void kmp_next(int m,char x[]){
int i,j;
j=next[0]=-1;
i=0;
while(i<m){
while(-1!=j &&x[i]!=x[j]) j=next[j];
next[++i]=++j;
}
}
void db(){
printf("db:
");
for(int i=0;i<=n;i++){
printf("%d ",next[i]);
}
}
int main(){
scanf("%d %d",&n,&k);
scanf("%s",t);
kmp_next(n,t);
int prefix=next[n];//[0..prefix-1] == [n-1-prefix+1,n-1]
//repeat [prefix...n-1]
//printf("db pre:%d
",prefix);
int q=0;
for(int i=0;i<prefix;i++){
tar[i]=t[i];
q++;
}
for(int j=0;j<k;j++){
for(int m=prefix;m<n;m++){
tar[j*(n-prefix)+m]=t[m];
q++;
}
}
tar[q]=' ';
printf("%s
",tar);
return 0;
}
B. Creating the Contest
题意
- 从单调增数组a[]选取子序列b[],满足b[i]*2>=b[i+1],最大化子序列长度
- 需要稍加分析，即通过a[j+1]>2*a[j]这样的条件将a[]分成几段，选取最长一段即可
- cf似乎常常中意这些稍加思考问题变得简单的题目呢
代码
#include<bits/stdc++.h>
int a[200010];
int n;
int solve(){
int res=1;
int b=1;
for(int i=2;i<=n;i++){
if(a[i]>2*a[i-1]){
res=std::max(i-b,res);
b=i;
}
}
res=std::max(n+1-b,res);
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
printf("%d",solve());
return 0;
}
C. Maximal Intersection
题意
- 给出[ai,bi]这样的线段n条，求删除一条后使得剩下(n-1)条线段重叠区域最长
- n<=3*1e5
- 思考线段重叠区域min(bi)-max(ai),考虑删除后的影响可以得到这样的方案
- 排序a[],b[],记作sa[],sb[],遍历之前的每一条边，处理这样情况
代码
#include<bits/stdc++.h>
const int maxn=300010;
int x1[maxn],x2[maxn];
int a[maxn],b[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x1[i],&x2[i]);
a[i]=x1[i];b[i]=x2[i];
}
std::sort(x1+1,x1+1+n);
std::sort(x2+1,x2+1+n);
int maxv=0;
for(int i=1;i<=n;i++){
int max1=x1[n];
int min2=x2[1];
if(a[i]==max1) max1=x1[n-1];
if(b[i]==min2) min2=x2[2];
//printf("db %d %d %d
",max1,min2,min2-max1);
maxv=std::max(min2-max1,maxv);
}
printf("%d
",maxv);
return 0;
}
感想
- 成为了3题选手,也没有fst,虽然是div3,但毕竟涨rating,自己还是太渣
- cf的数据真的很严格，边界一定会照顾到，一定要算时间复杂度
- 继续努力吧
- div3可以在赛后时间Hack,div1/div2只能在比赛时Hack;自己还没尝试hack滋味