信息学奥赛-提高级 题库

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}
(匠人的自我修养)一个匠人决定要学习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;
}

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}
(匠人的自我修养)一个匠人决定要学习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;
}