头像

灰人




离线:3天前


最近来访(36)
用户头像
诺坎普的小逗比
用户头像
clumsy
用户头像
Fr1nGeLove
用户头像
窗外的麻雀
用户头像
slight
用户头像
TheGiao
用户头像
OrderInChaos
用户头像
无秋物语
用户头像
DPCDPC
用户头像
陆诚
用户头像
OI
用户头像
StarrySky_5
用户头像
LC.
用户头像
Pursuingdreams
用户头像
fwxlj
用户头像
Cauchy
用户头像
autwind
用户头像
_2
用户头像
瞳星结
用户头像
Rain丶bow

活动打卡代码 AcWing 4342. 就一勾子

灰人
11天前
#include <bits/stdc++.h>

using namespace std;
/*
线段树
需要pushdown 操作
将区间中的每一个元素替换为lazy
*/
typedef long long LL;

const int N = 1e5+10;

struct Node{
    int l,r;
    int lazy;
    LL sum;
} tr[4 * N];

int n, m;

void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u){
    auto & root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.lazy == 0)return;
    left.lazy = root.lazy,left.sum = root.lazy * (left.r - left.l + 1);
    right.lazy = root.lazy,right.sum = root.lazy * (right.r - right.l + 1);
    root.lazy = 0;
}

void build(int u,int l,int r){
    if(l == r)tr[u] = {l,r,0,1};
    else {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1|1,mid + 1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int lazy){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].sum = lazy * (tr[u].r - tr[u].l + 1);
        tr[u].lazy = lazy; 
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)modify(u<<1,l,r,lazy);
        if(r > mid)modify(u << 1|1,l,r,lazy);
        pushup(u);
    }
}

LL query(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r)return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if(l <= mid)res += query(u << 1,l,r);
    if(r > mid)res += query(u << 1|1,l,r);
    return res;
}

int main()
{
    int T ,cases = 1;
    scanf("%d",&T);
    while(T -- ){
        cin >> n;
        memset(tr,0,(n + 1)*25);

        build(1,1,n);
        scanf("%d",&m);
        while(m -- ){
            int l,r,c; 
            scanf("%d%d%d",&l,&r,&c);
            modify(1,l,r,c);
        }
        printf("Case %d: The total value of the hook is %lld.\n",cases++,query(1,1,n));
    }
    return 0;
}



灰人
11天前

题目描述

设有 $N$ 堆石子排成一排,其编号为 $1,2,3,…,N。$

每堆石子有一定的质量,可以用一个整数来描述,现在要将这 $N$ 堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

问题是:找出一种合理的方法,使总的代价最小,输出最小代价。

分析

状态表示:f[i][j]表示将i - j这一堆石子合并的所有方案的集合
属性:Min

状态计算:
将集合划分成:
k ∈[l,r)
将石子划分成$i 到 k$ 和 $k 到 1-j$两堆进行合并
状态转移方程为:
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));

区间DP

通常对于区间DP问题,我们都采用先枚举区间长度,再枚举区间左端点的方式
并且一般 len = 1 时用来初始化,枚举从 len = 2 开始
右端点可以通过r = l + len - 1 来计算,模板如下:

for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k++) {        // 枚举分割点,构造状态转移方程
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}

模板参考自白马金羁侠少年

C++ Code

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int q[N],s[N],f[N][N]; // f[i][j] 代表将i - j这一堆石子合并的方案的集合
int n;

int main()
{
    cin >> n;
    // 预处理前缀和
    for(int i = 1; i <= n ; ++i){
        cin >> q[i];
        s[i] = s[i - 1] + q[i];
    }

    // 区间dp: 先枚举左端点,再枚举区间长度
    for(int len = 2; len <= n; ++len){
        for(int l = 1; l + len - 1 <= n ; ++l){
            int r = l + len - 1;
            f[l][r] = 1e8;
            for(int k = l; k < r; ++k){
                f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}




灰人
11天前

题目描述

给定两个字符串 A 和 B,现在要将 A 经过若干操作变为 B,可进行的操作有:

1.删除–将字符串 A 中的某个字符删除。
2.插入–在字符串 A 的某个位置插入某个字符。
3.替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出,将 A 变为 B 至少需要进行多少次操作。

分析

状态表示: f[i][j] 表示将 a[1 - i] 变为 b[1 - j]的所有方案的集合
属性:Min

状态计算(最后一个不同点):
从对a序列的最后一个操作出发:
1.如果 a[i] = b[j] 则最后一个操作是不操作

f[i][j] = f[i - 1][j - 1];

else

(1)如果最后一个操作是删除 a[i]

f[i][j] = f[i - 1][j] + 1; // 将a[1 - i-1]变成 b[1 - j] 的操作数再加上删除操作这一次

(2)如果最后一个操作是在 a[i] 后插入一个和 b[j] 一样的数

f[i][j] = f[i][j - 1] + 1; // 将a[1 - i]变成b[1 - j-1]的操作数再加上插入操作这一次

(3)如果最后一个操作是 将a[i] 替换成b[j]

f[i][j] = f[i - 1][j - 1] + 1; // 将a[1 - i-1]变成b[1 - j-1]的操作数再加上替换操作这一次

C++ Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

char a[N], b[N];
int n,m, f[N][N];

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;

    // 预处理:将a[1 - i]变成长度为0的序列需要i次操作 同理对于 b[1 - i]
    for(int i = 0; i <= n ; ++i)f[i][0] = i;
    for(int i = 0; i <= m ; ++i)f[0][i] = i;

    for(int i = 1; i <= n ; ++i){
        for(int j = 1; j <= m ; ++j){
            if(a[i] == b[j])f[i][j] = f[i - 1][j - 1];
            else {
                f[i][j] = min(f[i - 1][j] + 1,f[i][j - 1] + 1);
                f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1);
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}



灰人
11天前

题目描述

给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

分析

状态表示: f[i][j] 表示a[1] - a[i],b[1] - b[j] 的所有公共子序列的集合
属性:Max

状态计算(以最后一个不同点来划分):

1.a[i] = b[j]

f[i][j] = f[i - 1][j - 1] + 1;// a[1] - a[i - 1],b[1] - b[j - 1]的最长公共子序列长度 + (a[i] && b[j]);

2.a[i] != b[j]

当a[i]和b[j]不同时取时 可以把公共子序列分为三种情况
1.f[i - 1][j] 中的最大公共子序列

2.f[i][j - 1] 中的最大公共子序列

3.f[i - 1][j - 1] 中的最大公共子序列

由于f[i][j]表示的是 a[1] - a[i],b[1] - b[j]的最长公共子序列

所以f[i - 1][j] f[i][j - 1]中其实已经包含了f[i - 1][j - 1]的所有情况

此外,f[i - 1][j] 和 f[i][j - 1]中也有重合的部分

但是由于本体的属性是最大值,因此只要不漏,即使存在重复我们所求的最大值也是正确的。

C++ Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
char a[N],b[N];
int n,m, f[N][N];

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    for(int i = 1; i <= n ; ++i){
        for(int j = 1; j <= m ; ++j){
            if(a[i] == b[j])f[i][j] = f[i - 1][j - 1] + 1;
            f[i][j] = max(f[i][j],f[i - 1][j]);
            f[i][j] = max(f[i][j],f[i][j - 1]);
        }
    }

    cout << f[n][m] << endl;
    return 0;
}



灰人
11天前

题目背景

给定一个长度为 m 的模式串 S,以及一个长度为 n 的模板串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

Solution 1 :KMP $O(n + m)$

对于 S 中的每一个位置 i ,我们都要找到一个最大的 j 使得 P 的长度为j的前缀(P[1] -> P[j])和 包含 S[i] 的 i 位置的长度为 j 的前缀(S[i - j + 1] -> S[i])相同。

假设我们匹配到了当前位置1.png

此时我们需要分情况讨论:

1.如果 S[i + 1] = P[j + 1] 我们就可以继续向下匹配

2.如果 S[i + 1] != P[j + 1], 我们无法继续向下匹配了

那我们需要从头开始匹配吗? 不需要

我们需要找到一个最大的的位置 k 使得 P 的长度为k的前缀(P[1] -> P[k])和包含 S[i] 的 i 位置的长度为 k 的前缀(S[i - k + 1] -> S[i])相同。

由于i ,j 之前的位置都是匹配好的,因此(S[i - k + 1] -> S[i])(P[j - k + 1] -> P[j])是完全相同的

因此我们可以将问题转化成:
我们需要找到一个最大的的位置 k 使得 P 的长度为k的前缀(P[1] -> P[k])和包含 P[j] 的 j 位置的长度为 k 的前缀(P[j - k + 1] -> P[j])相同。
2.png
问题从两个串的问题变成了 P 串中的问题

对于 P 中的每一个位置 j 我们都可以找到一个对应的位置 k ,将所有 k 的位置存在一个next数组里, 用于匹配失败之后的状态转移。

整理一下KMP的思路:

1.两串匹配,i 指针遍历 S ,j 指针遍历 P
2.如果s[i + 1] = p[j + 1],就让 j ++ 然后继续匹配
3.如果s[i + 1] != p[j + 1], 就令j = next[j]直到二者可以继续匹配
4.如果 j 匹配到下标为 n 的字符并成功,那么这一轮匹配成功,j = next[j] 再重新进行下一轮匹配直到 i 移动到下标为 m 的字符,整个匹配结束。

如何求next数组呢?

其实求next数组的过程就是 P 串和自己匹配的过程,对于 P 的每一个字符 P[i], 我们都要找到使得 P[j] 的后缀和 P[1]的前缀相同的最大位置next[j]。

C++ Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10, M = 1e6+10;

char s[M], p[N];
int n,m, ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    // 求next数组
    ne[1] = 0;
    for(int i = 2, j = 0; i <= n ; ++i){//这里i 和 j 遍历的都是 P 串
        while(j && p[i] != p[j + 1])j = ne[j];
        // 所有需要用到的next值都会在之前的迭代中计算出来, 
        //  字符串下标是从1开始的,因此 j 至少为1时才可以回退
        if(p[i] == p[j + 1])j++; // 如果下一个字符对应相同就继续向下匹配
        ne[i] = j;// 记录每一个i值匹配到的最大前缀
    }

    // KMP 每一步的思路都与上面类似
    for(int i = 1, j = 0; i <= m ; ++i){
        while(j && s[i] != p[j + 1])j = ne[j];
        if(s[i] == p[j + 1])j++;
        if(j == n){ // 匹配成功
            printf("%d ",i - n);
            j = ne[j]; // 再开启下一轮匹配
        }
    }
    return 0;
}

Solution 2:字符串哈希 $O(n + m)$

字符串哈希的具体实现方式可以参考这篇题解

字符串哈希的思路就比较简单了,我们需要算出模板串 P 的哈希值,再与 S 的每一个长度为 n 的字串的哈希值进行比较,这里代码就不再给出详细注释。

C++ Code

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5+10, M = 1e6+10, P = 131;
int n,m;
char a[M], b[N];
ULL s[M],p[M];

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


int main()
{
    cin >> n >> b + 1 >> m >> a + 1;
    p[0] = 1;
    for(int i = 1; a[i] ; ++i){
      p[i] = p[i - 1] * P;
      s[i] = s[i - 1] * P + a[i];
    }

    ULL q[N];
    for(int i = 1; b[i] ; ++i)q[i] = q[i - 1]*P + b[i]; 

    for(int i = 1;  i + n - 1 <= m; ++i){
        if(q[n] == get(i,i + n - 1))cout << i - 1 << " ";
    }
    return 0;
}



灰人
12天前

题目描述

一个正整数 n 可以表示成若干个正整数之和,形如:$n=n1+n2+…+nk$,其中 $n1≥n2≥…≥nk,k≥1$。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。

算法1

多重背包

将问题转化为:
物品体积为1,2,3…n, 背包总体积为n, 求恰好装满背包的方案数

多重背包朴素版

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, mod = 1e9 + 7 ;

int f[N][N];// 1 - i中选恰好组成j的方案的集合

int main()
{
    int n;
    cin >> n;

    f[0][0] = 1;

    for(int i = 1 ; i <= n ; ++i){
        for(int j = 0 ;  j <= n ; ++j){
            for(int k = 0;i * k <= j; ++k){//k取0的情况可以表示不取i 这样状态表示可以做到不重不漏 
                f[i][j] = (f[i][j] + f[i - 1][j - k * i]) % mod;
            }
        }
    }

    cout << f[n][n] << endl;
    return 0;
}

多重背包滚动数组优化

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];

int main()
{
    int n;
    cin >> n;
    f[0] = 1;

    for(int i = 1; i <= n ; ++i){
        for(int j = i; j <= n ; ++j){
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }

    cout << f[n] << endl;
    return 0;
}

算法2

分析:将所有情况分成两种
1.将i划分为j个数后,j个数中的最小值为1
2.将i划分为j个数后,j个数中的最小值不为1

状态表示:f[i][j] 表示将i划分成j个数的方案的集合
属性:Count
状态计算:

// 1.将i划分为j个数后,j个数中的最小值为1
f[i][j] = f[i - 1][j - 1];// 将i - 1 划分为j - 1个数 再加上最小值1 就可以表示所有方案

// 2.将i划分为j个数后,j个数中的最小值不为1
f[i][j] = f[i - j][j];
/*
由于j个数中的所有值都大于1,因此将每一个数减去一就可以得到将i - j划分为j个数的一种方案。
由于方案中的数字都是一一对应的 (x - 1 <-> x),因此两种情况下的方案数是完全相等的,可以直接转移过来。
*/

计数dp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1010, mod = 1e9+7;
int f[N][N];


int main()
{
    int n;
    cin >> n;

    for(int i = 0 ; i <= n ;++i)f[i][1] = 1;

    for(int i = 1; i <= n  ;++i){
        for(int j = 1; j<= n ;++j){
            if(i >= j)f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }

    LL res = 0;
    for(int i = 1; i <= n  ;++i)res = (res + f[n][i]) % mod;// 统计答案时需要统计将n划分为i个数的所有情况并相加

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

灰人
13天前
#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};

int g[5],h[5];

bool check(int i,int j){
    return i >= 0 && i < 5 && j >= 0 && j < 5;
}

void turn(int x,int y){
    if(h[x] >> (4 - y) & 1)h[x] -= 1 << (4 - y);
    else h[x] += 1 << (4 - y); 
}

void flip(int x,int y){
    turn(x,y);

    for(int i = 0; i < 4 ; ++i){
        int x_ = x + dx[i], y_ = y + dy[i];
        if(check(x_,y_))turn(x_,y_);
    }
}

void print(int a[]){
    for(int i = 0; i < 5; ++i){
        for(int j = 4; j >=0 ; --j){
            cout << (a[i]>>j & 1);
        }
        cout << endl;
    }
    cout << endl;
}

bool finish(){
    for(int i = 0; i < 5 ; ++i)if(h[i] != 31)return false;
    return true;
}

int dfs(int cur ,int op,int n){
    if(cur == 5)return 7;

    for(int j = 4;j >= 0 ; --j){
        if(op >> j & 1)flip(cur, 4 - j),n++;
        if(finish())return n;
        if(n == 6)return 7;
    }

    int ne = 0;
    for(int j = 4; j >= 0; --j){
        if((h[cur] >> j & 1) == 0)ne += (1 << j);
    }
    //cout<<" ne = "<<ne<<endl;
    return dfs(cur + 1,ne,n);
}

int main()
{
    int T; cin >> T;
    getchar();
    while(T -- ){
        for(int i = 0; i < 5 ; ++ i){
            char s[5];
            int x = 0;
            scanf("%s",s);
            for(int j = 0; j < 5; ++j){
                if(j)x<<=1;
                x += s[j] - 48;
            }
            g[i] = x;
        }

        int res = INT_MAX;
        for(int i = 0; i < 32; ++i){
            memcpy(h,g,sizeof g);
            int t = dfs(0,i,0);
            if(t <= 6)res = min(res,t);
        }

        if(res == INT_MAX)puts("-1");
        else printf("%d\n",res);
    }
    return 0;
}


活动打卡代码 AcWing 4225. 石油储备

灰人
15天前
#include <bits/stdc++.h>

using namespace std;
/*
floodfill
*/
const int N = 110;

const int dr[] = {0,0,1,-1,1,1,-1,-1};
const int dc[] = {1,-1,0,0,1,-1,1,-1};

char g[N][N];
int n,m;
bool vis[N][N];

bool check(int i,int j){
    return i >= 0 && i < n && j >= 0 && j < m;
}

void floodfill(int r,int c){
    for(int i = 0; i < 8 ; ++i){
        int x = r + dr[i], y = c + dc[i];
        if(check(x,y) && !vis[x][y] && g[x][y] == '@'){
            vis[x][y] = true;
            floodfill(x,y);
        }
    }
}

int main()
{
    while(cin >> n >> m,n || m){
        memset(vis,false,sizeof vis);
        for(int i = 0;  i< n ; ++i){
            for(int j = 0; j < m ; ++j){
                cin >> g[i][j];
            }
        }
        int res = 0;
        for(int i = 0; i < n ; ++i){
            for(int j = 0; j < m ; ++j){
                if(!vis[i][j] && g[i][j] == '@' ){
                    vis[i][j] = true;
                    res++;
                    floodfill(i,j);
                }
            }
        }
        cout << res << endl;
    } 
    return 0;
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

灰人
16天前
#include <bits/stdc++.h>

using namespace std;
/*
线性筛一下
*/
const int N = 1e6+10;

bool st[N];
int prime[N];
int n,cnt;

void screen(){
    st[0] = st[1] = true;
    for(int i = 2; i <= N; ++i ){
        if(!st[i])prime[cnt++] = i;
        for(int j = 0; prime[j] * i <= N; ++j){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)break;
        }
    }
}

int main()
{
    screen();

    while(cin >> n, n){
        int a,b;
        for(int i = n ;i >= 3; --i){
            if(!st[i] && !st[n - i]){
                a = n - i, b = i;
                break;
            }
        }
        printf("%d = %d + %d\n",n,a,b);
    }
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

灰人
16天前
#include <bits/stdc++.h>

using namespace std;
/*
类似快速幂思想
*/
typedef long long LL;

LL qml(LL a,LL k,LL p){
    LL res = 0;
    while(k){
        if(k & 1)res = (res + a) % p;
         k >>= 1;
         a = 2 * a % p;
    }
    return res % p;
}

int main()
{
    LL a,k,p;
    cin >> a >> k >> p;
    cout << qml(a,k,p) << endl;
    return 0;
}