头像

英特耐雄纳尔




离线:11小时前


最近来访(3)
用户头像
qujunyi
用户头像
汤泡饭627
用户头像
酒曲流苏


#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

typedef long long LL;   //靠近10e9的统统用LL

unordered_map<int, int> mp;
LL num;

bool isJudge(LL x)
{
    string str = to_string(x);
    for (int i = 0; i < str.size() - 1; i++)
    {
        if (str[i + 1] - str[i] != -1 && str[i + 1] - str[i] != 1)
        {
            return false;
        }
    }
    return true;
}

void dfs(int l)
{
    if (l > 9) return;
    if(l>1) mp[num] = 1;    //一层以上才算叠加

    int yushu = num % 10;
    num = num * 10 + yushu + 1;
    if (isJudge(num)) dfs(l + 1);
    num = (num-1 - yushu) /10;

    yushu = num % 10;
    num = num * 10 + yushu - 1;
    if (isJudge(num)) dfs(l + 1);
    num = (num + 1 - yushu) / 10;
}

int main()
{
    for (int i = 1; i <= 9; i++)
    {
        num = i;
        dfs(1); //从一位数开始,从i起源
    }
    int n,res=0;
    cin >> n;
    while (n--)
    {
        res = 0;
        int l, r;
        cin >> l >> r;
        for (auto t : mp)
        {
            if (t.first >= l && t.first <= r) res++;
        }
        cout << res << endl;
    }
}



10^5不是贪心,就是DP
A是贪心
B是最优
证明A<=B且A>=B
且B向贪心A的变化过程是不会变大的(缩小的)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int arr[N];

int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        scanf("%d", &arr[i]);
    }
    sort(arr,arr+n);
    int res=0;
    for(int i=0;i<n;i+=2)
    {
        res+=arr[i+1]-arr[i];
    }
    cout<<res;
}

sugar
休息一下吧



活动打卡代码 AcWing 3580. 整数配对

10^5不是贪心,就是DP
A是贪心
B是最优
证明A<=B且A>=B
且B向贪心A的变化过程是不会变大的(缩小的)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int arr[N];

int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        scanf("%d", &arr[i]);
    }
    sort(arr,arr+n);
    int res=0;
    for(int i=0;i<n;i+=2)
    {
        res+=arr[i+1]-arr[i];
    }
    cout<<res;
}



要求字典序最小,每次都要问第i件物品选不选,如果选,就是选;如果不选,就从i+1(之后一个)转移过来,这是一个。。。
可是为什么要从大到小遍历呢?

// f[i][j]表示第i件物品以后选,体积不超过j的价值最大值
// 所以要从n开始倒着
// 才能求最小方案时正着推
// f[i][j]=max(f[i+1][j],f[i+1][j-v[i]+w[i])

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N][N];
int v[N],w[N];
int n,V;

int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=V;j++)
        {
            f[i][j]=f[i+1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    }

    int cur_v=V;
    for(int i=1;i<=n;i++)   //从第一个物品
    {
        if(cur_v>=v[i] && f[i+1][cur_v-v[i]]+w[i]>=f[i+1][cur_v])
        {
            printf("%d ",i);
            cur_v-=v[i];
        }
    }

}

学习累了放松一下吧

嘻嘻




// 堆的做法:
// 集合的大小是k,每次会插入n个数,所以nlogk
// 堆顶是最大的数,如果新来的数很大,那么插入堆之后删除的也是他,如果新来的小,那么就会删除掉最大的数



class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for(auto c:input)
        {
            heap.push(c);
            if(heap.size()>k) heap.pop();
        }
        vector<int> res;
        while(heap.size()) res.push_back(heap.top()),heap.pop();
        reverse(res.begin(),res.end());
        return res;
    }
};



二叉搜索树的性质:中序遍历是有序的
于是,将原数组排序,然后以中序的顺序放置到树中
层序遍历输出结果即可



#include<bits/stdc++.h>
using namespace std;

const int N = 110;
typedef struct Node{
    int val;
    int left;   //左右表示编号
    int right;
};  //这里有分号才表示结构体定义完毕
Node tree[N];


int arr[N];
int n;
int cnt;

void dfs(int u)     //u
{
    if(u==-1) return;
    dfs(tree[u].left);
    tree[u].val=arr[cnt++];
    dfs(tree[u].right);
}

void bfs()
{
    queue<Node> q;
    q.push(tree[0]);
    while(q.size())
    {
        auto t=q.front();    //q.front访问队首
        q.pop();
        cout<<t.val<<' ';
        if(t.left!=-1) q.push(tree[t.left]);
        if(t.right!=-1) q.push(tree[t.right]);
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        tree[i].left=l; //输入是按照编号0 1 2 3...顺序来的,尽管层序并不是这个顺序
        tree[i].right=r;
    }
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    dfs(0);
    bfs();
    return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>


using namespace std;

const int N = 110;

struct Node{
  int val;  
    int left;
    int right;
};
int n;
Node tree[N];
int arr[N];
int cnt;

void dfs(int u)
{
    if(u==-1) return;

    dfs(tree[u].left);
    tree[u].val=arr[cnt++];
    dfs(tree[u].right);
}

void bfs()  //层序遍历就是bfs
{
    queue<Node> q;
    q.push(tree[0]);
    while(q.size())
    {
        Node t=q.front();
        q.pop();
        cout<<t.val<<' ';
        if(t.left!=-1) q.push(tree[t.left]);
        if(t.right!=-1) q.push(tree[t.right]);
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        tree[i].left=x;
        tree[i].right=y;
    }
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    dfs(0);
    bfs();
    return 0;
}



环形DP
f[i][j]表示已经传了i次,落到编号为j的小朋友的所有传球可能数
状态数量 NM 转移O(1)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 35;

int n,m;
int f[N][N];    //f[i][j]表示已经传了i次,落到编号为j的小朋友的所有传球可能数

int main()
{
    cin>>n>>m;
    f[0][0]=1;  //一次没传,落在小蛮手上为一种
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<n;j++)
        {
            f[i][j]=f[i-1][(j-1+n)%n]+f[i-1][(j+1)%n];
        }
    }
    cout<<f[m][0];
}





// 容易观察出2的32次方用long long来存足够,也就是先转LL再转为二进制输出
// 转二进制输出只要枚举每一位与 1 与即可



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

void out(LL x)
{
    string res;
    for(int i=32;i>=0;i--)  //+3最多有33位
    {
        int v=x>>i&1;
        if(v==0 && i==32) continue;  //结果可能是33位
        cout<<v;
        //res+=to_string(v);
    }
    puts("");
   // cout<<res<<endl;
}

int main()
{
    cin>>n;
    while (n -- )
    {
        string s;
        cin>>s;
        LL x=0; //局部变量要赋初值
        for(auto c:s) x=x*2+c-'0';  //二进制转化为十进制的写法
        out(x+1);
        out(x+3);
    }
    return 0;
}


活动打卡代码 AcWing 3554. 二进制

// 容易观察出2的32次方用long long来存足够,也就是先转LL再转为二进制输出
// 转二进制输出只要枚举每一位与 1 与即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

void out(LL x)
{
    string res;
    for(int i=32;i>=0;i--)  //+3最多有33位
    {
        int v=x>>i&1;
        if(v==0 && i==32) continue;  //结果可能是33位
        cout<<v;
        //res+=to_string(v);
    }
    puts("");
   // cout<<res<<endl;
}

int main()
{
    cin>>n;
    while (n -- )
    {
        string s;
        cin>>s;
        LL x=0; //局部变量要赋初值
        for(auto c:s) x=x*2+c-'0';  //二进制转化为十进制的写法
        out(x+1);
        out(x+3);
    }
    return 0;
}



// 递归真的太巧妙了
// 数最大20000,最多2的十四次方,是2的多少次幂的和就是看移位的过程中有多少位为1



#include <iostream>
#include <cstring>
#include <algorithm>
#include<string>

using namespace std;

const int N = 20010;

int n;

string dfs(int n)
{
    string res;
    for(int i=14;i>=0;i--)  //是2的多少次幂的和就是看移位的过程中有多少位为1
    {
        if(n>>i&1)
        {
            if(res.size()) res+="+";
            if(i==0) res+="2(0)";
            else if(i==1) res+="2";
            else if(i==2) res+="2(2)";
            else res+="2("+dfs(i)+")";
        }
    }
    return res;
}

int main()
{
    while(cin>>n)
    {
        cout<<dfs(n)<<endl;
    }
    return 0;
}