【题解】ABC177
A
语法题
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int main(){
double d,t,s;
cin>>d>>t>>s;
if(s*t>=d)cout<<"Yes";
else cout<<"No";
return 0;
}
B
暴力枚举
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
string s;
string t;
int main(){
cin>>s;
cin>>t;
int slen=s.length();
int tlen=t.length();
int ans=999999;
for(int i=0;i<=slen-tlen;i++){
int cnt=0;
for(int j=0;j<tlen;j++){
if(s[i+j]!=t[j]){
cnt++;
}
}
ans=min(ans,cnt);
}
cout<<ans<<endl;
return 0;
}
C
可以用后缀和加速求和。
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
int n;
long long a[200005];
long long lsum[200005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){
lsum[i]=a[i]+lsum[i+1];
lsum[i]%=inf;
}
long long ans=0;
for(int i=1;i<=n;i++){
ans+=a[i]*lsum[i+1];
ans%=inf;
}
cout<<ans<<endl;
return 0;
}
D
非常裸的找最大并查集
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
int n,m;
int father[200005];
int find(int x){
if(father[x]==x){
return x;
}
return father[x]=find(father[x]);
}
void unite(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
father[fx]=fy;
}
}
int siz[200005];
int main(){
cin>>n>>m;
int u,v;
for(int i=0;i<200005;i++)father[i]=i;
for(int i=1;i<=m;i++){
cin>>u>>v;
unite(u,v);
}
for(int i=1;i<=n;i++){
siz[find(i)]++;
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,siz[i]);
}
cout<<ans<<endl;
return 0;
}
E
很水的 E,可是我脑子一抽竟然用筛法找每个质数,然后用再求每个数的质因数。。。卡了 40min QAQ
判断 pairwise coprime:将所有数字分解质因数,如果不同的数字出现同一个质因数就代表不是。否则就是。
判断 setwise coprime:直接 gcd 即可.
#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
const int maxn=1e6;
int n;
int a[maxn+5];
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}
int tot=0;
bool used[maxn+5];
int fen(int x){
int sqr=sqrt(x);
for(int i=2;i<=sqr;i++){
if(x%i==0){
if(used[i])return 0;
used[i]=1;
}
while(x%i==0){
x/=i;
}
}
if(x!=1){
if(used[x])return 0;
used[x]=1;
}
return 1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int ans=1;
for(int i=1;i<=n;i++){
if(!fen(a[i])){
ans=0;
break;
}
}
if(ans==1){
printf("pairwise coprime");
return 0;
}
ans=a[1];
for(int i=2;i<=n;i++){
ans=gcd(ans,a[i]);
}
if(ans==1){
printf("setwise coprime");
return 0;
}
printf("not coprime");
return 0;
}
F
简化一下题目其实就是 知道每一行都有一个 i,j 是以 i 开头,j 结尾的线段,要求不在这些线段的集合中的最大行数以及位置。并且 i,j 是可改变的。
最后贪心一下。
但是前者我并不知道如何维护。
所以,
我不会。