Problem.1 等比数列求和

题目标签：分治、数学

题目大意

对于有 \(x+1\) 项的等比数列 \(A=a^0+a^1+\cdots+a^x\)，求

\[ (\sum\limits_{i-1}^xa^i)\bmod p \]

数据范围

\(1\leq a_i,x\leq 10^{18},1\leq p\leq 10^9\)。

解题思路

考虑分治。

对于指数区间 \([0,m]\)，令 \(m'=\dfrac{m+1}{2}-1\)。考虑对 \([0,m']\) 和 \([m'+1,m]\) 分治进行处理。

对于区间 \([0,m']\)，求得 \(U=\sum\limits_{i=0}^{m'}a^i\)。

对于区间 \([m'+1,m]\)，可以同时通过分治计算 \(V=a^{m'+1}\)，然后进行分类讨论：

  • 若 \(m\) 为奇数，则有偶数项，此时区间和为

\[ U+UV \]

  • 若 \(m\) 为偶数，则有奇数项，考虑先处理前 \(m-1\) 项，最后加上第 \(m\) 项，则区间和为

\[ U+UV+V^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
#include<iostream>
using namespace std;
typedef long long ll;
ll x,a,p;
ll v;
ll work(ll m){
    if(!m){
        v=1;
        return 1;
    }
    ll mid=(m+1)/2-1;
    ll u=work(mid);
    ll lv=v;
    v=v*a%p;
    if(m&1){
        ll ans=(u+u*v%p)%p;
        v=lv*lv%p*a%p;
        return ans;
    }
    else{
        ll ans=(u+u*v%p+v*v%p)%p;
        v=v*v%p;
        return ans;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>a>>x>>p;
        a%=p;
        cout<<work(x)<<endl;
    }
    return 0;
}

Problem.2 LIS Number

题目标签：组合数学、动态规划

题目来源：Topcoder SRM 585

题目大意

设 \(A\) 是一个整数序列，LIS Number 是把 \(A\) 切成几个数列，每个数列内的数都单调增，能分出来的最小数列数。

例如，\(A=\{1,4,4,2,6,3\}\) 的 LIS Number 是 \(4\)，因为我们可以用 \(\{1,4\} + \{4\} + \{2,6\} + \{3\}\) 得到 \(A\)，并且没有办法创造一个连接 \(3\)（或更少）个单调增序列。

特殊地，一个单调增序列的 LIS Number 是 \(1\)。

你有 \(n\) 种类型的卡片。每一个 \(i\)，对于 \(0\leq i<n\)，你有 \(cnt_i\) 张 \(i\) 型卡。每张第 \(i\) 型卡上的数是 \(i\)。

给你 \(cnt\) 数组和整数 \(k\)。你要排所有的卡成排，使所得到的整数序列的 LIS Number 是 \(k\) 。 注意，你必须使用所有的卡，你只能选择它们的顺序。

计算 \(x\) 为你能产生的不同满足上述条件的序列数。计算并输出数 \(x\) 模 \(1000000007(10^9+7)\)。

数据范围

\(1 \leq n \leq 36,1\leq cnt_i \leq 36,1 \leq k \leq 1296\)

解题思路

考虑由小到大插入每种数字，进行动态规划。

我们设状态 \(f_{i,j}\) 为：插入完前 \(i\) 种数字，共生成了 \(j\) 个上升序列的方案数。

我们把安排好的数字看做一个序列，设当前序列里有 \(sum\) 个数字，我们要新安排进去的这种数字一共有 \(cnt\) 个。

此时我们新加入一种新的数字。如果我们把一些数字安排到原来的每个上升序列的末尾，则这个大序列的 LIS Number 不变，而插入到其他位置，必然会导致 LIS Number 个数增加。

考虑枚举放 \(t\) 个数字到共有 \(j\) 个上升序列的大序列末尾（即不会改变序列答案），则序列答案会增加 \(cnt-t\)。

我们要把 \(u=cnt-t\) 个数放在 \(v=sum+1-j+t\) 个位置里（因为在总共的 \(sum+1\) 个空格中，有 \(j-t\) 个位置已经被“放置在序列末尾”的策略占据），就可以把问题抽象成：把排成一列的 \(u\) 个球，分成 \(v\) 个抽屉里，允许有抽屉空着不放，求所有分法的方案数——这就可以用组合数处理，方案数为 \(C_{u+v-1}^u\)。

所以递推式为

\[ f_{i,j+u}=f_{i-1,j}\cdot C_j^t \cdot C_{u+v-1}^u \]

参考代码

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<iostream>
using namespace std;
#define MAXN 1305
#define mod 1000000007
typedef long long ll;
int n,cnt[MAXN],k;
ll f[MAXN][MAXN],C[MAXN][MAXN];
int main(){
    freopen("LISNumber.in","r",stdin);
    freopen("LISNumber.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>cnt[i];
    cin>>k;
    C[0][0]=1;
    for(int i=1;i<=1296;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
            C[i][j]%=mod;
        }
    }
    f[1][cnt[1]]=1;
    int sum=cnt[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=k;j++) if(f[i-1][j]){
            for(int t=0;t<=min(j,cnt[i]);t++){
                int x=sum+1-j+t;
                int y=cnt[i]-t;
                f[i][j+y]+=f[i-1][j]*C[j][t]%mod*C[x+y-1][y]%mod;
                f[i][j+y]%=mod;
            }
        }
        sum+=cnt[i];
    }
    cout<<f[n][k];
    return 0;
}

Problem.3 小蓝的旅行计划

题目标签：贪心、线段树

题目来源：第十四届蓝桥杯大赛软件赛省赛

题目大意

小蓝正计划进行一次漫长的旅行。小蓝计划开车完成这次旅行。显然他在途中需要加油，否则可能无法完成这次旅行。

小蓝要依次经过 \(n\) 个地点，其中从第 \(i-1\) 个地点到达第 \(i\) 个地点需要消耗 \(Dis_i\) 升油。小蓝经过的每个地点都有一个加油站，但每个加油站的规定也不同。在第 \(i\) 个加油站加 \(1\) 升油需要 \(Cost_i\) 的费用，且在这个加油站最多只能加 \(Lim_i\) 升油。

小蓝的车的油箱也有容量限制，他的车上最多只能装载 \(m\) 升油。

一开始小蓝的油箱是满的，请问小蓝需要准备多少钱才能顺利完成他的旅行计划。如果小蓝按给定条件无论准备多少钱都不能完成他的旅行计划，请输出 \(-1\) 。

数据范围

\(1 \leq n \leq 2\times 10^5\;,\;1 \leq Dis_i\;,\;Lim_i\;,\;m \leq 10^9\)。

解题思路

考虑从第 \(1\) 个点到第 \(n\) 个点，逐个贪心考虑。

从开头开始旅行，每走到一个点，尽可能少地加油，使得可以到达这个点，一定比加好多油到这里划算。

所以只考虑到达该点时，剩余的油量 \(oil<0\) 的情况时，在前面的加油站进行加油操作。

但是在哪里加油可以保证加油之后，一直走到这个当前的节点，一路上任何时刻油量小于油箱容量 \(m\)，并且花费最少呢？

考虑贪心处理，利用优先队列记录前面每一个加油站能加的油量和单价。注意，在到达位置 \(i\) 时，在位置 \(j\) 加油，需要保证加 \(k\) 升油之后，使得对于在 \([j,i]\) 中任意时刻，油箱里的油量需要小于等于 \(m\)。而在这里加完 \(k\) 升油之后，会对后面旅途的油量产生影响，需要对 \([j,i]\) 区间中的油量加上 \(k\)。

考虑用线段树记录每个节点时的油量，进行区间查询、区间修改、单点修改。

当没有油可以加，并且到不了节点 \(i\) 时（即 \(oil<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
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
#include<iostream>
#include<queue>
using namespace std;
#define MAXN 200005
#define mid ((tree[p].l+tree[p].r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
typedef long long ll;
ll ans;
int n,m;
struct K{
    int cost,lim,id;
    bool operator<(K x)const{
        return cost>x.cost;
    }
};
priority_queue<K> q;
struct node{
    int l,r,maxx,tag;
}tree[MAXN<<2];
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(tree[p].l==tree[p].r) return;
    build(l,mid,ls);
    build(mid+1,r,rs);
}
void pushdown(int p){
    if(tree[p].tag){
        int k=tree[p].tag;
        tree[ls].maxx+=k;
        tree[ls].tag+=k;
        tree[rs].maxx+=k;
        tree[rs].tag+=k;
        tree[p].tag=0;
    }
}
void update(int p){
    tree[p].maxx=max(tree[ls].maxx,tree[rs].maxx);
}
void modify(int l,int r,int k,int p){
    if(l<=tree[p].l&&r>=tree[p].r){
        tree[p].maxx+=k;
        tree[p].tag+=k;
        return;
    }
    pushdown(p);
    if(l<=mid) modify(l,r,k,ls);
    if(r>mid) modify(l,r,k,rs);
    update(p);
}
int query(int l,int r,int p){
    if(l<=tree[p].l&&r>=tree[p].r) return tree[p].maxx;
    int ans=0;
    pushdown(p);
    if(l<=mid) ans=max(ans,query(l,r,ls));
    if(r>mid) ans=max(ans,query(l,r,rs));
    return ans;
}
int main(){
    cin>>n>>m;
    build(1,n,1);
    int oil=m;
    for(int dist,cost,lim,i=1;i<=n;i++){
        cin>>dist>>cost>>lim;
        oil-=dist;
        modify(i,i,oil,1);
        if(oil>=0){
            q.push({cost,lim,i});
            continue;
        }
        while(q.size()&&oil<0){
            K now=q.top();
            q.pop();
            int cost=now.cost,lim=now.lim,id=now.id;
            int maxx=query(id,i-1,1);
            lim=min(lim,m-maxx);
            int add=min(lim,-oil);
            lim-=add;
            ans+=add*cost;
            oil+=add;
            if(lim) q.push({cost,lim,id});
            modify(id,i,add,1);
        }
        if(oil<0){
            cout<<-1;
            return 0;
        }
        q.push({cost,lim,i});
    }
    cout<<ans;
    return 0;
}

Problem.4 Distinct Numbers

题目标签：博弈论

题目来源：ARC137C

题目大意

给定长为 \(N\) 的非负整数列 \(A:a_1,a_2,\cdots a_n\)，保证元素互不相同。

Alice 和 Bob 在玩游戏。Alice 为先手，两人轮流操作。每次操作选手可以如下进行：

  • 选择当前 \(A\) 中最大的元素，将其替换为一个更小的非负整数。要求替换后 \(A\) 中元素仍然互不相同。

首先无法操作的一方失败。当两人都采取最优策略时，求谁有必胜策略。

数据范围

\(2\leq N \leq 3\times 10^5,0\leq a_i\leq 10^9\)。

解题思路

考虑每次都会将一个数减小，会有如下最优策略，记 \(x\) 为最大元素， \(y\) 为次大元素：

  1. 若 \(y+1<x\)，即 \(x,y\) 之间有空位。操作者可以将 \(x\) 改变至大于 \(y\) 或小于 \(y\)，从而将局面交给对方。如果其中某个操作会失败，可以选择另一个操作。因为两种操作最后交给对方的局面是对立的。
  2. 若 \(y+1=x\)，即 \(x,y\) 之间没有空位。因为每次都会减少至少 \(1\)，每次会填补一个空，答案就会和 \(\text{mex}\) 有关系。如果有奇数个空，那么前者胜，否则前者必败。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 300005
int t,n,a[MAXN];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int num=0;
    for(int i=1;i<=n;i++){
        if(i==1) num+=a[i];
        else num+=a[i]-a[i-1]-1;
    }
    if((a[n]==a[n-1]+1&&(num&1))||a[n]!=a[n-1]+1) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
    return 0;
}

Problem.5 Present

题目标签：数学、思维

题目来源：CF1322B

题目大意

给出一个长度为 \(n\) 的数列 \(a\)。其中第 \(i\) 项为 \(a_i\)。

求

\[ \bigoplus\limits_{i=1}^n\bigoplus\limits_{j=i+1}^n(a_i+a_j) \]

其中 \(\oplus\) 表示按位异或操作。

数据范围

\(1\leq n\leq 4\times 10^5,1\leq a_i\leq 10^7\)。

解题思路

首先可以得到 \(O(n^2)\) 的暴力算法。我们换个思路考虑问题。

我们直接求解答案的每一个二进制位，可以从低位向高位处理每个位。对于答案的第 \(k\) 个二进制位，考虑其为 \(1\) 的条件：\(\forall a_i+a_j(1\leq i<j\leq n)\)，统计其和的第 \(k\) 位为 \(1\) 的个数 \(num\)，只有 \(num\) 位奇数时，这一位才可能位 \(1\)，只与比其小的位有关。

从此我们得到了这个重要的性质，那我们就要考虑怎样统计 \(num\)。

对于第 \(k\) 位（最低位为第 \(0\) 位），我们只考虑一个数 \(b\) 的前 \(k\) 低位，这个操作可以简单地通过 \(b\&(2^{k+1}-1)\) 得到，得到的数的取值范围为 \([0,2^{k+1}-1]\)。

这一位为 \(1\) 有如下两种可能：

  • 没有进位，那么和在 \([2^{k},2^{k+1}-1]\) 的范围内；
  • 若有进位，那么和在 \([2^{k+1}+2^k,(2^{k+1}-1)\times 2]\)，等价于 \([2^i\times 3,2^{k+2}-2]\)。

这样我们得到了两个连续的区间。我们只需要找和在这两个区间范围内的 \(a_i+a_j\) 即可（这里的 \(a_i,a_j\) 只保留前 \(k\) 小位）。

我们可以通过双指针求出这个个数。具体地，令 \(b_i=a_i\&(2^{k+1}-1)\)。因为顺序不影响结果，不妨先对 \(b\) 升序排序。那么对于每一个 \(b_i\)，每个满足 \(b_i+b_j\) 在合法范围内的 \(j\) 是连续的，而且具有单调性。我们从大到小枚举 \(i\) 的时候（因为排过序，所以 \(b_i\) 也是从大到小的），合法的 \(j\) 的区间是单调不降的。这样可以 \(O(n)\) 的时间内求出低 \(k\) 位为 \(1\) 的加和的个数 \(num\)，进而判断答案的第 \(k\) 位是否为 \(1\)。

因为需要枚举每个二进制位 \(k\)，所以算法的总时间复杂度为 \(O(n\log N)\)，其中 \(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
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 400005
int n,a[MAXN],b[MAXN];
bool count(int x,int y){
	if(x>y) return 0;
	int cnt=0;
	for(int l=1,r=1,i=n;i;i--){
		while(l<=n&&b[i]+b[l]<x) l++;
		while(r<=n&&b[i]+b[r]<=y) r++;
		cnt+=r-l;
		if(i>=l&&i<r) cnt--;
	}
	return (cnt>>1)&1;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	for(int p=0;p<=24;p++){
		for(int i=1;i<=n;i++){
			b[i]=a[i]&((1<<(p+1))-1);
		}
		sort(b+1,b+1+n);
		bool k1=count(1<<p,(1<<(p+1))-1);
		bool k2=count(3<<p,(1<<(p+2))-2);
		ans|=((1&(k1^k2))<<p);
	}
	cout<<ans;
	return 0;
}

Problem.6 签到题

题目标签：图论、异或操作

题目来源：校内联考 [SO Round 1] T2

题目大意

给你一张 \(n\) 个点，\(m\) 条边的无向图，边有边权 \(w\)，定义一条路径的价值为它所经过的边的边权的异或和。

求从节点 \(1\) 到节点 \(n\) 的价值最大的路径的价值。

数据范围

\(1 \le n,m \le 3 \times 10^5,0 \le w \le 2^{30}\)。

解题思路

很巧妙的想法。

我们可能走很长的路径，每个路径的转移不符合三角形不等式，所以不能用求解最短路的方法求解。换个思路，因为是异或和，我们无需考虑具体怎样走的，只用考虑要走哪个边：考虑如果图上有一个环，我们可以任意地走这个简单环。如果我们从一个节点进，又从环的这个节点出去，这样只对对答案有影响。

那我们就可以找到图上的每个简单环，最后找到从 \(1\) 到 \(n\) 的路径即可。

或许我们实现的可以更加简单一些：我们构造出一个 \(\text{dfs}\) 生成树，对于不在树上的边，只可能是返祖边，从而构成一个环。我们记 \(dis_i\) 为从 \(1\) 到 \(i\) 在生成树上面的路径价值。我们把这样每一个环放到线性基里面，最后只需要在线性基里面求出关于 \(dis_n\) 的最大异或和即可。（这意味着我们在一条从 \(1\) 走到 \(n\) 的路径上随意地走简单环）

时间复杂度为 \(O(n\log w)\)。

参考代码

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
#include<iostream>
#include<vector>
using namespace std;
#define MAXN 300005
typedef pair<int,int> pii;
int n,m,dis[MAXN],t[50];
vector<pii> g[MAXN];
bool vis[MAXN];
void insert(int x){
    for(int i=30;i>=0;i--){
        if((x>>i)&1){
            if(t[i]) x^=t[i];
            else{
                t[i]=x;
                return;
            }
        }
    }
}
void dfs(int u,int fa){
    vis[u]=1;
    for(auto nd:g[u]){
        int v=nd.first,c=nd.second;
        if(v==fa) continue;
        if(vis[v]){
            insert(dis[u]^dis[v]^c);
        }
        else{
            dis[v]=dis[u]^c;
            dfs(v,u);
        }
    }
}
int query(int x){
    for(int i=30;i>=0;i--){
        if(!((x>>i)&1)) x^=t[i];
    }
    return x;
}
int main(){
    cin>>n>>m;
    for(int x,y,c,i=1;i<=m;i++){
        cin>>x>>y>>c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
    dfs(1,0);
    cout<<query(dis[n]);
    return 0;
}

Problem.7 树

题目标签：思维，树论

题目来源：清华集训 2012-2013 day 4

题目大意

有一颗 \(n\) 个节点的二叉树，编号1至n。你将这些节点依次删除，并规定你只能删除没有父亲的节点（即删除一个节点前，必须将其祖先全部删除）。这棵树可能有三种形态：

  1. 一个链，准确地说，每个点最多只有一个儿子；
  2. 满二叉树；
  3. 普通的二叉树。

你并不知道这棵树的形态，只能通过以下方式询问：

  • size()：返回这棵树的节点数量 \(n\)；　
  • type()：返回这棵树的类型；
  • question(p,q) ：返回 \(p\) 号点和 \(q\) 号点的关系。若返回值为 \(1\)，表示 \(p\) 是 \(q\) 的祖先，若返回值为 \(-1\)，表示 \(q\) 是 \(p\) 的祖先，否则返回值为 \(0\)。你用这个询问的次数将关系到你的分数；
  • void submit(x)：完成回答，表示删除 \(x\) 号节点。

你需要做的，就是通过尽可能少的 question 询问将所有点全部删除。你的答案得到满分，调用 question 函数从次数必须为 \(O(n\log n)\) 级别。

数据范围

\(1 \le n \le 300000\)。

解题思路

对于部分分，我们有 \(O(n^2)\) 的暴力算法，下面直接讲能得到满分的正解。

考虑选择一个点，则我们删除这个节点与根之间最短路径的每一个节点才能删除这一个节点。

那我们就若干次随机化，每次随机选择一个节点，目的是删除这个节点到根的所有节点（构成一条链）后删除这个节点。我们每一次对于这个节点向全局进行 question 询问，了解哪些节点是它的祖先，单次复杂度 \(O(n)\)。我们依次删除祖先节点。因为我们删除这条链之后，会分割成若干棵子树，我们有需要在这些子树中分别进行删点操作。因为我们使用随机化算法，每次的链长期望为 \(O(\log n)\)。

我们需要记录这条链上所有的节点，从而继续进行操作。考虑到我们还需要对节点到根（或所在子树的顶）的这条链按照祖先顺序排序，我们需要使用归并排序算法。为什么不使用快速排序呢，考虑到归并排序的复杂度是严格 \(O(n\log n)\) 的，最坏复杂度比快速排序更加优一些（或许因为这道题卡常）。我们只需要使用 C++ 自带的 stable_sort 函数进行排序，并重定义 cmp 函数即可。

对于 type 为 \(1\) 的树，即一条链，我们只需要选择链底的节点，进行一次操作即可，详见参考代码。

时间复杂度 \(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
int size();
int type();
int question(int p, int q);
void submit(int x);

#include<iostream>
#include<chrono>
#include<random>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 300005
int dep[MAXN],n,a[MAXN];
bool ins[MAXN];
mt19937 rnd(time(0));
bool cmp(int x,int y){
    return question(x,y)==1;
}
void solve(vector<int> p){
    if(p.empty()) return;
    int n=p.size(),now=p[rnd()%n];
    vector<int> fa;
    fa.clear();
    for(auto v:p){
        if(v!=now&&question(v,now)==1) fa.push_back(v);
    }
    fa.push_back(now);
    stable_sort(fa.begin(),fa.end(),cmp);
    int m=fa.size();
    vector<vector<int> > son;
    son.resize(n);
    for(auto v:fa) ins[v]=1;
    for(auto v:p){
        if(ins[v]) continue;
        int l=0,r=m-1;
        while(l!=r){
            int mid=(l+r+1)>>1;
            if(question(fa[mid],v)) l=mid;
            else r=mid-1;
        }
        son[l].push_back(v);
    }
    for(int i=0;i<m;i++){
        submit(fa[i]);
        solve(son[i]);
    }
}
int main(){
    n=size();
    if(type()==1){
        for(int i=1;i<=n;i++) a[i]=i;
        stable_sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++) submit(a[i]);
    }
    else{
        vector<int> v;
        for(int i=1;i<=n;i++) v.push_back(i);
        solve(v);
    }
    return 0;   
}

Problem.8 Stack Exterminable Arrays

题目标签：思维，字符串，哈希

题目来源：CF1223F

题目大意

给一个长度为 \(n\) 的数列，对于其中一段子序列称为可被删除的，当且仅当按照下表顺序，按照如下要求进栈和出栈后栈为空：

  • 如果当前元素等于栈顶元素，则弹出栈顶元素；

  • 否则将当前元素压入栈中。

求有多少个子序列为可被删除的。

数据范围

\(1\le \sum n,\sum q\le 3\times 10^5\)。

解题思路

CSP-S 2023 T2 的原题，可惜考场并没有想出正确的思路。

理解题意后我们发现，我们可以枚举每一个可被删除的子序列（下面简称为“合法子序列”）的起始位置，进行栈模拟，就可以找到以这个位置开始的所有合法子序列。这是一个时间复杂度为 \(O(n^2)\) 的算法。

我们考虑进行简化。如果只从第一个位置进行栈模拟，发现所有合法的子序列都有如下性质：

  • 设 \(p_i\) 表示栈在第 \(i\) 个位置的状态，如果子序列 \(l\dots r\) 是合法的子序列，则有 \(p_{l-1}=p_r\)，即经过合法子序列后栈的状态和未经过时一样。

考虑怎么证明这个东西。

如果 \(l\dots r\) 内的数会和栈里面的数抵消。形式化地，记栈为 \(S=YX\)，当前合法的子序列形如 \(XYYX\)，两个 \(X\) 或抵消，同时子序列内部重复的 \(Y\) 也会抵消，最后剩下 \(X\)，入栈，这样栈内元素又一样了。

例子 \(\quad\) 对于序列 2 2 3 3 2，子序列取区间 \([2,5]\) 时，\(p_1=\{2\}\)，\(p_5=\{2\}\)，二者相等，说明子序列 2 3 3 2 是合法的子序列。

那么我们就可以只进行一个堆栈模拟，记录到每个位置的 \(p_i\)，可以对其进行字符串哈希，再用一个哈希表记录当前以前的所有栈状态，统计每个位置与其相等的栈状态即可。复杂度 \(O(n)\)。

对于 unordered_map 类型的变量，可以使用 <name>.reserve(_size) 进行预制大小。

参考代码

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<iostream>
#include<unordered_map>
using namespace std;
#define MAXN 300005
#define mod 5323
#define p 233
typedef long long ll;
typedef unsigned long long ull;
int Q,n,s[MAXN],top,a[MAXN],num[MAXN];
ull hs[MAXN],table[MAXN],lable[MAXN];
ll ans;
const int maxx=300000;
unordered_map<ull,int> mp;
int main(){
    cin>>Q;
    table[0]=lable[0]=1;
    for(int i=1;i<=maxx;i++) table[i]=table[i-1]*mod;
    for(int i=1;i<=maxx;i++) lable[i]=lable[i-1]*p;
    while(Q--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        top=ans=0;
        mp.clear();
        mp.reserve(n+5);
        mp[0]++;
        for(int i=1;i<=n;i++){
            if(a[i]==a[s[top]]){
                hs[i]=hs[i-1]-table[top]*lable[a[i]];
                top--;
            }
            else{
                s[++top]=i;
                hs[i]=hs[i-1]+table[top]*lable[a[i]];
            }
            if(mp.find(hs[i])!=mp.end()) ans+=mp[hs[i]];
            mp[hs[i]]++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Problem.9 Cow Tennis Tournament

题目标签：组合计数、思维、线段树

题目来源：CF283E

题目大意

有 \(n\) 个点，每个点有一个点权 \(s_i\)，一开始，每个点向比其点权小的点连边。接下来 \(k\) 个操作，每个操作给定 \(l,r\)，将 \(s_x,s_y\in [l,r]\) 的点对 \((x,y)\) 的边翻转方向。

问最后有多少对三元组 \((x,y,z)\) 满足 \(x\rightarrow y,y\rightarrow z,z\rightarrow x\)​。（箭头表示连边方向）两个三元组不同当且仅当有一个点在其中一个三元组中而不在另一个三元组中。

数据范围

\(3\le n\le 10^5,0\le k\le 10^5,1\le s_i\le 10^9,1 \le a_i < b_i \le 10^9\)。

解题思路

考虑到正面思考好像很难，正难则反，考虑有多少组三元组不符合这个条件。

不难发现，对于不满足条件的三元组 \((x,y,z)\)，其中肯定有一个点的出度（在这三个点构成的图中）为 \(2\)。我们就考虑能否求出每个点在最后有多少个出度，进而求出答案。

因为一段区间翻转，只会对这个区间内的点对 \((x,y)\) 产生变化，不妨按照扫描线的思路，按照点权大小排序后，对离散化的点权建立线段树，表示每个点是否对当前点 \(x\) 的连边有翻转（即区间翻转操作是奇数次还是偶数次）。我们把每个操作拆分为两个：

  • 左端标记在区间 \([l,r]\) 翻转；
  • 右端标记在区间 \([l,r]\) 撤销翻转，即再进行一次翻转即可。

我们按照离散化的点集，按照权值从小到大扫描。再每一个点记录当前点的出度：

  • 对于比当前点 \(x\) 点权小的点 \(y\)，当前点连向这个点，当且仅当区间 \([y,x)\) 的翻转次数为偶数次；
  • 对于比当前点 \(x\) 点权大的点 \(y\)，当前点连向这个点，当且仅当区间 \((x,y]\) 的翻转次数为奇数次。

这样，我们进行区间修改，区间查询，就可以在 \(O(\log n)\) 的时间内求出一个点的出度。根据组合公式，可以得到不合法的种类数为 \(C_{num}^2\)，其中 \(num\) 为出度。

所以最后答案就是

\[ C_n^3-\sum\limits_{i=1}^nC_{num_i}^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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100005
#define mid ((tree[p].l+tree[p].r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
typedef long long ll;
int n,k,s[MAXN];
ll ans;
vector<int> add[MAXN],del[MAXN];
struct node{
    int l,r,sum[2];
    bool tag;
}tree[MAXN<<2];
void update(int p){
    tree[p].sum[0]=tree[ls].sum[0]+tree[rs].sum[0];
    tree[p].sum[1]=tree[ls].sum[1]+tree[rs].sum[1];
}
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].sum[0]=1;
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    update(p);
}
void pushdown(int p){
    if(!tree[p].tag) return;
    swap(tree[ls].sum[0],tree[ls].sum[1]);
    swap(tree[rs].sum[0],tree[rs].sum[1]);
    tree[ls].tag^=1;
    tree[rs].tag^=1;
    tree[p].tag=0;
}
void modify(int l,int r,int p){
    if(l<=tree[p].l&&r>=tree[p].r){
        swap(tree[p].sum[0],tree[p].sum[1]);
        tree[p].tag^=1;
        return;
    }
    pushdown(p);
    if(l<=mid) modify(l,r,ls);
    if(r>mid) modify(l,r,rs);
    update(p);
}
int query(int l,int r,int op,int p){
    if(l>r) return 0;
    if(l<=tree[p].l&&r>=tree[p].r) return tree[p].sum[op];
    pushdown(p);
    int sum=0;
    if(l<=mid) sum+=query(l,r,op,ls);
    if(r>mid) sum+=query(l,r,op,rs);
    return sum;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+1+n);//按照点权排序
    for(int x,y,i=1;i<=k;i++){
        cin>>x>>y;
        x=lower_bound(s+1,s+1+n,x)-s;//求出离散化后的操作范围
        y=upper_bound(s+1,s+1+n,y)-s-1;
        if(y<x) y=x;
        add[x].push_back(y);//建立类扫描线
        del[y].push_back(x);
    }
    build(1,n,1);
    for(int i=1;i<=n;i++){
        for(auto v:add[i]) modify(i,v,1);
        int cnt1=query(1,i-1,0,1);//比当前点点权小的点所带来的出度
        int cnt2=query(i+1,n,1,1);//比当前点点权大的点所带来的出度
        if(cnt1+cnt2>=2) ans+=1ll*(cnt1+cnt2)*(cnt1+cnt2-1)/2;//组合答案
        for(auto v:del[i]) modify(v,i,1);
    }
    ans=1ll*n*(n-1)*(n-2)/6-ans;
    cout<<ans;
    return 0;
}

Problem.10 作业 Homework

题目标签：根号分治

题目来源：2006上海省选 (SHOI2006)

题目大意

给定一个集合为 \(S\)，初始为空，你需要执行以下两个操作共 \(N\) 次。

  1. 在集合 \(S\) 中加入一个新元素，其代号为 \(X\)，保证 \(X\) 在当前集合中不存在。
  2. 在当前的集合 \(S\) 中询问所有元素 \(\bmod\ Y\) 最小的值。

数据范围

\(1\le N\le 10^5,1\le X,Y\le 3\times 10^5\)。

解题思路

看到维护操作中有取模操作，且难以维护区间信息，考虑根号分治。

记 \(T=\sqrt{3\times 10^5}\)。具体地，将询问的 \(Y\) 划分为两个种类：

  • 若 \(Y\le T\)，则这样的模数最多有 \(T\) 种，对每一种值在添加数据时暴力维护（添加并取最小值）；
  • 若 \(Y>T\)，考虑到商数最多有 \(T\) 种，即对于 \(Y/x=p\dots\dots q\) 的 \(p\) 最多有 \(T\) 种。变化式子为 \(x-pY=q\)，枚举每一个 \(p\)，则可以算出该商数情况下的最小 \(q\) 值。具体地，利用 set 维护 \(S\) 中的数，对于每一个模数 \(p\)，找到第一个大于等于 \(pY\)，减一下即可得到该模数下的最小 \(q\) 值。

令 \(\omega\) 为值域，则插入一次复杂度 \(O(\sqrt{\omega})\)，查询一次复杂度为 \(O(1)\) 或 \(O(\sqrt{\omega} \log n)\)，总复杂度 \(O(n\sqrt{\omega}\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
#include<iostream>
#include<cstring>
#include<set>
using namespace std;
#define MAXSQRTN 555
int lim=550,n,p[MAXSQRTN];
set<int> s;
void add(int x){
    for(int i=1;i<=lim;i++) p[i]=min(p[i],x%i);
    s.insert(x);
}
int query(int x){
    if(x<=lim) return p[x];
    int ans=0x3f3f3f3f;
    for(int k=0;1ll*k*x<=300000;k++){
        auto t=s.lower_bound(k*x);
        if(t==s.end()) break;
        ans=min(ans,*t-k*x);
    }
    return ans;
}
int main(){
    cin>>n;
    memset(p,0x3f,sizeof(p));
    for(int i=1;i<=n;i++){
        char ch;int x;
        cin>>ch>>x;
        if(ch=='A') add(x);
        else cout<<query(x)<<endl;
    }
    return 0;
}