PTA部分题解

什么？！我居然在老师上课的时候做题？
有一种必不可能一遍过的感觉…坑多

---

练习3-2016年天梯赛决赛题集

7-1 正整数A+B (15分)

Description

收入两个数字，输出和，如果数字不符合要求输出?，和也为?

Solution

这题坑好多..我服了
首先0不算正整数，范围为[1,1000]的意思不是只会有这个范围的数，而是这个范围的数才算合法
会有空字符串…
PTA ban了gets,要用cin.getline

Code

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1005;
char a[N];

int toNum(char* a, int l) {
    if(l==0) return -1;
    int x=0;
    for(int i=0; i<l; i++) {
        if(a[i]>'9' || a[i]<'0') return -1;
        else x=x*10+a[i]-'0';
        if(x>1000) return -1;
    }
    return x==0?-1:x;
}
int main() {
    cin.getline(a, N);
    int l=strlen(a), n1, n2;
    for(int i=0; i<l; i++) if(a[i]==' ') {
        n1 = toNum(a, i);
        n2 = toNum(a+i+1, l-i-1);
        break;
    }
    if(n1==-1 || n2==-1) {
        if(n1==-1) cout << "?";
        else cout << n1;
        cout << " + ";
        if(n2==-1) cout << "?";
        else cout << n2;
        cout << " = ?" << endl;
    } else {
        cout << n1 << " + " << n2 << " = " << n1+n2 << endl;
    }
    return 0;
}

7-2 I Love GPLT (5分)

Description

竖着输出I Love GPLT

Solution

Code

#include <cstdio>
#include <cstring>
int main() {
    char s[]="I Love GPLT";
    int l=strlen(s);
    for(int i=0; i<l; i++) printf("%c\n", s[i]);
    return 0;
}

7-3 出租 (20分)

Description

输入一个手机号，输出一个生成方式，如图所示，要求arr降序

Solution

Code

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

char a[100];
int c[11];
int arr[11];
int idx[11];

int main() {
    cin >> a;
    int l=11;
    for(int i=0; i<l; i++) c[a[i]-'0']++;
    for(int i=9;i>=0;i--) if(c[i]) arr[++arr[0]]=i,idx[i]=arr[0]-1;
    cout << "int[] arr = new int[]{";
    for(int i=1; i<=arr[0]; i++)
        if(i==arr[0]) cout << arr[i]; else cout << arr[i] << ","; 
    cout << "};" << endl;
    cout << "int[] index = new int[]{";
    for(int i=0; i<l; i++) 
        if(i==l-1) cout << idx[a[i]-'0'];
        else cout << idx[a[i]-'0'] << ",";
    cout << "};";
    return 0;
}

7-4 判断素数 (10分)

Description

输入$N,N\leqslant 10$个小于$2^{31}$的数，判断素数

Solution

懒得写了，直接$\sqrt {N}$判断就行了

Code

略

7-5 是不是太胖了 (5分)

Description

算数

Solution

一行代码的事

Code

略

7-6 一帮一 (15分)

Description

算数

Solution

一行代码的事

Code

略

7-7 到底是不是太胖了 (10分)

7-8 Left-pad (20分)

7-9 红色警报 (25分)

Description

给一个图，$N$个节点，$M$条边，其中有$K$个节点失去，问每个节点是否会改变连通性。$K\leqslant N\leqslant 500, M\leqslant 500$

Solution

这题还可以做一下，倒序加点，用并查集维护连通性
注意连得时候要小连大这样有顺序一些…不然就能连出一个环…
这题好像正序暴力模拟也能做？

Code

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

#define N 505
#define M 5005

int n, m, k, gmov;
int f[N], d[N], b[N], ra[N];
vector<int> g[N];

// int find(int x) { return f[x]=(f[x]==x?x:find(f[x])); }
int find(int x) {
    int t=x;
    while(f[x]!=x) { x=f[x]; }
    return f[t]=x;
}
void uni(int x, int y) {
    int fx=find(x), fy=find(y);
    if(fx!=fy) { 
        if(fx<fy) f[fy]=fx;
        else f[fx]=fy;
    }
}
int main() {
    cin >> n >> m;
    for(int i=0; i<=n; i++) f[i]=i;
    for(int i=1; i<=m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
    for(int i=1; i<=k; i++) { cin >> d[i]; b[d[i]]=1; }
    for(int i=0; i<n; i++) if(!b[i]) {
        for(int j=0; j<g[i].size(); j++) if(!b[g[i][j]]) {
            uni(i, g[i][j]);
        }
        gmov=1;
    }
    for(int i=k; i; i--) {
        int x=d[i], y=-1;
        for(int j=0; j<g[x].size(); j++) if(!b[g[x][j]]) {
            if(y==-1) y=find(g[x][j]);
            else {
                if(y!=find(g[x][j])) ra[i]=1;
            }
        }
        if(y!=-1) uni(x, y);
        b[x]=0;
    }
    for(int i=1; i<=k; i++) {
        if(ra[i]) cout << "Red Alert: City "<< d[i] << " is lost!" << endl;
        else cout << "City " << d[i] << " is lost." << endl;
    }
    if(!gmov) puts("Game Over.");
    return 0;
}

7-10 列车调度 (25分)

Description

按顺序的一堆火车，要递减的顺序出站，问最少需要多少车道 $N\leqslant 10^5$

Solution

贪心
首先贪心是对的，一开始我还想会不会把最大的直接开过去不占用空地，但是其实这样的结果还是和全停好了最后开过去是一样的，因为毕竟最大的一定会占一个车道开过去，那么后面的自然都可以排在它后面。
贪心是让大于他的最小，一开始写了一个简单的测试一下，发现不对，让我很疑惑，原来是反着给的顺序/呲牙笑 /抱拳
最后set优化一下就ok了，复杂度$O(n\log n)$
ps. 我人傻了，注释掉的那行的写法会被卡常数？

Code

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

const int N = 100050;

int n, k;
int a[N];
set<int> s;
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++) {
        int x=a[i];
//		set<int>::iterator t=upper_bound(s.begin(), s.end(), x);
        set<int>::iterator t=s.upper_bound(x);
        if(t==s.end()) { k++; s.insert(x); }
        else { s.erase(t); s.insert(x); }
    }
    cout << k << endl;
    return 0;
}

7-11 互评成绩 (25分)

Description

算成绩，$K$个成绩中去掉最大最小，取平均，算前$M$个，$N\leqslant 10^4,K\leqslant 10, M\leqslant 20$

Solution

这么水的题居然25pts…
随便sort一下就好了

Code

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

const int N = 10050;

int n, k, m;

double a[N], b[N];

int main() {
    cin >> n >> k >> m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=k; j++) cin >> b[j];
        sort(b+1, b+1+k);
        double sum=0;
        for(int j=2; j<k; j++) sum+=b[j];
        a[i]=sum/(k-2);
    }
    sort(a+1, a+n+1);
    for(int i=n-m+1; i<=n; i++) {
        if(i==n) printf("%.3lf", a[i]);
        else printf("%.3lf ", a[i]);
    }
    return 0;
}

7-12 愿天下有情人都是失散多年的兄妹 (25分)

Description

查询5代是否有重复的祖先$N\leqslant 10^4$

Solution

坑：输入格式透漏了父母的性别…所以可能会查询祖先..还可能查询未出现的人..所以性别不能用01
ps. 事实证明你儿子才是你爹x
pps. 我在第五层，老千层饼了
ppps. dk当然是dick的意思233
pppps. 玄学复杂度都能过

Code

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

const int N = 100050;

int n, k;
int dk[N];
vector<int> g[N];
int vis[N];

void dfs(int x, int d) {
    vis[x]=1;
    if(d==5) return;
    for(int i=0; i<g[x].size(); i++) dfs(g[x][i], d+1);
}
int dfs2(int x, int d) {
    if(vis[x]) return 1;
    if(d==5) return 0;
    int res=0;
    for(int i=0; i<g[x].size(); i++) res|=dfs2(g[x][i], d+1);
    return res;
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        int x, u, v; char c;
        cin >> x >> c >> u >> v;
        if(c=='M') dk[x]=1; else dk[x]=2;
        if(u!=-1) g[x].push_back(u), dk[u]=1;
        if(v!=-1) g[x].push_back(v), dk[v]=2;
    }
    cin >> k;
    for(int i=1; i<=k; i++) {
        memset(vis, 0, sizeof(vis));
        int x, y;
        cin >> x >> y;
        if(dk[x]==dk[y]) {
            puts("Never Mind");
            continue;
        }
        dfs(x, 1);
        if(dfs2(y, 1)) puts("No");
        else puts("Yes");
    }
    return 0;
}

7-13 是否完全二叉搜索树 (30分)

Description

给一个序列建立二叉搜索树，判断是否是完全二叉树

Solution

我居然忘记了完全二叉树的定义..我以为所有节点的子节点都是满的就ok..
直接强行标号，左节点就是f<<1，右节点就是f<<1|1，最后判断最大编号是否是n就完事了，注意处理根

Code

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

const int N = 100;

int n;
int rt, mxs, lc[N], rc[N], num[N];

void insert(int x) {
    if(!rt) { rt=1, mxs=1, num[rt]=x; return; }
    int t=rt, f=0;
    while(t!=0) {
        if(num[t]<x) f=t, t=lc[t];
        else f=t, t=rc[t];
    }
    int tt;
    if(num[f]<x) tt=lc[f]=f<<1;
    else tt=rc[f]=f<<1|1;
    num[tt]=x, mxs=max(mxs, tt);
}
void bfs() {
    queue<int> q;
    vector<int> t;
    q.push(rt);
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        t.push_back(x);
        if(lc[x]) q.push(lc[x]);
        if(rc[x]) q.push(rc[x]);
    }
    for(int i=0; i<t.size(); i++) printf("%d%c", num[t[i]], " \n"[i==t.size()-1]);
    if(mxs!=n) puts("NO");
    else puts("YES");
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        int x;
        cin >> x;
        insert(x);
    }
    bfs();
    return 0;
}

7-14 直捣黄龙 (30分)

Description

从己方大本营打到敌方大本营，要求路径最短，经过城镇最多，敌方兵力最强
输出路径条数，路径，敌方兵力 $N\leqslant 200$

Solution

SPFA
多条件最短路，深搜剪枝找路径条数
我真nmb人傻了，第一个要输出的居然不是经过的城镇数而是路径条数？？？我输出经过的城镇数居然过了两个点？？？我一直在找SPFA的错我是真的服了

Code

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

const int N = 250;

int n, k, cnt, s, t, tot;
map<string, int> mp;
map<int, string> rmp; 
struct Edge { int v, w; };
vector<Edge> g[N];
int zs[N], tzs[N];
int b[N];
int d[N], jg[N], vl[N], bf[N];

void AddEdge(int u, int v, int w) {
    g[u].push_back((Edge){ v, w });
    g[v].push_back((Edge){ u, w });
}
int idx(string x) {
    if(!mp.count(x)) mp[x]=++cnt, rmp[cnt]=x;
    return mp[x];
}

void DFS(int x, int dis) {
    if(dis>d[x] || dis>d[t]) return;
    if(x==t) { if(d[t]==dis) tot++; return; }
    for(int i=0; i<g[x].size(); i++) if(d[g[x][i].v]==d[x]+g[x][i].w) {
        DFS(g[x][i].v, dis+g[x][i].w);
    }
}

void SPFA(int s, int t) {
    queue<int> q;
    memset(b, 0, sizeof(b));
    memset(d, 0x3f, sizeof(d));
    memset(jg, 0, sizeof(d));
    memset(tzs, 0, sizeof(d));
    q.push(s); b[s]=1, d[s]=0, jg[s]=0, tzs[s]=zs[s];
    for(;!q.empty();) {
        int x=q.front(); q.pop(); // cout << x << endl;
        for(int i=0; i<g[x].size(); i++) {
            int v=g[x][i].v;
            int fl=0;
            
            if(d[v]>d[x]+g[x][i].w) fl=1;
            else if(d[v]==d[x]+g[x][i].w && jg[v]<jg[x]+1) fl=1;
            else if(d[v]==d[x]+g[x][i].w && jg[v]==jg[x]+1 && tzs[v]<=tzs[x]+zs[v]) fl=1;
            
            if(fl) {
                d[v]=d[x]+g[x][i].w;
                jg[v]=jg[x]+1;
                tzs[v]=tzs[x]+zs[v];
                if(!b[v]) q.push(v); b[v]=1; bf[v]=x;
            }
        } b[x]=0;
    }
    vector<int> rd;
    for(int tp=t; tp!=s; tp=bf[tp]) rd.push_back(tp);
    rd.push_back(s);
    for(int i=rd.size()-1; ~i; i--) {
        if(i) cout << rmp[rd[i]] << "->";
        else cout << rmp[rd[i]] << endl; 
    }
//	for(int i=0; i<g[4].size(); i++) cout << rmp[g[4][i].v] << endl;
    tot=0;
    DFS(s, 0);
    cout << tot << " " << d[t] << " " << tzs[t] << endl;
//	for(int i=1; i<=cnt; i++) cout << rmp[i] << " " << d[i] << " " << jg[i] << " " << tzs[i] << endl;
}

int main() {
    string a, b;
    cin >> n >> k >> a >> b;
    s=idx(a), t=idx(b);
    for(int i=1; i<n; i++) {
        string nm; int x, y;
        cin >> nm >> y;
        x=idx(nm); zs[x]=y;
    }
    for(int i=1; i<=k; i++) {
        int x, u, v;
        cin >> a >> b >> x;
        u=idx(a), v=idx(b);
        AddEdge(u, v, x);
    }
    // cout << "qwq" << endl;
    SPFA(s, t);
    return 0;
}