Post 79

Veröffentlicht am | Edited on

[POI2010]PIL-Pilots

题目描述

给定n,k和一个长度为n的序列，求最长的最大值最小值相差不超过k的区间

输入输出格式

输入格式：

第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表设定的最大值，n代表序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示序列。

输出格式：

Your program should print a single integer to the standard output:

the maximum length of a fragment of the flight that is within the given tolerance level.

一个整数代表最大的符合条件的序列

输入输出样例

输入样例#1：

1
2
3 9
5 1 3 5 8 6 6 9 10

输出样例#1：

1
4

说明

样例解释：5, 8, 6, 6 和8, 6, 6, 9都是满足条件长度为4的序列

题解

白浪费我20分钟。

区间翻译成序列，这水平翻译什么呢？

维护两个单调队列，由于区间越长最小值越小，最大值亦然，有一种单调关系，因此当不满足条件的时候把当前区间的左端不断弹出直到满足条件，由于任意时刻单调队列的区间都是合法的，不断更新答案即可。

时间复杂度$O(n)$

[POI2014]KAR-Cards

题目描述

There are nn cards arranged on a table in a certain order.

Two integers are written on each card, one per side: the obverse and the reverse.

Initially all cards lie with the averse facing up.

Byteasar, The Great Illusionist, intends to perform (multiple times!) his signature Binary Search Card Manipulation. However, to present it, he needs the sequence of numbers as seen on the cards to be non-decreasing.

Thus, Byteasar may have to turn over some cards so that the numbers on their reverse sides become visible.

Furthermore, the illusion requires a participant from the audience.

Alas, some of the volunteers are deployed by Byteasar’s competitors who want him to fail.

Each such supposititious volunteer, upon entering the scene, would swap two cards on the table in a lightning move of a hand. After each such swap, Byteasar can again turn over any cards he desires but nevertheless, he may not be able to perform his great illusion.

If that were to happen, he would be forced to turn to traditional illusions, such as pulling a rabbit out of a hat.

Write a program that determines, after each card swap, if Byteasar can perform his great illusion.

有一些卡牌，正反各有一个数，你可以任意翻转，每次操作会将两张卡牌的位置调换，你需要在每次操作后回答以现在的卡牌顺序能否通过反转形成一个单调不降的序列

输入输出格式

输入格式：

In the first line of the standard input, there is a single integer, nn (2\le n\le 200\ 0002≤n≤200 000), the number of the cards.

The nn lines that follow describe the cards, one per line,in the order they are arranged on the table.

The ii-th of these lines has two integers x_ix**i and y_iy**i (0\le x_i,y_i\le 10^70≤x**i,y**i≤107), separated by a single space.

These are the numbers written on the ii-th card:

x_ix**i is the one written on the obverse and y_iy**i the one on the reverse.

The initial sequence of cards may not allow performing the great illusion.

Afterwards, there is a line with a single integer mm (1\le m\le 1\ 000\ 0001≤m≤1 000 000), the number of card swaps.The mm lines that follow describe the swaps: jj-th of these lines has two integers $a_j$and $b_j$ ($1\le a_j,b_j\le n​$), separated by a single space, indicating that the jj-th (supposititious) volunteer will swap the a_jaj-th and the b_jbj*-th cards.

输出格式：

Your program should print mm lines to the standard output, each containing a single word:

TAK (Polish for yes) or NIE (Polish for no).

The jj-th line should read TAK if Byteasar can obtain a non-decreasing sequence of numbers by turning the cards over after the jj-th card swap. If he cannot, the line should read NIE.

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
NIE
TAK

说明

有一些卡牌，正反各有一个数，你可以任意翻转，每次操作会将两张卡牌的位置调换，你需要在每次操作后回答以现在的卡牌顺序能否通过反转形成一个单调不降的序列

题解

这道题想了半天还真猜到了做法？？

首先想一想静态情况。

我们尽量让不降前缀最后一个数尽可能的小。然后$O(n)$就做完了。

然后考虑如果只改变一对数该怎么办？

我们发现当序列第一个数决定选$a$还是选$b$的时候，这个序列的贪心结果就已经确定了。

所以我们可以用一个线段树。这个线段树合并确实是可以做到常数复杂度的（我想了半天）。

真的菜

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
inline void pushup(int l, int r, int o) {
    int ls = o << 1;
    int rs = ls | 1;
    int mid = (l + r) >> 1;
    // high_small[o] 
    if(high_s[ls] == -1) {
        high_s[o] = -1;
    }
    else {
        if(a[mid + 1] >= high_s[ls]) {
            high_s[o] = high_s[rs];
        }
        else if(b[mid + 1] >= high_s[ls]) {
            high_s[o] = high_l[rs];
        }
        else {
            high_s[o] = -1;
        }
    }
    // high_large[o]
    if(high_l[ls] == -1) {
        high_l[o] = -1;
    }
    else {
        if(a[mid + 1] >= high_l[ls]) {
            high_l[o] = high_s[rs];
        }
        else if(b[mid + 1] >= high_l[ls]) {
            high_l[o] = high_l[rs];
        }
        else {
            high_l[o] = -1;
        }
    }

    return;
}

突然想到我还不会Manacher

manacher算法

题目描述

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入输出格式

输入格式：

一行小写英文字符a,b,c…y,z组成的字符串S

输出格式：

一个整数表示答案

输入输出样例

输入样例#1：

1
aaa

输出样例#1：

1
3

说明

字符串长度$len <= 11000000$

题解

我们需要一种线性求解回文串的办法。

不过说之前要说明：Hash+二分可以$O(nlogn)$解决这个问题。

Step 1

考虑一个回文串S’, 它可能具有奇数长度或偶数长度. Manacher算法需要回文串具有奇数长度. 所以我们可以用’#’将读入串S的每个字符分隔:
abbabcacba —-> ##a#b#b#a#b#c#a#c#b#a#
这样就保证了我们需要的字串长度都是奇数.
回文串的中间字符记作中心, 其 ceil( S.length / 2 ) 的值记作回文半径.

1
2
3
4
5
6
7
8
9
scanf("%s", t);
   m = strlen(t);

   a[0] = a[1] = '#';
   for (int i = 1; i <= m; i++) {
       a[ ( i << 1 ) ] = t[i - 1];
       a[ ( i << 1 ) + 1 ] = '#';
   }
   n = ( m << 1 ) + 2;

step 2

接下来我们考虑回文串S’, 令其中心为 mid, 回文半径为 r0.

由回文串的对称性, 显然有:
$S’[mid + x] = S’[mid - x] (0 ≤ x < r0)$.

那么我们再设 $r[x]$ 为$S$中以$x$为中心的最长回文子串的回文半径, 则有:
$r[mid + x] >= r[mid - x] (0 ≤ x < r0).$（原文是等于，似有误）

step3

考虑从左向右遍历$i​$,递推出$r[i]​$.
记录当前已求得的回文子串右端最远延伸到的位置$maxright​$($maxright​$的左侧即为我们的已知区域),和该回文子串的回文中心$mid​$.

对于每个$i$:

1.先判断$i​$是否在$maxright​$的范围内,若在则进行’2.’,若$i​$已超出$maxright​$,则进行’3.’.

2.$i​$在$maxright​$范围内,$r[(mid<<1)-i]​$即为$i​$关于当前$mid​$的对称点处的最长回文子串回文半径长度,$r[i]​$就可以以$r[(mid<<1)-i]​$为基数开始扩展.
但此时,若$r[(mid<<1)-i]​$超过了$r[mid]+mid-i​$(即$i​$到$maxright​$的距离),就只能将$r[i]​$赋值为$r[mid]+mid-i​$,因为以$i​$为中心,$r[(mid<<1)-i]​$为回文半径的子串右端此时已超过$maxright​$,即已超过已知范围,而不能确定$r[i]​$实际上能否达到该长度.
故$r[i]=min(r[(mid<<1)-i],r[mid]+mid-i);​$
并进行’4.’.

3.$i​$超出$maxright​$,不能利用对称性,故$r[i]=1​$,进行’4.’.

4.以当前$i$和$r[i]$开始暴力向外拓展至求得$r[i]$最终结果.并将其右端与$maxright$比较,更新$maxright​$.

至此算法完成,答案即为最大的$r[i]-1​$.

都是什么鬼，就这样吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void manacher()
{
    int maxright=0,mid;
    for(int i=1;i<n;i++)
    {
        if(i<maxright)
            hw[i]=min(hw[(mid<<1)-i],hw[mid]+mid-i);
        else
            hw[i]=1;
        for(;s[i+hw[i]]==s[i-hw[i]];++hw[i]);
        if(hw[i]+i>maxright)
        {
            maxright=hw[i]+i;
            mid=i;
        }
    }
}

抄的

以后还是用Hash吧

晚上是多项式的。（不会Taylor展开）

来写一下容斥的推导。

$|U{i=1}^{n}S_i| = \sum\limits{i=1}^{n}|Si| - \sum\limits{i,j}^{n}|S_i \cap S_j| + …. + (-1)^{n+1}|S_1 \cap S_2…\cap S_n|​$

我们可以证明这样计算对于任意一个元素$a$满足$a$被$k$个集合包含，上面对它计算的贡献总是1.

那么它被选择的次数就是

$\sum\limits_{i=0}^{k}(-1)^i\binom{k}{i} = 1$

证明完了。用于已知相交求并的题目，或者说可以去掉一些限制，方便计算。

然后是可重集的组合数问题

假如有一个集合$S = \{a1…(n1个) , a2(n2个)….\}$

问你不同的可重子集有多少个？