AtCoder Beginner Contest 191
第一次打Atcoder，迟到了，只做了AB
A - Vanishing Pitch
题意：打棒球，棒球飞行速度是\(V\)，棒球当且仅当在第\(T-S\)秒（含）中会隐形，当棒球飞出去\(d\)之后就要打球，如果隐形就打不中，问是否能打中。
简单模拟题，看飞出去\(d\)的时间是否在隐形时间段中即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
double v,t,s,d;
int main()
{
cin>>v>>t>>s>>d;
double tim=d/v;
if(tim>=t&&tim<=s)puts("No");
else puts("Yes");
return 0;
}
B - Remove It
题意：给一个数列\(A\)，把\(A\)中等于\(x\)的数删掉得到\(A'\)，求\(A'\)。
按题意模拟。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,x,a[N];
int main()
{
n=read();x=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)if(a[i]!=x)printf("%d ",a[i]);
}
C - Digital Graffiti
题意：一个实心的联通的多边形，求边数。
边数等于角数，观察一个点旁边的田字格，1白3黑或1黑3白说明旁边有一个角，统计即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 15
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,m;
char ch[N][N],t[N][N];
int count(int x,int y)
{
return (ch[x][y]=='#')+(ch[x+1][y+1]=='#')+(ch[x+1][y]=='#')+(ch[x][y+1]=='#');
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
scanf("%s",(ch[i]+1));
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(count(i,j)==1||count(i,j)==3)t[i][j]='#';
else t[i][j]='.';
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//printf("%c",t[i][j]);
if(t[i][j]=='#')ans++;
}
//puts("");
}
printf("%d\n",ans);
}
D - Circle Lattice Points
题意：一个以\((X,Y)\)为圆心\(R\)为半径的圆，问圆上和圆内有多少整点。
枚举横坐标，勾股定理算出纵坐标范围即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
long double X,Y,R;
int main()
{
cin>>X>>Y>>R;
R+=1e-14;long long ans=0;
for(int i=ceil(X-R);i<=floor(X+R);i++)
{
int CE=floor(Y+sqrt(R*R-(X-i)*(X-i))),FL=ceil(Y-sqrt(R*R-(X-i)*(X-i)));
ans+=CE-FL+1;
}
printf("%lld\n",ans);
}
E - Come Back Quickly
题意：\(n\)个点\(m\)条边的带权有向图，问从每个点出发回来的最短路。
以每个点为源点跑一遍单源最短路，\(i\)的答案即为
\[\min^{n}_{i\neq j}dis(i,j)+dis(j,i) \]注意特判自环。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 2005
#define mp make_pair
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,f[N][N],dist[N],vis[N],v[N],w[N],head[N],nxt[N],cnt,self_circle[N];
void add(int a,int b,int c)
{
v[++cnt]=b;
w[cnt]=c;
nxt[cnt]=head[a];
head[a]=cnt;
}
void dij(int S)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
q.push(mp(0,S));
dist[S]=0;
while(!q.empty())
{
int c=q.top().second;q.pop();
if(vis[c])continue;
vis[c]=1;
for(int i=head[c];i;i=nxt[i])
{
if(dist[v[i]]>dist[c]+w[i])
{
dist[v[i]]=dist[c]+w[i];
q.push(mp(dist[v[i]],v[i]));
}
}
}
}
int main()
{
memset(self_circle,0x3f,sizeof(self_circle));
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
if(x==y)self_circle[x]=min(self_circle[x],z);
else add(x,y,z);
}
for(int i=1;i<=n;i++)
{
dij(i);
memcpy(f[i],dist,sizeof(f[i]));
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// {
// printf("%d ",f[i][j]);
// }
// puts("");
// }
for(int i=1;i<=n;i++)
{
int minn=self_circle[i];
for(int j=1;j<=n;j++)
{
if(i==j)continue;
minn=min(minn,f[i][j]+f[j][i]);
}
if(minn==0x3f3f3f3f)puts("-1");
else printf("%d\n",minn);
}
return 0;
}
F - GCD or MIN
题意：有\(N\)个数，每次可以删掉两个数，填上他们的\(gcd\)或取\(min\)，问最后一个数有多少种可能性。
本场中需要智力的题目。
首先要知道\(\gcd(x,y)\leq\min(x,y)\)，这个比较显然，但是很重要。
因为上述性质也就决定了答案不可能超过\(\min a[i]\)。
那我们思考一下对于小于\(\min a[i]\)的数怎么判断是否能取到呢？
由于小于\(\min a[i]\)，因此不可能直接通过\(\gcd\)取到，假设我们有一个数\(x<\min a[i]\)，那么\(x\)一定是\(a\)的子集的\(\gcd\)。然后再通过和其他数取\(min\)得到
而且一个比较好的性质就是，如果我们已经通过一些子集的\(\gcd\)获得了\(x\)，那么我们在让它和其他含有\(x\)这个因子的数做\(\gcd\)，那么还一定是\(x\)，因为\(\gcd(k\times x,x)=x,k\in N^+\)。所以如果有一个\(a\)的子集的\(\gcd\)为\(x\)，那么\(a\)中所有含\(x\)这个因子的数的\(gcd\)也必定是\(x\)
那考虑按顺序处理，对每一个\(a[i]\)处理一下\(a[i]\)的因数。设\(f[x]\)表示到目前为止含因子\(x\)的数的\(gcd\)，最后看一下有多少\(f[x]=x\)的\(x\)即可，由于值域较大，因此要拿\(map\)存。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define N 200005
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,a[N],maxn=0x3f3f3f3f;
map<int,int>f;
map<int,int>::iterator it;
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),maxn=min(maxn,a[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j*j<=a[i]&&j<maxn;j++)
{
if(a[i]%j==0)
{
if(f[j]==0)f[j]=a[i];
else f[j]=__gcd(f[j],a[i]);
if(a[i]/j<maxn)
{
int x=a[i]/j;
if(f[x]==0)f[x]=a[i];
else f[x]=__gcd(f[x],a[i]);
}
}
}
}
int ans=0;
for(it=f.begin();it!=f.end();it++)
{
ans+=(it->first==it->second);
}
printf("%d\n",ans+1);
}