头像

邓等灯




离线:2小时前


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


邓等灯
3小时前

题目:
不定方程1.png

思路:将左右两边变成乘积的形式
左边利用幂运算的性质,右边利用因数分解即可

不定方程2.png

程序验证:

#include<iostream>

using namespace std;

int main(){
    for(int x=0;x<31;x++){
        for(int y=0;y<31;y++){
            int a = (1<<x)-(1<<y);
            if(a==1984){
                cout<<x<<' '<<y<<endl;
            }
        }
    }
    return 0;
}

输出:
11 6




问题
降次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




邓等灯
12天前

题目:
递推函数2_1.png

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

即:

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

计算过程如下:

递推函数2_2.png




邓等灯
14天前

输入:
第一行 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;
}



邓等灯
16天前

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

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

比大小2.png

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

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

比大小3.png

展开做比较
比大小4.png

补充:
比大小5.png




邓等灯
18天前

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 比较大,但是 关键字个数不多的情况




邓等灯
19天前

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

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




邓等灯
20天前

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