Post 72

Veröffentlicht am | Edited on

又度过了精力不足的美好一天

在开始一个比较难的问题之前，我们先看一个前置问题。

最长上升子序列的数量

数组A包含N个整数（可能包含相同的值）。设S为A的子序列且S中的元素是递增的，则S为A的递增子序列。如果S的长度是所有递增子序列中最长的，则称S为A的最长递增子序列（LIS）。A的LIS可能有很多个。例如A为：{1 3 2 0 4}，1 3 4，1 2 4均为A的LIS。给出数组A，求A的LIS有多少个。由于数量很大，输出Mod 1000000007的结果即可。相同的数字在不同的位置，算作不同的，例如 {1 1 2} 答案为2。

输入

1
2
第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数A[i]，表示数组的元素(0 <= A[i] <= 10^9)

输出

1
输出最长递增子序列的数量Mod 1000000007。

输入样例

1
2
3
4
5
6
5
1
3
2
0
4

输出样例

1
2

题解

我还卡了一会。。。

LIS是一个二维偏序问题：

  1. $j < i$
  2. $a_j<a_i$
  3. $lis_j+1 = lis_i$

LIS的值表示的是如果用$O(nlogn)$dp得到的以每个数结尾最长上升子序列长度。

对于$lis$值相同的我们用$vector$存起来，$lis$相同的情况下后面的数比前面小，否则就构成了更长的$LIS$.

设$f_i$表示以$i$结尾的最长上升子序列长度。

我们需要找到所有满足条件2,3的$j$.

$lis$已经可以确定，问题转化为从一个$vector$中找到相应的满足$a_j<a_i$，二分即可。

这个算法注意一点就是两个过程好像必须同时做，因为如果你不同时做那vector可能得多记录一个下标再dp数量。

时间复杂度$O(nlogn)$

（时间紧迫转的胡小兔的code，其实也是从他那学的qwq）

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 0x3f3f3f3f
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
bool read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
    if(c == '-') op = 1;
    else if(c == EOF) return 0;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
    x = x * 10 + c - '0';
    if(op) x = -x;
    return 1;
}
template <class T>
void write(T x){
    if(x < 0) putchar('-'), x = -x;
    if(x >= 10) write(x / 10);
    putchar('0' + x % 10);
}

const int N = 50005, P = 1e9+7;
int n, m, a[N], s[N], cnt;
ll dp[N];
vector <ll> lst[N], sum[N];
//lst[i]存储所有以它结尾LIS长度为i的位置上的数值，
//sum存储对应lst数组中dp值的前缀和。
int find(int p, ll x){
//这个函数通过在lst[p]中找到最后一个>=x的数，
//从而得到所有“比x小且以它结尾的LIS长度为以x结尾的LIS长度-1”的数的dp值之和。
    int l = 0, r = lst[p].end() - lst[p].begin() - 1, mid;
    while(l < r){
    mid = (l + r + 1) >> 1;
    if(lst[p][mid] < x) r = mid - 1;
    else l = mid;
    }
    return ((sum[p].back() - sum[p][l]) % P + P) % P;
}
int main(){
    read(n);
    for(int i = 1; i <= n; i++)
    read(a[i]);
    for(int i = 0; i <= n; i++)
    lst[i].push_back(INF), sum[i].push_back(0);
    lst[0].push_back(-INF), sum[0].push_back(1);
    for(int i = 1; i <= n; i++){
    int lis; //以位置i结尾的LIS长度
    if(!cnt || a[i] > s[cnt]) s[++cnt] = a[i], lis = cnt;
    else {
        int pos = lower_bound(s + 1, s + cnt + 1, a[i]) - s;
        s[pos] = a[i];
        lis = pos;
    }
    lst[lis].push_back(a[i]);
    sum[lis].push_back((sum[lis].back() + find(lis - 1, a[i])) % P);
    }
    write(sum[cnt].back()), enter;
    return 0;
}

[USACO18DEC]Sort It Out

题目描述

FJ有 $N$ （ $1 \leq N \leq 10^5$ ）头奶牛（分别用 $1 \ldots N$ 编号）排成一行。FJ喜欢他的奶牛以升序排列，不幸的是现在她们的顺序被打乱了。在过去FJ曾经使用一些诸如“冒泡排序”的开创性的算法来使他的奶牛排好序，但今天他想偷个懒。取而代之，他会每次对着一头奶牛叫道“按顺序排好”。当一头奶牛被叫到的时候，她会确保自己在队伍中的顺序是正确的（从她的角度看来）。当有一头紧接在她右边的奶牛的编号比她小，她们就交换位置。然后，当有一头紧接在她左边的奶牛的编号比她大，她们就交换位置。这样这头奶牛就完成了“按顺序排好”，在这头奶牛看来左边的奶牛编号比她小，右边的奶牛编号比她大。

FJ想要选出这些奶牛的一个子集，然后遍历这个子集，依次对着每一头奶牛发号施令（按编号递增的顺序），重复这样直到所有N头奶牛排好顺序。例如，如果她选出了编号为 \{2,4,5\}{2,4,5} 的奶牛的子集，那么他会喊叫奶牛2，然后是奶牛4，然后是奶牛5。如果 NN 头奶牛此时仍未排好顺序他会再次对着这几头奶牛喊叫，如果有必要的话继续重复。

由于FJ不确定哪些奶牛比较专心，他想要使得这个子集最小。此外，他认为 KK 是个幸运数字。请帮他求出满足重复喊叫可以使得所有奶牛排好顺序的最小子集之中字典序第 KK 小的子集。

我们称 $\{1, \ldots ,N\}$的一个子集 $S$ 在字典序下小于子集 $T$ ，当 $S$的所有元素组成的序列（按升序排列）在字典序下小于 $T$的所有元素组成的序列（按升序排列）。例如， $\{1,3,6\}$ 在字典序下小于$ \{1,4,5\}$ 。

输入输出格式

输入格式：

输入的第一行包含一个整数 $N$。第二行包含一个整数 $K$ （ $1 \leq K \leq 10^{18}$）。第三行包含 $N$ 个空格分隔的整数，表示从左到右奶牛的编号。

保证存在至少$K$ 个符合要求的子集。

输出格式：

第一行输出最小子集的大小。接下来输出字典序第 $K$ 小的最小子集中奶牛的编号，每行一个数，升序排列。

输入输出样例

输入样例#1：

1
2
4 1
4 2 1 3

输出样例#1：

1
2
3
2
1
4

说明

开始的时候序列为 $\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}$ 。在FJ喊叫编号为 $1$的奶牛之后，序列变为 $\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}$。在FJ喊叫编号为 $4$ 的奶牛之后，序列变为$ \mathtt{\:1\:\; 2\:\; 3\:\; 4\:}$ 。在这个时候，序列已经完成了排序。

子任务

对于占总分 $3/16$ 的测试数据， $N \leq 6$，并且 $K=1$ 。对于另外的占总分 $5/16$的测试数据，$ K=1$ 。对于另外的占总分$ 8/16$的测试数据，没有其他限制。

题解

我们选出这个子集后，把它去掉，剩下的必须是一个上升的子序列。

输出大小就是$n-Lis$，这个谁都会$O(nlogn)$的dp吧。字典序最小的方案等价于让LIS选中的方案中第一个数尽可能的大，然后第二个……

所以本题就是让你求出字典序第$K$大的LIS。

然后我们倒着做最长下降子序列并用类似的方法来统计数量，这意味着我们求出了每个位置开头的最长上升子序列数量。

注意到给定的是排列，没有重复元素

然后又是求$k$大值的套路，我们已经把$LIS$的每个可能的转移位置以二元组$(a[i],i)$的形式都保存在了$vector$里，前面证明过第一维权值一定单调递减，所以我们按照权值从小到大枚举每个元素，看看那个元素开头的方案数是否大于$k$，大于就确定是这个数，同时要求的长度lis-1，去枚举lis的vector里的元素进而确定下一个。否则就用$k$减掉然后枚举下一个权值.注意选定后后面选的必须在右边，不满足条件的需要过滤掉。
典型的分治。

说的很对，有空就写（并不

[BJWC2010]外星联络

题目描述

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。

虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于 11 的子串。

但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

输入输出格式

输入格式：

输入文件的第一行是一个整数$N$ ，代表小 P 接收到的信号串的长度。
输入文件第二行包含一个长度为$N$的 01 串，代表小 P 接收到的信号串。

输出格式：

输出文件的每一行包含一个出现次数大于11 的子串所出现的次数。输出的顺序按对应的子串的字典序排列。

输入输出样例

输入样例#1：

1
2
7
1010101

输出样例#1：

1
2
3
4
5
6
7
8
9
3
3
2
2
4
3
3
2
2

说明

对于 $100\%$的数据，满足 $0 \le N \le 3000$

题解

SA做法没想，秒想SAM做法。
$O(n)$处理每个状态$|ENDPOS|$，然后为了字典序DAWG上贪心走就可以了。
复杂度$O(n^2)$
其实Hash 好像也行。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 3005
int ch[2][maxn<<1] , ln[maxn<<1] , lk[maxn<<1] , tot = 1 , la = 1 , sum[maxn<<1] , n , c[maxn] , tp[maxn<<1];

inline void ins(int c)
{
	int cur = ++tot , p = la;
	ln[cur] = ln[la] + 1 , sum[cur] = 1;
	for( ; !ch[c][p] && p ; ch[c][p] = cur , p = lk[p]);
	if(!p) lk[cur] = 1;
	else
	{
		int q = ch[c][p];
		if(ln[p] + 1 == ln[q]) lk[cur] = q;
		else
		{
			int nq = ++tot;
			//set up new status
			ch[0][nq] = ch[0][q] , ch[1][nq] = ch[1][q] ;
		   	lk[nq] = lk[q] , lk[q] = lk[cur] = nq;
			ln[nq] = ln[p] + 1;
			//modify DAWG
			for( ; p && ch[c][p] == q ; ch[c][p] = nq , p = lk[p]);
		}
	}
	la = cur;

}

inline void sort()
{
	for(int i = 1 ; i <= tot ; ++i) ++c[ln[i]];
	for(int i = 1 ; i <= n ; ++i) c[i] += c[i-1];
	for(int i = 1 ; i <= tot ; ++i) tp[c[ln[i]]--] = i;
}

void dfs(int x)
{
	if(sum[x] > 1 && x > 1) printf("%d\n",sum[x]);
	if(ch[0][x]) dfs(ch[0][x]);
	if(ch[1][x]) dfs(ch[1][x]);
}

inline void dp()
{
	sort();
	for(int i = tot ; i >= 1 ; --i)
		sum[lk[tp[i]]] += sum[tp[i]];
	dfs(1);
}

int main()
{
	scanf("%d\n",&n);
	char ch;
	for(int i = 1 ; i <= n ; ++i) ch = getchar() , ins(ch - 48);
	dp();
}

[USACO17FEB]Why Did the Cow Cross the Road I S

题目描述

Farmer John’s cows are trying to learn to cross the road effectively. Remembering the old “why did the chicken cross the road?” joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them.

农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路？”，他们想到鸡一定是过马路的专家，便动身寻找能够帮助它们的鸡。

As it turns out, chickens are very busy creatures and have limited time to help the cows. There are $C$chickens on the farm ($1 \leq C \leq 20,000$), conveniently numbered 1 \ldots C1…C, and each chicken ii is only willing to help a cow at precisely time $T_i$. The cows, never in a hurry, have more flexibility in their schedules. There are NN cows on the farm ($1 \leq N \leq 20,000$), conveniently numbered 1 \ldots N1…N, where cow$j$is able to cross the road between time A_jA**j and time $B_j$. Figuring the “buddy system” is the best way to proceed, each cow jj would ideally like to find a chicken $i$ to help her cross the road; in order for their schedules to be compatible, ii and jj must satisfy $A_j \leq T_i \leq B_j$.

牛们发现，鸡是一种特别繁忙的动物，并且只有一定的时间来帮助它们。农场上共有CC 只鸡（$1\le C\le 20000$），十分便利地被编号为1…C1…C, 而且，每只鸡$i$ 只有恰好在时间$T{i}$ 时才会愿意帮助牛们。而从不慌张的牛们，有更加灵活的时间安排。农场上共有 $N$ 只牛（$1\le N\le 20000$），也十分便利地被编号为1…N1…N，牛$j$ 在时间 $A{j} $ 到$B{j}$之间可以穿过马路。想到“小伙伴系统”是最好的行进方式，每只牛jj 会理想地愿意找到一只鸡ii 来帮助她穿过马路；为了是它们的时间表不冲突，$i$ 和$j$ 必须满足$A{j}\le T{i}\le B{j}$

If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed.

如果每头奶牛最多只能配一只鸡，而每只鸡最多只配上一头牛，请帮忙计算出可以构造的牛鸡对的最大数量。

输入输出格式

输入格式：

The first line of input contains $C$ and $N$ The next $C$ lines contain $T_1 \ldots T_C$, and the next $N$lines contain $A_j$and $B_j$($A_j \leq B_j$) for $j = 1 \ldots N$. The $A$’s, $B$’s, and $T$’s are all non-negative integers (not necessarily distinct) of size at most $1,000,000,000$

第一行的输入包括$C$ 和$N$。下面的$C$行包括$T1…TC$，再接下来的$N$行包括$A{j}$ 和$B{j}(A{j}\le B{j}$)，$j=1…N$。所有$A,B$ 与$T$都是非负整数（可能相等），并皆小于等于$1,000,000,000$

输出格式：

Please compute the maximum possible number of cow-chicken pairs.

请计算最大的可行牛-鸡配对数。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

输出样例#1：

1
3

题解

写了道贪心经典题（复杂度根本不对。。）。

把点按从小到大排序，区间按照右端点排序。

然后暴力匹配即可。

这样做的正确性：点是从小到大枚举的，如果当前不给右端点最小的区间给了一个更大的，下一个点能给的决策就变少了，然而对答案的贡献确实一样的。这就是决策包容性。

复杂度$O(nm)$

应该可以数据结构优化什么的。关键不在这就不说了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 50005
int p[maxn];
struct Node{
	int l , r;
	bool operator < (const Node& x)const{
		return r < x.r;
	}
}q[maxn];

int n , m , ans;
bool vis1[maxn] , vis2[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	for(int i = 1;  i <= m ; ++i)
		scanf("%d%d",&q[i].l,&q[i].r);
	std::sort(p+1,p+n+1) , std::sort(q+1,q+m+1);
	for(int i = 1 ; i <= m ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			if(p[j] >= q[i].l && p[j] <= q[i].r && !vis1[i] && !vis2[j]) vis1[i] = vis2[j] = true , ++ans;
	}
	printf("%d\n",ans);
}

突然发现我可以在中文下直接输出英文字符,这样就再也不用我写数学相关的东西用蹩脚的英文了哈哈哈.