题解——ABC239
\(AtCoder Beginner Contest239\)
A.horizon
题意
给定 \(x\)，求 \(\sqrt{x(12800000+x)}\)。
思路
直接算
代码
点击查看代码
int n;
int main(){
n=read();
printf("%.6lf\n",sqrt(1.0*n*(12800000.0+n)));
return 0;
}
B.Integer Division
题意
给定 \(x\)，\(x\in [-10^{18},10^{18}]\)，求 \(\left\lfloor \frac{x}{10}\right\rfloor\)
思路
特判正负性，直接算
代码
点击查看代码
ll n;
int main(){
n=read();
if(n>=0||n%10==0) n/=10;
else n=n/10-1;
printf("%lld\n",n);
return 0;
}
C.Knight Fork
题意
给定两个坐标 \((x1,y1)\)，\((x2,y2)\)，判断两个棋盘上的棋子是否能被一个马吃掉。
思路
双层循环判断即可。
代码
点击查看代码
int x_1,x_2,y_1,y_2;
int dx[8]={2,2,1,1,-2,-2,-1,-1},dy[8]={1,-1,2,-2,1,-1,2,-2};
int main(){
x_1=read(),y_1=read(),x_2=read(),y_2=read();
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
int xx1=x_1+dx[i],xx2=x_2+dx[j],yy1=y_1+dy[i],yy2=y_2+dy[j];
if(xx1==xx2&&yy1==yy2){
printf("Yes\n");
return 0;
}
}
}
printf("No\n");
}
D.Prime and Game
题意
\(\text{Takahashi}\) 和 \(\text{Aoki}\) 在玩游戏，\(\text{Takahashi}\) 先选取 \([A,B]\) 中的一个整数，接着 \(\text{Aoki}\) 在 \([C,D]\) 中选取一个整数，若二者的和为一个素数，则 \(\text{Aoki}\) 获胜，反之 \(\text{Takahashi}\) 获胜。
现在给定 \(A,B,C,D\) 判断谁会获胜
思路
当且仅当对于每一个 \(x\in [A,B]\)，都有一个 \(y\in [C,D]\)，使得 \((x+y)\in \mathbb{P}\)，\(\text{Aoki}\) 获胜，直接去枚举。
代码
点击查看代码
int a,b,c,d;
inline bool check(int x){
int cnt=0;
if(x==2) return 1;
for(int i=2;i*i<=x;i++){
if(x%i==0) cnt++;
}
if(!cnt) return 1;
return 0;
}
int main(){
a=read(),b=read(),c=read(),d=read();
for(int i=a;i<=b;i++){
bool pd=0;
for(int j=c;j<=d;j++){
if(check(i+j)){
pd=1;
break;
}
}
if(!pd){
printf("Takahashi\n");
return 0;
}
}
printf("Aoki\n");
return 0;
}
E.Subtree K-th Max
题意
给定一棵 \(n\) 个节点的树，每个节点有一个点权 \(w_i\)，\(q\) 次询问，每次求点 \(v\) 子树内的第 \(k\) 大值。
数据范围：\(n,q\le 10^5,k\le 20\)
思路
因为 \(k\) 很小且不支持修改，可以 \(\text{vector}\) 直接归并每个子树的所有权值，排序、翻转后只留下前 \(20\) 个，每次查询直接输出即可。
代码
点击查看代码
int n,q;
vector E[maxn],W[maxn];
int w[maxn];
inline void dfs(int u,int fa){
W[u].push_back(w[u]);
for(auto v:E[u]){
if(v==fa) continue;
dfs(v,u);
for(auto x:W[v]){
W[u].push_back(x);
}
}
sort(W[u].begin(),W[u].end());
reverse(W[u].begin(),W[u].end());
if(W[u].size()>20) W[u].resize(20);
}
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
w[i]=read();
}
for(int i=1;i //下边的咕咕咕……