比赛简述
ABC 中比较简单的一场，题目也都比较常规
A - Don’t be late
代码实现
#include <bits/stdc++.h>
using namespace std;
int main()
{
int d,t,s;
scanf("%d%d%d",&d,&t,&s);
printf("%s\n",t*s>=d ? "Yes" : "No");
return 0;
}
B - Substring
题目大意
给出两个串 $S$ 和 $T$，问 $S$ 至少替换多少字符可以使 $T$ 是 $S$ 的子串。
Tag: 暴力
简要题解
$S$ $T$ 长度都只有 1000，直接枚举 $T$ 的所有匹配位置即可。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int M=1005;
char s[M],t[M];
int main()
{
scanf("%s%s",s,t);
int n=strlen(s),m=strlen(t);
int ans=m;
for(int i=0;i+m<=n;i++)
{
int nans=0;
for(int j=0;j<m;j++)
nans+=(s[i+j]!=t[j]);
ans=min(ans,nans);
}
printf("%d\n",ans);
return 0;
}
C - Sum of product of pairs
题目大意
给出 $n$ 长数组 $A$ 求
求 $ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} A_{i} A_{j} $ 模 $(10^9 + 7)$
Tag: 前缀和
代码实现
#include <bits/stdc++.h>
using namespace std;
const int M=1005;
char s[M],t[M];
int main()
{
scanf("%s%s",s,t);
int n=strlen(s),m=strlen(t);
int ans=m;
for(int i=0;i+m<=n;i++)
{
int nans=0;
for(int j=0;j<m;j++)
nans+=(s[i+j]!=t[j]);
ans=min(ans,nans);
}
printf("%d\n",ans);
return 0;
}
D - Friends
题目大意
给出 $n$ 个人，$m$ 组朋友关系，朋友关系可传递，问至少分多少组，可以使得每组中的人彼此都不是朋友。
Tag: 并查集
简要题解
显然可以用并查集维护各个朋友圈子的大小，答案最终为最大的圈子。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int M=1005;
char s[M],t[M];
int main()
{
scanf("%s%s",s,t);
int n=strlen(s),m=strlen(t);
int ans=m;
for(int i=0;i+m<=n;i++)
{
int nans=0;
for(int j=0;j<m;j++)
nans+=(s[i+j]!=t[j]);
ans=min(ans,nans);
}
printf("%d\n",ans);
return 0;
}
E - Coprime
[AtCoder] Beginner Contest 177 E - CoprimeE - Coprime
题目大意
给出数组 $A$ 如果其中数字两两互质则返回 “pairwise coprime”，如果整个数组 $gcd$ 为 $1$ 则返回 “setwise coprime”，其他情况返回 “not coprime”
简要题解
显然 setwise 很好判断。
对于 pairwise 可以将每个数分解因数，则任意 $A_{i}$ 不和其他的任何项有相同的质因子，于是统计 $A$ 中所有的质因子频率，之后判断 $A_{i}$ 与其他因子频率的关系即可。
这里数组长度 $n \le 10^6$ 比较大，于是采用挂链分解的方式。
复杂度
$T$：$O(C + nlogC)$ 其中 $C \le 10^6$ 为 $A_{i}$ 的范围
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;
int a[M];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int isp[M],pri[M],pre[M],npri=0;
void get_pri()
{
for(int i=2;i<M;i++)
{
if(!isp[i])
{
pre[i]=i;
pri[npri++]=i;
}
for(int j=0;j<npri&&pri[j]*i<M;j++)
{
isp[i*pri[j]]=1;
pre[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
}
}
}
vector<int> get_factor(int nu)
{
vector<int> fa;
if(nu==1) return fa; // fa.push_back(1);
while(nu!=1)
{
fa.push_back(pre[nu]);
nu/=pre[nu];
}
return fa;
}
int cnt[M],cnt2[M];
int main()
{
get_pri();
int n; scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
vector<int> fas=get_factor(a[i]);
for(int i:fas)
cnt[i]++;
}
int f=1;
for(int i=0;i<n;i++)
{
vector<int> fas=get_factor(a[i]);
for(int i:fas)
cnt2[i]++;
for(int i:fas)
if(cnt2[i]<cnt[i])
{
// cout<<i<<" "<<cnt[i]<<" "<<cnt2[i]<<endl;
f=0;
break;
}
if(f==0) break;
for(int i:fas)
cnt2[i]--;
}
if(f)
{
printf("pairwise coprime\n");
return 0;
}
int g=a[0];
for(int i=1;i<n;i++)
g=gcd(g,a[i]);
printf("%s\n",g==1 ? "setwise coprime" : "not coprime");
return 0;
}
F - I hate Shortest Path Problem
[AtCoder] Beginner Contest 177 F - I hate Shortest Path ProblemF - I hate Shortest Path Problem
题目大意
给出一个 $(h+1) \times w$ 的二维矩阵，初始位置可以是第 $0$ 行的任意位置。
每一个格只能往右或下方向移动
每一行 $i$ 区间 $L_{i}$ 到 $R_{i}$ 的格子不能向下走，问到达每一行的最小可能步数
简要题解
$dp[i][j]$ 为到达 $(i,j)$ 位置的最小步数
注意从左侧走到某个格子总不会比从上方走来更好，除非无法从上方走来
$$ \begin{align} dp[i][j] & = dp[i-1][j]+1 & j \lt L[i-1] \ or \ R[i-1] \lt j \\ & = dp[i-1][L[i-1]-1]+1+(j-(L[i-1]-1)) & L[i-1] \le j \le R[i-1] \end{align} $$会发现 $dp$ 转移都是以区间为单位的，且对应操作都可以用线段树维护
复杂度
$T$：$O((h + w) \log (w))$
$S$：$O(w)$
代码实现
#include <bits/stdc++.h>
using namespace std;
/*
dp[i][j]=dp[i-1][j]+1; (j<L[i-1] or R[i-1]<j)
dp[i][j]=dp[i-1][L[i-1]-1]+1+(j-(L[i-1]-1)) (L[i-1]<=j<=R[i-1])
*/
const int M=2e5+5;
const int INF=0x3f3f3f3f;
struct SegT
{
struct TN
{
int mn,fi,add;
void app_add(int v)
{
add+=v;
mn+=v;
}
void app_set(int v) // arthimic
{
add=0;
fi=v;
mn=v;
}
}tn[M*4];
int P,L,R,V;
void push(int o,int l,int mi,int r)
{
if(tn[o].fi!=-1)
{
tn[o<<1].app_set(tn[o].fi);
tn[o<<1|1].app_set(tn[o].fi+mi-l+1);
tn[o].fi=-1;
}
if(tn[o].add)
{
tn[o<<1].app_add(tn[o].add);
tn[o<<1|1].app_add(tn[o].add);
tn[o].add=0;
}
}
void pull(int o)
{
tn[o].mn=min(tn[o<<1].mn,tn[o<<1|1].mn);
}
void build(int o,int l,int r)
{
tn[o].mn=tn[o].add=0;
tn[o].fi=-1;
if(l==r)
{
if(l==0) tn[o].mn=tn[o].add=INF;
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pull(o);
}
void add(int o,int l,int r)
{
if(L<=l&&r<=R)
{
tn[o].app_add(1);
return;
}
int mid=(l+r)>>1;
push(o,l,mid,r);
if(L<=mid) add(o<<1,l,mid);
if(mid<R) add(o<<1|1,mid+1,r);
pull(o);
}
void set(int o,int l,int r)
{
if(L<=l&&r<=R)
{
tn[o].app_set(V+l-L+1);
return;
}
int mid=(l+r)>>1;
push(o,l,mid,r);
if(L<=mid) set(o<<1,l,mid);
if(mid<R) set(o<<1|1,mid+1,r);
pull(o);
}
int query(int o,int l,int r)
{
if(l==r) return tn[o].mn;
int mid=(l+r)>>1;
push(o,l,mid,r);
if(P<=mid) return query(o<<1,l,mid);
else return query(o<<1|1,mid+1,r);
}
}segt;
int main()
{
int h,w; scanf("%d%d",&h,&w);
segt.build(1,0,w);
int l,r;
for(int i=0;i<h;i++)
{
scanf("%d%d",&l,&r);
if(l!=1)
{
segt.L=1; segt.R=l-1;
segt.add(1,0,w);
}
if(r!=w)
{
segt.L=r+1; segt.R=w;
segt.add(1,0,w);
}
segt.P=l-1;
segt.V=segt.query(1,0,w);
segt.L=l; segt.R=r;
segt.set(1,0,w);
int ans=segt.tn[1].mn;
printf("%d\n",ans>=INF ? -1 : ans);
}
return 0;
}
Next: [AtCoder] Beginner Contest 177 E - Coprime