1 条题解

  • 2
    @ 2026-10-29 12:03:48

    考虑最优化答案,然后用摩尔投票的方法直接做。这样是 O(n)O(n) 的,但是假完了。

    显然不能这样贪。我们考虑 dp。dpi,jdp_{i,j} 表示考虑了前 ii 个帮派,剩下 jj 头牛是否可行。

    dp 之后找 jj 的最小值,反推回去再按题意模拟。是 O(n2)O(n^2) 的,也假完了。

    对于一个帮派,可以把其中所有牛存到队列里,留着和后面的帮派对峙。

    我们可以枚举第 ii 个帮派有多少牛和之前的牛对峙,有多少牛进队。这样可以 O(n2)O(n^2) 求出前两问的答案。但是字典序假完了。

    以上是本人在赛时想到的全部假算。以下为正解:

    考虑最后顺序的构造。显然是一些 1 先和一些 xx 对峙,然后剩下的互相抵消,最后剩下若干个 1。

    由上文的 dp,我们可以 O(n2)O(n^2) 检验一些帮派互相抵消的可行性。

    所以我们枚举第一部分的数量以及 xx,并用 dp 验证。这部分时间复杂度 O(n3)O(n^3)。

    把第一部分的牛删掉,考虑第二部分。

    首先这一部分牛显然有偶数个。对于这个问题有一个结论,当所有 aia_i 的最大值 >∑ai2 > \frac{\sum a_i}{2} 时无解,当最大值 =∑ai2 = \frac{\sum a_i}{2} 时有唯一的匹配方式。

    所以我们每次尝试最靠前的帮派编号相邻的牛,若匹配之后满足 max≤∑ai2max \le \frac{\sum a_i}{2} 则匹配。当 max=∑ai2max = \frac{\sum a_i}{2} 时采用唯一构造。

    然后就做完了。复杂度 O(n3)O(n^3)。

    #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
    */
    
    • 1

    信息

    ID
    953
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    32
    已通过
    7
    上传者