Dylan's Blog
0%

Posted on Edited on In

2 月 14 日 Codeforces Global Round 1 题目链接：https://codeforces.com/contest/1110

F - Nearest Leaf

思路：

考虑用线段树维护当前点到叶子节点的距离，那么对于询问就是查询区间最小值。我们从根节点开始，按照 dfs 序依次维护在每一个点上的线段树。当从点 $x$ 走到点 $son_x$ 且边权为 $dis$ 时，$son_x$ 子树内点的距离减少了 $dis$，其余点点距离增加了 $dis$，由于一棵子树的 dfs 序是连续的，因此就对应于线段树的区间修改。

代码链接

G - Tree-Tac-Toe

思路：

首先发现黑色是不可能赢的。为了简化情况，我们先假设所有点都是没有涂色的，然后考虑有哪些情况白色必定赢。比较简单的一种就是存在度数大于 4 的节点，然后发现如果一个点度数为 3 且有两个相邻的非叶节点时，白色也同样必胜。排除掉这两种情况后，剩下的树的形态就比较简单了。如下图一样，就是中间一条长链，两端可能会有度数为 3 的点，当然也可能没有度数为3的点。

Tree-Tac-Toe 1

然后考虑这种情况下白色怎样才能获胜，可以发现只有两端都有度数为 3 的端点且链长为偶数时，白色才能获胜。然后其余的所有情况都会是平局。

如果一开始树上有些点已经是白色了，考虑如何处理这种情况。比较巧妙的方式就是将一个白点按照下图的方式，拆成 4 个无色的点，可以发现这两种是完全等价的。然后就按照开始所讲的情况进行讨论即可。

Tree-Tac-Toe 2

代码链接

Posted on Edited on In

问题描述

小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了 $N$ 个点，经测量发现这 $N$ 个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这 $N$ 个点的相对位置有关，因此不妨设坐标分别为 $(1, y_1) , (2, y_2), …, (n, y_n)$ 其中 $y_1$ 到 $y_n$ 是 $1$ 到 $N$ 的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与 4 个纵坐标值的相对大小排列顺序有关）： 闪电图腾 崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为 A 类，右边为 B 类（同样，图腾的形式也都只与 4 个纵坐标值的大小排列顺序有关）： A山峰图腾 小布的团队希望知道，这 $N$ 个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对 $16777216$ 的余数。

输入

第一行包含一个整数 $N$ ($N≤200000$) 为点的数目。 接下来一行包含 $N$ 个整数，分别为 $y1,y2,…,yn$。

输出

仅包含一个数，表示闪电图腾数目与山峰图腾数目的差值对 16777216 的余数。

思路

超级神仙的一道题。

我们先考虑所有的六种情况 $1234,1243,1324,1342,1423,1432$，然后题目要求的是 $1324-1243-1432$ 的数量。然后可以发现形如 $1xxx,12xx,13xx,1x2x,1234,1243$ 的这些情况是可以求出来的（可能还有其他的情况）。然后就将题目要求的情况变换成我们能求出的情况： $1324-1243-1432$ $=(1x2x-1423)-(12xx-1234)-(14xx-1423)$ $=1x2x-12xx+1234-14xx$ $=1234+13xx+1x2x-1xxx$

我们设 $l_i=\sum_{j=1}^{i}[a_j<a_i]$，$r_i=\sum_{j=i}^{n}[a_j<a_i]$

$1xxx$ 的数量比较好求，就是： $1234$ 的数量也不难，枚举 $3$ 的位置 $i$，那么 $4$ 的情况数就是 $n-r_i-i$，$12$ 的情况数就是 $\sum_{j=1}^{i} ([a_j<a_i] l_i)$，总数量就是： $13xx$ 的数量同样枚举 $3$ 的位置 $i$，那么 $4$ 的情况数还是 $(n-r_i-i)$，$132$ 的情况数可以先计算 $12$ 的情况数 $\sum_{j=i}^{n}([a_j<a_i] (a_j-1))$ 然后减去 $12$ 同时在 $3$ 右边的情况 ${r_i}\choose{2}$，总数量就是：

$1x2x$ 的数量可以枚举 $2$ 的位置 $i$，那么 $2$ 后面 $x$ 的情况数就是 $(n-r_i-i)$，$1x2$ 的情况数先可以计算 $1x$ 和 $x1$ 的情况数 $l_i*(i-1)$，然后减去两个数都比 $2$ 小的情况数 ${l_i \choose 2}$，最后减去 $x$ 在 $1$ 前的情况数 $\sum_{j=1}^{i} ([a_j<a_i]j)$，总数量就是： 所有这些东西都可以用树状数组在 $O(n\log n)$ 内维护。

代码

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 <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 200005
#define P 16777216
#define rint register int
#define LL long long
using namespace std;

int n, sum1, sum2, sum3, sum4, y[MAXN], l[MAXN], r[MAXN], t[MAXN];

void add(int x, int y)
{
    for (; x <= n; x += (x & -x))
        t[x] = (t[x] + y) % P;
}

int ask(int x)
{
    int ans = 0;
    for (; x; x -= (x & -x))
        ans = (ans + t[x]) % P;
    return ans;
}

int comb(int x, int y)
{
    LL up = 1, down = 1;
    for (rint i = 0; i < y; ++i)
        up *= (x - i), down *= (i + 1);
    return up / down % P;
}

int main()
{
    scanf("%d", &n);
    for (rint i = 1; i <= n; ++i)
        scanf("%d", &y[i]);
    for (rint i = 1; i <= n; ++i)
    {
        l[i] = ask(y[i]);
        r[i] = y[i] - l[i] - 1;
        add(y[i], 1);
    }
    for (rint i = 1; i <= n; ++i)
    {
        sum1 = (sum1 + comb(n - r[i] - i, 3)) % P;
    }
    memset(t, 0, sizeof(t));
    for (rint i = 1; i <= n; ++i)
    {
        sum2 = (sum2 + 1LL * (n - r[i] - i) * ask(y[i]) % P) % P;
        add(y[i], l[i]);
    }
    memset(t, 0, sizeof(t));
    for (rint i = n; i >= 1; --i)
    {
        sum3 = (sum3 + 1LL * (n - r[i] - i) * (ask(y[i]) - comb(r[i], 2) + P) % P) % P;
        add(y[i], y[i] - 1);
    }
    memset(t, 0, sizeof(t));
    for (rint i = 1; i <= n; ++i)
    {
        sum4 = (sum4 + 1LL * (n - r[i] - i) * (1LL * (i - 1) * l[i] - comb(l[i], 2) - ask(y[i])) % P + P) % P;
        add(y[i], i);
    }
    printf("%d\n", (sum2 + sum3 + sum4 - sum1 + P) % P);
}

Posted on Edited on In

2月10日 Yahoo Programming Contest 2019 题目链接：https://atcoder.jp/contests/yahoo-procon2019-qual

D - Ears

思路： 我们可以将 Snuke 走过的路抽象成这五个部分： 无论 Snuke 怎么走都会符合这个模型，只是可能有一些部分不会出现。如果发现了这个，后面只要直接 DP 就可以了。设 $f[i][j]$ 为第 $i$ 个位置属于第 $j$ 个部分的代价，转移时加上每个部分相应的代价即可。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define P 
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, a[MAXN];
LL ans=1e18, f[MAXN][5];

LL cost(int x, int op)
{
    if(op==0 || op==4) return x;
    if(op==1 || op==3)
    {
        if(!x) return 2;
        else return x&1;
    }
    if(op==2)
    {
        if(!x) return 1;
        else return !(x&1);
    }
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(f, 0x3f, sizeof(f));
    for(rint i=0; i<=4; ++i) f[0][i]=0;
    for(rint i=1; i<=n; ++i)
        for(rint j=0; j<=4; ++j)
        {
            if(j) f[i][j]=min(f[i][j], f[i][j-1]);
            f[i][j]=min(f[i][j], f[i-1][j]+cost(a[i], j));
        }
    for(rint i=0; i<=4; ++i) ans=min(ans, f[n][i]);
    printf("%lld\n", ans);
}

E - Odd Subrectangles

思路： 如果行的集合已知，有一个很巧妙的性质：如果这些行的 $m$ 位的异或和不全为 $0$，那么有 $2^{m-1}$ 个列的集合满足题目要求；否则不会有列的集合满足要求。

因此答案就变成了有多少个行的集合它们 $m$ 位的异或和不全为 $0$，这个东西和线性基的大小有关。设线性基的大小为 $siz$，那么不在线性基中 $n-r$ 个行构成的集合中的所有子集，线性基中都有唯一的集合和该子集异或和全为 $0$，因此答案就是 $2^{m-1}*(2^n-2^{n-siz})$。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 305
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, a[MAXN][MAXN], bas[MAXN][MAXN], temp[MAXN], vis[MAXN];

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%P;
        x=1LL*x*x%P; y>>=1;
    }
    return ans;
}

void insert(int a[])
{
    memcpy(temp, a, sizeof(temp));
    for(rint i=1; i<=m; ++i)
        if(temp[i])
        {
            if(!vis[i])
            {
                for(rint j=1; j<=m; ++j) bas[i][j]=temp[j];
                vis[i]=1;
                siz++;
                break;
            }
            for(rint j=1; j<=m; ++j) temp[j]^=bas[i][j];
        }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=m; ++j) scanf("%d", &a[i][j]);
    for(rint i=1; i<=n; ++i) insert(a[i]);
    printf("%d\n", 1LL*(ksm(2, n)-ksm(2, n-siz)+P)*ksm(2, m-1)%P);
}

F - Pass

思路： 有一个性质是第 $i$ 个球一个是从 $1～i$ 中的一个人手上来的。因此对于序列唯一的限制就是序列中前 $i$ 个中红球数量不能超过前 $i$ 个人手中的红球数量，对于黑球也同理，且序列中后 $n$ 球没有任何限制。然后就可以根据这个性质简单 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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 2005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, ans, r[MAXN], b[MAXN], c[MAXN*2][MAXN*2], f[MAXN][MAXN];
char s[MAXN];

int main()
{
    scanf("%s", s+1);
    n=strlen(s+1);
    c[0][0]=1;
    for(rint i=1; i<=n*2; ++i)
        for(rint j=0; j<=i*2; ++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    for(rint i=1; i<=n; ++i)
    {
        if(s[i]=='0') r[i]=2;
        if(s[i]=='1') r[i]=b[i]=1;
        if(s[i]=='2') b[i]=2;
        r[i]+=r[i-1], b[i]+=b[i-1];
    }
    f[0][0]=1;
    for(rint i=1; i<=n; ++i)
        for(rint j=max(0, i-b[i]); j<=min(i, r[i]); ++j)
        {
            f[i][j]=(f[i][j]+f[i-1][j])%P;
            if(j) f[i][j]=(f[i][j]+f[i-1][j-1])%P;
        }
    for(rint i=max(0, n-b[n]); i<=min(i, r[n]); ++i) ans=(ans+1LL*c[n][r[n]-i]*f[n][i]%P)%P;
    printf("%d\n", ans);
    return 0;
}

Posted on Edited on In

问题描述

有关系式 $fi = \left(\prod{j = 1}^{k} f{i - j}^{b_j}\right) \bmod p$，$p$ 为 $99844353$，并且设 $f_1 = f_2 = \ldots = f{k - 1} = 1$。题目告诉你 $b_1, b_2, \ldots, b_k$ 及 $f_n$，需要你求出 $f_k$。

输入

第一行一个正整数 $k$

第二行 $k$ 个整数表示 $b_1, b_2, \ldots, b_k$

第三行两个整数 $n, m$ 表示 $f_n=m$

输出

输出一个满足 $1 \leq f_k < p$ 的 $f_k$，如果有多个输出任意一个，如果不存在输出 $-1$

思路

思路不难，比较的套路，综合了很多知识点。

首先想到将系数递推关系写成矩阵的形式，然后利用矩阵快速幂将 $fn$ 写成 $f_n= \left(\prod{i = 1}^{k} f{k-i+1}^{a_i}\right) \bmod p$ 的形式，因为题目设 $f_1 = f_2 = \ldots = f{k - 1} = 1$，所以我们实际上要解一个形如 $x^a \equiv b \mod p$ 的方程。

解这个方程比较的套路。先将上面的方程写成离散对数的形式 $k^{a\log_kx} \equiv k^{\log_kb} \mod p$，再根据欧拉定理得到 $a\log_kx \equiv \log_kb \mod \varphi (p)$。其中 $k$ 应该要为 $p$ 的原根，因为这样 $k^1,k^2,…,k^{\varphi(p)}$ 是模 $\varphi(p)$ 的一个完全剩余系，这样就可以避免出现多个 $\log_kx$ 在模 $p$ 意义下的值相同。后面就很简单了，先用 BSGS 求出 $\log_kb$ 然后用 EXGCD 得到 $\log_kx$，最后用快速幂得出最终答案 $x$ 就好了。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 105
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, x, y, a[MAXN][MAXN], c[MAXN][MAXN], ans[MAXN][MAXN];

map<int, int> mp;

void mul(int a[MAXN][MAXN], int b[MAXN][MAXN])
{
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=n; ++j)
        {
            c[i][j]=0;
            for(rint k=1; k<=n; ++k) c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%(p-1);
        }
    memcpy(a, c, sizeof(c));
}

void ksm1(int a[MAXN][MAXN], int y)
{
    for(rint i=1; i<=n; ++i) ans[i][i]=1;
    while(y)
    {
        if(y&1) mul(ans, a);
        mul(a, a); y>>=1;
    }
}

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%p;
        y>>=1; x=1LL*x*x%p;
    }
    return ans;
}

int bsgs(int a, int b)
{
    int siz=sqrt(p)+0.5, base=1;
    int t=b;
    mp[t]=0;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*a%p;
        mp[t]=i;
        base=1LL*base*a%p;
    }
    t=1;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*base%p;
        if(mp.count(t))
        {
            int x=i*siz-mp[t];
            return x;
        }
    }
    return -1;
}

int exgcd(int a, int b, LL& x, LL& y)
{
    if(!b)
    {
        x=1, y=0;
        return a;
    }
    int d=exgcd(b, a%b, x, y);
    int temp=x; x=y, y=temp-a/b*y;
    return d;
}

int solve(int a, int b, int c)
{
    LL x, y;
    int d=exgcd(a, b, x, y);
    //printf("%d %d %d %d!!!\n", a, b, c, d);
    if(c%d) return -1;
    x*=c/d;
    return (x%(b/d)+(b/d))%(b/d);
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[1][i]);
    for(rint i=2; i<=n; ++i) a[i][i-1]=1;
    scanf("%d%d", &m, &y);
    ksm1(a, m-n);
    x=solve(ans[1][1], p-1, bsgs(3, y));
    if(x==-1) printf("-1\n");
    else printf("%d\n", ksm(3, x));
    return 0;
}

Posted on Edited on In

问题描述

简单来说就是限制空间，给你一个大小为 $5500$ 的数组，除该数组外不能调用其他储存。

然后有一辆长度为 $n$ 的火车，第 $i$ 节车厢上有编号 $c_i$，你需要按顺序输出每 $k$ 节车厢中的最小编号。

输入 & 输出

因为交互题，内容较多，详细内容见链接 Train Tracking 题面。

思路

我们设 $f_i$ 为 从 $i-k+1$ 到 $i$ 中最小值的下标，对于 $f$ 不难想到用单调队列去优化，但是显然是不能将所有元素加入队列中，这时我们就可以利用分块。我们设 $siz$ 为块的大小，第一遍扫过去时只计算 $f_{x*siz+k}$，这样就只需要把每一个块中的最小值放入队列中，并记录下 $f_{x*siz+k}$ 给第二遍的时候用。

第二遍时我们就需要根据 $f_{x*siz+k}$ 计算出所有的 $f$。我首先可以先忽略掉下标小于 $f_0$ 的元素，然后用一个大小同为 $siz$ 的单调队列维护最前的一段，后面的只需要记录下最小值就行了。如果当前扫到的位置是所在块的最小值，那么就可以先输出这一块之前的答案，并建立新的单调队列。

代码

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
#include "grader.h"
/*
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, curcar, curpas, sub[5505], a[1000006];

int get(int id)
{
    return sub[id];
}

void set(int id, int val)
{
    sub[id]=val;
}

void shoutMinimum(int x)
{
    printf("%d\n", x);
}

int getTrainLength()
{
    return n;
}

int getWindowLength()
{
    return k;
}

int getCurrentCarIndex()
{
    return curcar;
}

int getCurrentPassIndex()
{
    return curpas;
}*/

void helpBessie(int val)
{
    int op=getCurrentPassIndex();
    int k=getWindowLength();
    int n=getTrainLength();
    int i=getCurrentCarIndex();
    int siz=1000, QWQ=4400, INF=0x3f3f3f3f;
    if(!op)
    {
        if(i==0) set(0, 0), set(1, -1);
        int head=get(1), tail=get(0);
        if(i%siz==0 || (i>=k && (i-k)%siz==0))
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int headval=get(head*2+3);
            if(val<=headval)
            {
                while(head>=tail && get(2*head+3)>=val) head--;
                head++;
                set(2*head+2, i);
                set(2*head+3, val);
            }
        }
        if(i>=k-1 && (i+1-k)%siz==0)
        {
            while(head>=tail && get(tail*2+2)<=i-k) tail++;
            set(QWQ+(i+1-k)/siz, get(tail*2+2));
        }
        set(0, tail), set(1, head);
    }
    else
    {
        if(i<get(QWQ)) return;
        if(i==get(QWQ))
        {
            set(0, 0), set(1, -1);
            set(QWQ-1, 1);
            set(QWQ-2, INF);
            set(QWQ-3, 0);
        }
        int block=get(QWQ-1), l=get(QWQ-3);
        int head=get(1), tail=get(0);
        if(i-get(QWQ+block-1)<=siz)
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int minnum=get(QWQ-2);
            if(val<minnum) set(QWQ-2, val);
        }
        if(l+k-1==i)
        {
            while(head>=tail && get(tail*2+2)<l) tail++;
            int a=get(QWQ-2), b=get(2*tail+3);
            shoutMinimum(a<b?a:b);
            l++;
        }
        while(siz*block+k-1<n && get(QWQ+block)==i)
        {
            while(l<=siz*block)
            {
                while(head>=tail && get(tail*2+2)<l) tail++;
                int a=get(QWQ-2), b=get(2*tail+3);
                shoutMinimum(a<b?a:b);
                l++;
            }
            block++;
            set(QWQ-2, INF);
            head=tail=0;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        set(QWQ-1, block), set(QWQ-3, l);
        set(0, tail), set(1, head);
    }
}

/*
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i)
    {
        scanf("%d", &a[i]);
        curcar=i, curpas=0;
        helpBessie(a[i]);
    }
    for(int i=0; i<n; ++i)
    {
        curcar=i, curpas=1;
        helpBessie(a[i]);
    }
}*/