这道题求字典序最大,也就是说,每次还原字符都找字典序最大的字符例如123有三种情况ABC,LC,AW,它们三个字典序最大的就是LC,类似贪心。主要问题每次怎么选到字典序最大的字符。
【答案】
#include<iostream> #include<string> using namespace std; int main() { string s; cin >> s; int length = s.size(); for(int i=0;i<length;i++){ if((i+1)<length&&((s[i]-'0')*10+(s[i+1]-'0'))<=26){ cout << (char)('A'+((s[i]-'0')*10+(s[i+1]-'0'))-1); i++; } else{ cout << (char)('A'+(s[i]-'0')-1); } } return 0; } J:整数小拼接(25分)【问题描述】
给定义个长度为 n 的数组 A1, A2, · · · , An。你可以从中选出两个数 Ai 和 Aj (i 不等于 j),然后将 Ai 和 Aj 一前一后拼成一个新的整数。例如 12 和 345 可
以拼成 12345 或 34512 。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法,即便
是 Ai = Aj 时。
请你计算有多少种拼法满足拼出的整数小于等于 K。
【输入格式】
第一行包含 2 个整数 n 和 K。
第二行包含 n 个整数 A1, A2, · · · , An。
【输出格式】
一个整数代表答案。
【样例输入】
4 33 1 2 3 4【样例输出】
8【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ N ≤ 1000, 1 ≤ K ≤ 108, 1 ≤ Ai ≤ 104。
对于所有评测用例,1 ≤ N ≤ 100000,1 ≤ K ≤ 1010,1 ≤ Ai ≤ 109。
【解题思路】
典型的排列问题,直接上八皇后的模板,事实上所有的排列问题,都能用它解决,只需要在排列好两个数的时候,进行拼接,比较大小,计数即可,唯一害怕的就是时间过不了。
【答案】
#include<iostream> using namespace std; int n,k,sum=0; int a[5]; int b[100005]; bool isok(int r){ for(int i=0;i<r;i++){ if(a[i]==a[r]){ return false; } } return true; } void dfs(int r){ if(r==2){ int w=1; while(b[a[1]]/w){ w *= 10; } int cache = b[a[0]]*w+b[a[1]]; if(cache<k){ sum++; } return ; } for(int i=0;i<4;i++){ a[r]=i; if(isok(r)){ dfs(r+1); } } } int main() { cin >> n >> k; for(int i=0;i<n;i++){ cin >> b[i]; } dfs(0); cout << sum; return 0; } 参考链接第十一届蓝桥杯省赛第一场原题