昆明快速建站模板世界疫情最新数据

题意

给一个n，一个序列b[]，

bi=ai+a(n+i-1)，

求不降序的a序列[]

思路来源

组里各神犇&&自己

题解

Solution1:

显然a1=0，an=b1的时候，区间长度最长

区间里面内置区间的时候如果内区间能左对齐，显然内区间最长，

即，如果能[0,8]，显然不要[1,7]

而若不能左对齐的话，就一定要右对齐

即，如果能[3,10]，显然不要[6,7]，右对齐更长，

那么由于保证外区间都是最长的，

如果存在解，贪心最长区间一定是最优的

Solution2:

0<=a1<=a2<=…<=an/2<=bn/2-an/2<=…<=b1-a1

令a0=0，跑一遍差分约束的最长路，求最小值即可

注意从a0出发，spfa(0)，初始化赋负INF

代码

Solution1:(贪心O(n))

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n;
ll a[maxn],b[maxn/2];
int main()
{scanf("%d",&n);for(int i=1;i<=n/2;++i)scanf("%I64d",&b[i]);a[1]=0,a[n]=b[1];for(int i=2;i<=n/2;++i){int r=n-i+1;a[i]=a[i-1];a[r]=b[i]-a[i];if(a[r]>a[r+1]){a[r]=a[r+1];a[i]=b[i]-a[r];}}for(int i=1;i<=n;++i){printf("%I64d%c",a[i],i==n?'\n':' ');}return 0;
}

Solution2:(差分约束O(nlogn))

By Yzm007, contest: Educational Codeforces Round 56 (Rated for Div. 2), problem: (C) Mishka and the Last Exam, Accepted, ##include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=2e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%I64d",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int n,head[maxn],cnt;
ll b[maxn/2],a[maxn],dis[maxn],q[10*maxn];
bool vis[maxn];
struct edge
{int to,nex;ll w;
}e[maxn];
void init()
{cnt=0;mem(head,-1);
}
void spfa(int s)
{for(int i=0;i<maxn;++i)dis[i]=-8e18;mem(vis,0);int start=0,end=1;q[0]=s;dis[s]=0;while(start<end){int u=q[start++];vis[u]=0;for(int i=head[u];~i;i=e[i].nex){int v=e[i].to;ll w=e[i].w;if(dis[v]<dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){q[end++]=v;vis[v]=1;}}}}
}
void add(int u,int v,ll w)
{e[cnt].to=v;e[cnt].w=w;e[cnt].nex=head[u];head[u]=cnt++;
}
int main()
{ init();sci(n);rep(i,1,n/2)scll(b[i]);rep(i,2,n/2){add(i-1,i,b[i]-b[i-1]);//ai-ai-1>=kadd(i-1,i,0);//ai-ai-1>=0}add(0,1,0);//a1-a0>=0add(n/2,0,-b[n/2]/2);//a[n/2]<=b[n/2]-a[n/2]spfa(0);rep(i,1,n/2){a[i]=dis[i];a[n-i+1]=b[i]-dis[i];}rep(i,1,n){printf("%I64d%c",a[i],i==n?'\n':' ');}return 0;
}