头像

wxy_


访客:1380

离线:2小时前



wxy_
3天前

加法原理

完成一件事情有$n$类方法,每种方法的步骤分别为$a_1…a_n$

那么完成这件事情的方法总数为

$$
\sum_{i=1}^n
a_i
$$

乘法原理

如果完成一件事情有$n$个步骤,每个步骤有若干种方法分别$a_1…a_n$

那么完成这件事情的方法总数为$a_1\times a_2…\times a_n$

排列数

从$n$个不同元素中取出$m(m <=n)$个元素的所有排列的个数,叫做从$n$个不同元素中取出$m$个元素的排列数,⽤符号$A_n^m$表示
$$
A_n^m=n(n-1)(n-2)(n-3)(n-4)…(n-m+1)=\frac{n!}{(n-m)!}
$$

组合数

从$n$个不同元素中取出$m$个元素的所有组合的个数,叫做从$n$个不同元素中取出$m$个元素的组合数。⽤符号$C_n^m$或$\binom{n}{m}$来表示
$$
\binom{n}{m}=\frac{n!}{m!(n-m)!}
$$

组合恒等式

$$
\begin{aligned}
\binom{n}{m}&= \binom{n}{n-m} \
\binom{n}{m}&=\frac{n}{m}\binom{n-1}{m-1} \
m\binom{n}{m}&=n\binom{n-1}{m-1} \
(n-m)\binom{n}{i}&=n\binom{n-1}{m} \
\binom{n}{m}&=\binom{n-1}{m-1}+\binom{n-1}{m}
\end{aligned}
$$

组合数的求法(组合恒等递推$O(nm)$求组合数)

for(int i=0;i<=n;i++){   
    c[i][j]=1;   
    for(int j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1]; 
} 

二项式定理与二项式反演

$$
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}
$$

特殊恒等

$$
\begin{aligned}
a=1,b=1 \
\sum_{i=0}^n\binom{n}{i}=2^n
\end{aligned}
$$


$$
\begin{aligned}
a=1,b=-1 \
\sum_{i=0}^n\binom{n}{i}(-1)^i=0
\end{aligned}
$$

其中奇数项的和等于偶数项的和


二项式反演

而对于两个数列有

$$
f_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_i
$$

变形有

$$
f_n=\sum_{i=0}^{n}\binom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i
$$

容斥原理

$$
\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{T \subseteq{1,2,3, \ldots, n}}(-1)^{|T|-1}\left|\bigcap_{j \in T} S_{j}\right|
$$

即对于若干个集合的并集的元素个数,相当于$i(1<=i<=n)$个集合的交集的个数的乘上容斥系数(若交集个数为奇数则为-1,若交集个数为偶数则为+1)和

集合反演

对于函数$f(S),g(S)$有

$$
f(S)=\sum_{T \subseteq S} g(T) \Leftrightarrow g(S)=\sum_{T \subseteq S}(-1)^{|S|-|T|} f(T)
$$

证明

$$
\begin{aligned}
& \sum_{T \subseteq S}(-1)^{|S|-|T|} f(T) \
=& \sum_{T \subseteq S}(-1)^{|S|-|T|} \sum_{Q \in T} g(Q) \
=& \sum_{Q \subseteq S} g(Q) \sum_{Q \subseteq T \subseteq S}(-1)^{|S|-|T|} \
=& \sum_{Q \subseteq S} g(Q) \sum_{T \subseteq(S \backslash Q)}(-1)^{|S \backslash Q|-|T|} \
=& \sum_{Q \subseteq S} g(Q) h(S \backslash Q)
\end{aligned}
$$

其中

$$
\begin{aligned}
h(S) &=\sum_{T \subseteq S}(-1)^{|S|-|T|} \
&=\sum_{i=0}^{|S|}\left(\begin{array}{c}
|S| \
i
\end{array}\right)(-1)^{|S|-i} \
&=(1-1)^{|S|} \
&=[S=\varnothing]
\end{aligned}
$$

$$
\sum_{Q \subseteq S} g(Q)[(S \backslash Q)=\varnothing]=g(S)
$$

容斥原理与错排问题通项公式

$n$封信和信箱⼀⼀对应,求把每封信都装错信箱的⽅案数。

对于错排问题,我们有一个递推式,即$D[n]=(n-1)\times (D[n-1]+D[n-2])$

我们可以得知其中全部装错信箱的方案=总方案$-$没有把所有信都装错的方案

即总方案$-$不满足要求的方案

而显然,对于总方案即$n$的全排列,为$n!$

而什么样的方案是不满足的?

我们把我们的信编号为$1,2,3,4,5....n$

其对应的邮箱编号为$1,2,3,4,5....n$

如果存在一个$i$,其对应的邮箱编号是$i$,那么不管其他的信件对应的邮箱的编号是几,这种方案一定不合法。

我们设$A_i$为第$i$封信送进所对应的$i$号邮箱的方案集合。

我们有$1$个邮箱所放的信件是确定的,而其他$n-1$个邮箱放什么信我们都不关心

而对于除了第$i$个邮箱的其他邮箱,每一次分别可以从$(n-1),(n-2),(n-3)…1$封信中挑选一个进去,即有$n-1$步,第$k$步有$(n-k)$种选法,那么其选择的方案总和为$(n-1)!$

即对于任意一个$i$,都有$|A_i|=(n-1)!$

而我们把所有信都装错的方案数就等价于

$$
n!- \left|\bigcup_{i=1}^{n} A_{i}\right|
$$

那么我们只需要用容斥原理求出$A_i$的并集,即可容易地计算出答案

而要进行容斥,就需要知道
$$
\left|\bigcap_{j \in T \subseteq{1,2,3, \ldots, n}} A_{j}\right|
$$
考虑最简单的情况
$$
\left|A_i\bigcap A_j\right|
$$
$A_i$为第$i$个信箱装信$i$的方案
$A_j$为第$j$个信箱装信$j$的方案
因此$A_i \bigcap A_j$就等价于第$i$个信箱装信$i$且第$j$个信箱装信$j$的方案,其方案数为$(n-2)!$同理可推广到若干个集合的情况,即$k$个$A$集合的交的大小为$(n-k)!$

而我们要从$A_1,A_2,A_3,…,A_n$这些集合中,选若干个集合相交,选$k$个集合相交的个数为,则一共有$\binom{n}{k}$种选择方案。那么则有

$$
\begin{aligned}
\left|\bigcup_{i=1}^{n} A_{i}\right| = \sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)!
\end{aligned}
$$

那么

$$
\begin{aligned}
D[n]&=n!-\sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)! \
&=n!-\sum_{i=1}^n(-1)^{(i-1)}\frac{n!}{i!} \
\end{aligned}
$$

[HAOI2008]硬币购物

共有四种硬币,其面值分别为$c_1,c_2,c_3,c_4$

$n$次询问,每次给定每种硬币的个数$D_i$和付款金额$S$,问共有多少种付款方式

$n≤10^3,S≤10^5$

暴力做法

我们可以把问题看作做$n$次多重背包,用单调队列优化,最优的复杂度为$O(n4s)$在这里不详细讨论

完全背包+容斥

对于每次询问,相当于给定四个限制,第$i$个限制即只能至多使用$i$个硬币支付。类似于错排,满足限制的方案数=全部方案数-不满足的方案数

而对于全部的方案数,相当于做体积为$S$的完全背包,而$S$至多为$10^5$,因此我们可以$O(4S)$预处理所有$S$。

而对于不满足条件的方案数

类似于错排,若不满足其中一个限制条件,一定是非法的,我们可以设$A_i$为第$i$种硬币不满足限制的方案集合。

那么不满足条件的方案数即
$$
\left|\bigcup_{i=1}^4 A_i\right|
$$
而对于$|A_i|$,我们当前一共要支付$S$个硬币,而对于第$i$种只能支付$D_i$个,那么我们如果先把$D_i+1$个硬币付完剩下的支付方案(即从四种硬币中支付$S-C_i(D_i+1)$的金额)是一定不合法的,因为第$i$个硬币至少需要选零个,而如果选$0$个,最终还是多付了一个。

因此,第$|A_i|=F[S-C_i(D_i+1)]$

因为我们要求集合的并,因此,我们需要考虑容斥,而考虑容斥我们就需要求出集合的交

我们考虑任意最简单的情况:两个集合的交
$$
\left|A_i \bigcap\ A_j\right|
$$
我们从定义出发,$A_i$为第$i$种硬币不满足限制的方案集合,而$A_j$为第$j$种硬币不满足限制的方案集合。

而显然,同时满足$i$种硬币不满足限制与$j$种硬币不满足限制这样的性质的集合,为它们的交。

同样地,我们可以把他们两个的$D_i+1$都先支付出去,那么则有
$$
\left|A_i \bigcap\ A_j\right|=F[S-C_i(D_i+1)-C_j(D_j+1)]
$$

那么
$$
\begin{aligned}
ans&=F[s]-\left|\bigcup_{i=1}^4 A_i\right| \
&=F[s]-\sum_{T \subseteq{1,2,3,4}} -1^{|T|-1}\left|\bigcap_{j \in T } A_{j}\right| \
&=F[s]-(-1)^{|T|-1}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)]\
&=F[s]+(-1)^{|T|}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)]
\end{aligned}
$$
那么我们可以状压枚举$T$算出答案。

总的复杂度为$O(4S+16n)$

代码:


#include <iostream>

using namespace std;

const int maxn = 10;

int c[maxn],d[maxn];

long long f[100010];

int main(){
    int n;
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i++){
        for (int j = c[i]; j <= 100010; j++){
            f[j] += f[j - c[i]];
        }
    }
    while(n--){
        int s;
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        long long ans = f[s];
        for (int i = 0; i < 1 << 4; i++){
            long long sum = 0,cnt = 0;
            for (int j = 0; j < 4; j++){
                if (i >> j & 1){ 
                    sum += c[j + 1] * (d[j + 1] + 1);
                    cnt++;
                }
            }
            //cout << sum << endl;
            long long t = s - sum;
            if (cnt % 2 == 0 && t >= 0 && sum != 0) ans += f[s - sum];
            else if (t >= 0 && sum != 0) ans -= f[s - sum];
        }
        cout << ans << endl;
    }
    //system("PAUSE");
    return 0;
}




活动打卡代码 AcWing 1152. 格雷码

wxy_
5天前
#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

unsigned long long n,k;

vector<int> a;

ull power(int x){
    ull ans = 1;
    ull a = 2;
    for (; x;x >>= 1){
        if (x & 1) ans = ans * a;
        a = a * a;
    }
    return ans;
}


void solve(ull n,ull k){
    if (n == 1){
        if (k == 0) a.push_back(0);
        else a.push_back(1);
    }else{
        if (k < ull(power(n) / 2)){
            a.push_back(0);
            solve(n - 1,k);
        }
        if (k >= ull(power(n) / 2)){
            a.push_back(1);
            solve(n - 1,power(n) - k - 1);
        }
    }
}


int main(){

    cin >> n >> k;

    solve(n,k);

    for (int i = 0; i < a.size(); i++){
        cout << a[i];
    }

    return 0;
}




wxy_
7天前

第一问(哈希)

要使得包含单词最多,那么就需将文章中所有在单词表中出现过的单词全部统计。

而一个字符一个字符的比对复杂度过高,因此我们需要求出单词表与文章的字符串哈希,这样我们就可以$O(1)$比较了。而哈希之后的值是一个整数,那么我们目前的问题就转化为有两个数组$A[]$和$B[]$,$A[]$数组中有多少个不同的数在$B[]$中出现过。那么对于这个问题很显然我们可以建立一个$bool$数组$C[]$与$bool$数组$used[]$,扫 一遍$A[]$,以$A[]$中的每个元素为下标,赋值为$true$。扫一遍$B[]$,如果$C[B[i]]==true$且$used[B[i]]=false$那么$cnt++$,$used[B[i]]$赋值为$true$。

那么很显然我们就可以用哈希值作为$C[]$数组的下标(要保证在求哈希之模的数能作为数组下标)愉快的解决第一个问。

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s;
        have[hsh(s)] = true;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> s;
        val[i] = hsh(s);
        if (have[val[i]] && !used[val[i]]){
            cnt++;
            used[val[i]] = true;
        }
    }

此步复杂度为$O(m)$

第二问

第二问暴力部分分

$O(m^3)$暴力枚举

我们可以枚举长度$len$并分别判断从第$i$个单词开始为第一个单词的长度为$len$子串是否合法(即在$B[]$中存在连续的长度为$k$的一段,包含$cnt$个单词)。其中$1≤len≤m$,判断的复杂度为$O(m^2)$

因此总复杂度为$O(m^3)$

$O(m^2\ log\ m)$暴力二分

在上面所描述的暴力中,我们将第二问转化为了一个判定问题。

而在我们所枚举的集合很显然是具有单调性的:

如果答案为$k$

那么如果长度大于$k$必然合法

而长度要是小于$k$则必然不合法

因此我们可以二分长度$len$,$check$的复杂度为$O(m^2)$,二分的复杂度为$O(log\ m)$因此总复杂度为$O(m^2\ log\ m)$。

$O(m)$正解

设$f_{l,r}$为从$B[l]$到$B[r]$这段区间内,包含$A[]$中的数的个数。

当$f_{l,r}=cnt$且$C[B[r]]=true$并满足于$C[B[r+1]]=false$时

设其中包含$cnt$个$A[]$中元素个数的最短区间为$[a,b]$(等价于$[a,r]$)

那么显然$f_{a,b}=f_{l,r}=f_{a,r}$

那么我们则可以用$r - a + 1$更新元素

我们维护一个集合$S$与$S’$,$S$包括$B[l] \sim B[r]$,$S’$包括$B[a] \sim B[r]$

那么$(r-l+1)=|S|$,$(r-a+1)=|S’|$

我们已知$l,r$与集合$S$,接下来即求出$a$与$S’$

因为$f_{l,r}=f_{a,r}=cnt$且$[a,r]$为包含$cnt$个$A[]$中元素个数的最短区间

那么$f_{a+1,r}$必然小于$cnt$

且$f_{l,r-1}$必然小于$cnt$

且$[a,r]$为连续的一段

因此我们得到$S’$最朴素的做法即从$l$开始依次删除$B[i]$所对应的集合的元素。对应的区间为$[c,r]$当$f_{c,r}<cnt$时$r-c+2$即为$r - a + 1$。

因此我们可以枚举$r$,计算$f_{1,r}$并维护集合$S$,每次枚举插入$B[r]$。

当$f_{1,r}=cnt$时依次删除前$i$个元素,直到$f_{1,r}<cnt$

并用$|S’|+1$更新答案。

而对于集合$S$,因为我们只在一端插入,一端删除,因此可以用队列维护。

而对于每个元素最多进队$1$次出队$1$次。

因此复杂度为$O(m)$。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int mod = 1000007;
const int base = 131;
bool have[mod], used[mod];
int val[100005],sum[mod];
char s[15];
queue<int> q;

int hsh(char* s){
    int ret = 0, len = strlen(s);
    for (int i = 0; i < len; i++){
        ret = (ret * base + s[i]) % mod;
    }
    return ret;
}

int main() {
    int n, m, cnt = 0, len, now;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s;
        have[hsh(s)] = true;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> s;
        val[i] = hsh(s);
        if (have[val[i]] && !used[val[i]]){
            cnt++;
            used[val[i]] = true;
        }
    }
    if (cnt == 0){
        cout << 0 << endl;
        cout << 0 << endl;
    }else{
        len = m;
        now = 0;
        for (int i = 1; i <= m; i++){
            int queuelen = q.size();
            q.push(i);
            sum[val[i]]++;
            if (have[val[i]] && sum[val[i]] == 1) now++;
            if (now == cnt){
                while (now == cnt){
                    int v = q.front();
                    q.pop();
                    sum[val[v]]--;
                    if (sum[val[v]] == 0 && have[val[v]]) now--;
                }
                queuelen = q.size() + 1;
                len = min(len,queuelen);
            } 
        }
        cout << cnt << endl << len;
    }
    return 0;
}



wxy_
7天前

题目大意

给定一个长度为$n$的序列$a$,求出长度至少为$k$的子序列,使得:

所有下标为奇数的元素的最大值与所有下标为偶数的元素的最大值的最小值最小

即$min(max(s_1,s_3,s_5…),max(s_2,s_4,s_6…))$

$2 ≤k≤2\times10^5$

$Time\ Limit:2s$

$input:$

4 2
1 2 3 4

$output:$

1

思路

我们如果考虑枚举每种组合方式,其复杂度是指数级的。

那么我们考虑能不能将这个问题转化为一个判定问题?

即$a_i$为在奇数位/偶数位时的最大值能否构造出一个符合条件的$s$

那么,我们可以$O(n)$的时间$check$:

对于在奇数位,即在$a$中找到不连续的至少$k-\lfloor\frac{k}{2}\rfloor$个不大于$a_i$的数

(且对于最后一位,如果$k$一共有偶数位而其小于$a_i$的数恰好有$k-\lfloor\frac{k}{2}\rfloor$个,而最后一位是$n$则也是不合法的,对于偶数位的check也同理)

证明:若当前满足条件的有$c$个数(即小于等于$a_i$),且$c≥k$

如果$k\ mod\ 2\ ==\ 0$ 那么$\lfloor\frac{k}{2}\rfloor=\frac{k}{2}$

而在$c$中间至少存在$c-\frac{k}{2}-1$个间隔可以插入偶数项,且可以保证最后一项为偶数项。

而因为$c≥k$,因此保证$c≥\frac{k}{2}+1$,而其最后一位为偶数项。

因此必定合法。

对于在偶数位,即在$a$中找到不连续的至少$\lfloor\frac{k}{2}\rfloor$个不大于$a_i$的数

因此我们可以遍历一遍$a$进行$check$

我们的答案就是所有合法的方案中最小的$a_i$。

但是这种$check$有一种问题,我们选的是最多的,但选的方案中不一定包含$a_i$。但任意一种不包含$a_i$的方案必然可以转化为最大值为小于$a_i$的一种方案,因此对取$min$是没有影响的。

bool check(int x,int state){

    if (state == 1){
        int c = 0,right = 0;
        for (int i = 1; i <= n; i++){
            if (a[i] <= x){
                right = i;
                c++;
                i++;
                //if (i <= n)b++;
            }
        }
        if (c == k - k / 2 && right == n && k % 2 == 0) return false;
        return c  >= k - k / 2;
    }else{
        int c = 0,right = 0;
        for (int i = 2; i <= n; i++){
            //cout << i << endl;
            if (a[i] <= x){
                right = i;
                c++;
                i++;
                //if (i <= n)c++;
            }
        }
        //cout << right << endl;
        if (c == k / 2 && right == n && k % 2 != 0) return false;
        return c  >= k / 2;
    }
}

而对于我们所找到的这段不连续的数,如果其可以找到对应的$s_1,s_3,s_5…$,而我们的目标为$min(max(s_1,s_3,s_5…),max(s_2,s_4,s_6…))$

而对于$max(s_2,s_4,s_6…)$,因为在$a$中一定存在至少$k$个不连续的且小于$a_i$的元素,因此在这些元素之间至少可以包含$\lfloor\frac{k}{2}\rfloor$个元素,而这些元素可以当偶数位。且对应着一种合法的偶数方案。

因此我们可以朴素枚举$a_i$,每次用$a_i$去取$min$更新$ans$,复杂度$O(n^2)$。

那么我们已经把这个问题的求解转化为了判定,那么此时就应该证明其单调性,试图用二分将复杂度降到$O(n\log n)$。

单调性证明:

我们要证明的命题如下:

命题一:对于任一合法的$a_i$,则对于任何大于等于$a_i$的$a_j$都合法

命题二:对于任一不合法的$a_i$,则对于任何小于等于$a_i$的$a_j$都不合法

对于命题一:
如果$a_i$为奇数项

如果对于$a_i$来说,设其满足不连续的不大于$a_i$的数的个数为$c_i$,对于$c_i$,最小为$k-\lfloor\frac{k}{2}\rfloor$,且$a_j$为大于等于$a_i$的正整数集合中最小的元素。

如果$k-\lfloor\frac{k}{2}\rfloor$

那么这$k$个数必然不相邻

若不存在相邻的情况,则$k-\lfloor\frac{k}{2}\rfloor+1$

而对于$a_j$,在满足$a_i$的集合中,至多有两个元素与$a_j$相邻。

此时,$c_j=k-\lfloor\frac{k}{2}\rfloor-1$

那么如果$a_j$为偶数项,则必定满足

当$\lfloor \frac{k}{2} \rfloor=\frac{k}{2}-1$时(即$k$一共有奇数项)

$c_j=k-\frac{k}{2}$(则$a_j$作奇数项时一定合法)

当$\lfloor \frac{k}{2} \rfloor=\frac{k}{2}$时(即$k$一共有偶数项)

$c_j=k-\frac{k}{2}-1$

而它既不能放在奇数项,又不能放在偶数项是不是就不合法了呢?

但是这并不影响二分的最终结果

因为最多会有两个在$c_j$两边的小于$a_j$的值,而如果我们选取不选$a_j$,仍然可以保证其所选的数大于等于$k$,而因为它比$a_i$大,必然不会成为答案,而答案一定在$a_j$的左边,即对于任一$a_j$只要其非连续地小于等于它的数大于等于特定值,答案一定在$a_j$的左边,

而对于命题二,同样地如果$a_i$不合法有以下两种可能:

1.不大于$a_i$的数的个数不足$k$

2.小于$a_i$的数不能够满足不连续分布

首先对于1,$a_j$必然不可能

而对于2,因为我们每次找的都是连续的,不超过$a_i$的,而$a_i$没找到,则$a_j$必然找不到。

因此我们的$check$是满足单调性的。

#include <iostream>
#include <algorithm>

using namespace std;


const int maxn = 2e5 + 10;

int a[maxn],b[maxn];
int n,k;

bool check(int x,int state){

    if (state == 1){
        int c = 0,right = 0;
        for (int i = 1; i <= n; i++){
            if (a[i] <= x){
                right = i;
                c++;
                i++;
                //if (i <= n)b++;
            }
        }
        if (c == k - k / 2 && right == n && k % 2 == 0) return false;
        return c  >= k - k / 2;
    }else{
        int c = 0,right = 0;
        for (int i = 2; i <= n; i++){
            //cout << i << endl;
            if (a[i] <= x){
                cout << a[i] << " ";
                right = i;
                c++;
                i++;
                //if (i <= n)c++;
            }
        }
        //cout << right << endl;
        if (c == k / 2 && right == n && k % 2 != 0) return false;
        return c  >= k / 2;
    }
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }   
    sort(b + 1,b + n + 1);

    int l = 1,r = n;
    while(l < r){
        int mid = r + l >> 1;
        cout << l << " " << r << " " << mid << endl;
        if (check(b[mid],0) || check(b[mid],1)) r = mid;
        else l = mid + 1;
    }
    cout << b[l];



    //system("PAUSE");

    return 0;
}



wxy_
7天前

题目大意

题目描述

给定两个长度为$n$的$01$串$a$和$b$,要求串$a$的任意子序列经过若干次“旋转”操作变为串$b$

对于一次“旋转操作”我们这样定义:
如果我们要旋转的序列为

$c_1,c_2,c_3,c_4,c_5…c_n$

那么旋转之后的序列为$c_n,c_1,c_2,c_3,c_4…c_{n-1}$

例如对于$s=1110100$

如果我们旋转的子序列的下标为${2,6,7}$(从$1$开始)

那么旋转之后的串为$1010110 $

求至少进行多少次“旋转”操作,能够把串$a$变成串$b$

输入格式

输入一共三行

第一行输入一个整数$n(1≤n≤10^6)$
第二行输入串$a$

第三行输入串$b$

输出格式

输出为$1$行,为最小的操作次数

思路

首先,如果要求我们改变的次数最小,那么我们就只改变$a$与$b$中不相同的元素。

设集合$c$为$a$中与$b$中的元素不同的元素,并且对于每个元素其值等于$a$的值。

而对于$c$中的元素而言,每一对不同的$1$和$0$都可以进行一次“旋转”操作,我们可以看作其两个元素进行交换。

而若干个元素的“旋转”操作可以看作若干次“交换”操作

因此如果$c$当中的$1$和$0$的个数不同是一定不能将$a$变为串$b$

而现在,我们的目标为用尽量少的操作使得$c$中的元素全部取反(即$1$变成$0$,$0$变成$1$)

那么我们每次进行旋转操作的序列一定是形如$010101$或$101010$这样的序列(必须为偶数位)

如果我们进行旋转操作的序列为形如$111000$这样的序列,那么就等价于我们进行三次$10$这样的旋转操作

那么我们要使得进行的操作次数尽量少,即每次使得我们选的子序列尽量的长

那么我们每进行一次操作就会使得和最大的子段的和减一,即每进行一次操作都能使得$max(\sum_{i=l}^r\left | c_i \right |)$减一

证明:

假设子段$[l,r]$的和为正数,那么子段两边的元素一定是$-1$,否则$\sum_{i=l}^r\left | c_i \right |$可以更大。

同理$c[l]$与$c[r]$必然是$1$,否则缩小区间范围,一定可以更大。

设该子段中一共有$k$个$1$,长度为$m$,那么该子段的$-1$的个数为$m-k$。

那么在该子段外至少有$2\times k -m$个$-1$

对于其中的$-1$,我们至多$m-k$次就可以将所有的$-1$变$1$(即所有的$-1$全都挨在一起的情况)

而对于每次操作,我们选择的$1$的个数比$-1$的个数多一定更优

因为我们当前子段的和是最大的,且为正,因此$1$的个数必然比$-1$的个数多

考虑反证

如果我们选的$-1$比$1$多的话,那么在当前子段至多选

$2\times m-2\times k-1$个元素

如果我们$1$的个数比$-1$的个数多,那么当前子段至多选

$2\times m-2\times k+1$个元素

而对于外面的元素,如果排序方式改变最多损失两个元素

因此至少不会变坏,且会更优

如果我们$-1$选$p$个,那么$1$必然会选$p+1$个

那么,其减少了$1$

如果到最后的序列不存在$-1$,那么每次我们至少可以从当前序列中选出一个$1$取反,因为在该子段外至少有$2\times k -m$个$-1$

因此,每次操作我们都可以使得$max(\sum_{i=l}^r\left | c_i \right |)$减一

并且,因为其和最大,所以能够确保每次操作,都能够作用于当前子段

那么,当$max(\sum_{i=l}^r\left | c_i \right |)$减为$0$时,即最小操作次数。

答案即为$max(\sum_{i=l}^r\left | c_i \right |)$

$QED$

而我们可以用下面代码$O(n)$的求出上述式子

#include <iostream>

using namespace std;

const int maxn = 1e6 + 10;

char a[maxn],b[maxn];

int c[maxn],n;


int get(int x){
    int cur = 0,res = 0;
    for (int i = 0; i < n; i++){
        cur += x * c[i];
        res = max(res,cur);
        if (cur < 0) cur = 0;
    }
    return res;
}

int main(){
    cin >> n >> a >> b;
    int s0 = 0,s1 = 0;
    for (int i = 0; i < n; i++){
        if (a[i] != b[i] && a[i] == '1'){ 
            c[i] = 1;
            s1++;
        }
        if (a[i] != b[i] && a[i] == '0'){ 
            c[i] = -1;
            s0++;
        }
    }
    if (s1 != s0){
        cout << -1;
        //system("PAUSE");
        return 0;
    }
    cout << max(get(1),get(-1));
    //system("PAUSE");
    return 0;
}


活动打卡代码 AcWing 320. 能量项链

wxy_
1个月前

#include <iostream>

using namespace std;

const int N = 110;

long long f[N * 2][N * 2],a[N * 2];

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        a[i + n] = a[i];
    }
    a[n + n + 1] = a[1];
    for (int len = 3; len <= n + 1; len++){
        for (int l = 1; l <= 2 * n - len + 2; l++){
            int r = l + len - 1;
            //if (l == r) f[l][r] = 0;
            for (int k = l + 1; k < r; k++){
                f[l][r] = max(f[l][r],f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)ans = max(ans,f[i][i + n]);
    cout << ans;
    //cout << f[1][4];
    //cout << f[4][8];
    return 0;
}







活动打卡代码 AcWing 312. 乌龟棋

wxy_
1个月前
#include <iostream>

using namespace std;

const int N = 400,M = 41;

int f[M][M][M][M];

int s[N],card[10];

int main(){
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= m; i++){
        int v;
        cin >> v;
        card[v]++;
    }
    f[0][0][0][0] = s[1];

    for (int a = 0; a <= card[1]; a++){
        for (int b = 0; b <= card[2]; b++){
            for (int c = 0; c <= card[3]; c++){
                for (int d = 0; d <= card[4];d++){
                    int sum = s[a * 1 + b * 2 + c * 3 + d * 4 + 1];
                    int &v = f[a][b][c][d];
                    if (a > 0)v = max(v,f[a - 1][b][c][d] + sum);
                    if (b > 0)v = max(v,f[a][b - 1][c][d] + sum);
                    if (c > 0)v = max(v,f[a][b][c - 1][d] + sum);
                    if (d > 0)v = max(v,f[a][b][c][d - 1] + sum);
                }
            }
        }
    }

    cout << f[card[1]][card[2]][card[3]][card[4]];
    return 0;
}


活动打卡代码 AcWing 325. 计算机

wxy_
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;

int head[N],fail[N << 1],ver[N << 1],edge[N << 1],maxson[N],c[N],fw[N],tot;

int d[N];

void add(int x,int y,int w){
    ver[++tot] = y;
    edge[tot] = w;
    fail[tot]= head[x];
    head[x] = tot;
}

void dfs_d(int u,int father){
    fw[u] = d[u] = c[u] = 0;
    for (int i = head[u]; i; i = fail[i]){
        int son = ver[i];
        int w = edge[i];
        if (son == father)continue;
        dfs_d(son,u);
        if (d[u] < d[son] + w){
            c[u] = d[u];
            maxson[u] = son;
            d[u] = d[son] + w;
        }else if(c[u] < d[son] + w){
            c[u] = d[son] + w;
        }
    }
}

void dfs_f(int u,int father){
    for (int i = head[u];i;i = fail[i]){
        int son = ver[i];
        int w = edge[i];
        if (son == father) continue;
        if (maxson[u] == son){
            fw[son] = max(fw[u],c[u]) + w;
        }else{
            fw[son] = max(fw[u],d[u]) + w;
        }
        dfs_f(son,u);
    }
}

int main(){
    int n;
    while (cin >> n){
        memset(head,0,sizeof head);
        tot = 0;
        for (int i = 2; i <= n; i++){
            int a,b;
            cin >> a >> b;
            add(i,a,b);
            add(a,i,b);
        }
        dfs_d(1,0);
        dfs_f(1,0);
        for (int i = 1; i <= n; i++) cout << max(fw[i],d[i]) << endl; 
    }
    return 0;
}



活动打卡代码 AcWing 324. 贿赂FIPA

wxy_
1个月前
void dfs(int u){
    siz[u] = 1;
    f[u][0] = 0;
    for (int i = head[u];i; i = fail[i]){
        int son = edge[i];
        dfs(son);
        siz[u] += siz[son];
        for (int v = m; v >= 0; v--)
            for (int j = 0; j <= v; j++)
                f[u][v] = min(f[u][v],f[son][j] + f[u][v - j]);
    }
    for (int i = 1; i <= siz[u]; i++) f[u][i] = min(f[u][i],w[u]);
}


活动打卡代码 AcWing 323. 战略游戏

wxy_
1个月前
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1510;

int f[N][2];
bool father[N];

int edge[N],head[N],fail[N],tot;

void add(int x,int y){
    edge[++tot] = y;
    fail[tot] = head[x];
    head[x] = tot;
}

void dfs(int u){
    f[u][1] = 1;
    f[u][0] = 0;
    for (int i = head[u];i; i = fail[i]){
        int son = edge[i];
        dfs(son);
        f[u][1] += min(f[son][1],f[son][0]);
        f[u][0] += f[son][1];
    }
}

int main(){
    int n;
    while(cin >> n){
        memset(father,false,sizeof father);
        memset(head,0,sizeof head);
        tot = 0;
        for (int i = 0; i < n; i++){
            f[i][1] = 1;
            f[i][0] = 0;
            int a,cnt;
            scanf("%d:(%d)",&a,&cnt);
            for (int i = 0; i < cnt; i++){
                int b;
                cin >> b;
                add(a,b);
                father[b] = true;
            }
        }
        int root;
        for (int i = 0; i < n; i++)
            if (father[i] == false) root = i;
        dfs(root);
        cout << min(f[root][1],f[root][0]) << endl;
    }
    return 0;
}