本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-23 22:10:12

前言：

第一次At赛场AC ABCDE祭

A-Horizon

题目分析：

签到题，只需要直接照着题目式子计算即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll a;
int main()
{
    cin>>a;
    printf("%.7lf",sqrt(a*(12800000+a)));
    return 0;
}

B - Integer Division

题目分析：

仍然是签到题，照着题目的式子计算即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll a;
int main()
{
    cin>>a;
    if(a<0)
    {
        ll ans=a\/10;
        if(a%10)ans--;
        cout<<ans;
        return 0;
    }
    cout<<a\/10;
    return 0;
}

C - Knight Fork

题目大意：

给定两个点 $a,b$，坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$。问是否存在一个点，与$a$ 和 $b$ 的距离都是 $\sqrt{5}$。
$-10^{9} \le x1 \le 10^{9}$
$-10^{9} \le x2 \le 10^{9}$
$-10^{9} \le y1 \le 10^{9}$
$-10^{9} \le y2 \le 10^{9}$
保证给定两点的坐标不相等。

题目分析：

直接看上去看不出什么解法，不过鬼子很良心，配了一张图：

图中所有白色的点就是与黑色点距离为 $\sqrt{5}$ 的点。
所以只需要把所有与 $a$ 的距离为 $\sqrt{5}$ 的坐标用 map 存下来，$b$ 点同理。
最后只需要用 map 判断有没有点，与 $a$ 点距离为 $\sqrt{5}$ ，也与 $b$ 点距离也为 $\sqrt{5}$。如果有，输出 Yes 否则输出 No。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll xa,ya,x2,y2;
map<pair<int,int>,bool> im1;
map<pair<int,int>,bool> im2;
int main()
{
    cin>>xa>>ya>>x2>>y2;
    im1[make_pair(xa-2,ya-1)]=1;
    im1[make_pair(xa-2,ya+1)]=1;\/\/
    im1[make_pair(xa+2,ya-1)]=1;\/\/
    im1[make_pair(xa+2,ya+1)]=1;\/\/
    im1[make_pair(xa-1,ya-2)]=1;\/\/
    im1[make_pair(xa-1,ya+2)]=1;\/\/
    im1[make_pair(xa+1,ya-2)]=1;\/\/
    im1[make_pair(xa+1,ya+2)]=1;\/\/
    \/\/------------
    im2[make_pair(x2-2,y2-1)]=1;
    im2[make_pair(x2-2,y2+1)]=1;
    im2[make_pair(x2+2,y2-1)]=1;
    im2[make_pair(x2+2,y2+1)]=1;
    im2[make_pair(x2-1,y2-2)]=1;
    im2[make_pair(x2-1,y2+2)]=1;
    im2[make_pair(x2+1,y2-2)]=1;
    im2[make_pair(x2+1,y2+2)]=1;
    if((im1[make_pair(xa-2,ya-1)]&&im2[make_pair(xa-2,ya-1)])||(im1[make_pair(xa-2,ya+1)]&&im2[make_pair(xa-2,ya+1)])
    ||(im1[make_pair(xa+2,ya-1)]&&im2[make_pair(xa+2,ya-1)])||(im1[make_pair(xa+2,ya+1)]&&im2[make_pair(xa+2,ya+1)])||
    (im1[make_pair(xa-1,ya-2)]&&im2[make_pair(xa-1,ya-2)])||(im1[make_pair(xa-1,ya+2)]&&im2[make_pair(xa-1,ya+2)])||
    (im1[make_pair(xa+1,ya-2)]&&im2[make_pair(xa+1,ya-2)])||(im1[make_pair(xa+1,ya+2)]&&im2[make_pair(xa+1,ya+2)])
    )cout<<"Yes";
    else cout<<"No";
    return 0;
}

D - Prime Sum Game

题目大意：

Takahashi 和 Aoki 在玩一个游戏，规则如下：
首先，Takahashi 选择一个在 $A$ 和 $B$ 之间的数 $a$。
然后，Aoki 选择一个在 $C$ 和 $D$ 之间的数 $b$。
如果 $a + b$ 是一个质数，那么 Aoki 获胜，否则，Takahashi 获胜。
在双方都采取最优策略的情况下，输出谁会获胜。
$1 \le A \le B \le 100$
$1 \le C \le D \le 100$

题目分析：

因为 Takahashi 先手，所以只要在所有初始情况（Takahashi 选完一个数时）下有一种情况 Takahashi 必胜，那么 Takahashi 必胜。
然后需要对每一种初始情况判断 Takahashi 是否必胜。
显然，在当前初始情况下，Aoki 只要有一种方案获胜，那么在当前初始情况，Takahashi 必败。
总的来说就是只要 Takahashi 能选择的所有初始情况有胜局，那么 Takahashi 必胜，如果所有初始情况 Aoki 都能获胜，那么 Aoki 必胜.

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
int a,b,c,d;
int main()
{
    cin>>a>>b>>c>>d;
    int tak;
    int aok;
    bool ansf=0;
    for(tak=a;tak<=b;tak++)
    {
        bool ansf2=1;
        for(aok=c;aok<=d;aok++)
        {
            int num=tak+aok;
            int gh=sqrt(num);
            bool flag=1;
            for(int i=2;i<=gh;i++)
            {
                if(num%i==0)
                {
                \/\/    cout<<"num: "<<num<<endl;
                    flag=0;
                    break;
                }
            }
            ansf2&=(~flag);
        }
        ansf|=ansf2;
    }
    if(ansf)
    {
        cout<<"Takahashi";
        return 0;
    }
    cout<<"Aoki";
    return 0;
}

E - Subtree K-th Max

题目大意：

有 $N$ 个点，编号为 $1$ 到 $N$。每个点都有一个初始点权 $x_i$，有 $N-1$ 条边。
有 $Q$ 次询问，每次询问包含两个数 $(V_i,K_i)$，代表询问以 $V_i$ 为根的子树中第 $K_i$ 大的点点权是多少。
$2 \le N \le 10^{5}$
$0 \le X_i \le 10^{9}$
$1 \le A_i,B_i \le N$
$1 \le Q \le 10^{5}$
$1 \le V_i \le N$
$1 \le K_i \le 20$

题目分析

赛场上刚看到这道题时，想到了主席树。但是我太菜了只会用主席树存储线段树历史版本。再看看数据范围，$K_i$ 居然不超过 $20$，$N$ 也只有 $10^5$ 大小。这说明了什么呢？
说明了可以写爆搜预处理每个点的子树中第 $1$ 大到 第 $20$ 大的点都是哪些点！
很容易写出了下面的代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int head[maxn<<1];
struct EDGE
{
    int to,nxt;
}edge[maxn];
int cnt;
inline void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,q;
int val[maxn];
int kd[maxn][21];
bool vis[maxn];
inline bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int x)
{
    kd[x][1]=val[x];
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        dfs(to);
        int tmp[42];
        for(int j=1;j<=20;j++)
        {
            tmp[j]=kd[to][j];
        }
        for(int j=1;j<=20;j++)
        {
            tmp[j+20]=kd[x][j];
        }
        sort(tmp+1,tmp+40+1,cmp);
        for(int j=1;j<=20;j++)
        {
            kd[x][j]=tmp[j];
        }
    }
}
int main()
{
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<=20;j++)
        {
            kd[i][j]=-0x3f3f3f3f;
        }
    }
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    int a1,b1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a1,&b1);
        add(a1,b1);
        add(b1,a1);
    }
    dfs(1);
    int v,k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&v,&k);
        printf("%d\n",kd[v][k]);
    }
    return 0;
}

顺利测过了所有样例，满怀期待的交上去之后令我震撼无比：

WA,RE,TLE 满天飞。
不过只要有 AC 的测试点就还有救。
首先 RE 的原因是，题目是双向边，所以邻接链表应该开到 $2 \cdot 10^5$ 大小。
分析一下 TLE 的原因，可以发现原来的代码存在大量的时空浪费，有很多情况子树节点数量根本到不了 $20$ 个，但是都按 $20$ 个节点来计算了。赛场上注意到了这个地方后紧急换成 vector 来存，子树有多少节点就 emplace_back 多少节点。 然后就 AC 了。
$ \color{green}\text{AC代码：}$ (我为了保险开了 4 倍数组）

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int head[maxn<<2];
struct EDGE
{
    int to,nxt;
}edge[maxn<<2];
int cnt;
inline void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,q;
int val[maxn<<2];
vector<int> kd[maxn<<2];
bool vis[maxn<<2];
inline bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int x)
{
    kd[x].emplace_back(val[x]);
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        dfs(to);
        vector<int> tmp;
        for(int j=0;j<kd[to].size();j++)
        {
            tmp.emplace_back(kd[to][j]);
        }
        for(int j=0;j<kd[x].size();j++)
        {
            tmp.emplace_back(kd[x][j]);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        kd[x].clear();
        for(int j=0;j<tmp.size()&&j<20;j++)
        {
            kd[x].emplace_back(tmp[j]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    int a1,b1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a1,&b1);
        add(a1,b1);
        add(b1,a1);
    }
    dfs(1);
    int v,k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&v,&k);
        printf("%d\n",kd[v][k-1]);
    }
    return 0;
}