PAT1045. Favorite Color Stripe

发表于 2017-10-12 | 分类于 algorithm

题目大意

1045. Favorite Color Stripe

给定两个序列 a 和 b, 求 b 中元素按照 a 的子序列中元素出现的次序的最大公共序列长度.

题目分析

当 a 为 0 或者 b 为 0, 则平凡态为 0

f(0, l) = f(m, 0) = 0

当两个序列当前的末尾相同, 即 a[i] == a[j], 则当前长度等于原有长度 + 1.

f(i, j) = f(i, j - 1) + 1
// m 相同代表末尾颜色相同, l - 1 表示先前(即长度减一)的状态.
当两个序列当前的末尾不相同, 即 a[i] != a[j], 肯定不可以进行拼凑.
所以当前状态f(i, j)的值肯定由上一个 a[i] == a[j]的状态转移而来.
我们可以缩短a的长度来改变a的末尾元素, 即 f(i - 1, j).
或者缩短b的长度来改变b的末尾元素, 即f(i, j - 1).

代码

#include <cstdio>
using namespace std;
const int maxm = 200 + 10;
const int maxl = 10000 + 10;
int dp[maxl];
int favo[maxm];
int stri[maxl];
int main(){
    int n, m, l;
    scanf("%*d%d", &m);
    for(int i = 1; i <= m; i++)
        scanf("%d", &favo[i]);
    scanf("%d", &l);
    for(int i = 1; i <= l; i++)
        scanf("%d", &stri[i]);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= l; j++)
            if(favo[i] == stri[j])
                dp[j] = dp[j - 1] + 1;
            else if(dp[j] < dp[j - 1])
                dp[j] = dp[j - 1];
    printf("%d\n", dp[l]);
    return 0;
}

PAT1043. Is It a Binary Search Tree

发表于 2017-10-11 | 分类于 algorithm

题目大意

1043. Is It a Binary Search Tree
注意此处的二叉搜索树定义

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

PS: 没认真读题还去找强哥问, 真是切腹自尽算了…

给定前序遍历, 问是一棵BST还是镜像BST, 是的话, 则输出YES, 以及后序遍历, 否则, 输出NO.

题目分析

最开始写了四个函数(判断是否BST, 判断是否镜像BST, 求BST的后序, 求镜像BST的后序). 后来看了柳婼的code, 发现只需要一个函数. 直接求后序, 然后一个全局变量标记是否为镜像, 进行不同的判断. 如果不是BST的话, 则不会遍历所有结点(return 会提前返回), 因此长度不足n. 同理可以判断是否为镜像BST.

代码

#include <iostream>
#include <vector>
using namespace std;
vector<int> preOrder;
vector<int> postOrder;
bool isMirror = false;
int nNode;
void prPostOrder(){
    cout << "YES" << endl;
    for(int i = 0; i < nNode; i++){
        if(i != 0)
            cout << " ";
        cout << postOrder[i];
    }
}
void bst(int begin, int end){
    if(end < begin)
        return;
    if(begin == end){
        postOrder.push_back(preOrder[begin]);
        return;
    }
    int rootKey = preOrder[begin];
	//注意此处i, j的含义 以及 初始值
    int i = end;
    int j = begin + 1;
    if(isMirror == false){
        while(i >= begin + 1 && preOrder[i] >= rootKey)
            --i;
        while(j <= end && preOrder[j] < rootKey)
            ++j;
    }
    else{
        while(i >= begin + 1 && preOrder[i] < rootKey)
            --i;
        while(j <= end && preOrder[j] >= rootKey)
            ++j;
    }
    if(i > j)
        return;
    bst(begin + 1, i);
    bst(j, end);
    postOrder.push_back(rootKey);
}
int main(){
    cin >> nNode;
    for(int i = 0; i < nNode; i++){
        int key;
        cin >> key;
        preOrder.push_back(key);
    }
    bst(0, nNode - 1);
    if(postOrder.size() != nNode){
        isMirror = true;
        postOrder.clear();
        postOrder.resize(0);
        bst(0, nNode - 1);
    }
    if(postOrder.size() == nNode)
        prPostOrder();
    else
        cout << "NO";
    return 0;
}

PAT1038. Recover the Smallest Number

发表于 2017-10-08 | 分类于 algorithm

题目大意

1038. Recover the Smallest Number

给定 n 个数字片段, 求这个所能组成的最大数值是多少, 输出并忽略前导 0.

分析

不能简单的按照字典序排序, 因为有320, 32, 8 这种情况, 若简单按照字典序进行排序, 会出现 323208, 而真正的答案是 320328.

假设序列中有相邻的数字片段a, b. 若a, b交换位置能使 a + b < b + a (因为二者长度相同, 所以比较字典序即可) 则序列可以变小, 所以最终答案也是这个顺序, 给 sort 函数传一个 cmp 即可.

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool aFuckingAmazingCmp(const string& a, const string& b){
    return a + b < b + a;
}
int main(){
    int nNum;
    cin >> nNum;
    vector<string> arr;
    for(int i = 0; i < nNum; i++){
        string s;
        cin >> s;
        arr.push_back(s);
    }
    sort(arr.begin(), arr.end(), aFuckingAmazingCmp);
    string s = "";
    for(int i = 0; i < nNum; i++)
        s += arr[i];
    while(s.size() != 0 && s[0] == '0')
        s.erase(s.begin());
    if(s.size() == 0)
        cout << 0 << endl;
    else
        cout << s << endl;
    return 0;
}

PAT1030. Travel Plan

发表于 2017-10-02 | 分类于 algorithm

题目大意

PAT1030

给定一个图, 图中边有两类边权, 路径长度 和花费, 选择路径长度最短的路线, 并保存. 当存在相同长度的最优解, 花费最小的解.

题目分析

按照路径长度进行边的松弛, 此时不要忘记对花费进行松弛.
当路径长度相同时, 按照花费进行松弛.

保存图中最短路径时, 记录当前结点的前一个结点. 输出答案时, 回溯即可.

代码

#include <iostream>
#include <stack>
using namespace std;
const int arrSize = 510;
const int INF = 9999999;
int dist[arrSize][arrSize];
int cost[arrSize][arrSize];
int path[arrSize];
int disCost[arrSize];
int disDist[arrSize];
bool isVis[arrSize];
int nVertex, nEdge, srcCity, tarCity;
void init(){
    for(int i = 0; i < nVertex; i++){
        path[i] = -1;
        disCost[i] = INF;
        disDist[i] = INF;
        isVis[i] = false;
        for(int j = 0; j < nVertex; j++){
            dist[i][j] = cost[i][j] = INF;
            if(i == j){
                dist[i][i] = cost[i][i] = 0;
            }
        }
    }
}
int main(){
    cin >> nVertex >> nEdge >> srcCity >> tarCity;
    init();
    for(int i = 0; i < nEdge; i++){
        int a, b;
        cin >> a >> b;
        cin >> dist[a][b] >> cost[a][b];
        dist[b][a] = dist[a][b];
        cost[b][a] = cost[a][b];
    }
    for(int i = 0; i < nVertex; i++){
        disDist[i] = dist[srcCity][i];
        disCost[i] = cost[srcCity][i];
    }
    isVis[srcCity] = true;
    for(int i = 0; i < nVertex - 1; ++i){
        int u;
        int minV = INF;
        for(int j = 0; j < nVertex; j++){
            if(isVis[j])
                continue;
            if(disDist[j] < minV){
                minV = disDist[j];
                u = j;
            }
        }
        isVis[u] = true;
        for(int v = 0; v < nVertex; v++){
            if(disDist[u] + dist[u][v] < disDist[v]){
                disDist[v] = disDist[u] + dist[u][v];
                disCost[v] = disCost[u] + cost[u][v];
                path[v] = u;
            }
            else if(disDist[u] + dist[u][v] == disDist[v]){
                if(disCost[u] + cost[u][v] < disCost[v]){
                    disCost[v] = disCost[u] + cost[u][v];
                    path[v] = u;
                }
            }
        }
    }
    stack<int> sav;
    int p = tarCity;
    while(p != -1){
        sav.push(p);
        p = path[p];
    }
    sav.push(srcCity);
    while(!sav.empty()){
        cout << sav.top() << " ";
        sav.pop();
    }
    cout << disDist[tarCity] << " " << disCost[tarCity];
    return 0;
}

PAT1026 Table Tennis

发表于 2017-09-30

POJ3660 Cow Contest

发表于 2017-09-27 | 分类于 algorithm

题目大意

POJ3660 Cow Contest

n 只牛之间进行比赛, 给定 m 条关于两只牛之间的强弱信息, 求有多少只牛排名确定.

思路

若对于任意一只牛, 若知道比它排名高的牛有 x 只, 比它排名低的牛有 y 只, x + y == n - 1. 则可以知道这头牛的排名.

利用 Floyd-Warshall, 求出图中的传递闭包, 若一个点与其他所有点的关系已知, 则可以求解这个点的排名.

代码

#include <iostream>
using namespace std;
const int arrSize = 110;
bool edge[arrSize][arrSize];
int main(){
    int nVertex, nEdge;
    cin >> nVertex >> nEdge;
    for(int i = 0; i < nEdge; i++){
        int a, b;
        cin >> a >> b;
        edge[a][b] = true;
    }
    for(int k = 1; k <= nVertex; ++k){
        for(int i = 1; i <= nVertex; ++i){
            for(int j = 1; j <= nVertex; ++j){
                if(edge[i][k] && edge[k][j])
                    edge[i][j] = true;
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= nVertex; ++i){
        bool flag = true;
        for(int j = 1; j <= nVertex; ++j){
            if(i == j)
                continue;
            if(edge[i][j] == false && edge[j][i] == false){
                flag = false;
                break;
            }
        }
        if(flag)
            cnt++;
    }
    cout << cnt;
    return 0;
}

PAT1021 Deepest Root

发表于 2017-09-26 | 分类于 algorithm

题目大意

PAT1021 Deepest Root

给定一个图, 问是否为连通图, 若不是, 则输出连通分量的数目. 否则, 以任一个点为根, 求树的最大深度, 输出这些根节点.

思路

用并查集检查图是否的连通图.
从任意一点进行dfs, 得到一个集合, 该集合的点即为 deepest root 的一部分.
从上一步的集合中任意一点进行dfs, 得到一个集合.
答案集合即为 2, 3步的合集.

证明

设任一点为 A , 从点 A 到其他点的最大距离为 Lx, Lx 为局部最优解答, 由于图是连通的, 图中任意一点都可以到达点 A , 且距离 Ly < Lx. 因此第一次 dfs 得到的解为最终解的部分解.

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstdio>
using namespace std;
int nNode;
struct Node{
    vector<int> nodeList;
};
const int arrSize = 10100;
int arr[arrSize];
bool isVis[arrSize];
vector<Node> edge(arrSize);
int getFather(int loc){
    if(arr[loc] == loc)
        return loc;
    loc = getFather(arr[loc]);
    return loc;
}
void merge(int a, int b){
    a = getFather(a);
    b = getFather(b);
    if(a < b)
        arr[b] = a;
    else
        arr[a] = b;
}
void init(){
    for(int i = 0; i <= nNode + 1; i++){
        arr[i] = i;
        isVis[i] = false;
    }
}
int getComponents(){
    int cnt = 0;
    for(int i = 1; i <= nNode; i++){
        if(arr[i] == i)
            cnt++;
    }
    return cnt;
}
set <int> ans;
int maxD = 0;
int dfs(int vertex, int depth){
    if(depth > maxD){
        ans.clear();
        maxD = depth;
    }
    if(depth == maxD)
        ans.insert(vertex);
    for(int i = 0; i < edge[vertex].nodeList.size(); i++){
        if(isVis[edge[vertex].nodeList[i]])
            continue;
        isVis[edge[vertex].nodeList[i]] = true;
        dfs(edge[vertex].nodeList[i], depth + 1);
    }
}
int main(){
    cin >>  nNode;
    if(nNode == 1){
        cout << 1 << endl;
        return 0;
    }
    init();
    for(int i = 0; i < nNode - 1; ++i){
        int a, b;
        cin >> a >> b;
        merge(a, b);
        edge[a].nodeList.push_back(b);
        edge[b].nodeList.push_back(a);
    }
    int cs = getComponents();
    if(cs != 1){
        cout << "Error: " << cs << " components" << endl;
        return 0;
    }
    init();
    isVis[1] = true;
    dfs(1, 0);
    init();
    isVis[*ans.begin()] = true;
    set<int> temp = ans;
    ans.clear();
    dfs(*temp.begin(), 0);
    for(set<int>::iterator it = temp.begin(); it != temp.end(); it++){
        ans.insert(*it);
    }
    for(set<int>::iterator it = ans.begin(); it != ans.end(); it++){
        cout << *it << endl;
    }
    return 0;
}
// 6
// 1 2
// 5 4
// 2 4
// 2 3
// 3 6

PAT1020 Tree Traversals

发表于 2017-09-25 | 分类于 algorithm

题目大意

PAT1020

给定一棵树的后序和前序遍历, 求树的层序遍历.

思路

不断进行递归, 当长度为 0 时, 返回空指针.
柳婼的博客是利用一个大的数组进行存储结点, 但题目中给出了30 个结点, 最坏情况下需要 2 ^ 31 - 1 个结点. 虽然这道题用数组存储结点并不会出错, 但是为了 robust. 还是动态的创建结点比较好~

坑

要充分理解函数传参当中 postLoc, inLoc 是绝对位置, 而 length 为相对长度.
函数参数写错了就很坑 QAQQQQQQQQQ

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Node{
    Node *leftChild, *rightChild;
    int data;
    Node(int d, Node* l, Node* r)
        : data(d), leftChild(l), rightChild(r){};
};
vector<int> postOrder;
vector<int> inOrder;
Node* constructTree(int postLoc, int inLoc, int length){
    // cout << length << endl;
    if(length <= 0)
        return NULL;
    Node* temp = new Node(postOrder[postLoc + length - 1], NULL, NULL);
    int loc = inLoc;
    for(; loc < inLoc + length
            && inOrder[loc] != postOrder[postLoc + length - 1]; loc++);
    temp->leftChild = constructTree(postLoc, inLoc, loc - inLoc);
    //右子树的长度 为 中序的起始位置 + 中序长度 得到 中序终止位置
    //               再减去 左子树 和 根节点的长度和.
    temp->rightChild = constructTree(postLoc + loc - inLoc, loc + 1, inLoc + length - loc - 1);
    return temp;
}
int nNode;
void prTree(Node* root){
    queue<Node*> que;
    que.push(root);
    int cnt = 0;
    while(!que.empty()){
        cout << que.front()-> data;
        cnt++;
        if(cnt != nNode)
            cout << " ";
        if(que.front()->leftChild != NULL)
            que.push(que.front()->leftChild);
        if(que.front()->rightChild != NULL)
            que.push(que.front()->rightChild);
        que.pop();
    }
}
int main(){
    cin >> nNode;
    for(int i = 0; i < nNode; ++i){
        int data;
        cin >> data;
        postOrder.push_back(data);
    }
    for(int i = 0; i < nNode; ++i){
        int data;
        cin >> data;
        inOrder.push_back(data);
    }
    Node* root = constructTree(0, 0, nNode);
    prTree(root);
    return 0;
}

POJ1860 Currency Exchange

发表于 2017-09-23 | 分类于 algorithm

题目大意

POJ1860

给定一个带有点权和边权的图, 求是否存在正权回路.

思路

由于Bellman-Ford算法可以求图中是否存在负权回路. 因此可以将 dis数组的初始状态置为 0, 求是否存在正权回路.

代码

#include <iostream>
#include <vector>
using namespace std;
struct Edge{
    Edge(int a_, int b_, double r_, double c_)
        : a(a_), b(b_), rate(r_), commi(c_){}
    int a, b;
    double rate, commi;
};
const int arrSize = 210;
int main(){
    int nEdge, nVertex, amoCur;
    double vCur;
    cin >> nVertex >> nEdge >> amoCur >> vCur;
    vector<Edge> edge;
    for(int i = 0; i < nEdge; ++i){
        int a, b;
        cin >> a >> b;
        double r, c;
        cin >> r >> c;
        edge.push_back(Edge(a, b, r, c));
        cin >> r >> c;
        edge.push_back(Edge(b, a, r, c));
    }
    double dis[arrSize];
    for(int i = 0; i < nEdge * 2; i++)
        dis[i] = 0;
    dis[amoCur] = vCur;
    for(int i = 0; i <= nVertex; i++){
        bool flag = true;
        for(int j = 0; j < edge.size(); j++){
            if(dis[edge[j].b] < (dis[edge[j].a] - edge[j].commi) * edge[j].rate){
                dis[edge[j].b] = (dis[edge[j].a] - edge[j].commi) * edge[j].rate;
                flag = false;
            }
        }
        if(flag)
            break;
        if(i == nVertex){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

About DEATH

发表于 2017-09-22

若无牵无挂, 我宁愿迎接的是死亡, 而非自由.