2022河南萌新联赛第（二）场——B.宝石 C.斩龙 G.无限

河南萌新联赛第（二）场——B.宝石 C.斩龙 G.无限"/>

2022河南萌新联赛第（二）场——B.宝石 C.斩龙 G.无限

目录

B.宝石

题目描述：

输入描述:

输出描述:

分析：

代码实现：

 1.错误代码（通过90%测试样例）

原因：

2.AC代码

总结：

C.斩龙

1.题目描述：

1）输入描述:

2）输出描述:

2.分析：

3.代码实现：

G.无限

1.题目描述

1）输入描述: 

2）输出描述:

2.分析：

3.代码实现：

---

 

B.宝石

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述：

小Y得到了一堆宝石，但是其中有一些宝石是假的没有价值，显然小Y并不想要这些假的宝石，小Y被告诉了一个鉴别真假宝石的方法。将这些宝石排成一行，按照从 1∼n标上标号并得出其真实度，如果第 i个宝石的真实度等于标号大于 i 的三个宝石的真实度乘积(可以使用标号相同的三个宝石)，这个宝石被认为是真的，你能帮小Y找出所有真的宝石的数量吗。

输入描述:

 第一行一个整数 n (4≤n≤1500)，表示所有宝石数量。

第二行 n个整数 (−1e6≤ai≤1e6)，表示每个宝石的真实度。

输出描述:

一个整数，表示所有真宝石的数量。

分析：

此题n的范围较小显然复杂度为O（n*n）不会超时，允许双层for循环 ，可以往此方向考虑。

• 标号>i
• 某个数等于三个数的乘积（三个数的乘积直接枚举显然不太现实需要转化，也就是存在三个因数，可以确定的是，如果是真宝石，那么数组中某一个数肯定是它的因数，此时相当于有一个确定的因数去找另外两个，而此时并不需要确切知道，只需知道其积）

代码实现：

 1.错误代码（通过90%测试样例）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4;
int a[N];
map<ll, int>mp;
void solve()
{int n,cnt=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n-1;i>=1;i--){for(int j=i+1;j<=n;j++)mp[a[i+1]*a[j]]=1;//遍历a[i]之后的所有数for(int j=i+1;j<=n;j++){//0不能作除数if(!a[j])continue;else if(a[i]%a[j]==0)//a[j]是a[i]的因数，找是否存在另一个因数{if(mp[a[i]/a[j]]){cnt++;break;}}}}cout<<cnt;}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T;//cin>>T;T=1;while(T--){solve();
}}

错误样例如图： 

原因：

显然0不是正确答案，再看代码可以发现 i 从n-1开始所以第一次a[i]==0,a[j]==0,直接判断a[j]为0就通过continue回到了内层循环头部没有判断后续是否有乘积为0，少计算了cnt。

2.AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4;
int a[N];
map<ll, int>mp;
void solve()
{int n,cnt=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n-1;i>=1;i--){for(int j=i+1;j<=n;j++)mp[a[i+1]*a[j]]=1;//记录第i+1个与其后每一个数的乘积（包括自身平方）//遍历a[i]之后的所有数for(int j=i+1;j<=n;j++){//先判断a[i]是否为0，再找mp中是否有0if(a[i]==0){if(mp[0])cnt++;break;}//0不能作除数if(!a[j])continue;else if(a[i]%a[j]==0)//a[j]是a[i]的因数，找是否存在另一个因数{if(mp[a[i]/a[j]]){cnt++;break;}}}}cout<<cnt;}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T;//cin>>T;T=1;while(T--){solve();
}}

总结：

1. for循环从数组末端开始往前 ，保证题中所说的标号大于 i ；
2. 题目中所说某个数等于三个数的乘积,也就是说其后存在该数的因数，那么一定会存在a[i]%a[x]==0（n>=x>i）,这个很好判断，那么就需要知道是否存在另外两个数，其乘积等于a[i]/a[x],问题转化为求i之后的任意两个数的乘积
3. 用一个内层for循环将i+1到n进行两两相乘，固定住第i+1个数，将指针j不断移动记录乘积并用map标记，此操作记录了i后面的每两个数的乘积
4. 一个for循环计算乘积同时另一个for进行判断

C.斩龙

1.题目描述：

在一个星球上存在两种势力： Dragon，Virm，Franxx。Franxx是守护家园的使者；而Dragon，Virm是破坏和平的侵略者（Dragon是Virm的手下）。

为了捍卫和平，Franxx展开了对恶势力的战斗。

该星球存在一个Franxx，一只Virm，和 x 只Dragon，他们都有一个生命值和一个攻击力（所有Dragon的生命值与攻击力相同）。

Franxx会先对Dragon发动攻击，当Dragon剩 k 只时（0≤k≤x），Virm会加入战斗。

注：Franxx先发动攻击；Franxx将Dragon击倒完才能攻击Virm，且 Dragon是一只一只上的（被攻击的Dragon才能对Franxx造成伤害）。

1）输入描述:

第一行两个整数 A1,H1表示 Franxx 的攻击力和生命值；
第二行三个整数 A2,H2,x表示 Dragon的攻击力，生命值和个数；
第三行一个整数 k ，如题所述。
第四行两个整数 A3,H3，表示 Virm的攻击力，生命值；
数据范围：
1≤A1,A2,A3≤1e6 
1≤H1,H2,H3≤1e6
0≤x≤1e9
0≤k≤x

2）输出描述:

输出一行。若能击败邪恶势力，输出“Franxx”的攻击次数。
不能击败邪恶势力，输出“No Franxx!”。（输出不带引号）

2.分析：

此题为模拟题，难度不大 ，答案要求Franxx的攻击次数，该次数包括击败x只Dragon和一个virm所需次数；无法击败的情况：Franxx生命被消耗完

3.代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int M=1e9;
map<ll,int>mp,res;
string s="No Franxx!";
void solve()
{ll ans=0;ll fa,fh,da,dh,x,k,va,vh;cin>>fa>>fh>>da>>dh>>x>>k>>va>>vh;/*进攻次数：cnt ; k只前：生命减少值----（x-k）*da*cnt------*//* k只后：生命减少值----(k+cnt_v)*va+da*cnt*k------*//*总生命减少值：(k+cnt_v)*va+da*cnt*x------*//*---------cnt_d:F打败一只D所需次数   cnt_v:F打败V所需次数-------*/ll cnt_d=dh/fa,cnt_v=vh/fa;if(dh%fa)cnt_d++;if(vh%fa)cnt_v++;//坏人进攻次数应比守护者进攻次数少一次，当只剩k只时，每一次都有Virm的进攻fh=fh-(x*da*(cnt_d-1)+(k+cnt_v-1)*va); if(fh<=0)cout<<s;else {//总次数ans=cnt_d*x+cnt_v;cout<<ans;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();
}

G.无限

1.题目描述

 给定一个无限集合，已知集合中存在一个 1，集合中元素满足以下性质：

1.  如果 x 在无限集合中，那么 x*4也在无限集合中。
2.  如果 x 在无限集合中，那么 x*2+1也在无限集合中。

问：给定一个正整数 p，求无限集合中小于 2^p 的数的个数(对 998244353 取模)。 

1）输入描述: 

一行，一个整数 p（1≤p≤10^6） 。

2）输出描述:

一个整数，为无限集合中小于 2^p 的数的个数。

2.分析：

分析：p可达到10^6，显然求2^p不太现实，将集合的一部分元素列举出来并升序排列（便于计数），到p=6，观察答案，很明显答案满足规律1+2+1=4,2+4+1=7……类似于斐波那契数列，那么此题就简单了。

3.代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int Mod=998244353;
typedef long long ll;
int p;
ll a[N];
void solve()
{cin>>p; a[1]=1;a[2]=2;for(int i=3;i<=p;i++)a[i]=a[i-1]%Mod+a[i-2]%Mod+1;cout<<a[p]%Mod;
}
int main()    
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>p;int T;//cin>>T;T=1;while(T--){solve();}}

tips：不要忘记取模！！！