[游戏开发]2019hbcpc部分题解

Date：2022.04.28
A.Battle of Balls
B Icebound and Sequence
C 分治
E Paper Plane Fly Away
G 点我
H 天神的密码
J 舔狗
K 河北美食
L smart robot

A.Battle of Balls

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
Now that you have a ball of radius r, you want it to go from the bottom boundary of the map to the top boundary of the map (starting and ending points can be considered outside the map, entering the map from the bottom boundary and leaving the map from the top boundary). But there are a lot of little spikes in the map, and we can think of them as points. Your ball can’t touch any of the points and the left or the right boundary of the map, even if the edge of the ball can’t touch them. The area of the map can be seen as 100×100, with the lower left corner (0,0)and the upper right corner (100,100). The bottom boundary is y = 0, and the top boundary is y = 100.
输入描述:
The first line contains an integer T, representing the number of data sets.
After that, there were T sets of data. In each set:
The first line contains an integer n ,which represents the number of small spikes, and a floating point number r, which is your ball’s radius.
The next n lines, each line containing two floating point numbers x,y, representing the coordinates of the spikes.
$1\le T\le 100,0\le n\le 1000,0\le r\le 1000,0\le x,y\le 100$
输出描述:
For each set of input, if the ball can reach the top boundary of the map, output Yes ; Otherwise, output No.
示例1
输入
1
1 25.0
50.0 50.0
输出
No

思路：看任意两点之间的距离是否<=圆的直径，若<=则这两点之间无法通过这个圆，因此将这两个点连通。注意边界为左（x=0）、右（x=100）两条竖边，我们以点到左边的距离为例：
开始在想点到边的距离不好确定，因为可以到边上任意点，后来画个图发现若点$i$的横坐标$x[i]?0<=2?r$，则圆一定不能从左边~$i$点这段距离穿过，右边也同理。如图：

就算在斜的部分合法，最后若想从左边~$x[i]$穿过，必定要过的一道坎是直径<$x[i]?0$。
因此，找所有点到边的距离时，以点的纵坐标为基准，因此点到左边的距离即为$x[i]?0$。由此，若$x[i]?0<=2?r$，则将点$i$和左边连通。这里不妨将左右两边分别看为$0、n+1$号点，若最后维护所得连通性是$0、n+1$连通，则表示在左边~右边连接了一个每两个点间都无法通过圆的“屏障”，则为No；否则Yes。
如何维护点与点间的连通性？并查集。
此外几何注意精度（以此纪念这是我做的第一道几何）。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
const double eps=1e-8;
int t,n,m,p[N];
double x[N],y[N];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
double dis(int i, int j)
{
    return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
int main()
{
    cin>>t;
    while(t--)
    {
        double r,d;cin>>n>>r;d=r*2;
        for(int i=0;i<=n+1;i++) p[i]=i;
        for(int i = 1; i <= n; i++)
        {
            cin >> x[i] >> y[i];
            if(x[i] - d <= eps) p[find(i)]=find(0);
            if(100 - x[i] - d <= eps) p[find(i)]=find(n+1);
        }
        for(int i = 1; i <= n; i++)
            for(int j = i + 1; j <= n; j++)
                if(dis(i, j) - d*d <= eps) p[find(i)]=find(j);
        if(find(0) == find(n + 1)) cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}

B Icebound and Sequence

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
Icebound hates math. But Imp loves math. One day, Imp gave icebound a problem.
The problem is as follows.
$S=({\sum }_{i=1}^n{q}^i）modp$
For given q,n,p, you need to help icebound to calculate the value of S.
输入描述:
The first line contains an integer T, denoting the number of test cases.
The next T lines, each line contains three integers q,n,p, separated by spaces.
$1\le T\le 100,1\le n,q,p\le 10^9$
输出描述:
For each test case, you need to output a single line with the integer S.
示例1
输入
2
2 3 100
511 4 520
输出
14
184

思路：$s=\frac{a_1?a_n?q}{1?q}=\frac{q?q^{n+1}}{1?q}$，这其中涉及取模，取模就要求$1?q$在$modp$下的逆元，但$1?q$与$p$不一定互质，因此不一定存在逆元，且不一定互质也不能用费马小定理。如此一来，需要一个公式：
$\frac{x}{b}\%m==\frac{x\%(b?m)}{b}$，由此仍由快速幂求解分子，分母仍为$1?q$，不过分子求快速幂过程中要对$相应的(b?m)$也就是$(1?q)?p$取模。
特判$q==1$，答案是$n?q$。
此外快速幂会爆LL，要配上龟速乘。
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL q,n,p;
LL qmul(LL a,LL k,LL p)
{
    LL res=0;
    while(k)
    {
        if(k&1) res=(res+a)%p;
        k>>=1;
        a=(a+a)%p;
    }
    return res;
}
LL qmi(LL a,LL k,LL p)
{
    LL res=1;
    while(k)
    {
        if(k&1) res=qmul(res,a,p);
        a=qmul(a,a,p);
        k>>=1;
    }
    return res;
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>q>>n>>p;
        if(q==1) {cout<<n%p<<endl;continue;}
        LL mi=qmi(q,n+1,(q-1)*p);
        LL x,y;
        cout<<(mi-q)%((q-1)*p)/(q-1)<<endl;
    }
    return 0;
}

C.分治

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
你是DEEP国的大军师，辅佐一个非常有野心的国王，这位国王非常有野心，他计划攻占 n 个国家。在地图上，这些国家排成一行。
探子已经查明，当攻打一个国家 i 时，为了防止国家间的联合对抗，需要给该国家周围，所有未被攻占的国家支付$cos{t}_i$个金币，即对于国家 i，它左侧第一个已被攻打的国家为 l，右侧第一个已被攻打的国家为 r，则他需要给[l+1,i-1] 和 [i+1,r-1] 之间的国家支付金币。如果 l 不存在，则需要给 [1, i-1] 之间的所有国家支付金币；若 r 不存在，则需要给 [i+1,n] 之间的所有国家支付金币。
现在，你的下属已经给你提供了每个国家需要支付金币的数量。为了满足国王的野心，你需要计算出攻占完所有国家需要的最小花费。
输入描述:
第一行是一个整数 T，代表接下来有T组数据。
接下来每组数据
第一行有一个整数 n，代表要攻占的国家数目。
第二行共 n 个整数，代表攻占每个国家前，需要支付给其周围未被攻占国家 $cos{t}_i$个金币。
$1\le T\le 50，1\le n\le 100，1\le cos{t}_i\le 10000$输出描述:
对于每组数据输出一行，代表需要支付的最小花费。
示例1
输入
2
1
1
3
1 1 2
输出
0
2
说明
3
1 1 2
先打中间这个1 给左右两个各1块钱
再打左右两个 不用花钱

思路：区间dp，倒序的石子合并，注意边界。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=210;
LL a[N],n,m,f[N][N];

int main()
{
    int t;cin>>t;
    while(t--)
    {
        memset(f,0,sizeof f);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int len=2;len<=n;len++)
            for(int l=1;l+len-1<=n;l++)
            {
                LL r=l+len-1;
                f[l][r]=1e18;
                for(int k=l;k<=r;k++)
                {
                    if(k==l) f[l][r]=min(f[l][r],f[l+1][r]+(r-l)*a[l]);
                    else if(k==r) f[l][r]=min(f[l][r],f[l][r-1]+(r-l)*a[r]);
                    else f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+(r-l)*a[k]);
                }
            }
        cout<<f[1][n]<<endl;
    }
    return 0;
}

E.Paper Plane Fly Away

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
There are n boys, indexed from 1 to n, and n girls indexed from n+1 to 2n.
One day, they have a party together. The girls are seated in the first row, and the boys sit in the second row. They take their seat in such a way, that a boy sit just behind a girl, and boy indexed 1 sit on the leftmost chair, 2 sit on the second, etc.
Each boy has a girl he likes,and he may make contact to his sweetheart, by writing down what he wants to tell her on a piece of paper, and makes it a paper plane, which he will throw directly at her. You may assume that the plane will go in a straight line.
But, the trouble occurs, when two paper plane collide in the air and drop halfway. Obviously, this will be extremely awkward. So each boy wants to know, if he throws his paper plane, how many paper planes have the potential to collide with it halfway.
It’s guaranteed that each girl is the sweetheart of exactly one boy.
输入描述:
The first line contains a single integer n.
Then n lines follow, the i-th of which contains two integers, the index of the girl seated in front of the i-th boy and the girl he likes.
$1\le n\le 10^5$
输出描述:
Output n lines, the i-th of which contains one integer, the number of planes that may collide with i-th boy’s plane.
示例1
输入
5
7 9
6 6
8 10
9 7
10 8
输出
3
2
2
3
2

思路：BIT看下对于每个男喜欢的女，女前面有多少未被配对的+女后面有多少人已被配对的。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
typedef long long LL;
LL n,m;
LL g[N],b[N],girl[N],like[N];
LL tr[N];
map<LL,LL>q;
LL lowbit(LL x) {return x&-x;}
void add(LL x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
LL getsum(LL x)
{
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>girl[i]>>like[i];
        q[girl[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        add(q[like[i]],1);
        cout<<q[like[i]]-getsum(q[like[i]])+getsum(n)-getsum(q[like[i]])<<endl;
    }
    return 0;
}

G.点我

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
X腿与队友到河北省来参加2019河北省大学生程序设计竞赛，然而这场比赛的题目难度实在是太高了。比赛开始一个小时后，X腿仍然没有做出一个题。这时候，X腿惊讶的发现电脑屏幕上出现了一个神奇按钮，按钮上写着”点我签到“。X腿非常兴奋，于是他点击了这个按钮，只见屏幕上的题目状态由“未提交”转变成了“答案错误”。他又点击了一下这个按钮，题目状态由“答案错误”变成了“通过”！
当题目状态为“通过”时，我们认为X腿签到成功了。
通过多次实验，X腿总结出以下经验：
当题目状态为”未提交“时，点击按钮后题目状态将变为”答案错误“。
当题目状态为”答案错误“时，点击按钮后题目状态将变为”通过“。
当题目状态为”*通过“时，点击按钮后题目状态将变为”答案错误“。
现在，已知初始的题目状态为”未提交“。由于X腿过于兴奋，点击了 n 次按钮。请问X腿签到成功了吗？
输入描述:
一行一个正整数 n，代表X腿点击了 n 次按钮。
$0\le n\le 100000$
输出描述:
输出一行。如果X腿签到成功，请你输出“qiandaochenggong”；否则输出"qiandaoshibai”。（输出均不含引号)
示例1
输入
3
输出
qiandaoshibai

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
int main()
{
    cin>>n;
    if(n<=1) {cout<<"qiandaoshibai\n";return 0;}
    if(n%2) cout<<"qiandaoshibai\n";
    else cout<<"qiandaochenggong\n";
    return 0;
}

H.天神的密码

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
2018年，icebound打开了神殿。而在2019年，icebound正在试图破解天神的密码，以期获得天神的力量。
icebound发现，想要得到神的密码，必须先要完成一个祭祀仪式。在这个祭祀仪式上，我们首先会追随神的指引，得到两个正整数 N和 K。随后，我们令 $X=N^K$，得到天神喜欢的数字X。
利用 X，我们进行以下方式得到天神最后的密码：
步骤 1 将 X每个数位上的数字相加得到 Y。
步骤 2 令 X=Y
步骤 3 反复执行 步骤 1，直到 X只有一个数位时停止，即 $1\le X\le 9$。此时的 X 即为天神的密码。
比如：当 N=11,K=2 时，首先我们得到 $X=N^K=11^2=121$。然后我们把 X 的各个数位上的数相加，即 Y=1+2+1=4。此时 X=Y=4，X 仅有一个数位了，所以我们停止操作，得到天神的密码为4。
icebound许诺，如果他获得了天神的力量，一定保你荣华富贵，全家幸福，还会另外送你一块金牌。所以，请你帮助他计算天神的密码。
输入描述:
首先第一行一个整数 T ，代表数据组数。
随后 T 行，每行两个数 N,K ，用空格隔开。
$1\le T\le 20，1\le N\le 10^9，1\le K\le 2$
输出描述:
一行一个整数 X，表示天神的密码。
示例1
输入
2
11 2
100 1
输出
4
1

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,t,k;
LL count(LL x)
{
    LL res=0;
    while(x) {res+=x%10;x/=10;}
    return res;
} 
int main()
{
    cin>>t;
    while(t--)
    {
        LL a,k;cin>>a>>k;
        LL cnt=(k==2?a*a:a);
        while(cnt>=10)
        {
            cnt=count(cnt);
        }
        cout<<cnt<<endl;
    } 
    return 0;
}

J.舔狗

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述:
“舔狗舔狗，
舔到最后，
一无所有。”
有 n 只舔狗，每只舔狗的心中都有自己朝思暮想的一位。
每个人虽然受到了一万次拒绝，还毅然第一万零一次鼓起勇气。
作为一个不食人间烟火的算法设计师，你早已看破红尘。但是，人世间的苦难仍让你挂念。看到众生在单恋中苦苦坚持，你决定普度众生，给大家找到一个最好的结局，让一无所有的舔狗尽量地少，让每个人都尽量能和自己喜欢的或喜欢自己的人修成正果。
也就是说，你需要给这 n 只舔狗配对，对于舔狗 i，他可以和他朝思暮想的人 $a_i$配对。另外，喜欢 i 的其他舔狗也可以和他配对。你需要让没有被配对的舔狗尽量少。
输入描述:
第一行一个 n，表示舔狗个数。
第二行 n 个数字，第 i 个数字表示第 i只舔狗的朝思暮想的一位的编号 $a_i$。
$2\le n\le 10^6$
输出描述:
第一行一个数字，表示一无所有的舔狗的最小数量。
示例1
输入
10
3 1 8 6 10 1 4 1 6 1
输出
0

思路：开始交了发类比拓扑序“拆点”，结果wa了。要用贪心，我们规定一个点的入度是多少人喜欢他，因此入度少的选择就少，比如说入度为0的不选反而选入度为100的和别人组合，而这个入度100的恰好又是这个入度为0的人唯一喜欢的，那入度为0的不就注定单身吗？这样显然更糟糕，因此核心思想：每次拆掉入度最小的点和它喜欢的点。
此外，之所以可以这样贪心是题意强限制每个人只喜欢一个人。
代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef pair<int,int> PII;
int n,m,ans,in[N],q[N],fa[N];
bool vis[N];
void topsort()
{
    priority_queue<PII,vector<PII>,greater<PII> >q;
    for(int i=1;i<=n;i++) q.push({in[i],i});
    while(q.size())
    {
        PII t=q.top();q.pop();
        int id=t.second;
        if(vis[id]) continue;
        vis[id]=true;
        int j=fa[id];
        if(vis[j]||!fa[j]||!j) continue;
        //cout<<id<<' '<<j<<' '<<fa[j]<<endl;
        vis[j]=true;
        in[j]--;in[fa[j]]--;ans+=2;
        q.push({in[j],j});q.push({in[fa[j]],fa[j]});
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        fa[i]=x;in[x]++;
    }
    topsort();
    cout<<n-ans;
    return 0;
}

K.河北美食

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述:
不知不觉当中，河北成为了一些人心中的“美食荒漠”，除了驴肉火烧，大抵想不起什么河北的美食了。大概是京津太过闪耀，盖过了冀菜的光芒。其实河北并不是美食荒漠，像邯郸的豆沫，石家庄的缸炉烧饼，唐山的酥糖，秦皇岛的皮皮虾，总能勾起心中最美好的回忆。
icebound最喜欢吃河北菜，于是他想要大厨做一桌河北菜宴请宾客。icebound购买了一些食材，并且制订了宴会的菜单。但是他并不知道这些食材是否足够，所以希望你写一个程序帮助他。
icebound将会给出每种食材的名称和数量，以及完整的菜单。菜单将包含每种菜品所需的食材及数量。菜单上的每道菜只需制作一次。
输入描述:
第一行给出两个整数 n , m，分别代表食材种类和菜品数量。
第 二 到第 n+1 行，每行一个由小写字母组成的字符串 $s_i$和一个数字 $a_i$，表示这种食材的名称和数量。
接下来 m 行，每行首先有一个整数 k，代表这种菜品所需的食材种类数。
随后将会有 k 个字符串，代表食材名称，每个字符串后跟有一个数字 $t_i$，用空格隔开，代表需要的食材数量。
$1\le n,m\le 1000，1\le k\le 10$且 $k\le n$
$1\le a_i,t_i\le 10^9$，$1\le |s_i|\le 20$
保证输入合法，食材名称不会相同，且菜谱中不会有未出现的食材。
输出描述:
如果食材足够将菜单上的所有菜品全部制作一遍，请输出一行“YES”，并且按照输入顺序输出剩下的食材以及对应的数量，每行一个食材，用空格将食材和其数量隔开。如果某种食材全部被用完，则不输出该食材。
如果不能，输出一行“NO”。
示例1
输入
5 3
water 100
flour 20
cabbage 71
pork 12
bean 5
2 water 20 flour 5
3 water 70 cabbage 54 pork 10
5 water 1 flour 1 cabbage 1 pork 2 bean 1
输出
YES
water 9
flour 14
cabbage 16
bean 4

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10010;
LL n,m,k;
unordered_map<string,LL>sum,q,use;
struct node
{
    string name;
    LL num;
}s[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].name>>s[i].num;q[s[i].name]=i;
    }
    bool flag=true;
    while(m--)
    {
        cin>>k;
        while(k--)
        {
            string x;LL c;cin>>x>>c;
            s[q[x]].num-=c;
            if(s[q[x]].num<0) {flag=false;break;}
        }
        if(!flag) break;
    }
    if(!flag) cout<<"NO\n";
    else
    {
        cout<<"YES\n";
        for(int i=1;i<=n;i++)
        {
            if(s[i].num>0) cout<<s[i].name<<' '<<s[i].num<<endl;
        }
    }
    return 0;
}

L.smart robot

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述:
Icebound dreams of being aLegendary grandmaster. So he built a smart robot to help him.
The robot works on a N*N matrix. All the numbers in the matrix are non-negative integers less than 10. The robot can move in the matrix. If it’s in the (x,y) position of the matrix, it can move to (x+1,y) , (x,y+1), (x-1,y), (x,y-1), which are the adjacent positions of the robot. But the robot has to operate inside the matrix. It can’t get out of the matrix.
The robot can start at any position in the matrix, take any step, and it can stop at any position in the matrix. We connect the numbers in the robot’s path in order to get a magic number. For example, if the robot takes 3 steps and passes through 3 numbers of the matrix, 0,7 and 8, the magic number is 78.All the magic numbers are non-negative integers, and the number generated by the robot does not contain leading 0.
Through the robot, icebound got a lot of magic numbers. Now he wants to know what isthe smallest magic number he can’t get.
输入描述:
The first line is an integer N, denoting the length and width of the matrix.
The next N lines, N numbers per line, separated by spaces, represent this matrix. Ensure that each number in the matrix is less than 10 and greater than or equal to zero.
The numbers in the matrix are randomly generated.
$1\le N\le 50$
输出描述:
One integer per line, indicating the smallest magic number that icebound can not get.
示例1
输入
4
1 2 3 4
3 6 7 8
0 1 5 4
9 1 1 1
输出
复制
17

思路：直观想象答案会很小，因为数的总数应该不会超过一定值，因此只需枚举若干个，第一个不存在的输出就好。但是这里的0搞得我一直tle，后来一想不用管0，多于若干位显然就无意义了，假设是000001，高位都为0也不会影响什么，因此只需标记搜索不超过若干位即可。
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110;
int n,t,m,k,a[N][N];
bool st[N][N],vis[1000010];
map<string,int>mp;
struct node
{
    int x,y;
    LL sum=0,num=0;
};
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
void bfs(int x,int y)
{
    queue<node>q;q.push({x,y,a[x][y],1});
    while(q.size())
    {
        node t=q.front();q.pop();
        if(t.num>=6) continue;
        vis[t.sum]=true;
        for(int i=0;i<4;i++)
        {
            int ix=t.x+dx[i],iy=t.y+dy[i];
            if(ix<1||iy<1||ix>n||iy>n) continue;
            q.push({ix,iy,t.sum*10+a[ix][iy],t.num+1});
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) bfs(i,j);
    for(int i=0;i<100000;i++)
        if(!vis[i]) {cout<<i<<' ';break;}
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖