做印刷网站公司哪家好,网页制作如何添加背景图片,江门网站如何制作,发布视频的平台大全目录
x进制减法
数组切分
gcd
青蛙过河 x进制减法 其实就是一道观察规律的题。你发现如果a这个位置上的数x#xff0c;b这个位置上的数是y#xff0c;那么此位置至少是max(x,y)1进制。一定要把位置找对啊
#include bits/stdc.h
using namespace std;
typedef l…目录
x进制减法
数组切分
gcd
青蛙过河 x进制减法 其实就是一道观察规律的题。你发现如果a这个位置上的数xb这个位置上的数是y那么此位置至少是max(x,y)1进制。一定要把位置找对啊
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e510,mod1000000007;
int len1,len2;
ll tmp,ans,a[N],b[N],c[N],n;
int main(){cinn;cinlen1;for(int ilen1;i1;i--)cina[i];cinlen2;for(int ilen2;i1;i--)cinb[i];for(int ilen1;i1;i--){c[i]max(max(a[i]1,b[i]1),2*1ll);a[i]a[i]-b[i];}tmp1;for(int i1;ilen1;i){ans(tmp*a[i]ans)%mod;tmp(tmp*c[i])%mod;}coutans;return 0;
}
/*错解
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N1e510,mod1000000007;
int len1,len2;
ll tmp,ans,a[N],b[N],c[N],n;
int main(){cinn;cinlen1;for(int i1;ilen1;i)cina[i];cinlen2;for(int i1;ilen2;i)cinb[i];for(int i1;ilen1;i){c[i]max(max(a[i]1,b[i]1),2*1ll);a[i]a[i]-b[i];//这个bug我找了两个小时不能从高位开始减}tmp1;for(int ilen1;i1;i--){ans(tmp*a[i]ans)%mod;tmp(tmp*c[i])%mod;}
coutans;return 0;
}*/ 数组切分 一道动态规划题
我们设置f[i]表示从1到i区间的切法。那么可以从任意区间[j,i]转移只要这个区间[j,i]也是满足题意的就行。那么如果判断[j,i]是否满足题意呢
首先要注意到题上给出的是连续的的1~n的某个排列然后我们只需要判断区间的极值和区间长度是否一样就行如果相等就说明此区间一定是连续的自然数。
#include bits/stdc.h
using namespace std;
long long f[10010],mod 1000000007;
int a[10010],n;
int main(){cinn;for(int i1;in;i)cina[i];f[0]1;for(int i1;in;i){int maa[i],mia[i];for(int ji;j1;j--){mamax(ma,a[j]);mimin(mi,a[j]);if(i-jma-mi){f[i](f[i]f[j-1])%mod;}}}coutf[n];return 0;
} gcd 这道题本以为很麻烦但是做着做着就发现了个不可思议的规律。
观察5和7它们的最大gcd一定是2为什么呢因为你5k和7k始终保持差2所以它们不可能有比2更大的gcd因为它们两个一定是不等的 对于一组a和b假设b大于a不妨另cb-a。最终的ak和bk一定是差c而且c必是它们的公因数。所以如果bk是m*c的话那么此时ak必然也是c的倍数因为它们两个差c啊所以只需要枚举到b的下一个c的倍数即可也就是(b/c1)*c 验证5和9它们差值为4我们枚举到8和12时候发现gcd已经是4了那么k就确定了
验证2和9它们差值为7我们一直枚举到7和14时发现gcd为7那么此时k也确定了
#include bits/stdc.h
using namespace std;
typedef long long ll;
ll a,b,s,c;
int main(){cinab;cabs(a-b);if(ab)swap(a,b);sb/c;cout(s1)*c-b;return 0;
} 青蛙过河 二分做法
我们对跳跃距离二分然后去判断这个距离能不能跑2x次即可既然我们都已经确定了区间长度了。
那么不妨我们把这整个长度分成等长的mid区间只需要保证所有的mid长度区间和都是大于2x的就行。
证明我只会反证法
假设存在一组mid长度的区间和小于2x那么经过x次来回必然要经过此区间2x次所以不成立。故原假设成立。
#include bits/stdc.h
using namespace std;
const int N1e510;
typedef long long ll;
int s[N];
ll n,x;
bool check(int m){for(int i1;imn;i){if(s[im-1]-s[i-1]2*x) return false;}return true;
}
int main(){cinnx;int a;for(int i1;in;i)cina,s[i]s[i-1]a;int l1,rn;while(lr){int mid(lr)1;if(check(mid)) rmid-1;else lmid1;}coutl;return 0;
}
