首页 > 代码库 > vijos1009-1011
vijos1009-1011
1009：数论 扩展欧几里得算法
1010：高精+细心模拟
1011：记忆化搜索
1009：扩展欧几里得
其实自己对扩展欧几里得算法一直很不熟悉...应该是因为之前不太理解的缘故吧
这次再次思考，回看了某位大神的推导以及某位大神的模板应该算是有所领悟了
首先根据题意：
L1=x+mt; L2=y+nt;
可知当两人相遇： L1-L2=k*l;
即 :(m-n)t-(y-x)=kL
根据整除取余的方法：[ a/b=c...d --> a-d=c*b;]
可得到：(m-n)t mod l=y-x;
得到线性同余方程
此方程有解当且仅当 y-x 能被 m-n 和l的最大公约数整除接下来
就要用到欧几里得算法的扩展应用中的三条定理：
定理一：如果d = gcd(a, b)，则必能找到正的或负的整数k和l，使d = a*x+ b*y。 定理二：若gcd(a, b) = 1，则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。（恒等于）
定理三：若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。
求a * x + b * y = n的整数解。 1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a‘ * x + b‘ * y = n‘，此时Gcd(a‘,b‘)=1; 2、利用上面所说的欧几里德算法求出方程a‘ * x + b‘ * y = 1的一组整数解x0,y0，则n‘ * x0,n‘ * y0是方程a‘ * x + b‘ * y = n‘的一组整数解； 3、根据数论中的相关定理，可得方程a‘ * x + b‘ * y = n‘的所有整数解为： x = n‘ * x0 + b‘ * t y = n‘ * y0 - a‘ * t
代码：
# include <stdio.h>#include<cmath>using namespace std;__int64 gcd(__int64 a,__int64 b){ if(b==0) return a; return gcd(b,a%b);}void exgcd(__int64 a,__int64 b,__int64 &m,__int64 &n){ if(b==0) { m=1; n=0; return ; } exgcd(b,a%b,m,n); __int64 t; t=m; m=n; n=t-a/b*n;}int main(){ __int64 x,y,m,n,l,a,b,c,k1,k2,r,t; while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF) { a=abs(n-m); b=l; c=x-y; r=gcd(a,b); if(c%r) { printf("Impossible\n"); continue; } a/=r; b/=r; c/=r; exgcd(a,b,k1,k2); t=c*k1/b;//mark k1=c*k1-t*b;// if(k1<0) k1+=b; printf("%I64d\n",k1); } return 0;}
最后，这里需要注意一个地方：
就是k1的取值问题...
此时方程的所有解为：x=c*k1-b*t,x的最小的可能值是0，令x=0可求出当x最小时的t的取值，但由于x=0是可能的最小取值，那么由计算机的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中，求出的x可能会小于0，当x小于0时，加上b，也就是距离；如果代回后x仍是大于等于0的，那么不需要再做修正。
vj1010:高精乘+细心模拟
这题的话思路挺简单的，主要是打一个高精乘，然后考虑一些细节的东西
码得挺少时间的，但是调错调了很久...
讲一下思路吧：
就是读入的时候，先把小数点去掉，mark一下小数点的位置
去掉小数点之后也就进行高精乘法即可，去掉前导零
之后计算一下小数点的位置
再去掉小数点后多余的零
以及特判k=1的情况，直接输出答案
细节的地方主要就是在模拟上吧，
我WA了几次：
1.当小数点后面没有数字的时候，当然不需要输出小数点...这个没有考虑进去
2.没有特判k=1的情况，因为答案是放在c数组里，所以当k=1的时候，没有答案
3.数组开小了....
附上代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;char s[201];int n,m;int l,mark;bool f;int a[100050],b[101],c[100001];void into(){ l=strlen(s); int i=1; f=true; while(i<=l){ if(s[i]==‘.‘ && f){ mark=i; f=false; } else{ a[i]=s[l-i]-‘0‘; i++; } } mark=l-mark; l=i-1; for(int j=mark;j<l;j++) a[j]=a[j+1]; for(int j=1;j<=l;j++){ b[j]=a[j]; }}int main(){ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); //freopen("data.txt","r",stdin); while(cin>>s>>n){ if(n==1){ cout<<s<<"\n"; continue; } memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); mark=0; into(); l-=1; int bl=l; int sum=mark-1; for(int k=2;k<=n;k++){ memset(c,0,sizeof(c)); for(int i=1;i<=l;i++) for(int j=1;j<=bl;j++){ c[i+j-1]+=(a[i]*b[j]); c[i+j]+=(c[i+j-1]/10); c[i+j-1]%=10; } l+=bl; l++; mark=sum*k; while(l>1 && !c[l] && l>mark) l--; for(int i=1;i<=l;i++) a[i]=c[i]; } for(int i=l;i>mark;i--){ printf("%d",c[i]); } int t=1; for(int i=1;i<=mark;i++){ if(c[i]==0){ t++; } else break; } if(t-1==mark){ cout<<"\n"; continue; } else{ cout<<"."; for(int i=mark;i>=t;i--){ printf("%d",c[i]); } cout<<"\n"; } } fclose(stdin); fclose(stdout); return 0;}
vj1011:记忆化搜索
这题就是很简单的记忆化搜索即可，和经典题目滑雪简直一模一样
对于记忆化搜索，我也是暑假看了ccy大神的题解才有所领悟的
其实也就是DFS+mark
主要的部分int search(int x,int y){ if(f[x][y]>0) return f[x][y]; int ans=0; int xx,yy; for(int i=0;i<4;i++){ xx=x+dx[i]; yy=y+dy[i]; if(xx>0 && xx<=n && yy>0 && yy<=m && a[x][y]>a[xx][yy]){ ans=max(ans,search(xx,yy)); } } return f[x][y]=ans+1; }
恩..其实也说不出来记忆化搜索这类题目的技巧吧...多感受码起来挺简单的：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <queue>#include <algorithm>#include <cmath>using namespace std;const int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};int a[501][501],f[501][501];int h,n,m,maxn=0,ans;int max(int a,int b){ return a>b?a:b;}int search(int x,int y){ if(f[x][y]>0) return f[x][y]; int ans=0; int xx,yy; for(int i=0;i<4;i++){ xx=x+dx[i]; yy=y+dy[i]; if(xx>0 && xx<=n && yy>0 && yy<=m && a[x][y]>a[xx][yy]){ ans=max(ans,search(xx,yy)); } } return f[x][y]=ans+1; }int main(){ memset(f,-1,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; ans=-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(f[i][j]==-1) ans=max(ans,search(i,j)); } printf("%d\n",ans); return 0;}
vijos1009-1011
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。