PTA L2一些题目

L2-014 列车调度 - 团体程序设计天梯赛-练习集

样例是怎么来的呢？通过题目我们知道每一条轨道的车牌号必须是依次递减的。那么，我们如果让每条轨道尽可能长就能保证轨道数最少------也就是说，我们要尽可能的找最长降序序列。

但是1e5数据量还是太大了，暴力找会超时。

注意到，找最长降序序列的时候，我们是8-4-2-1、5-3、9-6、7，现在这个数能放那个就放哪个，尽可能往前面找，如果都放不了就新开一个

于是，考虑二分，找现在所有轨道队尾车牌号大于当前车牌号的那条。可以分析出队尾车牌号是单调的

int n,a[N];
vector <int> vec;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int p = lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
        if(p==vec.size()) vec.pb(a[i]);
        else vec[p] = a[i];
    }
    cout<<vec.size()<<endl;
}

L2-015 互评成绩 - 团体程序设计天梯赛-练习集

模拟水题，大一在学c的时候就做过（）

int n,k,m;
vector  <double> ans;
void solve()
{
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        vector <double> tmp;
        for(int j = 0;j<k;j++)
        {
            double x;
            cin>>x;
            tmp.push_back(x);
        }
        sort(tmp.begin(),tmp.end());
        double sum=0;
        for(int j=1;j<=k-2;j++)
        {
            sum+=tmp[j];
        }
        ans.push_back(sum/(1.0*(k-2)));
    }
    sort(ans.begin(),ans.end());
    for(int i=ans.size()-m;i<ans.size();i++)
    {
        printf("%.3f",ans[i]);
        if(i<ans.size()-1) cout<<" ";
    }
}

L2-016 愿天下有情人都是失散多年的兄妹 - 团体程序设计天梯赛-练习集

看似并查集实则不然，是类似于树求深度

给出两个点后，我们先把其中一个的所有祖先全部找到，然后再找另一个的祖先，如果这个后者的其中一个祖先在前者的祖先中被访问到了，且不超过5步的话，那麽就是有血缘关系的

坑点是要记录一下父母的性别（）

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    //ed[IDX].w = w;
}
int n;
bool sx[N];
map <int,bool> vis;
bool dfs(int now,int st)
{
    if(st>5)
    {
        return 0;
    }
    bool f=0;
    if(vis[now]==1)
    {
        return 1;
    }
    vis[now]=1;
    for(int i=head[now];i;i=ed[i].ne)
    {
        int t = ed[i].t;
        f=dfs(t,st+1);
        if(f==1) break;
    }
    return f;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,c,d;
        char b;
        cin>>a>>b>>c>>d;
        sx[a] = (b=='M');
        if(c!=-1) add(a,c),sx[c]=1;//傻逼
        if(d!=-1) add(a,d);
    }
    int q;
    cin>>q;

    while(q--)
    {
        int a,b;
        vis.clear();
        cin>>a>>b;
        if(sx[a]==sx[b])
        {
            cout<<"Never Mind"<<endl;
            continue;
        }
        dfs(a,1);
        if(dfs(b,1))
        {
            cout<<"No"<<endl;
        }
        else
        {
            cout<<"Yes"<<endl;
        }
    }
}

L2-017 人以群分 - 团体程序设计天梯赛-练习集

水题，排个序，然后前缀和，左右两部分做差就行

int n,a[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i] += a[i-1];
    }
    printf("Outgoing #: %d\n",n/2+n%2);
    printf("Introverted #: %d\n",n/2);
    printf("Diff = %d",a[n]-a[n/2]*2);
}

L2-019 悄悄关注 - 团体程序设计天梯赛-练习集

模拟水题

int n,m;
typedef pair<string,int>PSI;
map<string ,int> hs;
PSI a[N];
bool cmp(string a,string b)
{
    return a<b;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        hs[s]++;
    }
    cin>>m;
    int ave=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].fi>>a[i].se;
        ave+=a[i].se;
    }
    ave/=m;
    vector<string>ans;
    for(int i=1;i<=m;i++)
    {
        if(hs[a[i].fi]==0 && a[i].se>ave)
        {
            ans.pb(a[i].fi);
        }
    }
    sort(ans.begin(),ans.end(),cmp);
    if(ans.size()==0)
    {
        cout<<"Bing Mei You"<<endl;
    }
    else
    {
        for(auto it : ans)
        {
            cout<<it<<endl;
        }
    }
}

L2-020 功夫传人 - 团体程序设计天梯赛-练习集

建出一棵树，叶子节点的权值要在削减传下来后乘倍数。注意精度

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    //ed[IDX].w = w;
}
int n;
double k1,r;
double fd[N],wg[N];
void dfs(int now,double v)
{
    if(fd[now]>0)
    {
        wg[now] = v*fd[now];
        return ;
    }
    wg[now] = v;
    for(int i=head[now];i;i=ed[i].ne)
    {
        int t = ed[i].t;
        dfs(t,v*(100.0-r)/100.0);
    }
}
void solve()
{
    cin>>n>>k1>>r;
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        if(k==0)
        {
            cin>>fd[i];
        }
        else
        {
            for(int j=1;j<=k;j++)
            {
                int x;
                cin>>x;
                add(i,x);
            }
        }
    }

    dfs(0,k1);
    double sum=0;
    for(int i=0;i<n;i++)
    {
        if(fd[i]>0)
        {
            sum+=wg[i];
        }
    }
    printf("%.0f",floor(sum));
}

L2-021 点赞狂魔 - 团体程序设计天梯赛-练习集

模拟

int n,a;
string name[105];
long long sum[105],ave[105];
int srank[105],averank[105];
int cmp1(long long x,long long y)
{
    if(sum[x]!=sum[y])
    {
        return sum[x]>sum[y];
    }
    else if(ave[x]!=ave[y])
    {
        return ave[x]<ave[y];
    }
}
set <int> s;
int main()
{
    int n,k;
    int i,j;
    long long total;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>name[i]>>k;
        srank[i]=i;averank[i]=i;
        total=0;
        for(j=0;j<k;j++)
        {
            cin>>a;s.insert(a);
        }

        sum[i]=s.size();
        ave[i]=k;
        s.clear();
    }
    sort(srank+1,srank+n+1,cmp1);
    //sort(averank+1,averank+n+1,cmp1);
    if(n>=3)
    {
        for(i=1;i<=2;i++)
        {
            cout<<name[srank[i]]<<' ';
        }
        cout<<name[srank[3]]<<endl;
    }
    else
    {
        for(i=1;i<=3;i++)
        {
            if(i<=n)cout<<name[srank[i]]<<' ';
            else
            {
                if(i!=3)
                cout<<'-'<<' ';
            }
            if(i==3)
            {
                cout<<'-'<<endl;
            }
        }
    }
}

L2-022 重排链表 - 团体程序设计天梯赛-练习集

很有意思的一道题，有了上次的教训我们应在所有结点都输入完后再处理前驱。

使用一个数组记录每个地址在当前链表中的位置，每次插入只需要从两边往中间交换即可，可以证明每次插入不会影响其他节点的相对位置

int n,k1;
int kv[N],ne[N],pre[N];
int p[N];
int cnt ;
void dfs(int now,int idx)//处理前驱
{
    if(now == -1) return;
    cnt = max(cnt,idx);
    pre[ne[now]] = now;
    p[idx] = now;
    dfs(ne[now],idx+1);
}
void ist(int a,int b)//b插到a前面
{
    int ka = p[a];
    int kb = p[b];
    if(pre[ka]==-1)
    {
        k1 = kb;
    }
    ne[pre[kb]] = ne[kb];
    ne[pre[ka]] = kb;
    pre[ka] = kb;
    pre[kb] = pre[ka];
    ne[kb] = ka;
}
void dfs1(int now)输出新链表
{
    if(now == -1)
    {
        return ;
    }
    //cout<<now<<' '<<kv[now]<<' '<<ne[now]<<endl;
    printf("%05d %d ",now,kv[now]);
    if(ne[now]!=-1)
    {
        printf("%05d\n",ne[now]);
    }
    else
    {
        printf("-1\n");
    }
    dfs1(ne[now]);
}
void solve()
{
    cin>>k1>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        kv[a] = b;
        ne[a] = c;
    }
    pre[k1] = -1;
    dfs(k1,1);
    int l=1,r=cnt;
    //cout<<cnt<<endl;
    while(l<r)
    {
        //cout<<l<<' '<<r<<endl;
        //cout<<p[l]<<' '<<p[r]<<endl;
        ist(l,r);
        //dfs(k1,1);
        //dfs1(k1);
        l++,r--;
        //cout<<endl;
    }
    dfs1(k1);
}

L2-023 图着色问题 - 团体程序设计天梯赛-练习集

使用链式前向星，实际上建单向图就可以，无向图疑似会tle（）。

对于每个方案，遍历每一个点的相邻点，只要有一组有相同颜色就不行

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    //ed[IDX].w = w;
}
int v,e,k;
int c[N];
void solve()
{
    cin>>v>>e>>k;
    for(int i=1;i<=e;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    int q;cin>>q;
    set<int>st;
    while(q--)
    {
        st.clear();
        for(int i=1;i<=v;i++) cin>>c[i],st.emplace(c[i]);
        if(st.size()!=k)
        {
            cout<<"No"<<endl;
            continue;
        }
        bool f=1;
        for(int i=1;i<=v;i++)
        {
            for(int j=head[i];j;j=ed[j].ne)
            {
                int t=ed[j].t;
                if(c[i] == c[t])
                {
                    f=0;
                    break;
                }
            }
            if(f==0) break;
        }
        cout<<(f?"Yes":"No")<<endl;
    }
}

L2-024 部落 - 团体程序设计天梯赛-练习集

？并查集板子

统计人数用个set存就行。每一个圈子的每一个人都只需要与第一个人合并即可

int FA[N];
int _fi(int x){return (FA[x] == x) ? x : FA[x] = _fi(FA[x]);}
void uni(int x, int y){int xx = _fi(x), yy = _fi(y);if (xx != yy) FA[xx] = yy;}
int n;
set<int>st;
int a[N];
void solve()
{
    for(int i=1;i<=10000;i++)
    {
        FA[i] = i;
    }
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>a[j];
            uni(a[j],a[1]);
            st.emplace(a[j]);
        }
    }
    int q,cnt=0;
    for(int i=1;i<=st.size();i++)
    {
        if(_fi(i) == i )
        {
            cnt++;
        }
    }
    cout<<st.size()<<' '<<cnt<<endl;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        if(_fi(a) == _fi(b))
        {
            cout<<"Y"<<endl;
        }
        else
        {
            cout<<"N"<<endl;
        }
    }
}

L2-025 分而治之 - 团体程序设计天梯赛-练习集

跟上面图着色问题差不多，这里只需要判断每个还存在的点有没有相邻点即可

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    //ed[IDX].w = w;
}
int n,m,k;
map <int ,bool> hs;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    cin>>k;
    while(k--)
    {
        hs.clear();
        int u;
        cin>>u;
        for(int i=1;i<=u;i++)
        {
            int x;
            cin>>x;
            hs[x] = 1;
        }
        bool f = 1;
        for(int i=1;i<=n;i++)
        {
            if(!hs[i])
            {
                for(int j=head[i];j;j=ed[j].ne)
                {
                    int t = ed[j].t;
                    if(!hs[t])
                    {
                        f=0;
                        break;
                    }
                }
                if(!f) break;
            }
        }
        cout<<(f?"YES":"NO")<<endl;
    }
}

L2-026 小字辈 - 团体程序设计天梯赛-练习集

建树求高度

void add(int s,int t)
{
    ed[++idx].ne = head[s];
    ed[idx].t = t;
    head[s] = idx;
}
int n;
int a[N];
int deep=0,dp[N],root;
void dfs(int now,int d)
{
    dp[now] = d;
    deep = max(deep,d);
    for(int i=head[now];i;i=ed[i].ne)
    {
        int t = ed[i].t;
        dfs(t,d+1);
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==-1)
        {
            root = i;
        }
        else
            add(a[i],i);
    }
    dfs(root,1);
    cout<<deep<<endl;
    vector <int> ans;
    for(int i=1;i<=n;i++)
    {
        if(dp[i] == deep)
        {
            ans.push_back(i);
        }
    }
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i];
        if(i<ans.size()-1) cout<<' ';
    }
}

L2-027 名人堂与代金券 - 团体程序设计天梯赛-练习集

模拟，最后输出的时候注意一下名次就行

int n,g,k;
typedef pair<string,int> PSI;
vector <PSI> vec,ans;
int sum = 0;
bool cmp(PSI x,PSI y)
{
    if(x.se==y.se)
    {
        return x.fi<y.fi;
    }
    else
    {
        return x.se>y.se;
    }
}
void solve()
{
    cin>>n>>g>>k;
    for(int i=1;i<=n;i++)
    {
        string s;
        int sc;
        cin>>s>>sc;
        vec.pb({s,sc});
        if(sc>=60 && sc<g) sum+=20;
        else if(sc>=g) sum+=50;
    }
    cout<<sum<<endl;
    sort(vec.begin(),vec.end(),cmp);
    int p=1,cnt=1;
    for(int i=0;i<vec.size();i++)
    {
        cout<<p<<' '<<vec[i].fi<<' '<<vec[i].se<<endl;
        cnt++;
        if(i<vec.size()-1&&vec[i+1].se<vec[i].se) p=cnt;
        if(p>k) break;
    }
}

L2-028 秀恩爱分得快 - 团体程序设计天梯赛-练习集

很牛逼的模拟题，光是数据处理就很头疼。用邻接表（？）存一下每两个点之间的亲密度

后面就按题意处理即可

int n,m,a,b;
double mp[1005][1005];
bool sx[N];
int kk[N];
typedef pair<int,double> PID;
vector <PID> va,vb;
bool cmp(PID x,PID y)
{
    if(abs(x.se-y.se)<1e-9)
    {
        return x.fi<x.fi;
    }
    else
    {
        return x.se>y.se;
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int k;
        cin>>k;
        double add = 1.0/k;
        for(int j=1;j<=k;j++)
        {
            string s;
            cin>>s;
            int id = abs(stoi(s));
            kk[j] = id;
            if(s[0] != '-')
            {
                sx[id] = 1;
            }
        }
        for(int j=1;j<=k;j++)
        {
            for(int jj=j+1;jj<=k;jj++)
            {
                mp[kk[j]][kk[jj]] += add;
                mp[kk[jj]][kk[j]] += add;
            }
        }
    }
    string sa,sb;
    cin>>sa>>sb;
    a = abs(stoi(sa));
    b = abs(stoi(sb));
    sx[a] = (sa[0]!='-');
    sx[b] = (sb[0]!='-');
    double now = mp[a][b];
    double topa=0,topb=0;
    for(int i=0;i<n;i++)
    {
        if(sx[a]!=sx[i])
        {
            va.pb({i,mp[a][i]});
            topa = max(topa,mp[a][i]);
        }
        if(sx[b]!=sx[i])
        {
            vb.pb({i,mp[b][i]});
            topb = max(topb,mp[b][i]);
        }
    }
    if(topa == topb && topa == now)
    {
        if(sx[a]==0)
        cout<<'-'<<a<<' '<<b<<endl;
        else
        {
            cout<<a<<' '<<"-"<<b<<endl;
        }
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(mp[a][i]==topa && sx[i]!=sx[a])
        {
            cout<<(sx[a]?"":"-")<<a<<' '<<(sx[i]?"":"-")<<i<<endl;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(mp[b][i]==topb && sx[i]!=sx[b])
        {
            cout<<(sx[b]?"":"-")<<b<<' '<<(sx[i]?"":"-")<<i<<endl;
        }
    }
}

L2-029 特立独行的幸福 - 团体程序设计天梯赛-练习集

写懵了，这里代码看个乐子就行，纯翻译题面。数据量只有1000，直接暴力

int a,b;
map<int,int>hs,pl;
bool prime(int x)
{
    if(x==1) return 0;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int fun(int x)
{
    int res = 0,y=x;
    while(y)
    {
        int tmp = y%10;
        res+=tmp*tmp;
        y/=10;
    }
    return res;
}
void dfs(int x)
{
    //cout<<x<<endl;
    int res = x,cnt=1;
    int y = x;
    int f = 1;
    map <int,bool> hss;
    hss[x] = 1;
    while(res!=1)
    {
        //cout<<res<<endl;
        int tmp = fun(res);
        cnt++;
        res = tmp;
        if(hss[res] == 1)
        {
            f=0;
            break;
        }
        hss[res] = 1;
    }
    if(res==1)
    {
        pl[x]=--cnt;
        hs[x]=0x3f3f3f3f;
        res = x;
        while(res!=1)
        {
            int tmp = fun(res);
            res = tmp;
            hs[res] = 1;
        }
        return ;
    }
    if(f==0)
    {
        hs[x] = -1;
        res = fun(x);
        while(hs[res] != -1)
        {
            hs[res]=-1;
            int tmp = fun(res);
            res = tmp;
        }
    }
}
void solve()
{
    cin>>a>>b;
    int f = 0;
    for(int i=a;i<=b;i++)
    {
        //cout<<prime(i)<<endl;
        if(hs[i] == -1) continue;
        if(hs[i] == 0x3f3f3f3f)
        {
            //cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;
            //f=1;
        }
        else if(hs[i]==0)
            dfs(i);
    }
    for(int i=a;i<=b;i++)
    {
        if(hs[i] == -1) continue;
        if(hs[i] == 0x3f3f3f3f)
        {
            cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;
            f=1;
        }
    }
    if(!f) cout<<"SAD"<<endl;
}

L2-031 深入虎穴 - 团体程序设计天梯赛-练习集

建树求高度

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    //ed[IDX].w = w;
}
int n,rd[N];
int ans,ansd=0;
void dfs(int now,int dpp)
{
    if(dpp>ansd)
    {
        ansd=dpp;
        ans = now;
    }
    for(int i=head[now];i;i=ed[i].ne)
    {
        dfs(ed[i].t,dpp+1);
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int x;
            cin>>x;
            add(i,x);
            rd[x]++;
        }
    }
    int rt;
    for(int i=1;i<=n;i++)
    {
        if(rd[i]==0)
        {
            rt=i;
            break;
        }
    }
    dfs(rt,1);
    cout<<ans<<endl;
}

L2-032 彩虹瓶 - 团体程序设计天梯赛-练习集

用stack模拟就行，栈满了也不要停止输入（）。不要忘记如果栈还有东西就尽量往外拿

int n,m,k;
stack<int> st;
int now;
void solve()
{
    cin>>n>>m>>k;
    while(k--)
    {
        while(!st.empty())
        {
            st.pop();
        }
        bool f = 0;
        now = 1;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            //cout<<now<<endl;
            if(x == now)
            {
                now++;
                while(!st.empty()&&st.top()==now)
                {
                    st.pop();
                    now++;
                }
            }
            else
            {
                if(st.size()==m)
                {
                    f=0;
                    continue;
                }
                st.push(x);
            }
        }
        while(!st.empty()&&st.top()==now)
        {
            st.pop();
            now++;
        }
        if(now == n+1) f=1;
        cout<<((f==1)?"YES":"NO")<<endl;
    }
}

L2-033 简单计算器 - 团体程序设计天梯赛-练习集

栈入门题

stack <int> s1;
stack <char> s2;
int n;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s1.push(x);
    }
    for(int i=1;i<n;i++)
    {
        char c;
        cin>>c;
        s2.push(c);
    }
    while(s2.size())
    {
        int na,nb;
        na = s1.top();
        s1.pop();
        nb = s1.top();
        s1.pop();
        char op = s2.top();
        s2.pop();
        if(op=='+')
        {
            s1.push(na+nb);
        }
        else if(op =='-')
        {
            s1.push(nb-na);
        }
        else if(op == '*')
        {
            s1.push(na*nb);
        }
        else
        {
            if(na == 0)
            {
                cout<<"ERROR: "<<nb<<'/'<<na<<endl;
                return ;
            }
            else
            {
                s1.push(nb/na);
            }
        }
    }
    cout<<s1.top()<<endl;
}

L2-035 完全二叉树的层序遍历 - 团体程序设计天梯赛-练习集

建树之后，使用bfs层次遍历就行了

int n,hx[N];
struct TREE
{
    int v,l,r;
}tr[N];
int hdx;
int build(int idx)
{
    if(idx>n)
        return 0;
    tr[idx].v = hx[hdx];
    hdx--;
    tr[idx].r = build(idx*2+1);
    tr[idx].l = build(idx*2);
    return idx;
}
vector <int> ans;
void bfs(int rt)
{
    queue <int> q;
    q.push(rt);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        ans.pb(tr[now].v);
        if(tr[now].l!=0)
        {
            q.push(tr[now].l);
        }
        if(tr[now].r!=0)
        {
            q.push(tr[now].r);
        }
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>hx[i];
    }
    hdx=n;
    int rt = build(1);
    bfs(rt);
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<(i<ans.size()-1?" ":"\n");
    }
}