week15实验 D_瑞瑞爱上字符串/F_东东：“来不及解释了，快上车！！”

D_瑞瑞爱上字符串##

题目

瑞瑞最近迷上了字符串，因此决定出一个字符串的题。
给定两个正整数 N、K，考虑所有由 N - 2 个 a 和 2 个 b 组成的字符串，要求输出其中字典序第 K 小的。
例如当 N = 5 时，共有如下 10 种组成方式：

aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa

输入输出

Input

多组数据，第一行给定 T，表示数据组数。（1 ≤ T ≤ 1e4）
对于每组数据，给出两个正整数 N、K。（3 ≤ N ≤ 1e5, 1 ≤ K ≤ min(2e9, N * (N-1) / 2 )）
N 的总和不会超过 1e5。

Output

对于每组数据，输出长度为 N 的字典序第 K 小的字符串。

Sample Input

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Sample Output

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

思路分析

这道题的思路是确定k的大小与两个b位置的关系。找规律发现：假设第一个b后面的字母个数为x个，则满足x(x-1)/2>=k，那么x=(1+sqrt(1+8k))/2上取整；而第二个b后面的字母个数为k-x(x-1)/2个。然后按照b的位置逆序输出字符串。

总结反思

找规律的题目如果数据规模小，可以暴力求解；如果规模大，考虑优化算法降低复杂度或者根据规律列方程求解。

AC代码

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

long long t,n,k,cnt1,cnt2;
int main()
{
 cin>>t;
 while(t--){
  cin>>n>>k;
  cnt1=cnt2=0;
  cnt1=ceil((-1+sqrt(1+8*k))/2);
  cnt2=k-cnt1*(cnt1-1)/2;
  cnt1++;
  for(long long i=n;i>=1;i--) 
  {
   if(i==cnt1||i==cnt2)
    cout<<'b';
   else cout<<'a';
  }
  cout<<endl;
 }
 return 0;
}  

F_东东：“来不及解释了，快上车！！”

题目

东东要上学了！
东东要去他家路口的公交车站等车！！！
东东从家出发，需要 d 分钟到达公交站台。
已知有 n 班公交车，第 i 路公交车在 a_i 分钟到达公交站台，随后每 b_i 分钟会有该路公交车。
东东想着他要迟到了！！！可恶！！！要迟到了！！于是他看见了一辆公交车来了，立马跳上了这辆"他见到的"第一辆公交车。
东东上车后发现了一个问题！！这不是去幼儿园的车！！！！可惜车门已经焊死。
那么问题来了东东上的是第几路车？

输入输出

Input

第一行输入路线数n和东东到达的时间d(1≤n≤100,1≤d≤1e5)
接下来n行，每行两个数字a_i和b_i（1≤a_i,b_i≤1e5），分别为该路公交首辆车到达的时间和两辆车之间的发车间隔
第一行输入路线数n和东东到达的时间d(1≤n≤100,1≤d≤1e5)
接下来n行，每行两个数字a_i和b_i（1≤a_i,b_i≤1e5），分别为该路公交首辆车到达的时间和两辆车之间的发车间隔

Output

东东所上车的公交车的路线编号。
如果有多种可能，输出一种

Sample Input1

2 2
6 4
9 5

Sample Output1

1

Sample Input2

5 5
3 3
2 5
5 6
4 9
6 1

Sample Output2

3

思路分析

开两个数组a[]、b[]分别存储第i班汽车的到达时间和发车间隔。利用一个while循环，在到达时间上不断累加间隔时间，直到满足到达时间>=d，然后，求最小到达时间，并记录车辆编号。

AC代码

#include<iostream>
#include<string>
using namespace std;

int d,n,a[105],b[105],ans;
int main()
{
 cin>>n>>d;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i]>>b[i];
 }
 int mintime=1e9;
 for(int i=1;i<=n;i++)
 {
  while(a[i]<d) a[i]+=b[i];
  if(a[i]<mintime)
  {
   ans=i;
   mintime=a[i];
  }
 } 
 cout<<ans<<endl; 
 return 0;
}