牛客安徽大学新生赛 G

传送门：：https://ac.nowcoder.com/acm/contest/2720/G

题意：：构造一个字符串 (串长 <=1e9 ) 当且仅包含 n个 “ AHUICPC ” 子序列且字符串长度 <=1e5

思路：：

当你在串（"UICPC"）最前面每添加1个”AH“，总共会构成 ( i +1 ) * i / 2 个子序列，这样就是可以构造最优解，使串尽量最短；

当然为啥是构造长度为2的最优了，同样的道理当构造长度为3 的时候，虽然可以构造出那麽多子序列，但是长度会炸；

举个例子 “AHAHAHAH UICPC” 你会发现子序列下总和 4 + 3 + 2 +1 =10 （等差求和）

因此我们首先要找出最大的 i 满足 ( i + 1 ) * i /2 < n ，然后对于多出的部分 k 我们是不是可以找到一个位置（也就是构造的第 k 个“AH”位置前加上一个“A”）满足用它为起始位置刚好构造出 k 个子序列，显然只花费了一个单位长度

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n;
 8     scanf("%d",&n);
 9     if(n==1){
10         printf("AHUICPC");return 0;
11     }
12     int k;
13     for(int i=1;;i++){
14         if((ll)(i+1)*i/2<(ll)n){
15             k=i;
16         }
17         else{
18             break;
19         }
20     }
21     int t=(n-(k+1)*k/2);
22     for(int i=1;i<=t;i++){
23         if(i==t-k+1){
24             printf("AAH");
25         }
26         else{
27             printf("AH");
28         }
29     }
30     printf("UICPC");
31     return 0;
32 }

不足之处请指出！！！

纵使单枪匹马，也要勇闯天涯

牛客 安徽大学新生赛 G

牛客安徽大学新生赛 G