BestCoder赛码杯题解

1001 Movie (hdu 5214)

Problem Description

Cloud and Miceren like watching movies.
Today, they want to choose some wonderful scenes from a movie. A movie has N scenes can be chosen, and each scene is associate with an interval [L, R]. L is the beginning time of the scene and R is the ending time. However, they can’t choose two scenes which have overlapping intervals. (For example, scene with [1, 2] and scene with [2, 3], scene with [2, 5] and scene with[3, 4]).
Now, can you tell them if they can choose such three scenes that any pair of them do not overlap?
Since there are so many scenes that you can’t get them in time, we will give you seven parameters N, L1, R1, a, b, c, d, and you can generate L1 ~ LN, R1 ~ RN by these parameters.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case contains seven integers N, L1, R1, a, b, c, d, meaning that there are N scenes. The i-th scene’s interval is [Li, Ri]. L1 and R1 have been stated in input, and Li = (Li−1 ∗ a + b) mod 4294967296, Ri = (Ri−1 ∗ c + d) mod 4294967296.
After all the intervals are generated, swap the i-th interval’s Li and Ri if Li > Ri.
T is about 100.
1 ≤ N ≤ 10000000.
1 ≤ L1,R1 ≤ 2000000000.
1 ≤ a,b,c,d ≤ 1000000000.
The ratio of test cases with N > 100 is less than 5%.

Output

For each test, print one line.
If they can choose such three scenes, output “YES”, otherwise output “NO”.

Sample Input

2
3 1 4 1 1 1 1
3 1 4 4 1 4 1

Sample Output

NO
YES

Source

赛码”BestCoder”杯中国大学生程序设计冠军赛

题解

很水的一道题,和队友想了半天,结果被另一位队友点醒,真**水……
先生成序列,然后在里面找到最小的r和最大的l,之后O(N)查找l比minr大的同时r比maxl小的,若存在任意一个,则输出YES,否则NO。
注意trick:输入的L1不一定比R1小……
上队友的代码~~

源代码:

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned int uint;

struct interval
{
explicit interval(uint il = 0, uint ir = 0)
:l(il), r(ir)
{}

interval(const interval& x)
:l(x.l), r(x.r)
{}
uint l, r;
};

interval data[10000001];

int main()
{

int T = 0;
scanf("%d", &T);
while(T--)
{
uint n = 0, lnow = 0, rnow = 0;
uint a = 0, b = 0, c = 0, d = 0;
//scanf("%u%u%u%u%u%u%u", &n, &lnow, &rnow, &a, &b, &c, &d);
cin >> n >> lnow >> rnow >> a >> b >> c >> d;
uint lmax = min(lnow, rnow), rmin = max(lnow, rnow);
for(uint i = 0; i < n; ++i)
{
data[i].l = min(lnow, rnow);
data[i].r = max(lnow, rnow);
lmax = max(data[i].l, lmax);
rmin = min(data[i].r, rmin);
lnow = lnow * a + b;
rnow = rnow * c + d;
}
bool isok = false;
for(uint i = 0; i < n; ++i)
if(data[i].l > rmin && data[i].r < lmax)
{
isok = true;
break;
}
if(isok)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

1009 Exploration (hdu 5222)

Problem Description

Miceren likes exploration and he found a huge labyrinth underground!
This labyrinth has N caves and some tunnels connecting some pairs of caves.
There are two types of tunnel, one type of them can be passed in only one direction and the other can be passed in two directions. Tunnels will collapse immediately after Miceren passing them.
Now, Miceren wants to choose a cave as his start point and visit at least one other cave, finally get back to start point.
As his friend, you must help him to determine whether a start point satisfing his request exists.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with three integers N, M1, M2, indicating the number of caves, the number of undirectional tunnels, the number of directional tunnels.
The next M1 lines contain the details of the undirectional tunnels. Each line contains two integers u, v meaning that there is a undirectional tunnel between u, v. (u ≠ v)
The next M2 lines contain the details of the directional tunnels. Each line contains integers u, v meaning that there is a directional tunnel from u to v. (u ≠ v)
T is about 100.
1 ≤ N,M1,M2 ≤ 1000000.
There may be some tunnels connect the same pair of caves.
The ratio of test cases with N > 1000 is less than 5%.

Output

For each test queries, print the answer. If Miceren can do that, output “YES”, otherwise “NO”.

Sample Input

2
5 2 1
1 2
1 2
4 5
4 2 2
1 2
2 3
4 3
4 1

Sample Output

YES
NO

Hint

If you need a larger stack size, please use #pragma comment(linker, “/STACK:102400000,102400000”) and submit your solution using C++.

Source

赛码”BestCoder”杯中国大学生程序设计冠军赛

题解

就是dfs与并查集一起做,队友写的,貌似最终有点问题,不过能过。正解应该用并查集缩点。
上队友代码~~

源代码:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stack>
#include <stdio.h>
#include <vector>
#define MAXN 1000005
using namespace std;
int dfn[MAXN];
int vis[MAXN];
int judge[MAXN];
int head[MAXN];
int root[MAXN];
struct Edge
{
int to, next;
}edge[MAXN];
int n, m1, m2;
int num;
void add(int from, int to)
{

edge[num].to = to;
edge[num].next = head[from];
head[from] = num++;
}
int findRoot(int x)
{

if(x == root[x]) return x;
else
return root[x] = findRoot(root[x]);
}
void unite(int x, int y)
{

x = findRoot(x);
y = findRoot(y);
if(x != y) root[x] = y;
}
bool flag;
void dfs(int u)
{

dfn[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(judge[v])
{
flag = true;
break;
}
if(vis[findRoot(v)])
{
flag = true;
break;
}
if(!dfn[v])
{
judge[v] = 1;
vis[findRoot(v)] = 1;
dfs(v);
judge[v] = 0;
vis[findRoot(v)] = 0;
}
if(flag) break;
}
}
int main()
{

int t;
scanf("%d", &t);
while(t--)
{
flag = false;
scanf("%d%d%d", &n, &m1, &m2);
for(int i = 1; i <= n; i++) root[i] = i;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(dfn ,0 ,sizeof(dfn));
memset(judge, 0, sizeof(judge));
num = 0;
for(int i = 0; i < m1; i++)
{
int a, b;
scanf("%d%d", &a, &b);
if(findRoot(a) != findRoot(b))
{
unite(a, b);
}
else
{
flag = true;
}
}
for(int i = 0; i < m2; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
for(int i = 1; i <= n; i++)
if(!dfn[i] && !flag)
{
judge[i] = 1;
vis[findRoot(i)] = 1;
dfs(i);
vis[findRoot(i)] = 0;
judge[i] = 0;
}

if(flag) puts("YES");
else
puts("NO");
}
return 0;
}

1010 GCD (hdu 5223)

Problem Description

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.—-Wikipedia
BrotherK and Ery like playing mathematic games. Today, they are playing a game with GCD.
BrotherK has an array A with N elements: A1 ~ AN, each element is a integer in [1, 10^9]. Ery has Q questions, the i-th question is to calculate GCD(ALi, ALi+1, ALi+2, …, ARi), and BrotherK will tell her the answer.
BrotherK feels tired after he has answered Q questions, so Ery can only play with herself, but she don’t know any elements in array A. Fortunately, Ery remembered all her questions and BrotherK’s answer, now she wants to recovery the array A.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, Q, indicating the number of array A, and the number of Ery’s questions. Following Q lines, each line contains three integers Li, Ri and Ansi, describing the question and BrotherK’s answer.
T is about 10
2 ≤ N Q ≤ 1000
1 ≤ Li < Ri ≤ N
1 ≤ Ansi ≤ 10^9

Output

For each test, print one line.
If Ery can’t find any array satisfy all her question and BrotherK’s answer, print “Stupid BrotherK!” (without quotation marks). Otherwise, print N integer, i-th integer is Ai.
If there are many solutions, you should print the one with minimal sum of elements. If there are still many solutions, print any of them.

Sample Input

2
2 2
1 2 1
1 2 2
2 1
1 2 2

Sample Output

Stupid BrotherK!
2 2

Source

赛码”BestCoder”杯中国大学生程序设计冠军赛

题解

水题一个,把最小公倍数添进数组里就好了,代码队友敲的……
上队友代码~~

源代码:

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
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#define MAXN 1005
#define LL long long
using namespace std;
int g[MAXN][MAXN];
int n, q;
int gcd(int a, int b)
{

if(a % b == 0) return b;
else
return gcd(b, a % b);
}
struct Node
{
int l, r, ans;
}input[MAXN];
LL a[MAXN];
void work(int l, int r, int gg)
{

for(int i = l; i <= r; i++)
{
int temp = gcd(a[i], gg);
a[i] = a[i] * (LL)gg;
a[i] = a[i] / (LL)temp;
}
}
bool judge(int num)
{

int l = input[num].l, r = input[num].r, gg = input[num].ans;
int rr = a[l];
for(int i = l + 1; i <= r; i++)
{
rr = gcd(a[i], rr);
}
if(rr != gg) return false;
else
return true;
}
int main()
{

int t;
scanf("%d", &t);
while(t--)
{
bool flag = true;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++) a[i] = 1;
for(int i = 0; i < q; i++)
{
scanf("%d%d%d", &input[i].l, &input[i].r, &input[i].ans);
work(input[i].l, input[i].r, input[i].ans);
}
for(int i = 0; i < q; i++)
{
flag = judge(i);
if(!flag) break;
}
if(flag)
{
for(int i = 1; i <= n; i++)
{
if(i != 1) printf(" ");
printf("%I64d", a[i]);
}
puts("");
}
else
puts("Stupid BrotherK!");
}
return 0;
}