2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest
A. Xu Xiake in Henan Province
签到
D. Keiichi Tsuchiya the Drift King
几何，队友过的，好像说用三角函数会卡精度？
#include <bits/stdc++.h>
using namespace std;
const long double pi=acos(-1.0);
int main()
{
int _;
scanf("%d",&_);
while(_--){
long double a, b, r, d;
scanf("%Lf %Lf %Lf %Lf",&a,&b,&r,&d);
// long double angle=atan2(a+r, b) * 180.0 / pi;
long double res;
if(d>=90) res=sqrt((r+a)*(r+a) + b*b)-r;
else{
long double ss=tan(d*pi/180);
long double tmp=b/(a+r);
// printf("ss=%Lf tmp=%Lf\n", ss, tmp);
if(ss>=tmp) res=sqrt((r+a)*(r+a) + b*b)-r;//
else{
// long double ss=tan(d*pi/180.0);
// printf("ss=%Lf %lf\n", ss, sqrt(3.0)/3);//
long double cg, ca, gd, fd, ad;
ca=r+a;
cg=ca*ss;
gd=b-cg;
long double zz=(ca*ca)*(gd*gd)/((ca*ca)+(cg*cg));
res=sqrt(ca*ca+b*b-zz)-r;
}
}
printf("%.12Lf\n", max(res, a));
}
return 0;
}
E. Resistors in Parallel
打表找规律，分子是质数相乘，分母是分子+1相乘，python大数，我把//当成/了，wa(演)飞了~
import math
def init(n: int):
prime = []
vis = [0] * (n+1)
cnt = 0
for i in range(2, n + 1):
if vis[i] == 0:
prime.append(i)
cnt = cnt + 1
j = 0
while (j < cnt and prime[j] * i <= n ):
vis[i * prime[j]] = 1
if (i % prime[j] == 0):
break
j = j + 1
return prime
ret = init(100000)
_ = int(input())
for t in range(0,_) :
n = int(input())
son = int(1)
mo = int(1)
for i in ret :
if son * i > n :
break
son = son * i
mo = mo * (i+1)
d = math.gcd(son, mo)
son //= d
mo //= d
print("%i/%i"%(son,mo))
F. Honeycomb
这题纯bfs迷宫裸题啊。。。，格子数清楚同时读入的时候不能getline，会T
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int n,m;
char s[10000][10000];
int len[N];
bool vis[5000][7000];
struct Node{
int x,y;
int cnt;
}e;
int main(){
int _;
cin>>_;
while(_--){
cin>>n>>m;
getchar();
int cnt=0;
for(int i=1;i<=4*n+3;++i){
cnt=0;
while(char c=getchar()){
if(c=='\n') break;
s[i][++cnt]=c;
}
len[i]=cnt;
}
int sx,sy,ex,ey;
for(int i=1;i<=4*n+3;++i){
for(int j=1;j<=len[i];++j){
vis[i][j]=false;
if(s[i][j]=='S'){
sx=i,sy=j;
}
if(s[i][j]=='T'){
ex=i,ey=j;
}
}
}
queue<Node> q;
q.push({sx,sy,1});
int ans=-1;
while(!q.empty()){
auto tmp=q.front();
q.pop();
int x=tmp.x,y=tmp.y;
int cnt=tmp.cnt;
if(x==ex && y==ey){
ans=cnt;
break;
}
if(vis[x][y]) continue;
vis[x][y]=true;
bool flag=true;
if(s[x-2][y]!=' ') flag=false;
if(flag) q.push({x-4,y,cnt+1});
flag=true;
if(s[x+2][y]!=' ') flag=false;
if(flag) q.push({x+4,y,cnt+1});
flag=true;
if(s[x-1][y-3]!=' ') flag=false;
if(flag) q.push({x-2,y-6,cnt+1});
flag=true;
if(s[x+1][y-3]!=' ') flag=false;
if(flag) q.push({x+2,y-6,cnt+1});
flag=true;
if(s[x-1][y+3]!=' ') flag=false;
if(flag) q.push({x-2,y+6,cnt+1});
flag=true;
if(s[x+1][y+3]!=' ') flag=false;
if(flag) q.push({x+2,y+6,cnt+1});
}
printf("%d\n",ans);
}
return 0;
}
I. Distance
先将每个点坐标求出来，不难发现，每次选左右两边的距离一定最大，记前缀后缀和，输出答案即可
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int n;
ll a[N],b[N];
ll pre[N],suf[N];
int main(){
int _;
scanf("%d",&_);
while(_--){
scanf("%d",&n);
for(int i=2;i<=n;++i){
scanf("%lld",&a[i]);
}
b[1]=0;
for(int i=2;i<=n;++i){
b[i]=b[i-1]+a[i];
}
pre[0]=0;
for(int i=1;i<=n;++i){
pre[i]=pre[i-1]+b[i];
}
suf[n+1]=0;
for(int i=n;i>=1;--i){
suf[i]=suf[i+1]+b[i];
}
int l=1,r=n;
int f=0;
ll ans=0;
while(l<=r){
if(!f){
ans+=abs((l-1)*b[l]-pre[l-1])+abs(suf[r+1]-(n-r)*b[l]);
printf("%lld",ans);
l++;
f^=1;
}
else{
ans+=abs((l-1)*b[r]-pre[l-1])+abs(suf[r+1]-(n-r)*b[r]);
printf("%lld",ans);
r--;
f^=1;
}
if(l<=r) printf(" ");
}
puts("");
}
return 0;
}