Rday21

Rday2

并查集 + 贪心 + CTF入门

Cyclic Components

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
You are given an undirected graph consisting of nn vertices and mm edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex aa is connected with a vertex bb, a vertex bb is also connected with a vertex aa). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices uu and vv belong to the same connected component if and only if there is at least one path along edges connecting uu and vv.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

the first vertex is connected with the second vertex by an edge,
the second vertex is connected with the third vertex by an edge,
...
the last vertex is connected with the first vertex by an edge,
all the described edges of a cycle are distinct.
A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

There are 66 connected components, 22 of them are cycles: [7,10,16][7,10,16] and [5,11,9,15][5,11,9,15].
`Input:`

The first line contains two integer numbers nn and mm (1≤n≤21051≤n≤2105, 0≤m≤21050≤m≤2105) — number of vertices and edges.

The following mm lines contains edges: edge ii is given as a pair of vertices vivi, uiui (1≤vi,ui≤n1≤vi,ui≤n, ui≠viui≠vi). There is no multiple edges in the given graph, i.e. for each pair (vi,uivi,ui) there no other pairs (vi,uivi,ui) and (ui,viui,vi) in the list of edges.

 

`Output:`

Print one integerthe number of connected components which are also cycles.
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
Example:

Input

5 4
1 2
3 4
5 4
3 5
Output

1
 

Input

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6
Output

2
 

Note:

In the first example only component [3,4,5][3,4,5] is also a cycle.

The illustration above corresponds to the second example.

题意:
1.
通过观察发现单圈环里的顶点的度都为2,所以并查集找连通图,sum存顶点度数,遍历查找单圈环。
2.
并查集判环大致就是在两个点进行unite操作时先判断一下父节点是否相同,
不相同的话就正常把两个点放进一个集合,如果相同,说明这两个点已经处于一个集合中了,再把这两个点联通,也就出现了环。

code:

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
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 2e5 + 7;
int n, m, ans;
int par[maxx] , sum[maxx];

struct edge{
int u, v;
};

void init(int n)
{
for(int i = 0; i < n; i ++)
par[i] = i;
}

int find(int x)
{
return par[x] == x ? x : par[x] = find(par[x]);
}

void join(int x, int y)
{
x = find(x);
y = find(y);
if(x != y) par[x] = y;
else ans ++;
}

int main()
{
while(cin >> n >> m)
{
memset(sum, 0, sizeof sum);
init(n);
ans = 0;
edge e[m];
for(int i = 0; i < m; i ++)
{
cin >> e[i].u >> e[i].v;
sum[e[i].u] ++;
sum[e[i].v] ++;
}
for(int i = 0; i < m; i ++)
{
if(sum[e[i].u] == 2 && sum[e[i].v] == 2)
{
join(e[i].u, e[i].v);
}
}
cout << ans << endl;
}

return 0;
}

P1094 纪念品分组

题目描述
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

输入格式
共n+2行:

第1行包括一个整数w,为每组纪念品价格之和的上上限。
第2行为一个整数n,表示购来的纪念品的总件数G。
第3至n+2行每行包含一个正整数P_i(5 <= P_i <= w)表示所对应纪念品的价格。

输出格式
一个整数,即最少的分组数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入输出样例
输入
100
9
90
20
20
30
50
60
70
80
90
输出
6
说明/提示
50%的数据满足:1 \le n \le 151≤n≤15

100%的数据满足:1 \le n \le 30000,80 \le w \le 2001≤n≤30000,80≤w≤200

题意:

1
很简单的一道贪心题,设一个"指针"l和r分别指向首和尾,首先排序,然后开始让a[l] + a[r] <= w的时候作为一组,l和r分别向后向前移一位,组数++,否则数组++,r--

code:

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
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;
int a[maxx];
int main()
{
int n, w;
cin >> w;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int ans = 0;
sort(a, a + n);
int l = 0, r = n - 1;
while(l <= r)
{
if((a[l] + a[r]) <= w)
{
ans ++;
l ++;
r --;
}
else
{
ans ++;
r --;
}
}
cout << ans << '\n';

return 0;
}

CTF:

一道来自Wargame.kr v2.1的SB题WTF_CODE
进去之后题目是

이게 진짜 소스코드라고? 아무것도 안보인다고!!

is this source code really???? i can`t see anything really!

然后你点击链接之后会让你下载一个文件,然后打开(用记事本就可以)之后你会发现里面什么都没有((艹皿艹 )),但是当你全选之后你会发现一个神奇的事情,全tm是空格是tab
然后你可能就和我一样,人直接就傻了
google一波后发现还有一个神奇的网站

(艹皿艹 )严重怀疑这两个网站是一伙的,然后在最下面的选择语言里面有一个Whitespace,选择它然后复制并粘贴之前的一堆“答案”,Run。拉倒最下面,就能得到答案了

---------------- The End ----------------
0%