A - Horizon

Code

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

int main(){
	double h;
	scanf("%lf",&h);
	printf("%.9f\n",sqrt(h*(12800000+h)));
    return 0;
}

B - Integer Division

Code

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

int main() 
{
  long long X;
  cin >> X;
  cout << X / 10 - (X % 10 < 0) << "\n";
  return 0;
}

C - Knight Fork

代码

#include <iostream>
using namespace std;
typedef long long ll;

ll x1, y1, x2, y2;

int main()
{
    cin >> x1 >> y1 >> x2 >> y2;
    
    bool flag = false;
    if (abs (x1 - x2) == 2 && abs(y1- y2) == 0) flag = true;
    if (abs (x1 - x2) == 3 && abs(y1- y2) == 1) flag = true;
    if (abs (x1 - x2) == 3 && abs(y1- y2) == 3) flag = true;
    if (abs (x1 - x2) == 2 && abs(y1- y2) == 4) flag = true;
    if (abs (x1 - x2) == 0 && abs(y1- y2) == 2) flag = true;
    if (abs (x1 - x2) == 1 && abs(y1- y2) == 3) flag = true;
    if (abs (x1 - x2) == 1 && abs(y1- y2) == 1) flag = true;
    if (abs (x1 - x2) == 0 && abs(y1- y2) == 4) flag = true;
    if (abs (x1 - x2) == 4 && abs(y1- y2) == 2) flag = true;
    if (abs (x1 - x2) == 4 && abs(y1- y2) == 0) flag = true;

    if (flag) cout << "Yes";
    else cout << "No";
    return 0; 
}

D - Prime Sum Game

题目描述

叨叨念

一开始看到“最佳”这个字眼，觉得是“博弈论”，出于对数论的恐惧，竟然没想到用暴力？
补题的过程中又WA了3次,原来是循环条件错了，我竟然把“inclusive”误认为是“不包含”的意思了

其实本题就是暴力，如果对于A区间内的某个数，在B中找不到数让它们相加后变为素数，那么Takahashi就可以获胜

Code

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

bool check(int n)
{
  	if (n < 2) return false;
	for (int i = 2; i <= n / i; i++)
		if (n % i == 0)	return false;
	return true;
}
int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = a; i <= b; i++)
	{
		bool flag = true;  // 每次换数字都要初始化
		for (int j = c; j <= d; j++)
			if (check(i + j))	
				flag = false;
		if (flag)  // 一旦在Aoki所拥有的范围中找不到数让它们相加变为负数，直接输出Takahashi
		{
			cout << "Takahashi";
			return 0;
		}
	}	
	cout << "Aoki";
	return 0;
} 

E - Subtree K-th Max

题目描述

解题思路

做的时候用了优先队列+BFS暴力求解，但是最后tle了
赛后看了题解才知道是用树形dp
真正的题解参考此处

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
typedef pair<int,int> PII;
typedef long long ll;

int n, m;
int h[N], e[N], ne[N], idx;
vector<int> w[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)    continue;  // 不能等于父节点，不然会往回搜
        dfs(j, u);

        // 这里会先放入最深的点权，然后慢慢再往上回溯放入，复杂度很高，所以下面才有resize(20);
        for (int k = 0; k < w[j].size(); k++)   w[u].push_back(w[j][k]);
    }

    sort(w[u].begin(), w[u].end());
    reverse(w[u].begin(), w[u].end());  // 倒序排序
    if (w[u].size() > 20)  w[u].resize(20);  // 不加这句会tle 3个测试点
}

int main()
{
    memset(h, -1, sizeof h);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        w[i].push_back(x);
    }

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);  // 由于不知道谁是父、子结点，所以加双向
    }

    dfs(1, -1);

    while (m--)
    {
        int v, k;
        cin >> v >> k;
        cout << w[v][k - 1] << endl;  // 坐标从0开始，所以k-1
    }

    return 0;
}