How to AK ABC239

__vector__ · 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}。

保证给定两点的坐标不相等。

题目分析：

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

图中所有白色的点就是与黑色点距离为 \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 获胜。
在双方都采取最优策略的情况下，输出谁会获胜。

题目分析：

因为 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 大的点点权是多少。

题目分析

赛场上刚看到这道题时，想到了主席树。但是我太菜了只会用主席树存储线段树历史版本。再看看数据范围，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 了。