鑫汇工作室邀请赛2-DIV2题解
以下为本次比赛的题解，请没能AC部分题目的同学仔细阅读。
希望发现问题或表述不清楚、不完整的地方的同学通过洛谷私信告诉我，会有相应的酷町豆奖励。
部分无需特别注意的点没有提到，敬请谅解。
本次比赛的题目难度较大（当然对于一些大佬们肯定非常简单），只有一位同学AK，买分这一题只有一位同学AC（除我以外）。
神秘对战游戏比买分那一题难度还要大很多，测试点给我的脑子都配炸了。
U190399 鑫汇工作室邀请赛2-DIV2签到题
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout<<1;
}U190651 斐波那契数列
根据题意，输出斐波那契数列的第n个数。
斐波那契数列的前2个数都是1，后面的每一个数都是前两个数的和。
n≤90，所以要用long long，不必用高精度进行求解。
F1：递推
学递推的第一课必学内容。
代码：
#include <bits/stdc++.h>
using namespace std;
long long f[91];
int n;
int main()
{
cin>>n;
f[1]=f[2]=1;
for(int i=3;i<=n;i++)
{
f[i]=f[i-1]+f[i-2];
}
cout<<f[n];
}F2：递归
学递归的第一课必学内容。
代码：
#include <bits/stdc++.h>
using namespace std;
long long f(int n)
{
if(n==1) return 1;
if(n==2) return 1;
return f(n-2)+f(n-1);
}
int main()
{
int a;
cin>>a;
cout<<f(a);
}显然，这样写必定会超时。
原因：分支过多，大量相同的东西被反复算。
献上一张丑陋的图片：
可以看到f(3),f(2),f(1)都被重复算了。
当n的数值逐渐增多，被重复算的函数的数量和次数也增多。
记忆化搜索可以有效地避免这种情况。
我们可以将算过的函数值存在一个数组中，当发现还要再算时，直接把这个数组中的那个函数的数值带进去。
具体可以询问老师或百度一下。
改进后的代码：
#include <bits/stdc++.h>
using namespace std;
long long f1[91];
long long f(int n)
{
if(f1[n]!=-1) return f1[n];
if(n==1) return 1;
if(n==2) return 1;
return f1[n]=f(n-2)+f(n-1);
}
int main()
{
memset(f1,-1,sizeof(f1));
int a;
cin>>a;
cout<<f(a);
}U190705 买分
根据题意，如果可以买来n分，输出需要花的最少的钱；如果不可以，输出-1。
先设定：
an表示买n分需要an元（1≤n≤10，n为整数，an是在买分表里面的）
fn表示买n分最少需要fn元（n为正整数）
这道题目需要分段递推：
第一段：n≤10
第二段：n＞10
我们先看第一段：
因为不一定买的分越多价钱越高，所以需要依次比较。
在看第二段：
取每种买法的最小值。
由于我的表达能力十分欠缺，举个例子说明一下：
假设我要买2分，
第一种：a1+a1
第二种：a2
取最小值即可。
假设我要买3分，
第一种：a1+a1+a1
第二种：a1+a2
第三种：a3
取最小值即可。
假设我要买11分，
第一种：f1+a10
第二种：f2+a9
第三种：f3+a8
第四种：f4+a7
第五种：f5+a6
第六种：f6+a5
第七种：f7+a4
第八种：f8+a3
第九种：f9+a2
第十种：f10+a1
取最小值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n,a[15],f[100005],x;//a,f的意思和前文相同
int main()
{
for(int i=1;i<=10;i++) cin>>a[i];
cin>>n>>x;
for(int i=1;i<=10;i++)
{
f[i]=a[i];
for(int j=1;j<i;j++)
{
f[i]=min(f[i],f[i-j]+a[j]);//取最小值
}
}//第一段
for(int i=11;i<=n;i++)
{
f[i]=0x3f3f3f3f;
for(int j=1;j<=10;j++)
{
f[i]=min(f[i],f[i-j]+a[j]);//取最小值
}
}//第二段
if(f[n]<=x) cout<<f[n];
else cout<<-1;
}U192775 加法和乘法
根据题意，输出两个数的和与积。
由于这两个数很大，需要用到高精度。
高精度加法和乘法可以看一下代码和注释、询问老师、百度一下。
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
void cf(string s1,string s2)
{
int a[105],b[105],c[10050];
memset(a,0,sizeof(a));//计算前一定要清0，在函数内定义的数组里的数字是随机的
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=s1.size(),b[0]=s2.size();//数组的第0位存储这个大数的位数
for(int i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-48;//倒序存储各位数值
}
for(int i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-48;//倒序存储各位数值
}
//高精度乘法
c[0]=a[0]+b[0];//假设结果的位数
for(int i=1;i<=a[0];i++)//不计算进位时每位的结果
{
for(int j=1;j<=b[0];j++)
{
c[i+j-1]+=a[i]*b[j];
}
}
int jw=0;//用来存储进位
for(int i=1;i<=c[0];i++)//计算进位
{
c[i]+=jw;//加上进位
jw=c[i]/10;//进位是现在这一位除以10
c[i]%=10;//现在的这一位%10
}
if(c[c[0]]==0) c[0]--;//调整结果的位数
for(int i=c[0];i>=1;i--) cout<<c[i];
}
void jf(string s1,string s2)
{
int a[105],b[105],c[10050];
memset(a,0,sizeof(a));//计算前一定要清0
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
a[0]=s1.size(),b[0]=s2.size();//数组的第0位存储这个大数的位数
for(int i=1;i<=a[0];i++)
{
a[i]=s1[a[0]-i]-48;//倒序存储各位数值
}
for(int i=1;i<=b[0];i++)
{
b[i]=s2[b[0]-i]-48;//倒序存储各位数值
}
//高精度加法
c[0]=max(a[0],b[0]);//暂且不考虑最高位进位的情况
int jw=0;//用来存储进位
for(int i=1;i<=c[0];i++)//先判断到c[0]位
{
c[i]=a[i]+b[i]+jw;//加上两数相同的位数和进位
jw=c[i]/10;//进位等于c[i]除以10
c[i]%=10;//某一位不可能是个多位数
}
if(jw)//如果最高位有进位
{
c[0]++;//位数加1
c[c[0]]=jw;//最高位等于这个进位
}
for(int i=c[0];i>=1;i--) cout<<c[i];
}
int main()
{
cin>>s1>>s2;
jf(s1,s2);
cout<<" ";
cf(s1,s2);
}U190401 鑫汇工作室邀请赛2-DIV2结束题
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout<<1;
}