头像

Riki




离线:2小时前



Riki
3天前

题目描述

给定一个数n,要求输出1~n的全排列,按字典序输出;

样例

3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

经典dfs $O(n^2)$

dfs(深度优先搜索) : 沿着树的深度来遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

dfs使用递归, 我个人理解dfs函数可以分为四个部分;
1. 边界判断, 即何时递归到底, 以及到达边界后需要进行什么操作;
2. 状态数组更新, 以及此时需要做的记录等操作;
3. 进行下一步新的dfs;
4. 回溯回来后现场恢复, 包括状态数组的恢复,以及其他需要做的操作;

C++ 代码

#include<iostream>
using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;

void dfs(int u){                    //u是dfs的层数,或者说是树高;
    if(u == n){                     //边界条件的判断,以及到达边界后,将这一条路径输出出来;
        for(int i = 0; i < n; ++i) cout<<path[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i = 1; i <= n; ++i){    //i是当前值;
        if(!st[i]){                 //如果i没有在path里的话
            path[u] = i;            //将i加入path中
            st[i] = true;           //更新i的状态;
            dfs(u+1);               //进行下一层的dfs;
            st[i] = false;          //回溯回来后,将i从path中去除,更新i的状态;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 842. 排列数字

Riki
3天前
#include<iostream>
using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; ++i) cout<<path[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i = 1; i <= n; ++i){
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    dfs(0);
    return 0;
}



Riki
3天前

题目描述

给定一个长度为 m 的整数序列 a1,a2,…,am。

序列中每个元素的值 ai 均满足 1≤ai≤n。

当一个值为 i 的元素和一个值为 j 的元素相邻时,可以产生的收益为 w[i][j]。

现在,我们可以从序列中删除最多 k 个元素,删除一些元素后,原本不相邻的元素可能会变得相邻。

序列的收益和为所有相邻元素对产生的收益之和,例如一个长度为 3 的整数序列 1,3,2 的收益和为 w[1][3] + w[3][2]。

请问,通过利用删除操作,能够得到的序列的最大收益和是多少?

样例

输入样例

4 1 3       //n为数据最大值,k为最多允许删除多少,m为序列长度;
1 4 2       //给定的序列
0 3 0 1     //收益矩阵,由题意,此收益矩阵是对称矩阵;
3 0 0 0
0 0 0 0
1 0 0 0

输出样例

3           //输出最大收益

数据范围
对于 30% 的数据,1≤n,k,m≤20。
对于 100% 的数据, 1≤n,k,m≤200 ,0≤w[i][j]≤10^7,1≤ai≤n。

数据保证 w[i][j]=w[j][i],w[i][i]=0。 //即收益矩阵为对称矩阵;


算法1

dp $O(n^3)$
  • 状态表示:我们可以设一个状态数组f[i][j],表示在序列的前i-1个数中删除j个数,并保留第i个数,所得到的收益最大值,即i为一个右边界,j为在这个范围中删掉的元素个数,j∈[0,k]
  • 状态计算:在0i之间取一个点u,删除掉 ui 之间的其他元素,则共删掉 i-u-1 个元素,并且有 ui 相邻,即有 w[a[u]][a[i]];因为要删掉 j 个元素,所以在区间[0, u-1]中要删掉 j-(i-u-1) 个元素,并且满足这个要求的最大值 f[u][j-(i-u-1)];则有状态转移方程 f[i][j] = max(f[i][j], f[u][j-(i-u-1)] + w[a[u]][a[i]]);
  • 最后在所有f[m][i], i∈[0,k]中找到最大值即可;

时间复杂度

状态数(n^2) * 转移数(n) = O(n^3)

Tips

  • 第一个和最后一个数可以不删的原因:因为这两个数属于端点数,删了不会产生收益,相反,保留可能会有额外收益;
  • 最后找最大值时第一维为m也是这个原因;

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 207;
int a[N], w[N][N], f[N][N];
//a[]为序列数组,w[][]为收益矩阵,f[][]为二维状态数组;

int main()
{
    ios::sync_with_stdio(false);

    int n, k, m;
    cin>>n>>k>>m;
    for(int i = 1; i <= m; ++i)
        cin>>a[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin>>w[i][j];
    //状态数组因为是全局变量,自动初始化为0,故这里可以省略初始化步骤;
    for(int i = 1; i <= m; ++i)
        for(int j = 0; j <= k; ++j)
            for(int u = 0; u < i; ++u)      //以u为界
                if(j >= i-u-1)              //要删除的数j必须>= u与i之间的元素数,“=”的情况下u前面已经没有元素可以删了
                    f[i][j] = max(f[i][j], f[u][j-(i-u-1)] + w[a[u]][a[i]]);
    int res = 0;
    for(int i = 0; i <= k; ++i)
        res = max(res, f[m][i]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 3499. 序列最大收益

Riki
3天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 207;
int s[N], w[N][N], f[N][N];

int main()
{
    int n, k, m;
    cin>>n>>k>>m;
    for(int i = 1; i <= m; ++i)
        cin>>s[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin>>w[i][j];
    for(int i = 1; i <= m; ++i)
        for(int j = 0; j <= k; ++j)
            for(int u = 0; u < i; ++u)
                if(j >= i-u-1)
                    f[i][j] = max(f[i][j], f[u][j-(i-u-1)] + w[s[u]][s[i]]);
    int res = 0;
    for(int i = 0; i <= k; ++i)
        res = max(res, f[m][i]);
    cout<<res;
    return 0;
}



Riki
3天前

题目描述

给定一个长度为 n 的正整数数列 a1,a2,…,an。

初始时,数列中的每个元素要么处于可选状态,要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。

请问,在经过此操作后,所有处于可选状态的元素之和最大是多少。

样例

输入样例

4 3
10 5 4 7
0 1 1 0

输出样例

19

数据范围
对于 30% 的数据,1≤k≤n≤1000
对于 100% 的数据,1≤k≤n≤10^5,1≤ai≤10^5


算法一

前缀和 $O(n)$

根据题意,可以将所要求的和分为两部分, 第一部分是本来状态就是1的数的和, 用sum1表示, 第二部分是窗口k 内本来状态为0, 后被置为1的数的和, 使用sum2表示, 则最终答案为这两者之和;

因为窗口可以看作一个区间, 于是这里先用前缀和做一遍;

使用前缀和数组的时候, 前缀和数组中存的是状态为0的数的前缀和, 所有状态为1的数不被计入前缀和数组中;

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5+7;
typedef long long LL;
int a[N];                           //保存原数组;
LL s[N], sum1;                      //状态0的前缀和数组与 状态1的所有数之和;

int main()
{
    ios::sync_with_stdio(false);

    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    for(int i = 1; i <= n; ++i){
        int b;
        cin>>b;
        if(b == 0)                  //状态为0时计入前缀和数组中;
            s[i] = s[i-1] + a[i];
        else{
            s[i] = s[i-1];          //状态为1的数不计入前缀和;
            sum1 += a[i];           //但是加到sum1中;
        }
    }
    LL sum2 = 0;
    for(int i = 0; i < n-k+1; ++i){ //找到窗口为k的区间里状态0的数之和最大值, 使用sum2保存;
        if(s[i+k] - s[i] > sum2)
            sum2 = s[i + k] - s[i];
    }
    cout<<sum2 + sum1;              //最终答案即为这两部分数之和
    return 0;
}

算法2

滑动窗口 $O(n)$

如上所述, sum2为一个窗口内的状态为0的数之和, 则可以使用滑动窗口来做

C++代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+7;
typedef long long LL;
int a[N], b[N];                 //a为数据数组,b为状态数组;
LL sum1, sum2;

int main()
{
    ios::sync_with_stdio(false);

    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    for(int i = 1; i <= n; ++i){
        cin>>b[i];
        if(b[i])
            sum1 += a[i];       //输入状态数组的同时把sum1算出来;
    }
    LL tmp = 0;
    for(int i = 1; i <= n; ++i){
        if(!b[i]) tmp += a[i];              //滑动窗口右边界, 状态为0就加到临时变量里;
        if(i > k && !b[i-k]) tmp -= a[i-k]; //滑动窗口左边界, 超出窗口长度且状态为0就减去;
        sum2 = max(sum2, tmp);
    }
    cout<<sum2 + sum1;
    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

Riki
3天前
#include<iostream>
using namespace std;

const int N = 1e5+7;
typedef long long LL;
int a[N];
LL s[N], sum1;

int main()
{
    ios::sync_with_stdio(false);

    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    for(int i = 1; i <= n; ++i){
        int b;
        cin>>b;
        if(b == 0)
            s[i] = s[i-1] + a[i];
        else{
            s[i] = s[i-1];
            sum1 += a[i];
        }
    }
    LL sum2 = 0;
    for(int i = 0; i < n-k+1; ++i){
        if(s[i+k] - s[i] > sum2)
            sum2 = s[i + k] - s[i];
    }
    cout<<sum2 + sum1;
    return 0;
}


活动打卡代码 AcWing 3485. 最大异或和

Riki
4天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100007*31, M = 1e5+7;
int s[M];
int son[N][2], cnt[N], idx;

void insert(int x, int v)
{
    int p = 0;
    for(int i = 30; i >= 0; --i){
        int u = x >> i & 1;
        if(!son[p][u])
            son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += v;
    }
}

int query(int x)
{
    int res = 0, p = 0;
    for(int i = 30; i >= 0; --i){
        int u = x >> i & 1;
        if(cnt[son[p][!u]]){
            p = son[p][!u];
            res = res*2 + 1;
        }
        else{
            p = son[p][u];
            res *= 2;
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        int x;
        cin>>x;
        s[i] = s[i-1] ^ x;
    }

    int res = 0;
    insert(s[0], 1);

    for(int i = 1; i <= n; ++i){
        if(i > m) insert(s[i-m-1], -1);
        res = max(res, query(s[i]));
        insert(s[i], 1);
    }

    cout<<res;
    return 0;
}



Riki
21天前

题目描述

给定一个字符串,再给定m个询问,要求输出每一次询问中[l1, r1] 和[l2, r2] 这两个区间内的字符串是否相同;

样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
Yes
No
Yes

算法1

字符串哈希

字符串哈希即将一个字符串转化成一个整数,并保证字符串不同,得到的哈希值不同,这样就可以用来判断一个该字串是否重复出现过。构造哈希函数的关键点在于使不同字符串的哈希冲突率尽可能小。字符串哈希中也有用到前缀和思想;
字符串哈希与普通哈希的区别是 没有解决冲突的函数,是否冲突基本看脸
字符串哈希函数常用的有:
1. 自然溢出法:
p一般取值为131或13331;

Hash[i] = Hash[i-1]*p + str[i];

利用unsigned long long 自然溢出,相当于自动对2^64−1取模;
2. 单哈希法:

Hash[i] = (Hash[i-1]*p + str[i])%mod;

p,mod均为质数,p < mod,p,mod取尽量大时冲突很小
3. 双哈希法:
将字符串用不同mod单哈希两次,结果用二元组表示

Hash1[i] = (Hash1[i-1]*p + str[i])%mod1
Hash2[i] = (Hash2[i-1]*p + str[i])%mod2
Hash[i]:<Hash1[i],Hash2[i]>

这种方法很安全

C++ 代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e5+7, P = 131;
ULL h[N], p[N];
//h[]为字符串哈希数组;p[]为P的n次方预处理数组;

ULL get(int l, int r){
    return h[r] - h[l-1] * p[r-l+1];
}

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    string s;
    cin>>n>>m>>s;
    p[0] = 1;           //P^0 = 1;
    for(int i = 0; i < s.size(); ++i){
        p[i+1] = p[i] * P;
        h[i+1] = h[i] * P + s[i];
    }
    int l1, r1, l2, r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1, r1) == get(l2, r2) ? "Yes" : "No")<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

Riki
21天前
#include<iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e5+7, P = 131;
ULL h[N], p[N];

ULL get(int l, int r){
    return h[r] - h[l-1] * p[r-l+1];
}

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    string s;
    cin>>n>>m>>s;
    p[0] = 1;
    for(int i = 0; i < s.size(); ++i){
        p[i+1] = p[i] * P;
        h[i+1] = h[i] * P + s[i];
    }
    int l1, r1, l2, r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1, r1) == get(l2, r2) ? "Yes" : "No")<<endl;
    }
    return 0;
}



Riki
21天前

题目描述

维护一个集合,支持下面两种操作吗,共输入N个操作;
1. I x,插入一个数 x;
2. Q x,询问数 x 是否在集合中出现过,输出结果;

样例

5
I 1
I 2
I 3
Q 2
Q 5
Yes
No

算法1

散列表开放寻址法

散列表是将关键键值映射到哈希表中一个位置来进行访问的数据结构;这个映射的函数叫散列函数,存放记录的数组叫散列表;

开放寻址法是当发生冲突时的解决方法,当两个或以上键值映射到散列表的同一个位置时,如果发现该位置已经有元素,则看它前一位有没有元素,如果有,则再向前一位,直到存入数据;

散列表大小最好要选择大于数据量的最小质数,离2的幂远一点更好, 可以降低冲突概率;

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5+7, null = 0x3f3f3f3f;

int h[N];

int find(int x){                //散列函数加开放寻址;
    int t = (x%N+N) % N;
    while(h[t] != null && h[t] != x) if(++t == N) t = 0;
    return t;
}

int main()
{
    ios::sync_with_stdio(false);

    memset(h, 0x3f, sizeof h);
    int n, x;
    char op;
    cin>>n;
    while(n--){
        cin>>op>>x;
        if(op == 'I') h[find(x)] = x;
        else cout<< (h[find(x)] == x ? "Yes" : "No")<<endl;
    }
    return 0;
}

算法2

散列表拉链法

拉链法是另一种解决哈希冲突的办法,是将哈希到同一个位置的元素做成一个单链表挂在该位置;

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5+7;

int h[N], e[N], ne[N], idx;
//h[]为哈希数组,e[]存每个节点的具体值,ne[]用来寻找同一个位置上的节点;

void insert(int x){
    int t = (x%N+N)%N;
    e[++idx] = x;
    ne[idx] = h[t];
    h[t] = idx;
}

bool find(int x){
    int t = (x%N+N)%N;
    for(int i = h[t]; i != -1; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    int n, x;
    char op;
    memset(h, -1, sizeof h);
    cin>>n;
    while(n--){
        cin>>op>>x;
        if(op == 'I') insert(x);
        else cout<<(find(x) ? "Yes" : "No")<<endl;
    }
    return 0;
}