年轻人振作起来，国家需要你

隽bro精选好题：

OJ：

• HS008 子集 深搜基本遍历
• P1445 【系列题】单调栈（一）每日温度
• P1446 【系列题】单调栈（二）下一个更大元素 施工中

洛谷：

• P1042 [NOIP2003 普及组] 乒乓球
• P2670 [NOIP2015 普及组] 扫雷游戏
• P1563 [NOIP2016 提高组] 玩具谜题
• P1601 A+B Problem（高精）
• P1303 A*B Problem
• P1009 [NOIP1998 普及组] 阶乘之和
• P4924 [1007] 魔法少女小Scarlet
• P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
• P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
• P1067 [NOIP2009 普及组] 多项式输出
• P1098 [NOIP2007 提高组] 字符串的展开
• P1065 [NOIP2006 提高组] 作业调度方案
• P1786 帮贡排序
• P1591 阶乘数码
• P1249 最大乘积
• P1045 [NOIP2003 普及组] 麦森数
• P1714 切蛋糕
• P2629 好消息，坏消息

有需要可以Copy（主要方便我自己）

谢绝复制挂主页的 赖达元，卓骞佑等

set & map

set<int> st;
map<string,int> mp;
mp[key] = value;//插入键值

随机数造数据

#include
using namespace std;
int main(){
	freopen( "test.in" , "w" , stdout );
	srand( int ( time ( 0 ) ) );
	int n, m, p, a;
	n = rand() % 10000;
	m = rand() % 10000;
	cout << m << endl;
	cout << n << endl;
	while( m-- ){
		p = rand() % 10000;
		a = rand() % 10000;
		cout << p << ' ' << a << endl;
	}
	fclose( stdout );
}

万能开头：

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

int main(){}

关于vector：

vector<int> v;//创建一个空vector
v.push_back(x)//向尾部增加一个元素x
v.insert(pos,x)//向pos地址指向元素前增加一个元素x
v[i]//访问第i位元素
v.pop_back()//删除向量中最后一个元素
v.clear()//清空向量中所有元素
v.empty()//判断向量是否为空
v.size()//返回向量中元素的个数
v.begin()//返回量头指针（迭代器），指向第一个元素
v.end()//返回量尾指针（迭代器），指向第一个元素+1位置
v.erase(v.begin()+i)//删除第i位位置的元素

全排列函数：

next_permutation(数组头地址，数组尾地址);//求下一个全排列
prev_permutation(数组头地址，数组尾地址);//求上一个全排列

排列数组(sort函数)：

sort(a(begin),a(end)+size);//默认小到大
sort(a(begin),a(end)+size,greater<int>());//大到小
sort(a(begin),a(end)+size,less<int>());//小到大

与字符相关的函数

getchar()//输入单个字符
putchar()//输出单个字符
islower(x)//判断x是否为小写字母
isupper(x)//判断x是否为大写字母
isdigit(x)//判断x是否为数字
isalpha(x)//判断x是否为字母

builtin内建函数

__builtin_ffs(x)//返回x中最后一个为1的位是从后往前的第几位
__builtin_popcount(x)//x中1的个数
__builtin_ctz(x)//x末尾0的个数，x=0时结果未定义
__builtin_clz(x)//x前导0的个数，x=0时结果未定义
__builtin_parity(x)//x中1的奇偶性

二分查找核心代码

int dp[30000];
int n;
int fun(int k){
    int l=0,r=n-1,m=(l+r)/2;
    while(l<r){
        if(k==dp[m]){
            return m;
        }else if(k>dp[m]){
            l=m+1;
        }else{
            r=m-1;
        }
    }
    return -1;
}

最大公因数(gcd)递归实现

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

斐波那契数列

int dfs( int a ){
    if( a == 1 || a == 2 ){
        return 1;
    }
    return dfs( a - 1 ) + dfs( a - 2 );
}

评测状态

• Waiting 评测：评测请求正在等待被评测机抓取
• Fetched 评测：评测请求已被评测机抓取，正在准备开始评测
• Compiling 评测：正在编译中
• Judging 评测：编译成功，正在评测中
• Accepted 通过：程序输出完全正确
• Wrong Answer 不通过：程序输出与标准答案不一致（不包括行末空格以及文件末空行）
• Time Limit Exceeded 不通过：程序运行时间超过了题目限制
• Memory Limit Exceeded 不通过：程序运行内存空间超过了题目限制
• Runtime Error 不通过：程序运行时错误（如数组越界、被零除、运算溢出、栈溢出、无效指针等）
• Compile Error 不通过：编译失败
• System Error 错误：系统错误（如果您遇到此问题，请及时在讨论区进行反馈）
• Canceled 其他：评测被取消
• Unknown Error 其他：未知错误
• Ignored 其他：被忽略

广度优先搜索

#include <bits/stdc++.h>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void BFS(int startVertex);

private:
    int vertices; // 图的顶点数
    std::vector<std::vector<int>> adjList; // 邻接表
};

Graph::Graph(int vertices) : vertices(vertices) {
    adjList.resize(vertices);
}

// 添加边
void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // 将w添加到v的邻接表中
    adjList[w].push_back(v); // 因为是无向图，反向添加
}

// 广度优先搜索
void Graph::BFS(int startVertex) {
    std::vector<bool> visited(vertices, false); // 访问标记
    std::queue<int> queue; // 使用队列存储要访问的节点

    // 从起始节点开始
    visited[startVertex] = true; // 标记为已访问
    queue.push(startVertex); // 入队

    while (!queue.empty()) {
        int currentVertex = queue.front(); // 获取队首元素
        queue.pop(); // 出队
        std::cout << currentVertex << " "; // 处理当前节点

        // 将未访问的邻接节点入队
        for (int neighbor : adjList[currentVertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true; // 标记为已访问
                queue.push(neighbor); // 入队
            }
        }
    }
}

int main() {
    Graph graph(5); // 创建一个包含5个顶点的图
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);

    std::cout << "广度优先搜索结果: ";
    graph.BFS(0); // 从顶点0开始BFS
    return 0;
}

深度优先搜索框架

#include <bits/stdc++.h>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void DFS(int startVertex);

private:
    int vertices; // 图的顶点数
    std::vector<std::vector<int>> adjList; // 邻接表
};

Graph::Graph(int vertices) : vertices(vertices) {
    adjList.resize(vertices);
}

// 添加边
void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w); // 将w添加到v的邻接表中
    adjList[w].push_back(v); // 因为是无向图，反向添加
}

// 深度优先搜索
void Graph::DFS(int startVertex) {
    std::vector<bool> visited(vertices, false); // 访问标记
    std::stack<int> stack; // 使用栈存储要访问的节点

    // 从起始节点开始
    stack.push(startVertex);

    while (!stack.empty()) {
        int currentVertex = stack.top(); // 访问栈顶元素
        stack.pop();

        if (!visited[currentVertex]) {
            std::cout << currentVertex << " "; // 处理当前节点
            visited[currentVertex] = true; // 标记为已访问
        }

        // 将未访问的邻接节点压入栈中
        for (int neighbor : adjList[currentVertex]) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

int main() {
    Graph graph(5); // 创建一个包含5个顶点的图
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);

    std::cout << "深度优先搜索结果: ";
    graph.DFS(0); // 从顶点0开始DFS
    return 0;
}

深度优先搜索（递归版）

#include <bits/stdc++.h>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void DFS(int startVertex);

private:
    void DFSUtil(int v, std::vector<bool>& visited);
    int vertices;
    std::vector<std::vector<int>> adjList;
};

Graph::Graph(int vertices) : vertices(vertices) {
    adjList.resize(vertices);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
    adjList[w].push_back(v);
}

// 辅助函数用于递归DFS
void Graph::DFSUtil(int v, std::vector<bool>& visited) {
    visited[v] = true;
    std::cout << v << " ";

    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            DFSUtil(neighbor, visited);
        }
    }
}

// 主DFS函数
void Graph::DFS(int startVertex) {
    std::vector<bool> visited(vertices, false);
    DFSUtil(startVertex, visited);
}

int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 4);

    std::cout << "深度优先搜索结果: ";
    graph.DFS(0);
    return 0;
}

二叉树叶子结点数等于度为二的节点加一

我们的赞助商