首页 › 题库 › 信息学奥赛 › 1.4 并查集

信息学奥赛-提高级 题库

共 4 道题 · 按题型筛选,点「查看答案」核对解析
1 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

01 #include <iostream>

02 #include <queue>

03 using namespace std;

04

05 const int max1 = 2000000000;

06

07 class Map (

08 struct item {

09 string key; int value;

10} d[max1];

11int cnt;

12public:

13int find(string x) {

14for (int i = 0; i < cnt; ++i)

15if (d[i].key == x)

16return d[i].value;

17return -1;

18}

19static int end() { return -1; } 

20void insert(string k, int v) {

21d[cnt].key = k; d[cnt++].value = v; 

22}

23} s[2];

24

25class Queue {

26string q[max1];

27int head, tail;

28public:

29void pop() { ++head; }

30string front() { return q[head + 1]; } 

31bool empty() { return head == tail; } 

32void push(string x) { q[++tail] = x; } 

33} q[2];

34

35string st0,stl;

36int m;

37

38string LtoR(string s, int L, int R) { 

39string t = s;

40char tmp = t[L];

41for (int i = L; i < R; ++i)

42t[i] = t[i + 1];

43t[R] = tmp;

44return t;

45}

46

47string RtoL(string s, int L,int R) { 

48string t = s;

49char tmp = t[R];

50for (int i = R; i > L; --i)

51t[i] = t[i - 1];

52t[L] = tmp;

53return t;

54}

55

56bool check(string st, int p,int step) { 

57if (s[p].find(st) != s[p].end()) 

58return false;

59++step;

60if (s[p ^ 1].find(st) == s[p].end()) { 

61s[p].insert(st, step); 

62q[p].push(st);

63return false;

64}

65cout << s[p ^ 1].find(st) + step << end1; 

66return true;

67}

68

69int main() {

70cin >> st0 >> stl;

71int len = st0.length();

72if (len != stl.length()) { 

73cout << -1 << end1; 

74return 0;

75}

76if (st0 == st1) { 

77cout << 0 << end1; 

78return 0;

79}

80cin >> m;

81s[0].insert(st0, 0); s[1].insert(st1, 0); 

82q[0].push(st0); q[1].push(st1);

83for (int p = 0;

84!(q[0].empty() && q[1].empty());

85p ^=1) {

86string st - q[p].front(); q[p].pop();

87int step = s[p].find(st);

88if ((p == 0 &&

89(check(LtoR(st,m, len - 1), p, step) || 

90check(RtoL(st, 0, m), p, step)))

91|| 

92(p == 1 &&

93(check(LtoR(st,0, m), p, step) || 

94check(RtoL(st, m, len - 1), p, step)))) 

95return 0;

96}

97cout << -1 << end1; 

98return 0;

99}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
2 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤107)。

接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值(≤107),以及学会第i个技术后可获得的经验值(≤104)。

接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n2)的时间复杂完成这个问题,试补全程序。

#inclde

using namesoace std;

const int maxn = 1001;


int n;

int cnt [maxn]

int child [maxn] [maxn];

int unlock[maxn];

int unlock[maxn];

int threshold [maxn],bonus[maxn];


bool find(){

int target=-1;

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

if(①&&②){

target = i;

break;

}

if(target-1)

return false;

unlock[target]=-1;

③;

for (int i=0;i<cut[target];++i)

④;

return true;

}


int main(){

scanf(“%d%d”,&n, &points);

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

cnt [i]=0;

scanf(“%d%d”,&threshold[i],&bonus[i];

}

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

int m;

scanf(“%d”,&m);

⑤;

for (int j=0; j<m ;++j={

int fa;

scanf(“%d”, &fa);

child [fa][cnt[fa]]=i;

++cnt[fa];

}

}

int ans = 0;

while(find())

++ans;

printf(“%d\n”, ans);

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
3 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

01 #include <iostream>

02 #include <queue>

03 using namespace std;

04

05 const int max1 = 2000000000;

06

07 class Map (

08 struct item {

09 string key; int value;

10} d[max1];

11int cnt;

12public:

13int find(string x) {

14for (int i = 0; i < cnt; ++i)

15if (d[i].key == x)

16return d[i].value;

17return -1;

18}

19static int end() { return -1; } 

20void insert(string k, int v) {

21d[cnt].key = k; d[cnt++].value = v; 

22}

23} s[2];

24

25class Queue {

26string q[max1];

27int head, tail;

28public:

29void pop() { ++head; }

30string front() { return q[head + 1]; } 

31bool empty() { return head == tail; } 

32void push(string x) { q[++tail] = x; } 

33} q[2];

34

35string st0,stl;

36int m;

37

38string LtoR(string s, int L, int R) { 

39string t = s;

40char tmp = t[L];

41for (int i = L; i < R; ++i)

42t[i] = t[i + 1];

43t[R] = tmp;

44return t;

45}

46

47string RtoL(string s, int L,int R) { 

48string t = s;

49char tmp = t[R];

50for (int i = R; i > L; --i)

51t[i] = t[i - 1];

52t[L] = tmp;

53return t;

54}

55

56bool check(string st, int p,int step) { 

57if (s[p].find(st) != s[p].end()) 

58return false;

59++step;

60if (s[p ^ 1].find(st) == s[p].end()) { 

61s[p].insert(st, step); 

62q[p].push(st);

63return false;

64}

65cout << s[p ^ 1].find(st) + step << end1; 

66return true;

67}

68

69int main() {

70cin >> st0 >> stl;

71int len = st0.length();

72if (len != stl.length()) { 

73cout << -1 << end1; 

74return 0;

75}

76if (st0 == st1) { 

77cout << 0 << end1; 

78return 0;

79}

80cin >> m;

81s[0].insert(st0, 0); s[1].insert(st1, 0); 

82q[0].push(st0); q[1].push(st1);

83for (int p = 0;

84!(q[0].empty() && q[1].empty());

85p ^=1) {

86string st - q[p].front(); q[p].pop();

87int step = s[p].find(st);

88if ((p == 0 &&

89(check(LtoR(st,m, len - 1), p, step) || 

90check(RtoL(st, 0, m), p, step)))

91|| 

92(p == 1 &&

93(check(LtoR(st,0, m), p, step) || 

94check(RtoL(st, m, len - 1), p, step)))) 

95return 0;

96}

97cout << -1 << end1; 

98return 0;

99}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
4 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤107)。

接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值(≤107),以及学会第i个技术后可获得的经验值(≤104)。

接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n2)的时间复杂完成这个问题,试补全程序。

#inclde

using namesoace std;

const int maxn = 1001;


int n;

int cnt [maxn]

int child [maxn] [maxn];

int unlock[maxn];

int unlock[maxn];

int threshold [maxn],bonus[maxn];


bool find(){

int target=-1;

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

if(①&&②){

target = i;

break;

}

if(target-1)

return false;

unlock[target]=-1;

③;

for (int i=0;i<cut[target];++i)

④;

return true;

}


int main(){

scanf(“%d%d”,&n, &points);

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

cnt [i]=0;

scanf(“%d%d”,&threshold[i],&bonus[i];

}

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

int m;

scanf(“%d”,&m);

⑤;

for (int j=0; j<m ;++j={

int fa;

scanf(“%d”, &fa);

child [fa][cnt[fa]]=i;

++cnt[fa];

}

}

int ans = 0;

while(find())

++ans;

printf(“%d\n”, ans);

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情