首页 > 其他 > 详细

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

时间:2020-05-26 22:13:44      阅读:39      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!