Dylan's Blog
0%

Posted on Edited on In

问题描述

小A在平面上 $(0,0)$ 点的位置，第 $i$ 栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$ 的线段表示，其中 $Hi$为第 $i$ 栋楼房的高度。如果这栋楼房上任何一个高度大于 $0$ 的点与 $(0,0)$ 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 $M$ 天。初始时，所有楼房都还没有开始建造，它们的高度均为 $0$。在第 $i$ 天，建筑队将会将横坐标为 $X_i$ 的房屋的高度变为 $Y_i$ (高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

输入

第一行两个正整数 $N,M$

接下来 $M$ 行，每行两个正整数 $X_i,Y_i$

输出

$i$ 行一个整数表示第 $i$ 天过后小A能看到的楼房有多少栋

思路

如果从分块的角度入手，思路会比较简单。对于每一个块维护一个栈，栈内存放这一个块中能够看见的楼房（不考虑该块外部的楼房）。对于修改操作，直接将所在块的栈删去重构；对于询问操作，以前面的最大值在每一个栈中二分。当每一块大小为 $\sqrt{n \log size}$ 时，复杂度为 $n\sqrt{n\log size}$。

其实这个也可以用线段树维护。每一个节点维护区间最大值和该区间中的答案，考虑如果将两个区间的答案合并。左区间的答案肯定要全部算上，而右区间的答案就与左区间最大值有关，我们设这个值为 $val$。如果右区间的左子区间的最大值小于 $val$，显然这个区间的答案为 $0$，我们只需要递归计算右区间的答案；如果右区间的左子区间的最大值大于 $val$，那么原先右区间的贡献不会变，我们只需要递归计算左区间的答案。因此对于每一个区间都需要向下再递归 $\log n$ 层合并答案，那么总复杂度就是 $O(n\log^2 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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, bel[MAXN], top[400];
LD h[MAXN], sta[400][405];

int main()
{
    scanf("%d%d", &n, &m);
    siz=400;
    for(rint i=1; i<=n; ++i) bel[i]=(i-1)/siz+1;
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        int pos=bel[x], ans=0;
        top[pos]=0, h[x]=1.0*y/x;
        for(rint j=(pos-1)*siz+1; j<=pos*siz; ++j)
            if(h[j]>sta[pos][top[pos]]) sta[pos][++top[pos]]=h[j];
        LD maxn=0;
        /*
        for(rint j=1; j<=bel[n]; ++j)
        {
            printf("%d:", j);
            for(rint k=1; k<=top[j]; ++k) printf("%lf ", sta[j][k]);
            printf("\n");
        }
        */
        for(rint j=1; j<=bel[n]; ++j)
        {
            int l=1, r=top[j], p=top[j]+1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(sta[j][mid]>maxn+eps) p=mid, r=mid-1;
                else l=mid+1;
            }
            ans+=top[j]-p+1;
            maxn=max(maxn, sta[j][top[j]]);
        }
        printf("%d\n", ans);
    }
    return 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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define P 998244353
#define INF 0x3f3f3f3f
#define eps 1e-11
#define rint register int
#define LL long long
#define LD long double
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int n, m, sum[MAXN*4];
LD maxn[MAXN*4];

int cal(int root, int l, int r, LD k)
{
    if(l==r) return maxn[root]>k;
    if(maxn[ls]>k) return cal(ls, l, mid, k)+sum[root]-sum[ls];
    else return cal(rs, mid+1, r, k);
}

void update(int root, int l, int r, int x, LD k)
{
    if(l==r)
    {
        sum[root]=1, maxn[root]=k;
        return;
    }
    if(x<=mid) update(ls, l, mid, x, k);
    else update(rs, mid+1, r, x, k);
    maxn[root]=max(maxn[ls], maxn[rs]);
    sum[root]=sum[ls]+cal(rs, mid+1, r, maxn[ls]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        update(1, 1, n, x, 1.0*y/x);
        printf("%d\n", sum[1]);
    }
    return 0;
}

Posted on Edited on In

2 月 19 日 Educational Codeforces Round 60 比赛链接：https://codeforces.com/contest/1117

F - Crisp String

思路：

首先我们考虑删去哪些字符集是合法的。有一种很直观的做法就是枚举字符集，然后再用 $O(n)$ 判断是否合法，但这复杂度显然是不符合要求的。考虑统计非法的情况，可以对于每一个字母枚举与它产生矛盾的字符对，那么让这两个字母相邻的所有字符集都是非法的。这个的可以 $O(nq^2)$ 预处理，$(2^qq^2)$ 统计得到。

知道了那些字符集合法后，我们就需要计算出经过题目所给操作，能得到的答案最小的字符集。这个对合法字符集进行简单的 DP 即可得到。

代码链接

G - Recursive Queries

思路：

每一个询问其实要求的就是 $\sum_{i=l}^r(max(l_i, l)+min(r_i, r))$，$l,r$ 就是该询问的左右端点，$l_i,r_i$ 表示一个过点 $i$ 的一个极长区间，该区间的所有元素都小于等于 $p_i$。

发现这个东西不好维护，但我们可以换一个角度，考虑每个点对询问的贡献。那么对于询问 $l,r$，答案应该就是 $l \sim r$ 中每一个点对 $r$ 的贡献减去对 $l$ 的贡献之和。我们考虑点 $i$ 对于位置 $pos$ 的贡献，如果$pos < l_i$ 贡献为 $l_i$；如果$l_i < pos < r_i$ 贡献为 $pos$；如果$r_i < pos$ 贡献为 $r_i$。于是我们用线段树维护这个的和就可以在 $O(n \log n)$ 内得出答案。

代码链接

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