51 nod 1624 取余最长路

假设我们在第一行x处从第一行到第二行,在第二行的y处从第二行到第三行。

sum[1][x]+sum[2][y]-sum[2][x-1]+sum[3][n]-sum[3][y-1];

将相同的移动到一边

sum[1][x]-sum[2][x-1]+sum[3][n]-sum[3][y-1]+sum[2][y]

对于a+b<p取最大
我们可以将a<p-b;
在枚举每一个端点y的时候,查找最优的x，因为x<=y,所以我们可以用二分在枚举每一个y的时候将当时的p-x插入。如果能找到就取找到的，不能找到就取容器中最小的。
为什么要用p-b呢，因为在查找的时候如果在大于a的情况下，p-b越小则说明b越大，a+b的值是越大的。
为什么找不到的时候我们要去容器中最大的呢?因为这说明在这种情况下2p>a+b>p，所以我们把b尽可能大，则值会越大。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long ll;
typedef double dl;

const int N = 1e5+7;
const int M = 1e9+7;
const int INF = 0x7fffffff;

int a[4][N]; 
multiset<int> mst;
int pre1[N];
int pre2[N];
int pre3[N];
void solve()
{
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);    
        }
    }
    for(int i=1;i<=n;i++)
    {
        pre3[i]=pre3[i-1]+a[3][i];
        pre3[i]%=p;
        pre2[i]=pre2[i-1]+a[2][i];
        pre2[i]%=p;
        pre1[i]=pre1[i-1]+a[1][i];
        pre1[i]%=p;
    }
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        int b=(pre1[i]+pre3[n]-pre2[i-1]+p)%p;
        mst.insert(p-b);
        int a=(pre2[i]-pre3[i-1]+p)%p;
        auto it=mst.upper_bound(a);
        if(it!=mst.end())
        {
            maxn=max(maxn,(a-*it+p)%p); 
        }
        else 
        {
            it=mst.begin();
            maxn=max(maxn,(a-*it+p)%p);
        }
    }
    printf("%d",maxn%p);

}

int main()
{
    solve();
}

补充：这个题数据应该不严谨，因为我在容器中求最大和最小的时候都A了。。