级算法上机解题报告郑鹏飞Word文件下载.docx
《级算法上机解题报告郑鹏飞Word文件下载.docx》由会员分享，可在线阅读，更多相关《级算法上机解题报告郑鹏飞Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
voidH（intn,charstart,charover,charmiddle）
{
if（n==1）printf（"
%cto%c\n"
start,over）;
//一个盘子，从a-c
else
{
f（n-1,start,middle,over）;
//n-1个盘子，借助柱子c,从a-b
printf（"
f（n-1,middle,over,start）;
//n-1个盘子，借助柱子a,从b-c
}
}
usingnamespacestd;
intmain（）
charA='
A'
;
charB='
B'
charC='
C'
intn;
while（~scanf（"
%d"
&
n））
H（n,A,C,B）;
\n"
）;
零崎的人间冒险Ⅱ
106总提交人数:
127
零崎本以为他的无聊冒险马上就要结束了，然而实际上距离魔王的魔法成功发动还有很久很久，于是他的无聊冒险还可以继续……无聊的零崎需要给自己的冒险找点事做，然而实际上他的日常非常平和，如果说有什么意外的话，那就是他去打麻将了。
零崎在玩一种叫做日式麻将的竞技游戏，然而无聊的零崎总是遭遇别人立直需要防守的场面。
零崎在防守时，会跟打现物和搏筋兜牌两种技能，然而为了不被婊得太惨，零崎不会连续搏筋兜牌。
也就是说，零崎任意两次选择中不会都是搏筋兜牌。
那么对于n次舍牌，无聊的零崎会有多少种选择？
因为无聊的零崎可以打很久的麻将，所以n可能很大，无聊的零崎决定只要结果对100007求模后的选择数。
多组输入数据，每组一个数字n，1<
=n<
=Int_MAX
每组一行，只需要选择种数对100007求模后的结果。
3
听说这个也是很简单的，不然你们推推递推公式看？
ps：
n=1:
刚，怂
n=2刚怂，怂怂，怂刚
n=3刚怂怂，刚怂刚，怂怂怂，怂怂刚，怂刚怂
解题思路：
看到提示之后，明显得到类似于斐波那契数列的数列，f
（1）=2,f
（2）=3,f（3）=5……f（k）=f（k-1）+f（k-2）….
2.算法的选取：
另外斐波那契数列可以使用递归，也可以用非递归。
其实题目说n会很大，那么当递归时候必然会花费大量的时间。
（经过测试递归代码会WA，所以还是提交非递归代码。
）
3.算法差别有差别多大呢？
上课老师讲过斐波那契的时间复杂度：
递归计算：
（大于O（2^n）），等于O（（（1+5^0.5）/2）^n）
非递归的for循环：
O（n）；
另外可以参考13级的第二次算法上机危险的td-2013级算法上机之二-OJ3RD
4.参考代码：
（483ms,40232kb）
cstring>
#defineMAX_SIZE10000010
inta[MAX_SIZE];
memset（a,0,sizeof（a））;
a[1]=2;
a[2]=3;
for（inti=3;
i<
=n;
i++）
a[i]=a[i-1]+a[i-2];
a[i]%=100007;
%d\n"
a[n]）;
Let'
splayagame
38总提交人数:
61
这是一个古老而无聊的游戏，这是一个欧几里得躺枪的游戏。
Nova君和LaoWang决定一分胜负。
给定两个正整数a,b。
Nova君和LaoWang轮流从中将较大的数字减去较小数字的整数倍（1倍，2倍等等）。
并且保证每次减完不会出现负数的情况。
由Nova君先手。
最终在自己回合将其中一个数变为0的一放获胜。
两个人智商都还行，都会采取最优策略，谁会赢呢？
多组测试数据。
对于每组测试数据，给出两个数字a和b（保证Int范围内）
对于每组数据，输出获胜者的名字。
3412
1524
Nova
LaoWang
题目描述：
欧几里得游戏：
2个玩家，Nova，LaoWang，以2个自然数开始。
第一个玩家，Nova，从2个数中较大数中减去较小数的任何正整数倍，只要差为非负即可。
然后，LaoWang，对剩下的2个数进行同样的操作，然后Nova，然后....。
直至较大数减去较小数的某个倍数之后差为0为止。
布尔递归求解。
Boolgame（inta,intb）
假定：
找到a,b最大的，下面分析将a视为最大值,a=max（a,b）;
1.如果a%b==0，先开始的玩家肯定赢。
Returntrue（返回true,代表Nova获胜）
2.如果a/b<
2，（其实也就是0<
a-b<
b），那么Nova第一次只能进行a-b操作，因为相减结果非负。
接下来LaoWang开始进行游戏，如果将LaoWang视为游戏的第一开始人，那么同样可以使用Nova的递归函数来进行判断。
不过有一点需要注意，就是当LaoWang获胜的时候，Nova则输掉游戏，应该返回取反。
Return!
game（a-b,b）;
3.如果a>
2*b,那么returntrue。
这种当a>
2*b情况下，第一个人拥有先手优势，好比狼人中的首杀保护。
下面分析在a>
2*b时候，先手获胜的原因：
（1）当（b,a%b）是必输状态的时候，Nova需要将这两个数（a,b）转化为（a%b+b,b）这样LaoWang处于必输状态。
因为Nova经过运算之后，两个数从（a,b）变为（a%b+b,b），LaowWang经过运算之后，两个数变为（a%b,b），这样Nova必胜。
（2）当（a%b+b,b）是必输状态时，Nova需要将这两个数（a,b）转化为（b,a%b+b）.这样LaoWang拿到的两个数就是（b,a%b+b）,运算之后得到（b,a%b），Nova获胜。
a>
2b:
假如在某个状态（a,b）（a>
b）时，有a-b>
b，那么这时一定先走的必胜。
因为此时可以拿成（a%b,b）或（a%b+b,b），而这两个状态其中必有一个是先走必败的。
参考代码：
（2ms1152kb）
boolgame（inta,intb）
inttemp;
if（a<
b）
swap（a,b）;
if（a%b==0）
returntrue;
elseif（a-b<
b）return!
（game（a-b,b））;
//因为是轮流，两次取非为正，所以LaoWang回合
//递归函数若为1，则递归完成后为0
elsereturntrue;
inta,b;
%d%d"
a,&
b））
if（game（a,b））printf（"
Nova\n"
elseprintf（"
LaoWang\n"
零崎的人间冒险Ⅲ
91总提交人数:
122
不打麻将的零崎特别的无聊，所以他又四处乱逛了。
四处乱逛的无聊零崎遇到了另一个特别无聊的人，因为这个人竟然在无聊的算各种一元n次多项式a0+a1x+a2x^2+……+anx^n！
这个无聊的人算的实在太慢了令零崎忍不住想开启嘲讽模式，所以现在，快来给零崎搞一个能快速计算多项式的东西吧。
（其实可能也不用特别快
多组输入数据。
每组数据以多项式次数n开始，下一个数字为变量x，之后n+1个数字为系数a0……an。
输入数据保证在int范围内
每行一个结果，也许n特别大所以最后结果还是对1e6+7求模吧……
1212
321234
5
49
你听说过上古卷轴吗？
你听说过彩虹小马吗？
你听说过HornerRule（霍纳规则）吗？
1.算法选取：
看提示，很有用滴。
霍纳规则？
课本（P23练习题）
霍纳规则的代码片段：
y=0;
fori=ndownto0
y=ai+x*y
也就是P（x）=a0+x（a1+x（a2+x（a3+x（….+x（an-1+xan）…））
算法的时间复杂度为O（n），计算过程中需要进行模除
2.细节注意：
最后结果对1e6+7求模
（663ms,1173kb）
#definemax_size1000010
inta[max_size];
intn,x;
scanf（"
x）;
intans=0;
for（inti=0;
i<
i++）
a[i]）;
for（inti=n;
i>
=0;
i--）
ans=a[i]+x*ans;
ans%=1000007;
//注意这里是mod1000007一共5个0！
ans）;
Inversenumber：
Reborn
63总提交人数:
92
输入一个正整数n，随后给出一个长度为n的整数序列a1,a2,a3...an。
求给定序列的逆序数。
概念回顾：
逆序对：
数列a[1],a[2],a[3]…中的任意两个数a[i],aj，如果a[i]>
a[j],那么我们就说这两个数构成了一个逆序对。
逆序数：
一个数列中逆序对的总数。
对于每组测试数据，给出序列长度n，和一个长度为n的序列a1,a2,a3...an
（0<
n<
=10^6，保证ai在int范围内）
对于每组数据，输出该序列的逆序数。
7
3548269
6
1、用n^2的算法是不行不行滴╮（╯_╰）╭
2、分治法
1.算法的选取以及原因：
O（n^2）会超时！
提示给出来了。
分治法：
采用归并排序。
在这里选2.择归并排序的原因：
归并排序的时间复杂度为O（nlgn），另外算法可以很好地进行判断逆序数的个数。
3.数据类型的选取以及原因：
考虑数据结果是否会超过int，输入的n在int范围之内，worst-case:
单调递增序列。
得到此时逆序对=（n-1）*n/2;
结果超过int，使用longlong数据类型。
归并排序中间需要在归并中计算逆序对的个数。
Ex：
归并排序的过程：
假如输入数据：
N=7;
接下来的7个数组成以下序列
52471326
具体过程参照下面的图示：
（201ms1992kb）
#defineMaxsize100010
intarray[Maxsize];
intMergeArray（intarry[],intstart,intmid,intend,inttemp[]）//数组的归并操作
inti=mid;
intj=end;
intk=0;
intcount=0;
//count表示逆序对的个数
while（i>
=start&
&
j>
mid）
if（arry[i]>
arry[j]）
temp[k++]=arry[i--];
count+=j-mid;
//这里的count需要加上j-mid，根据逆序对的定义
temp[k++]=arry[j--];
=start）
while（j>
for（i=0;
k;
arry[end-i]=temp[i];
returncount;
//返回逆序数
longlongPairs（intarry[],intstart,intend,inttemp[]）
longlongans=0;
//总共的逆序数
if（start<
end）
intmid=（start+end）/2;
ans+=Pairs（arry,start,mid,temp）;
//数组的左边
ans+=Pairs（arry,mid+1,end,temp）;
//数组的右边
ans+=MergeArray（arry,start,mid,end,temp）;
//归并，计算逆序数
returnans;
longlongInversePairs（intarry[],intlen）//第一个参数是数组，第二个参数是长度
int*temp=newint[len];
longlongnum=Pairs（arry,0,len-1,temp）;
delete[]temp;
returnnum;
n;
array[i]）;
longlongans=0;
ans=InversePairs（array,n）;
%lld\n"
//longlong的输出格式%lld或者%I64d
零崎的人间冒险Ⅳ
在干掉了guangtou之后，无聊的零崎又去找事了……
说起来零崎前几周学到了一个叫做Apriori算法的东西，其第一步是挑出所有出现频率大于某个给定值的数据。
然而作为一个具有一定程度的强（qiǎng）迫（pò
）症的人，零崎显然希望先排个序再对其子集进行操作。
于是，现在的任务是简单的升序排列。
多组输入数据，每组两行，第一行为一个整数n。
第二行为n个整数。
每组一行，输出n个整数的升序排列，两个整数之间用一个空格隔开。
65231
12356
排序，冒泡、归并等等.
1.冒泡排序：
两个嵌套的for循环，加上判断语句，交换数值；
2.归并排序：
递归方法，和上面一道题的方法基本相同，不需要输出逆序数即可。
3.参考代码冒泡排序：
（87ms,1192kb）
#include<
intx[1010];
intans;
while（cin>
>
n）
memset（x,0,sizeof（x））;
ans=0;
cin>
x[i];
for（intj=0;
j<
n-i-1;
j++）
if（x[j]>
x[j+1]）
swap（x[j],x[j+1]）;
ans++;
cout<
<
x[i]<
"
"
endl;
4.参考代码归并排序：
（12ms1216kb）
#defineMAX_SIZE1010
intarrs[MAX_SIZE];
int*tempArr=newint[MAX_SIZE];
voidmergeArray（int*arrs,int*tempArr,intleft,intmiddle,intright）{
inti=left,j=middle;
intm=middle+1,n=right;
intk=0;
while（i<
=j&
m<
=n）{
if（arrs[i]<
=arrs[m]）
tempArr[k++]=arrs[i++];
tempArr[k++]=arrs[m++];
=j）
while（m<
=n）
i<
k;
arrs[left+i]=tempArr[i];
voidmergeSort（int*arrs,int*tempArr,intleft,intright）{
if（left<
right）{
intmiddle=（left+right）/2;
mergeSort（arrs,tempArr,left,middle）;
mergeSort（arrs,tempArr,middle+1,right）;
mergeArray（arrs,tempArr,left,middle,right）;
arrs[i]）;
mergeSort（arrs,tempArr,0,n-1）;
for（inti=0;
n;
%d"
arrs[i]）;
升级会员 