A. Game with Board

题意：

给出一个包含n个1的数组，Alice和Bob轮流操作（Alice先手），每次操作可以将若干个（最少为两个）不同的元素相加，组成一个新的元素插入数组中，同时删去被操作的元素。当轮到某名玩家时无法再进行操作，则该玩家获胜。

思路：

容易想到，当n=1时，Alice不能进行操作，此时Alice获胜。

当n=2时，Alice只能将两个1相加为2得到数组[2]，此时Bob获胜。

当n=3时，Alice只能将两个1相加为2，得到数组[1、2]，或者将三个1相加得到数组[3]，均为Bob获胜。

当n=4时，Alice将三个1相加得到数组[1，3]，此时Bob获胜，或者Alice将两个1相加得到[1、1、2]，此时Bob再将剩下的两个1相加得到数组[2、2]，回到形同n=2的情况，此时Bob获胜。

当n>4时，Alice可以将n - 2个1相加，得到[1、1、n - 2]，此时Bob只能将两个1相加得到数组[2、n - 2],所以Alice获胜。

B. Keep it Beautiful

题意：

若一个数组可以将开头若干个元素按照相同顺序插入到数组末尾，形成一个非递减数组，则称该数组为美丽数组。

初始数组为空，给出若干个元素，若将该元素放入数组可以得到美丽数组，则放入该元素并输出1，否则输出0。

思路：

按照题目要求模拟即可

代码：

 1 int a[N];
 2 void solve() {
 3     deque<int> q;
 4     int n;
 5     bool flag = false;
 6     cin>>n;
 7     for (int i = 1; i <= n; i++) {
 8         cin>>a[i];
 9         if (i == 1) {
10             q.push_back(a[i]);
11             cout<<"1";
12         }
13         else {
14             if (flag) {
15                 if (a[i] >= q.back() && a[i] <= q.front()) {
16                     cout<<"1";
17                     q.push_back(a[i]);
18                 } else {
19                     cout<<"0";
20                 }
21             } else {
22                 if (a[i] >= q.back()) {
23                     cout<<"1";
24                     q.push_back(a[i]);
25                 } else {
26                     if (a[i] <= q.front()) {
27                         q.push_back(a[i]);
28                         cout<<"1";
29                         flag = true;
30                     } else {
31                         cout<<"0";
32                     }
33                 }
34             }
35         }
36     }
37     cout<<"\n";
38 }

C. Ranom Numbers

题意：

一串只包含A到E的字符串，其中A表示1，B表示10,......,E表示10000。字符串大小表示按照字符串顺序进行相加减，若某字符后面存在比该字符大的字符，则该字符表示的数字前的符号为 - ，否则为 +。

给出一个字符串，允许替换一个字符（可以不替换），求进行操作后的字符串表示的最大值。

思路：

容易发现，当出现多个相同字符时，修改字符串中的字符得到的值总是不如修改两端该字符得到的值。因此，我们只需要找到开头与结尾的A、B、C、D、E，枚举每次修改的情况，找到其中得到的最大值即为答案。

代码：

 1 const int INF = 0x3f3f3f3f3f3f3f3fLL;
 2 int a[N];
 3 int trash(char a) {
 4     if (a == 'A')
 5         return 1;
 6     if (a == 'B')
 7         return 10;
 8     if (a == 'C')
 9         return 100;
10     if (a == 'D')
11         return 1000;
12     if (a == 'E')
13         return 10000;
14     return 0;
15 }
16 int love(string s) {
17     int len = s.size();
18     char mmax = 'A';
19     int sum = 0;
20     for (int i = len - 1; i >= 0; i--) {
21         if (s[i] < mmax) {
22             sum -= trash(s[i]);
23         } else {
24             sum += trash(s[i]);
25             mmax = s[i];
26         }
27     }
28     return sum;
29 }
30 void solve() {
31     string s;
32     cin>>s;
33     int ans = -INF;
34     for (char i = 'A'; i <= 'E'; i++) {
35         if (s.find(i) != string :: npos) {
36             int x = s.find(i);
37             string s1 = s;
38             for (char j = 'A'; j <= 'E'; j++) {
39                 s1[x] = j;
40                 ans = max(ans, love(s1));
41             }
42         }
43     }
44     for (char i = 'A'; i <= 'E'; i++) {
45         if (s.rfind(i) != string :: npos) {
46             int x = s.rfind(i);
47             string s1 = s;
48             for (char j = 'A'; j <= 'E'; j++) {
49                 s1[x] = j;
50                 ans = max(ans, love(s1));
51             }
52         }
53     }
54     cout<<ans<<"\n";
55 }

D. Pairs of Segments

题意：

一个数组中每个元素包含 [l, r] ，若数组中元素可以组成若干对，每对元素具有交集，不同对元素不存在交集，则称该数组为美丽数组。

给出一个数组，删掉若干个元素使该数组成为美丽数组，求需要删掉的最少的元素数量。

思路&代码：

 1 bool cmp(pair<int, int> a, pair<int, int> b) {
 2     if (a.first == b.first) 
 3         return a.second < b.second;
 4     return a.first < b.first;
 5 }
 6 //dp[i]表示i作为一个新的组合的第一个元素时，前i-1个元素可以组成的最大数量
 7 int dp[2005];
 8 void solve() {
 9     int n;
10     cin>>n;
11     memset(dp, 0, sizeof(dp));
12     vector<pair<int, int>> a(n + 1);
13     for (int i = 1; i <= n; i++) {
14         cin>>a[i].first>>a[i].second;
15     }
16     sort(a.begin() + 1, a.end(), cmp);
17     for (int i = 1; i <= n; i++) {
18         //找到前i - 1个元素组成的最大数量，i为一个新的组合的第一个元素
19         dp[i] = max(dp[i], dp[i - 1]);
20         for (int j = i + 1; j <= n; j++) {
21             if (a[i].second >= a[j].first) {
22                 //第i个元素和第j个元素可以组成一个新的组合。同时k作为下一个组合的第一个元素,所以a[k].first > max(a[i].second, a[j].second)
23                 int k = lower_bound(a.begin() + 1, a.end(), make_pair(max(a[i].second, a[j].second) + 1, 0), cmp) - a.begin();
24                 dp[k] = max(dp[k], dp[i] + 2);
25             } else
26                 break;
27         }
28     }
29     cout<<n - max(dp[n], dp[n + 1])<<"\n";
30     return ;
31 }