头像

水羊




离线:23小时前


最近来访(26)
用户头像
Whalefall.
用户头像
小赵不废
用户头像
迟遇_1
用户头像
Sou1Power
用户头像
xzx_123
用户头像
zheside
用户头像
清风飘扬
用户头像
Carry_On
用户头像
拂拂晓_4
用户头像
ZzzzH777
用户头像
可是接受自己的平庸好难啊
用户头像
brilliant.
用户头像
哇每秒都想吃夕瓜
用户头像
微雨双飞燕
用户头像
Judy_ccc
用户头像
._5910
用户头像
zz哲
用户头像
种花家的虎式坦克
用户头像
bi_nian
用户头像
纳西索斯


水羊
1天前
首先这个题目我是怎么写的我就简单说一说
全是抄的,nnd,一点也不会写,md真该死呜呜呜呜


#include<bits/stdc++.h>
using namespace std;

const int N=12;
const int M=1<<N;
long long f[N][M];
bool st[M];
int n,m;

int main()
{
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<1<<n;i++)
        {
            st[i]=true;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        st[i]=false;
                        break;
                    }
                }
                else cnt++;
            }
            if(cnt&1) st[i]=false;
        }
        memset(f,0,sizeof f);

        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            {
                for(int k=0;k<1<<n;k++)
                {
                    if((j&k)==0&&st[j|k])
                    {
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
    cout<<f[m][0]<<endl;


    }


    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 901. 滑雪

水羊
1天前

这个记忆化搜索确实有点牛皮,确实不简单,这个思路感觉确实厉害,不得不说,明天再刷一遍


#include<bits/stdc++.h>
using namespace std;

const int N=310;
int n,m;
int g[N][N],f[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int dp(int x,int y)
{
    if(f[x][y]) return f[x][y];

    f[x][y]=1;

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&g[a][b]<g[x][y])
        f[x][y]=max(f[x][y],dp(a,b)+1);
    }
    return f[x][y];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];

    // memset(f,-1,sizeof f);

    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            res=max(res,dp(i,j));
        }
    }

    cout<<res<<endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



水羊
2天前

树状dp我感觉这种题目的精髓在于使用好
1.邻接表
2.各种搜索,例如dfs,bfs等等,ok,加油吧!!!

第二遍写的时候已经算是差不多了,但是动态规划所用到的算法还是有点难度的,建议以后多来几遍

#include<bits/stdc++.h>
using namespace std;

const int N=6000+10;
int happy[N];
int f[N][2];
int e[N],ne[N],h[N],idx;
bool father[N];
int n;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    f[u][1]=happy[u];

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];//f[N][2]并不是单单对于选不选
                        //而是对于他的快乐能否给加上。
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];

    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        father[a]=true;
        add(b,a);
    }

    int root=1;
    while(father[root]) root=root+1;

    dfs(root);

    cout<<max(f[root][0],f[root][1])<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 803. 区间合并

水羊
2天前
怎末说呢,区间合并这个题目是很容易就能懂得,但是他这个题目吧
感觉不会写的最大原因就是因为vector以及pair根本不想去想

第二遍写完这个题目简单说一下感想吧,第二遍思路是有的卡在了auto这四个字母上边
害,还是不熟悉,只希望以后不要考这玩意就行了,md


#include<bits/stdc++.h>
#include<vector>
using namespace std;

typedef pair<int,int> PII;
vector<PII> nums,res;

int main()
{
    int n;
    int l=-(1e9+10);
    int r=l;
    cin>>n;

    while(n--)
    {
        int x,y;
        cin>>x>>y;
        nums.push_back({x,y});
    }

    sort(nums.begin(),nums.end());

    for(auto num:nums)
    {
        if(r<num.first)
        {
            res.push_back({l,r});
            l=num.first;
            r=num.second;
        }
        else if(r<num.second)
        {
            r=num.second;
        }
    }

    res.push_back({l,r});
    cout<<res.size()-1<<endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2816. 判断子序列

水羊
2天前
这个题目是有点可惜,我虽然有思路过13个测试点,但是思路还是不够简介
md,这种题目一定要把分给拿了,要不然太亏了


#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int a[N],b[N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++) cin>>b[j];

    int i,j;

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

    if(i==n+1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 798. 差分矩阵

水羊
2天前

我承认这是我第n次写这个题解,这次必须记住,md,再记不住,我直接写题目写到四


思路:
一共用到连个数组a,b,a是用来存用起始数组的,而b是用来存用差分数组的,
所以这就比较厉害了,差分数组有点像前缀和,只不过差分的话是用前缀和求某一项
但是我不是很建议用前缀和的思想去理解,因为,你绝对会迷茫的,反之我们利用前缀和的
变相思想,把前缀的累加思想给学到,也就是insert函数的精髓,b是用来存前后上下和左上角以及自身的数,
并且也存有需要变化的数,通过a数组累加给加上,卧槽
不讲了,md又迷了,哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇哇!!!


#include<bits/stdc++.h>
using namespace std;

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

void insert(int x1,int y1,int x2,int y2,int k)
{
    b[x1][y1]+=k;
    b[x2+1][y2+1]+=k;
    b[x1][y2+1]-=k;
    b[x2+1][y1]-=k;
}

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);
        }
    }

    while(q--)
    {
        int x1,x2,y1,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        insert(x1,y1,x2,y2,k);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 797. 差分

水羊
3天前
我的评价是差分他就是利用好关系,尽量被让太多的数被牵扯到

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int a[N];
int n,m,l,r,k;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(int i=n;i>=1;i--) a[i]=a[i]-a[i-1];//主要是这一步是精髓

    while(m--)
    {
        cin>>l>>r>>k;
        a[l]+=k;
        a[r+1]-=k;
    }

    for(int i=1;i<=n;i++)
    {
        a[i]=a[i]+a[i-1];
        cout<<a[i]<<' ';
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 796. 子矩阵的和

水羊
3天前
#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int a[N][N];
int n,m,q;

int find(int x1,int y1,int x2,int y2)
{
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

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

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int x1,x2,y1,y2;
    while(q--)
    {
        cin>>x1>>y1>>x2>>y2;
        cout<<find(x1,y1,x2,y2)<<endl;
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 795. 前缀和

水羊
3天前



#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N];
int n,m;
int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=a[i]+a[i-1];
    }

    while(m--)
    {a
        int l,r;
        cin>>l>>r;
        cout<<a[r]-a[l-1]<<endl;
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



水羊
4天前

首先我先展示我的代码


#include<bits/stdc++.h>
using namespace std;

const int N=1010;
const int mod=1e9+7;
int f[N][N];//前i,总和j
int n;

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

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

    return 0;
}

/首先我们能分析出这是一个是完全背包问题,同样的数可以选好多次,所以如果是把f[i][j-i]替换成f[i-1][j-i]的话相当于第i个数只能选一次,不符合和条件/
但是f[i][j-i]又该如何理解呢,我们可以认为是在遍历第i个数的时候,我们通过双重循环遍历背包容量j,不断把i装入j内,最后得到能装下i的几种情况。(感觉说的有点勉强,大家有什么好的观点也请发表一下,谢谢了)