[CF1202D] Print a 1337-string... - 构造

Description

给你一个数 $ n $，求出一个有 $ n $ 个子序列为 $ 1337 $ 的序列，序列长度不能大于 $ 10^5 $。

Solution

考虑 1 + n个3 + m个7

则方案数为 \(\frac {mn(n-1)} 2\) 种，不一定能用

于是考虑 133 + k7 + (n-2)3 + m7

则方案数为 \(\frac {mn(n-1)} 2 +k\) 种

不妨取 \(n=300\)，然后暴力尝试 \(m\) 并计算 \(k\)，最后选择一个可行的即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;

int a,n=300,m,k;

signed solve() {
    cin>>a;
    for(int i=0;i<=50000;i++) {
        m=i;
        k=a-m*n*(n-1)/2;
        if(k>=0 && n-2+3+k+m<=1e5) {
            cout<<133;
            while(k--) cout<<7;
            while(n-2) --n,cout<<3;
            while(m--) cout<<7;
            cout<<endl;
            return 0;
        }
    }
}

signed main() {
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--) {
        n=300;
        solve();
    }
}

[CF1202D] Print a 1337-string... - 构造

原文：https://www.cnblogs.com/mollnn/p/12968538.html