贪心

区间选点

给定N个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (range[i].l > ed){
            res ++ ;
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}

最大不相交区间数量

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return r < W.r;
    }
}range[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l){
            res ++ ;
            ed = range[i].r;
        }
    printf("%d\n", res);
    return 0;
}

区间分组

给定N个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输出最小组数。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return l < W.l;
    }
}range[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++ ){
        auto r = range[i];
        if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else{
            heap.pop();
            heap.push(r.r);
        }
    }
    printf("%d\n", heap.size());
    return 0;
}

区间覆盖

给定N个闭区间ai,bi]以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l, r;
    bool operator< (const Range &W)const{
        return l < W.l;
    }
}range[N];
int main(){
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);
    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ ){
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st){
            r = max(r, range[j].r);
            j ++ ;
        }
        if (r < st){
            res = -1;
            break;
        }
        res ++ ;
        if (r >= ed){
            success = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    if (!success) res = -1;
    printf("%d\n", res);
    return 0;
}

合并果子

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- ){
        int x;
        scanf("%d", &x);
        heap.push(x);
    }
    int res = 0;
    while (heap.size() > 1){
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    printf("%d\n", res);
    return 0;
}

排队打水

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int t[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);
    sort(t, t + n);
    reverse(t, t + n);
    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * i;
    printf("%lld\n", res);
    return 0;
}

货仓选址

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    sort(q, q + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);
    printf("%d\n", res);
    return 0;
}

耍杂技的牛

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int n;
PII cow[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int s, w;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ ){
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s);
        sum += w;
    }
    printf("%d\n", res);
    return 0;
}

判断子序列

给定一个长度为nn的整数序列a1,a2,…,an以及一个长度为m mm的整数序列b1,b2,…,bm。

请你判断a序列是否为b序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列a1,a3,a5} 是序列a1,a2,a3,a4,a5} 的一个子序列。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    int i = 0, j = 0;
    while (i < n && j < m){
        if (a[i] == b[j]) i ++ ;
        j ++ ;
    }
    if (i == n) puts("Yes");
    else puts("No");
    return 0;
}

表达式求值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}
int main(){
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ ){
        auto c = str[i];
        if (isdigit(c)){
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')'){
            while (op.top() != '(') eval();
            op.pop();
        }
        else{
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

上机课

进制转换

将一个长度最多为 30 位数字的十进制非负整数转换为二进制数输出。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int> A, int b){
    vector<int> C;
    for (int i = A.size() - 1, r = 0; i >= 0; i -- ){
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string s;
    while (cin >> s){
        vector<int> A;
        for (int i = 0; i < s.size(); i ++ )
            A.push_back(s[s.size() - i - 1] - '0');
        string res;
        if (s == "0") res = "0";
        else{
            while (A.size()){
                res += to_string(A[0] % 2);
                A = div(A, 2);
            }
        }
        reverse(res.begin(), res.end());
        cout << res << endl;
    }
    return 0;
}

3374. 进制转换2

将 M 进制的数 X 转换为 N 进制的数输出。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int a, b;
    string s;
    cin >> a >> b >> s;
    vector<int> A;
    for (int i = 0; i < s.size(); i ++ ){
        char c = s[s.size() - 1 - i];
        if (c >= 'A') A.push_back(c - 'A' + 10);
        else A.push_back(c - '0');
    }
    string res;
    if (s == "0") res = "0";
    else{
        while (A.size()){
            int r = 0;
            for (int i = A.size() - 1; i >= 0; i -- ){
                A[i] += r * a;
                r = A[i] % b;
                A[i] /= b;
            }
            while (A.size() && A.back() == 0) A.pop_back();
            if (r < 10) res += to_string(r);
            else res += r - 10 + 'a';
        }
        reverse(res.begin(), res.end());
    }
    cout << res << endl;
    return 0;
}

重排链表

class Solution {
public:
    void rearrangedList(ListNode* head) {
        if (!head->next) return;
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;
        int left = (n + 1) / 2;  // 前半段的节点数
        auto a = head;
        for (int i = 0; i < left - 1; i ++ ) a = a->next;
        auto b = a->next, c = b->next;
        a->next = b->next = NULL;
        while (c) {
            auto p = c->next;
            c->next = b;
            b = c, c = p;
        }
        for (auto p = head, q = b; q;) {
            auto o = q->next;
            q->next = p->next;
            p->next = q;
            p = p->next->next;
            q = o;
        }
    }
};

打印日期

给出年份 y 和一年中的第 d 天，算出第 d 天是几月几号。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int months[13] = {
    0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year){  // 闰年返回1，平年返回0
    if (year % 4 == 0 && year % 100 || year % 400 == 0)
        return 1;
    return 0;
}
int get_days(int y, int m){  // y年m月有多少天
    if (m == 2) return months[m] + is_leap(y);
    return months[m];
}
int main(){
    int y, s;
    while (cin >> y >> s){
        int m = 1, d = 1;
        s -- ;
        while (s -- ){
            if ( ++ d > get_days(y, m)){
                d = 1;
                if ( ++ m > 12){
                    m = 1;
                    y ++ ;
                }
            }
        }
        printf("%04d-%02d-%02d\n", y, m, d);
    }
    return 0;
}

日期累加

设计一个程序能计算一个日期加上若干天后是什么日期。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int months[13] = {
    0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year){
    if (year % 4 == 0 && year % 100 || year % 400 == 0)
        return 1;
    return 0;
}
int get_days(int y, int m){
    if (m == 2) return months[m] + is_leap(y);
    return months[m];
}
int get_year_days(int y, int m){
    if (m <= 2) return 365 + is_leap(y);
    return 365 + is_leap(y + 1);
}
int main(){
    int T;
    cin >> T;
    while (T -- ){
        int y, m, d, a;
        cin >> y >> m >> d >> a;
        if (m == 2 && d == 29) a --, m = 3, d = 1;
        while (a > get_year_days(y, m)){
            a -= get_year_days(y, m);
            y ++ ;
        }
        while (a -- ){
            if ( ++ d > get_days(y, m)){
                d = 1;
                if ( ++ m > 12){
                    m = 1;
                    y ++ ;
                }
            }
        }
        printf("%04d-%02d-%02d\n", y, m, d);
    }
    return 0;
}

二叉树的带权路径长度

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和，也就是每个叶结点的深度与权值之积的总和。

class Solution {
public:
    int dfs(TreeNode* root, int depth) {
        if (!root) return 0;
        if (!root->left && !root->right) return root->val * depth;
        return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
    }
    int pathSum(TreeNode* root) {
        return dfs(root, 0);
    }
};

二叉排序树

你需要写一种数据结构，来维护一些数，其中需要提供以下操作：

插入数值 x。

删除数值 x。

输出数值 x 的前驱(前驱定义为现有所有数中小于 x 的最大的数)。

输出数值 x 的后继(后继定义为现有所有数中大于 x 的最小的数)。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e8;
struct TreeNode{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;
void insert(TreeNode* &root, int x){
    if (!root) root = new TreeNode(x);
    else if (x < root->val) insert(root->left, x);
    else insert(root->right, x);
}
void remove(TreeNode* &root, int x){
    if (!root) return;
    if (x < root->val) remove(root->left, x);
    else if (x > root->val) remove(root->right, x);
    else{
        if (!root->left && !root->right) root = NULL;
        else if (!root->left) root = root->right;
        else if (!root->right) root = root->left;
        else{
            auto p = root->left;
            while (p->right) p = p->right;
            root->val = p->val;
            remove(root->left, p->val);
        }
    }
}
int get_pre(TreeNode* root, int x){
    if (!root) return -INF;
    if (root->val >= x) return get_pre(root->left, x);
    return max(root->val, get_pre(root->right, x));
}
int get_suc(TreeNode* root, int x){
    if (!root) return INF;
    if (root->val <= x) return get_suc(root->right, x);
    return min(root->val, get_suc(root->left, x));
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int t, x;
        cin >> t >> x;
        if (t == 1) insert(root, x);
        else if (t == 2) remove(root, x);
        else if (t == 3) cout << get_pre(root, x) << endl;
        else cout << get_suc(root, x) << endl;
    }
    return 0;
}

表达式树

请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。

class Solution {
public:
    string dfs(TreeNode* root) {
        if (!root) return "";
        if (!root->left && !root->right) return root->val;
        return '(' + dfs(root->left) + root->val + dfs(root->right) + ')';
    }
    string expressionTree(TreeNode* root) {
        return dfs(root->left) + root->val + dfs(root->right);
    }
};

未出现过的最小正整数

给定一个长度为 n 的整数数组，请你找出未在数组中出现过的最小正整数。

class Solution {
public:
    int findMissMin(vector<int>& nums) {
        int n = nums.size();
        vector<bool> hash(n + 1);
        for (int x: nums)
            if (x >= 1 && x <= n)
                hash[x] = true;
        for (int i = 1; i <= n; i ++ )
            if (!hash[i])
                return i;
        return n + 1;
    }
};

三元组的最小距离

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int l, m, n;
int a[N], b[N], c[N];
int main(){
    scanf("%d%d%d", &l, &m, &n);
    for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]);
    LL res = 1e18;
    for (int i = 0, j = 0, k = 0; i < l && j < m && k < n;){
        int x = a[i], y = b[j], z = c[k];
        res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));
        if (x <= y && x <= z) i ++ ;
        else if (y <= x && y <= z) j ++ ;
        else k ++ ;
    }
    printf("%lld\n", res * 2);
    return 0;
}

众数

给定一个整数序列，其中包含 n 个非负整数，其中的每个整数都恰好有 m 位，从最低位到最高位，依次编号为 1∼m 位。

现在，请你统计该序列各个位的众数。

第 i 位的众数是指，在给定的 n 个整数的第 i 位上，出现次数最多的最小数字。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int s[6][10];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    while (n -- ){
        int x;
        scanf("%d", &x);
        for (int i = 0; i < m; i ++ ){
            s[i][x % 10] ++ ;
            x /= 10;
        }
    }
    for (int i = 0; i < m; i ++ ){
      int k = 0;
        for (int j = 0; j < 10; j ++ )
            if (s[i][k] < s[i][j])
                k = j;
        printf("%d\n", k);
    }
    return 0;
}

玛雅人的密码

玛雅人有一种密码，如果字符串中出现连续的 2012 四个数字就能解开密码。

给定一个长度为 N 的字符串，该字符串中只含有 0,1,2 三种数字。

可以对该字符串进行移位操作，每次操作可选取相邻的两个数字交换彼此位置。

请问这个字符串要移位几次才能解开密码。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int n;
int bfs(string start){
    queue<string> q;
    unordered_map<string, int> dist;
    dist[start] = 0;
    q.push(start);
    while (q.size()){
        auto t = q.front();
        q.pop();
        for (int i = 0; i < n; i ++ )
            if (t.substr(i, 4) == "2012")
                return dist[t];
        for (int i = 1; i < n; i ++ ){
            string r = t;
            swap(r[i], r[i - 1]);
            if (!dist.count(r)){
                dist[r] = dist[t] + 1;
                q.push(r);
            }
        }
    }
    return -1;
}
int main(){
    string start;
    cin >> n >> start;
    cout << bfs(start) << endl;
    return 0;
}

等差数列

有一个特殊的n行m列的矩阵 Aij，每个元素都是正整数，每一行和每一列都是独立的等差数列。

在某一次故障中，这个矩阵的某些元素的真实值丢失了，被重置为 0。

现在需要你想办法恢复这些元素，并且按照行号和列号从小到大的顺序（行号为第一关键字，列号为第二关键字，从小到大）输出能够恢复的元素。

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1010;
int n, m, a[N][N], r[N][4], c[N][4];
queue<int> q;
//给坐标[i, j]赋值为x
//同时判断第i 行是否有两个点，第j 列是否有两个点
void add(int i, int j, int x){
    a[i][j] = x;
    //如果第i 行一个点都没有，给定第一个点的值到r[i][0],列数为r[i][1]
    //其次如果第i 行没第二个点，给定第二个点的值到r[i][2],列数为r[i][3]，并且加入到bfs中
    //如果还有第三个点其实就不进行操作
    if(!r[i][0]) r[i][0] = x, r[i][1] = j;
    else if(!r[i][2]) r[i][2] = x, r[i][3] = j, q.push(i * 2 + 1);//如果是行扩展，加入奇数
    //对列进行同等操作
    if(!c[j][0]) c[j][0] = x, c[j][1] = i;
    else if(!c[j][2]) c[j][2] = x, c[j][3] = i, q.push(j * 2);//如果是列扩展，加入偶数
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            int x;
            scanf("%d",&x);
            if(x) add(i, j, x);//给[i, j] 赋值 x
        }
    vector<pii> ans;//frist 里面存[x, y]坐标，sceond里面存值
    while(q.size()){
        int now = q.front() / 2, f = q.front() % 2; q.pop();//取出行号或者列号
        if(f){//如果是行扩展
            int suf = (r[now][2] - r[now][0]) / (r[now][3] - r[now][1]);//得到等差值
            int start = r[now][0] - (r[now][1] * suf);//求得第一个点的值
            for(int i = 0; i < m; i++){
                if(!a[now][i]){//如果a[now][i]是0，将a[now][i]按照等差公式赋值
                    add(now, i, start + i * suf);//赋值
                    ans.push_back({now * 2000 + i, start + i * suf});//加入[坐标，值]答案数组中
                }
            }
        }
        else{//列扩展，以下同理
            int suf = (c[now][2] - c[now][0]) / (c[now][3] - c[now][1]);
            int start = c[now][0] - (c[now][1] * suf);
            for(int i = 0; i < n; i++){
                if(!a[i][now]){
                    add(i, now, start + i * suf);
                    ans.push_back({i * 2000 + now, start + i * suf});
                }
            }
        }
    }
    sort(ans.begin(), ans.end());//按照坐标排序
    for(auto [xy, val] : ans){
        printf("%d %d %d\n",xy/2000+1,xy%2000+1,val);//输出答案
    }
    return 0;
}

3441. 重复者

给定一个仅包含一种字符和空格的模板，将之不断重复扩大。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<string> p;
vector<string> g(int k){
    if (k == 1) return p;
    auto s = g(k - 1);
    int m = s.size();
    vector<string> res(n * m);
    for (int i = 0; i < n * m; i ++ )
        res[i] = string(n * m, ' ');
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (p[i][j] != ' ')
                for (int x = 0; x < m; x ++ )
                    for (int y = 0; y < m; y ++ )
                        res[i * m + x][j * m + y] = s[x][y];
    return res;
}
int main(){
    while (cin >> n, n){
        p.clear();
        getchar();  // 读掉n后的回车
        for (int i = 0; i < n; i ++ ){
            string line;
            getline(cin, line);
            p.push_back(line);
        }
        int k;
        cin >> k;
        auto res = g(k);
        for (auto& s: res) cout << s << endl;
    }
    return 0;
}

3382. 整数拆分

一个整数总可以拆分为 2 的幂的和

用 f(n) 表示 n 的不同拆分的种数，例如 f(7)=6。

要求编写程序，读入 n，输出 f(n)mod1e9

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010, MOD = 1e9;
int n;
int f[N];
int main(){
    scanf("%d", &n);
    f[0] = 1;
    for (int i = 1; i <= n; i *= 2)
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % MOD;
    cout << f[n] << endl;
    return 0;
}

位操作练习

给出两个不大于 65535 的非负整数，判断其中一个的 16 位二进制表示形式，是否能由另一个的 16 位二进制表示形式经过循环左移若干位而得到。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int a, b;
    while (cin >> a >> b){
        string x, y;
        for (int i = 15; i >= 0; i -- ){
            x += to_string(a >> i & 1);
            y += to_string(b >> i & 1);
        }
        y += y;
        if (y.find(x) != -1) puts("YES");
        else puts("NO");
    }
    return 0;
}

最小面积子矩阵

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 100000;
int n, m, k;
int s[N][N];
int main(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ){
            cin >> s[i][j];
            s[i][j] += s[i - 1][j];
        }
    int res = INF;
    for (int x = 1; x <= n; x ++ )
        for (int y = x; y <= n; y ++ ){
            for (int i = 1, j = 1, sum = 0; i <= m; i ++ ){
                sum += s[y][i] - s[x - 1][i];
                while (sum - (s[y][j] - s[x - 1][j]) >= k){
                    sum -= s[y][j] - s[x - 1][j];
                    j ++ ;
                }
                if (sum >= k) res = min(res, (y - x + 1) * (i - j + 1));
            }
        }
    if (res == INF) res = -1;
    cout << res << endl;
    return 0;
}

矩阵幂

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n, m;
int w[N][N];
void mul(int c[][N], int a[][N], int b[][N]){
    static int tmp[N][N];
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            for (int k = 0; k < n; k ++ )
                tmp[i][j] += a[i][k] * b[k][j];
    memcpy(c, tmp, sizeof tmp);
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];
    int res[N][N] = {0};
    for (int i = 0; i < n; i ++ ) res[i][i] = 1;
    while (m -- ) mul(res, res, w);
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < n; j ++ )
            cout << res[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

C翻转

给定一个 5×5 的矩阵，对其进行翻转操作。

操作类型共四种，具体形式如下：

1 2 x y，表示将以第 x 行第 y 列的元素为左上角，边长为 2 的子矩阵顺时针翻转 90 度。

1 3 x y，表示将以第 x 行第 y 列的元素为左上角，边长为 3 的子矩阵顺时针翻转 90 度。

2 2 x y，表示将以第 x 行第 y 列的元素为左上角，边长为 2 的子矩阵逆时针翻转 90 度。

2 3 x y，表示将以第 x 行第 y 列的元素为左上角，边长为 3 的子矩阵逆时针翻转 90 度。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5;
int n;
int g[N][N];
void rotate(int x, int y, int m){
    int w[N][N];
    memcpy(w, g, sizeof g);
    for (int i = 0; i < m; i ++ )
        for (int j = 0, k = m - 1; j < m; j ++, k -- )
            w[i][j] = g[x + k][y + i];
    for (int i = 0; i < m; i ++ )
        for (int j = 0; j < m; j ++ )
            g[x + i][y + j] = w[i][j];
}
int main(){
    for (int i = 0; i < 5; i ++ )
        for (int j = 0; j < 5; j ++ )
            cin >> g[i][j];
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    x --, y -- ;
    if (a == 1) rotate(x, y, b);
    else{
        for (int i = 0; i < 3; i ++ )
            rotate(x, y, b);
    }
    for (int i = 0; i < 5; i ++ ){
        for (int j = 0; j < 5; j ++ )
            cout << g[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

最长平衡串

给定一个只含 01 的字符串，找出它的最长平衡子串的长度。

如果一个 01 字符串包含的 0 和 1 的个数相同，则称其为平衡串。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1000010;
int n;
char str[N];
int main(){
    scanf("%s", str + 1);
    unordered_map<int, int> hash;
    n = strlen(str + 1);
    int res = 0;
    hash[0] = 0;
    for (int i = 1, s = 0; i <= n; i ++ ){
        if (str[i] == '0') s ++ ;
        else s -- ;
        if (hash.count(s)) res = max(res, i - hash[s]);
        else hash[s] = i;
    }
    printf("%d\n", res);
    return 0;
}

Python

差

读取四个整数 A,B,C,D，并计算 (A×B−C×D) 的值。

a = int(input())
b = int(input())
c = int(input())
d = int(input())
print("DIFERENCA = %d" % (a * b - c * d))

倍数

a, b = map(int, input().split(' '))
if a % b == 0 or b % a == 0:
    print("Sao Multiplos")
else:
    print("Nao sao Multiplos")

零食

x, y = map(int, input().split(' '))
prices = [0, 4, 4.5, 5, 2, 1.5]
print("Total: R$ %.2lf" % (prices[x] * y))

字符串长度

print(len(input()))

递增序列

while True:
    x = int(input())
    if x == 0:
        break
    for i in range(1, x + 1):
        print(i, end=' ')
    print()

质数

import math
n = int(input())
for i in range(n):
    x = int(input())
    for j in range(2, int(math.sqrt(x)) + 1):
        if x % j == 0:
            print(x, "is not prime")
            break
    else:
        print(x, "is prime")

数组的右上

t = input()
s, c = 0, 0
for i in range(12):
    d = list(map(float, input().split(' ')))
    for j in range(12):
        if j > i:
            s += d[j]
            c += 1
if t == "M":
    s /= c
print("%.1f" % (s))

蛇形矩阵

n, m = map(int, input().split())
res = [[0 for j in range(m)] for i in range(n)]
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
x, y, d = 0, 0, 1
for i in range(1, n * m + 1):
    res[x][y] = i
    a, b = x + dx[d], y + dy[d]
    if a < 0 or a >= n or b < 0 or b >= m or res[a][b]:
        d = (d + 1) % 4
        a, b = x + dx[d], y + dy[d]
    x, y = a, b
for i in range(n):
    for j in range(m):
        print(res[i][j], end = ' ')
    print()

排列

n = int(input())
path = [0 for i in range(n)]
used = [False for i in range(n)]
def dfs(u):
    if u == n:
        for i in range(n):
            print(path[i] + 1, end=' ')
        print()
    else:
        for i in range(n):
            if not used[i]:
                path[u] = i
                used[i] = True
                dfs(u + 1)
                used[i] = False
                path[u] = 0
dfs(0)

a+b

#输入无行数限制
while True:
    try:
        a, b = map(int, input().split())
        print(a + b)
    except:
        break

#先输入行数
n = int(input())
while n:
    a, b = map(int, input().split())
    print(a + b)
    n -= 1

#输入00结束
while True:
    a, b = map(int, input().split())
    if a != 0 and b != 0: print(a + b)
    else: break

行内数组求和

#给定数组长度,输入0停止
while True:
    arr = list(map(int, input().split()))
    if arr[0] == 0: break
    else: print(sum(arr[1:]))

#给定总数组数量
n = int(input())
while n:
    print(sum(list(map(int, input().split()))[1:]))
    n -= 1

#不给定总数组数量
while True:
    try:  # 对于没有行提示的，使用try except就很简单
        print(sum(list(map(int, input().split()))[1:]))
    except:
        break

# 不给行数和每行数组长度
while True:
    try:
        print(sum(list(map(int, input().split()))))
    except:
        break

字符串排序

#给定字符数量
n = int(input())
arr = input().split()
arr.sort()
print(' '.join(arr))

#不给定字符数量
while True:
    try:
        arr = input().split()
        arr.sort()
        print(" ".join(arr))
    except:
        break

#逗号分割
while True:
    try:
        arr = input().split(",")
        arr.sort()
        print(",".join(arr))
    except:
        break

Acwing 算法基础课 c++模板整理（附python语法基础题）（三）

贪心