题目链接：https://codeforces.com/contest/1573

A Countdown

题意：给定一个含前导零的字符串，每次可以选择将字符串的最后一位减一或者将字符串的其它位和最后一位置换。、

思路：模拟一下即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 3e5 + 100;

int n;
string s;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif 
    int T; cin>>T;
    while(T--)
    {
        cin>>n>>s;
        ll ans = 0;
        for(int i = 0; i < n-1; i++)
            if(s[i] != '0') ans += int(s[i]-'0')+1;
        ans += int(s[n-1]-'0');
        cout<<ans<<endl;
    }
    return 0;
}

B Swaps

题意:给定两个数组，数组a由奇数组成，数组b由偶数组成。可以在一个数组中任意交换两个连续的值，问使得数组a小于数组b的最小交换次数是多少。

思路：最优结果肯定是交换两个值分别到a和b数组的开头，满足a数组小于b数组。对a数组从小到大排序，然后遍历a数组，在b数组中第一次找到比a[i]大的值时，是一种满足a数组小于b数组的交换方式。由于a数组单调递增，所以b数组只用遍历一次。对所有合法的交换方式取最小值即为答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e5 + 100;

int n, b[N];
struct node 
{
    int x, idx;
    bool operator < (const node &b) const
    {
        return x < b.x;
    }
}a[N];


int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif 
    int T; cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 0; i < n; i++) cin>>a[i].x, a[i].idx = i;
        for(int i = 0; i < n; i++) cin>>b[i];
        sort(a, a+n);
        int j = 0, ans = inf;
        for(int i = 0; i < n; i++)
        {
            while(b[j] < a[i].x && j < n) j++;
            ans = min(ans, j+a[i].idx);
        }
        cout<<ans<<endl;
    }
    return 0;
}

C Book

题意：想读懂一本书,要读懂每一页。但是想读懂某一页的时候要先读过指定的几页。问最少要从前往后读几轮能把整本书读懂。

思路：拓扑排序加dp。dp[i]存读到第i页时最小是第几轮。状态转移方程，dp[v] = max(dp[v], dp[u]+(u>v))（要读第v页，需要先读第u页）。+ (u>v)是为了控制：若第u页在第v页前面(u<v)，则这两页是在同一轮读的；反之，要先读第u页，再在dp[u]的下一轮读第v页（u>v）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 2e5 + 100;

int n, in[N], dp[N];
queue<int> q;
vector<int> ans;
vector<int> edge[N];

void tuopo()
{
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int k; cin>>k;
        while(k--)
        {
            int x; cin>>x;
            edge[x].push_back(i);
            in[i]++;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(!in[i]) 
        {
            q.push(i);
            dp[i] = 1;
        }
    }

    while(q.size())
    {
        int u = q.front(); q.pop();
        // ans.push_back(u);
        for(auto v : edge[u])
        {
            in[v]--;
            dp[v] = max(dp[v], dp[u]+(u>v));
            if(!in[v]) q.push(v);
        }
    }    
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif 
    int T; cin>>T;
    while(T--)
    {
        for(int i = 1; i <= n; i++) edge[i].clear();
        while(q.size()) q.pop();
        // ans.clear();
        mem(dp, 0);
        mem(in, 0);
        tuopo();
        int flag = 0, cnt = -inf;
        for(int i = 1; i <= n; i++)
        {
            if(in[i]) flag = 1;
            cnt = max(cnt, dp[i]);
        }
        if(flag) cout<<-1<<endl;
        else cout<<cnt<<endl;
    }
    return 0;
}

D Xor of 3

题意：给定一个由0或1组成的数组，定义一种操作：把$a_{i}$, $a_{i+1}$, $a_{i+2}$ 变为$a_{i}$⊕$a_{i+1}$⊕$a_{i+2}$的结果（1<=i<=n-2）。问是否可以通过这种操作将给定的数组全部变为0，如果不可以，输出NO；否则在第一行输出YES，第二行输出选择的下标个数，第三行输出选择的下标。

思路：首先，对于连续的三个数字来说，只有两个1和一个0，亦或的结果才是0。所以只有当1的个数是偶数时，才有可能实现。
然后，分析一段连续出现的1的个数
（1）当这一位前面1的个数为奇数时（这一位为0），枚举下一位的可能情况，当下一位为0，则出现了偶数个1和1 0 0，这时选择将1 0 0变为 1 1 1，继续向后枚举；当下一位为1，则出现了偶数个1和1 0 1，则可以将其全部变为0。
（2）当这一位前面1的个数为偶数时（这一位为0），则出现了 偶数个1和1个0（110），这时可以从后往前间隔两位选1，变成0 0 0，则前面的所有值都变成了0
最后，需要特判一种情况，即最后变为偶数个1时没有0了（1 0 0 1 –> 1 1 1 1）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 2e5 + 100;

int n, a[N], sum[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif 
    int T; cin>>T;
    while(T--)
    {
        cin>>n;
        int cnt = 0;
        for(int i = 1; i <= n; i++) 
        {
            cin>>a[i];
            sum[i] = sum[i-1]+a[i];
            if(a[i] == 1) cnt++;
        }
        if(cnt%2) 
        {
            cout<<"NO"<<endl;
            continue;
        }
        cnt = 0;
        vector<int> ans;
        for(int i = 1; i <= n; i++)
        {
            if(a[i]) cnt++;
            // 前面有奇数个1，本身是0
            else if(cnt%2)
            {
                if(!a[i+1])     // 100
                {
                    ans.push_back(i-1);
                    a[i] = 1;
                    a[i+1] = 1;
                    cnt++;  // a[i+1]变成1之后cnt还会+1，所以这里+1
                }
                else    // 101
                {
                    a[i-1] = 0;
                    a[i+1] = 0;
                    for(int j = i-1; j >= i-cnt; j -= 2)
                    {
                        ans.push_back(j);
                        a[j] = a[j+1] = 0;
                    }
                    cnt = 0;
                }
            }
            else // 前面偶数个1，本身为0  110
            {
                for(int j = i-2; j >= i-cnt; j -= 2)
                {
                    ans.push_back(j);
                    a[j] = 0;
                    a[j+1] = 0;
                }
                cnt = 0;
            }
        }
        if(cnt)
        {
            if(cnt == n)
            {
                cout<<"NO"<<endl;
                continue;
            }
            for(int i = n-cnt; i <= n-2; i +=2 ) ans.push_back(i);
        }
        cout<<"YES"<<endl;;
        cout<<ans.size()<<endl;
        for(int i : ans) cout<<i<<" ";
        if(ans.size()) cout<<endl;
    }
    return 0;
}

E Paint

(整理ing…)
题意：

思路：优化的区间dp

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 3e3 + 100;

int n, a[N], p[N], c[N];
int dp[N][N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif 
    int T; cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 1; i <= n; i++) cin>>a[i];
        mem(c, 0);

        // p数组存的是这个位置的数字上次出现的位置
        for(int i = 1; i <= n; i++)
        {
            p[i] = c[a[i]];
            c[a[i]] = i;
        }

        for(int len = 1; len < n; len++)
        {
            for(int l = 1; l <= n-len; l++)
            {
                int r = l+len;
                // dp[l][r] = min(dp[l][r-1]+1, dp[l+1][r]+1);
                dp[l][r] = dp[l][r-1] + (a[r-1] != a[r]);

                // 如果[l, r]中有和r相同的数字，则dp[l][k]]+dp[k+1][r]可能会更新出更优解
                // 如果没有，那[l, r]就是最优解：枚举一个断点x，少一次把[l, x]染为r相同颜色的操作，多一次x左右颜色统一的操作
                for(int k = p[r]; k >= l; k = p[k])
                    dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]);
            }
        }
        cout<<dp[1][n]<<endl;
    }

    return 0;
}