APCS 2016/3 題解

成績指標

題目

成績指標

核心

排序、條件判斷

思路

容易!

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int student[20];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",student+i);
    sort(student,student+n);
    int best=101,worst=-1;
    for(int i=0;i<n;i++)
    {
        if(student[i]<60&&student[i]>worst) worst=student[i];
        if(student[i]>=60&&student[i]<best) best=student[i];
    }
    for(int i=0;i<n;i++) printf("%d ",student[i]);
    if(worst==-1) printf("\nbest case\n");
    else printf("\n%d\n",worst);
    if(best==101) printf("worst case\n");
    else printf("%d\n",best);
}

矩陣轉換

題目

矩陣轉換

核心

模擬、二維陣列

思路

旋轉的部分比較需要思考，用tmp暫存。

#include<bits/stdc++.h>
using namespace std;
int r,c,m,arr[10][10],tmp[10][10];
vector<int>ops;
int main(){
    while(cin>>r>>c>>m)
    {
        for(int i=0;i<r;i++)for(int j=0;j<c;j++)cin>>arr[i][j];
        ops.assign(m,0);
        for(int i=0;i<m;i++)cin>>ops[i];
        while(ops.size())
        {
            if(ops.back()==1)
            {
                for(int i=0;i<r/2;i++)for(int j=0;j<c;j++)swap(arr[i][j],arr[r-i-1][j]);
            }
            else
            {
                for(int i=0;i<r;i++)for(int j=0;j<c;j++)tmp[i][j]=arr[i][j];
                swap(r,c);
                for(int i=0;i<r;i++)for(int j=0;j<c;j++)arr[i][j]=tmp[j][r-1-i];
            }
            ops.pop_back();
        }
        cout<<r<<" "<<c<<"\n";
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)cout<<arr[i][j]<<(j==c-1?"":" ");
            cout<<"\n";
        }
    }
}

線段覆蓋長度

題目

線段覆蓋長度

核心

排序、貪心

思路

取聯集的意思。
依照每一條線段的左端由小到大排序。s為目前線段的左端，t為右端，若下一個線段和此線段無重疊，則計算長度後更新s,t為下一線段，若有重疊，則取兩線段的最右端。最後別忘再計算一次。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
pair<int,int> seq[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&seq[i].first,&seq[i].second);
    long long sum=0;
    int s=-1,t=-1;
    sort(seq,seq+n);
    for(int i=0;i<n;i++)
    {
        if(t<seq[i].first) sum+=t-s,s=seq[i].first,t=seq[i].second;
        else t=max(t,seq[i].second);
    }
    sum+=t-s;
    printf("%lld",sum);
}

血緣關係

題目

血緣關係

核心

tree、dfs

思路

dfs過程中順便計算，每一個節點記錄他的最高和第二高子樹高度，相加便是有經過此節點的最長距離，從這些最長距離中找最大值就行。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int parent[N];
vector<int> child[N];
int ans=0;
int dfs(int v)
{
    int maxRank=0,secondRank=0;
    for(int u:child[v])
    {
        int p=dfs(u)+1;
        if(p>=maxRank) secondRank=maxRank,maxRank=p;
        else if(p>secondRank) secondRank=p;
    }
    ans=max(ans,maxRank+secondRank);
    return maxRank;
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(parent,-1,sizeof(parent));
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&v,&u);
        parent[u]=v;
        child[v].push_back(u);
    }
    for(int i=0;i<n;i++)
    {
        if(parent[i]==-1) dfs(i);
    }
    printf("%d",ans);
}