AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int a,b,i,j,num=0,digit=1;
    string s;
    cin>>a>>s>>b;
    reverse(s.begin(),s.end());
    for(i=0;i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9'){
            num+=digit*(s[i]-'0');
        }else if(s[i]>='a'&&s[i]<='z'){
            num+=digit*(s[i]-'a'+10);
        }else{
            num+=digit*(s[i]-'A'+10);
        }
        digit*=a;
    }
    string ans="";
    int t;
    while(num){
        t=num%b;
        if(t>=0&&t<=9){
            ans+=(t+'0');
        }else{
            ans+=(t+'A'-10);
        }
        num/=b;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;


    return 0;
}

思路

• 按照数制转换规则，将 $a$ 进制数先转化为十进制，再把转化后的十进制数转化为 $b$ 进制。

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int a,b,i,j,num=0,digit=1;
    string s;
    cin>>a>>s>>b;
    reverse(s.begin(),s.end());
    for(i=0;i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9'){
            num+=digit*(s[i]-'0');
        }else if(s[i]>='a'&&s[i]<='z'){
            num+=digit*(s[i]-'a'+10);
        }else{
            num+=digit*(s[i]-'A'+10);
        }
        digit*=a;
    }
    string ans="";
    int t;
    while(num){
        t=num%b;
        if(t>=0&&t<=9){
            ans+=(t+'0');
        }else{
            ans+=(t+'A'-10);
        }
        num/=b;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;


    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int main(void){
    int n;
    int i;;
    scanf("%d",&n);
    int tmp;
    for(i=1;i<=n;i++){
        scanf("%d",&tmp);
        q.push(tmp);
    }
    int ans=0;
    for(i=1;i<n;i++){
        tmp=q.top();
        q.pop();
        tmp+=q.top();
        q.pop();
        q.push(tmp);
        ans+=tmp;
    }
    cout<<ans<<endl;

    return 0;
}

思路

• 哈夫曼树，贪心思想，用优先队列实现。
• 时间复杂度为 $O(nlogn)$ ，空间复杂度为 $O(n)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int main(void){
    int n;
    int i;;
    scanf("%d",&n);
    int tmp;
    for(i=1;i<=n;i++){
        scanf("%d",&tmp);
        q.push(tmp);
    }
    int ans=0;
    for(i=1;i<n;i++){
        tmp=q.top();
        q.pop();
        tmp+=q.top();
        q.pop();
        q.push(tmp);
        ans+=tmp;
    }
    cout<<ans<<endl;

    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n,i;
    set<int> s;
    scanf("%d",&n);
    int tmp;
    for(i=1;i<=n;i++){
        scanf("%d",&tmp);
        s.insert(tmp);
    }
    set<int>::iterator it;
    for(it=s.begin();it!=s.end();it++){
        cout<<(*it)<<" ";
    }
    cout<<endl;

    return 0;
}

思路

• 将所有元素放入 $set$ 中，$set$ 本身有序，可以直接按序输出。
• 时间复杂度为 $O(nlogn)$ ，空间复杂度为 $O(n)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n,i;
    set<int> s;
    scanf("%d",&n);
    int tmp;
    for(i=1;i<=n;i++){
        scanf("%d",&tmp);
        s.insert(tmp);
    }
    set<int>::iterator it;
    for(it=s.begin();it!=s.end();it++){
        cout<<(*it)<<" ";
    }
    cout<<endl;

    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=15,M=10;
int f[N][N];
int main(void){
    int i,m,n,j,k;
    for(i=0;i<=M;i++) f[0][i]=1;
    for(i=1;i<=M;i++){
        for(j=1;j<=M;j++){
            if(j>i) f[i][j]=f[i][i];
            else{
                for(k=1;k<=j;k++){
                    f[i][j]+=f[i-k][k];
                }
            }
        }
    }
    while(~scanf("%d%d",&m,&n)){
        cout<<f[m][n]<<endl;
    }

    return 0;
}

思路

• 设 $f[i][j]$ 表示把 $i$ 个苹果放到 $j$ 个盘子的方案数，当 $i \ge j$ 时放有苹果的盘子数可能有 $1,2,…j$ ，每种情况看成一类，设有 $k$ 个盘子不空（$k\le j$），则这种情况相当于 $i-k$ 个苹果放到 $k$ 个盘子中的方案数（在原方案上每个盘子再加上一个苹果即可）。所以有转移方程 $f[i][j]=\sum_{k=1}^{k=j}f[i-k][k],i \ge j$ ，当 $i <j$ 时最少有 $j-i$ 个盘子一定为空，所以有 $f[i][j]=f[i][i],i < j$ 。
• 时间复杂度为 $O(10^3+t)$ ，空间复杂度为 $O(10^3)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=15,M=10;
int f[N][N];
int main(void){
    int i,m,n,j,k;
    for(i=0;i<=M;i++) f[0][i]=1;
    for(i=1;i<=M;i++){
        for(j=1;j<=M;j++){
            if(j>i) f[i][j]=f[i][i];
            else{
                for(k=1;k<=j;k++){
                    f[i][j]+=f[i-k][k];
                }
            }
        }
    }
    while(~scanf("%d%d",&m,&n)){
        cout<<f[m][n]<<endl;
    }

    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int num,n,i,j;
    scanf("%d",&num);
    for(j=1;j<=num;j++){
        unordered_set<string> place;
        unordered_set<string> arrive;
        unordered_map<string,string> ap;
        scanf("%d",&n);
        string s,t;
        for(i=1;i<=n;i++){
            cin>>s>>t;
            place.insert(s),place.insert(t);
            arrive.insert(t);
            ap[s]=t;
        }
        string tmp;
        unordered_set<string>::iterator it;
        for(it=place.begin();it!=place.end();it++){
            if(arrive.count(*it)==0){
                tmp=(*it);
            }
        }
        printf("Case #%d:",j);
        for(i=1;i<=n;i++){
            cout<<" "<<tmp<<"-"<<ap[tmp];
            tmp=ap[tmp];
        }
        cout<<endl;
    }
    return 0;
}

思路

• 入度为 $0$ （即没有航班抵达的地方是出发点），然后从出发点开始遍历航班即可找到完整路线。
• 时间复杂度为 $O(T \times N)$ ，空间复杂度为 $O(N)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int num,n,i,j;
    scanf("%d",&num);
    for(j=1;j<=num;j++){
        unordered_set<string> place;
        unordered_set<string> arrive;
        unordered_map<string,string> ap;
        scanf("%d",&n);
        string s,t;
        for(i=1;i<=n;i++){
            cin>>s>>t;
            place.insert(s),place.insert(t);
            arrive.insert(t);
            ap[s]=t;
        }
        string tmp;
        unordered_set<string>::iterator it;
        for(it=place.begin();it!=place.end();it++){
            if(arrive.count(*it)==0){
                tmp=(*it);
            }
        }
        printf("Case #%d:",j);
        for(i=1;i<=n;i++){
            cout<<" "<<tmp<<"-"<<ap[tmp];
            tmp=ap[tmp];
        }
        cout<<endl;
    }
    return 0;
}