1 条题解

  • 0
    @ 2025-11-19 0:03:29

    题解

    如果一共比了 nn 局,那么双方得到的总分就是 1+2++n=n(n+1)/21+2+\dots+n = n(n+1)/2。因此只有当 a+ba+b 正好是某个三角形数时,才存在合法的 nn。枚举 nn(或直接解一元二次方程)即可判断是否可行。

    一旦 nn 确定下来,把局数从大到小依次尝试分给 ljcc:若当前局数 ii 还不超过剩余的 aa,就把它分给 ljcc 并把 aa 减去 ii。因为每个局数只出现一次,且总和不超过 aa,这个贪心总能成功地凑出和为 aa 的子集。输出 nn 以及被选择的局数就是一组合法方案。

    
    #include<bits/stdc++.h>
    using namespace std;
    int f[100010];
    long long a,b;
    int main(){
    	
    	scanf("%lld%lld",&a,&b);
    	int fl=0;
    	int i;
    	for(i=1;i<=100000;i++){
    		if(a+b==(1ll*i*(i+1)/2)) {
    			fl=1;
    			break;
    		}
    	}	
    	if (!fl){
    		printf("No\n");
    		return 0;	
    	}
    	int n=i,p=0;
    	while(a){
    		if (a>=i){
    			f[++p]=i;
    			a=a-i;
    		}
    		i--;
    	}
    	printf("%d ",n);
    	for (int i=1;i<p;i++) printf("%d ",f[i]);
    	printf("%d\n",f[p]);
    }
    
    • 1

    信息

    ID
    5469
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    5
    已通过
    1
    上传者