360Java开发笔经 21/03/28

选择题

好多 数据结构的题

编程题 两道

1. 两个数 进行或 求和
   longlong 二维暴力 可AC
   结果 做了一小时
   我是 是在想不出啥法子 最后才暴力
   过了 36好像 然后 试了下long long 就过了
   早知道就先 暴力试试 以后做题

   #include<iostream>
   #include<vector>
   using namespace std;
    long long c[20];
   int main(){
    int n;
    long long t;
    cin>>n;
    long long sum=0;
    vector<long long>v(n);
    for(int i=0;i<n;i++){
        cin>>t;
        v[i]=t;
        sum+=t;
        for(int j=0;j<i;j++){
            sum+=v[i]|v[j];
        }
    }
        cout<<sum<<endl;
    return 0;
   }

2. 感觉是背包
   第一题 以为很难 就先做的第二题
   第二题也没做上来
   用的 背包 创建 n*k+1 的数组
   然后 动态规划更新 好像是这么描述 我 描述的不对
   这个题有个限制 就是必须从 0 开始背包 我写的 从任意 开始背包
   然后 想 加一个 if 条件 过滤一下
   但是 时间不够我又紧张 没加上
   骗了 百分之 18

   #include<iostream>
   #include<vector>
   using namespace std;
   int main(){
    int n,m,k,a,b;
    cin>>n>>m>>k;
    vector<vector<int>>v(n,vector<int>(2));
    for(int i=0;i<n;i++){
        cin>>a>>b;
        v[i][0]=a;
        v[i][1]=b;
    }
    vector<vector<int>>ans(n,vector<int>(k+1));
    vector<vector<int>>vis(n,vector<int>(k+1));
    vis[0][0]=1;
    //for(int i=0;i<k+1;i++)ans[i][0]=-1;
    ans[0][0]=v[0][1];
    int mmax=v[0][1];
    for(int i=1;i<n;i++){
        int ta = v[i][0];// 下标 
        int tb = v[i][1];// 值
        for(int j=1;j<=k;j++){
            int t = i-1;
            while(t>=0&&v[i][0]-m<=v[t][0]){
                vis[i][j]=1;
                int pa = v[t][0];
                int pb = v[t][1];
                if(tb+ans[t][j-1]>ans[i][j]&&vis[t][j-1]){
                    ans[i][j]=tb+ans[t][j-1];
                    if(tb+ans[t][j-1]>mmax){
                        mmax=tb+ans[t][j-1];
                    }
                }
                t--;
            } 
   
        }
    }
    for(int j=0;j<k+1;j++){
        for(int i=0;i<n;i++){
            cout<<ans[i][j]<<" ";
        }cout<<endl;
    }
    cout<<mmax<<endl;
    return 0;
   }