1.斐波那契数列的模三（HDU1021）

题目要求判断fn是否能被3整除，因此我们需要维护一个f(i)，f(i)表示F(i)对3取模的余数。则可得状态转移方程

#include <iostream>

#include <string>

#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;


int main()
{
    int n;

    while (cin >> n)
    {
        if (n < 2)
        {
            cout << "no" << endl;
            continue;
        }
        int f0 = 1;

        int f1 = 2;
        for (int i = 2; i <= n; i++)
        {
            int temp = f1;
            f1 = (f1 + f0) % 3;
            f0 = temp;
        }
        if (f1 == 0)

            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }

    return 0;
}

2.并查集求最大连通子图（HDU1232）

题给信息可化为并查集求最大连通子图的问题

给出下标a，b。先判断a，b是否在同一个最大连通子图中，即找它们各自的根，若相同则表示在同一个并查集中，否则不在。

void unionS(int a, int b, vector<int> &s)

{
    a = findS(a, s);
    b = findS(b, s);


    if (a != b)
    {
        s[a] = b;
    }

    return;
}

在并查集中当s(i) <= -1 时，表示该节点为根节点(负节点的绝对值为该并查集所含节点个数)。于是查找函数的基本逻辑为，如果节点值非负即非根，继续向上递归寻找。

int findS(int a, vector<int> &s)

{
    if (s[a] > -1)
        return findS(s[a], s);
    else
        return a;
}

#include <iostream>

#include <string>

#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;


int findS(int a, vector<int> &s)
{
    if (s[a] > -1)
        return findS(s[a], s);
    else
        return a;
}


void unionS(int a, int b, vector<int> &s)

{
    a = findS(a, s);
    b = findS(b, s);

    if (a != b)
    {
        s[a] = b;
    }



    return;
}
int main()
{
    int n, m;
    while (cin >> n >> m && n != 0)
    {

        vector<int> s(n + 1, -1);
        vector<bool> root(n + 1, 0);
        int count = 0;
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            unionS(a, b, s);
        }
        for (int i = 1; i <= n; i++)
        {
            if (s[i] <= -1 && !root[i])
            {
                root[i] = 1;
                count++;
            }

            else
            {
                int rootIndex = findS(i, s);
                if (!root[rootIndex])
                {
                    root[rootIndex] = 1;
                    count++;
                }
            }
        }

        cout << count - 1 << endl;
    }

    return 0;
}

注意，连通n个最大连通子图所需的路径数目为n-1条

int findS(int a, vector<int> &s)

{
    int root = a;
    while (s[root] >= 0)    //循环找到根节点
        root = s[root];
    while (a != root)   //压缩路径
    {
        int next = s[a];    //下一个元素
        s[a] = root;
        a = next;
    }

    return root;    //root为根节点的下标
}

每次查找时都调整路径上的节点值，经过一定次数的查找后，路径上的节点值会都变为根节点的下标，从树形上看相当于把一棵树慢慢压扁，最后全都变成根节点的叶节点。

先前的union函数只是简单的合并，并没有考虑到查找效率的问题。因为数的查找效率和树的高度有关，因此我们的优化思路为尽可能的降低树的高度，即每次union时把小树合并到大数上。

void unionS(int a, int b, vector<int> &s)

{
    a = findS(a, s);
    b = findS(b, s);


    if (a != b)
    {
        if (a > b)
        {
            s[b] += s[a];
            s[a] = b;
        }
        else
        {
            s[a] += s[b];
            s[b] = a;
        }
    }
    else if (a == b && a == -1)
    {
        s[b] += s[a];
        s[a] = b;
    }

    return;
}

表示该节点为根节点(负节点的绝对值为该并查集所含节点个数)。因此每次union时要把小树的节点个数加到大数上，然后把小树挂到大树上。

排序规则为按分数从高到低排序，若分数相同，则按考号从小到大排序。

class stuInfo
{
public:
    string number;
    int totalScore;


public:
    stuInfo()
    {
        this->number = "";
        this->totalScore = 0;
    }
};

bool compare(stuInfo a, stuInfo b)

{
    if (a.totalScore == b.totalScore)
        return a.number < b.number;
    return a.totalScore > b.totalScore;
}

#include <iostream>

#include <string>

#include <vector>
#include <algorithm>
using namespace std;

class stuInfo
{
public:
    string number;

    int totalScore;

public:
    stuInfo()
    {

        this->number = "";
        this->totalScore = 0;

    }
};

bool compare(stuInfo a, stuInfo b)
{
    if (a.totalScore == b.totalScore)
        return a.number < b.number;
    return a.totalScore > b.totalScore;

}
int main()
{
    int n, m, g;
    while (cin >> n && n != 0)
    {
        cin >> m >> g;
        vector<stuInfo> stu(n);

        vector<int> score(m + 1, 0);
        int stuNum = 0;
        for (int i = 1; i <= m; i++)
            cin >> score[i];
        for (int i = 0; i < n; i++)
        {
            cin >> stu[i].number;
            int solvedNum;
            cin >> solvedNum;
            for (int j = 0; j < solvedNum; j++)
            {
                int x;
                cin >> x;
                stu[i].totalScore += score[x];
            }
        }
        sort(stu.begin(), stu.end(), compare);
        for (auto i : stu)
            if (i.totalScore >= g)
                stuNum++;
        cout << stuNum << endl;

        for (auto i : stu)
        {
            if (i.totalScore >= g)
            {
                cout << i.number << " " << i.totalScore << endl;
            }
        }
    }

    return 0;
}


读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。 

主要思路为用栈转为后缀表达式来计算。

string temp = "";
            while (s[Idx] != ' ' && isdigit(s[Idx]))
            {
                temp += s[Idx++];
            }
            if (!temp.empty())
                num.push(stod(temp));

if (s[Idx] == ' ')
            {
                Idx++;
                continue;
            }

对于后缀表达式，操作符栈的操作原则为：若当前栈空，则入栈；若非空，且当前操作符的优先级小于等于栈顶操作符的优先级，则弹出栈顶操作符

 压入操作数栈，直到当前操作符的优先级大于栈顶操作符。

if (op.empty())
                    op.push(s[Idx++]);
                else if (pri(op.top()) >= pri(s[Idx]))
                {
                    while (!op.empty() && pri(op.top()) >= pri(s[Idx]))
                    {
                        char opr = op.top();
                        op.pop();
                        double a = num.top();
                        num.pop();
                        double b = num.top();
                        num.pop();
                        num.push(Calculate(b, a, opr));
                    }
                    op.push(s[Idx++]);
                }
                else
                    op.push(s[Idx++]);

int pri(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    else
        return 0;
}

当所有操作符以及操作数都压入栈后，循环计算，直到栈空。

while (!op.empty())
        {
            char opr = op.top();
            op.pop();
            double a = num.top();
            num.pop();
            double b = num.top();
            num.pop();
            num.push(Calculate(b, a, opr));
        }

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <iomanip>
using namespace std;

double Calculate(double a, double b, char op)
{
    if (op == '+')
        return a + b;
    if (op == '-')
        return a - b;
    if (op == '*')
        return a * b;
    if (op == '/')
        return a / b;
    else
        return 0;
}

int pri(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    else
        return 0;
}
int main()
{
    string s;
    while (getline(cin, s))
    {
        if (s == "0")
            break;
        stack<double> num;
        stack<char> op;
        int Idx = 0;
        while (Idx < s.size())
        {
            string temp = "";
            while (s[Idx] != ' ' && isdigit(s[Idx]))
            {
                temp += s[Idx++];
            }
            if (!temp.empty())
                num.push(stod(temp));
            if (s[Idx] == ' ')
            {
                Idx++;
                continue;
            }
            if (Idx >= s.size())
                break;
            else
            {
                if (op.empty())
                    op.push(s[Idx++]);
                else if (pri(op.top()) >= pri(s[Idx]))
                {
                    while (!op.empty() && pri(op.top()) >= pri(s[Idx]))
                    {
                        char opr = op.top();
                        op.pop();
                        double a = num.top();
                        num.pop();
                        double b = num.top();
                        num.pop();
                        num.push(Calculate(b, a, opr));
                    }
                    op.push(s[Idx++]);
                }
                else
                    op.push(s[Idx++]);
            }
        }
        while (!op.empty())
        {
            char opr = op.top();
            op.pop();
            double a = num.top();
            num.pop();
            double b = num.top();
            num.pop();
            num.push(Calculate(b, a, opr));
        }
        cout << fixed << setprecision(2) << num.top() << endl;
    }

    return 0;
}
    

题目要求判断fn是否能被3整除，因此我们需要维护一个f(i)，f(i)表示F(i)对3取模的余数。则可得状态转移方程f(i) = (f(i-1) + f(i-2)) % 3 

Coding Day6

数据库

本文详解HDU编程题解法，包括斐波那契数列模3判断、并查集求连通图、结构体排序和中缀表达式计算。提供AC代码实现，涵盖状态转移方程、路径压缩优化、自定义排序规则和栈计算方法等核心算法技巧，适合算法竞赛学习参考。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Coding Day6

Coding Day6

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐