一个数分成几份，可以被 3 整除的最大份数。比如 12345 分成12 3 45 结果为3.

思路： 从前向后扫描，贪心： 遇到符合要求的继续下去。

• m 记录前后几个数相加之和，最大不超过3 （111 222）, c1 c2 记录单位被 3 除余1 余2 的情况， m>0 && m%3==0 || c1 >1 && c2 >2 归位

• 某个数可以被 3 整除 continue

作者：泫
链接：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
来源：牛客网

#include <bits/stdc++.h>

using namespace std;

int main() {
    //freopen("../in.txt", "r", stdin);
    string str;
    cin >> str;
    int i, len = str.length(), m, number, ans = 0, c1, c2;
    for (i = 0, m = 0, c1 = 0, c2 = 0; i < len; i++) {
        number = str[i] - '0';
        //遇到3的情况直接加1
        if (number % 3 == 0) {
            ans++;
            m = 0, c1 = 0, c2 = 0;
            continue;
        }
        m += number;
        if (number % 3 == 1)
            c1++;
        else
            c2++;
        //判断能不能有一个组合
        if ((m > 0 && m % 3 == 0) || (c1 > 0 && c2 > 0)) {
            ans++;
            m = 0, c1 = 0, c2 = 0;
        }
    }
    cout << ans << endl;
}

x + y = x|y 给定x, 求满足要求的第 k 个 y

思路: 位运算。把 k 的所有位从低到高填充到 x 对应为0的位上。

比如 x = 2 =0b10

k = 1 = 0b1 , y = 0b01

k = 2 = 0b10 , y = 0b100(加粗的1是因为要跳过x对应的1)

仔细想一下就知道为什么了。

作者：泫
链接：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
来源：牛客网

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int main() {
    //freopen("../in.txt", "r", stdin);
    ll t,x,k,ans,i,j,a,lenX,lenK,lenA;
    int posX[160],posK[160],posA[160];
    cin>>t;
    while (t--){
        memset(posX,0, sizeof(posX));
        cin>>x>>k;
        i=0,ans=0;
        while (x>0){
            posX[i++]=x&1;
            x=x>>1;
        }
        lenX=i;

        i=0;
        while (k>0){
            posK[i++]=k&1;
            k=k>>1;
        }
        lenK=i;

        for(i=0,j=0,a=0;j<lenK;i++){
            if(posX[i]==0)
                posA[a++]=posK[j++];
            else
                posA[a++]=0;
        }
        lenA=a;
        for(i=lenA-1;i>=0;i--){
            ans=ans<<1;
            ans=ans|posA[i];
        }
        cout<<ans<<endl;
    }
}

自己的代码（丑）

# coding=utf-8
import sys



if __name__ == "__main__":
    n = sys.stdin.readline().strip()

    for i in range(int(n)):
        x, k = list(map(int, sys.stdin.readline().strip().split()))
        x_bin = bin(x)[2:]
        x_bin_len = len(x_bin)
        x_bin_reverse = [i for i in x_bin][::-1]

        k_bin = bin(k)[2:]

        res = []
        x_index = 0
        for k_i in k_bin[::-1]:
            while x_index <= x_bin_len-1 and x_bin_reverse[x_index]== "1":
                res.append(0)
                x_index += 1

            res.append(k_i)
            x_index += 1

        num = "".join(list(map(str, res[::-1])))
        print(int(num, 2))

给定数组[1-9] 和 boll_array[01111110], 0表示可以不输出， 1必须输出对应位，输出所有可能情况（字符串升序）

这道题不是很会，暴力递归 ac 了50多的用例。后来想了想感觉可以求多个数组的笛卡尔集。

下面是别人的ac代码。

作者：whlprogram
链接：https://www.nowcoder.com/discuss/100047?type=2&order=0&pos=7&page=1
来源：牛客网

#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/100031?type=2&order=0&pos=7&page=1
来源：牛客网

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int a[10]={0,1,2,3,4,5,6,7,8,9};
int pos[10],i,p[10];
set<string> v;

void Print(){
    string s="";
    for(i=0;i<10;i++){
        if(p[i]==1)
            s+=a[i]+'0';
//            cout<<a[i];
    }
    v.insert(s);
    //    cout<<s<<endl;
}

int main() {
//    freopen("../in.txt", "r", stdin);
    for(i=0;i<10;i++)
        cin>>pos[i];

    int add = 0,tmp;
    while (1){
        int flag=0;
        for(i=9;i>=0;i--){
            if(p[i]==0){
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
        //打印
        tmp=add++;
        for(i=9;i>=0;i--){
            p[i]=pos[i];
            if(pos[i]==0){
                p[i]=tmp&1;
                tmp=tmp/2;
            }
        }
        Print();
    }
    set<string>::iterator it;
    for(it=v.begin();it!=v.end();it++){
        cout<<*it<<endl;
    }
}

求期望。

n 面筛子，m面有奖，有奖继续掷筛子，没奖结束。

输入给定 score 数组 s_array, len(s_array) == n， 求期望。

数学题, e =

• ave_score = sum(s_array)/n

• (n-m)/n * avg_score (第一次就没奖)+
• m/n * (score + e) (第一次有奖，相当于从头开始)

化简得到 e = sum(s_array)/n-m

最大上升子序列和， 动态规划

题目和思路见 https://blog.csdn.net/sjf0115/article/details/8715586， 贴下大佬的代码

作者：whlprogram
链接：https://www.nowcoder.com/discuss/100047?type=2&order=0&pos=7&page=1
来源：牛客网

#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;
}