跳转至

USACO23Jan Silver

T1ψ(｀∇´)ψ

考虑类似置换环的连边。

然后显然一个点不能有多个出边，不然因为同步变化，它必然无解。

然后一个点显然可以有多个入边。

一个链显然直接倒着做就行。

注意到对于一个环，我们的处理方式应该是找一个不在环上的点（且没有在序列里出现过），断开，然后就是一条链。

但是这里只有 52 个字符，有可能找不到这样的“中转点”，但是注意到，如果一个点指向了一个环上节点，我们可以把这个点作为“中转”点。

于是我们可以缩点，反向建图，如果一个环出现在了入度不为零的节点，显然无解。

然后有几个坑点，缩完点之后统计答案要特殊考虑有团和没有团的情况，然后还要去掉重边。

然后还有，如果一个长度为 \(51\) 的环出现了，另外一个字符是自环，也会寄掉。

但是这样还是 Wa on 10, 13, 14, 15。

先放着代码，现在交不了。

感觉这个 T1 非常恶心。

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
 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// author : black_trees

#include <map>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int n, m;
int tot = 0, tt = 0;
int head[si], hd[si];
struct Edge { int ver, Next; } e[si << 1], ee[si << 1];
inline void add(int u, int v) { e[tot] = (Edge){v, head[u]}, head[u] = tot++; }
inline void addd(int u, int v) { ee[tt] = (Edge){v, hd[u]}, hd[u] = tt++; }
int tyq = 0; // occ of all letters.

int cnt = 0, tim = 0;
std::stack<int>st;
bool ins[si];
int dfn[si], low[si];
int c[si], num[si];
void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    st.push(u), ins[u] = true;
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int x; ++cnt;
        do {
            x = st.top(), st.pop();
            ins[x] = false, c[x] = cnt, num[cnt]++;
        } while(u != x);
    }
}
std::map<char, int>mp, mpp;
int ind[si], clz = 0, oug[si];
std::map<std::pair<int, int>, bool> vis;
int out[si];

void Init() {
    vis.clear();
    mp.clear(), mpp.clear();
    while(!st.empty()) st.pop();
    tot = tt = clz = tyq = cnt = tim = 0;
    memset(ins, false, sizeof ins);
    memset(c, 0, sizeof c), memset(num, 0, sizeof num);
    memset(dfn, 0, sizeof dfn), memset(low, 0, sizeof low);
    memset(head, -1, sizeof head), memset(hd, -1, sizeof hd);
    memset(ind, 0, sizeof ind), memset(oug, 0, sizeof oug), memset(out, 0, sizeof out);
}
int dfs(int u) {
    int ret = num[u];
    for(int i = hd[u]; ~i; i = ee[i].Next) {
        int v = ee[i].ver;
        ret += dfs(v);
    }
    return ret;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        Init(); bool nosol = false;
        string s, t;
        cin >> s >> t;
        n = (int)s.size();
        s = ' ' + s, t = ' ' + t;

        for(int i = 1; i <= n; ++i) {
            if(!mpp[s[i]]) mpp[s[i]] = ++tyq;
            if(!mpp[t[i]]) mpp[t[i]] = ++tyq; 
        }
        for(int i = 1; i <= n; ++i) {
            if(s[i] != t[i]) {
                if(!mp[s[i]]) mp[s[i]] = ++clz;
                if(!mp[t[i]]) mp[t[i]] = ++clz;
                if(vis[{mp[s[i]], mp[t[i]]}]) continue;
                add(mp[s[i]], mp[t[i]]), ++oug[mp[s[i]]];
                vis[{mp[s[i]], mp[t[i]]}] = true;
                if(oug[mp[s[i]]] > 1) {
                    nosol = true;
                    break;
                }
            }
        }
        for(int i = 1; i <= n; ++i) {
            if(s[i] == t[i]) {
                if(!mp[s[i]]) continue;
                if(oug[mp[s[i]]]) {
                    nosol = true;
                    break;
                }
            }
        }
        if(nosol) { cout << "-1" << endl; continue; }
        for(int i = 1; i <= clz; ++i) {
            if(!dfn[i]) tarjan(i);
        }
        for(int u = 1; u <= clz; ++u) {
            for(int i = head[u]; ~i; i = e[i].Next) {
                int v = e[i].ver;
                if(c[u] == c[v]) continue;
                addd(c[v], c[u]), ++ind[c[u]], ++out[c[v]];
            }
        }

        int ans = 0;
        for(int i = 1; i <= cnt; ++i) {
            if(ind[i] > 0 && num[i] > 1) {
                nosol = true;
                break;
            }
            if(!ind[i]) {
                ans += dfs(i);
                if(num[i] == 1) ans--;
                else {
                    if(!out[i]) {
                        if(tyq < 52) ans++;
                        else {
                            nosol = true; break;
                        }
                    }
                }
            }
        }
        if(nosol) { cout << "-1" << endl; continue; }
        cout << ans << endl;
    } 

    return 0;
}

// ()()()(?`

T2ψ(｀∇´)ψ

还没改。

T3ψ(｀∇´)ψ

考虑贪心做一个类似欧拉路的东西。

就是你对于一个奇数，你显然会走过去不走回来，那就先转，然后转到只剩 1 了再走过去，一段也是一样。

然后对于一个偶数，你会走回来，所以其实可以考虑一段一段的，先走通然后拉回来，多的也是转两下就没了。

因为保证有解所以我们不用管那么多，直接构造就行了。

我赛时没看到要最小化步数，但是瞎整的也对了，很巧。

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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e6 + 10;

int n, a[si], ans[si], tot = 0;

void dfs(int u, int lst) {
    if(lst == 0) {
        while(a[u]) a[u]--, dfs(u + 1, 0);
        while(a[u - 1]) a[u - 1]--, dfs(u - 1, 1);
    }
    else {
        while(a[u - 1]) a[u - 1]--, dfs(u - 1, 1);
        while(a[u]) a[u]--, dfs(u + 1, 0);
    }
    ans[++tot] = u;
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    dfs(1, 0);
    string s;
    for(int i = 1; i < tot; ++i) 
        if(ans[i + 1] < ans[i]) 
            s += 'R';
        else s += 'L';
    reverse(s.begin(), s.end());
    cout << s << endl;


    return 0;
}


// ()()()(?
最后更新: May 9, 2023