PAT甲级题目合集

1001

C++新特性里的to_string()函数可以将数字变为字符串,非常方便

#include <iostream>
#include <string>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    string c = to_string(a + b);
    int flag = 0;
    for (int i = 0; i<c.size(); ++i) {
        if (c[i] == '-')
            flag = 1;
        cout << c[i];
        if ((c.size() - 1 - i) % 3 == 0 && i != c.size() - 1&&(flag!=1||i!=0)) {
            cout << ",";
        }
    }
    return 0;
}

1002

映射法

#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    float hashT[1001];
    memset(hashT,0,sizeof(hashT));
    int k,cnt=0;
    for(int i=0;i<2;++i){
        scanf("%d",&k);
        int N;
        float ai;
        for(int j=0;j<k;++j){
            scanf("%d %f",&N,&ai);
            hashT[N]+=ai;
        }
    }
    for(int i=0;i<1001;++i){
        if(hashT[i]!=0)cnt++;
    }
    printf("%d",cnt);
    for(int i=1000;i>=0;--i){
        if(hashT[i]!=0.0){
            printf(" %d %.1f",i,hashT[i]);
        }
    }
    return 0;
}

1003

经典的Dijkstra算法,dist[i]数组存储起始点到i点的路径长度,w[i]存储当前路径下最多的救援队数目,num[i]存储起点到达i点的最短路径数目。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define INF 1000000
using namespace std;

/* 
scatter 分散
call up hands 召集人手 
*/

int main() {
    int N,M,C1,C2;
    int dist[510];//起点到终点的距离
    int e[510][510];//边的权重
    int num[510];//代表起点到终点最短路径的条数 
    int weight[510];//代表各个城市救援队的数目 
    int w[510];//代表起点到终点救援队的数目 
    bool visited[510];//代表该结点是否访问过 
    fill(e[0],e[0]+510*510,INF);
    fill(dist,dist+510,INF);
    scanf("%d %d %d %d",&N,&M,&C1,&C2);
    for(int i=0;i<N;++i){
        scanf("%d",&weight[i]);
    }
    int a,b,c;
    for(int i=0;i<M;++i){
        scanf("%d%d%d",&a,&b,&c);
        e[a][b]=e[b][a]=c;
    }
    dist[C1]=0;
    w[C1]=weight[C1];
    num[C1]=1;
    for(int i=0;i<N;++i){
        int u=-1,minn=INF;//u存储从这个点出发可以访问的点中距离最小的 
        for(int j=0;j<N;++j){
            if(visited[j]==false&&dist[j]<minn){
                u=j;
                minn=dist[j];
            }
        }
        if(u==-1)break;//没有找到u,即图里的所有非孤立点已经搜索完毕 
        visited[u]=true;
        for(int v=0;v<N;++v){//寻找点u的未访问过的邻接点 
            if(visited[v]==false&&e[u][v]!=INF){//这个点没有访问过,并且u和v之间存在边 
                if(dist[v]>dist[u]+e[u][v]){
                    dist[v]=dist[u]+e[u][v];//如果距离小,更新v到起点的距离
                    num[v]=num[u];
                    w[v]=w[u]+weight[v]; 
                }else if(dist[v]==dist[u]+e[u][v]){
                    num[v]=num[u]+num[v];
                    if(w[u]+weight[v]>w[v]){//更新救援队数目 
                        w[v]=w[u]+weight[v];
                    }
                }
            }
        } 
    }
    printf("%d %d",num[C2],w[C2]);
    return 0;
}

1004

题目的意思是输出一棵树每一层的叶子节点数目,使用邻接表存储输入的树。用dfs遍历每一个节点,并用一个高度数组存储每一层叶子节点的数目。

#include <iostream>
#include <vector>
#include <string.h> 
#include <stdio.h>
#include <algorithm>
using namespace std;
vector<int> tree[100];
int book[100],max_depth=-1;
/*
pedigree 血统 家族 
*/
void dfs(int index,int depth){
    if(tree[index].size()==0){
        book[depth]++;
        max_depth=max(depth,max_depth);
        return;
    }
    for(int i=0;i<tree[index].size();++i){
        dfs(tree[index][i],depth+1);
    }
}

int main() {
    int n,m;
    memset(book,0,sizeof(book));
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;++i){
        int id,num,son;
        scanf("%d %d",&id,&num);
        for(int j=0;j<num;++j){
            scanf("%d",&son);
            tree[id].push_back(son);
        }
    }
    dfs(1,0);
    for(int i=0;i<=max_depth;++i){
        if(i==0)printf("%d",book[i]);
        else printf(" %d",book[i]); 
    } 
    return 0;
}

1005

#include <iostream>
#include <stdio.h>
#include <string>
#define charToNum(x) (x-'0')
using namespace std;


int main() {
    int sum = 0;
    string hashT[] = { "zero","one","two","three","four","five","six","seven","eight","nine" };
    string input;
    cin >> input;
    for (int i = 0; i<input.size(); ++i) {
        sum += charToNum(input[i]);
    }
    string pig = to_string(sum);
    bool flag = true;
    for (int i = 0;i< pig.size(); ++i) {
        if (flag) {
            cout << hashT[charToNum(pig[i])];
            flag = false;
        }
        else {
            cout << " " << hashT[charToNum(pig[i])];
        }
    }
}

1006

字符串处理

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    string unlock,lock,input;
    int N,t_ul_h,t_ul_m,t_ul_s,t_l_h,t_l_m,t_l_s;
    int ul=999999,l=0;
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>input;
        scanf("%d:%d:%d",&t_ul_h,&t_ul_m,&t_ul_s);
        scanf("%d:%d:%d",&t_l_h,&t_l_m,&t_l_s);
        int t_ul=t_ul_h*3600+t_ul_m*60+t_ul_s;
        int t_l=t_l_h*3600+t_l_m*60+t_l_s;
        if(ul>t_ul){
            unlock=input;
            ul=t_ul;
        }
        if(l<t_l){
            lock=input;
            l=t_l;
        }
    }
    cout<<unlock<<" "<<lock;
    return 0;
}

1007

最大连续子列和问题
递推式:dp[i]=max(dp[i-1],0)+num[i]
dp[i]表示以i结尾的子列的最大和

#include <iostream>
#include <algorithm>
using namespace std;

/*
indices index的复数 
*/ 

int main() {
    int N;
    int dp[10010],save[10010];
    dp[0]=0;
    cin>>N;
    int left=1,right=N,max_num=-1,temp=1;
    for(int i=1;i<=N;++i){
        cin>>save[i];
    }
    for(int i=1;i<=N;++i){
        if(dp[i-1]>0){
            dp[i]=dp[i-1]+save[i];
        }else{
            dp[i]=save[i];
            temp=i;
        }
        if(dp[i]>max_num){
            left=temp;
            right=i;
            max_num=dp[i];
        }
    }
    if(max_num<0){
        max_num=0;
        left=1;
        right=N;
    }
    cout<<max_num<<" "<<save[left]<<" "<<save[right];
    return 0;
}

1008

??甲级

#include <iostream>
#include <stdio.h>
using namespace std;
/*
denote 代表 指代 预示 
*/
int main() {
    int N,sum=0,refloor=0,floor;
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>floor;
        floor>refloor?sum+=(6*(floor-refloor)):sum+=(4*(refloor-floor));
        sum+=5;
        refloor=floor;
    } 
    cout<<sum;
    return 0;
}

1009

num数组开1000只有5分...开1001就25分了

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    double num1[1001]={0.0};
    double answer[2010]={0.0};
    int K1,K2,expo,cnt=0;
    double coef;
    scanf("%d",&K1);
    for(int i=0;i<K1;++i){
        scanf("%d %lf",&expo,&coef);
        num1[expo]=coef;
    }
    scanf("%d",&K2);
    for(int i=0;i<K2;++i){
        scanf("%d %lf",&expo,&coef);
        for(int j=0;j<=1000;++j){
            answer[expo+j]+=(coef*num1[j]);
        }
    }
    for(int i=0;i<2005;++i){
        if(answer[i]!=0)cnt++;
    }
    cout<<cnt;
    for(int i=2005;i>=0;--i){
        if(answer[i]!=0)printf(" %d %.1f",i,answer[i]);
    }
    return 0;
}

1011

?????甲级

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
/*
trophy 纪念品,战利品
lottery 彩票
triple 三倍的
tie 平局
odd 奇数的
product 乘积
time 乘以 
*/

int main() {
    double w,t,l,sum=0.65;
    char output[]={'W','T','L'};
    int num[3];
    for(int i=0;i<3;++i){
        scanf("%lf%lf%lf",&w,&t,&l);
        if(w>t&&w>l){
            num[i]=0;
            sum*=w;
        }else if(t>w&&t>l){
            num[i]=1;
            sum*=t;
        }else{
            num[i]=2;
            sum*=l;
        }
    } 
    for(int i=0;i<3;++i){
        printf("%c ",output[num[i]]);
    }
    printf("%.2f",(sum-1)*2);
    return 0;
}

1012

先将学生的四个成绩存储到vector中排序,然后用map存储学生的best rank,按c,m,e,a的顺序更新一个学生的rank

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct one{
    int id;
    double grade;
};
struct best{
    char subject;
    int rank=-1;
};
vector<one> C,Math,E,A;
map<int,best> ranker;

bool compare(one a,one b){
    return a.grade>b.grade;
}

int main() {
    int N,M,id,c,m,e,a;
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;++i){
        scanf("%d",&id);
        cin>>c>>m>>e;
        C.push_back(one{id,c});
        Math.push_back(one{id,m});
        E.push_back(one{id,e});
        A.push_back(one{id,c+m+e});
    }
    sort(C.begin(),C.end(),compare);
    sort(Math.begin(),Math.end(),compare);
    sort(E.begin(),E.end(),compare);
    sort(A.begin(),A.end(),compare);
    int num=1,save=1;
    for(int i=0;i<E.size();++i){
        if(i>=1&&E[i].grade<E[i-1].grade){
            num+=save;
            save=1; 
        }else if(i>=1)save++;
        ranker[E[i].id].rank=num;
        ranker[E[i].id].subject='E';
    }
    num=1,save=1;
    for(int i=0;i<Math.size();++i){
        if(i>=1&&Math[i].grade<Math[i-1].grade){
            num+=save;
            save=1; 
        }else if(i>=1)save++;
        if(num<=ranker[Math[i].id].rank){
            ranker[Math[i].id].rank=num;
            ranker[Math[i].id].subject='M';
        }
    }
    num=1,save=1;
    for(int i=0;i<C.size();++i){
        if(i>=1&&C[i].grade<C[i-1].grade){
            num+=save;
            save=1; 
        }else if(i>=1)save++;
        if(num<=ranker[C[i].id].rank){
            ranker[C[i].id].rank=num;
            ranker[C[i].id].subject='C';
        }
    }
    num=1,save=1;
    for(int i=0;i<A.size();++i){
        if(i>=1&&A[i].grade<A[i-1].grade){
            num+=save;
            save=1; 
        }else if(i>=1)save++;
        if(num<=ranker[A[i].id].rank){
            ranker[A[i].id].rank=num;
            ranker[A[i].id].subject='A';
        }
    }
    for(int i=0;i<M;++i){
        scanf("%d",&id);
        if(ranker[id].rank!=-1)
            cout<<ranker[id].rank<<" "<<ranker[id].subject<<endl;
        else
            cout<<"N/A"<<endl;
    }
}

1013

图的连通分量

#include <iostream>
#include <vector>
#include <map> 
#include <string.h>
#include <algorithm>
using namespace std;
bool e[1000][1000];
int N,M,K,u,v,lost; 
bool once[1000];

void dfs(int node,int lost_node){
    if(once[node])return;
    once[node]=true;
    for(int i=1;i<=N;++i){
        if(i!=lost_node&&e[node][i])
            dfs(i,lost_node);
    }
}

int main() {
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<M;++i){
        scanf("%d%d",&u,&v);
        e[u][v]=true;
        e[v][u]=true;
    }
    for(int i=0;i<K;++i){
        scanf("%d",&lost);
        memset(once,0,sizeof(once));
        int cnt=0;
        for(int j=1;j<=N;++j){
            if(j!=lost&&!once[j]){
                dfs(j,lost);
                cnt++;
            }
        }
        cout<<cnt-1<<endl;
    } 
    return 0;
}

1015

素数判定+进制转换

#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std;

/*
decimal 十进制的,小数的 
radix 根 基数
negative 负数的 负的 
*/

bool isPrime(int x){
    if(x==1||x==0)return false;
    for(int i=2;i*i<=x;++i){
        if(x%i==0)return false;
    }
    return true;
}

int toDecimal(int x,int r){
    string ans="";
    int the_num=0;
    while(x!=0){
        ans+=numToChar(x%r);
        x/=r;
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();++i){
        the_num+=charToNum(ans[i])*pow(r,i);
    }
    return the_num;
}

int main() {
    int x,radix;
    while(scanf("%d",&x)){
        if(x<0)return 0;
        scanf("%d",&radix);
        if(isPrime(x)&&isPrime(toDecimal(x,radix)))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

1017

将输入的时间全部转化为秒,再排序。
windows数组记录每个窗口结束工作的时间,如果一个人的到达时间小于窗口的结束工作时间,总等待时常sum增加(结束工作的时间-到达时间)

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std; 
struct person{
    int tt;
    int process;
}t[10000];

bool compare(person a,person b){
    return a.tt<b.tt;
}

int main() {
    int N,K,h,m,s;
    double sum=0;
    scanf("%d%d",&N,&K);
    vector<int> windows(K,8*60*60);
    for(int i=0;i<N;++i){
        scanf("%d:%d:%d %d",&h,&m,&s,&t[i].process);
        t[i].tt=h*3600+m*60+s;
    }
    int people=N;
    sort(t,t+N,compare);
    for(int i=0;i<N;++i){
        if(t[i].tt>17*60*60){
            people--;
            continue;
        }
        int cnt=0;
        for(int j=0;j<K;++j){
            if(windows[cnt]>windows[j]){
                cnt=j;
            }
        }
        if(t[i].tt<=windows[cnt]){
            sum+=(windows[cnt]-t[i].tt);
            windows[cnt]+=t[i].process*60;
        }else{
            windows[cnt]=t[i].tt+t[i].process*60;
        }
    }
    printf("%.1f",sum/(60*people));
    return 0;
}

1018

Dijkstra+dfs
本题主要的坑在于后面节点的单车不能移送给前面的节点,导致第五,第七个测试点无法通过,解决方法是用Dfs回溯所有的节点。

#include <iostream>
#include <stack>
#include <map>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define INF 1000000
using namespace std; 
int minNeed=INF,minBack=INF;
int C,N,S,M,dist[510],e[510][510],weight[510];
bool visit[510];
vector<int> preway[510];
vector<int> path,temppath;
void Dfs(int v){
    temppath.push_back(v);
    if(v==0){
        int need=0,back=0;
        for(int i=temppath.size()-1;i>=0;--i){
            int pos=temppath[i];
            if(weight[pos]>0){
                back+=weight[pos];
            }else{
                if(back>(0-weight[pos])){
                    back+=weight[pos];
                }else{
                    need+=(0-weight[pos]-back);
                    back=0;
                }
            }
        } 
        if(need<minNeed){
            minNeed=need;
            minBack=back;
            path=temppath;
        }else if(need==minNeed&&back<minBack){
            minBack=back;
            path=temppath;
        }
        temppath.pop_back();
        return;
    }
    for(int i=0;i<preway[v].size();++i){
        Dfs(preway[v][i]);//检索一条路 
    }
    temppath.pop_back();
}

int main() {
    
    fill(e[0],e[0]+510*510,INF);
    fill(dist,dist+510,INF);
    scanf("%d %d %d %d",&C,&N,&S,&M);
    for(int i=1;i<=N;++i){
        scanf("%d",&weight[i]);
        weight[i]=weight[i]-C/2;
    }
    int a,b,c;
    for(int i=1;i<=M;++i){
        scanf("%d %d %d",&a,&b,&c);
        e[a][b]=e[b][a]=c;
    }
    dist[0]=0;
    for(int i=0;i<=N;++i){
        int u=-1,minn=INF;
        for(int j=0;j<=N;++j){
            if(dist[j]<minn&&!visit[j]){
                u=j;
                minn=dist[j];
            }
        }
        if(u==-1)break;
        visit[u]=true;
        for(int v=0;v<=N;++v){
            if(!visit[v]&&e[u][v]!=INF){
                if(e[u][v]+dist[u]<dist[v]){
                    dist[v]=dist[u]+e[u][v];
                    preway[v].clear();
                    preway[v].push_back(u);
                }else if(e[u][v]+dist[u]==dist[v]){
                    preway[v].push_back(u);
                }
            }
        }
    }
    Dfs(S);
    printf("%d 0",minNeed);
    for(int i=path.size()-2;i>=0;--i){
        printf("->%d",path[i]);
    }
    printf(" %d",minBack);
    return 0;
}

1019

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
/*
notation 记号
*/

int main() {
    int N, base;
    vector<string> save;
    cin >> N >> base;
    while (N != 0) {
        save.push_back(to_string(N%base));
        N /= base;
    }
    bool isOK = true;
    for (int i = 0; i < save.size() / 2; ++i) {
        if (save[i] != save[save.size() - i - 1])isOK = false;
    }
    isOK ? cout << "Yes" << endl : cout << "No" << endl;
    bool flag = true;
    reverse(save.begin(), save.end());
    for (int i = 0; i < save.size(); ++i) {
        if (flag) {
            cout << save[i];
            flag = false;
        }
        else {
            cout <<" "<< save[i];
        }
    }
    return 0;
}

1021

这是只有23分的代码,第三个测试点超时了,估计是进行了多次深搜的缘故,英国可以用一次深搜解决不过我太懒了

#include <iostream>
#include <vector>
#include <map> 
#include <string.h>
#include <algorithm>
using namespace std;
/*
acyclic 非循环的 非周期的 
*/
bool e[10001][10001];
int N,a,b,circle=0,deepest=-1;
bool visited[10001];
int highest[10001];
void dfs(int node){
    visited[node]=true;
    for(int i=1;i<=N;++i){
        if(e[node][i]&&!visited[i])dfs(i);
    }
}
void DFS(int root,int node,int depth){
    if(visited[node]){
        return;
    }
    highest[root]=max(highest[root],depth);
    visited[node]=true;
    deepest=max(deepest,depth);
    for(int i=1;i<=N;++i){
        if(e[node][i])DFS(root,i,depth+1);
    }
    visited[node]=false;
}
int main() {
    memset(highest,0,sizeof(highest));
    cin>>N;
    for(int i=0;i<N-1;++i){
        cin>>a>>b;
        e[a][b]=e[b][a]=true;
    }
    for(int i=1;i<=N;++i){
        if(!visited[i]) {
            dfs(i);
            circle++;
        }
    }
    memset(visited,0,sizeof(visited));
    if(circle>=2){
        printf("Error: %d components",circle);
        return 0;
    }
    for(int i=1;i<=N;++i){
        DFS(i,i,1);
    }
    for(int i=1;i<=N;++i){
        if(highest[i]==deepest)cout<<i<<endl;
    }
    return 0;
}

1023

大整数加减进位要注意呀

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std; 
/*
duplication 重复
permutation 排序 
*/

int main() {
    int mapper[9];
    fill(mapper,mapper+9,0);
    string a;
    cin>>a;
    for(int i=0;i<a.size();++i){
        mapper[charToNum(a[i])]++;
    }
    reverse(a.begin(),a.end());
    bool flag=false,isOk=true;
    for(int i=0;i<a.size();++i){
        int t=charToNum(a[i])*2;
        if(flag){
            t+=1;
            flag=false; 
        }
        if(t>9)flag=true;
        t%=10;
        a[i]=numToChar(t);
        if(--mapper[t]<0)isOk=false;
    }
    if(flag)a+='1';
    isOk&&!flag?cout<<"Yes"<<endl:cout<<"No"<<endl;
    reverse(a.begin(),a.end());
    cout<<a<<endl;
    return 0;
}

1024

大整数加减

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define charToNum(x) (x-'0')
#define numToChar(x) (x+'0')
using namespace std;
/*
palindromic 复发的 再发的
via 通过 经过 
*/

string add(string x,string y){
    string ans="";
    int sum=0;
    bool flag=false;
    for(int i=0;i<x.size();++i){
        if(flag){
            sum+=1;
            flag=false;
        }
        sum+=charToNum(x[i])+charToNum(y[i]);
        if(sum>9){
            sum%=10;
            flag=true;
        }
        ans+=numToChar(sum);
        sum=0;
    }
    if(flag)ans+='1';
    reverse(ans.begin(),ans.end());
    return ans;
}

bool isPalindromic(string x){
    string y=x;
    reverse(x.begin(),x.end());
    return x==y;
}

int main() {
    string input;
    int step,cnt=0;
    cin>>input>>step;
    while(cnt++<step&&!isPalindromic(input)) {
        string temp=input;
        reverse(temp.begin(),temp.end());
        input=add(input,temp);
    }
    cout<<input<<endl<<cnt-1;
    return 0;
}

1025

含有并列的排名如何排序

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
simultaneously 同时地 一齐的 
testee 考试者 
*/

struct testee{
    string id;
    int grade;
    int local_rank;
    int rank;
    int location;
}; 

vector<testee> save;

bool cmp(testee a,testee b){
    return a.grade!=b.grade?a.grade>b.grade:a.id<b.id;
}

int main() {
    int N,K;
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&K);
        vector<testee> atemp;
        for(int j=0;j<K;++j){
            testee temp;
            cin>>temp.id>>temp.grade;
            temp.location=i+1;
            atemp.push_back(temp);
        }
        sort(atemp.begin(),atemp.end(),cmp);
        int cnt=1,saver=1;
        atemp[0].local_rank=1;
        for(int i=1;i<atemp.size();++i){
            if(atemp[i].grade!=atemp[i-1].grade){
                cnt+=saver; 
                saver=1;
            }else saver++;
            atemp[i].local_rank=cnt;
        }
        save.insert(save.end(),atemp.begin(),atemp.end());
    }
    sort(save.begin(),save.end(),cmp);
    int cnt=1,saver=1;
    save[0].rank=1;
    for(int i=1;i<save.size();++i){
        if(save[i].grade!=save[i-1].grade){
            cnt+=saver; 
            saver=1;
        }else saver++;
        save[i].rank=cnt;
    }
    cout<<save.size()<<endl;
    for(int i=0;i<save.size();++i){
        cout<<save[i].id<<" "<<save[i].rank<<" "<<save[i].location<<" "<<save[i].local_rank<<endl;
    }
    return 0;
}

1027

十进制转13进制

#include <iostream>
#include <string>
using namespace std;

string trans(int x){
    string ans="";
    char hashT[]={'A','B','C'};
    int a=x/13;
    int b=x%13;
    if(a>=0&&a<10)ans+=(a+'0');
    else if(a>=10)ans+=hashT[a-10];
    if(b>=0&&b<10)ans+=(b+'0');
    else if(b>=10)ans+=hashT[b-10];
    return ans;
}

int main() {
    int r,g,b;
    cin>>r>>g>>b;
    cout<<"#"<<trans(r)<<trans(g)<<trans(b);
    return 0;
}

1029

双指针法,第二行不用存储,在线处理即可

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

int main() {
    int N,M,temp,flag=0;
    int count=0;
    vector<int> save;
    scanf("%d",&N);
    save.resize(N);
    for(int i=0;i<N;++i){
        scanf("%d",&save[i]);
    }
    scanf("%d",&M);
    int mid=(M+N+1)/2; 
    for(int i=0;i<M;++i){
        scanf("%d",&temp);
        bool ud=false;
        while(temp>save[flag]&&flag<N&&count<mid){
            if(++count==mid){
                cout<<save[flag];
            }
            flag++;
        }
        if(++count==mid){
            cout<<temp;
        }
    }
    while(flag<N){
        if(++count==mid){
            cout<<save[flag];
        }
        flag++;
    }
    return 0;
}

1030

Dijkstra+dfs
1018的简化版,把点权改成了边权

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 1000000
using namespace std;
int N,M,S,D,min_cost=INF;
int dist[510],weight[510][510],e[510][510];
bool visit[510];
vector<int> save[510];
vector<int> path,temppath;

void Dfs(int v){
    temppath.push_back(v);
    if(v==S){
        int cost=0;
        for(int i=0;i<temppath.size()-1;++i)
            cost+=weight[temppath[i]][temppath[i+1]];
        if(cost<min_cost){
            min_cost=cost;
            path=temppath;
        }
        temppath.pop_back();//回溯 
        return;
    }
    for(int i=0;i<save[v].size();++i){
        Dfs(save[v][i]);
    }
    temppath.pop_back();
}

int main() {
    fill(dist,dist+510,INF);
    fill(e[0],e[0]+510*510,INF);
    scanf("%d%d%d%d",&N,&M,&S,&D);
    int a,b,c,d;
    for(int i=0;i<M;++i){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        e[a][b]=e[b][a]=c;
        weight[a][b]=weight[b][a]=d;
    }
    dist[S]=0;
    for(int i=0;i<N;++i){
        int u=-1,minn=INF;
        for(int j=0;j<N;++j){
            if(!visit[j]&&dist[j]<minn){
                u=j;
                minn=dist[j];
            }
        }
        if(u==-1)break;
        visit[u]=true;
        for(int v=0;v<N;++v){
            if(e[u][v]!=INF&&!visit[v]){
                if(e[u][v]+dist[u]<dist[v]){
                    dist[v]=e[u][v]+dist[u];
                    save[v].clear();
                    save[v].push_back(u);
                }else if(e[u][v]+dist[u]==dist[v]){
                    save[v].push_back(u);
                }
            }
        }
    }
    Dfs(D);
    for(int i=path.size()-1;i>=0;--i){
        printf("%d ",path[i]);
    }
    printf("%d",dist[D]);
    printf(" %d",min_cost);
    return 0;
}

1031

#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
/*
vertical  竖直的 垂直的 
*/

int main() {
    string input;
    cin>>input;
    int k,t=3;
    int maxlen=0;
    for(;t<=input.size();++t){
        for(k=0;k<=t;k++){
            if(input.length()+2==2*k+t){
                maxlen=max(maxlen,k);
            }
        }
    }
    t=input.size()+2-2*maxlen;
    for(int i=0;i<maxlen-1;++i){
        cout<<input[i];
        for(int j=0;j<t-2;++j)cout<<" ";
        cout<<input[input.length()-i-1]<<endl;
    }
    for(int i=maxlen-1;i<=input.length()-maxlen;++i)cout<<input[i];
    return 0;
}

1032

简单的链表题

#include <iostream>
#include <algorithm>
#include <string.h>
#define INF 100000
using namespace std;

/*
suffix 后缀 词尾 
*/

int main() {
    int add[INF];
    int head1,head2,N,temp,next;
    bool visit[INF];
    memset(visit,0,sizeof(visit));
    char alpha;
    cin>>head1>>head2>>N;
    for(int i=0;i<N;++i){
        cin>>temp>>alpha>>next;
        add[temp]=next;
    }
    while(head1!=-1){
        visit[head1]=true;
        head1=add[head1];
    }
    while(head2!=-1){
        if(!visit[head2]){
            visit[head2]=true;
            head2=add[head2];
        }else break;
    }
    if(head2!=-1)
        printf("%05d",head2);
    else
        printf("-1");
    return 0;
}

1035

姥姥日常挖坑。。。注意account单复数

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
/*
generate 形成 造成 
*/
struct line{
    string id;
    string pwd;
}lines[1000];
bool flag[1000];

int main() {
    int N,cnt=0;
    fill(flag,flag+1000,0);
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>lines[i].id>>lines[i].pwd;
        for(int j=0;j<lines[i].pwd.size();++j){
            if(lines[i].pwd[j]=='1'){
                lines[i].pwd[j]='@';
                flag[i]=true;
            }else if(lines[i].pwd[j]=='0'){
                lines[i].pwd[j]='%';
                flag[i]=true;
            }else if(lines[i].pwd[j]=='l'){
                lines[i].pwd[j]='L';
                flag[i]=true;
            }else if(lines[i].pwd[j]=='O'){
                lines[i].pwd[j]='o';
                flag[i]=true;
            }
        }
        if(flag[i])cnt++;
    } 
    if(cnt){
        cout<<cnt<<endl;
        for(int i=0;i<N;++i){
            if(flag[i])cout<<lines[i].id<<" "<<lines[i].pwd<<endl;
        }
    }else if(N!=1){
        printf("There are %d accounts and no account is modified\n",N);
    }else{
        printf("There is 1 account and no account is modified\n");
    }
    return 0;
}

1036

怕不是假的甲级

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*
distinct 不同的,明显的 
*/

int main() {
    int N;
    string name,id,name_man,id_man,name_girl,id_girl;
    char gender;
    int grade,min_man=101,max_girl=-1;
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>name>>gender>>id>>grade;
        if(gender=='F'&&grade>max_girl){
            max_girl=grade;
            name_girl=name;
            id_girl=id;
        }else if(gender=='M'&&grade<min_man){
            min_man=grade;
            name_man=name;
            id_man=id;
        }
    }
    if(max_girl!=-1){
        cout<<name_girl<<" "<<id_girl<<endl;
    }else{
        cout<<"Absent"<<endl;
    }
    if(min_man!=101){
        cout<<name_man<<" "<<id_man<<endl;
    }else{
        cout<<"Absent"<<endl;
    }
    if(min_man!=101&&max_girl!=-1){
        cout<<max_girl-min_man<<endl;
    }else{
        puts("NA");
    }
    return 0;
}

1037

将正数与负数分开存储,然后贪心

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
bonus 奖金
exceed 超过 超越 
*/
bool cmp(int a,int b){
    return a>b;
}

int main() {
    int N,K,temp,sum=0,flag1=0,flag2=0;
    vector<int> coupon_1,coupon_2,product_1,product_2;
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>temp;
        if(temp>0)
            coupon_1.push_back(temp);
        else
            coupon_2.push_back(temp);
    }
    cin>>K;
    for(int i=0;i<K;++i){
        cin>>temp;
        if(temp>0)
            product_1.push_back(temp);
        else
            product_2.push_back(temp);
    }
    sort(coupon_1.begin(),coupon_1.end(),cmp);
    sort(product_1.begin(),product_1.end(),cmp);
    sort(coupon_2.begin(),coupon_2.end());
    sort(product_2.begin(),product_2.end());
    for(;flag1<coupon_1.size()&&flag2<product_1.size();){
        sum+=coupon_1[flag1++]*product_1[flag2++];
    }
    flag1=0;flag2=0;
    for(;flag1<coupon_2.size()&&flag2<product_2.size();){
        sum+=coupon_2[flag1++]*product_2[flag2++];
    }
    cout<<sum;
    return 0;
}

1038

这道题直接sort是不行的,要比较两个字符串谁在前面,只需将两者分别加起来比较就行。可以用erase方法删除首元素的0

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/*
segment 部分 
*/

bool cmp(string a,string b){
    return a+b<b+a;//这波操作真的牛逼 
}

int main() {
    int N;
    string temp,output;
    cin>>N;
    vector<string> input;
    for(int i=0;i<N;++i){
        cin>>temp;
        input.push_back(temp);
    }
    sort(input.begin(),input.end(),cmp);
    for(int i=0;i<N;++i)
        output+=input[i];
    while(output.length()!=1&&output[0]=='0'){
        output.erase(output.begin());
    }
    cout<<output<<endl;
    return 0;
}

1040

回文数的动态规划问题
dp[i][j]=1代表i~j为回文字符串
dp[i][j]=0代表i~j不是回文字符串
如果str[i]==str[j],dp[i][j]=dp[i+1][j-1]

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*
symmetric 相称的 均衡的 
*/
int main() {
    int max_num=1;
    string str;
    getline(cin,str);
    int dp[1010][1010];
    for(int i=0;i<str.length();++i){
        dp[i][i]=1;
        if(i<str.size()-1&&str[i]==str[i+1]){
            dp[i][i+1]=1;
            max_num=2; 
        }
    }
    for(int L=3;L<=str.length();++L){
        for(int i=0;i+L-1<str.length();++i){
            int j=i+L-1;
            if(str[i]==str[j]&&dp[i+1][j-1]==1)dp[i][j]=1;
            else dp[i][j]=0;
            if(dp[i][j])max_num=L;
        }
    }
    cout<<max_num;
    return 0;
}

1041

hash散列

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;


int main() {
    int ascii[100000],N;
    vector<int> save;
    memset(ascii,0,sizeof(ascii));
    cin>>N;
    for(int i=0;i<N;++i){
        int temp;
        cin>>temp;
        ascii[temp]++;
        save.push_back(temp);
    }
    for(int i=0;i<save.size();++i){
        if(ascii[save[i]]==1){
            cout<<save[i]<<endl;
            return 0;
        }
    }
    cout<<"None"<<endl;
    return 0;
}

1046

数组的每一项保存第一个node到这一项的node的距离,当要求两点距离时,只需将右边的距离减去左边的距离即可

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

int main() {
    int N,e[100000],sum=0,temp;
    e[0]=0;
    cin>>N;
    for(int i=1;i<=N;++i){
        cin>>temp;
        sum+=temp;
        e[i]=e[i-1]+temp;
    }
    int K,node1,node2;
    cin>>K;
    for(int i=0;i<K;++i){
        cin>>node1>>node2;
        if(node1>node2)swap(node1,node2);
        int len=e[node2-1]-e[node1-1];
        cout<<(len>sum-len?sum-len:len)<<endl;
    }
    return 0;
}

1047

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

/*
sake 缘故 理由 
*/

int main() {
    int N,K,C,id;
    cin>>N>>K;
    vector<string> save[2510];
    string name;
    for(int i=0;i<N;++i){
        cin>>name>>C;
        for(int i=0;i<C;++i){
            cin>>id;
            save[id].push_back(name);
        }
    }
    for(int i=1;i<=K;++i){
        sort(save[i].begin(),save[i].end());
        printf("%d %d\n",i,save[i].size());
        for(int j=0;j<save[i].size();++j){
            printf("%s\n",save[i][j].c_str());
        }
    }
    return 0;
}

1048

#include <iostream>
#include <string.h>
using namespace std;

int main() {
    int N,M,a[1001],input;;
    cin>>N>>M;
    memset(a,0,sizeof(a));
    for(int i=0;i<N;++i){
        cin>>input;
        a[input]++;
    }
    for(int i=0;i<1001;++i){
        if(a[i]){
            a[i]--;
            if(M>i&&a[M-i]!=0){
            cout<<i<<" "<<M-i;
            return 0;
        }
        }
    }
    cout<<"No Solution";
    return 0;
}

1052

链表排序题

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

/*
adjacent 相邻的 
*/

struct node{
    int data;
    int next;
    int add;
};

bool cmp(node a,node b){
    return a.data<b.data;
}

int main() {
    node nodes[100010];
    vector<node> output;
    int N,head,add,next,data;
    scanf("%d %d",&N,&head);
    for(int i=0;i<N;++i){
        scanf("%d %d %d",&add,&data,&next);
        nodes[add]={data,next,add};
    }
    while(head!=-1){
        output.push_back(nodes[head]);
        head=nodes[head].next;
    }
    if(output.size()!=0){
        sort(output.begin(),output.end(),cmp);
        printf("%d %05d\n",output.size(),output[0].add);
    }
    else{
        printf("0 -1");
        return 0;
    }
    for(int i=0;i<output.size()-1;++i){
        printf("%05d %d %05d\n",output[i].add,output[i].data,output[i+1].add);
    }
    printf("%05d %d -1",output[output.size()-1].add,output[output.size()-1].data);
    return 0;
}

1054

stl map的使用

#include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;

/*
pixel 像素 
proportional 成比例的
dominant 占优势的
resolution 分辨率 决心 
*/

map<int,int> save;

int main() {
    int N,M,pixel,dominant;
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            scanf("%d",&pixel);
            if(++save[pixel]>(N*M/2))dominant=pixel;
        }
    }
    cout<<dominant<<endl;
    return 0;
}

1076

图的bfs,关键是stl中queue的使用,首先先把待查询的node入队,然后将node出队,把与node相连的节点依次入队,直到队列为空为止。

#include <iostream>
#include <queue>
#include <string.h>
#include <stdio.h>
using namespace std;
/*
query 询问 
trigger 扳机 
*/
struct node{
    int id;
    int level;
};
int N,L,K; 
vector<int> graph[1010];

int bfs(node query){
    bool vis[1010];
    memset(vis,0,sizeof(vis));
    queue<node> q;
    q.push(query);
    vis[query.id]=true;
    int cnt=0;
    while(!q.empty()){
        node top=q.front();
        q.pop();
        for(int i=0;i<graph[top.id].size();++i){
            if(vis[graph[top.id][i]]==false&&top.level<L){
                vis[graph[top.id][i]]=true;
                node temp={graph[top.id][i],top.level+1};
                q.push(temp);
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    int temp,query;
    cin>>N>>L;
    for(int i=1;i<=N;++i){
        int num;
        cin>>num;
        for(int j=0;j<num;++j){
            cin>>temp;
            graph[temp].push_back(i);
        }
    }
    cin>>K;
    for(int i=0;i<K;++i){
        cin>>query;
        node temp={query,0};
        printf("%d\n",bfs(temp));
    }
    return 0;
}

1078

哈希表的平方探测,关键是index=(x+step*step)%M将step的平方加上原来的下标再取余size,当step的值已经达到size时终止循环

#include <iostream>
#include <string.h>
using namespace std;
/*
collision 冲突
quadratic 二次的 
*/
int M,N,input;
bool hashT[10010];
bool is_prime(int x){
    if(x<=1)return false;
    for(int i=2;i*i<=x;++i){
        if(x%i==0)return false;
    }
    return true;
} 

void insert(int x){
    for(int step=0;step<M;step++){
        int index=(x+step*step)%M;
        if(hashT[index]==0){
            hashT[index]=1;
            cout<<index;
            return;
        }
    }
    cout<<"-"; 
}

int main() {
    memset(hashT,0,sizeof(hashT));
    cin>>M>>N;
    while(!is_prime(M))M++;
    for(int i=0;i<N;++i){
        cin>>input;
        if(i!=0)cout<<" ";
        insert(input);
    }
    return 0;
}

1079

给定一棵树,从根节点开始dfs
另外pow()比自己用for快

#include <iostream>
#include <map>
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
/*
increment 增长 
*/
int N;
double sum=0,P,r;
vector<int> graph[100010];
map<int,int> retailers;
void dfs(int node,int cnt){
    if(graph[node].size()==0){
        double add=1+r/100;
        sum+=retailers[node]*P*pow(add,cnt); 
        return;
    }
    for(int i=0;i<graph[node].size();++i){
        dfs(graph[node][i],cnt+1);
    }
}

int main() {
    scanf("%d%lf%lf",&N,&P,&r);
    int k,temp;
    for(int i=0;i<N;++i){
        scanf("%d",&k);
        for(int j=0;j<k;++j){
            scanf("%d",&temp);
            graph[i].push_back(temp);
        }
        if(k==0){
            scanf("%d",&temp);
            retailers[i]=temp;
        }
    }
    dfs(0,0);
    printf("%.1f",sum);
    return 0;
}

1094

求generation最大的一代,先用二维数组存储这棵树,然后从根节点开始dfs

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int N,M,levels[110];
vector<int> tree[110];
void dfs(int node,int level){
    levels[level]++;
    if(tree[node].size()==0) return;
    for(int i=0;i<tree[node].size();++i){
        dfs(tree[node][i],level+1);
    }
}

int main() {
    int id,k,temp,max_level=1,max_size=1;
    memset(levels,0,sizeof(levels));
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;++i){
        scanf("%d %d",&id,&k);
        for(int j=0;j<k;++j){
            scanf("%d",&temp);
            tree[id].push_back(temp);
        }
    }
    dfs(1,1);
    for(int i=1;i<=100;++i){
        if(levels[i]>max_size){
            max_size=levels[i];
            max_level=i;
        }
    }
    cout<<max_size<<" "<<max_level;
    return 0;
}

1145

哈希表的二次方探测法
注意检索的时候,如果vis[index]=false,要提前return

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int MSize,N,M;
int hashT[10010];
double cnt=0;
bool vis[10010];
bool is_prime(int x){
    if(x<=1)return false;
    for(int i=2;i*i<=x;++i){
        if(x%i==0)return false;
    }
    return true;
}

void insert(int x){
    for(int step=0;step<MSize;step++){
        int index=(x+step*step)%MSize;
        if(!vis[index]){
            vis[index]=true;
            hashT[index]=x;
            return;
        }
    }
    printf("%d cannot be inserted.\n",x);
}

void find(int x){
    for(int step=0;step<=MSize;step++){
        int index=(x+step*step)%MSize;
        cnt++;
        if(hashT[index]==x||vis[index]==false){
            return;
        }
    }
}

int main() {
    memset(vis,0,sizeof(vis));
    int input;
    cin>>MSize>>N>>M;
    while(!is_prime(MSize))MSize++;
    for(int i=0;i<N;++i){
        cin>>input;
        insert(input);
    }
    for(int i=0;i<M;++i){
        cin>>input;
        find(input);
    }
    printf("%.1f",cnt/M);
    return 0;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345