ACM板子总结¶

#include <iostream>
using namespace std;

int main() {
    int n = 6;                     // 数组长度
    int a[] = {0, 2, 4, 6, 8, 10, 12}; // 数组，a[0]占位
    int x = 8;                     // 要查找的目标值
    int l = 1, r = n;              // 左边界l，右边界r
    int pos = -1;                  // 存储目标值下标，默认-1表示未找到
    while (l <= r) {               // 循环直到左右边界重叠或越界
        int m = (l + r) / 2;       // 中间位置m
        if (a[m] == x) {           // 找到目标值
            pos = m;               // 记录下标
            break;                 // 退出循环
        } else if (a[m] < x) l = m + 1; // 目标值在右区间
        else r = m - 1;            // 目标值在左区间
    }
    if (pos != -1) cout << "Found at: " << pos << endl;
    else cout << "Not found" << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
long long c;
const int N = 2e5 + 10;
int a[N];
long long check(int m){
    long long s = 0;
    for(int i = 1;i<=n;i++){
        s += (a[i] + 2LL * m) * (a[i] + 2LL * m); 
    if (s > c) return s; 
    }
    return s;
}


int main() {
    cin>>n>>c;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }

    int l = 1, r = 1e6;          
    int pos = -1;              
    while (l <= r) {           
        int m = (l + r) / 2;
        long long s  = check(m);  
        if (s == c) {       
            pos = m;
            break;              
        } else if (s < c) l = m + 1; 
        else r = m - 1;        
    }

cout<<pos;


    return 0;
}

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
(满足性质的是右“半”边)
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
(满足性质的是左“半”边)
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

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

const int N = 1e5 + 10;
int sum[N],a[N];
int n,m;
int  l,r;

int main() {

    cin>>n>>m;  //n为数组a的长度，m为询问次数

    for(int i = 1;i<=n;i++){
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    for(int i = 1;i<=m;i++){
        cin>>l>>r;   ////左区间和右区间
        cout<<sum[r] - sum[l-1]<<endl; //区间[l, r]内元素的和,非下标
    }

    return 0;
}

#include <iostream> 
using namespace std;

int main() {
    const int N = 1e5 + 10;     //N表示数组的最大长度
    int a[N] = {0}, b[N] = {0};
    int n, m;                   //n为数组a的长度，m为询问次数
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];            
        b[i] = a[i] - a[i - 1]; // 构建差分数组b
    }

    while (m--) {
        int l, r, c;            // l 和 r 表示操作的区间 [l, r]，c 表示加的值
        cin >> l >> r >> c; 
        b[l] += c;
        if (r + 1 <= n) {       // 如果 r+1 没有越界
            b[r + 1] -= c;
        }
    }
    // 根据差分数组 b 计算最终的数组a
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + b[i]; // 根据前缀和恢复原数组a
    }

    for (int i = 1; i <= n; i++) {
        cout << a[i] << " "; 
    }
    cout << endl;
    return 0; 
}

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

const int N = 1e9+100;
int s[N][N],a[N][N];
int x,y,w;
int main() {

    int n,m,q;
    cin>>n>>m>>q;

    for(int i = 1;i<=n;i++){
        for(int j =1;j<=m;j++){
            cin>>a[i][j];
            s[i][j] = s[i-1][j]+ s[i][j-1]+a[i][j] - s[i-1][j-1];//二维前缀和模板数组
        }
    }

    int x1,y1,x2,y2;
    for(int i = 1;i<=q;i++){
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]<<endl; //求从x1,y1到x2,y2的区域和
    }

    return 0;
}

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

const int N = 1000 + 10;
int a[N][N], b[N][N];
int n, m, q;

void insert(int x1, int y1, int x2, int y2, int c) {     
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
    }
    while (q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

do {   } while (next_permutation(v.begin(), v.end()));

cin.ignore(numeric_limits<streamsize>::max(), '\n');

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

int main() {
    int m, n;           //m表示缓存最大容量，n表示询问次数
    cin >> m >> n;      // 读取缓存容量 m 和页面访问次数 n
    deque<int> q(m);  // 创建一个大小为 m 的双端队列，用来模拟缓存，默认大小为 m
    int a;  // 用来存储当前访问的页面
    int cnt = 0;  // 用来记录页面缺失的次数
    int qq[1010] = {0};  // 定义一个数组 qq，长度为 1010，初始化所有元素为 0，用来记录哪些页面在缓存中
    for (int i = 1; i <= n; i++) {  // 遍历所有页面访问
        cin >> a;  // 读取当前访问的页面号
        if (!qq[a]) {  // 如果页面 a 不在缓存中
            cnt++;  // 页面缺失，增加缺页次数
            if (q.size() == m) {  // 如果缓存已满
                int x = q.front();  // 获取队列的第一个元素，即最久未使用的页面
                q.pop_front();  // 从队列中移除最久未使用的页面
                qq[x] = 0;  // 更新数组 qq，标记页面 x 不在缓存中
            }
            q.push_back(a);  // 将当前页面 a 加入队列（缓存）
            qq[a] = 1;  // 更新数组 qq，标记页面 a 已经在缓存中
        }
    }
    cout << cnt;  // 输出缺页次数
    return 0;  // 程序结束
}

string arr[100];
getline(cin, arr[i]);

bool cmp(类型 a, 类型 b) {
    // 第一条件: 比较 a 和 b
    if (条件1) {
        return 排序规则1;
    }
    // 第二条件: 如果第一条件不满足，比较 a 和 b
    if (条件2) {
        return 排序规则2;
    }
    // 第三条件: 如果前面所有条件都不满足，继续比较
    if (条件3) {
        return 排序规则3;
    }
    // 默认返回
    return 排序规则默认;
}

index = (index + 1) % n; // 因为是循环，使用%运算确保数组循环

cout << setfill('0') << setw(2) << sum;
cout << fixed << setprecision(2) << num << endl;

cout << bitset<32>(n) << endl;
cin >> oct >> n; // 从输入以八进制形式读取一个整数
cout << dec << n; // 以十进制形式输出该整数

char a[100];
int b = strlen(a);

string a;
int b = a.size();

#define 宏名 替换内容

using ll = long long;

typedef long long ll;

#include <iostream>
#include <algorithm> // 包含 sort 函数
using namespace std;

struct Point {
    int x, y;
};

// 自定义比较函数
bool cmp(const Point &a, const Point &b) {
    if (a.x == b.x) {
        return a.y < b.y;  // 如果 x 相同，按 y 排序
    }
    return a.x < b.x;  // 否则按 x 排序
}

int main() {
    Point points[3];
    // 通过 cin 输入结构体数组
    for (int i = 0; i < 3; i++) {
        cin >> points[i].x >> points[i].y;
    }
    // 使用自定义比较函数进行排序
    sort(points, points + 3, cmp);
    // 输出排序后的数组
    for (int i = 0; i < 3; ++i) {
        cout << "points[" << i << "]: x=" << points[i].x << ", y=" << points[i].y << endl;
    }
    return 0;
}

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

vector<int> vec = {1, 3, 3, 5, 7, 9};
// 查找第一个不小于 3 的位置（即第一个 3）
auto lb = lower_bound(vec.begin(), vec.end(), 3);
// 查找第一个大于 3 的位置（即第一个大于 3 的元素位置）
auto ub = upper_bound(vec.begin(), vec.end(), 3);
//lb 的位置是 vec.begin() + 1，即指向第一个 3。
//ub 的位置是 vec.begin() + 3，即指向第一个大于 3 的元素 5。
cout << "lb: " << (lb - vec.begin()) << endl;  // 输出 1，表示第一个 3
cout << "ub: " << (ub - vec.begin()) << endl;  // 输出 3，表示 5

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

long long a[N], b[N];

int main() {
    int n, m, sum;
    cin >> n >> m >> sum;

    // 输入数组 a[] 和 b[]
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    // 对数组 b[] 进行排序
    sort(b, b + m);

    // 遍历数组 a[]，对于每个 a[i] 使用二分查找
    for (int i = 0; i < n; i++) {
        long long target = sum - a[i];
        // 在 b[] 中查找 target
        int idx = lower_bound(b, b + m, target) - b;

        // 检查是否找到并且满足 a[i] + b[idx] == sum
        if (idx < m && b[idx] == target) {
            cout << i << " " << idx << endl;
            return 0;  // 找到后直接退出
        }
    }

    // 如果没有找到符合条件的 pair
    cout << -1 << endl;
    return 0;
}

max(x, y);  // 返回 x 和 y 较大值
min(x, y);  // 返回 x 和 y 较小值

#include <iostream>
#include <cstring> // 包含 C 字符串处理函数 strstr
using namespace std;

int main() {
    //子串截取
    string s = "Hello, World!";
    string sub = s.substr(7, 5);    // 从下标 7 开始截取 5 个字符
    s.erase(7, 10);                 // 从下标7 删除 10 个字符

    //查找子串
    size_t pos = s.find("World");   // 查找 "World" 的位置，一般返回第一个字母起始下标
    if (pos != string::npos) {
    cout << "Found at: " << pos << endl; // 如果找到，输出位置
    }

    // 定义两个字符数组，用于存储输入的源字符串和需要查找的子串
    char str[100];                  // 源字符串
    char target[100];               // 子串
    cin.getline(str, 100);          // 使用 getline 读取一整行字符串
    cin.getline(target, 100);       // 输入需要查找的子串
    const char* pos = strstr(str, target);  // 使用 strstr 函数查找子串在源字符串中的位置
     // 判断是否找到子串
    if (pos != nullptr) {
        // 如果找到，计算子串的起始下标，并输出
        cout << "Substring found at index: " << (pos - str) << endl;  
    } else {
        cout << "Substring not found!" << endl;  
    }
    return 0; 
}

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

int main() {
    int n, x;           // n为数组大小，x为目标和
    cin >> n >> x;      // 输入n和目标和x
    int a[n + 1];       // 数组，从1开始存储
    for (int i = 1; i <= n; i++) {
        cin >> a[i];    // 输入数组
    }
    sort(a + 1, a + n + 1); // 排序数组
    int i = 1, j = n;   // 双指针初始化
    while (i < j) {
        int s = a[i] + a[j]; // 当前两个数的和
        if (s == x) {
            cout << a[i] << " " << a[j] << endl;
            break;
        } else if (s < x) {
            i++;        // 左指针右移
        } else {
            j--;        // 右指针左移
        }
    }
    if (i >= j) {
        cout << "No solution" << endl; // 没有找到满足条件的数对
    }
    return 0;
}

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

int main()
{
    char str[1000];
    // 使用 gets() 读取一行字符串（注意：gets() 已被弃用，推荐使用 fgets() 或 getline()）
    gets(str);

    // 获取字符串的长度
    int n = strlen(str);

    // 遍历字符串，逐个输出单词
    for (int i = 0; i < n; i++)
    {
        int j = i;
        // 指针 j 扫描字符串，直到遇到空格或者字符串结束
        while (j < n && str[j] != ' ') 
            j++; // j 指向当前单词结束的位置（空格处或者字符串末尾）

        // 输出当前单词（从 i 到 j-1）
        for (int k = i; k < j; k++) 
            cout << str[k];
        cout << endl; // 输出换行符，每个单词单独占一行

        // 将 i 移动到 j 处，即空格后的第一个字符位置
        // 注意：这里 i 在 for 循环的自增中会自动 +1，因此如果想跳过空格，
        // 可能需要额外处理多个连续空格的情况（当前代码假设单词间仅有一个空格）
        i = j;
    }
    return 0;
}

//数字反转,消除原数末尾0,但中间0不动.
int flag = 1;
for(int i = p-1;i>=0;i--){
    if(a[i]=='0' && flag==1 && i>0){
        continue;
    }
    flag = 0;
    cout<<a[i];

}

#include<bits/stdc++.h>
using namespace std;
string s;
string zican(string sub){
    string a = "";
    a+=sub[0];

    for(int i = 0;i<sub.size()-1;i++){
        if(sub[i+1]!=sub[i]){
            a += sub[i+1];
        }
    }
    return a;

}
bool huiwen(string subb){
    int i = 0;
    int j = subb.size()-1;
    while(i<=j){
        if(subb[i]!=subb[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
}

int main() {
    long long sumj = 0;
    long long sumo = 0;
    cin>>s;
    int n = s.size();
    for(int i = 0;i<n;i++){
        for(int j = 1;i+j<=n;j++){
            string sub = s.substr(i,j);
            string subb = zican(sub);
            if(huiwen(subb)){
                if(j%2==0){
                    sumo++;
                }else{
                    sumj++;
                }
            }
        }
    }
    cout<<sumo<<" "<<sumj;

    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    const char* str = "Hello, world!";
    char* pos = strchr(str, 'o');  // 查找字符 'o'

    if (pos != nullptr) {
        cout << "Found 'o' at position: " << (pos - str) << endl;  // 计算相对位置
    } else {
        cout << "'o' not found!" << endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char str[] = "Hello, world, C++!";
    char* token = strtok(str, ", ");  // 以 ", " 作为分隔符

    while (token != nullptr) {
        cout << "Token: " << token << endl;
        token = strtok(nullptr, ", ");  // 继续分割
    }

    return 0;
}

#include <iostream>
using namespace std;

// 快速幂函数：计算 a^b
int qp(int a, int b) {
    int r = 1;         // r 存储结果，初始为 1
    while (b > 0) {    // 当指数 b 大于 0 时继续循环
        if (b % 2)     // 如果 b 是奇数
            r *= a;    // 将当前基数累乘到结果
        a *= a;        // 基数自乘
        b /= 2;        // 指数减半
    }
    return r;          // 返回计算结果
}

int main() {
    int a, b;
    cout << "输入底数和指数：";
    cin >> a >> b;              // 输入底数 a 和指数 b
    cout << a << "^" << b << " = " << qp(a, b) << endl;
    return 0;
}



------------------------------------------------------------------------------

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

// 定义长整型别名，便于后续使用
typedef long long LL;

// 快速幂函数，计算 (a^k) % p
int qmi(int a, int k, int p)
{
    int res = 1; // 初始化结果为 1
    while (k) // 当指数 k 不为 0 时循环
    {
        if (k & 1) // 如果 k 是奇数，累乘当前的 a 并取模
            res = (LL)res * a % p;
        k /= 2; // 指数 k 右移一位，相当于整除 2
        a = (LL)a * a % p; // 底数自乘并取模
    }
    return res; // 返回计算结果
}

int main()
{
    int n;
    cin >> n; // 读取测试用例数量
    while (n--) // 循环处理每个测试用例
    {
        int a, k, p;
        cin >> a >> k >> p; // 读取底数 a，指数 k 和模数 p
        cout << qmi(a, k, p) << endl; // 输出快速幂结果
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;

int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        k/=2;
        a=(LL)a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}

vector<int> vec = {1, 2, 3, 4, 5};
// 计算 vec 中所有元素的和，初始值为 0
int sum = accumulate(vec.begin(), vec.end(), 0);