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
",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
",ans);
}
E - Come Back Quickly
题意：(n)个点(m)条边的带权有向图，问从每个点出发回来的最短路。
以每个点为源点跑一遍单源最短路，(i)的答案即为
[min^{n}_{i
eq 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
",minn);
}
return 0;
}
F - GCD or MIN
题意：有(N)个数，每次可以删掉两个数，填上他们的(gcd)或取(min)，问最后一个数有多少种可能性。
本场中需要智力的题目。
首先要知道(gcd(x,y)leqmin(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 imes x,x)=x,kin 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
",ans+1);
}