组建网站需多少钱,湖南室内设计公司排名,简单旅游网站模板下载,开网站挣不挣钱题意#xff1a;
给你n个小于101810^{18}1018的大数#xff0c;问在可以再不改变序列位置#xff0c;之改变数值中某数位的‘9’变为‘6’或将‘6’变为‘9’#xff0c;求的最终序列由小到大#xff0c;且字典序最小。
题目#xff1a;
链接#xff1a;https://ac.n…题意
给你n个小于101810^{18}1018的大数问在可以再不改变序列位置之改变数值中某数位的‘9’变为‘6’或将‘6’变为‘9’求的最终序列由小到大且字典序最小。
题目
链接https://ac.nowcoder.com/acm/contest/16741/H 来源牛客网 Woe is you – for your algorithms class you have to write a sorting algorithm, but you missed the relevant lecture! The subject was in-place sorting algorithms, which you deduce must be algorithms that leave each input number in its place and yet somehow also sort the sequence.
Of course you cannot change any of the numbers either, then the result would just be a difffferent sequence. But then it hits you: if you flflip a 6 upside-down, it becomes a 9, and vice versa! Certainly no one can complain about this since you changed none of the digits! The deadline to hand in the exercise is in fifive hours. Try to implement this sorting algorithm before then!
输入描述:
The input consists of: • A line with an integer n (2 ≤ n ≤ 10 000), the number of integers in the input sequence. • n lines, the ith of which contains a positive integer xi (1 ≤ xi ≤ 1018), the ith number of the sequence.
输出描述:
If the sequence cannot be sorted non-decreasingly by flipping some number 6 or 9 in input 1, output “not possible”. Otherwise, output “possible” followed by the sorted sequence - each number on its own line. If there is more than one valid solution, please output the smallest sequence.
示例1
输入
4 9 7 7 9
输出
possible 6 7 7 9
示例2
输入
4 97 96 66 160
输出
possible 67 69 69 160
示例3
输入
3 80 97 79
输出
impossible
示例4
输入
2 197 166
输出
possible 167 169
分析
是一道比较容易的题但比赛时考虑太多wa了十几遍。。。下来看题解有点想吐血 废话不多说了下面看分析
贪心构造使每个串在大于等于前一个串的前提下尽可能小。注意字符串之间的大小比较与数字之间大小比较的不同以字符串形式输入数字。 依次遍历n个串分情况构造 当前串长度 前一个串长度。那直接把当前串的所有9变成6就可以了变完之后当前串肯定还是大于前一个串。当前串长度 前一个串长度。就算把当前串的所有6变成9也无力回天了直接impossible结束。当前串长度 前一个串长度。先还是把当前串的所有6变成9如果还是比前一个串小直接impossible结束否则从高位到低位依次尝试把9变回6这个时候要注意如果变了之后比前一个串小了那就说明不能变一定要还原回去
AC代码
#includestdio.h
#includestring.h
#includemath.h
#includealgorithm
#includeiostream
using namespace std;
typedef long long ll;
const int M1e410;
string a[M];
int n;
bool solve(string f,int ii){if(f.size()a[ii-1].size()){for(int j0;jf.size();j)if(f[j]9)f[j]6;a[ii]f;}else{if(f.size()a[ii-1].size())return 0;for(int i0;if.size();i)if(f[i]6)f[i]9;if(fa[ii-1])return 0;for(int i0;if.size();i){if(f[i]9){f[i]6;if(fa[ii-1])f[i]9;}}a[ii]f;}return 1;
}
int main(){cinn;int vis0;a[0]0;for(int i1;in;i){cina[i];if(vis1)continue;if(!solve(a[i],i))vis1;}if(vis1) coutimpossibleendl;else{coutpossibleendl;for(int i1;in;i)couta[i]endl;}return 0;
}
想了想还是抛上我比赛时地错误代码 分析
因为我没有分长度判断所以开了一个函数计算长度为101810^{18}1018的数值也是够够的比赛时的确注意到直接比较字符串的字典序由于长度的问题会有问题但是随即的解决方案搞了这么个吃力不讨好的。暴力莽想着对于所有6和9的出现位置可以先全部更为6然后进制枚举一下可能性将6变为9那么有2182^{18}218种排列数据量218∗1042^{18}*10^4218∗104妥妥的超时…
#includestdio.h
#includestring.h
#includemath.h
#includealgorithm
#includemap
#includeiostream
using namespace std;
typedef long long ll;
const int M1e410;
string a[M];
int b[M];
int n,tot;
ll dfs(string f){ll ans0;int pf.size();for(int i0;ip;i){ansans*10f[i]-0;}return ans;
}
bool solve(string f,int ii){int ans1tot;for(int i0;ians;i){string wf;int ki;int kk0;while(k0){if(k%21){w[b[tot-1-kk]]9;}k/2;kk;}if(dfs(w)dfs(a[ii-1])){a[ii]w;return true;}}return false;
}
int main(){//while(1){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;int vis0;a[0]0;for(int i1;in;i){cina[i];tot0;if(vis1)continue;string sa[i];int ls.size();for(int j0;jl;j){if(s[j]6)b[tot]j;if(s[j]9){b[tot]j;s[j]6;}}if(!solve(s,i))vis1;}if(vis1) coutimpossibleendl;else{coutpossibleendl;for(int i1;in;i)couta[i]endl;}//}return 0;
}
