题目
原题连接
Codeforces Round #742 (Div. 2) Problem - C. Carrying Conundrum
题目大意
题目大概意思为给你一个数\(n\),这个\(n\)是按照Alice的那种加法方法算\(a + b\)算出来的。
求\((a,b)\)有几种。
Alice的加法方法为,加法进位时候,进到下下一位。具体操作看图片咯。
题解
思路
Alice的加法,其实可以看做,奇数位加奇数位的,偶数位加偶数位的。
假设\(n=12345\),把它奇偶数位拆分开得到\(a=135, b=24\)。\(a\)可以拆分成\(135 = 45 + 90\),\(b\)可以拆分成\(24 = 9 + 15\)。然后再将\(45,9\),\(90,15\)组合起来,就能得到一组数\((495, 1950)\)。
运用Alice的加法,\(495 + 1950 = 12345\)。 这就是其中一个解。
总共有多少种解?这取决于\(a,b\)可以拆分成多少种。
一个正数\(x\)可以拆分成\(x+1\)种:\(0+x, 1+(x-1), 2+(x-2), ..., x+0\)。
所以总共的解应该为\((a+1)*(b+1)\)。题目中要求拆分出来的数字,必须为正数,也就是\(n=12345\)时,\((0, 12345)\)与\((12345, 0)\)是不符合的。所以要减去\(2\)。
最终结果为\((a+1)*(b+1)-2\)。
代码
then show the code.
#include <iostream>
#include <string>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
string s, s1, s2;
cin >> s;
for(int i=0; i<s.size(); i++){
if(i&1) s2 += s[i];
else s1 += s[i];
}
if(s2.empty()) cout << stoi(s1) - 1 << endl;
else cout << (stoi(s1)+1) * (stoi(s2)+1) - 2 << endl;
}
return 0;
}
Codeforces Round #742 (Div. 2) Problem - C. Carrying Conundrum 题解