Codeforces Round #739 (Div. 3) 題解(A-F)
A. Dislike of Threes
題目大意：
輸出第 k k k個既不被 3 3 3整除，尾數也不是 3 3 3的正整數，
解題思路：
因為 1 ≤ k ≤ 1000 1\le k\le 1000 1≤k≤1000，所以直接列舉就行了，
代碼：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
bool check(int x){
if(x%3==0||x%10==3) return false;
return true;
}
int main()
{
int cnt=0;
for(int i=1;cnt<=1000;i++)
if(check(i)) a[++cnt]=i;
int T;
scanf("%d",&T);
while(T--){
int k;
scanf("%d",&k);
printf("%d\n",a[k]);
}
}
B. Who’s Opposite?
題目大意：
n n n個數字按順時針圍成一個圈，每個數的對立面都會有一個相對的數，現在給出 a a a和跟 a a a相對的數 b b b，問 c c c的相對的數字是多少，如果不存在就輸出 ? 1 -1 ?1，
解題思路：
通過觀察題意可以發現，對于一個 n n n個數字圍城的一個圈，相對的兩個數之間的差是 n 2 \dfrac{n}2 2n?，
所以我們可以根據 a a a和 b b b得到 n n n的大小，如果 a a a、 b b b、 c c c大于 n n n就輸出 ? 1 -1 ?1，
因為 c c c和 d d d的差值一定是 n 2 \dfrac{n}2 2n?，所以 d = c ± n 2 d=c\pm\dfrac{n}2 d=c±2n?，
代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int n=abs(a-b)*2;
if(a>n||b>n||c>n) puts("-1");
else{
if(c+n/2<=n) printf("%d\n",c+n/2);
else printf("%d\n",c-n/2);
}
}
return 0;
}
C. Infinity Table
題目大意：
按照題意的規則填數，問第 k k k個數的坐標是多少，
解題思路：
觀察之后可以發現，第 i i i輪填 2 × i ? 1 2\times i-1 2×i?1個數，先從 ( 1 , i ) (1,i) (1,i)開始向下填 i i i個數，再向左填 i ? 1 i-1 i?1個數，
所以可以通過累加和的形式找到第 k k k個數是第幾輪填上去的，再根據剩余的步數判斷坐標，
時間復雜度 O ( k ) O(\sqrt k) O(k ?)
代碼：
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
int T;
cin>>T;
while(T--){
cin>>n;
int sum=0,p;
for(int i=1;;i++){
if(sum+2*i-1>=n){
p=i;
break;
}
sum+=2*i-1;
}
n-=sum;
if(n<=p) printf("%d %d\n",n,p);
else printf("%d %d\n",p,2*p-n);
}
return 0;
}
D. Make a Power of Two
題目大意：
對于給出的整數 n n n,可以采取以下兩種操作：
- 洗掉任何一位上的數字
- 從右邊添加一位數字
執行操作的程序不允許出現前導零，
問從 n n n變成任何一個 2 2 2的整次冪需要的最少操作步數，
解題思路：
因為 1 ≤ n ≤ 1 0 9 1\le n \le10^9 1≤n≤109，所以我們只用考慮 [ 1 , 1 0 18 ] [1,10^{18}] [1,1018]內所有的 2 2 2的整次冪，一共只有 60 60 60個，
所以我們只用計算 n n n轉換成將這所有的 2 2 2的整次冪所需的操作步數，取一個最小值就行了，
假設我們要轉變的 2 2 2的整次冪是 a a a，我們將 n n n和 a a a都當做字串來處理，其中 n n n中能留下的字符數量就是 n n n中子序列與 a a a前綴匹配的最大長度，設這個最大長度為 l e n len len，那么我們所需的操作步驟就是將 n . s i z e ( ) ? l e n n.size()-len n.size()?len個字符洗掉，并從右邊加上 a . s i z e ( ) ? l e n a.size()-len a.size()?len個字符，
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100;
LL a[N];
void init()
{
a[0]=1;
for(int i=1;i<60;i++) a[i]=a[i-1]*2;
}
int check(LL x,LL y){
string s1=to_string(x),s2=to_string(y);
int i=0,j=0;
while(i<s1.size()&&j<s2.size()){
if(s1[i]==s2[j]) i++,j++;
else i++;
}
return s1.size()-j+s2.size()-j;
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--){
int n;
cin>>n;
int res=1e9;
for(int i=0;i<60;i++) res=min(res,check(n,a[i]));
printf("%d\n",res);
}
return 0;
}
E. Polycarp and String Transformation
題目大意：
對于一個字串 s s s，一直執行以下操作直到字串為空，字串 t t t初始是個空字串：
- 將字串 s s s拼接到字串 t t t的后面，即 t = t + s t=t+s t=t+s，
- 選擇一個 s s s中存在的字符 c c c，洗掉字串 s s s中所有的c
現在給出字串 t t t，求原始字串和洗掉字符的順序，如果不存在輸出 ? 1 -1 ?1，
解題思路：
因為字串中的字符種類是越來越少的，所以我們可以直接反著遍歷一遍字串 t t t，字符出現的順序就是洗掉字符順序的逆序，
除此之外，我們還可以發現一個性質，
如果一個字符是第一次洗掉的，這個字符在 t t t中出現的次數 = s =s =s中出現的次數，
如果一個字符是第二次洗掉的，這個字符在 t t t中出現的次數$ = s 中 出 現 的 次 數 中出現的次數 中出現的次數\times 2$，
. . . . . . ...... ......
同理，我們就可以通過字符在 t t t中出現的次數以及洗掉順序就可以得到原字串 s s s的長度并進一步得到原字串 s s s，
這樣我們只需要將現在得到的字串 s s s按照洗掉序列執行題意中的操作，看得到的結果與 t t t是否一致，一致的話就輸出 s s s和 o r d e r order order，否則輸出 ? 1 -1 ?1，
代碼：
#include<bits/stdc++.h>
using namespace std;
string t;
int num[26];
string get(string t){
string res;
for(int i=t.size()-1;i>=0;i--){
if(!num[t[i]-'a']) res.push_back(t[i]);
num[t[i]-'a']++;
}
reverse(res.begin(),res.end());
return res;
}
string check(string s,string order){
string res=s;
for(int i=0;i<order.size();i++){
string temp;
for(int j=0;j<s.size();j++)
if(order[i]!=s[j]) temp+=s[j];
res+=temp;
s=temp;
}
return res;
}
int main()
{
int T;
cin>>T;
while(T--){
cin>>t;
memset(num,0,sizeof num);
string order=get(t);
int len=0;
for(int i=0;i<order.size();i++){
len+=num[order[i]-'a']/(i+1);
}
string s=s.substr(0,len);
if(check(s,order)==t) cout<<s<<" "<<order<<endl;
else cout<<-1<<endl;
}
return 0;
}
F. Nearest Beautiful Number (hard version)
題目大意：
給出兩個整數 n n n和 k k k，輸出不小于 n n n的最小k-beautiful數，
k-beautiful數的含義是最多由 k k k個不同的數字構成的整數，
解題思路：
難易版本的區別在于 k k k的范圍，簡單版本的 1 ≤ k ≤ 2 1\le k\le 2 1≤k≤2，因為 k k k比較小，可以直接通過一層回圈或者兩層回圈列舉所有的情況，這里就不再贅述了，
困難版本 k k k的資料范圍是 1 ≤ k ≤ 10 1\le k \le 10 1≤k≤10，做法的主要思想是貪心，通過讓高位的數盡可能小達到整個數盡可能小的目的，
因為如果當前數不滿足限制的話，我們就要嘗試找一個更大的數，那就意味著必須要有一位比原來大，那么我們就要貪心思考這個問題，每次找到一個盡可能低的位+1，再將后面的數全部置為零，第一次滿足條件的時候就是最優解，
有一個要注意的細節，最優解一定是不用進位的，因為就算當前所有位上都填 9 9 9也會比進一位的情況更優，所以要注意別對 9 9 9進行 + 1 +1 +1，
代碼：
#include<bits/stdc++.h>
using namespace std;
int check(string n){
set<char> se;
for(auto c:n) se.insert(c);
return se.size();
}
int main()
{
int T;
cin>>T;
while(T--){
string n;
int k;
cin>>n>>k;
while(check(n)>k){
set<char> se;
for(int i=0;i<n.size();i++){
se.insert(n[i]);
if(se.size()>k){
while(n[i]=='9') i--;
n[i]++;
for(int j=i+1;j<n.size();j++) n[j]='0';
break;
}
}
}
cout<<n<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295103.html
標籤：其他
上一篇：iOS基于二進制重排啟動優化