1 条题解
-
2
考虑最优化答案,然后用摩尔投票的方法直接做。这样是 的,但是假完了。
显然不能这样贪。我们考虑 dp。 表示考虑了前 个帮派,剩下 头牛是否可行。
dp 之后找 的最小值,反推回去再按题意模拟。是 的,也假完了。
对于一个帮派,可以把其中所有牛存到队列里,留着和后面的帮派对峙。
我们可以枚举第 个帮派有多少牛和之前的牛对峙,有多少牛进队。这样可以 求出前两问的答案。但是字典序假完了。
以上是本人在赛时想到的全部假算。以下为正解:
考虑最后顺序的构造。显然是一些 1 先和一些 对峙,然后剩下的互相抵消,最后剩下若干个 1。
由上文的 dp,我们可以 检验一些帮派互相抵消的可行性。
所以我们枚举第一部分的数量以及 ,并用 dp 验证。这部分时间复杂度 。
把第一部分的牛删掉,考虑第二部分。
首先这一部分牛显然有偶数个。对于这个问题有一个结论,当所有 的最大值 时无解,当最大值 时有唯一的匹配方式。
所以我们每次尝试最靠前的帮派编号相邻的牛,若匹配之后满足 则匹配。当 时采用唯一构造。
然后就做完了。复杂度 。
#include<bits/stdc++.h> using namespace std; #define int long long #define lb(x) x&(-x) #define ls(p) (p<<1) #define rs(p) ((p<<1)|1) #define pii pair<int,int> #define F first #define S second #define mkp make_pair #define psb push_back #define vi vector<int> const int mod=998244353; const int N=110,inf=1e15; int n,m,a[N]; int dp[N][N]; int chk(){ for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++) dp[i][j]=0; }dp[1][0]=1; for(int i=1;i<m;i++){ int v=a[i+1]; for(int j=0;j<=n;j++){ if(dp[i][j]==0) continue; for(int k=0;k<=min(j,v);k++) dp[i+1][j-k+v-k]=1; } } return dp[m][0]; } int hsum[N],hmax[N]; vector<int>vec[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); // system("fc ex.out my.out");return 0; // freopen("ex.in","r",stdin); // freopen("my.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]; } int nlen=n+1,ni=0; for(int len=0;len<a[1]&&nlen==n+1;len++){ for(int i=2;i<=m;i++){ if(len>a[i]) continue; a[i]-=len; if(chk()){ ni=i,nlen=len; break; }a[i]+=len; } } if(nlen==n+1){ cout<<"NO\n";return 0; } cout<<"YES\n"<<a[1]-nlen<<"\n";a[1]-=nlen; for(int i=1;i<=nlen;i++) cout<<"1\n"; while(nlen--) cout<<ni<<"\n"; for(int i=m;i>=2;i--){ hsum[i]=hsum[i+1]+a[i]; hmax[i]=max(hmax[i+1],a[i]); } int sti=0,stk=0; for(int i=2;i<m;i++){ if(a[i]){ for(int j=min(a[i],a[i+1]);j>=1;j--){ int nsum=hsum[i+1]+a[i]-2*j,nmx=max(hmax[i+2],max(a[i],a[i+1])-j); if(nmx<=nsum/2){ for(int k=1;k<=j;k++) vec[i].psb(i+1); a[i]-=j;a[i+1]-=j; break; } } if(a[i]){ stk=a[i];sti=i; } }else{ for(int j=min(stk,a[i+1]);j>=1;j--){ int nsum=hsum[i+1]+stk-2*j,nmx=max(hmax[i+2],max(stk,a[i+1])-j); if(nmx<=nsum/2){ for(int k=1;k<=j;k++) vec[sti].psb(i+1); stk-=j;a[sti]-=j;a[i+1]-=j; break; } } } int nsum=hsum[i+2]+a[i]+a[i+1]+stk,nmx=max(hmax[i+2],max(max(a[i],stk),a[i+1])); if(nsum==0) break; if(nmx==nsum/2){ int maxi=0,maxx=0; for(int j=m;j>=2;j--){ if(a[j]>maxx){ maxx=a[j];maxi=j; } } for(int j=2;j<=m;j++){ if(j==maxi||a[j]==0) continue; a[maxi]-=a[j]; for(int k=1;k<=a[j];k++) vec[min(j,maxi)].psb(max(j,maxi)); }break; } } for(int i=2;i<=m;i++){ for(int x:vec[i]){ // cerr<<i<<"->"<<x<<"???\n"; cout<<i<<"\n"; }for(int x:vec[i]) cout<<x<<"\n"; } while(a[1]--) cout<<"1\n"; return 0; } /* 9 6 1 1 1 1 1 4 */
信息
- ID
- 953
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 32
- 已通过
- 7
- 上传者