广州三合一网站建设,重庆招聘网官网,简易logo在线设计,电子商务专业是干什么的A题意#xff08;取余最长路#xff09;: 佳佳有一个n*m的带权矩阵#xff0c;她想从(1,1)出发走到(n,m)且只能往右往下移动#xff0c;她能得到的娱乐值为所经过的位置的权的总和。 有一天#xff0c;她被下了恶毒的诅咒#xff0c;这个诅咒的作用是将她的娱乐值变为对p…A题意取余最长路: 佳佳有一个n*m的带权矩阵她想从(1,1)出发走到(n,m)且只能往右往下移动她能得到的娱乐值为所经过的位置的权的总和。 有一天她被下了恶毒的诅咒这个诅咒的作用是将她的娱乐值变为对p取模后的值这让佳佳十分的不开心因为她无法找到一条能使她得到最大娱乐值的路径了 她发现这个问题实在是太困难了既然这样那就只在3*n的矩阵内进行游戏吧 现在的问题是在一个3*n的带权矩阵中从(1,1)走到(3,n)只能往右往下移动问在模p意义下的移动过程中的权总和最大是多少。 n(1n100000),p(1p1000000000)。 最简单的思路就是 搞一搞前缀和 枚举两个转折点 那么复杂度是n^2。BOOM! 设三段的前缀和和 分别为s1,s2,s3 设转折点分别为(2,x1) (2,x2) 再仔细想一想p-1肯定是我们能得到的最大值那么我们可以优化到枚举一个转折点第二个转折点前两段的结果丢在set里; 二分就OK了。 但是为了不影响二分的结果做了一点改动set不能丢入1,1-2,x1-2,x2。应丢入1,1-2,x1-2,n 的和 前缀和表示为 s2[n]s1[x1]-s2[x1-1]; 二分的值变为((p-1)-(s3[n]-s3[x2-1])((s2[n]-s2[x2]))p)%p,每次更新答案就OK了 再观察一下发现插入和查询的时候都加了s2[n] 所以我们把s2[n]去掉。 然后s3[]用的一直是x2-n的和 这里应该用个后缀和的 写的时候手残读入错误导致以为思路不对 --- 浪费了很多时间 被自己气笑 PS:啊现在的我们是多么幸福现成的STL啦啦啦 #include iostream
#include cstdio
#include algorithm
#include cmath
#include vector
#include cstring
#include set
using namespace std;
const int maxn 1e510;
typedef long long ll;
inline void r(llnum){num0;ll f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
inline void r(int num){num0;int f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
ll s1[maxn],s2[maxn],s3[maxn];
int main()
{int n;ll p;r(n),r(p);for(int i1;in;i){r(s1[i]);s1[i](s1[i]s1[i-1])%p;}for(int i1;in;i){r(s2[i]);s2[i](s2[i]s2[i-1])%p;}for(int i1;in;i){r(s3[i]);s3[i](s3[i]s3[i-1])%p;}setlls;ll ans -1;setll::iterator it;ll sum;ll cnt;for(int i1;in;i){s.insert(((s1[i]-s2[i-1])%pp)%p);sum (s3[n]-s3[i-1]s2[i])%p;cnt ((p-sum)%pp)%p;it s.lower_bound(cnt);if(it!s.begin()) it--;ans max(ans,((((*it)sum)p)%p));}coutansendl;return 0;
} 有漏洞 这里有一个小技巧 我们如果想找出小于等于X的最大值 我们只需lower_boundX1 得到大于等于X1的区间[it,end 那么 [begin,it) 就是小于等于X的区间 if it begin 不存我们要的值 else *(--it)就是我们要的值辣 #include iostream
#include cstdio
#include algorithm
#include cmath
#include vector
#include cstring
#include set
using namespace std;
const int maxn 1e510;
typedef long long ll;
inline void r(llnum){num0;ll f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
inline void r(int num){num0;int f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
ll s1[maxn],s2[maxn],s3[maxn];
int main()
{int n;ll p;r(n),r(p);for(int i1;in;i){r(s1[i]);s1[i](s1[i]s1[i-1])%p;}for(int i1;in;i){r(s2[i]);s2[i](s2[i]s2[i-1])%p;}for(int i1;in;i){r(s3[i]);s3[i](s3[i]s3[i-1])%p;}setlls;ll ans -1;setll::iterator it;ll sum;ll cnt;for(int i1;in;i){s.insert(((s1[i]-s2[i-1])%pp)%p);sum (s3[n]-s3[i-1]s2[i])%p;cnt ((p-sum)%pp)%p;it s.lower_bound(cnt);if(it!s.begin()) it--;else it --s.end();ans max(ans,((((*it)sum)p)%p));}coutansendl;return 0;
} AC代码 C题意比大小: 有两个数列A和B 已知A_0,a,b,N A_nA_(n-1)*ab (n1) B数列满足 B_n2*B_(n/2) 1 (n为偶数) B_n2*B_((n-1)/2) (n1)/2 (n为奇数)现在问B数列的第A_N项和第(A_N)1项的关系T组数据 A_0,a,b,N1e15 T100 N 1e15 没规律铁定做不了 B_0 -1; 然后把B序列暴力出来前40项 发现规律 除了0-3 不符合规律外 后面连续的四个都符合规律 这时候就需要考虑A序列了 如果发现A_N小于4 那就需要特判 (题意说的也不是太清如果 A_03 , a 0b 0, N 1e15 这个数据肯定T 然后暴力N项 发现还有规律 N3 特判 N4 走N次 和 N%44结论一样 #include iostream
#include cstdio
#include algorithm
#include cmath
#include vector
#include cstring
#include set
using namespace std;
typedef long long ll;
inline void r(llnum){num0;ll f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
inline void r(int num){num0;int f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)numnum*10ch-0,chgetchar();num*f;
}
ll a,b,N;
ll A0,AN,A;
bool flag false;
ll B[40];
void check()
{if(flag){A4;}if(B[A]B[A1]){puts();}else{if(B[A]B[A1]){puts();}else{puts();}}
}
int main()
{int T;r(T);B[0] -1;//cout-1endl;for(int i1;i40;i){B[i] B[i/2]*21;if(i1){B[i]i/2;}//coutB[i]endl;}while(T--){flag false;r(A0),r(a),r(b),r(N);A A0;for(ll i1;iN;i){if(A4){flag true;break;}A A*ab;//A%4;}A A0%4;N N 3 ? N % 4 4 : N;for(int i1;iN;i){A A*ab;A%4;} check();}return 0;
} AC代码 转载于:https://www.cnblogs.com/Geek-xiyang/p/5785437.html
