Codeforces Round #708 (Div. 2) C1 C2

古城微笑少年丶 2024-03-29 14:25 87阅读 0赞

[Problem - C1 - Codeforces][]

题意：

让你构造三个数，使它们加起来是n，然后lcm(a1,a2,a3)<=n/2

思路：

构造题，要满足两个条件

首先是lcm，lcm的构造典中典，就是希望一个数是另外两个数的倍数

因为是构造题，所以考虑特殊情况，取最大值为n/2，那么剩下两个数加起来要是n/2

注意到n的奇偶性不确定，n不一定能被2整除，因此讨论奇偶性

如果n是奇数，那就使最大那个数为(n-1)/2，然后再构造两个因子，考虑特殊情况，取一个是1，那么另一个就是(n-1)/2，刚好满足条件

如果是n是偶数，那么最大的因子为n/2，然后去考虑两个因子

如果构造成n/2，n/4，n/4，那么就能满足，但是前提是n能被4整除

因此再去讨论n是不是4的倍数

如果是，就构造成n/2，n/4，n/4

**如果不是，注意到不是4的倍数的偶数有个特点：(n-2)/2一定是偶数**

因为n是偶数，所以n=4k+2，带进去就知道一定是偶数了

所以就构造2，(n-2)/2，(n-2)/2，其中(n-2)/2一定是偶数，这样就满足lcm的条件了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    int n,k;
    void solve(){
        cin>>n>>k;
        if(n%2==0){
            if(n%4==0){
                cout<<n/2<<" "<<n/4<<" "<<n/4<<'\n';
            }else{
                cout<<2<<" "<<(n-2)/2<<" "<<(n-2)/2<<'\n';
            }
        }else{
            cout<<1<<" "<<(n-1)/2<<" "<<(n-1)/2<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

然后看C2，就是把三个数改成了k个数

构造考虑线性极端情况，前k-3个数都是1，后面三个数就按前面C1构造就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    int n,k,ansk;
    void get(int n){
        if(n%2==0){
            if(n%4==0){
                cout<<n/2<<" "<<n/4<<" "<<n/4<<'\n';
            }else{
                cout<<2<<" "<<(n-2)/2<<" "<<(n-2)/2<<'\n';
            }
        }else{
            cout<<1<<" "<<(n-1)/2<<" "<<(n-1)/2<<'\n';
        }
    }
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=k-3;i++) cout<<1<<" ";
        get(n-(k-3));
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

**总结：**

**不是4的倍数的偶数有个特点：(n-2)/2一定是偶数**

**构造的线性极端情况：要不是平均分布，要不就把重点都集中在后几项，前面都为1或0**

[Problem - C1 - Codeforces]: https://codeforces.com/contest/1497/problem/C1