柳婼の blog – 第193页 – 我不管，反正我最萌～

【C++】判断两个vector是否相等~直接用“==”

如果vector里面的元素类型是简单类型（内置类型），可以直接使用“==”或者“!=”进行比较

因为在STL里面，==和!=是可以直接使用的：
template< class T, class Alloc >
bool operator==( const vector<T,Alloc>& lhs,
                 const vector<T,Alloc>& rhs );

template< class T, class Alloc >
bool operator!=( const vector<T,Alloc>& lhs,
                 const vector<T,Alloc>& rhs );

因为在STL里面，==和!=是可以直接使用的：

template< class T, class Alloc >

bool operator==( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

template< class T, class Alloc >

bool operator!=( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

甚至可以使用“<=” “<” “>=” “>”比较两个vector大小：按照字典序排列

template< class T, class Alloc >
bool operator<( const vector<T,Alloc>& lhs,
                const vector<T,Alloc>& rhs );

template< class T, class Alloc >
bool operator<=( const vector<T,Alloc>& lhs,
                 const vector<T,Alloc>& rhs );

template< class T, class Alloc >
bool operator>( const vector<T,Alloc>& lhs,
                const vector<T,Alloc>& rhs );

template< class T, class Alloc >
bool operator>=( const vector<T,Alloc>& lhs,
                 const vector<T,Alloc>& rhs );

template< class T, class Alloc >

bool operator<( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

template< class T, class Alloc >

bool operator<=( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

template< class T, class Alloc >

bool operator>( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

template< class T, class Alloc >

bool operator>=( const vector<T,Alloc>& lhs,

const vector<T,Alloc>& rhs );

1087. All Roads Lead to Rome (30)-PAT甲级真题（Dijkstra + DFS）

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness — it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
Sample Output:
3 3 195 97
HZH->PRS->ROM

题目大意：有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为幸福值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出幸福值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径
分析：Dijkstra+DFS。Dijkstra算出所有最短路径的路线pre二维数组，DFS求最大happiness的路径path，并求出路径条数，最大happiness，最大average～
注意：average是除去起点的average。城市名称可以用m存储字符串所对应的数字，用m2存储数字对应的字符串

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
const int inf = 999999999;
int e[205][205], weight[205], dis[205];
bool visit[205];
vector<int> pre[205], temppath, path;
map<string, int> m;
map<int, string> m2;
int maxvalue = 0, mindepth, cntpath = 0;
double maxavg;
void dfs(int v) {
    temppath.push_back(v);
    if(v == 1) {
        int value = 0;
        for(int i = 0; i < temppath.size(); i++) {
            value += weight[temppath[i]];
        }
        double tempavg = 1.0 * value / (temppath.size() - 1);
        if(value > maxvalue) {
            maxvalue = value;
            maxavg = tempavg;
            path = temppath;
        } else if(value == maxvalue && tempavg > maxavg) {
            maxavg = tempavg;
            path = temppath;
        }
        temppath.pop_back();
        cntpath++;
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++) {
        dfs(pre[v][i]);
    }
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 205 * 205, inf);
    fill(dis, dis + 205, inf);
    scanf("%d %d", &n, &k);
    string s;
    cin >> s;
    m[s] = 1;
    m2[1] = s;
    for(int i = 1; i < n; i++) {
        cin >> s >> weight[i+1];
        m[s] = i+1;
        m2[i+1] = s;
    }
    string sa, sb;
    int temp;
    for(int i = 0; i < k; i++) {
        cin >> sa >> sb >> temp;
        e[m[sa]][m[sb]] = temp;
        e[m[sb]][m[sa]] = temp;
    }
    dis[1] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 1; j <= n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 1; v <= n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    int rom = m["ROM"];
    dfs(rom);
    printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);
    for(int i = path.size() - 1; i >= 1; i--) {
        cout << m2[path[i]] << "->";
    }
    cout << "ROM";
    return 0;
}

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

using namespace std;

int n, k;

const int inf = 999999999;

int e[205][205], weight[205], dis[205];

bool visit[205];

vector<int> pre[205], temppath, path;

map<string, int> m;

map<int, string> m2;

int maxvalue = 0, mindepth, cntpath = 0;

double maxavg;

void dfs(int v) {

temppath.push_back(v);

if(v == 1) {

int value = 0;

for(int i = 0; i < temppath.size(); i++) {

value += weight[temppath[i]];

}

double tempavg = 1.0 * value / (temppath.size() - 1);

if(value > maxvalue) {

maxvalue = value;

maxavg = tempavg;

path = temppath;

} else if(value == maxvalue && tempavg > maxavg) {

maxavg = tempavg;

path = temppath;

}

temppath.pop_back();

cntpath++;

return ;

}

for(int i = 0; i < pre[v].size(); i++) {

dfs(pre[v][i]);

}

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 205 * 205, inf);

fill(dis, dis + 205, inf);

scanf("%d %d", &n, &k);

string s;

cin >> s;

m[s] = 1;

m2[1] = s;

for(int i = 1; i < n; i++) {

cin >> s >> weight[i+1];

m[s] = i+1;

m2[i+1] = s;

}

string sa, sb;

int temp;

for(int i = 0; i < k; i++) {

cin >> sa >> sb >> temp;

e[m[sa]][m[sb]] = temp;

e[m[sb]][m[sa]] = temp;

}

dis[1] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 1; j <= n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 1; v <= n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

int rom = m["ROM"];

dfs(rom);

printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);

for(int i = path.size() - 1; i >= 1; i--) {

cout << m2[path[i]] << "->";

}

cout << "ROM";

return 0;

}

L1-015. 跟奥巴马一起画方块-PAT团体程序设计天梯赛GPLT

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！
输入格式：
输入在一行中给出正方形边长N（3<=N<=21）和组成正方形边的某种字符C，间隔一个空格。
输出格式：
输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。
输入样例：
10 a
输出样例：
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;
    char c;
    cin >> c;
    int t = N / 2 + N % 2;
    for (int i = 0; i < t - 1; i++) {
        for (int k = 0; k < N; k++)
            cout << c;
        cout << endl;
    }
    for (int i = 0; i < N; i++)
        cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N;

cin >> N;

char c;

cin >> c;

int t = N / 2 + N % 2;

for (int i = 0; i < t - 1; i++) {

for (int k = 0; k < N; k++)

cout << c;

cout << endl;

}

for (int i = 0; i < N; i++)

cout << c;

return 0;

}

Swift代码规范

一行不要超过160个字符
左大括号不换行
运算符（ + – * / == != ->）左右加空格，

let myValue = 20 + (30 / 2) * 3

1	let myValue = 20 + (30 / 2) * 3

逗号、冒号的后面加空格，但遇到后面是小括号则不需要加空格

func insert(_ newElement: Element, atIndex i: Int) -&gt; Int {
  
}

let myValue = [1, 2, 3, 4, 5]

func insert(_ newElement: Element, atIndex i: Int) -> Int {

}

let myValue = [1, 2, 3, 4, 5]

if else的else、do catch的catch，与大括号在同一行

if a == b {
  
} else {
  
}

do {
  
} catch {
  
}

if a == b {

} else {

}

do {

} catch {

}

跨多行函数声明要缩进

func myFunctionWithManyParameters(parameterOne: String,
                                  parameterTwo: String,
                                  parameterThree: String) {
    print("\(parameterOne) \(parameterTwo) \(parameterThree)")
}

func myFunctionWithManyParameters(parameterOne: String,

parameterTwo: String,

parameterThree: String) {

print("\(parameterOne) \(parameterTwo) \(parameterThree)")

}

跨多行if语句要缩进

if myFirstVariable > (mySecondVariable + myThirdVariable)
    && myFourthVariable == .SomeEnumValue {
    print("Hello, World!")
}

if myFirstVariable > (mySecondVariable + myThirdVariable)

&& myFourthVariable == .SomeEnumValue {

print("Hello, World!")

}

尽量避免多行断言，可以使用本地变量或者其他策略

let firstCondition = x == firstReallyReallyLongPredicateFunction()
let secondCondition = y == secondReallyReallyLongPredicateFunction()
let thirdCondition = z == thirdReallyReallyLongPredicateFunction()
if firstCondition && secondCondition && thirdCondition {

}

let firstCondition = x == firstReallyReallyLongPredicateFunction()

let secondCondition = y == secondReallyReallyLongPredicateFunction()

let thirdCondition = z == thirdReallyReallyLongPredicateFunction()

if firstCondition && secondCondition && thirdCondition {

}

尽可能多使用let，少使用var
如果变量类型可以依靠推断得出，不建议声明变量时指名类型
switch模块中不用显式使用break
if语句左右不要使用小括号

if x == y {
  
}

if x == y {

}

不要使用as! 或 try!
在解析可选类型时，推荐使用 guard 语句，而不是 if 语句，因为 guard 语句可以减少不必要的嵌套缩进
如果需要在2个状态间做出选择，建议使用if 语句，而不是使用 guard 语句

// 推荐
if isFriendly {
    print("你好, 远路来的朋友！")
} else {
    print(“穷小子，哪儿来的？")
}

// 不推荐
guard isFriendly else {
    print("穷小子，哪儿来的？")
    return
}
print("你好, 远路来的朋友！")

// 推荐

if isFriendly {

print("你好, 远路来的朋友！")

} else {

print(“穷小子，哪儿来的？")

}

// 不推荐

guard isFriendly else {

print("穷小子，哪儿来的？")

return

}

print("你好, 远路来的朋友！")

即使文档注释只有一行，也要使用模块化格式 (/** */)
使用首字母大写的驼峰命名规则来命名枚举值

enum Shape {
  case Rectangle
  case Square
  case Triangle
  case Circle
}

enum Shape {

case Rectangle

case Square

case Triangle

case Circle

}

尽可能的避免使用强制转换和强制解包
不要在 if 和 switch 条件两边或者 return 关键词上加 Objective-C 样式的圆括号
避免使用行尾分号，尽管这样是可以编译通过的。但是它们会让你的代码看起来很糟糕，而且用起来体验也很差。
版权声明应该被包含在所有源文件的顶部
笑脸

// 推荐：
:]

// 不推荐：
:)

// 推荐：

// 不推荐：

用足够的空行把代码分割成合理的块
不要在一行结尾留下空白，也不要在空行留下缩进
文件结束时留一空行

LeetCode 387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

分析：map存储每个字符的出现次数，从头遍历数组return第一个m[s[i]] == 1的下标。如果没有就return -1。

class Solution {
public:
    int firstUniqChar(string s) {
        map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        for(int i = 0; i < s.length(); i++) {
            if(m[s[i]] == 1)
                return i;
        }
        return -1;
    }
};

class Solution {

public:

int firstUniqChar(string s) {

map<char, int> m;

for(int i = 0; i < s.length(); i++)

m[s[i]]++;

for(int i = 0; i < s.length(); i++) {

if(m[s[i]] == 1)

return i;

}

return -1;

}

};

L3-005. 垃圾箱分布-PAT团体程序设计天梯赛GPLT（Dijkstra）

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N（<= 103）是居民点的个数；M（<= 10）是垃圾箱候选地点的个数；K（<= 104）是居民点和垃圾箱候选地点之间的道路的条数；DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出“No Solution”。

输入样例1：
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
输出样例1：
G1
2.0 3.3
输入样例2：
2 1 2 10
1 G1 9
2 G1 20
输出样例2：
No Solution

题目大意：从m个垃圾站里面选取1个站点，让他离居民区的最近的人最远，并且没有超出服务范围ds之内。如果有很多个最远的垃圾站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列垃圾站编号最小的那个、
分析：
因为垃圾站之间也是彼此有路连接的，所以最短路径计算的时候也要把垃圾站算上。所以我们就是堆n+m个点进行Dijkstra计算最短路径。要求计算出1~m号垃圾站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围ds的距离，那么我们就舍弃这个垃圾站。取最最短的路径，这就是距离它最近的垃圾站mindis。如果mindis > ansdis，就是说找到了一个距离居民最小距离的垃圾站是更远的，那就选这个垃圾站，更新ansid为它的id。最后输出
对于垃圾站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
    fill(e[0], e[0] + 1020 * 1020, inf);
    fill(dis, dis + 1020, inf);
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    for(int i = 0; i < k; i++) {
        int tempdis;
        string s, t;
        cin >> s >> t >> tempdis;
        int a, b;
        if(s[0] == 'G') {
            s = s.substr(1);
            a = n + stoi(s);
        } else {
            a = stoi(s);
        }
        if(t[0] == 'G') {
            t = t.substr(1);
            b = n + stoi(t);
        } else {
            b = stoi(t);
        }
        e[a][b] = tempdis;
        e[b][a] = tempdis;
    }
    int ansid = -1;
    double ansdis = -1, ansaver = inf;
    for(int index = n + 1; index <= n + m; index++) {
        double mindis = inf, aver = 0;
        fill(dis, dis + 1020, inf);
        fill(visit, visit + 1020, false);
        dis[index] = 0;
        for(int i = 0; i < n + m; i++) {
            int u = -1, minn = inf;
            for(int j = 1; j <= n + m; j++) {
                if(visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 1; v <= n + m; v++) {
                if(visit[v] == false && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
            }
        }
        for(int i = 1; i <= n; i++) {
            if(dis[i] > ds) {
                mindis = -1;
                break;
            }
            if(dis[i] < mindis) mindis = dis[i];
            aver += 1.0 * dis[i];
        }
        if(mindis == -1) continue;
        aver = aver / n;
        if(mindis > ansdis) {
            ansid = index;
            ansdis = mindis;
            ansaver = aver;
        } else if(mindis == ansdis && aver < ansaver) {
            ansid = index;
            ansaver = aver;
        }
    }
    if(ansid == -1)
        printf("No Solution");
    else {
        printf("G%d\n", ansid - n);
        printf("%.1f %.1f", ansdis, ansaver);
    }
    return 0;
}

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <string>

using namespace std;

const int inf = 999999999;

int n, m, k, ds, station;

int e[1020][1020], dis[1020];

bool visit[1020];

int main() {

fill(e[0], e[0] + 1020 * 1020, inf);

fill(dis, dis + 1020, inf);

scanf("%d%d%d%d", &n, &m, &k, &ds);

for(int i = 0; i < k; i++) {

int tempdis;

string s, t;

cin >> s >> t >> tempdis;

int a, b;

if(s[0] == 'G') {

s = s.substr(1);

a = n + stoi(s);

} else {

a = stoi(s);

}

if(t[0] == 'G') {

t = t.substr(1);

b = n + stoi(t);

} else {

b = stoi(t);

}

e[a][b] = tempdis;

e[b][a] = tempdis;

}

int ansid = -1;

double ansdis = -1, ansaver = inf;

for(int index = n + 1; index <= n + m; index++) {

double mindis = inf, aver = 0;

fill(dis, dis + 1020, inf);

fill(visit, visit + 1020, false);

dis[index] = 0;

for(int i = 0; i < n + m; i++) {

int u = -1, minn = inf;

for(int j = 1; j <= n + m; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 1; v <= n + m; v++) {

if(visit[v] == false && dis[v] > dis[u] + e[u][v])

dis[v] = dis[u] + e[u][v];

}

for(int i = 1; i <= n; i++) {

if(dis[i] > ds) {

mindis = -1;

break;

}

if(dis[i] < mindis) mindis = dis[i];

aver += 1.0 * dis[i];

}

if(mindis == -1) continue;

aver = aver / n;

if(mindis > ansdis) {

ansid = index;

ansdis = mindis;

ansaver = aver;

} else if(mindis == ansdis && aver < ansaver) {

ansid = index;

ansaver = aver;

}

if(ansid == -1)

printf("No Solution");

else {

printf("G%d\n", ansid - n);

printf("%.1f %.1f", ansdis, ansaver);

}

return 0;

}