头像

洋宝

辽宁工程技术大学




离线:6天前



洋宝
22天前
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int dx[8]={0,0,-1,1,1,1,-1,-1};
const int dy[8]={-1,1,0,0,1,-1,-1,1};
//这种求几次可以覆盖完全Map的,可以借助数组实现,既可以判重,还可以存储答案
const int N=105;
int ans=0;//ans每次都和新扩展的结点相比求最大值,最终就是最后扩展到的那一批结点的长度值,也就是完成牧场入侵的天数~
int X,Y,MX,MY;
int dist[N][N];
char map[N][N];
struct Node
{
    int x;int y;
};

void bfs(Node start)
{
    queue<Node> q;
    memset(dist,-1,sizeof(dist));
    //将第一个结点压入栈中
    q.push(start);
    dist[start.x][start.y]=0;

    //开始bfs
    while(!q.empty())
    {
        Node t=q.front();
        q.pop();
        //延伸结点t的子结点
        for(int i=0;i<8;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<=0||a>X||b<=0||b>Y||map[a][b]=='*') continue;
            if(dist[a][b]==-1)
            {
                //表示当前结点还未走过
                dist[a][b]=dist[t.x][t.y]+1;//当前a,b的值是其父结点+1
                ans=max(ans,dist[a][b]);
                //将新结点压入队列
                Node w;
                w.x=a,w.y=b;
                q.push(w);
            }
        }
    }
    cout<<ans<<endl;

}

int main()
{
    //先处理一下输入输出
    cin>>Y>>X>>MY>>MX;
    for(int i=X;i;i--)
    cin>>map[i]+1;
    Node start;
    start.x=MX,start.y=MY;
    bfs(start);

    return 0;
}



活动打卡代码 AcWing 1246. 等差数列

洋宝
22天前
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=100000+5;
int num[N],n;


int gcd(int a, int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&num[i]);
    }

    sort(num,num+n);
    int d=0;
    for(int i=0;i<n;i++)
    {
        d=gcd(d,num[i]-num[0]);
    }
    if(!d)
    {
        //如果d为0 说明是公差为0的等差数列
        cout<<n<<endl;
    }
    else
    {
        int x=(num[n-1]-num[0])/d+1;
        cout<<x<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 2067. 走方格

洋宝
1个月前
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=35;
int n,m,res;
int dx[2]={0,1},dy[2]={1,0};
int f[N][N];
bool check(int x,int y)
{
    if((x%2==0)&&(y%2==0))
    return true;

    else return false;
}
int dfs(int x, int y)
{
    if(x & 1 || y & 1)
    {
        if (f[x][y]) return f[x][y];         // 如果该点已经被搜索过,那么不再处理
        // 否则说明没搜索过,需要搜索一遍
        if (x < n) f[x][y] += dfs(x + 1, y);
        if (y < m) f[x][y] += dfs(x, y + 1);
    }
    return f[x][y];
}
int main()
{
    scanf("%d%d",&n,&m);
    //先特判一下,如果终点两坐标都是偶数的话,直接就可以输出答案了
    f[n][m] = n & 1 || m & 1;  // 这里要特判下 n, m 是否都为偶数
    cout<<dfs(1,1)<<endl;

}


活动打卡代码 AcWing 2066. 解码

洋宝
1个月前
//
//  main.cpp
//  十一届蓝桥杯解码
//
//  Created by 魏浩洋 on 2020/7/16.
//  Copyright ? 2020 魏浩洋. All rights reserved.
//

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;


string res;
char last_char;


bool judge_char(char a)
{
    if((a>='a'&&a<='z')||(a>='A'&&a<='Z')) return true;
    else return false;
}

bool judge_num(char a)
{
    if(a>='0'&&a<='9')
    return true;
    else return false;
}
int char_to_num(char a)
{
    int num=a-'0';
    return num;
}
int main()
{
    string str;
    cin>>str;

    last_char=str[0];
    res.push_back(str[0]);


    for(int i=1;i<str.length();i++)
    {
        if(judge_num(str[i])&&judge_char(last_char))
        {
            int a=char_to_num(str[i])-1;
            while(a--)
            {
                res.push_back(last_char);
            }
            last_char=str[i];
        }
        if(judge_char(str[i]))
        {
            res.push_back(str[i]);
            last_char=str[i];
        }
    }
    cout<<res<<endl;
    return 0;


}



洋宝
1个月前
//
//  main.cpp
//  十一届蓝桥杯解码
//
//  Created by 魏浩洋 on 2020/7/16.
//  Copyright ? 2020 魏浩洋. All rights reserved.
//

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;


string res;
char last_char;


bool judge_char(char a)
{
    if((a>='a'&&a<='z')||(a>='A'&&a<='Z')) return true;
    else return false;
}

bool judge_num(char a)
{
    if(a>='0'&&a<='9')
    return true;
    else return false;
}
int char_to_num(char a)
{
    int num=a-'0';
    return num;
}
int main()
{
    string str;
    cin>>str;

    last_char=str[0];
    res.push_back(str[0]);


    for(int i=1;i<str.length();i++)
    {
        if(judge_num(str[i])&&judge_char(last_char))
        {
            int a=char_to_num(str[i])-1;
            while(a--)
            {
                res.push_back(last_char);
            }
            last_char=str[i];
        }
        if(judge_char(str[i]))
        {
            res.push_back(str[i]);
            last_char=str[i];
        }
    }
    cout<<res<<endl;
    return 0;


}


活动打卡代码 AcWing 2065. 整除序列

洋宝
1个月前
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long LL;
LL n;
int main()
{
    cin>>n;
    while(n)
    {
        cout<<n<<' ';
        n/=2;
    }
    cout<<endl;
    return 0;
}


分享 dp问题

洋宝
1个月前

类型一:将n个苹果分成多份,最少可分0个,问所有的分配方案

参考例题: 鸣人影分身

大致思想:dp问题采用通用的dp分析法来思考,这个题的话
f(i,j)含义:将数字i分成j份的所有合法方案数
属性:个数
状态计算:一般dp问题划分集合的思路为寻找解决问题最后一个不同的点,这里的话我们以方案中的最后一位数字是否为0来划分状态。如果最后一位数字是0的话,那么f(i,j)=f(i,j-1);如果最后一位数字不为1的话,我们可以将每个方案中分配的数字都-1,这样做一个映射的话整体合法方案数是不变的,那么f(i,j)=f(i-j,j)

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=11;
int f[N][N],t,n,m;

int main()
{
    cin>>t;
    while(t--)
    {
        memset(f,0,sizeof(f));
        //m是能量总数,n是最多分配的个数
        cin>>m>>n;
        //设置边界
        //能量为0,分配0个的合法方案为1
        f[0][0]=1;//从语义理解,没能量,不分配,也算是一种合法的方案,
        for(int i=0;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]+=f[i][j-1];
                if(i>=j) f[i][j]+=f[i-j][j];
            }
        }
        cout<<f[m][n]<<endl;


    }
    return 0;
}

类型二:01背包类问题,选择+某种限制条件

参考例题: 糖果
思路:这种问题大致的意思都是从n件物品中选择若干件,然后再加上某一限定条件,例如这一题是要求模k结果为0,而往往这些限制条件都体现在状态方程的某一维上,例如本题,就采用其中一维表示模k的余数。并且个人感觉这种选择问题在划分集合时一般都按照最后一件物品选or不选来划分
状态方程:f(i,j)表示从前i件物品中选,并且物品总数量%k余数为j的最大值
属性:最大值
状态计算:1.若不选择第i件物品,那么f(i,j)=f(i-1,j)
2.选择第i件物品,那么 f(i,j)=f(i-1,(j-w[i])%k)+w[i];
第二种计算的推导:sum%k=j 那么 sum=nk+j -> sum-w[i]=nk+j-w[i]
两边同时%k, (sum-w[i])%k=(j-w[i])%k;

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=105;
int n,k,f[N][N],w[N];// w记录糖果的数目



int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;//表示从0个糖果中选,模k为0,的最大值为0,语义是合理的

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            f[i][j]=max(f[i][j],f[i-1][j]);
            f[i][j]=max(f[i][j],f[i-1][(j+k-w[i]%k)%k]+w[i]);// 为了保证模后为正数,所以做了些操作

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

}

类型三:寻找字符串中最长回文子序列的问题

大致意思就是:ACDECA, 则最长的回文子序列就是其中的ACCA,答案为4
参考例题: 密码脱落
思路:密码脱落这道题大致意思是,原先有一个,现在有一个残缺的字符串,问加多少个字符可以变成回文串,那么这实际上等价于现在这个字符串删除几个字符可以变成回文串,两个问题是等价的。所以就可以转化成求最长子回文序列问题,求出长度以后用字符串长度n-回文子序列长度=最少删除的个数

状态方程:f(l,r)表示字符串从l到r位置之间的最长子回文序列的长度的最大值
属性:最大值
状态计算:可以按照字符串l,r两端的情况来划分
1.子回文序列中包含字符串l,r两端的值, f(l,r)=f(l+1,r-1)+2;
2.子回文序列包含l,不包含r f(l,r)=f(l+1,r);(实际上这一计算包含了状态2,但因为是求最大值,所以无伤大雅,)
3.子回文序列不包含l,包含r f(l,r)=f(l,r-1)
4.子回文序列l,r两端都不包含 f(l,r)=f(l+1,r-1)

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int f[N][N];
char str[N];


int main()
{
    cin>>str;
    int n=strlen(str);

    //由于是区间dp,所以最外层循环长度
    for(int len=1;len<=n;len++)
    {
        for(int l=0;l+len-1<n;l++)
        {
            int r=l+len-1;//计算右边界
            if(len==1) f[l][r]=1;//特殊情况
            else
            {
                if(str[l]==str[r]) f[l][r]=f[l+1][r-1]+2;
                f[l][r]=max(f[l][r],f[l+1][r]);
                f[l][r]=max(f[l][r],f[l][r-1]);
                f[l][r]=max(f[l][r],f[l+1][r-1]);
            }
        }
    }
    cout<<n-f[0][n-1]<<endl;
    return 0;
}

类型四:最长上升子序列问题

参考例题1: 最长上升子序列
思路:本题要求的是给定一个数列,求其中严格单调递增的子序列长度最大是多少,可以将dp的状态看成是以每一个数字结尾的最长子序列的长度
状态方程:f[i]表示以第i个数字结尾的最长上升子序列的长度,这样的话就可以进行状态的转换了,如果在i之前的某个数字num[j]是小于num[i]
的话,那么f[i]=f[j]+1,即f[i]这个状态可以是 f[j]的长度+1,1即为num[i]本身这个数字的长度,所以状态计算就是f[i]=max(f[j]+1,f[i]) if(num[j]<num[i])

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=1000+5;
int num[N],f[N],n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>num[i];

    for(int i=0;i<n;i++)
    {
        f[i]=1;//若没有比 num[i]小的,则它长度为1
        for(int j=0;j<i;j++)
        {
            if(num[j]<num[i])
            {
                f[i]=max(f[j]+1,f[i]);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=max(res,f[i]);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1217. 垒骰子

洋宝
1个月前
// 骰子这道题,线性dp的话复杂度为O(n),这个数据量想要完全过掉显然是不可能滴
//所以采取的做法是 dp与矩阵快速幂相结合的做法

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=6;
const int MOD=1e9+7;
typedef long long LL;
//为了方便处理,对骰子数做一个映射
int op[N]={3,4,5,0,1,2};//分别存放第i位对应的数字
int n,m;
//先把两个矩阵运算的函数码一下
bool st[N][N];//用于记录两个数字是否互斥
void mul(int c[],int a[], int b[][N])
{
    // a 和 b的计算结果存到c里面
    int temp[N]={0};

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%MOD;
        }
    }
    memcpy(c,temp,sizeof(temp));
}

void mul(int c[][N],int a[][N], int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%MOD;
            }
        }
    }
    memcpy(c,temp,sizeof(temp));
}

int main()
{
    cin>>n>>m;
    int k,c;
    for(int i=0;i<m;i++)
    {
        cin>>k>>c;
        k--,c--;
        st[k][c]=st[c][k]=true;
    }
    int f1[N]={4,4,4,4,4,4};
    int a[N][N];
    //memset(a,4,sizeof(a));
    //接下来处理一下a矩阵,使得互斥数字置为0,方便后续运算
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(st[i][op[j]]) a[i][j]=0;
            else a[i][j]=4;
        }

    }
    n--;
    //快速幂
    while(n)
    {
        if(n&1) mul(f1,f1,a);
        mul(a,a,a);
        n=n>>1;
    }
    int res=0;
    for(int i=0;i<N;i++)
    res=(res+f1[i])%MOD;

    cout<<res<<endl;
    return 0;

}



洋宝
1个月前
// 骰子这道题,线性dp的话复杂度为O(n),这个数据量想要完全过掉显然是不可能滴
//所以采取的做法是 dp与矩阵快速幂相结合的做法

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=6;
const int MOD=1e9+7;
typedef long long LL;
//为了方便处理,对骰子数做一个映射
int op[N]={3,4,5,0,1,2};//分别存放第i位对应的数字
int n,m;
//先把两个矩阵运算的函数码一下
bool st[N][N];//用于记录两个数字是否互斥
void mul(int c[],int a[], int b[][N])
{
    // a 和 b的计算结果存到c里面
    int temp[N]={0};

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%MOD;
        }
    }
    memcpy(c,temp,sizeof(temp));
}

void mul(int c[][N],int a[][N], int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%MOD;
            }
        }
    }
    memcpy(c,temp,sizeof(temp));
}

int main()
{
    cin>>n>>m;
    int k,c;
    for(int i=0;i<m;i++)
    {
        cin>>k>>c;
        k--,c--;
        st[k][c]=st[c][k]=true;
    }
    int f1[N]={4,4,4,4,4,4};
    int a[N][N];
    //memset(a,4,sizeof(a));
    //接下来处理一下a矩阵,使得互斥数字置为0,方便后续运算
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(st[i][op[j]]) a[i][j]=0;
            else a[i][j]=4;
        }

    }
    n--;
    //快速幂
    while(n)
    {
        if(n&1) mul(f1,f1,a);
        mul(a,a,a);
        n=n>>1;
    }
    int res=0;
    for(int i=0;i<N;i++)
    res=(res+f1[i])%MOD;

    cout<<res<<endl;
    return 0;

}



洋宝
1个月前
//由于数据量过大,所以我们采取矩阵+快速幂的形式计算
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=3;
//由于数据量大,怕爆int,所以用 longlong
typedef long long LL;
int n,m;
void mul(int c[],int a[], int b[][N])
{
    //计算 a 与b的乘积,并且赋值给c
    int temp[N]={0};
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
        }
    }
    memcpy(c,temp,sizeof(temp));
}

void mul(int c[][N], int a[][N], int b[][N])
{
    //用于计算 a与 b矩阵相乘,并且将值赋给c 
    int temp[N][N]={0};

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
            }
        }
    }
    memcpy(c,temp,sizeof(temp));

}

int main()
{
    cin>>n>>m;
    int f1[N]={1,1,1};//f1矩阵,里面分别是 f1,f2,s1
    int a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };//这是已经手算出来的a矩阵
    n--;
    //快速幂
    while(n)
    {
        if(n&1) mul(f1,f1,a);
        mul(a,a,a);
        n=n>>1;
    }
    cout<<f1[2]<<endl;
    return 0;
}