头像

邓等灯




离线:8小时前


最近来访(29)
用户头像
寰宇_9
用户头像
yxc的小迷妹1
用户头像
寻_39
用户头像
Richard-H
用户头像
loop
用户头像
wnllt@163.com
用户头像
yangxujing
用户头像
吴语峰
用户头像
123_34
用户头像
lmagawaujizane
用户头像
豪文
用户头像
K__8
用户头像
99_5_又菜又爱玩版
用户头像
努力刷leetcode
用户头像
我想吃饺子
用户头像
Hacker_King
用户头像
AcWing_Umbrella
用户头像
Msckf
用户头像
NJJ
用户头像
atsy


邓等灯
15小时前

问题
降次11.png

先通过平方和公式拆和凑得:
降次12.png

再立方和公式拼凑得:
降次13.png




问题:
同余1png.png

同余的四则运算,这里主要用到了加法和幂运算的,注意:除法是不满足的
(1) (a + b) % p = (a % p + b % p) % p
(2) (a - b) % p = (a % p - b % p) % p
(3) (a * b) % p = (a % p * b % p) % p
(4) a ^ b % p = ((a % p)^b) % p

步骤1:
同余3.png

由此可知,就按照1-10来分类即可

同余4.png

同余5.png

程序验证一下:

#include<iostream>
#include<cmath>

using namespace std;

int n;

int main(){
    cin>>n;
    int ans = 0;
    for(int i=1;i<=n;i++){
        ans = (ans + (int)pow((i%10),4)%10)%10;
    }
    cout<<ans<<endl;
    return 0;
}

输入:
2022
输出:
3




问题:100! 后面有多少个0

先正常的算:
阶乘11.png

程序:

因为只需要2,5. 所以求2,5的总的因子的个数即可
复杂度 O(nlogn)
代码如下

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int p2;
int p5;

void getNum(int x){
    while(x){
        if(x%2==0){
            x/=2;
            p2++;
        }else{
            break;
        }
    }
    while(x){
        if(x%5==0){
            x/=5;
            p5++;
        }else{
            break;
        }
    }
}

int main(){
    cin>>n;

    for(int i=1;i<=n;i++){
        getNum(i);
    }
    int ans = min(p2,p5);
    cout<<ans<<endl;
    return 0;
}

输入
100
输出:
24




题目:
递推函数2_1.png

直接 根据条件 直接递归算 即可
即自顶向下的算,把它当成一个递归函数,其退出条件为 n==1

即:

int func(int n){
    if(n==1){
        return 1;
    }
    return func(n/2)*(n/2);
}

计算过程如下:

递推函数2_2.png




输入:
第一行 n, 表示 n个非负整数
第二行,n 个数

输出:
这n个数排好序后的结果

基数排序的思路分析:
从个位开始,以各位数(0-9) 做为关键字进行分桶,然后再收集
重复这个动作,直至到最高位为止。最高位不够的填0处理

比如下面的这个用例:

10
434 22234 43 983 8 98 34 12 3 111

模拟一下:

第一阶段:
基数排序1.png

第二阶段:
基数排序2.png

第三阶段:
基数排序3.png

第四阶段:
基数排序4.png

第五阶段:
基数排序5.png

代码如下:

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

using namespace std;

vector<int> arr;
int n;

int getBits(int x){
    int res = 0;
    while (x)
    {
        res++;
        x/=10;
    }
    return res;
}

int main(){
    scanf("%d",&n);
    int maxBit = 0;
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        maxBit = max(maxBit,getBits(a));
        arr.push_back(a);
    }
    int baseBit = 1;

    for(int i=0;i<maxBit;i++){
        vector<int> bbulket[10];
        for(auto& v:arr){
            int digit = (v/baseBit)%10;
            bbulket[digit].push_back(v);
        }
        baseBit*=10;
        //收集
        arr.clear();
        for(int i=0;i<10;i++){
            for(int j=0;j<bbulket[i].size();j++){
                arr.push_back(bbulket[i][j]);
            }
        }
    }
    for(auto&v:arr){
        printf("%d ",v);
    }
    printf("\n");
    return 0;
}



邓等灯
10天前

例题:比较大小
比大小1.png

直接算几乎不可能
于是乎,又想到枚举,即 从 1,2,3,4......枚举,然后找规律

比大小2.png

貌似已经得出来了规律,但是感觉还是不够严谨。

于是列出代数式,去找一般规律

比大小3.png

展开做比较
比大小4.png

补充:
比大小5.png




邓等灯
12天前

1 按照 城市,学校,成绩作为关键字来排名

相当于:

struct Student{
    int cityId;
    int schoolId;
    char grade;
    int stuId;
    bool operator<(const Student& s)const{
        if(cityId==s.cityId){
            if(schoolId==s.schoolId){
                return grade<s.grade;
            }
            return schoolId<s.schoolId;
        }
        return cityId<s.cityId;
    }
};
sort(students.begin(),students.end());

代码如下:

#include<iostream>
#include<vector>
#include<cstdlib> 
#include<ctime>

using namespace std;

struct Student{
    int cityId;
    int schoolId;
    char grade;
    int stuId;
};

ostream& operator << (ostream& os, const Student& obj)
{
   os << "城市: "<<obj.cityId<<"  学校:"
   <<obj.schoolId<<" 学生id:"<<obj.stuId<<
   " 分数:"<<obj.grade;
   return os;
}

int main(){
    srand(time(NULL));
    vector<Student> students;
    for(int i=0;i<12;i++){
        auto cid = rand() % 3 + 1;
        auto sid = rand() % 6 + 1;
        char g = 'A'+(rand() % 4 );
        auto stuId = 1001001+i;
        students.push_back({cid,sid,g,stuId});
    }
    for(auto& s:students){
        cout<<s<<endl;
    }

    vector<Student> gBulket[4];
    for(auto& s:students){
        int gmod = s.grade-'A';
        gBulket[gmod].push_back(s);
    }
    vector<Student> sBulket[7];
    for(int i=0;i<4;i++){
        for(int j=0;j<gBulket[i].size();j++){
            auto& stu = gBulket[i][j];
            sBulket[stu.schoolId].push_back(stu);
        }
    }
    vector<Student> cBulket[5];
    for(int i=1;i<7;i++){
        for(int j=0;j<sBulket[i].size();j++){
            auto& stu = sBulket[i][j];
            cBulket[stu.cityId].push_back(stu);
        }
    }
    //收集
    students.clear();
    for(int i=1;i<5;i++){
        for(int j=0;j<cBulket[i].size();j++){
            students.push_back(cBulket[i][j]);
        }
    }
    cout<<"按关键字排好后:"<<endl;
    for(auto& s:students){
        cout<<s<<endl;
    }
    return 0;
}

输出结果:
城市: 2 学校:1 学生id:1001001 分数:D
城市: 1 学校:6 学生id:1001002 分数:D
城市: 1 学校:5 学生id:1001003 分数:D
城市: 1 学校:6 学生id:1001004 分数:A
城市: 2 学校:4 学生id:1001005 分数:C
城市: 1 学校:5 学生id:1001006 分数:B
城市: 2 学校:6 学生id:1001007 分数:C
城市: 2 学校:2 学生id:1001008 分数:A
城市: 1 学校:5 学生id:1001009 分数:C
城市: 3 学校:1 学生id:1001010 分数:D
城市: 1 学校:4 学生id:1001011 分数:A
城市: 1 学校:2 学生id:1001012 分数:D
按关键字排好后:
城市: 1 学校:2 学生id:1001012 分数:D
城市: 1 学校:4 学生id:1001011 分数:A
城市: 1 学校:5 学生id:1001006 分数:B
城市: 1 学校:5 学生id:1001009 分数:C
城市: 1 学校:5 学生id:1001003 分数:D
城市: 1 学校:6 学生id:1001004 分数:A
城市: 1 学校:6 学生id:1001002 分数:D
城市: 2 学校:1 学生id:1001001 分数:D
城市: 2 学校:2 学生id:1001008 分数:A
城市: 2 学校:4 学生id:1001005 分数:C
城市: 2 学校:6 学生id:1001007 分数:C
城市: 3 学校:1 学生id:1001010 分数:D

复杂度分析:
设数组长度为 n
第一关键字种类为 m
第二关键字种类 为 r
第三关键字种类 为 q

则复杂度为 O(nmr*q)

比较适合 n 比较大,但是 关键字个数不多的情况




邓等灯
13天前

好比,在打桥牌或者升级。我们的牌抓到手上以后的习惯是,先按照花色来分类。再在花色之间从小到大排序。

1 阶段1 按花色来分类

#include<iostream>
#include <cstdlib> 
#include <ctime>
#include<vector>
#include<unordered_map>
#include<cstring>

using namespace std;

const int MAXN = 1e5+5;

enum class Suits:int{
    Spades = 0,
    Hearts,
    Clubs,
    Diamonds,
    Count
};

struct Card{
    Suits suit;
    int point;
};

unordered_map<Suits,string> suitStr = {{Suits::Spades,"黑桃"},
    {Suits::Hearts,"红桃"},{Suits::Clubs,"梅花"},{Suits::Diamonds,"方片"}
};

unordered_map<int,string> ptStr = {{1,"A"},{11,"J"},
    {12,"Q"},{13,"K"}
};

ostream& operator << (std::ostream& os, const Suits& obj)
{
   string s = suitStr[obj];
   os << s;
   return os;
}

ostream& operator << (ostream& o, Card& a)
{
    string s = "";
    if(ptStr.find(a.point)!=ptStr.end()){
        s = ptStr[a.point];
    }else{
        s = to_string(a.point);
    }
    o << "花色:"<<a.suit<<"   "<< "点数:" << s;
    return o;
}

int n;

int main(){
    srand(time(NULL));
    int divisor = static_cast<int>(Suits::Count);


    vector<Card> cards;

    for(int i=0;i<10;i++){
        auto a = static_cast<Suits>(rand()%divisor);
        auto p = rand() % 13 + 1;
        cards.push_back({a,p});
    }

    for(auto c:cards){
        cout<<c<<endl;
    }

    //花色桶,按花色排序
    vector<Card> bulket[4];
    for(int i=0;i<cards.size();i++){
        //按花色分类
        auto st = static_cast<int>(cards[i].suit);
        bulket[st].push_back(cards[i]);
    }
    //收集
    cards.clear();
    for(int i=0;i<4;i++){
        for(int j=0;j<bulket[i].size();j++){
            cards.push_back(bulket[i][j]);
        }

    }
    cout<<"按花色分类后:"<<endl;
    for(auto c:cards){
        cout<<c<<endl;
    }

    return 0;
}

输出:
花色:红桃 点数:8
花色:红桃 点数:10
花色:梅花 点数:Q
花色:红桃 点数:3
花色:梅花 点数:K
花色:方片 点数:3
花色:红桃 点数:Q
花色:黑桃 点数:2
花色:方片 点数:2
花色:梅花 点数:5
按花色分类后:
花色:黑桃 点数:2
花色:红桃 点数:8
花色:红桃 点数:10
花色:红桃 点数:3
花色:红桃 点数:Q
花色:梅花 点数:Q
花色:梅花 点数:K
花色:梅花 点数:5
花色:方片 点数:3
花色:方片 点数:2

可见,扑克牌,已经按照花色排好序了,但花色之间还是乱序的。

阶段 2 再把点数的分类结合进去

注意顺序,先按点数来分,最后按花色来分
因为全局是按 花色来分,然后花色内才是按照点数来排。
如果先按花色来分,最后按点数来分的话,就变成,全局以点数来排,然后点数同的,再以花色来分了
这个地方要注意.

相当于:

struct Card{
    Suits suit;
    int point;
    bool operator<(const Card& c)const{
        if(suit==c.suit){
            return point<c.point;
        }
        return suit<c.suit;
    }
};
sort(cards.begin(),cards.end());

完整代码如下:

#include<iostream>
#include <cstdlib> 
#include <ctime>
#include<vector>
#include<unordered_map>
#include<cstring>

using namespace std;

const int MAXN = 1e5+5;

enum class Suits:int{
    Spades = 0,
    Hearts,
    Clubs,
    Diamonds,
    Count
};

struct Card{
    Suits suit;
    int point;
};

unordered_map<Suits,string> suitStr = {{Suits::Spades,"黑桃"},
    {Suits::Hearts,"红桃"},{Suits::Clubs,"梅花"},{Suits::Diamonds,"方片"}
};

unordered_map<int,string> ptStr = {{1,"A"},{11,"J"},
    {12,"Q"},{13,"K"}
};

ostream& operator << (std::ostream& os, const Suits& obj)
{
   string s = suitStr[obj];
   os << s;
   return os;
}

ostream& operator << (ostream& o, Card& a)
{
    string s = "";
    if(ptStr.find(a.point)!=ptStr.end()){
        s = ptStr[a.point];
    }else{
        s = to_string(a.point);
    }
    o << "花色:"<<a.suit<<"   "<< "点数:" << s;
    return o;
}

int n;

int main(){
    srand(time(NULL));
    int divisor = static_cast<int>(Suits::Count);


    vector<Card> cards;

    for(int i=0;i<10;i++){
        auto a = static_cast<Suits>(rand()%divisor);
        auto p = rand() % 13 + 1;
        cards.push_back({a,p});
    }

    for(auto c:cards){
        cout<<c<<endl;
    }


    //按点数分类
    vector<Card> bulket_pt[14];
    for(int i=0;i<cards.size();i++){
        bulket_pt[cards[i].point].push_back(cards[i]);
    }

    //花色桶,按花色排序
    vector<Card> bulket[4];

    for(int i=1;i<14;i++){
        for(int j=0;j<bulket_pt[i].size();j++){
            auto st = static_cast<int>(bulket_pt[i][j].suit);
            bulket[st].push_back(bulket_pt[i][j]);
        }
    }

    //收集
    cards.clear();
    for(int i=0;i<4;i++){
        for(int j=0;j<bulket[i].size();j++){
            cards.push_back(bulket[i][j]);
        }

    }
    cout<<"按花色和点数分类后:"<<endl;
    for(auto c:cards){
        cout<<c<<endl;
    }

    return 0;
}

输出:
花色:红桃 点数:3
花色:梅花 点数:A
花色:红桃 点数:10
花色:红桃 点数:A
花色:梅花 点数:K
花色:方片 点数:K
花色:红桃 点数:5
花色:黑桃 点数:3
花色:方片 点数:6
花色:黑桃 点数:7
按花色和点数分类后:
花色:黑桃 点数:3
花色:黑桃 点数:7
花色:红桃 点数:A
花色:红桃 点数:3
花色:红桃 点数:5
花色:红桃 点数:10
花色:梅花 点数:A
花色:梅花 点数:K
花色:方片 点数:6
花色:方片 点数:K




邓等灯
14天前

1.举个例子
比如有一个只有 小写字母 [a-z]组成的字符串 s

那么当 s 的长度 n>26 时,则必有两个字母是相同的。这就是鸽巢原理

先进行最不利构造,即先构造一个字母全不相同的字符串,即[a-z]刚好出现一次的串,长度为 26

比如 xyzabcdefghijklmnopqrstuvw, xyzabcdefklmnopqrstuvwghij .... 任意排列都可以

即这个是满足条件的最长序列了

然后加长度,无论加那个字母,都会出现重复的字母

2简单例题:
CF672B - Different is Good
题目要求,任意子串,包括长度为1的都不同。
考虑最不利情况,那么即是,每个字母都不相同。

然而,根据鸽巢原理可知,当n>26 时,比有两个字母相同,不满足条件,返回-1

代码如下:

#include<iostream>
#include<cstring>

using namespace std;
const int MAXN = 1e5+5;
char cs[MAXN];
int cnt[26];
int n;

int main(){
    cin>>n;
    cin>>cs;
    for(int i=0;i<n;i++){
        cnt[cs[i]-'a']++;
    }
    int a = 0;
    for(int i=0;i<26;i++){
        if(cnt[i]>1){
            a+= cnt[i]-1;
        }
    }
    //根据鸽槽原理,至少2个相同
    if(n>26){
        cout<<-1<<endl;
        return 0;
    }
    if(a>=26){
        cout<<-1<<endl;
    }else{
        cout<<a<<endl;
    }
    return 0;
}



邓等灯
18天前

例题:P1164 小A点菜

因为题目要求,钱要刚好用完。所以剩余钱 leftMoney 为0时是才算一个合法的方案。

先看记忆化搜索的代码

#include<iostream>
#include<cstring>

using namespace std;
using i64 = long long;

const int MAXN = 105;
const int MAXM = 10005;
int foods[MAXN];
i64 dp[MAXN][MAXM];
int n,m;

i64 ans;

i64 dfs(int idx,int leftMoney){
    if(idx>n){
        if(leftMoney==0){
           return 1;
        }
        return 0;
    }
    if(dp[idx][leftMoney]!=-1){
        return dp[idx][leftMoney];
    }
    i64 res = 0;
    if(leftMoney>=foods[idx]){
        res += dfs(idx+1,leftMoney-foods[idx]);
    }
    res += dfs(idx+1,leftMoney);
    dp[idx][leftMoney] = res;
    return res;
}

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

搜索就两个分支,选和不选,选的时候判断一下,钱够不够。

然后由记忆化搜索的代码可以推导出dp 的代码。
dp[MAXN][MAXM] 表示,选到当前第i个食物时,还剩余j块钱时的方案数。

dp 和 记忆化搜索一样,采用的是 自底向上的求解。

初始状态都是 剩余 m 块钱。
记忆化搜索时 是,从n 向 1 推导。dp 时是 从 1 到 n 推导,本质是一样的。

而当前的剩余钱数leftMoney 都一样,从钱少的状态向钱多的状态转移。

和组合数学中组合计数原理是一样的,即运用的是加法原理。

下面是朴素dp的代码

#include<iostream>
#include<cstring>

using namespace std;
using i64 = long long;

const int MAXN = 105;
const int MAXM = 10005;
int foods[MAXN];
i64 dp[MAXN][MAXM];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>foods[i];
    }
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j] += dp[i-1][j];
            if(j>=foods[i]){
                dp[i][j] += dp[i-1][j-foods[i]];
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

要注意的是初始化状态 dp[0][0] = 1
因为只有钱刚好花完,才是合法的方案。由记忆化搜索代码可知。

下面来模拟一下用例:
初始状态:
01背包方案数01.png

阶段1:
01背包方案数02.png

阶段2:
01背包方案数03.png

阶段3:
01背包方案数04.png

阶段4:
01背包方案数05png.png

由图可以看出,当前状态只依赖于上一行,而且必须加上上一行。
而未计算的状态默认为0

所以可以使用滚动数组优化
dp[i][j] += dp[i-1][j];
dp[i][j] += dp[i-1][j-foods[i]];

而dp[i][j] 当前为0,初始时就是直接加上上一行
所以 等价于 dp[j] = dp[j], 一句废话,舍去。
等价于 :
dp[j] += dp[j-foods[i]];

和求最大的01背包一样,j容量从大往小枚举

所以优化空间后代码如下

#include<iostream>
#include<cstring>

using namespace std;
using i64 = long long;

const int MAXN = 105;
const int MAXM = 10005;
int foods[MAXN];
i64 dp[MAXM];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>foods[i];
    }
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            if(j>=foods[i]){
                dp[j] += dp[j-foods[i]];
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

01背包方案数06png.png

容量 j 要从大往小遍历,防止状态值被前修改,导致错误的状态转移和状态值传递
如果从小到大遍历,就会产生上图中的错误值传递,导致最终结果计算错误。