头像

曦薇




离线:4小时前


最近来访(127)
用户头像
CodeFish
用户头像
pdsujc05
用户头像
OI
用户头像
也_1
用户头像
modinte
用户头像
淡漠忧伤
用户头像
我要出去乱说
用户头像
WangJY
用户头像
你在干什么
用户头像
诗人kris
用户头像
realdan
用户头像
Cccc
用户头像
努力学习鸭
用户头像
solo起来
用户头像
Le_5
用户头像
List
用户头像
不知不觉我怎么......
用户头像
mfs0914
用户头像
Kingsley
用户头像
嘉然今天写代码

活动打卡代码 AcWing 3438. 数制转换

曦薇
7小时前

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;
}




曦薇
7小时前

思路

  • 按照数制转换规则,将 $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;
}



活动打卡代码 AcWing 3531. 哈夫曼树

曦薇
1天前

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;
}




曦薇
1天前

思路

  • 哈夫曼树,贪心思想,用优先队列实现。
  • 时间复杂度为 $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;
}



活动打卡代码 AcWing 3477. 简单排序

曦薇
2天前

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;
}




曦薇
2天前

思路

  • 将所有元素放入 $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;
}



活动打卡代码 AcWing 3428. 放苹果

曦薇
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;
}




曦薇
3天前

思路

  • 设 $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;
}



活动打卡代码 AcWing 693. 行程排序

曦薇
4天前

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;
}




曦薇
4天前

思路

  • 入度为 $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;
}