(1)求和
用 f(x) 来表示满足下列条件的最小正整数 a：

a≥x。
a 的各个数位不包含除了 4 和 7 以外的其他数字。
现在，给定两个整数 l,r(l≤r)，请你计算 f(l)+f(l+1)+…+f(r) 的值。

输入格式
一行，两个整数 l,r。

输出格式
一行，一个整数表示求得的和。

数据范围
前三个测试点满足 1≤l≤r≤10，
所有测试点满足 1≤l≤r≤109。

输入样例1：
2 7
输出样例1：
33
输入样例2：
7 7
输出样例2：
7
代码

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long LL;

//r最大为10的9次方,所以最大为十个4,十位
vector<LL> q;

void dfs(int u,LL a)
{
    q.push_back(a);
    if(u==10)return;
    dfs(u+1,a*10+4);
    dfs(u+1,a*10+7);
}

int main()
{
    dfs(0,0);
    sort(q.begin(),q.end());

    LL l,r;
    cin>>l>>r;

    LL res=0;

    for(int i=1;i<q.size();i++)
    {
        LL a=q[i-1]+1,b=q[i];
        res+=b*max(0ll,min(r,b)-max(l,a)+1);
    }
    cout<<res;
    return 0;
}

01数
如果一个正整数，其各个数位上的数字均满足要么是 0，要么是 1，则称该数字为 01 数。

例如，1 和 10 都是 01 数。

给定一个整数 n。

请你计算，1∼n 中有多少个 01 数。

输入格式
一行，一个整数 n。

输出格式
一个整数，表示 01 数的数量。

数据范围
前六个测试点满足 1≤n≤100。
所有测试点满足 1≤n≤109。

输入样例：
10
输出样例：
2
代码

#include <bits/stdc++.h>

using namespace std;

int n;
int res;

void dfs(int k)
{
    if ( k > n ) return ;
    dfs(k * 10);
    dfs(k * 10 + 1);
    res ++ ;
}

int main()
{
    cin >> n;
    dfs(1);
    cout << res;
    return 0;
}

(2)锦标赛
链接：https://ac.nowcoder.com/acm/problem/13223
来源：牛客网

组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？
输入描述:
第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。
输出描述:
小美最多参赛的轮次。
示例1
输入
复制
4
4 1 2 3
输出
复制
2
代码

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<21);
int a[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int cnt1=0,cnt2=0;
    for(int i=2;i<=n;i++) 
    {
        if(a[i]>a[1]) cnt1++;
        else          cnt2++;
    }
    //总有一个会单出来.不是cnt1就是cnt2.
    int ans=0;
    while(cnt2>1)
    {
        cnt2/=2;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

(3)健康的荷斯坦奶牛
农夫约翰以拥有世界上最健康的奶牛而感到自豪。

奶牛想要保持健康，每天就要补充足量的多种维生素。

约翰为奶牛们准备了多种牛饲料，每种牛饲料中都富含奶牛所需的多种维生素，但是每种维生素的具体含量可能并不相同。

每种牛饲料每天最多只能喂给奶牛们一勺，也就是说每种饲料可以选择不喂给奶牛，或喂给奶牛一勺的量。

现在给定所有饲料的每种维生素的（每勺）具体含量，以及奶牛对于每种维生素的每日最低需求量。

请你求出，保证奶牛各种维生素的每日摄入量达标的情况下，最少需要喂给奶牛多少勺饲料。

数据保证有解。

输入格式
第一行包含一个整数 V，表示共有 V 种所需维生素，编号 1∼V。

第二行包含 V 个不超过 1000 的正整数，其中第 i 个数表示第 i 号维生素的奶牛每日最低需求量。

第三行包含整数 G，表示牛饲料的种类数。

接下来 G 行，每行包含 V 个不超过 1000 的非负整数，其中第 i 个数表示一种饲料中第 i 号维生素的含量（每勺）。

输出格式
共一行，首先输出一个整数 S，表示最少需要喂给奶牛的饲料数量，接下来输出 S 个升序排列的整数，表示喂给奶牛的饲料的具体编号。

当存在多个解时，输出序列字典序最小的那个解。

数据范围
1≤V≤25,
1≤G≤15
输入样例：
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399
输出样例：
2 1 3
代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 25;

int n, m;
int need[N], s[N][N], sum[N];
vector<int> res, t;

//对每一种选出来的方案t进行判断
bool check()
{
    memset(sum, 0, sizeof sum);
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < t.size(); j++)
            sum[i] += s[t[j]][i];
        if(sum[i] < need[i]) return false;
    }

    if(res.empty() || res.size() > t.size() || (res.size() == t.size() && res > t))
        return true;

    return false;
}

void dfs(int u)
{
    if(u == n)
    {
        if(check()) res = t;
        return;
    }

    //选择u这行
    t.push_back(u);
    dfs(u + 1);
    t.pop_back();

    //不选择u这行
    dfs(u + 1);
}

int main()
{
    cin >> m;
    for(int i = 0; i < m; i++) cin >> need[i];

    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> s[i][j];

    dfs(0);

    cout << res.size() << ' ';
    for(auto t : res) cout << t + 1 << ' ';

    return 0;
}

（4）循环数
循环数是一种没有重复数字且不含 0 并具有一些有趣性质的整数。

我们以 81362 为例：

如果从最左边的那个数字（在这里是 8）开始，向右数该数字位（当数到最右边的数字时，若还没有数完，则从左边第一位继续数），你将在一个新的数字处停下（如果没停在新数字上，则这个数不是循环数）。对于本例，从 8 开始右数 8 位：1 3 6 2 8 1 3 6，将停在 6 上。
在新停下的位置，继续重复上一个操作，也就是从 6 开始右数 6 位：2 8 1 3 6 2，将停在 2 上。
再次重复此操作，从 2 开始右数 2 位：8 1，将停在 1 上。
继续重复此操作，从 1 开始右数 1 位：3，将停在 3 上。
最后，从 3 开始右数 3 位：6 2 8，将停在 8 上。
循环数满足在所有的数字上均停留一次后，又能够回到出发点上。如果在所有的数字上均停留一次后，没有回到出发点，则这个数不是循环数。
给定一个数字 M，请你找到第一个比 M 大的循环数是多少。

输入格式
共一行，包含一个整数 M。

输出格式
输出一个整数，表示第一个比 M 大的循环数。

数据范围
1≤M≤107
输入样例：
81361
输出样例
81362
代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int m, ans = 1e9;
string path;
bool st[N], used[N];

bool check()
{
    memset(used,0,sizeof used);
    int n=path.size();
    int t=0; 
    int x;
    for(int i=0;i<path.size()-1;i++){//循环这么多次 
        x=path[t]-'0';
        t=(t+x)%n;          //字符串的每一位下标看是否出现过
        if(used[t])return false;
        used[t]=true;
    } 
        x=path[t]-'0';
        t=(t+x)%n;
        if(t!=0)return false;//特判最后一个数
   return true;
}
void dfs(int u)
{
    if (path.size()) {
        int t=stoi(path);
        if(check()&&t>m)ans=min(ans,t);
    }
    //暴力枚举所有方案合法的大概就是几十万种
    for (int i = 1; i <= 9; ++i){ 
        if(!st[i]){
        path += i+'0';
        st[i]=true;
        dfs(u + 1);
        path.pop_back();//回溯 
        st[i]=false;//回溯 
    }
   } 
}

int main()
{
    cin >> m;
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

（5）选择困难症
链接：https://ac.nowcoder.com/acm/problem/13594
来源：牛客网

题目描述
小L有严重的选择困难症。
早上起床后，需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。
小L想知道，有多少种方案，使得选出来的总喜欢值>M
需要注意，每类物品，至多选择1件，可以不选。

输入描述:
多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。
输出描述:
每组输出一行，表示方案数
示例1
输入
复制
2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2
输出
复制
3
8
代码

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e2+10;
ll a[maxn][maxn]={0};
ll n,m,cnt,ans;
int num[maxn];
void dfs(int t,int sum){
    if(t>n){
        return;
    }
    if(sum>ans){
        ll res=1;
        for(int i=t;i<n;i++)
            res*=(num[i]+1);    //如果已经符合条件了，则从第t类物品后面的几类可以随意选
        cnt+=res;
        return;
    }
    for(int j=0;j<num[t];j++)
        dfs(t+1,sum+a[t][j]);    //选
    dfs(t+1,sum);                //不选
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>ans){
        cnt=0;
        mst(a,0);
        for(int i=0;i<n;i++){
            cin>>num[i];
            for(int j=0;j<num[i];j++){
                cin>>a[i][j];
            }
        }
        dfs(0,0);
        cout<<cnt<<endl;
    }
    return 0;
}

(6)集合中的质数
链接：https://ac.nowcoder.com/acm/problem/14686
来源：牛客网

题目描述
给出一个集合和一个数m。

集合里面有n个质数。

请你求出从 1 到 m 的所有数中，至少能被集合中的一个数整除的数的个数。

输入描述:
第一行两个正整数 n 和 m 。
第二行n个正整数，分别为集合中的质数。
输出描述:
输出一个整数，表示符合要求的正整数的个数。
示例1
输入
复制
3 37
5 7 13
输出
复制
13
备注:
对于100%的数据，有n<=20，m为有符号64位正整数，集合内质数<=1000000000
代码

#include<iostream>
using namespace std;
typedef long long ll;
ll arr[25], n, m, ans;

//必须是x的倍数的数
void dfs(ll x, int start, int f) {
    if(x > m) return ;
    if(f & 1) ans += m/x;
    else ans -= m/x;
    for(int i = start+1; i <= n; i++) {
        dfs(x*arr[i], i, f+1);
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for(int i = 1; i <= n; i++) {
        dfs(arr[i], i, 1);
    }
    cout << ans << endl;
    return 0;
}

代码

#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long a[32];
int main()
{
    cin >> n >> m;
    long long res,ans = 0;
    long long fl = 0;
    for (int i = 0; i < n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < (1 << n);i++)//总共有2的n次方-1种情况，集合中的每个元素都有选和不被选的情况，
        //所以用01代表，没有000这种情况；
    {
        res = m,fl = 0;
        for (int j = 0; j < n;j++)
        {
            if((i >> j) & 1)
            {
                res /= a[j];
                fl++;
            }
        }

        if(fl % 2) ans += res;
        else ans -= res;
    }
    cout << ans;
}

（7）iko和她的糖
链接：https://ac.nowcoder.com/acm/problem/15891
来源：牛客网

题目描述
iko超级超级喜欢吃糖，有一天iko想出去玩，她计划从1点走到N点（按1,2,3，…，n的顺序走），每个点都有一个补给站，第i点的补给站有a[i]颗糖，从i点走到i+1点会消耗掉b[i]颗糖，iko在出游的途中可以选择三个补给站，iko想知道她走完全程到达N点时口袋里最多还能剩下几颗糖（初始时iko的口袋里一颗糖都没有）。

输入描述:
第一行输入N（3<=N<=1000）
第二行输入N个数代表a[1].......a[N] (0<=a[i]<=1000 )
第三行输入N-1个数代表b[1]......b[N-1] ( 0<=b[i]<=1000 )
输出描述:
输出一个数字表示iko到达n点时口袋里最多剩下的糖，
若不能到达N点输出-1。
示例1
输入
复制
3
1 3 4
3 4
输出
复制
-1
示例2
输入
复制
5
3 4 5 2 4
3 2 2 2
输出
复制
3
代码

#include<iostream>
using namespace std;
int a[1005], b[1005];
int ans = -1, n;
void dfs(int s, int cnt, int deep) {
    if (s < 0)
        return;
    if (cnt > 3)
        return;
    if (deep > n) {
        ans = max(s, ans);
        return;
    }
    dfs(s - b[deep], cnt, deep + 1);
    dfs(s - b[deep] + a[deep], cnt + 1, deep + 1);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        cin >> b[i];
    dfs(0, 0, 1);
    cout << ans << endl;
}