比賽連接：Codeforces Round 1043 (Div.3)

A. Homework

題目鏈接：A - Homework
Vlad and Dima have been assigned a task in school for their English class. They were given two strings $a$ and $b$ and asked to append all characters from $b$ to string $a$ in any order. The guys decided to divide the work between themselves and, after lengthy negotiations, determined who would add each character from string $b$ to $a$.

Due to his peculiarities, Vlad can only add characters to the beginning of the word, while Dima can only add them to the end. They add characters in the order they appear in string $b$. Your task is to determine what string Vlad and Dima will end up with.
Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $n$ ($1\le n\le 10$) — the length of the string $a$.

The second line contains the string $a$, consisting of lowercase letters of the English alphabet.

The third line contains an integer $m$ ($1\le m\le 10$) — the length of the strings $b$ and $c$.

The fourth line contains the string $b$, consisting of lowercase letters of the English alphabet.

The fifth line contains the string $c$, consisting of the characters ‘V’ and ‘D’ — the distribution of the characters of string $b$ between Dima and Vlad. If $c_i$ = ‘V’, then the $i$-th letter is added by Vlad; otherwise, it is added by Dima.
Output

For each test case, output the string that will result from Dima and Vlad’s work.
這是一道很簡單的模擬題，按照題意進行模擬即可。

// Problem: A. Homework
// Contest: Codeforces - Codeforces Round 1043 (Div. 3)
// URL: https://codeforces.com/contest/2132/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;string s;cin>>s;int m;cin>>m;string t;cin>>t;string op;cin>>op;string ans = s;for(int i=0;i<op.size();i++){if(op[i] == 'D'){ans += t[i];}else{string tt;tt += t[i];ans = tt + ans;}}cout<<ans<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

B. The Secret Number

題目鏈接：B. The Secret Number
Vadim has thought of a number $x$. To ensure that no one can guess it, he appended a positive number of zeros to the right of it, thus obtaining a new number $y$. However, as a precaution, Vadim decided to spread the number $n=x+y$. Find all suitable $x$ that Vadim could have thought of for the given $n$.
Input

Each test consists of several test cases. The first line contains a single integer $t$ $(1\le t\le 10^4)$ — the number of test cases. The following lines describe the test cases.

In a single line of each test case, there is an integer $n$ — the number spread by Vadim $(11\le n\le 10^{18})$.
Output

For each number $n$, output $0$ if there are no suitable $x$. Otherwise, output the number of suitable $x$, followed by all suitable $x$ in ascending order.

已知 n = x + y，其中 y 是 x 右邊添加若干個 0 得到的數。假設 x 是 k 位數，在 x 右邊添加 m 個 0 后，y = x * 10^m 。那么 n = x + x * 10^m = x * (1 + 10^m) ，所以 x = n / (1 + 10^m)，需要滿足 x 是整數，并且 y = x * 10^m 是 x 右邊添加 m 個 0 得到的（即 x 和 y 的數字組成符合要求 ）。

所以我們只需要暴力地求出來所有的可能的數即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;vector<int> ans;int k = 10;for(int i=1;i<=18;i++){int x = 1LL + k;if(x > n) break;if(n % x == 0){int y = n / x;string t = to_string(y);string tt = t + string(i,'0');if(to_string(y * k) == tt) ans.push_back(y);}if(k * 10 > n) break;k *= 10;}if(ans.size() == 0){cout<<0<<endl;return ;}sort(ans.begin(),ans.end());cout<<ans.size()<<endl;for(auto &i : ans) cout<<i<<' ';cout<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
}

C1. The Cunning Seller (easy version)

題目鏈接：C1. The Cunning Seller (easy version)
這道題依舊是暴力，從大到小一直遍歷就行了（感覺比B題還水）

// Problem: C1. The Cunning Seller (easy version)
// Contest: Codeforces - Codeforces Round 1043 (Div. 3)
// URL: https://codeforces.com/contest/2132/problem/C1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;void solve()
{int n;cin>>n;int ans = 0;for(int i=18;i>=0;i--){int k = pow(3LL,i+1LL) + i * pow(3LL,i-1);int num = pow(3,i);if(num > n) continue;int cnt = n / num;n -= cnt * num;ans += k * cnt;}// cout<<"n = "<<n<<endl;cout<<ans<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

C2. The Cunning Seller (hard version)

題目鏈接：C2. The Cunning Seller (hard version)
首先還是用C1的思路求出最少需要的交易次數，然后看能不能用交易次數來換交易金幣數（貪心的思想），通過列式子就能發現貪心的思路：詳解見代碼：

// Problem: C2. The Cunning Seller (hard version)
// Contest: Codeforces - Codeforces Round 1043 (Div. 3)
// URL: https://codeforces.com/contest/2132/problem/C2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define lbt(x) ((x) & (-x)) const int INF = 0x3f3f3f3f;
const int inf = 1e18; 
const int N = 20;
int n,k;void solve()
{cin>>n>>k;int ans = 0;vector<int> cs(N,0);for(int i=19;i>=0;i--){int num = pow(3,i);if(num > n) continue;int cnt = n / num;n -= cnt * num;ans += cnt;cs[i] = cnt;//用cs數組存當前的i所需要的交易次數}if(ans > k)//如果最少的操作次數都達不到的話就是-1啦{cout<<"-1"<<endl;return ;}k -= ans;//計算還能“浪費多少次數來使得花費更小”for(int i=19;i>=1;i--){if(k < 2) break;//因為是三進制 所以我們可以用一次高位交易抵三次的低位交易 所以每一次的貪心操作都能“浪費2次交易”int x = k / 2;int y = cs[i];//k小于2了就貪心不了了，所以就要退出int mi = min(x,y);cs[i] -= mi;cs[i-1] += 3 * mi;//每一次貪心就相當于是低位上多了三次交易k -= 2 * mi;//浪費了2 * mi次交易}/*想一下為什么這樣就貪心了？首先對于x來說：我們所需要花費的金幣數是：3^(x+1) + x*3^(x-1)對于更高位來說：我們所需要的金幣數是：3^(x+2) + (x+1)*(3^x)我們知道對于三進制來說，一次高位操作等于3個低位操作（高位 = 低位 * 3）那么我們計算3次低位所需要花費的金幣數：3 * (3^(x+1) + x*3^(x-1))即：3^(x+2) + x * 3^x我們與之和高位所需要花費的金幣數來進行比較，是不是少了3^x？這就是貪心的過程：浪費交易次數使得高位的交易盡量少 盡量轉移到低位上去*/int res = 0;for(int i=0;i<=19;i++){int t = pow(3, i+1) + i * pow(3, i-1);res += t * cs[i];}cout<<res<<endl;
//	cout<<fixed<<setprecision(x)<< ; 
}signed main()// Don't forget pre_handle!
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
}