发表于   |   分类于   |  

275

Description

懒得写了= =自己看吧。。。

Solution

直接dp即可，用二进制的小技巧表示相同颜色即可

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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N = 55, inf = 1e7;
int a[N], dp[N];
class Stamp {
    public:
        int getMinimumCost(string s, int A, int B) {
            int n = s.size();
            for (int i = 0; i < n; ++i) {
                if (s[i] == 'R')    a[i] = 1;
                if (s[i] == 'G')    a[i] = 2;
                if (s[i] == 'B')    a[i] = 4;
                if (s[i] == '*')    a[i] = 7;
            }
            int ans = inf;
            for (int l = 1; l <= n; ++l) {
                fill(dp, dp + n + 1, inf);
                dp[0] = 0;
                for (int i = 0; i < n; ++i) {
                    int now = 7;
                    for (int j = i; j < n; ++j) {
                        now &= a[j];
                        if (!now)   break;
                        int len = j - i + 1;
                        if (len >= l && dp[i] != inf)   dp[j + 1] = min(dp[j + 1], dp[i] + ((len + l - 1) / l) * B);
                    }
                }
                if (dp[n] != inf)   ans = min(ans, dp[n] + A * l);
            }
            return ans;
        }
};

550

Description

看图泥就懂题意了= =

Solution

首先枚举两个蓝色点，再枚举$B$点，复杂度可以接受
从小到大枚举$B$点时可以同时记录可以满足条件的$A$的个数，然后二分求出右面$C,D$的个数，统计即可

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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
#define mp make_pair
#define pb push_back
#define F first
#define S second
class Ear {
    public:
        long long getCount(vector <string> redX, vector <string> blueX, vector <string> blueY) {
            string a, b, c;
            vector<int> r, bx, by;
            for (int i = 0; i < redX.size(); ++i)   a += redX[i];
            for (int i = 0; i < blueX.size(); ++i)  b += blueX[i];
            for (int i = 0; i < blueY.size(); ++i)  c += blueY[i];
            stringstream sa(a), sb(b), sc(c);
            int x;
            while (sa >> x) r.pb(x);
            while (sb >> x) bx.pb(x);
            while (sc >> x) by.pb(x);
            sort(r.begin(), r.end());
            LL ans = 0;
            int n = bx.size(), m = r.size();
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) {
                    if (i == j) continue;
                    if (by[i] > by[j]) {
                        int tot = 0;
                        for (int k = 0; k < m; ++k) {
                            if (r[k] < bx[j]) {
                                int R = max(bx[i], bx[j]) + 1;
                                double x = 1e50;
                                if (bx[i] != bx[j]) {
                                    double k = (double)(by[i] - by[j]) / (bx[i] - bx[j]);
                                    x = bx[i] - (double)by[i] / k;
                                    R = max(R, (int)floor(x + 1e-6) + 1);
                                }
                                int RR = lower_bound(r.begin(), r.end(), R) - r.begin();
                                int LL = upper_bound(r.begin(), r.end(), bx[j]) - r.begin();
                                ans += 1ll * tot * (RR + m - LL * 2 - 1) * (m - RR) / 2;
                                if (r[k] < bx[i] && r[k] < x - 1e-6)    ++tot;
                            }       
                        }
                    }
                }
            return ans;
        }
};

发表于   |   分类于   |  

250

Description

在二维坐标轴上从$(0,h_0)$走到$(n, h_n)$,走一次在x轴上前进一个单位长度，在y轴上上升或者下降一个单位长度
现在已知中间的某段连续区域的走法（只由’U’和’D’构成的不超过50的字符串）
问是否在保证最低点不低于0的情况下成功走到终点。

Solution

判断连续一段最低点到哪里，前面补$U$即可，其余部分判判奇偶随便搞搞就行了

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
#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;
struct FoxAndMountainEasy {
    string possible(int n, int h0, int hn, string s) {
        int l = s.size();
        int mn = 0, now = 0;
        for (int i = 0; i < l; ++i) {
            if (s[i] == 'U')    ++now;
            else --now;
            mn = min(mn, now);
        }
        mn = h0 + mn;
        int del = hn - h0 - now;
        n -= l;
        if (mn < 0) del += mn, n += mn;
        if (abs(del) > n || n < 0)  return "NO";
        int t = del - n;
        if (t & 1)  return "NO";
        return "YES";
    }
};

550

Description

一张普通图，$50*50$，可能有自环。初始全白
给一个闭包矩阵，每次挑一个点染成灰色则它可达的点全黑,求最多能有多少点变灰

Solution

所求即最长反链，根据dilworth定理，即为最大反链大小等于最少划分成的链数
即求最小可相交路径覆盖，求个闭包$|V|-最大匹配$即为答案

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
#include <bits/stdc++.h>//dilworth
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, l[N];
bool g[N][N], v[N];
struct Incubator {
    bool can(int u) {
        for (int i = 0; i < n; ++i) 
            if (g[u][i] && !v[i]) {
                v[i] = 1;
                if (l[i] == -1 || can(l[i])) {
                    l[i] = u;
                    return 1;
                }
            }
        return 0;
    }
    int maxMagicalGirls(vector <string> s) {
         n = s.size();
         for (int i = 0; i < n; ++i) 
             for (int j = 0; j < n; ++j)
                 g[i][j] = s[i][j] == 'Y';
         for (int k = 0; k < n; ++k)
             for (int i = 0; i < n; ++i)
                 for (int j = 0; j < n; ++j)
                     g[i][j] |= g[i][k] & g[k][j];
         int t = 0;
         memset(l, -1, sizeof(l));
         for (int i = 0; i < n; ++i) {
             memset(v, 0, sizeof(v));
             if (can(i))    ++t;
         }
         return n - t;
    }
};

发表于   |   分类于   |  

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;
    }
};

发表于   |   分类于 ，   |  

Descripiton

给定一棵树，有若干个询问，每次给定$m$个点，每个点都被这$m$个点中最近（距离相同，编号小的近）的点管辖。问$m$个点分别管几个点
$\sum m\le 300000$

Solution

一个很经典的题，通过这题学到了一个叫虚树的东西，修为得到的精进
虚树就是包含了给定点，并收缩了不分叉边的连通子图
然后我们讨论下虚树的构建
先给代码
$t$表示虚树的节点，$h$是给定点，$st$是栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void build(int m) {
    int top = 0;
    sort(h + 1, h + m + 1, cmp);
    for (int i = 1; i <= m; ++i) {
        if (!top)   fa[st[++top] = h[i]] = 0;
        else {
            int x = lca(st[top], h[i]);
            for (; dep[st[top]] > dep[x]; --top)
                if (dep[st[top - 1]] <= dep[x]) fa[st[top]] = x;
            if (st[top] != x) {
                fa[x] = st[top];
                t[++tot] = st[++top] = x;
                near[x] = mp(0x3f3f3f3f, 0);
            }
            fa[st[++top] = h[i]] = x;
        }
    }
}

我们将给定点按lca递增排序，用一个栈表示已构建的虚树上以最后一个点为断点的链,设栈顶元素为p,当前点为x,然后我们求出lca
有两种情况

  • (1):$p$和$x$在$lca$的两棵子树下
  • (2):$lca$是$p$
    对于第二种情况，由于$dfs$序递增，$lca$不可能是$x$,因为$lca$一定不晚于$p$访问，这种情况直接连边即可
    对于第一种情况，由于$dfn[lca] < dfn[p] < dfn[x]$，说明$p$的子树我们一定都处理完了，否则一定会在x前处理
    由于$p$子树已经处理完，我们可以退栈辣，退栈直到lca夹在两个栈元素之间，处理完边的关系，再退一次，这条链就处理完辣！
    然后就可以继续把当前x加入栈中，继续处理这条链，代码很短，但是需要理解一会~

容易发现构建的虚树最多$2m$个点，完全可以接受
构建完虚树就是树形dp的事情了，先按$dfs$序正反两遍扫出虚树上每个点被哪个点管理，并记录距离。(容易想到用个pair来存，编程复杂度会少一些)
继续按dfs序递增处理
如果是虚树的根，那么首先对管理它的点的贡献就是$n-sz[rt]$
假设当前点是$x$,虚树上的父节点是$fa$,$rt$同时是真树上$x$的祖先和fa的儿子,考虑$fa$和$x$是否被同一个点管辖，如果是，中间都属于同一个点
否则考虑尽量靠中间的点，分奇偶讨论下即可

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
#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 = 3e5 + 5;
vector<int> g[N];
pii near[N];
int n, tot, ind, dep[N], dfn[N], sz[N], f[N][20], pos[N], h[N], t[N], st[N], fa[N], w[N], dis[N], ans[N];
bool cmp(const int &x, const int &y) {
    return dfn[x] < dfn[y];
}
int find(int x, int d) {
    for (int i = 19; i >= 0; --i)
        if (dep[f[x][i]] >= d)  x = f[x][i];
    return x;
}
int lca(int x, int y) {
    if (dep[x] < dep[y])    swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
void dfs(int u) {
    sz[u] = 1;
    dfn[u] = ++ind;
    for (int i = 0, v; i < g[u].size(); ++i) {
        v = g[u][i];
        if (v == f[u][0])   continue;
        f[v][0] = u;
        for (int j = 1; j <= 19; ++j)   f[v][j] = f[f[v][j - 1]][j - 1];
        dep[v] = dep[u] + 1;
        dfs(v);
        sz[u] += sz[v];
    }
}
void build(int m) {
    int top = 0;
    sort(h + 1, h + m + 1, cmp);
    for (int i = 1; i <= m; ++i) {
        if (!top)   fa[st[++top] = h[i]] = 0;
        else {
            int x = lca(st[top], h[i]);
            for (; dep[st[top]] > dep[x]; --top)
                if (dep[st[top - 1]] <= dep[x]) fa[st[top]] = x;
            if (st[top] != x) {
                fa[x] = st[top];
                t[++tot] = st[++top] = x;
                near[x] = mp(0x3f3f3f3f, 0);
            }
            fa[st[++top] = h[i]] = x;
        }
    }
}
void work() {
    tot = 0;
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &h[i]);
        t[++tot] = pos[i] = h[i], ans[h[i]] = 0, near[h[i]] = mp(0, h[i]);
    }
    build(m);
    sort(t + 1, t + tot + 1, cmp);
    for (int i = 1; i <= tot; ++i) {
        int x = t[i];
        w[x] = sz[x];
        if (i > 1)  dis[x] = dep[x] - dep[fa[x]];
    }
    for (int i = tot; i > 1; --i) {
        int x = t[i];
        near[fa[x]] = min(near[fa[x]], mp(near[x].F + dis[x], near[x].S));
    }
    for (int i = 2; i <= tot; ++i) {
        int x = t[i];
        near[x] = min(near[x], mp(near[fa[x]].F + dis[x], near[fa[x]].S));
    }
    for (int i = 1; i <= tot; ++i) {
        int x = t[i];
        if (i == 1) ans[near[x].S] += n - sz[x];
        else {
            int rt = find(x, dep[fa[x]] + 1);
            int sum = sz[rt] - sz[x];
            w[fa[x]] -= sz[rt];
            if (near[fa[x]].S == near[x].S) ans[near[x].S] += sum;
            else {
                int mid = dep[x] - (near[fa[x]].F - near[x].F + dis[x]) / 2;
                if ((near[fa[x]].F + near[x].F + dis[x]) % 2 == 0 && near[fa[x]].S < near[x].S) ++mid;
                int tmp = sz[find(x, mid)] - sz[x];
                ans[near[fa[x]].S] += sum - tmp;
                ans[near[x].S] += tmp;
            }
        }
    }
    for (int i = 1; i <= tot; ++i)  ans[near[t[i]].S] += w[t[i]];
    for (int i = 1; i <= m; ++i)    printf("%d ", ans[pos[i]]);
    puts("");
}
void gao() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].pb(v), g[v].pb(u);
    }
    dfs(dep[1] = 1);
    int q;
    scanf("%d", &q);
    while (q--) work();
}
int main() {
    gao();
    return 0;
}

发表于   |   分类于   |  

255

Description

问能将一个$0/1$串最少分成几个串使得每个串都是$5$的整数次幂，且没有前导零

Solution

dp即可，$dp[i]$表示前$i$个字符分割的结果，枚举一个分割点$j$，$check$即可

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
#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 = 55;
int dp[N];
struct CuttingBitString {
    bool ok(LL x) {
        while (x && x % 5 == 0) x /= 5;
        return x == 1;
    }
    int getmin(string S) {
        string s = "0" + S + "1";
        int n = s.size();
        for (int i = 1; i <= n; ++i)    dp[i] = 10000;
        for (int i = 1; i < n; ++i) {
            if (s[i] == '1') {
                for (int j = 0; j < i - 1; ++j) {
                    if (dp[j] == 10000 || s[j + 1] == '0')  continue;
                    LL now = 0;
                    for (int k = j + 1; k <= i - 1; ++k)    now = now * 2 + (s[k] == '1' ? 1 : 0);
                    if (ok(now))    dp[i - 1] = min(dp[i - 1], dp[j] + 1);
                }
            }
        }
        return dp[n - 2] == 10000 ? -1 : dp[n - 2];
    }
};

555

Description

有一个$H*W$的全$0$矩阵，给定对行列操作数，每次操作将行列$0/1$翻转，使得最后矩阵$1$的个数为$S$,求方案数
两个方案不同当且仅当有一行或列操作数不同

Solution

很容易想到操作两次相当于没操作，枚举行列分别操作$1$次的个数，剩下的相当于$n$个物品(n对操作两次)放到$m$个不同盒子的方案数，即$\binom{n+m-1}{n}$，统计即可

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
#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 = 1600, M = 555555555;
int c[N << 1][N << 1];
struct XorBoard {
    int count(int H, int W, int Rcount, int Ccount, int S) {
        for (int i = 0; i <= 1555 * 2; ++i) {
            c[i][0] = 1;
            for (int j = 1; j <= i; ++j)    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
        }
        int ans = 0;
        for (int i = 0; i <= Rcount && i <= H; ++i)
            for (int j = 0; j <= Ccount && j <= W; ++j) {
                if (i * W + j * H - 2 * i * j != S) continue;
                if ((Rcount - i) & 1 || (Ccount - j) & 1)   continue;
                int rl = (Rcount - i) / 2, cl = (Ccount - j) / 2;
                (ans += (LL)c[rl + H - 1][rl] * c[H][i] % M * c[cl + W - 1][cl] % M * c[W][j] % M) %= M;
            }
        return ans;
    }
};

发表于   |   分类于 ，   |  

Descripiton

给定一棵树，每个节点有一个字符，求从一个节点出发沿最短路径走到另一个节点所构成的字符串一共有多少种
注意：叶子数$\le$20

Solution

这个题，发现叶子数很少就很好做了，以每个叶子为根节点建立SAM即可，这样原树上所有路径都在SAM出现过,统计即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100005 * 2 * 20, M = 10;
typedef long long LL;
#define pb push_back
struct SAM {
    int tot, last, step[N], g[N], par[N], son[N][M], cnt[N], Q[N], ch[N], f[N];
    void init() {
        tot = 0;
        memset(par, 0, sizeof(par));
        par[0] = -1;
        memset(son, 0, sizeof(son));
    }
    int add(int last, int x) {
        int p = last, np = ++tot;
        step[np] = step[p] + 1, last = np, ++g[np];//right
        ch[np] = x;
        for (; !son[p][x] && ~p; p = par[p])    son[p][x] = np;
        if (p == -1)    return np;
        int q = son[p][x];
        if (step[q] == step[p] + 1) par[np] = q;
        else {
            step[++tot] = step[p] + 1;
            ch[tot] = x;
            int nq = tot;
            memcpy(son[nq], son[q], sizeof(son[q]));
            par[nq] = par[q];
            par[np] = par[q] = nq;
            for (; son[p][x] == q && ~p; p = par[p])    son[p][x] = nq;
        }
        return np;
    }
    void topo() {
        for (int i = 1; i <= tot; ++i)    ++cnt[step[i]];
        for (int i = 1; i <= tot; ++i)    cnt[i] += cnt[i - 1];
        for (int i = 1; i <= tot; ++i)    Q[cnt[step[i]]--] = i;        
    }
    LL gao() {
        LL ans = 0;
        for (int i = 1; i <= tot; ++i)  ans += step[i] - step[par[i]];//i状态表示多少个字符串
        return ans;
    }
}S;
int a[100005], d[100005];
vector<int> g[100005];
void dfs(int u, int fa, int last) {
    int t = S.add(last, a[u]);
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (v == fa)    continue;
        dfs(v, u, t);
    }
}
int main() {
    S.init();
    int n, c;
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; ++i)    scanf("%d", &a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].pb(v), g[v].pb(u);
        ++d[u], ++d[v];
    }
    for (int i = 1; i <= n; ++i)
        if (d[i] == 1)  dfs(i, 0, 0);
    printf("%lld\n", S.gao());
    return 0;
}

发表于   |   分类于 ，   |  

先扯几句

昨天tc怎么都上不去，突然想再补补姿势，然后发现SAM这个东西理解的很不到位，花了一晚上重新理解了一下，做了下题来回顾下>_<_

Description

对于一个给定长度为$N$的字符串，求它的第$K$小子串是什么
第二行为两个整数$T$和$K$，$T$为$0$则表示不同位置的相同子串算作一个
$T=1$则表示不同位置的相同子串算作多个,$K$的意义如题所述。
$k\le 5*10^5,N\le 10^9$

Solution

很容易想到用SAM做，$T=1$正常做，$T=0$时考虑right数组的意义，把right数组都赋值为1，拓扑排序处理下即可
最后$dfs$或者非递归处理一下即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 500005 * 2, M = 26;
struct SAM {
    int tot, last, step[N], g[N], par[N], son[N][M], cnt[N], Q[N], ch[N], f[N];
    void init() {
        tot = last = 0;
        memset(par, 0, sizeof(par));
        par[0] = -1;
        memset(son, 0, sizeof(son));
    }
    void add(int x) {
        int p = last, np = ++tot;
        step[np] = step[p] + 1, last = np, ++g[np];//right
        ch[np] = x;
        for (; !son[p][x] && ~p; p = par[p])    son[p][x] = np;
        if (p == -1)    return;
        int q = son[p][x];
        if (step[q] == step[p] + 1) par[np] = q;
        else {
            step[++tot] = step[p] + 1;
            ch[tot] = x;
            int nq = tot;
            memcpy(son[nq], son[q], sizeof(son[q]));
            par[nq] = par[q];
            par[np] = par[q] = nq;
            for (; son[p][x] == q && ~p; p = par[p])    son[p][x] = nq;
        }
    }
    void topo() {
        for (int i = 1; i <= tot; ++i)    ++cnt[step[i]];
        for (int i = 1; i <= tot; ++i)    cnt[i] += cnt[i - 1];
        for (int i = 1; i <= tot; ++i)    Q[cnt[step[i]]--] = i;        
    }
    void gao(int t) {
        for (int i = tot; i >= 0; --i) {
            if(t == 0)  g[Q[i]] = 1;
            else g[par[Q[i]]] += g[Q[i]];
            f[Q[i]] = g[Q[i]];
            for (int j = 0; j < 26; ++j)
                f[Q[i]] += f[son[Q[i]][j]];
        }
    }
}S;
char s[N];
int main() {
    scanf("%s", s);
    S.init();
    int l = strlen(s);
    for (int i = 0; i < l; ++i) S.add(s[i] - 'a');
    S.topo();
    int t, k;
    scanf("%d%d", &t, &k);
    S.gao(t);
    int rt = 0, sum = 0;
    for (int i = 0; i < 26; ++i)
        sum += S.f[S.son[0][i]];
    if (k > sum)    puts("-1");
    else {
        while (k) {
            for (int i = 0; i < 26; ++i)
                if (S.son[rt][i]) {
                    if (S.f[S.son[rt][i]] >= k) {
                        printf("%c", 'a' + i);
                        k -= S.g[S.son[rt][i]];
                        rt = S.son[rt][i];
                        break;
                    }
                    else k -= S.f[S.son[rt][i]];
                }
        }
    }
    return 0;
}

发表于   |   分类于   |  

250

Description

给高度为$h_1$的棍子$r_1$个，$h_2$的$r_2$个，轮流放，问最多放出多少种不同的高度

Solution

考虑$h_1$是否等于$h_2$，再讨论即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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;
struct TheBrickTowerEasyDivOne {
    int find(int r1, int h1, int r2, int h2) {
        if (h1 == h2) {
            return 2 * min(r1, r2) + (r1 == r2 ? 0 : 1);
        }
        else {
            return 2 * min(r1, r2) + (r1 > r2) + min(r1, r2) + (r2 > r1);
        }
    }
};

500

Description

将$n$个数重新排列，使得相邻两个数最大值之和尽量小，同时字典序最小。

Solution

$n$个数算$n-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
#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;
vector<pii> s;
vector<int> ans;
bool vis[N];
struct TheBrickTowerMediumDivOne {
    vector <int> find(vector <int> a) {
        int n = a.size();
        ans.pb(0), vis[0] = 1;
        for (int i = 1; i < n; ++i) {
            int p = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && a[j] <= a[ans[i - 1]]) {
                    p = j;
                    break;
                }
            }
            if (~p) ans.pb(p), vis[p] = 1;
            else break;
        }
        for (int i = 0; i < n; ++i)
            if (!vis[i])    s.pb(mp(a[i], i));
        sort(s.begin(), s.end());
        for (int i = 0; i < s.size(); ++i)  ans.pb(s[i].S);
        return ans;
    }
};

发表于   |   分类于   |  

之前一个月打了三场比赛，CCPC，沈阳和合肥。总体来说成绩比较满意吧，两银一金，但还是有很多遗憾

CCPC是技不如人，$F$题不会做

沈阳侥幸拿金，$G$那个$sb$题由于是手推公式调到死精度过不去，赛后改二分解方程就秒了

最遗憾的是合肥，自己上来把$H$题$k=2$的情况构造好了，结果忘了$k$可以等于$3$这种更trival的情况，坑了无数罚时，对不起队友QvQ

最后$A$题$cdq+NTT$的题，最后没有调对，由于自己最后时候写的有点紧张导致写了好多$SB$错误，以及原根求错了= =b(卜是窝的锅23333~)

讲道理的话，之前$SB$题不坑，省下来的时间，我$A$肯定可以调对的= =，菜是原罪。。坑了队友，最后拿了银牌第二，我的锅

这几场比赛暴露了好多问题，也幸好沈阳侥幸拿了金，不然合肥真是遗憾死了

感谢队友cpc,syx,大腿带窝飞，没有嫌弃窝坑了他们>_<，如果过段时间有时间或者心情或许会详细总结一下吧，接下来可以好好休息一段时间，补补姿势，调整调整状态，$EC-final$见！希望能有个好成绩~

发表于   |   分类于   |  

250

Solution

把$-1$分别替换为$0,1,2$来判断答案是否变化即可。简单粗暴

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
#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;
LL gao(vector<int> a) {
    stack<LL> S;
    int n = a.size();
    for (int i = 0; i < 100; ++i)   S.push(0);
    for (int i = 0; i < n; ++i) {
        if (!a[i]) {
            LL x = S.top();
            S.pop();
            LL y = S.top();
            S.pop();
            S.push(x + y);
        }
        else S.push(a[i]);
    }
    return S.top();
}
struct Suminator {
    int findMissing(vector <int> a, int S) {
        int n = a.size();
        int p;
        for (int i = 0; i < n; ++i) 
            if (a[i] == -1) p = i;
        a[p] = 0;
        LL t = gao(a);
        if (t == S) return 0;
        a[p] = 1;
        LL u = gao(a);
        a[p] = 2;
        LL v = gao(a);
        if (u == v) return -1;
        if (u <= S) return S - u + 1;
        return -1;
    }
};

500

Description

求将地图染成$2$个凸连通块的方案数

Solution

这是道比较有趣的题，首先发现，如果有一段连续的格子被染成同一颜色，在以后的行上，被同色染的格子数一定非递增或非递减，且会确定以后行的状态。于是可以$dp$，大概就是$dp$到第$i$行连续$j$个格子被染成同一颜色，当前状态是非递增还是非递减还是尚未确定。$记忆化搜索可能好写一点$。

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
#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, M = 1e9 + 7;
int n, m;
int dp[N][N][3][2][2];
bool bw[N][N], wb[N][N];
int f(int x, int y, int dir, int ok1, int ok2) {
    if (x == n) {
        if (y == m && dir == 2) return 0;
        return ok1 + ok2;
    }
    int &t = dp[x][y][dir][ok1][ok2];
    if (~t) return t;
    t = 0;
    for (int num = 0; num <= m; ++num) {
        if (dir == 0 && num < y || dir == 1 && num > y) continue;
        int ndir = dir;
        if (dir == 2 && num < y)    ndir = 1;
        if (dir == 2 && num > y)    ndir = 0;
        if (x == 0) ndir = 2;
        if (y == m && num == 0) continue;
        int t1 = ok1, t2 = ok2;
        if (!bw[x][num])    t1 = 0;
        if (!wb[x][num])    t2 = 0;
        (t += f(x + 1, num, ndir, t1, t2)) %= M;
    }
    return t;
}
struct TwoConvexShapes {
    int countWays(vector <string> grid) {
        n = grid.size(), m = grid[0].size();
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= m; ++j) {
                bw[i][j] = 1;
                for (int k = 0; k < j; ++k)
                    if (grid[i][k] == 'W')  bw[i][j] = 0;
                for (int k = j; k < m; ++k)
                    if (grid[i][k] == 'B')  bw[i][j] = 0;
                wb[i][j] = 1;
                for (int k = 0; k < j; ++k)
                    if (grid[i][k] == 'B')  wb[i][j] = 0;
                for (int k = j; k < m; ++k)
                    if (grid[i][k] == 'W')  wb[i][j] = 0;
            }
        int ans = 0;
        (ans += f(0, 0, 2, 1, 1)) %= M;
        return ans;
            
    }
};