NOIP2012 提高组 复赛 day1 game 国王游戏 再见
2017-1-15 20:48
1.经过近半年的历练，重回此题，一看样例解释，马上发现这是一个回溯问题，需用到深度优先遍历，效果等同于找出本人水平有所上升，开始编码。
2.看了下数据量，注意剪枝，应该能得更多的分。
3.随着编程的深入，发现还不是上面认识的问题，这里检讨一下。
4.此题不易，搜索网络，发现是贪心+高精度算法，好吧，继续学习。
5.
考试中容易想到的方法，与http://blog.csdn.net/alan_cty/article/details/50889524雷同。
我们设
受http://blog.sina.com.cn/s/blog_b187cbe10101dvey.html启发，下面给出按A*B的递赠数列排序的证明，考场中不可能花这么多时间，此类证明属于事后诸葛亮。
考虑交换相邻两个二元组的影响，交换i和i+1，实际上只影响到Fi和Fi+1
设T=A1*A2*A3*……*Ai-2*Ai-1
方案A：Fi=T/Bi,Fi+1=T*Ai/Bi+1 (i在i+1之前)
方案B：Fi=T/Bi+1,Fi+1=T*Ai+1/Bi (i+1在i之前)
1.若：1/Bi<Ai/Bi+1,1/Bi+1<Ai+1/Bi
(1)若A方案优于B方案,Ai/Bi+1<Ai+1/Bi
要求：Ai*Bi<Ai+1*Bi+1
(2)若B方案优于A方案,Ai+1/Bi<Ai/Bi+1
要求：Ai+1*Bi+1<Ai*Bi
此种情况要求，按A*B的递赠数列排序。
2.若1/Bi<Ai/Bi+1,1/Bi+1>=Ai+1/Bi
(1)若A方案优于B方案, Ai/Bi+1<=1/Bi+1，显然不成立。
(2)若B方案优于A方案,Ai/Bi+1>=1/Bi+1，显然成立。
此种情形，只有B方案优于A方案。
要求：
1/Bi<Ai/Bi+1=>Ai*Bi>Bi+1;
1/Bi+1>=Ai+1/Bi=>Ai+1*Bi+1<=Bi+1
即Ai*Bi>Bi+1>=Ai+1*Bi+1=>AiBi>=Ai+1*Bi+1
此种情况要求，按A*B的递赠数列排序。
3.若1/Bi>=Ai/Bi+1,1/Bi+1<Ai+1/Bi
(1)若A方案优于B方案,1/Bi<=Ai+1/Bi,显然成立。
(2)若B方案优于A方案, 1/Bi>Ai+1/Bi,显然不成立。
此种情形，只有A方案优于B方案。
要求：
1/Bi>=Ai/Bi+1=>Ai*Bi<=Bi+1即Ai*Bi<=Bi+1<=Ai+1*Bi+1即
Bi<=Ai*Bi<=Bi+1<=Ai+1*Bi+1
1/Bi+1<Ai+1/Bi=>Ai+1*Bi+1>Bi即Ai+1*Bi+1>Bi
综上：Bi<=Ai*Bi<=Bi+1<=Ai+1*Bi+1
此种情况要求，按A*B的递赠数列排序。
4.若1/Bi>=Ai/Bi+1,1/Bi+1>=Ai+1/Bi
(1)若A方案优于B方案,1/Bi<=1/Bi+1 即Bi+1<=Bi
要求：1/Bi>=Ai/Bi+1=>Ai*Bi<=Bi+1
即Ai*Bi<=Bi+1<=Ai+1*Bi+1;
1/Bi+1>=Ai+1/Bi=>Ai+1*Bi+1<=Bi;
Ai+1*Bi+1<=Bi<=Ai*Bi
显然矛盾，此种情形不成立。
(2)若B方案优于A方案,1/Bi>=1/Bi+1即Bi+1>=Bi
要求：1/Bi>=Ai/Bi+1=>Ai*Bi<=Bi+1
即Ai*Bi<=Bi+1<=Ai+1*Bi+1;
1/Bi+1>=Ai+1/Bi=>Ai+1*Bi+1<=Bi;
Ai+1*Bi+1<=Bi<=Ai*Bi
显然矛盾，此种情形不成立。
此种情况，没有最优方案。
综合以上四点，最有方案要求按A*B的递赠数列排序。
6.按一般的情形进行编码，不考虑高精度算法，猜测能得60分。
7.提交，得分60，没有采用高精度算法，里面用了long long 尽可能得扩充数据长度，下面的任务是采用高精度算法。
8.想一想高精度算法，结果的长度不确定，乘法：存储数据若是自左往右，要考虑堆栈，若是自右往左，要考虑最大长度；除法觉得相比乘法，简单些。
9.先将当前数据转化为字符数据，可以采用函数(整数转化为字符函数)，也可以自个编个函数(采用除、模
方式)，
10.是搜索网络，学习高精度算法，还是自个尝试编一个呢，为了提升能力，选择后者。
11.仔细想了想，用字符来计算乘还是简单的，设置一个进位数组即可，但除法感觉遇到麻烦，需要借位，那么采用移动栈的top标识来处理。看还是不看他人写法，为了提升能力，选择后者。
12.准备用字符数组来存储较长整数，写着写着，觉得挺烦，马上果断改整数数组，希望能简洁。
13.高精度算法，乘法编好，没有参考任何资料，独立完成的，如下：
//2012 game 国王游戏 高精度算法 乘multply 除divide
#include <stdio.h>
#include <string.h>
int product[10000];//乘积
int quotient[10000];//商数
int carry[10000];//进位
//高精度算法*
void multply(int *a1,int na1,int *b1,int nb1,int *product,int *np){//na1字符串a1长度，nb1字符串b1长度//np乘积数字长度
int i,j;
int a2,b2,p,c;
memset(product,0,sizeof(product));
for(i=0;i<nb1;i++){
memset(carry,0,sizeof(carry));
for(j=0;j<na1;j++){
product[j+i]+=b1[i]*a1[j]+carry[j+i];
carry[j+i+1]=product[j+i]/10;
product[j+i]%=10;
}
product[j+i]+=carry[j+i];//最高位进位处理
}
if(product[nb1+na1-1]==0)
*np=nb1+na1-1;
else
*np=nb1+na1;
}
void divide(int *a1,int na1,int *b1,int nb1,int *quotient,int *nq){
}
int main(){
int a[]={9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9};
int b[]={9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9};
int i;
int np;
int nq;
multply(a,18,b,18,product,&np);
for(i=np-1;i>=0;i--)
printf("%d",product[i]);
return 0;
}
14.高精度算法，除法，感觉还挺难的，无从下手，先想一想，再说。
15.参考了他人代码，才发现编写的高精度算法是一个普适算法，难度过大，可以考虑编写超过long long 的数据除以long long 的数据，那么，难度一下降低了好几个台阶。目标是独立完成。
16.高精度除，很快编好，编着编着才发现曾经编过，核心代码类似《算法竞赛入门经典（第2版）》P35 习题2-5 分数化小数
2017-1-26 8:47
17.经过一番努力，发现问题重重，无奈，寻找好的编码，进行学习。在洛谷里寻找耗时最短，内存最少的代码进行研究，发现许多代码是ifelse语句，也就是直接对答案进行输入输出，很多是骗人的写法，好不容易，找了一个耗时15ms的代码进行学习研究。
18.代码写得确实好，a[0]用来存储位数，a[1]开始每个元素用来存储整数的4位。算法的局限在于除运算，除数不能超过4位数。
2017-1-29 15:05
19.程序是这样的，想想很难，但编着编着，也就这么回事。
附上AC代码，编译环境Dev-C++4.9.9.2
//2012 国王游戏 game9
#include <stdio.h>
#include <string.h>
struct node{
int left;
int right;
int w;//左右手乘积
}m[1000+10],k,mt;//minister,king
int a[1000+10],b[1000+10],ans[1000+10];//product quotient [0]储备位数
void multply(int *a,int x){//高精度*单精度 高精度每个整数数组元素表示单精度4位
int i,j;
int t;
j=0;
for(i=1;i<=a[0]||j;i++){
t=a[i]*x+j;
a[i]=t%10000;//留下的数据
j=t/10000;//进位
}
a[0]=i-1;
}
void divide(int *a,int x){//高精度/单精度 高精度每个整数数组元素表示单精度4位,注意x要控制在4位数，否则，容易越界
int i,j;
int t;
j=0;
for(i=a[0];i>=1;i--){
t=a[i]+j*10000;
b[i]=t/x;
j=t%x;
}
for(i=a[0];i>=1;i--)
if(b[i]!=0)
break;
if(i==0)
b[0]=1;
else
b[0]=i;
}
int cmp(int *b,int *a){//高精度比大小 b>a 返回值大于0,b==a返回值为0
int i;
if(b[0]!=a[0])
return b[0]-a[0];
for(i=b[0];i>=1;i--)
if(b[i]!=a[i])
return b[i]-a[i];
return 0;
}
int main(){
int n;
int i,j;
scanf("%d",&n);
scanf("%d%d",&k.left,&k.right);
for(i=1;i<=n;i++){
scanf("%d%d",&m[i].left,&m[i].right);
m[i].w=m[i].left*m[i].right;
}
for(i=1;i<=n;i++)//冒泡排序，由小到大排序，因数据量不大，故采用
for(j=i+1;j<=n;j++)
if(m[i].w>m[j].w){
mt=m[i];
m[i]=m[j];
m[j]=mt;
}
memset(ans,0,sizeof(ans));
a[0]=1;
a[1]=k.left;
ans[0]=1;
for(i=1;i<=n;i++){
divide(a,m[i].right);
if(cmp(b,ans)>0)//此处一直会出问题不是if(cmp(b,ans))而是if(cmp(b,ans)>0),因为com(b,ans)<0 if语句也执行，曾经犯过这样的错
memcpy(ans,b,(b[0]+1)*sizeof(int));
multply(a,m[i].left);
}
//打印结果
printf("%d",ans[ans[0]]);
for(i=ans[0]-1;i>=1;i--)
printf("%04d",ans[i]);
printf("\n");
return 0;
}
附上60分代码，编译环境Dev-C++4.9.9.2
//2012 game 国王游戏
#include <stdio.h>
struct node{
int a;
int b;
long long product;//乘积
}minister[1000+10],king,t;
long long gold[1000+10];
int main(){
int n;
int i,j;
int a,b;
long long ans;
long long t2;
scanf("%d",&n);
scanf("%d%d",&king.a,&king.b);
for(i=1;i<=n;i++){
scanf("%d%d",&a,&b);
minister[i].a=a;
minister[i].b=b;
minister[i].product=a*b;
}
for(i=1;i<=n;i++)//因数据量比较小，采用冒泡排序，按a*b的乘积自小到大排序
for(j=i+1;j<=n;j++)
if(minister[i].product>minister[j].product){
t=minister[i];
minister[i]=minister[j];
minister[j]=t;
}
for(i=1;i<=n;i++){//计算每个大臣手上金币
ans=king.a;
for(j=1;j<=i-1;j++){
ans*=minister[j].a;
}
ans/=minister[i].b;
gold[i]=ans;
}
for(i=1;i<=n;i++)//按金币自大到小排序
for(j=i+1;j<=n;j++)
if(gold[i]<gold[j]){
t2=gold[i];
gold[i]=gold[j];
gold[j]=t2;
}
printf("%lld\n",gold[1]); //对%lld输出总有隐忧，因linxu与windows下不同
return 0;
}