寒假刷题13天

PTA甲级

1082 Read Number in Chinese

字符串处理，恶心

#include<iostream>
#include<algorithm>

using namespace std;

string num[10] = {"ling" , "yi" , "er" , "san" , "si"
                  , "wu" , "liu" , "qi" , "ba" , "jiu"};
string pos[10] = {"" , "Shi" , "Bai" , "Qian" , "Wan" ,
      "Shi", "Bai", "Qian" , "Yi"};
string s;
bool f = false;

int main()
{
    cin >> s;
    if(s[0] == '-') f = true , s.erase(0 , 1);
    int zeros = 0; // 两个以上的要读为0
    string res;
    for(int i = 1;i <= s.size();i ++)
    {
        int now = s[i - 1] - '0';
        if(now) // 非零
        {
            if(zeros) res += " ling" , zeros = 0;
            if(i > 1) res += " ";
            res += num[now] + " " + pos[s.size() - i];
        }
        else
        {
            zeros ++;
            if((s.size() - i) % 4 == 0 && zeros % 4) res += " " + pos[s.size() - i] , zeros = 0;
        }
    }
    res.pop_back();
    if(f) cout << "Fu ";
    if(s != "0") cout << res << endl;
    else cout << "ling" << endl;
    return 0;
}

1086 Tree Traversals Again

已知中序和前序，求后序

#include<iostream>
#include<stack>
#include<vector>

using namespace std;

const int N = 50;
int n;
stack<int>st;
int in[N] , pre[N] , pos[N];
int l[N] , r[N];
vector<int>post;

int build(int il , int ir , int pl , int pr)
{
    int root = pre[pl];
    int k = pos[root];
    if(il < k) l[root] = build(il , k - 1 , pl + 1 , pl + k - il);
    if(k < ir) r[root] = build(k + 1 , ir , pl + k - il + 1 , pr);
    post.push_back(root);
    return root;
}

int main()
{
    cin >> n;
    n *= 2;
    int cnt = 0 , cnti = 0;
    while(n --)
    {
        string s;
        int x;
        cin >> s;
        if(s == "Push") cin >> x , st.push(x) , pre[cnt ++] = x;
        else in[cnti] = st.top() , pos[st.top()] = cnti ++ , st.pop();
    }
    n = cnt;
    build(0 , n - 1 , 0 , n - 1);
    for(int i = 0;i < post.size();i ++)
    {
        if(i) cout << " ";
        cout << post[i];
    }
    return 0;
}

1087 All Roads Lead to Rome

迪杰斯特拉

#include<iostream>
#include<vector>
#include<cstring>
#include<unordered_map>
#include<algorithm>

using namespace std;

const int N = 510;
int n , m;
string start;
unordered_map<string , int>mp;
unordered_map<int , string>rev_mp;
int happy[N];
int g[N][N];
bool st[N];
int dist[N] , path[N] , cnt[N] , ha[N];
int point[N];

void dij()
{
    memset(st , 0 , sizeof st);
    memset(dist , 0x3f , sizeof dist);
    memset(path , -1 , sizeof path);
    dist[mp[start]] = 0, cnt[mp[start]] = 1 , point[mp[start]] = 1 , ha[mp[start]] = happy[mp[start]];
    for(int i = 1;i <= n;i ++)
    {
        int t = -1;
        for(int j = 1;j <= n;j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        for(int j = 1;j <= n;j ++)
        {
            if(dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                cnt[j] = cnt[t];
                ha[j] = ha[t] + happy[j];
                path[j] = t;
                point[j] = point[t] + 1;
            }
            else if(dist[j] == dist[t] + g[t][j])
            {
                cnt[j] += cnt[t];
                if(ha[j] < ha[t] + happy[j]) 
                {
                    ha[j] = ha[t] + happy[j];
                    path[j] = t;
                    point[j] = point[t] + 1;
                }
                else if(ha[j] == ha[t] + happy[j]) 
                {
                    if(point[j] > point[t] + 1)
                    {
                        path[j] = t;
                        point[j] = point[t] + 1;
                    }
                }
            }
        }
    }
}

int main()
{
    memset(g , 0x3f , sizeof g);
    cin >> n >> m >> start;
    
    for(int i = 0;i < n - 1;i ++)
    {
        string s;
        int h;
        cin >> s >> h;
        mp[s] = i + 1;
        rev_mp[i + 1] = s;
        happy[i + 1] = h;
    }
    mp[start] = n;
    rev_mp[n] = start;
    while(m --)
    {
        string a , b;
        int c;
        cin >> a >> b >> c;
        g[mp[a]][mp[b]] = g[mp[b]][mp[a]] = c;
    }
    
    dij();
    
    cout << cnt[mp["ROM"]] << " " << dist[mp["ROM"]] << " ";
    cout << ha[mp["ROM"]] << " ";
    vector<int>res;
    for(int i = mp["ROM"];~i;i = path[i])
        res.push_back(i);
    cout << ha[mp["ROM"]] / (res.size() - 1) << endl;
    reverse(res.begin() , res.end());
    for(int i = 0;i < res.size();i ++)
    {
        if(i) cout << "->";
        cout << rev_mp[res[i]];
    }
    return 0;
}