头像

腾杨天下

腾杨集团




离线:3小时前


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

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int a[N],w[N][N];
int f[N][N];
int n,k,m;
int main()
{
    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<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    for(int i=2;i<=m;i++)
    {
        for(int j=0;j<=k;j++)
        {
            for(int l=1;l<i;l++)
            {
                if(j>=i-l-1)f[i][j]=max(f[i][j],f[l][j-(i-l-1)]+w[a[l]][a[i]]);
            }
        }
    }
    int maxx=0;
    for(int i=0;i<=k;i++)
    {
        maxx=max(maxx,f[m][i]);
    }
    cout<<maxx;
    return 0;
}


活动打卡代码 AcWing 3502. 不同路径数

思路

简单来说就是dfs存到set里面,最后输出一下set里面的元素个数就可以了

代码

#include<bits/stdc++.h>
using namespace std;
int cnt;
int a[100][100];
int n,m,k;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
set<int> b;
void cal(int x,int y,int step,int num)
{
    num=num*10+a[x][y];
    if(step==k)
    {
        b.insert(num);
        return;
    }
    for(int i=0;i<4;i++)
    {
        if(x+dx[i]<1||x+dx[i]>n||y+dy[i]<1||y+dy[i]>m)continue;
        cal(x+dx[i],y+dy[i],step+1,num);
    }

}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cal(i,j,0,0);
        }
    }
    for(auto l:b)
    {
        cnt++;
    }
    cout<<cnt;
    return 0;
}



思路

简单来说就是dfs存到set里面,最后输出一下set里面的元素个数就可以了

代码

#include<bits/stdc++.h>
using namespace std;
int cnt;
int a[100][100];
int n,m,k;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
set<int> b;
void cal(int x,int y,int step,int num)
{
    num=num*10+a[x][y];
    if(step==k)
    {
        b.insert(num);
        return;
    }
    for(int i=0;i<4;i++)
    {
        if(x+dx[i]<1||x+dx[i]>n||y+dy[i]<1||y+dy[i]>m)continue;
        cal(x+dx[i],y+dy[i],step+1,num);
    }

}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cal(i,j,0,0);
        }
    }
    for(auto l:b)
    {
        cnt++;
    }
    cout<<cnt;
    return 0;
}



思路

先用sum来代表所有st[i]==1的a[i]加起来
前缀和稍微处理一下就可以了,如果st[i]==1则前缀和s[i]=s[i-1],否则s[i]=s[i-1]+a[i],然后用一个maxx一组组的去比哪个s[i+k-1]-s[i-1]最大,然后输出sum+maxx

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
long long a[N],st[N],n,k,s[N];
long long sum;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i];
        s[i]=s[i-1];
        if(st[i])sum+=a[i];        
        else s[i]+=a[i];
    }
    long long maxx=0;
    for(int i=1;i+k-1<=n;i++)
    {
        long long temp=s[i+k-1]-s[i-1];
        if(temp>maxx)maxx=temp;
    }
    cout<<sum+maxx;
    return 0;
}


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

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
long long a[N],st[N],n,k,s[N];
long long sum;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i];
        s[i]=s[i-1];
        if(st[i])sum+=a[i];        
        else s[i]+=a[i];
    }
    long long maxx=0;
    for(int i=1;i+k-1<=n;i++)
    {
        long long temp=s[i+k-1]-s[i-1];
        if(temp>maxx)maxx=temp;
    }
    cout<<sum+maxx;
    return 0;
}


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

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



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<int>temp;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root,0,sum);
        return ans;
    }
    void dfs(TreeNode* root,int s,int sum)
    {
        if(root==NULL)return;//很关键,没有这一行不给ac
        s+=root->val;
        temp.push_back(root->val);
        if(root->left==NULL&&root->right==NULL)
        {
            if(s==sum)ans.push_back(temp);
        }
        if(root->left)
        {
            dfs(root->left,s,sum);
        }
        if(root->right)
        {
            dfs(root->right,s,sum);
        }
        temp.pop_back();
    }
};



树的深度优先遍历

核心就是遍历左儿子右儿子,每一个节点都是一个struct,不同于以往的数组模拟链表,这样的struct链表更加好理解,但是用时较长,这一题偏向模板题,不卡常,所以没有问题。
左儿子有就遍历进去左儿(if(root->left)dfs(root->left,s,sum)),右儿子有就遍历进去右儿子(if(root->right)dfs(root->right,s,sum))
注意在搜索的时候如果根节点是空节点则直接返回就可以了,因为后面的对空节点取权值(val)等操作都做不了了,自然也就段错误了,所以我们要避免这种情况,(if(root==NULL)return)这样的话就可以呃在 [NULL] 0的情况下ac了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<int>temp;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root,0,sum);
        return ans;
    }
    void dfs(TreeNode* root,int s,int sum)
    {
        if(root==NULL)return;//很关键,没有这一行不给ac
        s+=root->val;
        temp.push_back(root->val);
        if(root->left==NULL&&root->right==NULL)
        {
            if(s==sum)ans.push_back(temp);
        }
        if(root->left)
        {
            dfs(root->left,s,sum);
        }
        if(root->right)
        {
            dfs(root->right,s,sum);
        }
        temp.pop_back();
    }
};



class Solution {
public:
    int cal(int x,vector<int>& weights)
    {
        int cnt=1;
        int d=0;
        for(auto i:weights)
        {
            if(i>x)return 1e6;
            if(i+d<=x)
            {
                d+=i;
            }
            else
            {
                d=0;
                cnt++;
                d+=i;
            }
        }
        return cnt;
    }
    int shipWithinDays(vector<int>& weights, int D)
    {

        int l=1,r=500000;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(cal(mid,weights)>D)l=mid+1;
            else r=mid;
        }

        return l;
    }
};


活动打卡代码 AcWing 680. 剪绳子

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int l[N];
int maxx;
int cal(double x)
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        cnt+=(int)(((double)l[i])/x);
    }
    return cnt;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i];
        maxx=max(maxx,l[i]);
    }
    double l1=0.1,r=1e9;
    while(l1<r-0.00001)
    {
        double mid=(l1+r)/2;
        if(cal(mid)<m)r=mid;
        else l1=mid;
    }
    printf("%.2f",l1);
    return 0;
}