T1《纯偶数》
题目描述
我们称一个非负整数为“纯偶数”，当且仅当它的每一位数字都是偶数（只能出现 0,2,4,6,8）。
把所有纯偶数按从小到大排列为：
0,2,4,6,8,20,22,24,…
从 1 开始编号（即第 1 个是 0）。你的任务是输出第 n 个纯偶数。
输入格式
一行一个正整数 n。
输出格式
输出第 n 个纯偶数。
思路
像这道题一样，这道题是一道以数学思维做的编程题，需要运用进制转换；
代码如下
#include<bits/stdc++.h>
using namespace std;
long long s[10000];
int main(){
long long n;
cin>>n;
int cnt = 0;
if(n == 1){
cout<<(n-1)*2;
return 0;
}
n = n-1;
while(n){
s[++cnt] = n % 5;
n /= 5;
}
for(int i = cnt;i>=1;i–){
cout<<s[i]*2;
}
return 0;
}
进制转换
十进制转二进制
使用除2取余法，将十进制数反复除以2并记录余数，直到商为0，余数逆序排列即为二进制结果。
示例代码：
#include <iostream>
#include <vector>
using namespace std;
void decimalToBinary(int n) {
vector<int> binary;
while (n > 0) {
binary.push_back(n % 2);
n /= 2;
}
for (int i = binary.size() – 1; i >= 0; –i) {
cout << binary[i];
}
}
int main() {
int num = 10;
decimalToBinary(num); // 输出: 1010
return 0;
}
二进制转十进制
从最低位开始，每位乘以2的幂次（从0开始），累加结果。
示例代码：
#include <iostream>
#include <cmath>
using namespace std;
int binaryToDecimal(string binary) {
int decimal = 0;
for (int i = 0; i < binary.length(); ++i) {
if (binary[i] == '1') {
decimal += pow(2, binary.length() – 1 – i);
}
}
return decimal;
}
int main() {
string bin = "1010";
cout << binaryToDecimal(bin); // 输出: 10
return 0;
}
十进制转十六进制
使用除16取余法，余数10~15分别对应字母A~F。
示例代码：
#include <iostream>
#include <vector>
using namespace std;
void decimalToHex(int n) {
vector<char> hex;
while (n > 0) {
int rem = n % 16;
if (rem < 10) hex.push_back(rem + '0');
else hex.push_back(rem – 10 + 'A');
n /= 16;
}
for (int i = hex.size() – 1; i >= 0; –i) {
cout << hex[i];
}
}
int main() {
int num = 255;
decimalToHex(num); // 输出: FF
return 0;
}
十六进制转十进制
每位乘以16的幂次（从右到左，幂次从0开始），字母A~F转换为10~15后计算。
示例代码：
#include <iostream>
#include <cmath>
#include <cctype>
using namespace std;
int hexToDecimal(string hex) {
int decimal = 0;
for (int i = 0; i < hex.length(); ++i) {
char c = toupper(hex[i]);
int val = (c >= 'A') ? (c – 'A' + 10) : (c – '0');
decimal += val * pow(16, hex.length() – 1 – i);
}
return decimal;
}
int main() {
string hex = "FF";
cout << hexToDecimal(hex); // 输出: 255
return 0;
}
使用STL库函数
C++的<bitset>和<iomanip>库提供快速进制转换支持。
二进制与十进制互转：
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int num = 10;
bitset<8> bin(num); // 8位二进制表示
cout << bin; // 输出: 00001010
string binary = "1010";
int dec = bitset<8>(binary).to_ulong();
cout << dec; // 输出: 10
return 0;
}
十六进制输出：
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int num = 255;
cout << hex << uppercase << num; // 输出: FF
return 0;
}
T2《CSP》
题目描述
给定一个长度为 n 的字符串 s（只包含大写字母）。
请你统计有多少个三元组 (i,j,k) 满足：
- 1≤i<j<k≤n；
- si=C、sj=S、sk=P。
也就是说，你需要统计字符串中有多少个子序列等于 "CSP"。
输入格式
第一行一个整数 n。 第二行一个长度为 n 的字符串 s。
输出格式
输出一个整数，表示满足条件的三元组数量。
思路
这是一道简单的dp，暴力只能拿50分
暴力代码
#include<bits/stdc++.h>
using namespace std;
char a[1000005];
int main(){
int n;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
}
long long ans = 0;
for(int i = 1;i<n-1;i++){
if(a[i] == 'C'){
for(int j = i+1;j<n;j++){
if(a[j] == 'S'){
for(int k = j+1;k<=n;k++){
if(a[k] == 'P'){
ans++;
}
}
}
}
}
}
cout<<ans;
return 0;
}
代码如下
#include<bits/stdc++.h>
using namespace std;
char a[1000005];
long long dp[3];
int main(){
long long n;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
}
for(int i = 1;i<=n;i++){
if(a[i] == 'C'){
dp[0]++;
}
if(a[i] == 'S'){
dp[1]+=dp[0];
}
if(a[i] == 'P'){
dp[2]+=dp[1];
}
}
cout<<dp[2];
return 0;
}
T3《填方格》
题目描述
有一个 2×n 的矩形网格（2 行 n 列）。你需要在每个格子里填入下列三个数之一：
- 1000000007
- 9223372036854775783
- 1000000000000000003
要求任意两个相邻格子（上下或左右相邻）中的数字互质，即它们的最大公因数为 1。
请你计算一共有多少种填数方案。
由于方案数可能很大，请输出答案对 10007 取模后的结果。
输入格式
一行一个正整数 n，表示列数。
输出格式
输出一个整数，表示答案对 10007 取模后的结果。
思路
这是一道纯数学题，只需运用快速幂
暴力70分
暴力代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a = 2,n;
cin>>n;
for(int i = 1;i<=n;i++){
a*=3;
a%=10007;
}
cout<<a%10007;
return 0;
}
代码如下
#include<bits/stdc++.h>
using namespace std;
int quick(long long n){
int ans = 2;
int a = 3;
while(n!=0){
if(n%2)ans = (ans*a)%10007;
n/=2;
a = a*a%10007;
}
return ans;
}
int main(){
long long a = 2,n;
cin>>n;
cout<<quick(n)%10007;
return 0;
}
快速幂
快速幂算法原理
快速幂（Exponentiation by Squaring）是一种高效计算大整数幂的方法，时间复杂度为O(log n)。其核心思想是通过分治策略将幂次分解为二进制形式，利用平方操作减少乘法次数。
递归实现
递归版本利用幂次的性质：当n为偶数时，a^n = (a^(n/2))^2；当n为奇数时，a^n = a * a^(n-1)。注意处理n为负数的情况。
double fastPow(double x, long long n) {
if (n == 0) return 1.0;
if (n < 0) return 1.0 / fastPow(x, -n);
double half = fastPow(x, n / 2);
return (n % 2 == 0) ? half * half : half * half * x;
}
迭代实现
迭代版本通过二进制分解幂次，更高效且无栈溢出风险。每次迭代检查n的最低位，若为1则累乘当前x值，同时x不断平方，n右移一位。
double fastPow(double x, long long n) {
double res = 1.0;
long long abs_n = abs(n);
while (abs_n > 0) {
if (abs_n & 1) res *= x;
x *= x;
abs_n >>= 1;
}
return n < 0 ? 1.0 / res : res;
}
模数处理
在密码学等场景中常需计算大数模幂，可在快速幂基础上加入模运算，防止数值溢出。
const int MOD = 1e9 + 7;
long long modPow(long long x, long long n) {
long long res = 1;
x %= MOD;
while (n > 0) {
if (n & 1) res = (res * x) % MOD;
x = (x * x) % MOD;
n >>= 1;
}
return res;
}
性能优化
对于固定底数的多次查询，可预处理底数的各次幂。使用位运算代替除法和取模能进一步提升速度，但会降低代码可读性。
未完待续…………………………………………………………………………..
欲知后事如何且听下回分解
T4《最短路》
题目描述
给定一个包含 n 个点、m 条边的连通无向图。每条边的长度均为 1。
请你计算从 1 号点到 n 号点的最短路长度（经过的边数）。
输入格式
第一行两个整数 n,m，表示点数与边数。 接下来 m 行，每行两个整数 ai,bi，表示一条无向边连接 ai 与 bi。
输出格式
输出一个整数，表示从 1 到 n 的最短路长度。
思路因为这道题每条路的权重是一样的所以这道题可以用dfs但正确的解法是用Dijkstra算法
dfs代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int x,step;
};
vector <int> g[1000005];
queue <node> q;
bool vis[1000000];
int bfs(){
q.push({1,0});
vis[1] = 1;
while(!q.empty()){
node n1 = q.front();
q.pop();
if(n1.x == n)return n1.step;
for(int i = 0;i<g[n1.x].size();i++){
node n2 = {g[n1.x][i],n1.step+1};
if(vis[n2.x]==0){
q.push(n2);
vis[n2.x] = 1;
}
}
}
return -1;
}
int main(){
cin>>n>>m;
int x,y;
for(int i = 1;i<=m;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
cout<<bfs();
return 0;
}
拓展
P3371 【模板】单源最短路径（弱化版）
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让 SPFA 不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
bool vis[1000005];
long long dis[1000005];
vector<pair<int ,int > > g[100000];
void di(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
for(int i = 1;i<=n;i++){
long long minx = 0x3f3f3f3f,u;
for(int j = 1;j <= n;j++){
if(dis[j] < minx && vis[j] == 0)minx = dis[j],u = j;
}
vis[u] = 1;
for(int j = 0;j<g[u].size();j++){
int y = g[u][j].first,z = g[u][j].second;
if(dis[y]>dis[u]+z)dis[y] = dis[u]+z;
}
}
}
int main(){
cin>>n>>m>>s;
long long u,v,w;
for(int i = 1;i<=m;i++){
cin>>u>>v>>w;
g[u].push_back({v,w});
}
di();
for(int i = 1;i<=n;i++){
if(vis[i] == 0){
cout<<(1<<31)-1<<" ";
}else{
cout<<dis[i]<<" ";
}
}
return 0;
}
P4779 【模板】单源最短路径（标准版）
题目背景
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100→60；
Ag→Cu；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数 n,m,s。 第二行起 m 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
bool vis[10000005];
long long dis[10000005];
struct node{
int x,dis;
friend bool operator < (node n1,node n2){
return n1.dis>n2.dis;
}
};
priority_queue<node> pq;
vector<pair<int ,int > > g[1000000];
void di(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
pq.push({s,0});
while(!pq.empty()){
int u = pq.top().x;pq.pop();
if(vis[u])continue;
vis[u] = true;
for(int i = 0;i<g[u].size();i++){
int y = g[u][i].first,z = g[u][i].second;
if(dis[y]>dis[u]+z){
dis[y] = dis[u]+z;
pq.push({y,dis[y]});
}
}
}
}
int main(){
cin>>n>>m>>s;
long long u,v,w;
for(int i = 1;i<=m;i++){
cin>>u>>v>>w;
g[u].push_back({v,w});
}
di();
for(int i = 1;i<=n;i++){
if(vis[i] == 0){
cout<<(1<<31)-1<<" ";
}else{
cout<<dis[i]<<" ";
}
}
return 0;
}
Dijkstra算法
戴克斯特拉算法（英语：Dijkstra's algorithm，又译迪杰斯特拉算法）由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体；戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。
T5《文件压缩》
题目描述
有 n 个文件，第 i 个文件的大小是 ai。
你可以反复进行“合并压缩”操作：每次任选两个文件合并成一个新文件，合并代价等于这两个文件大小之和，新文件的大小也等于它们之和。
你想把这 n 个文件最终合并成一个文件。请输出最小总代价。
输入格式
第一行一个整数 n。 第二行 n 个整数 a1,a2,…,an。
输出格式
输出一个整数，表示最小总代价。
代码如下
#include<bits/stdc++.h>
using namespace std;
long long h[10000005];
multiset<long long> st;
int main(){
long long a;
cin>>a;
for(int i = 1;i<=a;i++){
cin>>h[i];
st.insert(h[i]);
}
long long ans = 0;
while(st.size()>=2){
auto x = st.begin();
long long xx = *x;
st.erase(x);
auto y = st.begin();
long long yy = *y;
st.erase(y);
ans+=xx+yy;
st.insert(xx+yy);
}
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
long long h[10000005];
struct node{
long long x;
friend bool operator < (node n1,node n2){
return n1.x > n2.x;
}
};
priority_queue<node> st;
int main(){
long long a;
cin>>a;
for(int i = 1;i<=a;i++){
cin>>h[i];
st.push({h[i]});
}
long long ans = 0;
while(st.size()>=2){
node x = st.top();
st.pop();
node y = st.top();
st.pop();
ans+=x.x+y.x;
st.push({x.x+y.x});
}
cout<<ans;
return 0;
}
拓展
快速优先队列的实现
优先队列（Priority Queue）是一种抽象数据类型，支持插入元素和提取优先级最高的元素。在C++中，可以使用标准库中的priority_queue容器，也可以手动实现基于堆的优先队列。
使用STL的priority_queue
C++标准库提供了priority_queue模板类，位于<queue>头文件中。默认情况下，它是一个最大堆。
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// 输出: 30 20 10
return 0;
}
如果需要最小堆，可以通过传递比较函数来实现：
#include <iostream>
#include <queue>
#include <functional>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(20);
while (!min_pq.empty()) {
std::cout << min_pq.top() << " ";
min_pq.pop();
}
// 输出: 10 20 30
return 0;
}
手动实现基于堆的优先队列
如果需要更灵活的控制或学习目的，可以手动实现一个基于堆的优先队列。以下是最大堆的实现：
#include <iostream>
#include <vector>
#include <algorithm>
class PriorityQueue {
private:
std::vector<int> heap;
void heapifyUp(int index) {
while (index > 0) {
int parent = (index – 1) / 2;
if (heap[index] > heap[parent]) {
std::swap(heap[index], heap[parent]);
index = parent;
} else {
break;
}
}
}
void heapifyDown(int index) {
int left, right, largest;
while (true) {
left = 2 * index + 1;
right = 2 * index + 2;
largest = index;
if (left < heap.size() && heap[left] > heap[largest]) {
largest = left;
}
if (right < heap.size() && heap[right] > heap[largest]) {
largest = right;
}
if (largest != index) {
std::swap(heap[index], heap[largest]);
index = largest;
} else {
break;
}
}
}
public:
void push(int value) {
heap.push_back(value);
heapifyUp(heap.size() – 1);
}
int top() {
if (!heap.empty()) {
return heap[0];
}
throw std::runtime_error("Priority queue is empty");
}
void pop() {
if (heap.empty()) {
throw std::runtime_error("Priority queue is empty");
}
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
bool empty() {
return heap.empty();
}
};
int main() {
PriorityQueue pq;
pq.push(30);
pq.push(10);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
// 输出: 30 20 10
return 0;
}
性能优化
对于需要频繁操作的优先队列，可以考虑以下优化：
- 使用数组存储堆结构，减少内存分配开销。
- 在已知元素数量的情况下，预分配足够空间。
- 使用更高效的堆实现，如二项堆或斐波那契堆（适用于特定场景）。
自定义比较函数
当优先队列中的元素是自定义类型或需要特殊排序规则时，可以提供自定义比较函数：
#include <iostream>
#include <queue>
struct Task {
int priority;
std::string description;
bool operator<(const Task& other) const {
return priority < other.priority; // 最大堆
}
};
int main() {
std::priority_queue<Task> pq;
pq.push({3, "Low priority task"});
pq.push({1, "High priority task"});
pq.push({2, "Medium priority task"});
while (!pq.empty()) {
std::cout << pq.top().description << "\\n";
pq.pop();
}
return 0;
}
通过以上方法，可以在C++中高效地实现和使用优先队列。标准库的实现通常足够高效，但在特殊需求下，手动实现提供了更大的灵活性。
T6《按位异》
题目描述
你需要处理 n 组询问。
每组询问给定一个整数 x，你需要找两个整数 a,b，满足：
- 0≤a,b≤x；
- a⊕b=x；
并使 a+b 尽可能大。请输出这个最大值。
其中 ⊕ 表示按位异或：对应二进制位不同则为 1，相同则为 0。
输入格式
第一行一个正整数 n，表示询问组数。 接下来 n 行，每行一个整数 x。
接下来有n行数字，每行有一个整数x
输出格式
输出 n 行，每行一个整数，表示对应询问的答案。
思路
这道题需要运用贪心的思想，如果x的第i位是一，如果给A会爆则给b,如果是0则都为1；
代码如下
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T–){
int s;
cin>>s;
long long ans = 0;
long long a = 0,b = 0;
for(int i = 30;i>=0;i–){
if(s&(1<<i)){
if(a == 0)a|=(1<<i);
else b|=(1<<i);
}else{
if((a|(1<<i))<=s){
a|=(1<<i);
b|=(1<<i);
}
}
ans = a+b;
}
cout<<ans<<endl;
}
return 0;
}
