Codeforces Round #629 (Div. 3) A、B、C
传送门:点我
A:Divisibility Problem
大意:T组数据 给定a b ,a每次只能加一,问多少次操作后能让a%b==0
思路:如果a比b大,那么答案是(a/b+1)*b-a或者直接输出0(不用操作)
如果a比b小,答案是b-a
代码:
#include<bits/stdc++.h> using namespace std; #define LL long long #define INF 2000000000 #define eps 1e-8 #define pi 3.141592653589793 const LL mod = 1e9+7; using namespace std; int main() { LL a,b; int _; for(scanf("%d",&_);_--;){ scanf("%lld %lld",&a,&b); if(a<b){ printf("%d ",b-a); }else{ if(a%b == 0){ puts("0"); }else{ printf("%lld ",(a/b+1)*b-a); } } } }/* */
B:K-th Beautiful String
For the given integer lexicographical (alphabetical) order.
Recall that the string < in modern programming languages.
For example, if n=5 the strings are (the order does matter):
- aaabb
- aabab
- aabba
- abaab
- ababa
- abbaa
- baaab
- baaba
- babaa
- bbaaa
It is easy to show that such a list of strings will contain exactly n⋅(n−1)2 strings.
You are given k-th string from the list.
The input contains one or more test cases.
The first line contains one integer t test cases follow.
Each test case is written on the the separate line containing two integers 3≤n≤105,1≤k≤min(2⋅109,n⋅(n−1)2).
The sum of values 105.
For each test case print the n. Strings in the list are sorted lexicographically (alphabetically).
7 5 1 5 2 5 8 5 10 3 1 3 2 20 100
aaabb aabab baaba bbaaa abb bab aaaaabaaaaabaaaaaaaa
大意:
需要输出的字符串中有且必有2个b,其余都是a。
T组数据,给定n和k,询问有n个字母构成的字符串第k大的字符串是啥
思路:
观察到abb 是第1个 bab是第2个 baab是第4个 baaab是第7个,再手动计算了一下baaaab是第11个。
由此很容易的看得出来如果一个b在末尾,前一个b移动的规律是数组[1,2,3,4....]的前缀和。
也很好理解,因为每次都要加上后面一个b的活动范围。
那么就很好算得出第一个b的位置了,直接打表二分即可。算出第一个b的位置,第二个b也好算啦。
代码:
#include<bits/stdc++.h> using namespace std; #define LL long long #define INF 2000000000 #define eps 1e-8 #define pi 3.141592653589793 const LL mod = 1e9+7; using namespace std; vector<LL>v; int main() { LL ans = 1; for(int i = 2 ; i <= 100000 ; i ++){ v.push_back(ans); ans = ans+(i-1); } LL a,b; int _; for(scanf("%d",&_);_--;){ scanf("%lld %lld",&a,&b); int pos1 = lower_bound(v.begin(),v.end(),b)-v.begin(),pos2;//pos1是第一个b的位置,二分算得,pos2是第二个b的位置,由输入的k和pos1共同决定 if(b == v[pos1]){ pos2 = 0; pos1 += 1; }else{ pos2 = b-v[pos1-1]; } string s = ""; for(int i = 0 ; i < a ; i ++){ s += 'a'; } s[a-pos2-1] = 'b'; s[a-pos1-1] = 'b'; cout<<s<<endl; } }/* bb 1 bab 2 baab 4 baaab 7 */
C:Ternary XOR
A number is ternary if it contains only digits 2002.
You are given a long ternary number 2.
Let's define the ternary XOR operation 10222⊙11021=21210.
Your task is to find such ternary numbers max(a,b) is the minimum possible.
You have to answer t independent test cases.
The first line of the input contains one integer ∑n≤5⋅104).
For each test case, print the answer — two ternary integers max(a,b) is the minimum possible. If there are several answers, you can print any.
4 5 22222 5 21211 1 2 9 220222021
11111 11111 11000 10211 1 1 110111011 110111010
思路:对0,1,2的情况分类讨论即可。
代码:
#include<bits/stdc++.h> using namespace std; #define LL long long #define INF 2000000000 #define eps 1e-8 #define pi 3.141592653589793 const LL mod = 1e9+7; using namespace std; int main() { string s; int _; for(scanf("%d",&_);_--;){ cin>>s>>s; string s1 = "",s2 = ""; int flag = 0; for(int i = 0 ; i < s.size() ; i ++){ if(s[i] == '2'){ if(flag == 0){ s1 += '1'; s2 += '1'; }else{ s1 += '0'; s2 += '2'; } }else if(s[i] == '1'){ if(flag == 0){ s1 += '1'; s2 += '0'; flag = 1; }else{ s1 += '0'; s2 += '1'; } }else if(s[i] == '0'){ s1 += '0'; s2 += '0'; } } cout<<s1<<endl; cout<<s2<<endl; } }/* 4 5 22222 5 21211 1 2 9 220222021 */