2018 ACM-ICPC Asia Beijing Regional Contest (部分题解)

时间:2021-12-09 04:24:20

摘要

  本文主要给出了2018 ACM-ICPC Asia Beijing Regional Contest的部分题解,意即熟悉区域赛题型,保持比赛感觉。


 

Jin Yong’s Wukong Ranking List

题意

输入关系组数n和n组关系,每组关系是s1 > s2,问第一出现矛盾的组,或者没有矛盾就输出0.

解题思路

第一感觉是拓扑排序,未完,又写了一个深搜的传递闭包,1 A,和2018年河南省赛的题很像。

代码

 1 #include <cstdio>
 2 #include <map>
 3 #include <cstring>
 4 #include <string>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 const int maxn = 31;
 9 
10 int e[maxn][maxn];
11 int n, r;
12 bool f;
13 map<string, int> mp;
14 
15 void F(int a, int u) {
16     //printf("%d %d\n", a, u);
17     if(e[u][a]) {
18         f = 1;
19         return;
20     }
21     e[a][u] = 1;
22     for(int i = 0; i < r; i++) {
23         if(e[u][i]) {
24             F(a, i);
25             if(f)
26                 return;
27         }
28     }
29 }
30 
31 int main()
32 {
33     char s1[maxn], s2[maxn];
34     string s3, s4, s5, s6;
35     while(scanf("%d", &n) != EOF) {
36         mp.clear();
37         memset(e, 0, sizeof(e));
38         r = 0;
39         f = 0;
40 
41         for(int i = 0; i < n; i++) {
42             scanf("%s%s", s1, s2);
43             s3 = s1;
44             if(mp.find(s3) == mp.end()) {
45                 mp[s3] = r++;
46             }
47             s4 = s2;
48             if(mp.find(s4) == mp.end()) {
49                 mp[s4] = r++;
50             }
51             if(f == 0) {
52                 F(mp[s3], mp[s4]);
53                 if(f == 1) {
54                     s5 = s3;
55                     s6 = s4;
56                 }
57             }
58         }
59         if(f)
60             cout<<s5<<" "<<s6<<endl;
61         else
62             printf("0\n");
63     }
64     return 0;
65 }

Palindromes

题意

输出第k个回文数

解题思路

因为k的位数最长是1e5,所以试图根据给出的k找到结果,打表找出两者之间的规律。

首先长度为1时,减1输出;

然后s[0] == '1' && s[1] == '0'时,用9替换这两位,找规律回文输出;(注意特判一下10的情况)

再然后s[0] == '1' && s[1] == 'x'时(其中x是1到9任意一个数字),去掉s[0],找规律回文输出;

最后将s[0] - 1,找规律回文输出。

代码

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxn = 1e5 + 10;
 5 char s[maxn];
 6 
 7 int main()
 8 {
 9     int T;
10     scanf("%d", &T);
11     while(T--) {
12         scanf("%s", &s);
13         int l = strlen(s);
14         if(l == 1)
15             printf("%d\n", s[0] - '0' - 1);
16         else if(s[0] == '1' && s[1] == '0') {
17             putchar('9');
18             if(l > 2) {
19                 for(int i = 2; i < l; i++) {
20                     printf("%c", s[i]);
21                 }
22                 for(int i = l - 2; i >= 2; i--) {
23                     printf("%c", s[i]);
24                 }
25                 putchar('9');
26             }
27             puts("");
28         }
29         else if(s[0] == '1') {
30             for(int i = 1; i < l; i++) {
31                 printf("%c", s[i]);
32             }
33             for(int i = l - 1; i >= 1; i--) {
34                 printf("%c", s[i]);
35             }
36             puts("");
37         } else {
38             putchar((s[0] - '0' - 1) + '0');
39             for(int i = 1; i < l; i++) {
40                 printf("%c", s[i]);
41             }
42             for(int i = l - 2; i >= 1; i--) {
43                 printf("%c", s[i]);
44             }
45             putchar((s[0] - '0' - 1) + '0');
46             puts("");
47         }
48     }
49     return 0;
50 }

Frog and Portal

题意

给出从0上到200的方案数n,求搭建哪几条通道能够使得方案数恰好为n

解题思路

由于多种方案输出任意一种均可,所以我们采用先使用传送门,然后用后面的台阶凑方案数的方法,每次找到小于等于n离最近的斐波那契数F[x],然后连接1到(200 - x),然后跳过2,如果还需凑数,再找到小于等于离n - F[x]最近的斐波那契数F[y],然后3连接到(200 - y),直到凑够为止,最后添加一条下一个台阶自闭的通道即可。

代码

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 typedef pair<ll, ll> pir;
 7 
 8 ll f[110];
 9 
10 ll id(ll x) {
11     for(int i = 1; i < 80; i++) {
12         if(x < f[i]) {
13             return i - 1;
14         }
15     }
16 }
17 
18 int main()
19 {
20     f[1] = 1;
21     f[2] = 2;
22     for(int i = 3; i < 80; i++) {
23         f[i] = f[i - 1] + f[i - 2];
24     }
25 
26     ll n;
27     vector<pir> v;
28     while(scanf("%lld", &n) != EOF) {
29         if(0 == n) {
30             printf("2\n1 1\n2 2\n");
31             continue;
32         }
33         v.clear();
34         ll i;
35         for(i = 1; ; i += 2) {
36             int x = id(n);
37             v.push_back(pir(i, 200 - x));
38             n -= f[x];
39             if(0 == n)
40                 break;
41         }
42         v.push_back(pir(i + 1, i + 1));
43 
44         printf("%d\n", v.size());
45         for(i = 0; i < v.size(); i++) {
46             printf("%lld %lld\n", v[i].first, v[i].second);
47         }
48     }
49     return 0;
50 }

Heshen's Account Book

题意

输入一些含有空格,数字和小写字母的字符,计算并输出有哪些actual数

解题思路

细节题,先整合成一行字符处理,具体就是前一行末尾是数字并且后一行开头是数字就直接连接,否则加一个空格分开。然后记录每个字母在哪一行上,便于最后输出。最后分隔判断处理。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int ll;
 4 const int MAXN=1000100;
 5 int num[MAXN];
 6 vector<ll> ans;
 7 int pos[MAXN];
 8 string str;
 9  
10 pair<ll,int> check(int l,int r){
11     
12     for(int i=l;i<=r;i++){
13         if(str[i]>='a'&&str[i]<='z')
14             return {-1,0};
15     }
16  
17     ll cur=0;
18     if(str[l]=='0'&&l==r){
19         return {0,pos[l]};
20     }
21     else{
22         if(str[l]=='0'&&l!=r)
23             return {-1,0};
24     }
25  
26     for(int i=l;i<=r;i++){
27         cur=cur*10ll+ll(str[i]-'0');
28     }
29     return {cur,pos[l]};
30 }
31  
32 int main(){
33     
34     char c;
35     int line=0;
36     int len=0;
37     char last=0;
38  
39     while(~scanf("%c",&c)){
40         if(c=='\n')
41         {
42             if(last>='a'&&last<='z'){
43                 str.push_back(' ');
44                 pos[len++]=line;
45             }
46             line++;
47         }
48         else{
49  
50             if(last=='\n'&&c>='a'&&c<='z'){
51                 str.push_back(' ');
52                 pos[len++]=line;
53             }
54  
55             str.push_back(c);
56             pos[len++]=line;
57         }
58         last=c;
59     }
60     str.push_back(' ');
61     pos[len++]=line;
62  
63  
64     int l=-1,r=-1;
65     for(int i=0;i<len;i++){
66         if((str[i]>='a'&&str[i]<='z')||(str[i]>='0'&&str[i]<='9')){
67             if(l==-1){
68                 l=i;
69             }
70         }
71         else{
72             if(l!=-1){
73                 r=i-1;
74                 pair<ll,int> t=check(l,r);
75                 if(t.first!=-1){
76                     num[t.second]++;
77                     ans.push_back(t.first);
78                 }
79                 l=-1,r=-1;
80             }
81         }
82     }
83     
84     for(int i=0;i<ans.size();i++){
85         if(ans.size()-1==i)
86             cout<<ans[i]<<endl;
87         else
88             cout<<ans[i]<<" ";
89     }
90  
91     for(int i=0;i<=line;i++)
92         cout<<num[i]<<endl;
93     
94     return 0;
95 }