https://ac.nowcoder.com/acm/contest/17148

C - Alice and Bob

 

题意：给定数组 aa，常数 KK，多次询问，每次问区间 [L,R][L,R] 中有几个连续子区间中不同的数的个数大于等于 KK。

尺取+二分/主席树

首先尺取求出以每个位置为右端点时满足条件的最右的左端点。

查询时只要找到最靠左的完整在 [L,R][L,R] 中的区间。可以二分做到。

但这里脑子一热写了个主席树，就当是实现下上次浙江省赛的那道主席树了。

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

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n, m, K;
unordered_map<int, int> mp;
int a[N];

#define mid ((l+r)>>1)
int tot, root[N];
struct X {
    int lc, rc, cnt;
    ll sum;
} tr[N * 40];

void upd(int q, int l, int r, int &rt, int pre) {
    tr[++tot] = tr[pre];
    rt = tot;
    tr[rt].cnt++;
    tr[rt].sum += q;
    if (l == r)return;
    if (q <= mid)upd(q, l, mid, tr[rt].lc, tr[pre].lc);
    else upd(q, mid + 1, r, tr[rt].rc, tr[pre].rc);
}

int cnt; ll sum;

void qry(int ql, int qr, int l, int r, int rt) {
    if (ql <= l && qr >= r) {
        cnt += tr[rt].cnt;
        sum += tr[rt].sum;
        return;
    }
    if (ql <= mid)qry(ql, qr, l, mid, tr[rt].lc);
    if (qr > mid)qry(ql, qr, mid + 1, r, tr[rt].rc);
}

vector<pii> vc;

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int p = n;
    for (int i = n; i >= 1; i--) {
        if (i < n) {
            mp[a[i + 1]]--;
            if (!mp[a[i + 1]])mp.erase(a[i + 1]);
        }
        while (p >= 1 && mp.size() < K) {
            mp[a[p]]++;
            p--;
        }
        if (mp.size() >= K) {
            vc.push_back({i, p + 1});
        }
    }
    sort(vc.begin(), vc.end());
    for (int i = 0; i < (int) vc.size(); i++) {
        pii pp = vc[i];
        if (i > 0)for (int j = vc[i - 1].first + 1; j < vc[i].first; j++)root[j] = root[j - 1];
        upd(pp.second, 1, n, root[pp.first], root[pp.first - 1]);
    }
    ll ans = 0;
    while (m--) {
        int L, R, tL, tR;
        scanf("%d%d", &tL, &tR);
        L = min((tL ^ ans), (tR ^ ans)) + 1;
        R = max((tL ^ ans), (tR ^ ans)) + 1;
        cnt = 0, sum = 0;
        qry(L, R, 1, n, root[R]);
        ans = sum - 1ll * (L - 1) * cnt;
        printf("%lld\n", ans);
    }
    return 0;
}

 

E - Dance with a stick

 

题意：给定平面上 nn 个坐标都为整数的点 −108≤xi,yi≤108-10^8\le x_i,y_i\le 10^8，要求选出一个点，以及一条穿过该点的无限长的直线，该直线顺时针转动，当穿过另一个点时以新点为中心继续转动。要求选出的点和直线满足当直线转动180°后仍位于该选中点。输出点坐标和直线方向向量。

构造

当 nn 为偶数时必无解，nn 为奇数时必有解。

把所有点按照 x 坐标第一关键字，y 坐标第二关键字排序，中间的那个就是选中的点。直线的方向向量为 (−1,109)(-1,10^9)。

首先要发现直线转动时始终保持直线两边的点数与初始时相同。而我们构造出的直线必定只会穿过一个点，因为 10910^9 精度大于 10810^8，不可能有穿过两个格点。且初始时直线两边的点数相同。

所以当转180°，斜率相同时，只有在相同位置才能够保持直线两边点数相同，否则就是平移，平移到任意其它点都不行。

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

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n;
pii a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].first, &a[i].second);
    if (n % 2 == 0) {
        puts("No");
        return 0;
    }
    puts("Yes");
    sort(a + 1, a + n + 1);
    printf("%d %d %d %d\n", a[(n + 1) / 2].first, a[(n + 1) / 2].second, -1, 1000000000);
    return 0;
}

 

H - 焦糖布丁

 

题意：给定长为 nn 的数组 aa，问能否要求构造出一棵 n+1n+1 个节点的树，树根上没有石子，其它每个节点上的石子数等于对应的数组元素值，在树上进行博弈，两人轮流选择一个节点，把节点上任意正整数个石子移动到它的父节点上，无法移动的人输。问能否构造出这棵树使得后手胜。

博弈+线性基

这是树上的阶梯尼姆游戏。

阶梯Nim

阶梯尼姆游戏只需要判断奇数台阶上石子数的异或和，不为 0 则先手胜，为 0 则后手胜。

树上阶梯尼姆只需要判断深度为奇数的节点上的石子数的异或和，不为 0 则先手胜，为 0 则后手胜。

则判断能否构造等价于判断是否存在一个子集的异或和为 0。

判断是否存在子集的异或和为 0 等价于判断是否满秩，计算秩则可以用线性基。若线性基无法插入则表示存在线性相关，即存在子集异或和为 0.

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

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

struct Linear_Basis {
    ll b[63], nb[63], tot, len;    //共len个基，(1ll<<len)个不同的异或和值，包括0

    void init() {
        tot = 0;
        memset(b, 0, sizeof(b));
        memset(nb, 0, sizeof(nb));
    }

    bool ins(ll x)//插入
    {
        for (int i = 62; i >= 0; i--)
            if (x & (1ll << i)) {
                if (!b[i]) {
                    b[i] = x;
                    len++;
                    break;
                }
                x ^= b[i];
            }
        return x > 0;
    }

} LB;

int T;
int n;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        LB.init();
        bool f = 1;
        for (int i = 1; i <= n; i++) {
            ll x;
            scanf("%lld", &x);
            if (!LB.ins(x))f = 0;
        }
        puts(f ? "No" : "Yes");
    }
    return 0;
}

 

D - Connie

 

题意：给定只由字符 c,o,n,i,e 组成的字符串 s，定义字符串 t 的得分等于 2k2^k，kk 为 s 在 t 中作为子串出现的次数。问长为 nn 且只包含字符 c,o,n,i,e 的字符串的期望得分。

KMP自动机+dp

dp[i][j]dp[i][j] 表示 tt 串到第 ii 位，ss 串到第 jj 位，所有方案得分之和。

KMP自动机中数组 trans[i][c]trans[i][c] 表示从位置 ii 经过字符 cc 转移到位置 jj。

则 dp[i+1][trans[i][c]]+=dp[i][j]∗(trans[i][c]==n?2:1)dp[i+1][trans[i][c]]+=dp[i][j]*(trans[i][c]==n?2:1)，即若当前接收 cc 后出现了完整的串 ss，则该状态所有方案的 ss 的出现次数+1，即得分要*2；否则只需要累加当前得分。

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

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int fail[N], trans[N][30]; //fail即KMP中nxt，trans表示从第i位经过字符j转移到的位置

void build(char *s) {    // s从1开始
    int n = strlen(s + 1);
    fail[0] = 0, fail[1] = 0;
    trans[0][s[1] - 'a'] = 1, trans[1][s[2] - 'a'] = 2;
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && s[j + 1] != s[i])j = fail[j];
        fail[i] = j = (s[j + 1] == s[i] ? j + 1 : j);
        if (i < n)trans[i][s[i + 1] - 'a'] = i + 1;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            if (!trans[i][j])trans[i][j] = trans[fail[i]][j];
        }
    }
}

int n, m;
char s[N];
char ch[]{"conie"};
ll dp[110][110];

ll Pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    build(s);
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k < 5; k++) {
                dp[i + 1][trans[j][ch[k] - 'a']] =
                        (dp[i + 1][trans[j][ch[k] - 'a']] + dp[i][j] * (trans[j][ch[k] - 'a'] == m ? 2 : 1)) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= m; i++)ans = (ans + dp[n][i]) % mod;
    printf("%lld\n", ans * Pow(Pow(5, n), mod - 2) % mod);
    return 0;
}