题面：
题意：
给你a1----an，k，要求a [ 1 ] + … + a [ k ] < a [ 2 ]+ … + a [ k+1 ] < a [ 3 ] + … + a [ k+2 ]<…，然后这里的 ai 有可能是 ?，要求你填 ? 的数字，使 a1~an 的绝对值之和最小，不可能输出 Incorrect sequence
题解：由上式要求我们可以得到 a [ 1 ] < a [ k+1 ] < a [ 2k+1 ] < …且 a [ 2 ] < a [ k+2 ] < a [ 2k+2 ] < …且…。
要求绝对值最小，我们每次找连续的一连串?，尽可能让中间的位置为0，这样绝对值最小。
我们先按中间赋值0这样去操作，然后再根据左右边界对整个区间进行修正，全加或全减一个数使得符合要求。
为了操作方便，我们可以在开始加上k个负无穷大的数，在最后加上k个正无穷大的数。
终究是变成了我最讨厌的样子？
也不知道之后还能不能看懂我现在的代码。。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
#define ld long double
#define ui unsigned int
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define forhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define one(n) for(int i=1;i<=(n);i++)
#define rone(n) for(int i=(n);i>=1;i--)
#define fone(i,x,n) for(int i=(x);i<=(n);i++)
#define frone(i,n,x) for(int i=(n);i>=(x);i--)
#define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))
#define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))
#define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define cls(a) memset(a,0,sizeof(a))
#define cls1(a) memset(a,-1,sizeof(a))
#define clsmax(a) memset(a,0x3f,sizeof(a))
#define clsmin(a) memset(a,0x80,sizeof(a))
#define cln(a,num) memset(a,0,sizeof(a[0])*num)
#define cln1(a,num) memset(a,-1,sizeof(a[0])*num)
#define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)
#define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define scf(x) scanf("%lf",&x)
#define scf2(x,y) scanf("%lf%lf",&x,&y)
#define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)
#define scs(x) scanf("%s",x+1)
#define scs0(x) scanf("%s",x)
#define scline(x) scanf("%[^\n]%*c",x+1)
#define scline0(x) scanf("%[^\n]%*c",x)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxm=100100;
const int up=100000;
const int hashp=13331;
const int maxn=300100;
ll a[maxn];
int k,n;
char str[maxn];
bool ha[maxn];
bool check(void)
{
fone(i,1,k)
{
int l=i;
fonk(j,i+k,n,k)
{
if(!ha[j])
{
if((j-l-1)/k>a[j]-a[l]-1) return false;
l=j;
}
}
}
return true;
}
void get(int l,int r)
{
int sum=(r-l-1)/k;
if(sum==0) return ;
int m=(sum+1)/2;
int ans=0;
fronk(i,l+m*k,l+1,k) a[i]=ans--;
ans=0;
fonk(i,l+m*k,r-1,k) a[i]=ans++;
int dis=a[l]-a[l+k];
if(dis>=0)
{
dis++;
fonk(i,l+k,r-1,k) a[i]+=dis;
}
dis=a[r-k]-a[r];
if(dis>=0)
{
dis++;
fonk(i,l+k,r-1,k) a[i]-=dis;
}
}
int main(void)
{
sc2(n,k);
int cnt=0;
one(k) a[++cnt]=-lnf;
one(n)
{
scs(str);
if(str[1]=='?') ha[++cnt]=true;
else sscanf(str+1,"%lld",&a[++cnt]);
}
one(k) a[++cnt]=lnf;
n=cnt;
if(!check())
{
printf("Incorrect sequence\n");
return 0;
}
fone(i,1,k)
{
int l=i;
fonk(j,i,n,k)
{
if(!ha[j])
{
get(l,j);
l=j;
}
}
}
fone(i,k+1,n-k) printf("%lld ",a[i]);
putchar('\n');
return 0;
}
把代码展开之后：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
#define ld long double
#define ui unsigned int
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define forhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define one(n) for(int i=1;i<=(n);i++)
#define rone(n) for(int i=(n);i>=1;i--)
#define fone(i,x,n) for(int i=(x);i<=(n);i++)
#define frone(i,n,x) for(int i=(n);i>=(x);i--)
#define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))
#define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))
#define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
#define cls(a) memset(a,0,sizeof(a))
#define cls1(a) memset(a,-1,sizeof(a))
#define clsmax(a) memset(a,0x3f,sizeof(a))
#define clsmin(a) memset(a,0x80,sizeof(a))
#define cln(a,num) memset(a,0,sizeof(a[0])*num)
#define cln1(a,num) memset(a,-1,sizeof(a[0])*num)
#define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)
#define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define scf(x) scanf("%lf",&x)
#define scf2(x,y) scanf("%lf%lf",&x,&y)
#define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)
#define scs(x) scanf("%s",x+1)
#define scs0(x) scanf("%s",x)
#define scline(x) scanf("%[^\n]%*c",x+1)
#define scline0(x) scanf("%[^\n]%*c",x)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxm=100100;
const int up=100000;
const int hashp=13331;
const int maxn=300100;
ll a[maxn];
int k,n;
char str[maxn];
bool ha[maxn];
bool check(void)
{
for(int i=1;i<=k;i++)
{
int l=i;
for(int j=i+k;j<=n;j+=k)
{
if(!ha[j])
{
if((j-l-1)/k>a[j]-a[l]-1) return false;
l=j;
}
}
}
return true;
}
void get(int l,int r)
{
int sum=(r-l-1)/k;
if(sum==0) return ;
int m=(sum+1)/2;
int ans=0;
for(int i=l+m*k;i>=l+1;i-=k) a[i]=ans--;
ans=0;
for(int i=l+m*k;i<=r-1;i+=k) a[i]=ans++;
int dis=a[l]-a[l+k];
if(dis>=0)
{
dis++;
for(int i=l+k;i<=r-1;i+=k) a[i]+=dis;
}
dis=a[r-k]-a[r];
if(dis>=0)
{
dis++;
for(int i=l+k;i<=r-1;i+=k) a[i]-=dis;
}
}
int main(void)
{
scanf("%d%d",&n,&k);
int cnt=0;
for(int i=1;i<=k;i++) a[++cnt]=-lnf;
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
if(str[1]=='?') ha[++cnt]=true;
else sscanf(str+1,"%lld",&a[++cnt]);
}
for(int i=1;i<=k;i++) a[++cnt]=lnf;
n=cnt;
if(!check())
{
printf("Incorrect sequence\n");
return 0;
}
for(int i=1;i<=k;i++)
{
int l=i;
for(int j=i+k;j<=n;j+=k)
{
if(!ha[j])
{
get(l,j);
l=j;
}
}
}
for(int i=k+1;i<=n-k;i++) printf("%lld ",a[i]);
putchar('\n');
return 0;
}
京公网安备 11010502036488号