算法馬拉松13 A-E解題報告

A題意（取余最長路）:

　　佳佳有一個n*m的帶權矩陣，她想從(1,1)出發走到(n,m)且只能往右往下移動，她能得到的娛樂值為所經過的位置的權的總和。

有一天，她被下了惡毒的詛咒，這個詛咒的作用是將她的娛樂值變為對p取模后的值，這讓佳佳十分的不開心，因為她無法找到一條能使她得到最大娛樂值的路徑了！

她發現這個問題實在是太困難了，既然這樣，那就只在3*n的矩陣內進行游戲吧！

現在的問題是，在一個3*n的帶權矩陣中，從(1,1)走到(3,n)，只能往右往下移動，問在模p意義下的移動過程中的權總和最大是多少。

n(1<=n<=100000),p(1<=p<=1000000000)。

　　最簡單的思路就是 搞一搞前綴和 枚舉兩個轉折點 那么復雜度是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 = 1e5+10;
typedef long long ll;
inline void r(ll&num){num=0;ll f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
inline void r(int &num){num=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
ll s1[maxn],s2[maxn],s3[maxn];
int main()
{int n;ll p;r(n),r(p);for(int i=1;i<=n;i++){r(s1[i]);s1[i]=(s1[i]+s1[i-1])%p;}for(int i=1;i<=n;i++){r(s2[i]);s2[i]=(s2[i]+s2[i-1])%p;}for(int i=1;i<=n;i++){r(s3[i]);s3[i]=(s3[i]+s3[i-1])%p;}set<ll>s;ll ans = -1;set<ll>::iterator it;ll sum;ll cnt;for(int i=1;i<=n;i++){s.insert(((s1[i]-s2[i-1])%p+p)%p);sum = (s3[n]-s3[i-1]+s2[i])%p;cnt = ((p-sum)%p+p)%p;it = s.lower_bound(cnt);if(it!=s.begin()) it--;ans = max(ans,((((*it)+sum)+p)%p));}cout<<ans<<endl;return 0;
}

?這里有一個小技巧? 我們如果想找出小于等于X的最大值 我們只需lower_boundX+1? 得到大于等于X+1的區間[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 = 1e5+10;
typedef long long ll;
inline void r(ll&num){num=0;ll f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
inline void r(int &num){num=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
ll s1[maxn],s2[maxn],s3[maxn];
int main()
{int n;ll p;r(n),r(p);for(int i=1;i<=n;i++){r(s1[i]);s1[i]=(s1[i]+s1[i-1])%p;}for(int i=1;i<=n;i++){r(s2[i]);s2[i]=(s2[i]+s2[i-1])%p;}for(int i=1;i<=n;i++){r(s3[i]);s3[i]=(s3[i]+s3[i-1])%p;}set<ll>s;ll ans = -1;set<ll>::iterator it;ll sum;ll cnt;for(int i=1;i<=n;i++){s.insert(((s1[i]-s2[i-1])%p+p)%p);sum = (s3[n]-s3[i-1]+s2[i])%p;cnt = ((p-sum)%p+p)%p;it = s.lower_bound(cnt);if(it!=s.begin()) it--;else    it = --s.end();ans = max(ans,((((*it)+sum)+p)%p));}cout<<ans<<endl;return 0;
}

?C題意（比大小）:

　　　有兩個數列A和B 已知A_0,a,b,N A_n=A_(n-1)*a+b (n>=1) B數列滿足 B_n=2*B_(n/2) + 1 (n為偶數) B_n=2*B_((n-1)/2) + (n+1)/2 (n為奇數)
現在問B數列的第A_N項和第(A_N)+1項的關系
T組數據 A_0,a,b,N<=1e15

T<=100

N 1e15? 沒規律鐵定做不了

B_0 = -1;

然后把B序列暴力出來前40項? 發現規律 除了0-3 不符合規律外 后面連續的四個都符合規律

這時候就需要考慮A序列了 如果發現A_N小于4 那就需要特判 (題意說的也不是太清如果?A_0<=3 , ?a = 0，b = 0, N = 1e15 這個數據肯定T

然后暴力N項 發現還有規律

N<=3?特判

N>=4 ?走N次 和 N%4+4結論一樣

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
inline void r(ll&num){num=0;ll f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
inline void r(int &num){num=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
ll a,b,N;
ll A0,AN,A;
bool flag = false;
ll B[40];
void check()
{if(flag){A+=4;}if(B[A]==B[A+1]){puts("=");}else{if(B[A]<B[A+1]){puts("<");}else{puts(">");}}
}
int main()
{int T;r(T);B[0] = -1;//cout<<"-1"<<endl;for(int i=1;i<40;i++){B[i] = B[i/2]*2+1;if(i&1){B[i]+=i/2;}//cout<<B[i]<<endl;
    }while(T--){flag = false;r(A0),r(a),r(b),r(N);A = A0;for(ll i=1;i<=N;i++){if(A>4){flag = true;break;}A = A*a+b;//A%=4;
        }A = A0%4;N = N > 3 ? N % 4 + 4 : N;for(int i=1;i<=N;i++){A = A*a+b;A%=4;}    check();}return 0;
}

?