[Nowcoder]2020牛客寒假算法基础集训营4

20200211 第四场

进度（4 / 10）未完成：C / F / G / H / I / J

A、欧几里得

1、链接

https://ac.nowcoder.com/acm/contest/3005/A

2、题面

欧几里得算法是一种求最大公约数的有效算法，在算法竞赛中很常用。

这个算法的 Python 实现如下：

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

现在，如果已知 gcd(a,b) 共递归了 n次，求所有可能的a,b中满足a>b>=0且a+b最小的一组的a与b之和。

3、思路

打表找规律。然后就发现是个斐波那契数列了。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 105
 5 typedef long long ll;
 6 
 7 ll a[MAXN], b[MAXN], mx, t;
 8 
 9 int main() {
10     cin >> t;
11     for (int i = 1; i <= t; i++) cin >> a[i], mx = max(a[i], mx);
12     b[0] = 1, b[1] = 3, b[2] = 5;
13     for (int i = 3; i <= mx; i++) b[i] = b[i - 1] + b[i - 2];
14     for (int i = 1; i <= t; i++) cout << b[a[i]] << endl;
15     return 0;
16 }

B、括号序列

1、链接

https://ac.nowcoder.com/acm/contest/3005/B

2、题面

注意：数据已加强并进行了rejudge

给出一个仅包含'[',']','(',')','{','}'六种字符的括号序列，判断其是否合法。

空串是一个合法的括号序列
如果A, B 都是合法的括号序列，那么AB也是合法的括号序列
如果A是合法的括号序列，(A) , [A], {A}都是合法的括号序列

3、思路

标准栈问题。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 1000005
 5 
 6 stack <int> s;
 7 char ch[MAXN];
 8 int l;
 9 
10 int main() {
11     cin >> ch + 1, l = strlen(ch + 1);
12     for (int i = 1; i <= l; i++) {
13         if (ch[i] == '(' || ch[i] == '[' || ch[i] == '{') s.push(ch[i]);
14         else {
15             if (s.empty()) cout << "No", exit(0);
16             int o = s.top();
17             if (ch[i] == ')' && o == '(' || ch[i] == ']' && o == '[' || ch[i] == '}' && o == '}') s.pop();
18             else cout << "No", exit(0);
19         }
20     }
21     cout << (s.empty() ? "Yes" : "No");
22     return 0;
23 }

D、子段异或

1、链接

https://ac.nowcoder.com/acm/contest/3005/D

2、题面

输入一个数列a，你需要输出其中异或值为0的不同子段的数量。一个子段 [l,r] (1≤l≤r≤n)的异或值为al⊕al+1⊕al+2⊕…⊕ar，其中⊕符号代表异或运算。

两个子段被视为相同的，当且仅当其开始和结束位置均对应相同。

3、思路

先求了一下前缀异或s[]，发现当且仅当s[l - 1] = s[r]，[l, r]的异或值为0，则记录下所有前缀异或值，用map记录每一个出现过的值和出现次数，如果出现次数为i，则可以得到(i - 1) * i / 2个满足条件的子段。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 200005
 5 typedef long long ll;
 6 
 7 map <ll, ll> mp;
 8 ll a[MAXN], b[MAXN], n, c[MAXN], o, ans;
 9 
10 int main() {
11     cin >> n;
12     for (int i = 1; i <= n; i++) cin >> a[i];
13     b[1] = a[1], mp[0] = 0, c[0]++;
14     for (int i = 1; i <= n; i++) {
15         b[i] = i == 1 ? a[i] : b[i - 1] ^ a[i];
16         if (!mp.count(b[i])) mp[b[i]] = ++o;
17         c[mp[b[i]]]++;
18     }
19     for (int i = 0; i <= o; i++) ans += c[i] * (c[i] - 1) / 2;
20     cout << ans;
21     return 0;
22 }

E、最小表达式

1、链接

https://ac.nowcoder.com/acm/contest/3005/E

2、题面

给出一个包含数字1-9和加号的字符串，请你将字符串中的字符任意排列，但每种字符数目不变，使得结果是一个合法的表达式，而且表达式的值最小。输出那个最小表达式的值

合法的表达式的定义如下：

- 一个数字，如233，是一个合法的表达式

- A + B是合法的表达式，当且仅当 A , B 都是合法的表达式

保证给出的表达式经过重排，存在一个合法的解。

3、思路

首先将数字和加号分离，由于使总和最小，所有尽可能使数平均。设加号的个数x，则分出的数的个数为x - 1。将数字从大到小排列，然后从个位开始依次将这些数字填入这x - 1个数，可证这样总和最小。

4、代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAXN 500005
 5 
 6 int ans[MAXN], x = 1, l, hav;
 7 char ch[MAXN];
 8 
 9 struct cmp {
10     bool operator () (char a, char b) {
11         return a > b;
12     }
13 } cmpx;
14 
15 int main() {
16     cin >> ch + 1, l = strlen(ch + 1);
17     sort(ch + 1, ch + l + 1, cmpx);
18     while (ch[l] == '+') x++, l--;
19     for (int i = 0; i < l / x; i++)
20         for (int j = 1; j <= x; j++) {
21             ans[i] += ch[i * x + j] - '0'; 
22             ans[i + 1] += ans[i] / 10, ans[i] %= 10;
23         }
24     if (l % x)
25         for (int i = 1; i <= l % x; i++) {
26             ans[l / x] += ch[l / x * x + i] - '0';
27             ans[l / x + 1] += ans[l / x] / 10, ans[l / x] %= 10;
28         }
29     for (int i = l / x + 1; i >= 0; i--) 
30         if (ans[i] || hav) cout << ans[i], hav = 1;
31     return 0;
32 }