题目链接
题面：
题意： 给你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; }