[数据结构与算法]2019 ICPC Asia Taipei-Hsinchu Regional E.The League of Sequence Designers

题目链接：Dashboard - 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest - Codeforces?

思路：构造成0,0,0....0,0,-y,x这样的数列。这样做可以找出最短的数列。

此时，WA = x, AC = (x-y)*len，其中WA和AC分别是错误答案，正确答案，len是数组长度。

那么就有AC = WA+k，那么就有：，看右边那个，枚举所有满足x+k整除len的x，寻找对应的y（还要注意在范围内），代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)

int k,L,x,y;
inline void solve(){
    cin>>k>>L; L=max(2LL,L); //长度不可能<2，不然无法构造出结果
    bool ok = 0; int ax,ay,ai;
    FOR(i,L,1999){ //枚举所有可能长度
        x = i-k%i; //x的最小值（注意x是>0的）
        while(x <= 1e6){
            y = x-(x+k)/i;
            if(0<y && y<=1e6){
                ok=1; ax=x, ay=y, ai=i; break;
            }
            x+=i;
        }
        if(ok) break;
    }
    if(ok){
        cout<<ai<<'\n';
        FOR(i,1,ai-2) cout<<0<<' ';
        cout<<-ay<<' '<<ax<<'\n';
    }
    else cout<<-1<<'\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;  cin>> T; while(T--) solve();
}

另一种解法：

参考自：The League of Sequence Designers(构造)_Harris-H的博客-CSDN博客??

代码如下： （这个短很多）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define debug cout<<"!!!"<<endl;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)

inline void solve(){
    int k,L; cin>>k>>L;
    if(L>=2000) {cout<<-1<<'\n'; return;}
    cout<<1999<<'\n'<<-1<<' ';
    int ave = (k+1999)/1998, rest = (k+1999)%1998;
    FOR(i,1,1997) cout<<ave<<' ';
    cout<<rest+ave<<'\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;  cin>>T; while(T--) solve();
}