题解归档 - cf1202D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202D
• 本地来源：problems/cf1202D/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/D
• 原始标题：CF1202D — Print a 1337-string...

思路

CF1202D — Print a 1337-string...

题意

构造仅含 1,3,7 的串，使其子序列 1337 恰好出现 n 次（(1\le n\le 10^9)，长度 (\le 10^5)）。

做法

形如 133…337（中间共 x 个 3）时，子序列 1337 数为 (C(x,2)=x(x-1)/2)。

1. 取最大 len 使 len*(len+1)/2 ≤ n（等价于使 (C(len,2)\le n) 的最大 len）。
2. rem = n - len*(len-1)/2。
3. 输出 133 + rem 个 7 + len-2 个 3 + 7。

rem ≤ 45000，len ≤ 45000，总长约 (9\times 10^4)。

验证

对拍时统计 1337 子序列：遇 3 应先 c+=b 再 b+=a，顺序错误会高估。

样例

• n=6 → 133337（(C(4,2)=6)）
• n=1 → 1337

代码

来源：problems/cf1202D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:11:19
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string ans;
ll t,n,i,j,k,cur;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        k=2;
        while(k*(k-1)/2<=n) k++;
        k--;
        cur=n-k*(k-1)/2;
        ans="133";
        for(i=0;i<cur;i++) ans.push_back('7');
        for(i=0;i<k-2;i++) ans.push_back('3');
        ans.push_back('7');
        cout<<ans<<"\n";
    }
    return 0;
}