特判思路:  
1.如果有两个及以上的数位都出现了奇数次,则无法构造回文串
2.如果0出现2次以上,而且其他只有一个数位出现过且只出现了一次,则无法规避前导0,所以也无法构造(样例4)
3.下面开始构造:所有的数位次数累加,得到最终的字符串长度n,如果有数位出现次数为奇数,那么必然要放一个它在最中间
4.因为不能有前导0,所以如果有多个0的话,从1找到9,找到最小的数,首尾各贴一个
5.然后从小的数位到大的数位,首尾同时铺过去就完事了。
PS: 另需特判0出现多次而没有其他数字的情况,此时无法构造,对应12行。
#include <iostream>#include <string>#include <algorithm>using namespace std;int a[10];void solve() { int cna = 0, cnb = 0, p = -1; for(int i = 0; i < 10; i++) {  cin >> a[i];  if(a[i] % 2 == 1) cna++, p = i;  else if(a[i]) cnb++; }   // 特判  if(a[0] == 1 && cna == 1 && cnb == 0) {  cout << 0 << endl;  return; } if(cna > 1 || (a[0] && a[0] % 2 == 0 && cna <= 1 && cnb <= 1 && a[p] == 1) || (a[0] && a[0] % 2 && cna == 1 && !cnb)) { // 这里容易漏判   cout << -1 << endl;  return; }  string ans = ""; if(!a[0]) { // 没 0    if(cna) a[p]--;  for(int i = 1; i < 10; i++) {   if(!a[i]) continue;   int r = a[i];   r >>= 1;   while(r--) {    ans += (char)(i + '0');   }  }  string t = ans;  reverse(t.begin(), t.end());  if(cna) ans += (char)(p + '0');  ans += t; } else {  // 有 0   if(cna) a[p]--;  int q = 0;  for(int i = 1; i < 10; i++) {   if(!a[i]) continue;   ans += (char)(i + '0');   a[i]--;   q = i;   break;     }  int r = a[0] / 2;  while(r--) {   ans += '0';  }  for(int i = q; i < 10; i++) {   if(!a[i]) continue;   int r = a[i];   r >>= 1;   while(r--) {    ans += (char)(i + '0');   }  }  string t = ans;  reverse(t.begin(), t.end());  if(cna) ans += (char)(p + '0');  ans += t; }  cout << ans << endl;}int main() { solve();  return 0;}// hack : 0 4 6 9 4 2 6 4 8 2// hackii : 4 5 0 0 0 0 0 0 0 0把 输出 0 的情况放后面一并处理。#include <iostream>#include <string>#include <algorithm>using namespace std;int a[10];void solve() { int cna = 0, cnb = 0, p = -1; for(int i = 0; i < 10; i++) {  cin >> a[i];  if(a[i] % 2 == 1) cna++, p = i;  else if(a[i]) cnb++; }   // 特判 - 第三部分后面的 a[0] 改成了 a[0] > 1 if(cna > 1 || (a[0] && a[0] % 2 == 0 && cna <= 1 && cnb <= 1 && a[p] == 1) || (a[0] > 1 && a[0] % 2 && cna == 1 && !cnb)) { // 这里容易漏判   cout << -1 << endl;  return; }  string ans = ""; if(!a[0]) { // 没 0    if(cna) a[p]--;  for(int i = 1; i < 10; i++) {   if(!a[i]) continue;   int r = a[i];   r >>= 1;   while(r--) {    ans += (char)(i + '0');   }  }  string t = ans;  reverse(t.begin(), t.end());  if(cna) ans += (char)(p + '0');  ans += t; } else {  // 有 0   if(cna) a[p]--;  int q = 0;  for(int i = 1; i < 10; i++) {   if(!a[i]) continue;   ans += (char)(i + '0');   a[i]--;   q = i;   break;     }  int r = a[0] / 2;  while(r--) {   ans += '0';  }  for(int i = q; i < 10; i++) {   if(!a[i]) continue;   int r = a[i];   r >>= 1;   while(r--) {    ans += (char)(i + '0');   }  }  string t = ans;  reverse(t.begin(), t.end());  if(cna) ans += (char)(p + '0');  ans += t; }  cout << ans << endl;}int main() { solve();  return 0;}// hack : 0 4 6 9 4 2 6 4 8 2// hackii : 4 5 0 0 0 0 0 0 0 0
点赞 1
评论 1
全部评论

相关推荐

03-26 15:18
已编辑
华北水利水电大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务