好未来 2019校园招聘 笔试编程题-2018.8.28

思路：
这道题应该用动态规划的，当时考虑的有问题，可能只是通过了样例才AC的
代码回头再修改
1. 遍历求字符和sum，遍历过程之中碰到3的倍数，最终结果res+1，sum重新计数
2. 单个字符如果是3的倍数（包括0），res+1，然后立刻sum重新计数

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

int main()
{
    vector<int> arr;
    string str;
    int res=0, sum=0;
    cin >> str;
    for(int i=0; i<str.size(); i++){
        if(str[i]<'0' || str[i]>'9')
            return 0;
        int temp = str[i]-'0';
        arr.push_back(temp);
    }

    for(int i=0; i<arr.size(); i++){
        sum += arr[i];
        if(arr[i]%3 == 0){
            res++;
            sum = 0;
            continue;
        }
        if(sum%3 == 0){
            res++;
            sum = 0;
        }
    }
    cout << res << endl;
    return 0;
}

点击查看参考链接
链接有一点儿写的错了，不过不影响查看
这道题暴力是不行的，通过二进制来演算一下。
假设数据x=5，k=1的时候，y=2，分别用二进制进行表示：
5D = 0101B
2D = 0010B
7D = 0111B
这里其实已经可以发现规律了。
只有在x（y）为0的比特位置，y(x)才能为1，不然相加是必然产生进位，不符合条件。因此x&y==0，此时的y才满足条件
x+y 是 把x和y每一个二进制位进行相加，1+1就进位
x|y 则是每个二进制位置对应的进行或运算（0|1=1 1|0=1 1|1=1）

这个题目中，x的值是固定的，也就是x的二进制数中1的位置和数目是固定的，所以进行或运算的时候，结果中y对应的位上都是0, 结果必有x+y=x|y。

考虑如何得到第k个
因为有上面的规律，我们可以得知，x中为1的位 对应 y中的位 必须为0。

这里就很简单了，我们只需要求出k的二进制值，并且把这个二进制的值从低位逐个填入x为0的位即可得到相加的结果。

如：5+2 = 5|2 = 7 k=1

5D = 0101B
1D = 0001B
我们把1的二进制填入至x的二进制为0的地方则能得到0111B，也就是十进制的7。7-5=2，就能得到y的值。

再举一个例子：x=5, k=2
5D = 0101B
2D = 0010B

把2的二进制从低位开始填入5的二进制数中为0的地方，即可得到1101B，也就是13，所以y=13-5=8。

实际上，我们只需要把1101B中和 x 对应为1的地方改为0，就能直接得到y的值，相当于减去x。

#include <iostream>

using namespace std;

void fun(long long x, long long k){
    long long y = 0, n =1;
    while(k > 0){
        if(x%2 != 0){//此时x的二进制最右端为1
            while(x%2 != 0){//一直使x右移，找到x的为0的位置
                n = n*2;  //每移一位，n记录一下变化的值
                x = x/2;
            }
        }
        //如果k的二进制最右端为1，就使y加上n
        if(k%2 != 0)
            y = y+n;
        n = n*2;
        x = x/2;
        k = k/2; //同时使x,k右移，以便下一步判断
    }
    cout << y;
}

int main() {
    long long t, x, k;
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> x >> k;
        fun(x, k);
        if(i != t-1)
            cout << ndl;
    }
    return 0;
}

暴力出奇迹

#include<cstdio>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<string> arr;
int main()
{
    int a[11];
    for(int i=0; i<10; i++)
        scanf("%d",&a[i]);
    for(int i=0; i<(1<<10); i++){
        int f=0;
        for(int j=0; j<10; j++)
            if(!((i&(1<<j)))&&a[j])
            {
                f=1;
                break;
            }
        if(f)
            continue;
        string str="";
        for(int j=0; j<10; j++)
            if(i&(1<<j))
                str.push_back('0' + j);
        arr.push_back(str);
    }
    sort(arr.begin(),arr.end());
    for(int i=0; i<arr.size(); i++)
        cout<<arr[i]<<endl;
    return 0;
}

链接：https://www.nowcoder.com/discuss/100078

链接：https://www.nowcoder.com/discuss/100094
数学题, e = ave_score
= (n-m)/n * avg_score + m/n * (score + e)
= 没奖 + 有奖
化简得到 e = sum(s_array)/n-m


思路：
动态规划
dp[i]表示从0到i位置子序列最大升序和

#include<stdio.h>
using namespace std;
int arr[100];
int maxSumIS( int arr[], int n )
{
    int i, j, max = 0;
    int dp[n];
    for ( i = 0; i < n; i++ )
        dp[i] = arr[i];
    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if ( arr[i] > arr[j] && dp[i] < dp[j] + arr[i])
                dp[i] = dp[j] + arr[i];
    for ( i = 0; i < n; i++ )
        if ( max < dp[i] )
            max = dp[i];

    return max;
}
int main()
{
    int temp=0, i=0;
    while(~scanf("%d", &temp)){
        arr[i] = temp;
        i++;
    }
    printf("%d\n", maxSumIS(arr, 100));
    return 0;
}

思路：
KMP算法