蓝桥杯练习

十六进制转八进制

#include<bits/stdc++.h>
using namespace std;
int deal(char x) {
    if(x>='A') return x-'A'+10;
    else return x-'0';
}
int main() {
    string hex;
    while(cin>>hex) {
        int len=hex.size(),i=0;
        if(len%3==1) printf("%o",deal(hex[0])),i=1;
        else if(len%3==2) printf("%o",deal(hex[0])*16+deal(hex[1])),i=2;
        else printf("%o",deal(hex[0])*16*16+deal(hex[1])*16+deal(hex[2])),i=3;
        for(; i<len; i+=3) 
              printf("%04o",deal(hex[i])*16*16+deal(hex[i+1])*16+deal(hex[i+2]));
        printf("\n");
    }
    return 0;
}

刘晟大佬的思路，数字逻辑，直接映射。

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s;
    while(cin>>s) {
        int n=s.size();
        vector<int>bin;
        for(int i=n-1; i>=0; --i) {
            int x;
            if(s[i]>='0'&&s[i]<='9') x=s[i]-'0';
            else x=s[i]-'A'+10;
            if(!x) bin.push_back(0);
            for(; x; x/=2) bin.push_back(x&1);
            if(bin.size()%4!=0) for(int i=0,tmp=4-bin.size()%4; i<tmp; i++) bin.push_back(0);
        }
        if(bin.size()%3!=0) for(int i=0,tmp=3-bin.size()%3; i<tmp; i++) bin.push_back(0);
        vector<int>oct;
        int nb=bin.size();
        for(int i=0; i<nb; i+=3) oct.push_back(bin[i]+bin[i+1]*2+bin[i+2]*4);
        int no=oct.size();
        if(!oct[no-1])--no;
        for(int i=no-1; i>=0; --i) printf("%d",oct[i]);
        printf("\n");
    }
    return 0;
}

转换成二进制再转换成八进制。上面容器（向量），下面数组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1001000;
const int mod=1e9+7;
int main() {
    string s;
    while(cin>>s) {
        int n=s.size();
        int bin[N];
        int tb=0;
        for(int i=n-1; i>=0; --i) {
            int x;
            if(s[i]>='0'&&s[i]<='9') x=s[i]-'0';
            else x=s[i]-'A'+10;
            if(!x) bin[tb++]=0;
            for(; x; x/=2) bin[tb++]=x&1;
            if(tb%4!=0) for(int i=0,tmp=4-tb%4; i<tmp; i++) bin[tb++]=0;
        }
        if(tb%3!=0) for(int i=0,tmp=3-tb%3; i<tmp; i++) bin[tb++]=0;
        int oct[N];int no=0;
        for(int i=0; i<tb; i+=3) oct[no++]=bin[i]+bin[i+1]*2+bin[i+2]*4;
        if(!oct[no-1])--no;
        for(int i=no-1; i>=0; --i) printf("%d",oct[i]);
        printf("\n");
        s.clear();
    }
    return 0;
}

s=input()
n=int(s,16)
print(oct(n)[2:])

默认是0o123这样的

import java.util.*;
import java.math.*;

public class Main {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    String str = cin.nextLine();
    System.out.print(new BigInteger(str, 16).toString(8));
    cin.close();
  }
}

十六进制转十进制

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll deal(char x) {
    if(x>='A') return x-'A'+10;
    else return x-'0';
}
int main() {
    string hex;
    while(cin>>hex) {
        int len=hex.size();
        ll ans=0;
        for(int i=len-1,p=1;i>=0;i--,p*=16)
            ans+=deal(hex[i])*p;
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll hex;
    while(~scanf("%llx",&hex)) {
        printf("%lld\n",hex);
    }
    return 0;
}

小计算器

http://lx.lanqiao.cn/problem.page?gpid=T459
问题描述

　　模拟程序型计算器，依次输入指令，可能包含的指令有
　　1. 数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
　　2. 运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余
　　3. 进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36)
　　4. 输出指令：'EQUAL'，以当前进制输出结果
　　5. 重置指令：'CLEAR'，清除当前数字

　　指令按照以下规则给出：
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
　　进制转换指令可能出现在任何地方

　　运算过程中中间变量均为非负整数，且小于2^63。
　　以大写的'A'到'Z'表示10到35
输入格式
第1行：1个n，表示指令数量
第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则
坑题。
输出格式
　　依次给出每一次'EQUAL'得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040
思路
题目不难，模拟即可，但是有坑。 if(s.substr(0,5)=="CLEAR") v=0,op='+';操作符这里也要改，看得我怀疑人生了。
另外就是getline要先getchar，然后ll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll toInt(char x) {
    if(x >= '0' && x <= '9') return x - '0';
    else return x - 'A' + 10;
}
char toChar(ll x) {
    if( x>=0 && x<=9) return '0' + x;
    else return 'A' + x - 10;
}
int main() {
    int n;
    cin>>n;
    int mode=10;
    char op='+';
    ll v=0;
    getchar();
    while(n--) {
        string s;
        getline(cin,s);
        if(s.substr(0,5)=="CLEAR")  v=0,op='+';
        else if(s.substr(0,6)=="CHANGE") {
            if(s.size()==8) mode=s[7]-'0';
            else mode=s[8]-'0'+(s[7]-'0')*10;
        } else if(s.substr(0,3)=="ADD") op='+';
        else if(s.substr(0,3)=="SUB") op='-';
        else if(s.substr(0,3)=="MUL") op='*';
        else if(s.substr(0,3)=="DIV") op='/';
        else if(s.substr(0,3)=="MOD") op='%';
        else if(s.substr(0,3)=="NUM") {
            ll x=0;int len=s.size();
            ll j=1;
            for(int i=len-1; i>3; --i,j*=mode)
                x+=toInt(s[i])*j;
            if(op=='+') v+=x;
            else if(op=='-') v-=x;
            else if(op=='*') v*=x;
            else if(op=='/') v/=x;
            else if(op=='%') v%=x;
        } else if(s.substr(0,5)=="EQUAL") {
            if(!v) printf("0");
            else {
                stack<char>st;
                for(ll vs=v; vs; vs/=mode) {
                    ll x=vs%mode;
                    st.push(toChar(x));
                }
                while(!st.empty()) {
                    printf("%c",st.top());
                    st.pop();
                }
            }
            printf("\n");
        }
    }
    return 0;
}

ll Atoi(string s,ll radix) {
    ll ans=0;
    for(ll i=0; i<s.size(); ++i) {
        ll t=s[i];
        if(t>='0'&&t<='9')  ans=ans*radix+t-'0';
        else ans=ans*radix+t-'A'+10;
    }
    return ans;
}
string intToA(ll n,int radix) {
    string ans="";
    do {
        int t=n%radix;
        if(t>=0&&t<=9)    ans+=t+'0';
        else ans+=t-10+'A';
        n/=radix;
    } while(n!=0);
    reverse(ans.begin(),ans.end());
    return ans;
}
//抄蔡佳乐大佬的，他的博客https://blog.nowcoder.net/itachi0713（宇智波鼬还行）

质因数分解

http://lx.lanqiao.cn/problem.page?gpid=T57
问题描述
　　求出区间[a,b]中所有整数的质因数分解。
输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1xa2xa3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出

3=3
4=2x2
5=5
6=2x3
7=7
8=2x2x2
9=3x3
10=2x5

符号我改了一下 不然这个md语法nowcoder will鬼畜。这都呢屏蔽我也是服了
其实很多题都是模板题。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int prime[N];  //第i个素数
bool is_prime[N+1];  //is_prime[i]为true时表示i是素数
int sieve(int n) {//返回n以内素数的个数
    int p = 0;
    for(int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i]) {
            prime[p++] = i;
            for(int j = 2*i; j <= n; j+=i) is_prime[j] = false;  //筛去所有素数的倍数
        }
    }
    return p;
}
void work(int num,int nump){
    int pf[N],m=0;
    cout<<num;
    for(int i=0;num!=1&&i<nump;i++){
        while(num%prime[i]==0){
            pf[m++]=prime[i];
            num/=prime[i];
        }
    }
    cout<<"="<<pf[0];
    for(int i=1;i<m;i++)
        cout<<"*"<<pf[i];
    cout<<endl;
}
int main() {
    int a,b;
    cin>>a>>b;
    int nump=sieve(b);
    for(int i=a;i<=b;i++){
        if(is_prime[i]) cout<<i<<"="<<i<<endl;
        else work(i,nump);
    }
    return 0;
}

矩阵快速幂

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=32;
ll num,m;
void multi(ll p1[][N],ll p2[][N],int x) {
    ll p[N][N];
    memset(p,0,sizeof(p));
    for(int i=0; i<x; i++)
        for(int j=0; j<x; j++)
            for(int k=0; k<x; k++)
                p[i][j]+=p1[i][k]*p2[k][j];
    for(int i=0; i<x; i++)
        for(int j=0; j<x; j++)
            p1[i][j]=p[i][j];
}

ll res[N][N];
void Pow(ll p[][N],ll n) {
    memset(res,0,sizeof(res));
    for(int i=0; i<num; i++) res[i][i]=1;
    while(n) {
        if(n&1) multi(res,p,num);
        multi(p,p,num);
        n>>=1;
    }
}

int main() {
    while(cin>>num>>m) {
        ll a[N][N];
        for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
        cin>>a[i][j];
        Pow(a,m);
        for(int i=0;i<num;i++){
        for(int j=0;j<num;j++)
        cout<<res[i][j]<<" ";
        cout<<endl;
    }}
    return 0;
}

矩形的交

HDU2056
说来惭愧，我当时被卡住了。
思路是把对角线格式化为主对角线，然后按格式取交点，再按格式判断是否交，我觉得是很妙的。

#include <iostream>
#include <cstdio>
using namespace std;
struct p {
    double x,y;
} a[5];
void format(p &a,p &b) {
    if(a.x>b.x) swap(a.x,b.x);
    if(a.y<b.y) swap(a.y,b.y);
}
int main() {
    while(cin>>a[1].x>>a[1].y>>a[2].x>>a[2].y>>a[3].x>>a[3].y>>a[4].x>>***) {
        format(a[1],a[2]);
        format(a[3],a[4]);
        p v1,v2;
        v1.x=max(a[1].x,a[3].x);
        v1.y=min(a[1].y,a[3].y);
        v2.x=min(a[2].x,a[4].x);
        v2.y=max(a[2].y,***);
        double ans;
        if(v1.x<v2.x&&v1.y>v2.y) ans=(v2.x-v1.x)*(v1.y-v2.y);
        else ans=0;
        printf("%.2f\n",ans);
    }
    return 0;
}

贪心回文串

题意：一个字符串，最少需要多少步相互交换可以变成回文串。
标题是《完美的代价》
http://lx.lanqiao.cn/problem.page?gpid=T60

#include <bits/stdc++.h>
using namespace std;
int main() {
    int l;
    while(cin>>l) {
        string a;
        cin>>a;
        int b[26]= {0};
        for(int i=0; i<l; i++) b[a[i]-'a']++;
        int cnt=0;
        for(int i=0; i<26; i++) if(b[i]&1)++cnt;
        if(cnt>1) printf("Impossible\n");
        else {
            int ans=0,mid=(l-1)/2;
            for(int i=0,j,g=l-1; i<=mid; i++) {//g目标点 对称点 
                //查找是否存在不同位置的相同字母
                for(j=g; j>i; j--) {
                    //存在
                    if(a[i]==a[j]) {
                        if(j<g){
                            char tmp=a[j];
                            for(int k=j+1;k<=g;k++) a[k-1]=a[k];
                            a[g]=tmp;
                            ans+=(g-j);
                        }
                        --g;
                        break;
                    }
                }
                //不存在，则为奇数字母
                if(j==i) ans+=mid-i;//奇数字母到达中点位置所需次数
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

其他的地方都好理解，唯一麻烦的就是碰到奇数字母的时候：

1. 如果奇数字母出现在左半边(acbab)，也就是i循环能搜索到，j循环搜索不到，最核心的地方就在于那个g，g没有改变，所以对称位置（目标位置）是对的；
2. 如果奇数字母出现在右半边（abbac），i循环搜索不到，没有关系，会自动把它排过去，因为每个i都对应锚定了相应的正确的g，而离g最近的同字母也被换到了那个位置，最后就相当于不重复地完成了挪动操作，其实就可以理解为一个操作的可拆解成多个部分。

中文读数

杨文冠的代码比我的更好

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
    string liang[10]= {"","万","亿"};
    string digits[10] = {"","十", "百","千"};
    string number[10] = {"零", "一", "二", "三", "四", "五", "六", "七", "***"};
    string str;
    while(cin >> str) {
        int len=str.length();
        if(str=="0") cout<<"零";
        for(int i=0,j=0; i<len; ++i) {
            int a=(len-i-1)/4;
            int b=(len-i-1)%4;
            int num=str[i]-'0';
            if(num==0) {
                if(!b) {
                    int count = min(i+1, 4);
                    bool all = true;
                    for(int j=0; j<count; ++j)    if(str[i-j]!='0') {
                            all=false;
                            break;
                        }
                    if(a>2) a=(a&1)+!(a&1)*2;
                    if(all) {
                        if(a==2)    cout<<liang[a];
                        continue;
                    } else
                        cout<<liang[a];
                }
                if(i+1<len&&str[i+1]!='0')
                    cout<<"零";
            } else if(!i&&num==1&&b==1)    cout<<"十";
            else {
                cout<<number[num];
                if(b)    cout<<digits[b];
                else {
                    if(a>2) a=(a&1)+!(a&1)*2;
                    cout<<liang[a];
                }
            }
        }
        cout<<endl;
    }
    return 0;
}

芯片测试

http://lx.lanqiao.cn/problem.page?gpid=T64
枚举法：噪音低于50%，无法干扰正常报告，用所有芯片测试a，1的结果多于0的结果则是好的，反之则是坏的。即分析纵列。

#include<iostream>
using namespace std;
int main() {
    int a,cnt[30]= {0};
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=n; j++) {
            cin>>a;
            if(a) cnt[j]++;
        }
    for(int i=1; i<=n; i++) 
        if(cnt[i]>n/2) cout<<i<<" ";
    cout<<endl;
    return 0;
}

最优解法是分治，之后来填坑。

1. k ← n
2. while k > 3 do
3. ​ 将芯片分为k/2(下取整)组
4. ​ 对每一组
5. ​ if 两片好，任取一片留下
6. ​ else 两片同时丢掉
7. ​ k ← 剩下的芯片数
8. if k == 3
9. then 任取2片测试
10. ​ if 至少1坏，取没测的芯片
11. ​ else 任取1片被测芯片
12. if k = 2 or 1 then 任取1片
    对于 n为奇数的情况需要进一步处理 , 处理时间为 O(n).(剩下的那片用挑出的芯片检测)