AtCoder Beginner Contest 177 题解
A - Don't be late
问你能不能在时间(T)内用不高于(S)的速度走过(D)的路程，转化为判断(S imes T)不小于(D)即可。
#include<bits/stdc++.h>
using namespace std;
int d,s,t;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>d>>t>>s;
cout<<(t*s>=d?"Yes":"No");
return 0;
}
B - Substring
给你两个字符串(S)和(T)，保证(S)不短于(T)。问你在(S)中任意截取一个长度和(T)相同的子串（子串指原字符串中一段连续的字符，特别地，空串和原字符串也是原字符串的子串），在这个字符串中最少要修改多少个字母才能和(T)相同。
枚举截取的字符串位置即可。
#include<bits/stdc++.h>
using namespace std;
string s,t;
int n,m,a=1e9;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s>>t;
n=s.size();m=t.size();
for(int i=0;i+m<=n;i++){
int c=0;
for(int j=0;j<m;j++)c+=s[i+j]!=t[j];
a=min(a,c);
}
cout<<a<<endl;
return 0;
}
C - Sum of product of pairs
给你一个序列，要求你把其中的数字两两相乘，输出得到的所有乘积的和。
我们从序列中从前到后枚举一个数字，把它和前面的所有数分别相乘，并把这些乘积加到答案里，就可以不重复的算出答案（此时一种数对的相乘结果只被计算了一次）。根据乘法分配律，这相当于乘上前面所有数的和，然后就可以维护一个前缀和，加速求解。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a,ans,pre;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
ans=(ans+(long long)pre*a)%mod;
pre=(pre+a)%mod;
}
cout<<ans<<endl;
return 0;
}
D - Friends
给你一张无向图，要求划分成一些集合，使得集合内的点两两不能达到。输出最小集合数。
首先可以证明集合数的数量不少于最大的连通块的点的个数，因为每个点需要被单独地划分出来。
然后可以证明这些集合足够存放所有的点，因为不同连通块之内的点可以被放进同一个集合里，因此可以把它们相互独立地考虑。而一个连通块需要的集合数不会超过最大的连通块需要的集合数。
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[200005];
int sz;
bool vis[200005];
void dfs(int x){
vis[x]=1;
sz++;
for(int &y:g[x])if(!vis[y]){
dfs(y);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
static int u,v;
cin>>u>>v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int ans=0;
for(int i=1;i<=n;i++)if(!vis[i]){
sz=0;
dfs(i);
ans=max(ans,sz);
}
cout<<ans<<endl;
return 0;
}
E - Coprime
给你一个整数序列，判断是否两两互质，整个序列互质（整个序列的公因数为(1)），或者不满足先前两种情况。
首先先判断是否整个序列互质，这个单独判断方便一点，就求出整个序列的最大公因数。
那么再判断是否两两互质，我们对每个数分解质因数，记录它包含了哪些质因子（不论那个质因子被乘了多少次）。假如有多于一个的数包含同一个质因子，那么这个序列就不是两两互质的。
#include<bits/stdc++.h>
using namespace std;
inline int gcd(int a,int b){
while(b){
a=a%b;
swap(a,b);
}
return a;
}
int n,a[1000005],u[1000005];
int main(){
scanf("%d",&n);
int g=0;
for(int i=1;i<=n;i++){
scanf("%d",a+i);
g=gcd(g,a[i]);
for(int j=2;j*j<=a[i];j++){
if(a[i]%j==0){
u[j]++;
while(a[i]%j==0)a[i]/=j;
}
}
u[a[i]]++;
}
if(g>1){
cout<<"not coprime
";
return 0;
}
for(int i=2;i<=(int)1e6;i++){
if(u[i]>1){
cout<<"setwise coprime
";
return 0;
}
}
cout<<"pairwise coprime
";
return 0;
}
F - I hate Shortest Path Problem
给你一个高(H+1)，宽(W)的矩形，第(i)行第(A_i)个位置到第(B_i)个位置下方有挡板，特别地，底部的一行下方没有挡板。
你可以从顶部一行的任意一个位置开始行动，每一步可以向下或向右走一格，要求不能走出矩形或者穿过挡板。问你走到第(2, 3, dots, H)行各最少需要多少步，无法达到输出-1。
我们首先需要观察到，除了起始位置的选择不一定尽量靠前外，否则能向下走就直接向下走，不然向右走一格，再尝试向下走，这么持续下去一定是最优的一种考虑。
我们可以模拟走到某一行某一个位置最少需要多少步。
为了维护方便，我们反向考虑如何走到这个格子。这个格子一定是上一个格子向右移动了某些步数（可能移动零步），然后向下移动一格走到的。向下移动后，我们不需要考虑再向右移动的情况了。因为在转移到下一行时，之前描述的“向右移动了某些步数，然后向下移动一格”包含了这个情况。同时这样也可以保证对此行答案的贡献最优。
我们可以考虑使用数据结构来优化。那么此时我们需要分类一下：
- 对于上方没有挡板的格子，我们可以直接从上向下转移，假如这个走法不是最优的，可以证明它对答案没有影响。
- 对于上方有挡板的格子，直接把它的答案设成正无穷大，因为无法走到。假如这个走法不是最优的，也可以证明它对答案没有影响。
- 对于左上方有挡板的格子，可以从上方的格子所有左边的格子转移来。
感性理解，每一个格子继续行动时，它的贡献一定会通过以上三种转移方式继续向下传下去，所以可以保证是最优的。
然后我们就可以使用两棵线段树维护了，假如我们定义当前行的位置(i)的答案为(ans_i)，一棵维护真实的最小值(ans_i)，一棵维护(ans_i+W-i)，用于做第三种更新。需要先做第三种更新，因为我们此时的转移都做在同一个线段树内，顺序会相互影响。
#include<bits/stdc++.h>
using namespace std;
struct SegTree{
int sz;
vector<long long> dat,laz;
SegTree(){
sz=1<<18;
dat.resize(sz<<1);
laz.resize(sz<<1);
};
void upd(int id,int l,int r,int ql,int qr,long long val){
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr){
laz[id]+=val;
dat[id]+=val;
return;
}
laz[id<<1]+=laz[id];
dat[id<<1]+=laz[id];
laz[id<<1|1]+=laz[id];
dat[id<<1|1]+=laz[id];
laz[id]=0;
upd(id<<1,l,l+r>>1,ql,qr,val);
upd(id<<1|1,(l+r>>1)+1,r,ql,qr,val);
dat[id]=min(dat[id<<1],dat[id<<1|1]);
}
long long qry(int id,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 1e18;
if(ql<=l&&r<=qr){
return dat[id];
}
laz[id<<1]+=laz[id];
dat[id<<1]+=laz[id];
laz[id<<1|1]+=laz[id];
dat[id<<1|1]+=laz[id];
laz[id]=0;
return min(qry(id<<1,l,l+r>>1,ql,qr),qry(id<<1|1,(l+r>>1)+1,r,ql,qr));
}
void upd(int l,int r,long long d){
upd(1,1,sz,l,r,d);
}
long long qry(int l,int r){
return qry(1,1,sz,l,r);
}
};
int n,m;
int a[200005],b[200005];
SegTree upd,qry;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)upd.upd(i,i,m-i);
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
qry.upd(b[i]+1,b[i]+1,min(upd.qry(1,b[i])-(m-b[i]-1)-qry.qry(b[i]+1,b[i]+1),0ll));
upd.upd(b[i]+1,b[i]+1,min(upd.qry(1,b[i])-upd.qry(b[i]+1,b[i]+1),0ll));
qry.upd(a[i],b[i],1e9);
upd.upd(a[i],b[i],1e9);
qry.upd(1,m,1);
upd.upd(1,m,1);
if(qry.qry(1,m)>=1e9)cout<<"-1
";
else cout<<qry.qry(1,m)<<'
';
}
return 0;
}