AtCoder Beginner Contest 239 A~E

A

Problem surface
Problem Statement
Assuming that the horizon seen from a place x meters above the ground is
sqrt(x(12800000+x))

meters away, find how many meters away the horizon seen from a place H meters above the ground is.
Carelessness
Assuming that the horizon X seen from a place is sqrt (X (128000 + X)) meters away from the ground, find out how many meters the horizon is seen from a place, and the ground above H meters is.

Simple A, see the code understanding for details
code

#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>
using namespace atcoder;

using ll=long long;

int main(){
    ll H;
    cin>>H;
    long double ans=sqrt(H*(12800000+H));
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

B

Problem surface
Given an integer X between −1018 and 1018(inclusive), print ⌊ 10X ⌋.
Carelessness
Given an integer X between − 1018 and 1018 (inclusive), output ⌊ 10X ⌋

This is simpler, directly on the code
code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll x;
    cin>>x;
    ll ans=x/10;
    if(x<0&&x%10!=0)
        ans-=1;
        cout<<ans;
    return 0;
}

C

Problem surface
On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x1 ,y1 ) and (x2 ,y2) are both sqrt(5)?
Carelessness
On the xy coordinate plane, is there a grid point whose distance to two grid points (x1,y1) and (x2,y2) is root 5?

One point xy_- A coordinate plane whose X and Y coordinates are integers is called a grid point.
I traverse every coordinate and simulate it
code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
int main(){
  cout << fixed << setprecision(7);
  bool ans=false;
  int x1,x2,y1,y2; cin >> x1 >> y1 >> x2 >> y2;
  vector<int> x1a{x1+2,x1+2,x1+1,x1+1,x1-1,x1-1,x1-2,x1-2};
  vector<int> x2a{x2+2,x2+2,x2+1,x2+1,x2-1,x2-1,x2-2,x2-2};
  vector<int> y1a{y1+1,y1-1,y1+2,y1-2,y1+2,y1-2,y1+1,y1-1};
  vector<int> y2a{y2+1,y2-1,y2+2,y2-2,y2+2,y2-2,y2+1,y2-1};
  rep(i,8)rep(j,8){
    if(x1a[i]==x2a[j]&&y1a[i]==y2a[j]) ans=true;
    else continue;
  }
  if(ans) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

D

Problem surface
Takahashi and Aoki are playing a game.

First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
Next, Aoki chooses an integer between C and D (inclusive).
If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.
When the two players play optimally, which player will win?
Carelessness
First, Takahashi selects an integer between A and B (including B) and tells Aoki it.
Next, Aoki selects an integer (inclusive) between C and D.
If the sum of these two integers is prime, Aoki wins; Otherwise, Takahashi wins.
When two players are the best, which player will win?

This question is essentially to judge the prime number, and then add some messy things
Just simulate and write the judgment prime
code

#include <bits/stdc++.h>
using namespace std;


int main(){
    int a[4]; for (int i = 0; i < 4; ++i) cin >> a[i];
    int isprime[301] = {0};
    isprime[0] = isprime[1] = 1;
    for (int i = 2; i <= 300; ++i){
        if (isprime[i] == 1) continue;
        for (int s = 2*i; s <= 300; s += i){
            isprime[s] = 1;
        }
    }
    for (int k = a[0]; k <= a[1]; ++k){
        bool cur = true;
        for (int l = a[2]; l <= a[3]; ++l){
            if (isprime[k + l] == 0){
                cur = false;
                break;
            }
        }
        if (cur){
            cout << "Takahashi" << endl;
            return 0;
        }
    }
    cout << "Aoki" << endl;

}

E

Problem surface
We have a rooted tree with N vertices. The vertices are numbered 1 through N, and the root is Vertex 1.
The i-th edge connects Vertices Ai and Bi.
Vertex i has an integer Xi written on it.
You are given Q queries. For the i-th query, given a pair of integers (Vi ,Ki​), answer the following question.
Question: among the integers written on the vertices in the subtree rooted at Vertex Vi​,find the Ki-th largest value.
Carelessness
We have a root tree with n vertices. Vertex numbers range from 1 to N, and the root is vertex 1.
The ith edge connects the vertices Ai and Bi.
Vertex i has an integer Xi.
You are given a Q query. For the ith query, given a pair of integers (Vi,Ki), answer the following questions.
Q: find the ki - th largest value in the integer written on the vertex of the subtree with vertex Vi as the root.

This problem is the query tree. Recursively search each node, store all child elements with this node as the root, and then sort them in descending order
code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,a[100009];
vector<int> g[100009];
int ans[100009][33];
bool cmp(int x,int y){return x>y;}
void dfs(int p,int fa){
	int res[33],q[33];
	for(int i=1;i<=30;i++)res[i]=-1;
	for(int i=0;i<g[p].size();i++){
		if(g[p][i]==fa)continue;
		dfs(g[p][i],p);
		int j,k,cnt=1;
		for(j=1,k=1;cnt<=20;cnt++){
			if(res[j]>ans[g[p][i]][k]){
				q[cnt]=res[j];
				j++;
			}
			else {
				q[cnt]=ans[g[p][i]][k];
				k++;
			}
		}
		for(int l=1;l<=20;l++)res[l]=q[l];
	}
	res[21]=a[p];
	sort(res+1,res+22,cmp);
	for(int i=1;i<=20;i++)ans[p][i]=res[i];
}
void solve(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int p,q;
		cin>>p>>q;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	dfs(1,0);
	while(q--){
		int p,r;
		cin>>p>>r;
		cout<<ans[p][r]<<endl;
	}
}
int main(){
	solve();
	return 0;
}

It's not easy to make. Just like it qwq

Keywords: C++

Added by speedamp on Sat, 26 Feb 2022 08:49:57 +0200