FZU - 2112 Tickets (欧拉回路+联通块判断)

题目链接:

https://cn.vjudge.net/problem/FZU-2112


题目大意:

给定一个图的N个边,求添加最少的边使这个图形成欧拉路。不必所有的点都联通,只需要把已给出的边形成欧拉路。


解题过程:

之前好像做过一次做过题,然后又看到了,当时也忘记在哪看到了,不知道A了没有,反正记得看题解没理解……

这道题刚开始理解错了,还以为是求哈密顿图,这个是真的不会。回来又看了一遍题意才发现是之前做过的欧拉路。

然后又仔细想了下,可算是想通了。


题目分析:

首先BFS一遍记录下联通块个数, 每个联通块奇点的个数。

要构成欧拉路,就要把这些联通块之前用一条边连起来。
假设N个联通块,那么需要N-1个边把他们连接起来。

然后对于每一个联通块,如果奇点个数大于2,那么每多了个奇点,需要花费一条边连起来这两个奇点。

可以证明,对于任意一个无向图,他奇点的个数一定是偶数个。对于每无向边那么一定会给两个点增加一个度,所以奇点的个数一定是偶数个的。


AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int MAX = 112345;

int n, m;
int vis[MAX];
int book[MAX];
vector<int> edge[MAX];

//Dfs判断联通块个数和统计奇点的个数
void dfs(int u, int& odd) {
if (edge[u].size()%2)
odd++;
vis[u] = 1;
for (int i = 0; i < edge[u].size(); i++) {
int v = edge[u][i];
if (!vis[v])
dfs(v, odd);
}
}

int solve() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i] || !book[i])
continue;
int odd = 0;
dfs(i, odd);

//每个联通块的奇点如果大于2那么应该给做过联通块添加边消去奇点
cnt += odd > 2 ? (odd-2)/2:0;
cnt++;
}
printf("%d\n", cnt-1);
}

int main() {
int T;
scanf("%d", &T);
while (T--) {

scanf("%d %d", &n, &m);
memset(vis, 0, sizeof(vis));
memset(book, 0, sizeof(book));
for (int i = 0; i <= n; i++) {
edge[i].clear();
}

for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
book[u] = book[v] = 1;
edge[u].push_back(v);
edge[v].push_back(u);
}
solve();
}
}

DAG上的动态规划

不定终点的最长路:


矩阵嵌套问题:


题目链接:

http://acm.nyist.net/JudgeOnline/problem.php?pid=16


题目大意:

如果一个矩形的长和宽都大于另一个矩形,那么说这个矩形可以嵌套另一个矩形,现在有很多个矩形,输入矩形的长宽,求出他们的最大嵌套数。注意矩形的长宽是可以互换的。


题目分析:

这是一道经典的DAG上的动态规划问题,需要把问题转化成DAG上的最长路问题,把每个矩形看成点,如果两个矩形可以嵌套,那么他们建边,这样问题就是求最长路了。

状态的定义是对于第 i 个节点,由他出发最长的距离,根据边转移,如果一个矩形可以装下另一个矩形,那么这个矩形出发的最长距离就是他可以装下的那个矩形的最长距离加一。

递归边界是隐含的,如果一个矩形无法嵌套嵌套的矩阵,那么由他出发的最长距离是 1 ,即只有他本身。


AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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

int edge[1123][1123];
int d[1123], n;

int dp(int i) {
int& ans = d[i];
if (ans > 0)
return ans;
ans = 1;
for (int j = 0; j < n; j++) {
if (edge[i][j])
ans = max(ans, dp(j)+1);//状态转移
}
return ans;
}

int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int data[1123][2];
for (int i = 0 ; i < n; i++) {
scanf("%d %d", &data[i][0], &data[i][1]);
if (data[i][0] > data[i][1])
swap(data[i][0], data[i][1]);
}

memset(edge, 0, sizeof(edge));
memset(d, 0, sizeof(d));

for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (data[i][0] > data[j][0] && data[i][1] > data[j][1])
edge[i][j] = 1;//如果可以嵌套那么建边
}
}

int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp(i));//最终答案是所有节点出发最长的那个
}

printf("%d\n", ans);
}
}

The Tower of Babylon


题目链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=378


题目大意:

现在有很多立方体,每个立方体输入他的三个棱长即可确定,现在规定如果一个立方体的面的长和宽都大于另一个立方体的长和宽,那么这两个立方体是可以堆叠起来的。现在输入很多立方体,求堆叠出的最高高度。注意两个立方体三个棱长都要考虑,两个棱长确定是否可堆叠,一个决定堆起来的高度。立方体可以重复使用。


题目分析:

和上一题近似,不过这里我可以把每个立方体拆成三个,分别对于三个不同的面和高,然后根据面的长宽大小,对他们建边。然后就是求DAG上的最长路问题,不过这题的不同是,每条边有权了,并且不能直接拿长宽的大小当数组的下标。


AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;

struct Node {
int a, b;
int h;
Node(int a, int b, int h) {
if (a > b)
swap(a, b);
this->a = a;
this->b = b;
this->h = h;
}
};

bool operator < (const struct Node& a, const struct Node& b) {
if (a.a < b.a && a.b < b.b)
return true;
return false;
}

vector<Node> data;
int edge[1123][1123];
int dp[1123];

int dfs(int u) {
int& rst = dp[u];
if (rst >= 0)
return rst;
rst = 0;
for (int i = 0; i < data.size(); i++) {
if (edge[u][i])
rst = max(rst, dfs(i));
}
//最后要加上当前的立方体的高度
return rst += data[u].h;
}

int main() {
int n, cases = 0;
while (~scanf("%d", &n) && n) {
data.clear();
for (int i = 0; i < n; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
//把立方体根据每个面拆成三个
data.push_back(Node(a, b, c));
data.push_back(Node(a, c, b));
data.push_back(Node(b, c, a));
}
memset(edge, 0, sizeof(edge));
for (int i = 0; i < data.size(); i++) {
for (int j = 0; j < data.size(); j++) {
//如果可以堆叠,那么建边
if (data[i] < data[j]) {
edge[i][j] = 1;
}
}
}

memset(dp, -1, sizeof(dp));
int ans = 0;
for (int i = 0; i < data.size(); i++) {
ans = max(dfs(i), ans);
}
printf("Case %d: maximum height = %d\n", ++cases, ans);
}
}

数位DP(模板)

推荐博客:

http://zyk1997.github.io/2015/03/20/ShuWeiDP/


模板题:

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1009

http://acm.hdu.edu.cn/showproblem.php?pid=3555

http://acm.hdu.edu.cn/showproblem.php?pid=2089


模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//pos当前的位置,pre上一位的数字,ok现在是否已满足题目的条件,bound是否受到限制。
LL dfs(int pos,int pre,int ok,int bound){
//如果递归到个位,就到达了边界并返回。
if(pos < 0)
return ok;

//如果不受限制,那么可以查看dp数组当前状态是否计算过。
if(!bound && dp[x][pre][ok]!=-1)
return dp[x][pre][ok];

//根据是否受限制,确定需要枚举的数。
int last=bound? num[x]:9;

LL rst=0;

for(int i=0;i<=last;i++)
//成立条件根据题目要求,如果当前枚举的是最后应该是,并且受限制,那么下一位也受限制。
re+=dfs(x-1, i, ok || (成立条件), bound && (i==last));

//如果不受限制,那么更新dp数组。
if(!bound) f[x][pre][ok]=re;
return re;
}

LL solve(LL n){
int len=0;
while(n){
num[len++]=n%10;
n/=10;
}
return dfs(len-1,0,0,1);
}

SDUTOJ - 2781 二分练习(二分)

题目链接:

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2781.html


题目大意:

给你一个序列,然后给你m个元素,让你从序列中找出与每个元素最接近的数字输出来,如果有两个就输出两个。


解题过程:

刚开始是 WA 了好久,看了博客,听学长讲完才知道做法,这里当作一个二分的模板。


题目分析:

  • 本题主要是找二分的下界和上界。
  • 假设要查找一个数 n,上界是大于等于 n 的数中最小的。下界是小于等于 n 的数中最大的。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

int data[10000000+10];

int find_left(int l, int r, int k) {
int rst = 0;
while (l <= r) {
int m = (l+r) >> 1;
if (data[m] <= k) {
rst = m;
l = m+1;
} else {
r = m-1;
}
}
return rst;
}

int find_right(int l, int r, int k) {
int rst = 0;
while (l <= r) {
int m = (l+r) >> 1;
if (data[m] >= k) {
rst = m;
r = m-1;
} else {
l = m+1;
}
}
return rst;
}

int main() {
int n, m;
while (~scanf("%d %d", &n, &m)) {
for (int i = 0; i < n; i++) {
scanf("%d", data+i);
}
sort(data, data+n);
while (m--) {
int k;
scanf("%d", &k);
int left = find_left(0, n-1, k);
int right = find_right(0, n-1, k);

if (abs(k-data[left]) != abs(k-data[right])) {
if (abs(k-data[left]) < abs(k-data[right]))
printf("%d\n", data[left]);
else
printf("%d\n", data[right]);
}
else if (data[left] == data[right]) {
printf("%d\n", data[left]);
}
else {
printf("%d %d\n", data[left], data[right]);
}
}
putchar('\n');
}
}

POJ3494 - Largest Submatrix of All 1’s (单调栈)

题目链接:

http://poj.org/problem?id=3494

题目大意:

给定一个矩阵,里面只包含 0 和 1,求这个矩阵里所有子矩阵中值最大是多少(即矩阵内部所有的 0,1 的和)。


解题过程:

由于前几天刚做完一个单调栈的题,然后看到这个题就马上往那方面想了,但是还是不太熟练,对着模板才敲出来。


题目分析:

  • 首先处理一下数据,开一个数组,数组 data[i][j] 代表着以第 i 行,第 j 列结尾的连续 1 的个数(自上到下的连续,例如data[0][j], data[1][j]都是 1 ,那么 data[0][j] = 1, data[1][j] = 2)。
  • 这样我枚举每一行,对于每一行,问题转化成了一个典型的单调栈问题,求出所有行的最大值即是答案。
  • 这里说一下单调栈,在本题中,如果栈为空或者当前元素直接入栈,否则将栈顶元素出栈并计算栈顶元素的面积。

    • 这里的面积是计算以栈顶元素为最大高度的矩阵面积,那么栈顶元素最左边可到达的是栈中上一个比他小的数(如果栈为空就是左边界了),最右可到达是即将要入栈的数(因为比他小),这里不直接那栈顶元素的下标和当前元素的下标计算是因为可能有大小相同的元素。

    • 最后栈如果不为空的话要依次出栈并计算大小,计算大小的时候以栈中上一个比他小的数为最左可到达的地方(如果栈为空就是左边界了) ,最右可到达的是有边界,因为每一个栈中的数,都比右边所有的数要小。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<queue>
#include<cstdio>
#include<stack>
using namespace std;

const int MAX = 2000+100;

int data[MAX][MAX];

int main() {
int m, n;
while (~scanf("%d %d", &m, &n)) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &data[i][j]);
if (data[i][j] != 0 && i != 0)
data[i][j] += data[i-1][j];
}
}

int ans = 0;
for (int i = 0; i < m; i++) {
stack<int> ss;
for (int j = 0; j < n; j++) {
if (ss.empty() || data[i][j] > data[i][ss.top()]) {
ss.push(j);
} else {
int start = ss.top();
ss.pop();
int width = ss.empty() ? j : j - ss.top()-1;
ans = max(ans, data[i][start]*width);
j--;
}
}
while (!ss.empty()) {
int start = ss.top();
ss.pop();
int width = ss.empty() ? n : n - ss.top() - 1;
ans = max(ans, data[i][start]*width);
}
}
printf("%d\n", ans);
}
}

POJ2155 - Matrix (二维树状数组)

题目链接:

http://poj.org/problem?id=2155


题目大意:

给定一个矩阵,初始化为0,现在可以进行两种操作,一种是查询某个点的值是 0 还是 1。另一种是让这个矩阵的一个子矩阵内的值取反。


解题过程:

省赛选拔赛的题,太难了直接没看………
后来补起来,有模板还是挺容易的。


题目分析:

  • 首先这题虽然看起来像是一个区间修改,单点查询的题,但是可以转化成单点修改,查询区间和。

    • 首先考虑一维的情况,我要一段区间取反,假设是 [l, r]。那么我只需要book[l]+1book[r+1]+1,假设查询 k 的时候,只需要查询前 k 的和 mod 2 的结果即可。
    • 然后这种方法可以推广到二维,不过这里要用一下容斥原理。假设修改的子矩阵左上角和右下角分别为 x1 y1 x2 y2,首先book[x1][y1]+1, book[x2][y2]+1,不过这时要 book[x1][y2+1]+1, book[x2+1][y1]+1

    • 这里写图片描述

    • 这里红色的就是上面需要标记的点,标记后表示以这个点为左下角的子矩阵内的点全部取反一次。这里绿色代表取反一次,紫色是取反了两次,黄色是取反了四次。最后实际进行取反操作的就是要求取反的子矩阵内的点。

  • 注意这里的前缀和用二位树状数组维护,进行单点更新,单点查询。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cstring>
using namespace std;

const int MAX = 1123;
int data[MAX][MAX], n;

int lowbit(int x) {
return x&-x;
}

void Add(int x, int y, int w) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
data[i][j] += w;
}
}
}

int Sum(int x, int y) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans += data[i][j];
}
}
return ans;
}

int main() {
char str[10];
int T;
scanf("%d", &T);
while (T--) {
int k;
scanf("%d %d", &n, &k);
memset(data, 0, sizeof(data));
while (k--) {
scanf(" %s", str);
if (str[0] == 'C') {
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
Add(x1, y1, 1);
Add(x2+1, y1, 1);
Add(x1, y2+1, 1);
Add(x2+1, y2+1, 1);
}
else {
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", Sum(x, y)%2);
}
}
if (T)
printf("\n");
}
}

最长上升子序列(DP+模板)

题目链接:

http://poj.org/problem?id=1631


题目大意:

有两个不可描述的线段,每个上面有 n 个接口,现在给定了一个连接,求如果减去一些连接的话,最大的不交叉连接个数是多少。


解题过程:

省赛选拔赛的题,英文题面太长直接没看。
理解题意后挺简单的,只要找到规律。


题目分析:

要求最大的不交叉,可以找到一个规律,就是求不递减子序列,不过这里用 O(n^2) 的会超时,所以用了一个 O(nlongn) 的模板。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[40000+100];

int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, ans = 0, t;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &t);
if (!ans || t >= dp[ans-1])
dp[ans++] = t;
else
dp[lower_bound(dp, dp+ans, t)-dp] = t;
}
printf("%d\n", ans);
}
}

UVA - 1606 Amphiphilic Carbon Molecules(极角排序+扫描法+计算几何)

题目链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4481


题目大意:

平面上有 n 个点, 每个点为白点或黑点。现在需要放置一条隔板,使得隔板一侧的黑色点数加上另一侧白色点数的和最大。


解题过程:

这是人生第一道 AC 的计算几何题!
由于之前一直没接触过这种题,紫书上的分析也看不懂,一言不合就让我极角排序、叉乘,根本没学过啊QAQ。
然后翻了很多博客,重学了一下极坐标,可算是弄明白了。


题目分析:

首先这题最简单的想法是枚举所有可能的挡板,这样需要枚举两个点,然后统计两端的点。枚举是 n×n, 统计也是 n,总共时间复杂度是 n^3。显然是超时的。

然后扫描法的思想是,按照一定顺序枚举,这样可以动态的维护一个量,省去了扫描时的 n。

所以这题正解是枚举每一个点当作基点,然后计算每个点相对于基点的极角,进行极角排序。然后按极角的大小进行旋转时的枚举。每旋转一次可以根据之前统计的点的个数进行动态的更新(这就是“维护”)。

这题有个可以优化的地方,如果一个点是黑点的话,可以把他映射到关于基点对称的地方去,视为白点。这样扫描的时候只需要统计白点就够了。然后扫描的时候只从扫描 180 度即可。

判断是否超过 180 度用叉乘,a×b = |a| * |b| * sin<a,b>,两个点叉乘用坐标计算是,x1*y2 - y1*x2 因为向量的模一定是正的,所以只要判断这个叉乘正负,就可以判断 sin 的正负了,即是否超过 180 度。


AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1005;

struct Node {
int x, y;
int color;
double rad;
}raw_data[MAX], data[MAX];

bool operator < (const struct Node &a, const struct Node &b) {
return a.rad < b.rad;
}

int n, ans;

//用叉乘判断角度是否大于180度,即sin值。
bool Turn(Node &a, Node &b) {
return a.x * b.y >= a.y * b.x;
}

void solve() {
if (n <= 3) {
ans = n;
return;
}
ans = 0;

//枚举每一个点当多基点
for (int i = 0; i < n; i++) {
int k = 0;
for (int j = 0; j < n; j++) {
if (i == j)
continue;

//计算每个点关于基点的相对坐标。
data[k].x = raw_data[j].x - raw_data[i].x;
data[k].y = raw_data[j].y - raw_data[i].y;

//如果是黑点的话,那么映射到关于基点对称的地方,这样扫描的时候只记录白点就够了。
if (raw_data[j].color) {
data[k].x *= -1;
data[k].y *= -1;
}
//求极角
data[k].rad = atan2(data[k].y, data[k].x);
k++;
}

//极角排序
sort(data, data + k);

//L为与基点相连的点,R为扫描线。
int L = 0, R = 0, cnt = 1;

//枚举每一个点与基点相连当作挡板。
while (L < k) {
if (L == R) {
R = (R + 1) % k;
cnt++;
}

//扫描的时候只扫描一侧,保证扫描线与挡板的夹角不超过180度。
while (L != R && Turn(data[L], data[R])) {
cnt++;
R = (R + 1) % k;
}
ans = max(ans, cnt);
//挡板旋转。
L++;
//由于挡板旋转,与基点相连的点不在挡板上了,减去1。
cnt--;
}
}
}

int main() {
while (cin >> n && n) {
for (int i = 0; i < n; i++) {
cin >> raw_data[i].x >> raw_data[i].y >> raw_data[i].color;
}
solve();
cout << ans << endl;
}
}

社交网络图中结点的“重要性“计算(Dijkstra + SPFA + Floyd + 模板)

题目链接:

题目大意:

求一个点到其他所有点的最短距离和,保证图连通。

解题过程:

刚开始用 Floyd 水过的,后来用换了几种方法,不错的模板题,Floyd 的时候,要用 vector 存边,否则超内存。


题目分析


AC代码(Dijkstra + SPFA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;

const int MAX = 11234, INF = 0x3f3f3f3f;

vector<int> edges[MAX];
int dist[MAX], book[MAX];

void spfa(int s) {
memset(dist, INF, sizeof(dist));
memset(book, 0, sizeof(book));

queue<int> q;
q.push(s);
book[s] = 1;
dist[s] = 0;

while (!q.empty()) {
int u = q.front();
for (int i = 0; i < edges[u].size(); i++) {
int v = edges[u][i];
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
if (!book[v]) {
q.push(v);
book[v] = 1;
}
}
}
q.pop();
book[u] = 0;
}
}

void dijkstra(int s) {
memset(dist, INF, sizeof(dist));
priority_queue<pair<int, int> > q;
dist[s] = 0;
q.push(make_pair(-dist[s], s));
while (!q.empty()) {
int u = q.top().second;
q.pop();

for (int i = 0; i < edges[u].size(); i++) {
int v = edges[u][i];
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.push(make_pair(-dist[v], v));
}
}
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
edges[u].push_back(v);
edges[v].push_back(u);
}
int k;
scanf("%d", &k);
while (k--) {
int s;
scanf("%d", &s);
dijkstra(s);
int sum = 0;
for (int i = 1; i <= n; i++) {
if (i == s)
continue;
sum += dist[i];
}
printf("Cc(%d)=%.2f\n", s, (n-1.0)/sum);
}
}

AC代码(Floyd):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAX = 10001;

int main()
{
vector<int>edge[MAX];
int n, m;
scanf("%d %d", &n, &m);

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
edge[i].push_back(INF);
}
}

for (int i = 1; i <= n; i++) {
edge[i][i] = 0;
}

for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
edge[u][v] = edge[v][u] = 1;
}

for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (edge[i][j] > edge[i][k] + edge[k][j])
edge[i][j] = edge[i][k] + edge[k][j];
}
}
}

int k;
scanf("%d", &k);
while (k--) {
int c;
scanf("%d", &c);
double sum = 0;
for (int i = 1; i <= n; i++) {
if (i == c)
continue;
sum += edge[c][i];
}
printf("Cc(%d)=%.2f\n", c, (n-1)/sum);
}
}

STL在使用算法竞赛中的使用方法 (教程+未完成)

前言:

  • 本文面向已有 C 语言和部分算法基础的同学。
  • 内容均是个人总结,由于还没有系统的学习过 C++ 的面向对象,也没有翻过 STL 的代码,均以实用的角度来讲,可能不严谨些。
  • 接下来介绍的将是一些 C++ STL 容器的使用,特性及一些常用函数。然后还有部分好用的函数。都会以介绍加代码样例的方式写出。

STL:


Vector:


简介:

Vector 可以看做是一个不定长数组,可以对其进行插入元素,删除元素,按下标访问等基本操作。

重要的一点 Vector 是一个数组 而不是一个链表,例如对 Vector 进行插入操作,是基于元素的移位进行的,是 O(n)的复杂度而不是链表的 O(1),但是在其尾部添加元素时是 O(1),应该是内部可以自动优化。

vector 包含在 <vector> 头文件中。


基本操作:

首先创建一个 装着 int 类型元素的 vector。
ps:<int>这里其实是使用了模板,具体看概念中的模板部分。

1
vector<int> data;

接下来给 vector 添加元素,这里先向尾部添加元素,也是最常用的添加元素方式。
ps:这里添加是O(1)

1
2
3
data.push_back(1);
data.push_back(2);
data.push_back(3);

接下来可以用下标访问 vector 里面的元素,和数组类似,输出之前插入的1,2,3

1
2
3
cout << data[0] << endl;
cout << data[1] << endl;
cout << data[2] << endl;

接下来是插入元素和删除元素。下面的插入是把 t 插入到 下标为 i 的位置上,原来 i 位置及其后面的元素,都往后移一位。删除是删除掉下标为 i 的元素,后面的元素全部前移一位
ps:时间复杂度O(n)

1
2
data.insert(data.begin() + i, t);
data.erase(data.begin() + i);

定义 vector 数组时和普通类型一样使用即可

1
2
vector<int> example[112345];
example[233].push_back(666);

接下来是是一些常用的函数,将直接给出代码,代码中加入注释。

1
2
3
4
5
6
7
8
//返回 data 的大小,有 n 个元素即返回 n
data.size();

//清空 data,恢复 data 的初始状态
data.clear();

//重新设置 data 的长度,可用来直接截短
data.resize(len);


进阶技巧:

了解 vector 使用了模板后,其实 vector 可以用来存 vector 的,例如:

1
2
3
vector<vector<int> > example;
example.push_back(vector<int>());
example[0].push_back(1);

这里定义时 >> 用空格分开是编译器可能会把这里当成其他的关键字。
vector<int>() 表示定义一个空的储存 int 类型的 vector。
这里可能和 vector 数组有点类似,概念上是不同的,使用方法上也有差异。
同理 vector 也可以储存本文将要介绍的其他 STL 容器。


Map:


简介:

map容器常用来做映射,map的实现是用了数据结构的红黑树,通常来说是O(logn)比 hash 慢些,在一些时间限制不太紧的题中还是够用。
map 实现的是一种映射关系,详细见概念部分。

map 包含在头文件 <map> 中。

基本使用:

首先创建一个map,这里需要给定两个类型,一个是用来当做访问下标(暂且这样将)的,另一个是储存的数据类型。

部分概念:

本部分内容较啰嗦仅供读者更好的理解后面的 STL 如何工作,只希望了解 STL 用法可以直接略过。

模板:

关于模板这个概念。举个例子,大概意思是,如果要定义一个求两个函数和的函数,需要两个参数 a 和 b,然后返回他们的和。通常来讲我定义函数时如果参数设为 int,那么我这个函数就不可以为 double 类型求和。这时候我需要再为 double 定义一个求和函数。但是你会发现,无不需要关什么 int double 类型,只要输入进来的两个变量,只要定义了他们类型之间的加法应该是什么样子就可以了。

比如说输入两个整型和浮点型,直接返回他们的和就可以了。有了模板这个概念后,我甚至可以给这两个函数输入两个矩阵 a = [1,2,3,4], b = [2,2,3,4],求这两个矩阵的和,只要我定义好两个矩阵相加应该是什么样的规则就好了。

这样以后更深入的话,就可以知道,这样可以实现类的多态。
意思是给我两个你自己定义的 结构体/对象 我要求他的和,你只要定义好这个数据类型相加应该是什么样的就好了,不用再去定义一个函数。

接下来的 STL 容器都用了模板的概念,大概是 [容器名]<类型名> 这样的形式,然后类型那里可以随便填了(前提是有),int 也好,自己定义的结构体也好,运用上面的概念,STL 容器不关心他存的是上面类型,只要这个类型定义了某些运算应该符合什么样的规则就可以了。

迭代器:

这里可以当做指针对待,不再作详细介绍,[容器名].begin() 返回指向某容器首部的迭代器。

映射:

这里用数学里面的概念好了,意思是给定一个 x,对应一个唯一的 y。

亦可把 map 理解成一个下标为任意类型的数组,比如我可以用一个字符串当下标来储存一个整数。

这里用一下 Python 字典的概念好了,map 大概也是这个东西,map 中储存的是无数个 key:value 这样的键值对,不可存在同样的 key,访问 value,通过输入他的 key 来访问。