首页 > 代码库 > BUCT蓝桥杯热身赛I题解
BUCT蓝桥杯热身赛I题解
A 题 十六进制转换(hex)
看起来是一个水题，可是事实上确实是个水题。如果你按照题目的意思来，先把16进制转化成10进制，再把10进制转换成8进制，不好写。
所以从2进制的思想看16进制的数每一个数都是由4位二进制组成，然而8进制数是有3位二进制组成，所以我们大可把16进制先转成2进制，在从 二进制转成8进制，注意前导0.
注意姿势，由于姿势的问题，超时了3次，真冤。代码见下方
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 string const_ch[16] = {"0000","0001","0010","0011","0100","0101", 8 "0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"}; 9 10 string const_cc[8] = {"000","001","010","011","100","101","110","111"};11 12 int Find(string str) {13 for (int i = 0;i < 8;i++) {14 if (str == const_cc[i]) return i;15 }16 }17 18 int main ( ) {19 string str;20 while (cin >> str) {21 if (str == "0") cout << 0 << endl;22 else {23 string ans;24 for (int i = 0,len = str.length();i < len;i ++) {25 ans += const_ch[str[i] >= ‘A‘ && str[i] <= ‘F‘ ? str[i] - ‘A‘ + 10 : str[i] - ‘0‘];26 }27 int len = ans.length();28 if (len % 3 == 1){29 ans = "00" + ans;30 len += 2;31 }32 if (len % 3 == 2) {33 ans = "0" + ans;34 len ++;35 }36 int pos = 0;37 int ANS[300000];38 for (int i = 0;i < len;i += 3) {39 string temp = ans.substr(i,3);40 ANS[pos++] = Find(temp);41 }42 int temp = 0;43 while (ANS[temp] == 0) temp++;44 for (int i = temp;i < pos;i++) cout << ANS[i];45 cout << endl;46 }47 }48 }
B题 聊斋(storys)
没什么好说的,直接暴力。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int n; 8 string str; 9 int mark[410];10 11 int extend1(int i,char ch,int dir) {12 int pos = i;13 int ans = 0;14 while (!mark[pos] && (str[pos] == ch || str[pos] == ‘w‘)) {15 ans ++;16 mark[pos] = 1;17 if (ans >= n) return n;18 pos = (pos + n + dir) % n;19 }20 return ans;21 }22 23 int extend(int i,char ch,int dir) {24 if (ch == ‘w‘) {25 return max(extend1(i,‘r‘,dir),extend1(i,‘b‘,dir));26 }27 else return extend1(i,ch,dir);28 }29 30 int main () {31 // freopen("1.in","r",stdin);32 while (cin >> n) {33 getchar();34 cin >> str;35 int maxn = -1;36 for (int i = 0;i < n;i++) {37 if (str[i] == ‘w‘) {38 memset(mark,0,sizeof(mark));39 maxn = max(maxn,extend(i,‘r‘,-1) + extend((i + 1) % n,str[(i + 1) % n],1));40 memset(mark,0,sizeof(mark));41 maxn = max(maxn,extend(i,‘b‘,-1) + extend((i + 1) % n,str[(i + 1) % n],1));42 memset(mark,0,sizeof(mark));43 maxn = max(maxn,extend(i,‘r‘,1) + extend((i - 1 + n) % n,str[(i - 1 + n) % n],-1));44 memset(mark,0,sizeof(mark));45 maxn = max(maxn,extend(i,‘b‘,1) + extend((i - 1 + n) % n,str[(i - 1 + n) % n],-1));46 }47 else {48 memset(mark,0,sizeof(mark));49 maxn = max(maxn,extend(i,str[i],-1) + extend((i + 1) % n,str[(i + 1) % n],1));50 memset(mark,0,sizeof(mark));51 maxn = max(maxn,extend(i,str[i],1) + extend((i - 1 + n) % n,str[(i - 1 + n) % n],-1));52 }53 }54 cout << maxn << endl;55 }56 return 0;57 }
C题 奶牛的编号（privc）
刚看到这个题的时候，还以为是找逆序数，因为题目并没规定只能交换相邻的，所以就不是求逆序数了。后来想了想，因为题目之后1,2,3三个等级，所以我们可以
将所有的划分成3块，第一块放1，第二块放2，etc. 但是怎么交换才能保证交换次数最少呢，很简单，找到第一块中的其他数与相应的块里面的数做交换，比如在一块
中出现了2，那么我就找第二块中的1与之做交换。但是当交换完之后，会存在 这么一种情况不能被交换 2 3 1，所以最后要遍历一下看看有多少个这样的情况存在，
每种ans+=2；代码如下。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 int main () { 9 int a[1001];10 int n;11 int b[4] = {0};12 // freopen("1.in","r",stdin);13 cin >> n;14 for (int i = 0;i < n;i++) {15 cin >> a[i];16 b[a[i]]++;17 }18 b[2] = b[1] + b[2];19 b[3] = n;20 int ans = 0;21 for (int i = 1;i < 3;i++) { 22 for (int j = b[i - 1];j < b[i];j++) {23 if (a[j] == i) continue;24 else {25 for (int k = b[a[j] - 1];k < b[a[j]];k++) {26 if (a[k] == i) {27 ans ++;28 swap(a[j],a[k]);29 break;30 }31 }32 }33 }34 }35 for (int i = 0;i < b[1];i++) {36 if (a[i] == 1) continue;37 else {38 ans += 2;39 }40 }41 cout << ans << endl;42 }
下面是罗的代码
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define MAXN 1010 6 using namespace std; 7 int a[MAXN],c[MAXN],cnt; 8 int main(){ 9 int n;10 while(~scanf("%d",&n)){11 for(int i=0;i<n;i++){12 scanf("%d",&a[i]);13 c[i]=a[i];14 }15 sort(c,c+n);16 int ans=0;17 for(int i=0;i<n;i++){18 if(a[i]==c[i]) continue;19 ans++;20 int tmp=-1;21 for(int j=i+1;j<n;j++){22 if(a[j]==c[i]){23 if(a[i]==c[j]){24 swap(a[j],a[i]);25 break;26 }27 else tmp=j;28 }29 }30 if(~tmp) swap(a[i],a[tmp]);31 }32 printf("%d\n",ans);33 }34 }35
D题 贝贝与国王
水题一道，求2的（n - 1）次幂 （下面是陈的代码，不想吐槽了。。。。）
1 #include<iostream> 2 using namespace std; 3 string ss[101]={"1","2","4","8","16","32","64","128","256","512","1024","2048","4096","8192","16384","32768","65536","131072","262144","524288","1048576","2097152","4194304","8388608","16777216","33554432","67108864","134217728","268435456","536870912","1073741824","2147483648","4294967296","8589934592","17179869184","34359738368","68719476736","137438953472","274877906944","549755813888","1099511627776","2199023255552","4398046511104","8796093022208","17592186044416","35184372088832","70368744177664","140737488355328","281474976710656","562949953421312","1125899906842624","2251799813685248","4503599627370496","9007199254740992","18014398509481984","36028797018963968","72057594037927936","144115188075855872","288230376151711744","576460752303423488","1152921504606846976","2305843009213693952","4611686018427387904","9223372036854775808","18446744073709551616","36893488147419103232","73786976294838206464","147573952589676412928","295147905179352825856","590295810358705651712","1180591620717411303424","2361183241434822606848","4722366482869645213696","9444732965739290427392","18889465931478580854784","37778931862957161709568","75557863725914323419136","151115727451828646838272","302231454903657293676544","604462909807314587353088","1208925819614629174706176","2417851639229258349412352","4835703278458516698824704","9671406556917033397649408","19342813113834066795298816","38685626227668133590597632","77371252455336267181195264","154742504910672534362390528","309485009821345068724781056","618970019642690137449562112","1237940039285380274899124224","2475880078570760549798248448","4951760157141521099596496896","9903520314283042199192993792","19807040628566084398385987584","39614081257132168796771975168","79228162514264337593543950336","158456325028528675187087900672","316912650057057350374175801344","633825300114114700748351602688","1267650600228229401496703205376"}; 4 int main() 5 { 6 int n; 7 while(cin>>n) 8 { 9 cout<<ss[n-1]<<endl;10 }11 }
下面是张益宁的代码，可以学习以下，不过让他水过了，却是在意料之外哈
1 #include<stdio.h> 2 #include<math.h> 3 int main() 4 { 5 int n; 6 while(~scanf("%d",&n)) 7 { 8 printf("%.lf",(double)pow(2,n-1)); 9 } 10 }
E题 未出现的子串(unapeared)
水题一道，题目让求没有出现的子串，那么我就将输入的字符串从头到尾分成几个集合，每个集合都包含[1..q]（如果没有，也没办法）
所以出现一个这样的集合ans++；（为什么呢？如果这是一个不完整的集合，即没有出现所有的字母，那么就可以找没出现的字母，但是如果都出现了，我只能将长度
增加），代码如下。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int main ( ) { 8 int n,q; 9 // freopen("1.in","r",stdin);10 while (cin >> n >> q) {11 int ans = 1;12 int a;13 int temp = 0;14 q = (1 << q) - 1;15 for (int i = 0;i < n;i++) {16 cin >> a;17 a --;18 temp |= (1 << a);19 if (temp == q) {20 ans ++;21 temp = 0;22 }23 }24 cout << ans << endl;25 }26 }
这个题也可以DP来搞，DP[k]表示以k开头的最小非子串长度，那么可以从末尾向头找，（其实思想还是一样的）下面是罗的代码
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int dp[10],A[100100]; 6 int main(){ 7 int n,q; 8 while(~scanf("%d%d",&n,&q)){ 9 memset(dp,0,sizeof(dp));10 for(int i=0;i<n;i++)11 scanf("%d",A+i);12 for(int i=n-1;i>=0;i--){13 int tmp=99999999;14 for(int j=1;j<=q;j++){15 tmp=min(tmp,dp[j]);16 }17 dp[A[i]]=tmp+1;18 }19 int ans=99999999;20 for(int i=1;i<=q;i++)21 ans=min(ans,dp[i]);22 printf("%d\n",ans+1);23 }24 }
F题 棋子移动(chess)
特别恶心的模拟题，没意思，水题一道
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int n; 8 9 void work(string str1,int cur) {10 cout << "OOO*O**__*" + str1 << endl;11 cout << "O__*O**OO*" + str1 << endl;12 cout << "O*O*O*__O*" + str1 << endl;13 cout << "__O*O*O*O*" + str1 << endl;14 cout << "step=" << cur + 4 << endl;15 }16 17 void dfs(string str,int n,int temp,int num,int cur) {18 cout << str << endl;19 if (n == 3) {20 string str1;21 for (int i = 0;i < num - 1;i++) {22 str1 += "O*";23 }24 work(str1,cur);25 return;26 }else 27 if (temp == 0) {28 string str1;29 string str2;30 for (int i = 0;i < n;i++) {31 str1 += ‘O‘;32 str2 += ‘*‘;33 }34 string str3;35 for (int i = 0;i < num;i++) {36 str3 += "O*";37 }38 dfs(str1 + str2 + "__" + str3,n,!temp,num,cur + 1);39 }else if (temp == 1) {40 string str1;41 string str2;42 string str3;43 for (int i = 0;i < n - 1;i++) {44 str1 += ‘O‘;45 str2 += ‘*‘;46 }47 num++;48 for (int i = 0;i < num;i++) {49 str3 += "O*";50 }51 dfs(str1 + "__" + str2 + str3,n - 1,!temp,num,cur + 1);52 }53 }54 55 int main () {56 while (cin >> n) {57 string str1;58 string str2;59 for (int i = 0;i < n - 1;i++) {60 str1 += ‘O‘;61 str2 += ‘*‘;62 }63 dfs(str1 + "__" + str2 + "O*",n - 1,0,1,1);64 }65 }
G题 字母游戏(letters)
水题一道，直接暴力，注意‘26’剪枝。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int dir[4][2] = {-1,0,0,1,1,0,0,-1}; 8 string str[30]; 9 int ans[26];10 int n,m;11 int maxn;12 void dfs(int x,int y,int cur) {13 if (cur > maxn) {14 maxn = cur;15 }16 if (maxn == 26) return;17 for (int i = 0;i < 4;i++) {18 int xx = x + dir[i][0];19 int yy = y + dir[i][1];20 if (xx >= 0 && xx < n && yy >= 0 && yy < m && !ans[str[xx][yy] - ‘A‘]) {21 ans[str[xx][yy] - ‘A‘] = 1;22 dfs(xx,yy,cur + 1);23 ans[str[xx][yy] - ‘A‘] = 0;24 }25 }26 }27 28 int main () {29 // freopen("1.in","r",stdin);30 while (cin >> n >> m) {31 for (int i = 0;i < n;i++) {32 cin >> str[i];33 }34 memset(ans,0,sizeof(ans));35 maxn = -1;36 ans[str[0][0] - ‘A‘] = 1; 37 dfs(0,0,1);38 cout << maxn << endl;39 }40 }
BUCT蓝桥杯热身赛I题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。