srm 556

发表于   |   分类于   |  

250

Description

一个点数为$50$的无向图，每个节点$i$有一个分值$v[i]$，当你进入到$v[i]$的时候，你的分数是$value(当前分数) xor v[i]$，请问从点$0$开始，你任意走能获得的最大分数
$value \le 1023$

Solution

注意权值为$1023$，bfs即可

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 50, M = 1024;
bool d[N][N], f[N][M];
queue<pii> Q;
struct XorTravelingSalesman {
    int maxProfit(vector <int> a, vector <string> s) {
        int n = a.size();              
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (s[i][j] == 'Y') d[i][j] = 1;
        int mx = a[0];
        f[0][a[0]] = 1;
        Q.push(mp(0, a[0]));
        while (Q.size()) {
            pii t = Q.front();
            Q.pop();
            for (int i = 0; i < n; ++i) 
                if (d[t.F][i] && !f[i][t.S ^ a[i]]) {
                    f[i][t.S ^ a[i]] = 1;
                    Q.push(mp(i, t.S ^ a[i]));
                    mx = max(mx, t.S ^ a[i]);
                }
        }
        return mx;
    }
};

500

Description

你手头上有一个数$A$,通过这个数$A$你要构造最小的大于等于$B$的数$C$，每次将$A$最左端的数拿走，放到$C$的最左或最右端

Solution

观察到,这个过程前$i$位的数对应$B$连续的一段
考虑数位dp,$dp[i][l][r][fl]$表示用了前$i$位,和$B[l]\sim B[r]$的大小关系为$fl$的最小串
我们发现每次转移这个数可以通过放到最左或最右来转移，直接dp即可
我的大小关系$fl$设为

  • (1): 3 “>=”
  • (2): 2 “>”
  • (3): 1 “=”
  • (4): 0 任意状态

感觉写的挺烦的,非常愚蠢….

Code

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
#include <bits/stdc++.h>//dp
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55;
int n, A[N], B[N];
//3: >=
//2: > 
//1: = 
//0: any
string f[N][N][N][4], inf;
struct LeftRightDigitsGame2 {
    string dp(int p, int l, int r, int fl) {
        string &tmp = f[p][l][r][fl];
        if (tmp != "!") return tmp;
        tmp = "";
        string x = string(1, (char)(A[p] + '0'));
        if (l == r) {
            if (fl == 3 && A[p] >= B[l])    return tmp = x;
            if (fl == 2 && A[p] > B[l])     return tmp = x;
            if (fl == 1 && A[p] == B[l])    return tmp = x;
            if (fl == 0)    return tmp = x;
            return tmp = "";
        }
        string t1 = inf, t2 = inf, t;
        if (fl >= 2) {
            if (A[p] > B[l]) {
                t = dp(p - 1, l + 1, r, 0);
                if (t != "")    t1 = min(t1, x + t);//(l + 1, r)
            }
            else if (A[p] == B[l]) {
                t = dp(p - 1, l + 1, r, 2);
                if (t != "")    t1 = min(t1, x + t);
            }
            t = dp(p - 1, l, r - 1, 2); //(l, r - 1)
            if (t != "")    t2 = min(t2, t + x);
            if (A[p] > B[r]) {
                t = dp(p - 1, l, r - 1, 1);
                if (t != "")    t2 = min(t2, t + x);
            }
        }
        if (fl & 1) {
            if (A[p] == B[l]) {//(l + 1, r)
                t = dp(p - 1, l + 1, r, 1);
                if (t != "")    t1 = min(t1, x + t);                    
            }
            if (A[p] == B[r]) {//(l, r - 1)
                t = dp(p - 1, l, r - 1, 1);
                if (t != "")    t2 = min(t2, t + x);
            }
        }
        if (!fl) {
            t = dp(p - 1, l + 1, r, 0);
            if (t != "")    t1 = min(t1, x + t);
            t = dp(p - 1, l, r - 1, 0);
            if (t != "")    t2 = min(t2, t + x);
        }
        tmp = min(t1, t2);
        if (tmp == inf) tmp = "";
        return tmp;
    }
    string minNumber(string a, string b) {
        int n = a.size();
        for (int i = 0; i < n; ++i) {
            inf += "9";
            for (int j = 0; j < n; ++j)
                for (int k = 0; k < n; ++k)
                    for (int l = 0; l < 4; ++l)
                        f[i][j][k][l] = "!";
        }
        for (int i = 0; i < n; ++i) A[i] = a[i] - '0', B[i] = b[i] - '0';
        string ans = dp(n - 1, 0, n - 1, 3);
        if (ans == inf) ans = "";
        return ans;
    }
};