(打了Virtual但是没做完的)解题报告。

Table of Contents

  1. A. Vasya And Password
  2. B.Relatively Prime Pairs
  3. C. Vasya and Multisets
  4. D. Bi-coloring
  5. F. The Shortest Statement
  6. E & G ?

A. Vasya And Password

$\ldots$

细节还挺多.

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
//maki
#include <bits/stdc++.h>

using namespace std;

string s;
int tp[105];
vector<int> pos[4];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while(T--)
    {
        cin >> s; memset(tp, 0, sizeof tp);
        int len = s.size();
        pos[1].clear(); pos[2].clear(); pos[3].clear();
        for(int i = 0; i < len; ++i)
        {
            if(isupper(s[i])) tp[i] = 1, pos[1].push_back(i);
            else if(islower(s[i])) tp[i] = 2, pos[2].push_back(i);
            else tp[i] = 3, pos[3].push_back(i);
        }
        if(pos[1].size() && pos[2].size() && pos[3].size())
        {
            cout << s << endl;
            continue;
        }
        if((int)pos[1].size() == len)
        {
            s[0] = 'a';
            s[1] = '1';
            cout << s << endl; continue;
        }
        else if ((int)pos[2].size() == len)
        {
            s[0] = 'A';
            s[1] = '1';
            cout << s << endl; continue;
        }
        else if((int)pos[3].size() == len)
        {
            s[0] = 'A';
            s[1] = 'a';
            cout << s << endl; continue;
        }
        char tmp;
        if(!pos[1].size()) tmp = 'A';
        else if(!pos[2].size()) tmp = 'a';
        else if(!pos[3].size()) tmp = '1';
        for(int i = 1; i < len; ++i)
        {
            if(tp[i] != tp[i - 1])
            {
                if(i == len - 1)
                {
                    s[i-2] = tmp;
                    break;
                }
                else
                {
                    s[i+1] = tmp;
                    break;
                }
            }
        }
        cout << s << endl;
    }
    return 0;
}

B.Relatively Prime Pairs

给一个区间, 用所有数构造数对, 数对互质.

相邻嘛……唉……

C. Vasya and Multisets

一个可重集合内的好数是指只出现了一次的数, 把一个可重集分成两个可重集, 使得好数个数相同.

判个奇偶什么的吧……

D. Bi-coloring

把一个$2\times n$的矩阵黑白染色, 联通块是指连续的四连通同色格子, 问染色后恰有 $k$ 个联通块的方案数.

入门计数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
//maki
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;
const int maxn = 2005;

int n, k;
ll f[maxn][maxn][4];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

    f[1][1][0] = f[1][1][3] = f[1][2][1] = f[1][2][2] = 1;
    for(int i = 1; i < n; ++i)
        for(int j = 1; j <= k; ++j)
        {
            //0
            f[i+1][j][0] = (f[i+1][j][0] + f[i][j][0]) % mod;
            f[i+1][j+1][3] = (f[i+1][j+1][3] + f[i][j][0]) % mod;
            f[i+1][j+1][1] = (f[i+1][j+1][1] + f[i][j][0]) % mod;
            f[i+1][j+1][2] = (f[i+1][j+1][2] + f[i][j][0]) % mod;
            //1
            f[i+1][j][1] = (f[i+1][j][1] + f[i][j][1]) % mod;
            f[i+1][j+2][2] = (f[i+1][j+2][2] + f[i][j][1]) % mod;
            f[i+1][j][0] = (f[i+1][j][0] + f[i][j][1]) % mod;
            f[i+1][j][3] = (f[i+1][j][3] + f[i][j][1]) % mod;
            //2
            f[i+1][j][2] = (f[i+1][j][2] + f[i][j][2]) % mod;
            f[i+1][j+2][1] = (f[i+1][j+2][1] + f[i][j][2]) % mod;
            f[i+1][j][0] = (f[i+1][j][0] + f[i][j][2]) % mod;
            f[i+1][j][3] = (f[i+1][j][3] + f[i][j][2]) % mod;
            //3
            f[i+1][j][3] = (f[i+1][j][3] + f[i][j][3]) % mod;
            f[i+1][j+1][0] = (f[i+1][j+1][0] + f[i][j][3]) % mod;
            f[i+1][j+1][1] = (f[i+1][j+1][1] + f[i][j][3]) % mod;
            f[i+1][j+1][2] = (f[i+1][j+1][2] + f[i][j][3]) % mod; 
        }

    ll sum = 0;
    for(int i = 0; i < 4; ++i)
        sum = (sum + f[n][k][i]) % mod;
    cout << sum << endl;
    return 0;
}

F. The Shortest Statement

给一个无向连通图, 每次查询任意两点间的最短路, $n, q \le 10^5$.

$m - n \le 20$.

肯定先建最小生成树了, 问题是怎么处理剩下的20条边, 一开始想在环上打标记或者做差什么的, 但是似乎都不太可做.

正解是把边加进去, 以每个额外边的端点为起点跑一次最短路, 这样每次查询的时候, 要么在树上走, 要么强制至少经过一个端点.

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
154
155
156
157
158
159
//maki
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e+5 + 5;

struct krus
{
    int frm, to; ll v;
    bool operator < (const krus &rhs) const
    {
        return v < rhs.v;
    }
}k[maxn + 100];
int n, m, uf[maxn];

int tmp[100], tmps[100], tote, totp;

//bcj
inline void init()
{
    for(int i = 1; i <= n; ++i) uf[i] = i;
}
int find(int x)
{
    return (uf[x] == x) ? x : uf[x] = find(uf[x]);
}
bool link(int x, int y)
{
    int fx = find(x), fy = find(y);
    //cerr << x << " " << y << " " << fx << " " << fy << endl;
    if(fx != fy)
    {
        uf[fx] = fy; return true;
    }
    return false;
}

//heavy-light decomposition
struct edge
{
    int to, nxt; ll v;
}e[maxn << 1];
int ptr, lnk[maxn], dep[maxn], f[maxn], top[maxn], mxson[maxn], siz[maxn];
ll ddis[maxn];
inline void add(int bgn, int end, ll val)
{
    e[++ptr] = (edge){end, lnk[bgn], val};
    lnk[bgn] = ptr;
}
void dfs(int x, int fa, int d)
{
    //cerr << "vis" << x << endl;
    siz[x] = 1; 
    f[x] = fa;
    dep[x] = d;
    for(int p = lnk[x]; p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(y == fa) continue;
        ddis[y] = ddis[x] + e[p].v;
        //cerr<<"dfs"<<ddis[y]<<endl;
        dfs(y, x, d + 1);
        siz[x] += siz[y];
        if(siz[y] > mxson[x]) mxson[x] = y;
    }
}
void dfs2(int x, int init)
{
    top[x] = init;
    if(!mxson[x]) return;
    dfs2(mxson[x], init);
    for(int p = lnk[x]; p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(y == f[x] || y == mxson[x]) continue;
        dfs2(y, y);
    }
}
inline int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return (dep[x] > dep[y]) ? y : x;
}

//shortest-paths
int vis[maxn];
ll dis[50][maxn]; queue<int> q;
inline void spfa(int i, int s)
{
    memset(dis[i], 0x3f, sizeof dis[i]);
    q.push(s); dis[i][s] = 0; vis[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(dis[i][y] > dis[i][u] + e[p].v)
            {
                dis[i][y] = dis[i][u] + e[p].v;
                if(!vis[y])
                    vis[y] = 1, q.push(y);
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);	

    cin >> n >> m;init();
    for(int i = 1; i <= m; ++i)
        cin >> k[i].frm >> k[i].to >> k[i].v;
    sort(k + 1, k + 1 + m);
    for(int i = 1; i <= m; ++i)
    {
        if(link(k[i].frm, k[i].to))
        {
            add(k[i].frm, k[i].to, k[i].v);
            add(k[i].to, k[i].frm, k[i].v);
            //cerr << "add" << endl;
        }
        else tmp[++tote] = i;
    }
    dfs(1, 0, 1);
    dfs2(1, 1);
    for(int i = 1; i <= tote; ++i)
    {
        add(k[tmp[i]].frm, k[tmp[i]].to, k[tmp[i]].v);
        add(k[tmp[i]].to, k[tmp[i]].frm, k[tmp[i]].v);
        tmps[++totp] = k[tmp[i]].frm, tmps[++totp] = k[tmp[i]].to;
    }
    for(int i = 1; i <= totp; ++i) spfa(i, tmps[i]);

    int q; cin >> q;
    while(q--)
    {
        int x, y; cin >> x >> y;
        int LCA = lca(x, y);
        ll ans = ddis[x] + ddis[y] - 2ll * ddis[LCA];
        //cerr << "---" << ans << endl;
        for(int i = 1; i <= totp; ++i)
            ans = min(ans, dis[i][x] + dis[i][y]);
        cout << ans << endl;
    }

    return 0;
}

E & G ?

没啦(不会).