贪心
区间选点
给定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
