100
环中最长子串/最长子字符串长度（一）
#include using namespace std; string str; int n,i = 0;int main(){ cin >> str; while (str[i] != '\0'){if(str[i] == 'o'){n ++;}i ++;}printf("%d\n", n % 2 ? i - 1 : i);return 0;}#include #include class CharacterCounter {private:std::string str;int n;int i;public:CharacterCounter() : n(0), i(0) {}void readInput() {std::cin >> str;}void countCharacters() {while (str[i] != '\0') {if (str[i] == 'o') {n++;}i++;}}void printResult() const {std::cout << (n % 2 ? i - 1 : i) << std::endl;}};int main() {CharacterCounter characterCounter;characterCounter.readInput();characterCounter.countCharacters();characterCounter.printResult();return 0;}螺旋数字矩阵
#include #include using namespace std;//int res[100][100];int main(){int nums,n;cin >>nums >> n;int m = (nums - 1) / n + 1;vector<vector> res(n, vector(m, "*"));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for(int x = 0, y = 0, d = 0, k = 1; k <= nums; k ++){res[x][y] = to_string(k);int a = x + dx[d], b = y + dy[d];//a，b表示下一个位置if(a = n || b = m || res[a][b] != "*"){d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;}for(int i = 0; i < n; i ++){for(int j = 0; j < m; j++) cout << res[i][j] << ' ';cout << endl;}return 0;}#include #include #include class SpiralMatrix {private:int nums;int n;int m;std::vector<std::vector> res;public:SpiralMatrix() : nums(0), n(0), m(0) {}void readInput() {std::cin >> nums >> n;m = (nums - 1) / n + 1;res.resize(n, std::vector(m, "*"));generateSpiralMatrix();}void generateSpiralMatrix() {int dx[] = {0, 1, 0, -1};int dy[] = {1, 0, -1, 0};for (int x = 0, y = 0, d = 0, k = 1; k <= nums; k++) {res[x][y] = std::to_string(k);int a = x + dx[d], b = y + dy[d];if (a = n || b = m || res[a][b] != "*") {d = (d + 1) % 4;a = x + dx[d];b = y + dy[d];}x = a;y = b;}}void printResult() const {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cout << res[i][j] << ' ';}std::cout << std::endl;}}};int main() {SpiralMatrix spiralMatrix;spiralMatrix.readInput();spiralMatrix.printResult();return 0;}最富裕的小家庭
#include #include using namespace std;int n; // 树的节点数vector a; // 存储每个节点的权值vector fa; // 存储每个节点的父节点vector<vector> e; // 存储树的边关系int main() {// 读入节点数cin >> n;// 初始化向量 a，用于存储每个节点的权值a.resize(n + 1);// 读入每个节点的权值for (int i = 1; i > a[i];}// 初始化向量 fa，用于存储每个节点的父节点// 初始化向量 e，用于存储树的边关系fa.resize(n + 1);e.resize(n + 1);// 读入树的边关系，构建树结构for (int i = 1; i > x >> y;fa[y] = x; // y 是 x 的子节点，记录父节点信息e[x].push_back(y); // 将 y 添加到 x 的子节点列表中}int ans = 0; // 存储最大权值和// 遍历每个节点，计算以当前节点为根的子树的权值和for (int i = 1; i <= n; i++) {int sum = a[i]; // 初始化 sum 为当前节点的权值for (int j = 0; j < e[i].size(); j++) {// 将当前节点的每个子节点的权值加到 sum 中sum += a[e[i][j]];}ans = max(ans, sum); // 更新最大权值和}// 输出结果cout << ans << endl;return 0;}#include #include class TreeNode {public:int weight;int parent;std::vector children;TreeNode() : weight(0), parent(0) {}};class Tree {private:int n; // 树的节点数std::vector nodes;public:Tree() {}void readInput() {// 读入节点数std::cin >> n;// 初始化每个节点nodes.resize(n + 1);// 读入每个节点的权值for (int i = 1; i > nodes[i].weight;}// 读入树的边关系，构建树结构for (int i = 1; i > x >> y;nodes[y].parent = x;nodes[x].children.push_back(y);}}int calculateMaxWeightSum() const {int maxWeightSum = 0;// 遍历每个节点，计算以当前节点为根的子树的权值和for (int i = 1; i <= n; i++) {int sum = nodes[i].weight; // 初始化 sum 为当前节点的权值for (int j = 0; j < nodes[i].children.size(); j++) {// 将当前节点的每个子节点的权值加到 sum 中sum += nodes[nodes[i].children[j]].weight;}maxWeightSum = std::max(maxWeightSum, sum); // 更新最大权值和}return maxWeightSum;}};int main() {Tree tree;tree.readInput();int result = tree.calculateMaxWeightSum();// 输出结果std::cout << result << std::endl;return 0;}找座位
#include using namespace std;int main() {int res = 0;string str;cin >> str;for (int i = 0; i < str.length(); i++) {if (str[i] == '0') {//空位是第一位或左边有空位bool left = i == 0 || str[i - 1] == '0';// 空位是最后一位或右边有空位bool right = i == str.length() - 1 || str[i + 1] == '0';// 两者都满足if (left && right) {res++;str[i] = '1';// 坐一个人i++;}}}cout << res << endl;return 0;}#include #include class SeatingArrangement {private:std::string seating;int count;public:SeatingArrangement(const std::string& str) : seating(str), count(0) {}void findAndFillEmptySeats() {for (int i = 0; i < seating.length(); i++) {if (seating[i] == '0') {bool left = i == 0 || seating[i - 1] == '0';bool right = i == seating.length() - 1 || seating[i + 1] == '0';if (left && right) {count++;seating[i] = '1';i++;}}}}void printResult() const {std::cout << count <> str;SeatingArrangement seatingArrangement(str);seatingArrangement.findAndFillEmptySeats();seatingArrangement.printResult();return 0;}密码输入检测
#include using namespace std;int dx, xx, sz, n;bool check(string &str){n = str.size();if(n = 'a' && ch = 'A' && ch = '0' && ch = 1 && dx >= 1 && sz >= 1 && sz + xx + dx > str;for(auto &ch : str){if(ch == '<' ) {if(res.size()) res.pop_back();}else res.push_back(ch);}string flag = "false";if(check(res)) flag = "true";cout << res << ',' << flag << endl;return 0;}#include #include class PasswordChecker {private:int dx, xx, sz, n;public:PasswordChecker() : dx(0), xx(0), sz(0), n(0) {}bool check(const std::string &str) {n = str.size();if (n = 'a' && ch = 'A' && ch = '0' && ch = 1 && dx >= 1 && sz >= 1 && sz + xx + dx > str;for (auto &ch : str) {if (ch == '<') {if (!res.empty()) res.pop_back();} else {res.push_back(ch);}}std::string flag = "false";if (check(res)) flag = "true";std::cout << res << ',' << flag << std::endl;}};int main() {PasswordChecker passwordChecker;passwordChecker.processInput();return 0;}分配土地
#include #include #include const int MAX_SIZE = 500;class Rect {public:int minRow;int maxRow;int minCol;int maxCol;Rect() : minRow(INT_MAX), maxRow(INT_MIN), minCol(INT_MAX), maxCol(INT_MIN) {}void setRow(int row) {minRow = std::min(minRow, row);maxRow = std::max(maxRow, row);}void setCol(int col) {minCol = std::min(minCol, col);maxCol = std::max(maxCol, col);}int calculateArea() const {return (maxRow - minRow + 1) * (maxCol - minCol + 1);}};int main() {int m, n;std::cin >> m >> n;std::vector rects(MAX_SIZE, nullptr);for (int i = 0; i < m; i++) {for (int j = 0; j > num;if (num > 0) {if (rects[num] == nullptr) {rects[num] = new Rect();}rects[num]->setRow(i);rects[num]->setCol(j);}}}int maxArea = 0;for (int i = 0; i calculateArea();maxArea = std::max(maxArea, area);delete rect; // Don't forget to free memory}}std::cout << maxArea << std::endl;return 0;}#include #include #include const int MAX_SIZE = 500;class Rect {public:int minRow;int maxRow;int minCol;int maxCol;Rect() : minRow(INT_MAX), maxRow(INT_MIN), minCol(INT_MAX), maxCol(INT_MIN) {}void updateBounds(int row, int col) {minRow = std::min(minRow, row);maxRow = std::max(maxRow, row);minCol = std::min(minCol, col);maxCol = std::max(maxCol, col);}int calculateArea() const {return (maxRow - minRow + 1) * (maxCol - minCol + 1);}};class RectanglesAnalyzer {private:std::vector rects;public:RectanglesAnalyzer() : rects(MAX_SIZE, nullptr) {}void processInput() {int m, n;std::cin >> m >> n;for (int i = 0; i < m; i++) {for (int j = 0; j > num;if (num > 0) {if (rects[num] == nullptr) {rects[num] = new Rect();}rects[num]->updateBounds(i, j);}}}}int calculateMaxArea() const {int maxArea = 0;for (int i = 0; i calculateArea();maxArea = std::max(maxArea, area);delete rect; // Don't forget to free memory}}return maxArea;}};int main() {RectanglesAnalyzer analyzer;analyzer.processInput();int maxArea = analyzer.calculateMaxArea();std::cout << maxArea << std::endl;return 0;}智能成绩表
#include using namespace std;int idx;struct stu{string name;vector scores;};stu stus[1010];bool compare(stu& a, stu& b){if(a.scores[idx] != b.scores[idx])return a.scores[idx] > b.scores[idx];return a.name > n >> m;for(int i = 0; i > course_names[i];for(int i = 0; i > stus[i].name;int sum = 0;for(int j = 0; j > score;stus[i].scores.push_back(score);sum += score;}stus[i].scores.push_back(sum);}string key;cin >> key;idx = m;for(int i = 0; i < m; i ++){if(course_names[i] == key){idx = i;break;}}sort(stus , stus + n, compare);for(int i = 0; i < n; i ++){cout << stus[i].name;if(i == n) cout << endl;else cout << " ";}return 0;}转盘寿司
#include using namespace std;vector price;int num;string str;int main() {getline(cin, str);//获取价格stringstream ss(str);//转成数字while (ss >> num) {price.push_back(num);}int n = price.size();//价格总数price.insert(price.end(), price.begin(), price.end());vector res(n, 0);//赠送的stack stk;//单调栈for (int i = n * 2 - 1; i >= 0; i--){int x = price[i];while (stk.size() && x <= stk.top()) stk.pop();if (i < n){if (stk.empty()) res[i] = 0;else res[i] = stk.top();}stk.push(x);}for (int i = 0; i < n; i++) { cout << res[i] + price[i] << " ";}return 0;}开源项目热度榜单
#include using namespace std;struct project {string name;// 项目名称int hot;// 项目热度string name_lower;// 项目名称的小写形式};const int N = 110;int n, w[5];project a[N];//int main() {cin >> n;// 读取总项目数for (int i = 0; i > w[i];// 读取权重数组// 读取每个项目的信息for (int i = 0; i < n; i++) {string s;vector wd(5);cin >> s >> wd[0] >> wd[1] >> wd[2] >> wd[3] >> wd[4];int hot = 0;// 计算项目热度，热度为每个权重乘以对应值的总和for (int i = 0; i wd.hot;}return u.name_lower < wd.name_lower;}); // 输出排序后的项目名称for (int i = 0; i < n; i++)cout << a[i].name << endl;return 0;}提取字符串中的最长合法简单数学表达式
#include #define MAX_N 10000typedef long long ll;using namespace std;ll op,op1,op2,op3;char sign1, sign2;char c;bool is_digit;string input, maxst, tmp;queue s_que;queue op_que;ll res;void updatemaxst(){if(tmp.size() > maxst.size()) maxst = tmp;tmp = "";}int main(){cin >> input;for(int i = 0; i < input.size(); i++){c = input[i];if(c == '*' || c == '+' || c == '-'){if(i+1 = 0 && isdigit(input[i-1])) tmp += c;else updatemaxst();}else if(isdigit(c)) tmp += c;else updatemaxst();}updatemaxst();// //test maxst// cout << maxst << endl;for(int i = 0; i < maxst.size(); i++){if(isdigit(maxst[i])){op *= 10;op += maxst[i]-'0';}else{s_que.push(maxst[i]);op_que.push(op);op = 0;}}op_que.push(op);res = op_que.front();op_que.pop();while(s_que.size()){c = s_que.front();s_que.pop();op1 = op_que.front();op_que.pop();while(s_que.size() && s_que.front() == '*'){s_que.pop();op2 = op_que.front();op_que.pop();op1 *= op2;}switch(c){case '*':res *= op1;break;case '+':res += op1;break;case '-':res -= op1;break;}}cout << res;return 0;}机器人搬砖
#include #include using namespace std;vector s; // 保存输入的数组int x;int check(vector& w, int mid) {int res = 0;for (int x : w) res += (x + mid - 1) / mid;return res;}int main() {while (cin >> x)s.push_back(x); int n = s.size(); if (n > 8)cout << -1 << endl; else {int l = 1, r = 1e9; while (l > 1; if (check(s, mid) <= 8) r = mid; else l = mid + 1; }// 输出最终的结果cout << r << endl;}return 0;}内存冷热标记
#includeusing namespace std;int n,T,x;unordered_map cnt;vector res;int main(){cin>>n;for(int i=0;i>x;cnt[x]++;}cin>>T;for(auto& [a,b]:cnt) if(b >= T) res.push_back(a);sort(res.begin(),res.end(),[&](int &a,int &b){if(cnt[a]!=cnt[b])return cnt[a] > cnt[b];//按照频率降序排列returna < b;//按照编号升序排列});cout << res.size() << endl;if(res.size())for(int& x: res ) cout << x << endl;return 0;}爱吃蟠桃的孙悟空
#include using namespace std;vector s; // 保存输入的数组int H, num;string str;int check(vector& m, int mid) {int res = 0;for (int x : m) res += (x + mid - 1) / mid;return res;}int main() {getline(cin, str);//获取价格stringstream ss(str);//转成数字while (ss >> num) {s.push_back(num);//}cin >> H ;int n = s.size(); int l = 1, r = 1e9;if(n > H) cout << 0 << endl;else{while (l > 1; if (check(s, mid) <= H) r = mid; else l = mid + 1; }cout << r << endl;}return 0;}虚拟理财游戏
#include #define MIN(a, b) ((a) < (b) ? (a) : (b)) int main() {// 产品数, 总投资, 总风险int m, n, x;scanf("%d %d %d", &m, &n, &x); // 产品回报率序列int back[m];for (int i = 0; i < m; i++) scanf("%d", &back[i]); // 产品风险值序列int risk[m];for (int i = 0; i < m; i++) scanf("%d", &risk[i]); // 产品投资额序列int invest[m];for (int i = 0; i < m; i++) scanf("%d", &invest[i]); // 记录所选产品的最大投资回报int max_invest_back = 0; // 记录所选产品的序号int selectId[] = {-1, -1};int selectFee[] = {0, 0};for (int i = 0; i < m; i++) {// 如果单个产品的投资风险未超过总风险，则投资单个产品if (risk[i] max_invest_back) {max_invest_back = invest_back;selectId[0] = i;selectFee[0] = investI; selectId[1] = -1;}} else {continue;} for (int j = i + 1; j < m; j++) {// 如果两个产品的风险和不超过了总风险，那么两个产品都选if (risk[i] + risk[j] back[j]) {// 产品I回报率高，则能投多少投多少，最多不能超过min(总投资, 产品I的最多投资额)investI = MIN(n, invest[i]);// 留给产品J的剩余钱未 n - investI, 而产品J最多投资invest[j]，因此取二者较小值investJ = MIN(n - investI, invest[j]);} else {investJ = MIN(n, invest[j]);investI = MIN(n - investJ, invest[i]);} // 总投资回报int invest_back = investI * back[i] + investJ * back[j]; // 如果当前产品组合的总回报更大，则选当前组合产品if (invest_back > max_invest_back) {max_invest_back = invest_back; selectId[0] = -1;selectId[1] = -1; // select的key记录产品的ID，val记录产品的投资额if (investI > 0) {selectId[0] = i;selectFee[0] = investI;}if (investJ > 0) {selectId[1] = j;selectFee[1] = investJ;}}}}} for (int i = 0; i < m; i++) {if(i == selectId[0]) {printf("%d", selectFee[0]);} else if(i == selectId[1]) {printf("%d", selectFee[1]);} else {printf("%d", 0);} if(i < m - 1) {printf(" ");}} return 0;}游戏分组
#include #include using namespace std;int nums[10];int total;int res = 1e9; // 差距最小值bool choose[10];void dfs(int cnt, int sum1) {for (int i = 0; i < 10; i++) {if (!choose[i]) {choose[i] = true;dfs(cnt + 1, sum1 + nums[i]);choose[i] = false;}}if (cnt == 5) {res = min(res, abs(total - 2 * sum1));//取两者之差最小的情况return;}}int main() {for (int i = 0; i > nums[i];total += nums[i];}dfs(0, 0);//人数，dcout << res << endl;return 0;}围棋的气
#include#include#include#includeusing namespace std;vector<vector> g(19, vector(19, 0)); // 创建一个二维数组用于存储棋盘信息vector b, w;string input; int num;vector dx = { -1, 1, 0, 0 };vector dy = { 0, 0, 1, -1 };int main() {getline(cin, input); stringstream ss(input); while (ss >> num)b.push_back(num);getline(cin, input);stringstream ss2(input);while (ss2 >> num)w.push_back(num); for (int i = 0; i < b.size(); i += 2) { int x = b[i], y = b[i + 1];g[x][y] = 1;}for (int i = 0; i < w.size(); i += 2) { int x = w[i], y = w[i + 1];g[x][y] = 2;}int res1 = 0, res2 = 0; // 创建两个变量用于存储黑棋和白棋的气数量for (int i = 0; i < 19; i++) { // 统计黑棋和白棋的气数量for (int j = 0; j < 19; j++) {if (g[i][j] != 0) continue; // 如果当前位置有棋子，则跳过int f1 = 0, f2 = 0; // 创建两个变量用于存储黑棋和白棋的气标记for (int dirc = 0; dirc < 4; dirc++) { // 遍历四个方向int x = i + dx[dirc], y = j + dy[dirc];if (x = 19 || y = 19 || g[x][y] == 0) continue; // 如果越界或者没有棋子，跳过else if (g[x][y] == 1) f1 = 1; // 如果是黑棋，标记黑棋的气else if (g[x][y] == 2) f2 = 1; // 如果是白棋，标记白棋的气}res1 += f1; // 统计黑棋的气数量res2 += f2; // 统计白棋的气数量}}cout << res1 << " " << res2 << " "; // 输出结果return 0;}万能字符单词拼写、掌握的单词个数
#includeusing namespace std;const int N=110;string words[N], str;int n, ask, res;vector cnt(26,0);//存字母个数bool check(string &s){//每次检查初始化strauto ch_cnt = cnt;int num = ask; for(char &ch : s){int m = ch - 'a';if( ch_cnt[m] == 0 && num == 0) return false;else if( ch_cnt[m]) ch_cnt[m] --;else num --;}return true;}int main(){cin >> n;for(int i=0; i > words[i];cin >> str;for(auto &ch : str){if( ch == '?' ) ask ++;else cnt [ ch - 'a' ] ++;} for(int i = 0; i < n; i ++)if(check(words[i])) res ++;cout << res << endl;return 0;}小明找位置
#include #include #include #include using namespace std;const int N = 10010;int x,num;string str;vector nums;int main() {getline(cin, str);//获取价格stringstream ss(str);//转成数字while (ss >> num) {nums.push_back(num);if (ss.peek() == ',') ss.ignore();}cin >> x;int l = 0, r = nums.size() - 1;while (l > 1;if (nums[mid] >= x) r = mid;else l = mid + 1;}for (int i = 0; i = x) {cout << i + 1 << endl;break;}}return 0;}分割均衡字符串
#includeusing namespace std;string s;int res, sum;int main(){cin>>s;for(char &ch:s){if(ch=='X')sum++;else sum--;if(sum==0)res++;}cout<<res<<endl;return 0;}小华地图寻宝
#include #include #include using namespace std;int m, n, k;int res = 0;vector<vector> nums;// 计算数位和int get(int num) {int sum = 0;string s = to_string(num);for(char c : s) sum += c - '0';return sum;}// 深度优先搜索void dfs(int x, int y) {if (x = n || y = m || nums[x][y] == 1)return;nums[x][y] = 1;if (get(x) + get(y) > k)return;//先写递归基res++;// 一般情况dfs(x - 1, y);dfs(x, y + 1);dfs(x + 1, y);dfs(x, y - 1);// 遍历四个方向}int main() {cin >> m >> n >> k;nums = vector<vector>(n, vector(m, 0));dfs(0, 0);cout << res << endl;return 0;}数的分解
#include #include using namespace std;int main() {long long n;cin >> n;n *= 2;// 将问题转化为 2n 的形式，简化计算int flag = 1;// 判断有没有解for (int k = 2; k < sqrt(n); k++) {// 遍历所有可能的 kif (n % k != 0) continue;// 如果 n 不能被 k 整除，则继续下一轮循环// 判断是否有解if ((n / k - (k - 1)) % 2 == 0) {int startNum = (n / k - k + 1) / 2;cout << n / 2 << "=";// 输出等号右边的部分for (int x = startNum; x < startNum + k; x++) {cout << x;if (x != startNum + k - 1) {cout << "+";}}flag = 0;break;}}if (flag == 1) cout << "N" << endl;// 如果没有解，输出 "N"return 0;}执行任务赚积分
#include#include#include#includeusing namespace std;typedef pair PII;// 定义对组const int N = 1E5 + 10;// 定义常量Nint n, T;// 定义变量n和Tvector nums;// 定义vector数组vpriority_queue<int, vector, greater>heap;// 定义小根堆int main(){cin >> n >> T;for (int i = 0; i > a >> b;//a截至时间，b积分nums.push_back({ a,b });// 将数对加入数组nums}sort(nums.begin(), nums.end());// 从小到大排序for (int i = 0; i heap.size()) {if (heap.size() < T) heap.push(nums[i].second); //把积分加进去else if (heap.top() heap.top()) {// 如果当前任务的值比堆顶的任务的值大heap.pop();// 弹出堆顶的任务heap.push(nums[i].second);// 将当前任务加入堆}}}long long res = 0; for (int i = heap.size();i > 0; i --) {res += heap.top();// 将堆顶的任务的值加入结果heap.pop();// 弹出堆顶的任务}cout << res << endl;// 输出结果return 0;// 返回0}计算二又搜索树的高度
#include#includeusing namespace std;struct Treenode {int val;Treenode* left;Treenode* middle;Treenode* right;};void insert(Treenode* &root, int num) {//将值为num的结点插入到以root为根的树中if (root == nullptr) {Treenode* newNode = new Treenode;newNode -> val = num;newNode->left = nullptr;newNode->middle = nullptr;newNode->right = nullptr;root = newNode;}else if (num val - 500)return insert(root->left, num);else if (num > root->val + 500)return insert(root->right, num);elsereturn insert(root->middle, num);}int height(Treenode* root) {if (root == nullptr) return 0;return max(height(root->left), max(height(root->middle), height(root->right))) + 1;}int main() {int N;cin >> N;Treenode* root = nullptr;for (int i = 0; i > num;insert(root, num);}cout << height(root);return 0;}API集群负载统计
#include#include#includeusing namespace std;int N, Level;string keyword, url;int main() {cin >> N;vector urls(N);vector<vector> logs(N, vector());//初始化N个空的一维向量，每个元素存url//初始化大小为N的urls,每个url是一个stringfor (int i = 0; i > url;urls[i] = url;}cin >> Level >> keyword;// 对含有分隔符的 url 进行处理for (int i = 0; i < N; i++) {//对每一个urlstring temp = "";for (char c : urls[i]) {if (c == '/') {logs[i].push_back(temp);//logs[i]存url的每个分级temp = "";}else temp += c;}logs[i].push_back(temp);}int result = 0;for (int i = 0; i < N; i++) {// 检查 logs[i] 的大小，确保有足够的元素if (logs[i].size() - 1 < Level ){continue;}if (logs[i][Level] == keyword)result++;}cout << result;return 0;}剩余银饰的重量
#include #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int cmp(const void *a, const void *b) {return (*(int *) a) - (*(int *) b);} // 二分查找目标值位置，找不到则返回目标值在数组中有序插入位置int binarySearch(const int *nums, int nums_size, int target) {int low = 0;int high = nums_size - 1; while (low > 1;int midVal = nums[mid]; if (midVal > target) {high = mid - 1;} else if (midVal = 3) {// 尾删三个最大值int z = weights[weights_size - 1];int y = weights[weights_size - 2];int x = weights[weights_size - 3]; weights_size -= 3; // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉// 如果 x == y && y != z，那么下面公式结果：remain = z - y// 如果 x != y && y == z，那么下面公式结果：remain = y - x// 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))int remain = abs((z - y) - (y - x)); // 如果还有剩余银块if (remain != 0) {// 那么就二分查找其在剩余升序weights中的有序插入位置int idx = binarySearch(weights, weights_size, remain); if (idx = idx; i--) {weights[i + 1] = weights[i];}weights[idx] = remain;weights_size++;}} if (weights_size == 2) {// 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）printf("%d\n", MAX(weights[0], weights[1]));} else if (weights_size == 1) {// 如果只剩下一块，返回该块的重量printf("%d\n", weights[0]);} else {// 如果没有剩下，就返回 0puts("0");} return 0;}#include #include #include class SilverJewelry {private:std::vector weights;public:SilverJewelry() {}void readWeights(int n) {weights.resize(n);for (int i = 0; i > weights[i];}std::sort(weights.begin(), weights.end());}int binarySearch(int target) const {int low = 0;int high = weights.size() - 1;while (low > 1;int midVal = weights[mid];if (midVal > target) {high = mid - 1;} else if (midVal = 3) {int z = weights.back();weights.pop_back();int y = weights.back();weights.pop_back();int x = weights.back();weights.pop_back();int remain = std::abs((z - y) - (y - x));if (remain != 0) {int idx = binarySearch(remain);if (idx > n;SilverJewelry silverJewelry;silverJewelry.readWeights(n);silverJewelry.processWeights();std::cout << silverJewelry.getResult() << std::endl;return 0;}最多购买宝石数目
#include using namespace std;int n,value;int main() {cin >> n;vector nums(n);for (int i = 0; i > nums[i];cin >> value;int res = 0;for (int i = 0, j = 0, sum = 0; i value)sum -= nums[j++];//如果大于价值减去j，然后去到下一个jif (sum <= value) res = max(res, i - j + 1);//如果满足条件，把最大值存下}cout << res << endl;return 0;}连续字母长度(x)
#includeusing namespace std;string s;int k;vectorcnts(26,0);int main(){cin>>s;cin>>k;int n=s.size();for(int i = 0, j = 0; j < n; j ++){while( i < n && s[i] == s[j]) i++;int c = s[j] - 'A';cnts[c] = max( cnts[c], i - j );j = i - 1;}sort(cnts.begin(),cnts.end(),greater{});//降序排列 找第k大if( k > 26 || cnts[k-1] == 0) puts ("-1");else cout << cnts [k-1] << endl;return 0;}数组连续和
#include #include using namespace std;int n, x;long long res;int main() {cin >> n >> x;vector nums(n);for (int i = 0; i > nums[i];if(x == 0 ) cout << n * (n + 1 ) / 2 << endl;else{for (int i = 0, j = 0, sum = 0; i = x){res += n - i;sum -= nums[j++];}}cout << res << endl;}return 0;}小明的幸运数
#include #define MAX(a,b) ((a) > (b) ? (a) : (b)) int main() {int n;scanf("%d", &n); if (n 100) {// 异常情况下输出：12345puts("12345");return 0;} int m;scanf("%d", &m);if (m 100) {// 异常情况下输出：12345puts("12345");return 0;} int pos = 0;int maxPos = 0; for (int i = 0; i < n; i++) {int num;scanf("%d", &num); if(num 100) {// 异常情况下输出：12345puts("12345");return 0;} pos += num; if(num == m) {// 如果某个指令正好和幸运数相等，则小明行进步数+1// 注意，如果幸运数字为0，且存在指令为0，那么此时我理解小明应该继续保持不动if(num > 0) {pos += 1;} else if(num < 0) {pos -= 1;}} // 比较本次移动后的坐标位置和最大坐标位置maxPos = MAX(maxPos, pos);} printf("%d\n", maxPos); return 0;}#include #include class Movement {private:int n;int m;public:Movement() : n(0), m(0) {}void readInput() {std::cin >> n;if (n 100) {// 异常情况下输出：12345std::cout << "12345" <> m;if (m 100) {// 异常情况下输出：12345std::cout << "12345" << std::endl;return;}processMovements();}void processMovements() const {int pos = 0;int maxPos = 0;for (int i = 0; i > num;if (num 100) {// 异常情况下输出：12345std::cout << "12345" < 0) {pos += 1;} else if (num < 0) {pos -= 1;}}maxPos = std::max(maxPos, pos);}std::cout << maxPos << std::endl;}};int main() {Movement movement;movement.readInput();return 0;}悄悄话
#include #include #include // 添加这行using namespace std;vector nums;// 用于存储树节点值的数组int n, res, num;// 树的节点数和最大和string input;void dfs(int u, int sum) {// 深度优先搜索函数，接受两个参数：一个节点索引u和从根节点到当前节点的值之和sumif (u >= n || nums[u] == -1)return;//先处理递归姬res = max(res, sum + nums[u]);// 更新最大和为当前最大和和当前路径和的最大值dfs(2 * u, sum + nums[u]);// 递归调用dfs函数，处理左子节点dfs(2 * u + 1, sum + nums[u]);// 递归调用dfs函数，处理右子节点}int main() {getline(cin, input);// 从标准输入读取一行stringstream ss(input);// 使用字符串流处理输入nums.push_back(0);// 在数组开头添加一个虚拟元素，使索引从1开始while (ss >> num) nums.push_back(num);// 将读取的整数存入数组n = nums.size();// 获取数组的长度，即树的节点数dfs(1, 0);cout << res << endl;// 输出最大和return 0;}CPU算力分配
#include #include #include #include using namespace std;int main() {int n, m;cin >> n >> m;// 读取第一个整数 n 和第二个整数 mvector w1(n), w2(m);// 读取第一个数组的元素for (int i = 0; i > w1[i];}// 读取第二个数组的元素for (int i = 0; i > w2[i];}int total_1 = 0, total_2 = 0;// 计算第一个数组的总和for (int x : w1) {total_1 += x;}// 计算第二个数组的总和for (int x : w2) {total_2 += x;}int target = (total_1 - total_2) / 2;// 计算目标值，即两数组的差值的一半set st(w2.begin(), w2.end());// 使用集合提高查找效率sort(w1.begin(), w1.end());// 对第一个数组进行升序排序// 遍历第一个数组，查找符合条件的数对for (int x : w1) {if (st.count(x - target)) {// 输出符合条件的数对并结束循环cout << x << " " << x - target << " ";break;}}return 0;// 返回0表示成功执行}分披萨(dp盲区)
#include #include #include using namespace std;typedef long long LL ;int n;// 披萨的数量vector a;// 每块披萨的美味值vector<vector> dp;// 记忆化数组，用于存储已计算过的状态int solve(LL L, LL R) {// “馋嘴“选择一块披萨吃掉，对应端点移动if (a[L] > a[R]) {L = (L + 1) % n;} else {R = (R + n - 1) % n;}// 如果该状态已经计算过，则直接返回结果if (dp[L][R] != -1) {return dp[L][R];}// 如果左右端点相同，则说明只剩下一块披萨，直接返回该披萨的美味值if (L == R) {dp[L][R] = a[L];} else {// 分别计算选择左边披萨和选择右边披萨的情况下的最大美味值dp[L][R] = max(a[L] + solve((L + 1) % n, R), a[R] + solve(L, (R + n - 1) % n));}return dp[L][R];}int main() {cin >> n;// 输入披萨的数量a.resize(n);// 调整披萨美味值数组的大小为ndp.assign(n, vector(n, -1));// 初始化记忆化数组dp，全部赋值为-1for (int i = 0; i > a[i];// 输入每块披萨的美味值}LL ans = 0;// 枚举吃货第一步取哪块披萨for (LL i = 0; i < n; i++) {ans = max(ans, solve((i + 1) % n, (i + n - 1) % n) + a[i]);}cout << ans << endl;// 输出最多能吃到的披萨的美味值return 0;}机场航班调度程序
#include #include #include #include using namespace std;string input;vector str;int main() {//忽略掉逗号模板getline(cin, input);stringstream ss(input);string token;while (getline(ss, token, ',')) {str.push_back(token);}sort(str.begin(), str.end());// 输出排序后的字符串，使用逗号分隔for (size_t i = 0; i < str.size(); ++i) {cout << str[i];if (i < str.size() - 1) {cout << ",";}}cout << endl;return 0;}攀登者1
#include #define MAX_SIZE 100000 // 算法实现（本题实际考试为核心代码模式，因此考试时只需要写出此函数实现即可）int getResult(const int heights[], int heights_size) {int count = 0; for (int i = 0; i = 0 ? heights[i - 1] : 0;int rightHeight = i + 1 leftHeight && heights[i] > rightHeight) {count++;}} return count;} // 输入处理int main() {int heights[MAX_SIZE];int heights_size = 0; while (scanf("%d", &heights[heights_size++])) {if (getchar() != ',') break;} printf("%d\n", getResult(heights, heights_size)); return 0;}生成哈夫曼树（无oj）
#includeusing namespace std;typedef pairPII;#define x first#define y secondconst int N=1e5+10;int n,cnt;struct node{long long val,l,r;//记录当前节点的左节点和右节点，以及当前节点的权值};vectorres;///记录中序遍历结果vectorg;void dfs(long long u){//中序遍历if(u==-1)return;long long l=g[u].l,r=g[u].r;dfs(l);res.push_back(g[u].val);dfs(r);}int main(){cin>>n;priority_queue<PII,vector,greater>heap; //小根堆g.resize(n);for(long long i=0;i>x;heap.push({x,i});g[i].l=g[i].r=-1;g[i].val=x;}cnt=n;//新生成的节点编号while(heap.size()>1){ //模拟生成哈夫曼树的过程auto [x,idx]=heap.top();heap.pop();auto [y,idy]=heap.top();heap.pop();long long z=x+y,idz=cnt++;heap.push({z,idz});g.push_back({z,idx,idy});}dfs(cnt-1);//从根节点跑一遍中序遍历for(long long &x:res)cout<<x<<" ";return 0;}}密码解密
#include #include #include using namespace std;string replace(string s, const string& old, const string& new_str) {size_t pos = s.find(old);while (pos != string::npos) {s.replace(pos, old.length(), new_str);pos = s.find(old);}return s;}int main() {string s;getline(cin, s);for (int i = 26; i >= 1; i--) {string key = to_string(i);if (i > 9) {key += "*";}char val = static_cast(97 + i - 1);string val_str(1, val);s = replace(s, key, val_str);}cout << s << endl;return 0;}来自异国的客人
#include using namespace std;int main(void) {int k, n, m;cin >> k >> n >> m;int ans = 0;while (k) {ans += k % m == n;k /= m;}cout << ans << endl;}求幸存数之和
#include #include #define MAX_SIZE 10000 int sumOfLeft(int nums[], int nums_size, int jump, int left) {// 从起跳点开始的话，需要跳jump+1次，到达需要删除的节点// 从起跳点下一个节点开始的话，需要跳jump次，到达需要删除的节点// 这里我们从起跳点的下一个节点开始,初始时起跳点为索引0，因此下一个节点为索引1int start = 1; // 如果剩余节点数 > 幸存数量，则还需要继续删除节点while (nums_size > left) {// 跳 jump 次start += jump;// 为了避免越界，新起跳点索引位置对剩余节点数取余start %= nums_size; for (int i = start; i < nums_size - 1; i++) {nums[i] = nums[i + 1];}nums_size--;} int sum = 0;for (int i = 0; i < nums_size; i++) {sum += nums[i];} return sum;} int main() {int nums[MAX_SIZE];int nums_size = 0; while (scanf("%d", &nums[nums_size++])) {if (getchar() != ',') break;} int jump;scanf("%d", &jump); int left;scanf("%d", &left); printf("%d\n", sumOfLeft(nums, nums_size, jump, left)); return 0;}会议室占用时间
#include #include int rows = 0; int cmp(const void *a, const void *b) {return (*(int **) a)[0] - (*(int **) b)[0];} // 本题实际考试时会核心代码模式，无需处理输入输出，只需要写出merge方法相关实现即可int **merge(int **roomTimes, int roomTimes_size) {// 将各个会议按照开始时间升序qsort(roomTimes, roomTimes_size, sizeof(int *), cmp); // 记录合并后的会议室占用时间段int** res = (int**) malloc(sizeof(int*) * roomTimes_size); // 上一个会议占用时间段int* pre = roomTimes[0]; // 当前会议占用时间段for(int i=1; i<roomTimes_size; i++) {int* cur = roomTimes[i]; if(cur[0] <= pre[1]) {// 当前会议开始时间 pre[1]) {pre[1] = cur[1];}} else {res[rows++] = pre;pre = cur;}} res[rows++] = pre; return res;} // 输入输出处理int main() {int n;scanf("%d", &n); int **roomTimes = (int **) malloc(sizeof(int *) * n);for (int i = 0; i < n; i++) {roomTimes[i] = (int *) malloc(sizeof(int) * 2);scanf("%d %d", &roomTimes[i][0], &roomTimes[i][1]);} int **res = merge(roomTimes, n); for (int i = 0; i < rows; i++) {printf("%d %d\n", res[i][0], res[i][1]);} return 0;}石头剪刀布游戏
#include #include #include using namespace std;int main() {// 初始化一个包含三个vector的数组vector arr[3];// 从标准输入中读取数据，直到到达文件末尾string s1, s2;while (cin >> s1 >> s2) {// 将第一个字符串添加到对应的vector中arr[s2[0] - 'A'].push_back(s1);}// 如果三个vector都非空，说明有三种不同的出拳，是平手if (all_of(begin(arr), end(arr), [](const vector& lst) { return !lst.empty(); })) {cout << "NULL" << endl;return 0;}// 计算空vector的数量int num = count_if(begin(arr), end(arr), [](const vector& lst) { return lst.empty(); });// 如果有两个或以上的vector为空，说明只有一种出拳，也是平手if (num >= 2) {cout << "NULL" << endl;return 0;}// 对每个vector进行排序for (auto& lst : arr) {sort(begin(lst), end(lst));}int tmp = 0;// 找到赢家的索引if (arr[0].empty()) {tmp = 1;} else if (arr[1].empty()) {tmp = 2;}// 输出赢家的出拳方式for (const auto& t : arr[tmp]) {cout << t << endl;}return 0;}手机App防沉迷系统
#include #include #include #include #include #include using namespace std;class App {public:string name;int p;// 优先级int start;// 开始时间int end;// 结束时间};// 将时间字符串转换为分钟表示int transTo(string data) {string delimiter = ":";size_t pos = 0;string token;int hour, min;// 提取小时部分pos = data.find(delimiter);token = data.substr(0, pos);hour = stoi(token);// 提取分钟部分token = data.substr(pos + 1, data.length());min = stoi(token);return hour * 60 + min;}// 将应用信息字符串转换为 App 对象App transToApp(string s) {string delimiter = " ";size_t pos = 0;string token;string arr[4];int i = 0;// 使用空格分隔字符串while ((pos = s.find(delimiter)) != string::npos) {token = s.substr(0, pos);arr[i] = token;s.erase(0, pos + delimiter.length());i++;}arr[i] = s;// 构建 App 对象App app;app.name = arr[0];app.p = stoi(arr[1]);app.start = transTo(arr[2]);app.end = transTo(arr[3]);return app;}int main() {int n;cin >> n;cin.ignore();App apps[n];int cnt = 0;// 读取应用信息for (int i = 0; i temp.end) {cnt++;continue;}apps[i] = transToApp(s);}n -= cnt;vector res;// 遍历每个应用for (int i = 0; i < n; i++) {vector ids;// 找到与当前应用时间段有重叠的应用for (int j = 0; j < res.size(); j++) {if (res[j].start <= apps[i].end && apps[i].start <= res[j].end) {ids.push_back(j);}}int mx = -1;// 找到重叠应用中优先级最高的for (int j = 0; j < ids.size(); j++) {mx = max(mx, res[ids[j]].p);}// 如果当前应用优先级更高，则移除重叠应用，添加当前应用if (mx = 0; j--) {res.erase(res.begin() + ids[j]);}res.push_back(apps[i]);}}string timeStr;getline(cin, timeStr);int time = transTo(timeStr);string ans = "NA";// 查找当前时间所在的应用for (int i = 0; i < res.size(); i++) {if (res[i].start <= time && time <= res[i].end) {ans = res[i].name;break;}}cout << ans << endl;// 输出结果return 0;}小朋友来自多少小区
#include #include #include using namespace std;int main() {vector w;int num;// 输入一行整数，以空格分隔while (cin >> num) {w.push_back(num);if (cin.get() == '\n') break;}unordered_map cnts;for (int x : w) {cnts[x] = cnts.find(x) != cnts.end() ? cnts[x] + 1 : 1;}long long ans = 0;for (const auto& entry : cnts) {int k = entry.first;int v = entry.second;ans += (v + k) / (k + 1) * (k + 1);}cout << ans << endl;return 0;}精准核酸检测
#include #include #define MAX_SIZE 100 /** 并查集定义 **/typedef struct {int *fa;} UFS; UFS *new_UFS(int n) {UFS *ufs = (UFS *) malloc(sizeof(UFS)); ufs->fa = (int *) malloc(sizeof(int) * n);for (int i = 0; i fa[i] = i;} return ufs;} int find_UFS(UFS *ufs, int x) {if (x != ufs->fa[x]) {ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);return ufs->fa[x];}return x;} void union_UFS(UFS *ufs, int x, int y) {int x_fa = find_UFS(ufs, x);int y_fa = find_UFS(ufs, y); if (x_fa != y_fa) {ufs->fa[y_fa] = x_fa;}} int main() {int n;scanf("%d", &n); int confirmed[MAX_SIZE];int confirmed_size = 0; while (scanf("%d", &confirmed[confirmed_size++])) {if (getchar() != ',') break;} UFS *ufs = new_UFS(n); for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int v;scanf("%d", &v); // 有过接触的人进行合并if (v == 1) {union_UFS(ufs, i, j);} getchar();}} // 统计每个接触群体（连通分量）中的人数int cnts[MAX_SIZE] = {0};for (int i = 0; i < n; i++) {int fa = find_UFS(ufs, i);cnts[fa]++;} // 记录已统计过的可能感染群体int confirmed_fa[MAX_SIZE] = {0}; // 将有感染者的接触群体的人数统计出来int ans = 0;for (int i = 0; i < confirmed_size; i++) {int fa = find_UFS(ufs, confirmed[i]); // 已统计过的可能感染群体不再统计if(confirmed_fa[fa]) continue;confirmed_fa[fa] = 1; ans += cnts[fa];} // 最终需要做核酸的人数，不包括已感染的人printf("%d\n", ans - confirmed_size); return 0;}多段线数据压缩
#include #include using namespace std;// 计算两个整数的最大公约数int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;}int main() {// 存储输入的整数向量vector w;int num;// 读取输入并转为整数向量while (cin >> num) {w.push_back(num);}// 存储筛选结果的点的坐标向量vector<pair> res;res.push_back({w[0], w[1]});int n = w.size();for (int i = 2; i < n; i += 2) {if (res.size() == 1) {res.push_back({w[i], w[i + 1]});} else {int m = res.size();int a = res[m - 1].first - res[m - 2].first;int b = res[m - 1].second - res[m - 2].second;int g = gcd(abs(a), abs(b));int a1 = a / g;int b1 = b / g;a = w[i] - res[m - 1].first;b = w[i + 1] - res[m - 1].second;g = gcd(abs(a), abs(b));int a2 = a / g;int b2 = b / g;// 如果两组差值的归一化结果相同，则说明当前点共线，将上一个点弹出，并将当前点加入 resif (a1 == a2 && b1 == b2) {res.pop_back();}res.push_back({w[i], w[i + 1]});}}// 打印筛选出的点的坐标for (const auto& pair : res) {cout << pair.first << " " << pair.second << " ";}return 0;}测试用例执行计划
#includeusing namespace std;int main() {int n, m;cin >> n >> m;// 读取输入的整数n和mvector a(n + 1);// 创建整数向量a，长度为n+1for (int i = 1; i > a[i];// 读取n个整数并存入向量avector<vector> list(m, vector());// 创建整数向量的向量list，长度为m，每个元素为一个空的整数向量cin.ignore();// 忽略换行符for (int i = 0; i < m; i++) {string s;getline(cin, s);// 读取一行字符串istringstream iss(s);// 创建字符串流vector arr((istream_iterator(iss)), istream_iterator());// 将字符串流转为整数向量arrfor (int j = 0; j o2[0];return o1[1] < o2[1];});for (int i = 0; i < m; i++)cout << list[i].back() << endl;// 输出list的第i个元素的最后一个值return 0;}堆内存申请
#include #include #include #define MAX_COUNT 100 typedef struct {int offset;// 内存块起始位置int size; // 内存块大小} Memory; Memory *new_Memory(int offset, int size) {Memory *m = (Memory *) malloc(sizeof(Memory));m->offset = offset;m->size = size;return m;} int cmp(const void *a, const void *b) {Memory *A = *((Memory **) a);Memory *B = *((Memory **) b);return A->offset - B->offset;} int getResult(int malloc_size, Memory *used_memory[], int used_memory_count) {// 申请的内存大小非法，则返回-1if (malloc_size 100) {return -1;} // 记录最优的申请内存起始位置int malloc_offset = -1;// 记录最接近申请内存的空闲内存块大小int min_malloc_size = 100; // 对占用的内存按照起始位置升序qsort(used_memory, used_memory_count, sizeof(Memory *), cmp); // 记录（相对于已占用内存的前面一个）空闲内存块的起始位置int free_offset = 0; for (int i = 0; i offset offset > 99) return -1; // 如果占用的内存的大小少于0，则非法// 如果占用的内存的大小超过该内存起始位置往后所能申请到的最大内存大小，则无效if (used->size size > 100 - used->offset) return -1; // 空闲内存块地址范围是：free_offset ~ memory.offset - 1if (used->offset > free_offset) {// 空闲内存块大小int free_memory_size = used->offset - free_offset; // 如果该空闲内存块大小足够，且最接近申请的内存大小if (free_memory_size >= malloc_size && free_memory_size offset + used->size;} // 收尾int last_free_memory_size = 100 - free_offset;if (last_free_memory_size >= malloc_size && last_free_memory_size < min_malloc_size) {malloc_offset = free_offset;} return malloc_offset;} int main() {// 要申请的内存大小int malloc_size;scanf("%d", &malloc_size);getchar(); // 已占用的内存Memory *used_memory[MAX_COUNT];int count = 0; char s[100];while (gets(s)) {// 本地测试使用空行作为结束条件if(strlen(s) == 0) break; int offset, size;sscanf(s, "%d %d", &offset, &size);used_memory[count++] = new_Memory(offset, size);} printf("%d\n", getResult(malloc_size, used_memory, count)); return 0;}灰度图存储
#include int main() {int rows, cols;scanf("%d %d", &rows, &cols); int graph[rows * cols];int start = 0; int gray;int len;while (scanf("%d %d", &gray, &len)) {for (int i = start; i < start + len; i++) {graph[i] = gray;} start += len; if (getchar() != ' ') break;} int x, y;scanf("%d %d", &x, &y); printf("%d\n", graph[x * cols + y]); return 0;}火星文计算2
#include #include #include #define MAX_INPUT_LEN 10000#define MAX_NUM_LEN 100 typedef struct ListNode {char ele[MAX_NUM_LEN];struct ListNode *prev;struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, char *ele) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));strcpy(node->ele, ele);node->prev = NULL;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;node->prev = link->tail;link->tail = node;} link->size++;} char *removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;link->head->prev = NULL;} link->size--; char *res = (char *) calloc(MAX_NUM_LEN, sizeof(char));strcpy(res, removed->ele); free(removed); return res;} char *removeLast_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->tail; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->tail = link->tail->prev;link->tail->next = NULL;} link->size--; char *res = (char *) calloc(MAX_NUM_LEN, sizeof(char));strcpy(res, removed->ele); free(removed); return res;} // 尝试进行#运算void check(LinkedList *stack, char *operNum2) {// 如果栈顶元素是"#"号, 则可以进行#运算if (stack->size > 0 && strcmp(stack->tail->ele, "#") == 0) {// 取出栈顶的"#"removeLast_LinkedList(stack);// 取出操作数xchar *operNum1 = removeLast_LinkedList(stack); long long x = atoll(operNum1);long long y = atoll(operNum2); // 将4 * x + 3 * y + 2包装为字符串char res[MAX_NUM_LEN];sprintf(res, "%lld", 4 * x + 3 * y + 2); // 将计算结果加入栈addLast_LinkedList(stack, res);} else {// 如果栈顶元素不是#，那么操作数2直接入栈addLast_LinkedList(stack, operNum2);}} int main() {char s[MAX_INPUT_LEN];gets(s); strcat(s, "$"); // 末尾加一个$方便后续收尾处理 LinkedList *stack = new_LinkedList(); // 操作数缓存容器char operNum[MAX_NUM_LEN] = {'\0'};int operNum_size = 0; int i = 0;while (s[i] != '\0') { if (s[i] == '#' || s[i] == '$') {// 遇到操作符，则尝试进行#运算check(stack, operNum); // 如果s[i]是最后一个字符，即我们手动加到尾部的$，则此时直接结束循环，避免之前添加的收尾$进入stackif (s[i + 1] == '\0') break; // 否则，清空操作数缓存容器memset(operNum, '\0', MAX_NUM_LEN);operNum_size = 0; // 将操作符加入栈char operator[2];sprintf(operator, "%c", s[i]);addLast_LinkedList(stack, operator);} else {// 收集操作数operNum[operNum_size++] = s[i];} i++;} // 此时，栈中只会剩下 操作数和$// 取出栈底元素作为操作数xlong long x = atoll(removeFirst_LinkedList(stack)); while (stack->size > 1) {// 取出操作符$removeFirst_LinkedList(stack);// 取出操作数ylong long y = atoll(removeFirst_LinkedList(stack));// 进行$运算，并将运算结果作为新的操作数xx = 2 * x + y + 3;} printf("%lld", x); return 0;}求字符串中所有整数的最小和
#include #include #include #define MAX_SIZE 10000 int main() {char s[MAX_SIZE];gets(s); int isNegative = 0; char negative[MAX_SIZE];int negative_size = 0; long long ans = 0;int i = 0;while (s[i] != '\0') {char c = s[i]; if (c >= '0' && c 0) {ans -= atol(negative);memset(negative, '\0', MAX_SIZE);negative_size = 0;} isNegative = c == '-';} i++;} if (negative_size > 0) {ans -= atol(negative);} printf("%lld\n", ans); return 0;}求满足条件的最长子串的长度
#include #include #include #define MAX(a,b) ((a) > (b) ? (a) : (b)) typedef struct ListNode{int ele;struct ListNode* next;} ListNode; typedef struct {int size;ListNode* head;ListNode* tail;} LinkedList; LinkedList* new_LinkedList();void addLast_LinkedList(LinkedList* link, int ele);int removeFirst_LinkedList(LinkedList* link); int main() {char s[100000];gets(s); int maxLen = -1;int hasLetter = 0; int l = 0;int r = 0; LinkedList* letterIdx = new_LinkedList(); int len = strlen(s);while(r = 'a' && c = 'A' && c size > 1) {l = removeFirst_LinkedList(letterIdx) + 1;} if(r == l) {r++;continue;}} maxLen = MAX(maxLen, r - l + 1);r++;} if(!hasLetter) {puts("-1");} else {printf("%d\n", maxLen);}return 0;} LinkedList* new_LinkedList() {LinkedList* link = (LinkedList*) malloc(sizeof(LinkedList)); link->size = 0;link->head = NULL;link->tail = NULL; return link;} void addLast_LinkedList(LinkedList* link, int ele) {ListNode* node = (ListNode*) malloc(sizeof(ListNode)); node->ele = ele;node->next = NULL; if(link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} int removeFirst_LinkedList(LinkedList* link) {if(link->size == 0) exit(-1); ListNode* removed = link->head; if(link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; int res = removed->ele; free(removed); return res;}字符串分割(二)(py代码)
# 输入获取k = int(input())s = input()def convert(s):lowerCount = 0upperCount = 0 for c in s:if 'z' >= c >= 'a':lowerCount += 1elif 'Z' >= c >= 'A':upperCount += 1 if lowerCount > upperCount:return s.lower()elif lowerCount < upperCount:return s.upper()else:return s# 算法入口def getResult():arr = s.split("-") ans = []# ans.append(convert(arr[0])) # 看用例说明，对应第一个子串是不需要做大小写转换的，但是也拿不准，考试时可以都试下ans.append(arr[0]) # 剩余子串重新合并为一个新字符串，每k个字符一组newStr = "".join(arr[1:])for i in range(0, len(newStr), k):subStr = newStr[i:i + k]# 子串中小写字母居多，则整体转为小写字母，大写字母居多，则整体转为大写字母ans.append(convert(subStr)) return "-".join(ans)# 算法调用print(getResult())英文输入法(py代码)
import re # 输入获取s = input()pre = input()# 算法入口def getResult(s, pre):tmp = re.split("[^a-zA-Z]", s)cache = list(set(tmp))cache.sort()cache = list(filter(lambda x: x.startswith(pre), cache))if len(cache) > 0:return " ".join(cache)else:return pre# 算法调用print(getResult(s, pre))字符串筛选排序
#includeusing namespace std;int main(){string s,s1;int k;cin>>s>>k;s1=s;sort(s1.begin(),s1.end()); //排序int n=s.size();k=min(k,n);char ch=s1[k-1];//找到的字符for(int i=0;i<n;i++){if(s[i]==ch){cout<<i<<endl;break;}}return 0;}连续字母长度
#includeusing namespace std;int main(){string s;int k;cin>>s;cin>>k;vectorcnts(26,0);//统计A~Z连续出现的最大次数int n=s.size();for(int i=0;i<n;i++){int j=i;while(j<n&&s[j]==s[i])j++;//使用双指针找到连续出现的子串int c=s[i]-'A';cnts[c]=max(cnts[c],j-i);i=j-1;}sort(cnts.begin(),cnts.end(),greater{});//降序排列 找第k大if(k>26||cnts[k-1]==0)puts("-1");else cout<<cnts[k-1]<<endl;return 0;}拼接URL
#includeusing namespace std;string s;int main(){cin>>s;string pre,suf;bool flag=true;for(auto &ch:s){if(ch==','){flag=false;continue;}else if(flag)pre.push_back(ch);else suf.push_back(ch);}if(!pre.size())pre.push_back('/');//如果前缀为空 则填充/if(!suf.size())suf.push_back('/');//如果后缀为空 则填充/if(pre.back()!='/')pre.push_back('/');//如果前缀结尾没有/ 则自动补上/if(suf[0]!='/')suf='/'+suf; //如果后缀开头没有/ 则自动补上/if(pre.back()=='/'&&suf[0]=='/')pre.pop_back();//有多余的/ 需要自动去重string res=pre+suf;cout<<res<<endl;return 0;}字符串序列判定
#include #include using namespace std;int main() {string s;string t;cin >> s;cin >> t;int n = t.length();int now = 0;int pos = -1;for (int i = 0; i < n; i++) {if (t[i] == s[now]) {now++;}if (now == s.length()) {pos = i;break;}}cout << pos << endl;return 0;}最长的指定瑕疵度的元音子串
#include #include #include using namespace std;bool isy(char ch) {// 判断ch是否为元音字母return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';}int main() {int k;string s;cin >> k >> s;vector f(s.size());// 判断字符串中每个字符是否为元音，并存储结果到列表 f 中for (int i = 0; i < s.size(); i++) {f[i] = isy(s[i]);}int L = 0, R = 0, ans = 0, cnt = 0;// 初始化双指针 L 和 R，结果 ans，以及辅音个数计数器 cntwhile (R k || !f[L]) {// 当辅音个数大于 k 或者 L 指向的字符是辅音时就将左指针向前移动if (!f[L]) {// 如果 L 移动前指向的字符是辅音，就将计数减一cnt--;}L++;// 指针向前移动}if (cnt == k) {// 如果辅音个数等于 k，也就是符合题目要求的子串ans = max(ans, R-L+1);// 更新最大长度}}R++;// R 指针右移}cout << ans << endl;// 输出最大长度return 0;}考勤信息
#include #include #include using namespace std;// 定义考勤信息映射unordered_map mp = {{"absent", 0}, {"late", 1}, {"leaveearly", 2}, {"present", 3}};// 检查考勤信息是否合法的函数bool check(const vector& s) {// 统计每种考勤状态出现的次数vector cnts(4, 0);int m = s.size();// 遍历考勤信息for (int i = 0; i 6) {cnts[mp[s[i - 7]]]--;}// 如果考勤信息长度大于等于7，并且正常上班天数小于4，返回falseif (i >= 6 && cnts[3] 0 && 1 <= mp[s[i]] && mp[s[i]] <= 2 && 1 <= mp[s[i - 1]] && mp[s[i - 1]] <= 2) {return false;}}// 统计所有缺勤的次数int count = 0;for (const string& x : s) {if (mp[x] == 0) {count++;}}// 缺勤次数不超过1时返回true，否则返回falsereturn count > n;cin.ignore(); // 消耗掉换行符// 处理每个测试用例while (n--) {string line;getline(cin, line);vector s;// 分割字符串得到考勤信息size_t pos = 0, next;while ((next = line.find(' ', pos)) != string::npos) {s.push_back(line.substr(pos, next - pos));pos = next + 1;}s.push_back(line.substr(pos));// 调用check函数检查考勤信息是否合法，并输出结果if (check(s)) {cout << "true" << endl;} else {cout << "false" << endl;}}return 0;}字符串变换最小字符串
#include #include #include #define MAX_SIZE 1000 char *getResult(char s[]); int main() {char s[MAX_SIZE];gets(s); puts(getResult(s)); return 0;} int cmp(const void *a, const void *b) {return (*(char *) a) - (*(char *) b);} char *getResult(char s[]) {int len = strlen(s); char minS[len + 1];strcpy(minS, s); qsort(minS, len, sizeof(char), cmp); if (strcmp(minS, s) == 0) {return s;} for (int i = 0; i < len; i++) {if(s[i] != minS[i]) {char tmp = s[i];s[i] = minS[i]; int swapIdx = strrchr(s, minS[i]) - s;s[swapIdx] = tmp;break;}} return s;}查找接口成功率最优时间段
#include #include #include #define MAX_SIZE 100 int cmp(const void *a, const void *b) {int *A = (int *) a;int *B = (int *) b;return A[0] - B[0];} int main() {int minAverageLost;scanf("%d", &minAverageLost); int nums[MAX_SIZE];int nums_size = 0; while (scanf("%d", &nums[nums_size++])) {if (getchar() != ' ') break;} int preSum[nums_size + 1];preSum[0] = 0; for (int i = 1; i <= nums_size; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];} int arrList[MAX_SIZE][2];int arrList_size = 0; int maxLen = 0;for (int i = 0; i < nums_size; i++) {for (int j = i + 1; j <= nums_size; j++) {// sum 是 区间 [i, j-1] 的和int sum = preSum[j] - preSum[i];int len = j - i;int lost = len * minAverageLost; if (sum = maxLen) {if (len > maxLen) {arrList_size = 0;}arrList[arrList_size][0] = i;arrList[arrList_size][1] = j - 1;arrList_size++;maxLen = len;}}}} if (arrList_size == 0) {puts("NULL");} else {qsort(arrList, arrList_size, sizeof(int *), cmp); char res[10000];for (int i = 0; i < arrList_size; i++) {char tmp[100];sprintf(tmp, "%d-%d", arrList[i][0], arrList[i][1]);strcat(res, tmp);strcat(res, " ");} res[strlen(res) - 1] = '\0'; puts(res);} return 0;}执行时长
#include using namespace std;int main() {int m, n;cin >> m >> n;int nums[n];for (int i = 0; i > nums[i];}int ans = 0;int remain = 0;for (int i = 0; i < n; i++) {int x = nums[i];if (remain + x <= m) {remain = 0;} else {remain += x - m;}ans++;}ans += (remain + m - 1) / m; // 上取整cout << ans << endl;return 0;}查找众数及中位数
#include #include #include 最大N个数与最小N个数的和
#includeusing namespace std;int main() {int m;cin >> m;vector w(m);for (int i = 0; i > w[i];}int n;cin >> n;set s(w.begin(), w.end());w.assign(s.begin(), s.end());sort(w.begin(), w.end());m = w.size();if (m < 2 * n || w[0] 1000) {cout << -1 << endl;} else {int result = accumulate(w.begin(), w.begin() + n, 0) + accumulate(w.end() - n, w.end(), 0);cout << result << endl;}return 0;}整数对最小和
#include #include int cmp(const void *a, const void *b) {return *((int *) a) - *((int *) b);} int main() {int size1;scanf("%d", &size1); int nums1[size1];for (int i = 0; i < size1; i++) {scanf("%d", &nums1[i]);} int size2;scanf("%d", &size2); int nums2[size2];for (int i = 0; i < size2; i++) {scanf("%d", &nums2[i]);} int k;scanf("%d", &k); int size = size1 * size2; int pairs[size];int pairs_size = 0; for (int i = 0; i < size1; i++) {for (int j = 0; j < size2; j++) {pairs[pairs_size++] = nums1[i] + nums2[j];}} qsort(pairs, pairs_size, sizeof(int), cmp); int sum = 0;for (int i = 0; i < k; i++) {sum += pairs[i];} printf("%d\n", sum); return 0;}靠谱的车
#include #include using namespace std;int main() {string w;cin >> w;int n = w.length();long long ans = 0;for (int i = 0; i '4') {cost -= 1;}for (int j = n - i - 1; j > 0; j--) {cost *= 9;}ans += cost;}cout << ans << endl;return 0;}素数之积
#include #include void getResult(int n);int isPrime(int n); int main() {int n;scanf("%d", &n); getResult(n); return 0;} void getResult(int n) {// 如果n为素数，则必然不可能是两个素数之积if (isPrime(n)) {puts("-1 -1");return;} // 假设i为n的因子for (int i = 2; i < n; i++) {// 若n不能整除i,则i不是n的因子，继续下次循环，找新的i// 若n可以整除i,则i就是n的因子if (n % i == 0) {// j为n的另一因子int j = n / i; // 只有i,j因子都为素数时，n才是符合题意的素数之积if (isPrime(i) && isPrime(j)) {// 如果n为两个素数之积，则n只能分解为这两个因子，因为素数无法再次分解出其他因子，也就是说n不再有其他因子了（因子不包含1和自身）if (i < j) {printf("%d %d", i, j);} else {printf("%d %d", j, i);}return;} else {// 如果i，j有一个不是素数因子，则说明n存在非素数因子，此时n不可能是素数之积// 如果i，j为相同的素数因子，则n不是满足题意的素数之积// 此时可以判定n不符合要求了，直接退出循环break;}}} puts("-1 -1");} // 判断n是否为素数int isPrime(int n) {if (n 1; if (n % 6 != 1 && n % 6 != 5) {return 0;} for (int i = 5; i <= sqrt(n); i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return 0;}} return 1;}用连续自然数之和来表达整数（py）
# 输入获取t = int(input())# 算法入口def getResult():arr = [i + 1 for i in range(t)] ans = [] l = 0r = 1total = arr[l] while l t:total -= arr[l]l += 1elif total == t:ans.append(arr[l:r])total -= arr[l]l += 1if r >= t:breakelse:total += arr[r]r += 1else:total += arr[r]r += 1 ans.sort(key=lambda x: len(x)) for an in ans:print(f"{t}={'+'.join(map(str, an))}") print(f"Result:{len(ans)}")# 算法调用getResult()火星文计算（py）
import re # 输入获取s = input()# 算法入口def getResult(s):p = re.compile("(\\d+)\\$(\\d+)") while True:m = p.search(s)if m:subS = m.group()x = int(m.group(1))y = int(m.group(2))s = s.replace(subS, str(3 * x + y + 2), 1)# 注意这里replace只能进行替换第一次出现的，不能替换多次，因此replace方法第三个参数为1，表示只替换首次匹配else:break arr = list(map(int, s.split("#"))) x = arr[0]for y in arr[1:]:x = 2 * x + 3 * y + 4 return x# 算法调用print(getResult(s))寻找身高相近的小朋友（py）
# 输入获取h, n = map(int, input().split())heights = list(map(int, input().split()))# 算法入口def getResult():heights.sort(key=lambda x: (abs(x-h), x))return " ".join(map(str, heights))# 调用算法print(getResult())整型数组按个位值排序
#include using namespace std;int main() {string input;getline(cin, input);vector<pair> w;size_t pos = 0;int cnt = 0;while ((pos = input.find(',')) != string::npos) {w.push_back({input.substr(0, pos) , cnt++});input.erase(0, pos + 1); }w.push_back({input , cnt});sort(w.begin(), w.end(), [](const pair& a, const pair& b) {if (a.first.back() != b.first.back()) return a.first.back() < b.first.back();return a.second < b.second;});for (int i = 0; i < w.size(); i++) {cout << w[i].first;if (i != w.size() - 1) {cout << ",";}}return 0;}按身高和体重排队
#include #include #include typedef struct {int height;int weight;int idx;} Student; int cmp(const void* a, const void* b) {Student* A = (Student*) a;Student* B = (Student*) b; return A->height != B->height ? A->height - B->height : A->weight != B->weight ? A->weight - B->weight : A->idx - B->idx;} int main() {int n;scanf("%d", &n); Student students[n]; for(int i=0; i<n; i++) {scanf("%d", &students[i].height);} for(int i=0; i<n; i++) {scanf("%d", &students[i].weight);students[i].idx = i + 1;}qsort(students, n, sizeof(Student), cmp); char res[100000]; for(int i=0; i<n; i++) {char tmp[1000];sprintf(tmp, "%d", students[i].idx); strcat(res, tmp); if(i < n - 1) {strcat(res, " ");}} puts(res); return 0;}解密犯罪时间(py)
import re reg = re.compile("(([01][0-9])|([2][0-3]))[0-5][0-9]") # 输入获取hour, minute = input().split(":")def dfs(arr, path, res):if len(path) == 4:timeStr = "".join(path)if reg.search(timeStr) is not None:res.append(timeStr)return for i in range(len(arr)):path.append(arr[i])dfs(arr, path, res)path.pop()# 算法入口def getResult():arr = list(hour)arr.extend(list(minute)) arr = list(set(arr)) res = []dfs(arr, [], res)res.sort() index = res.index(hour + minute) if index == len(res) - 1:recentTime = res[0]else:recentTime = res[index + 1] ans = list(recentTime)ans[1] += ":"return "".join(ans)# 调用算法print(getResult())数组连续和
#include #include using namespace std;int n, x;long long res;int main() {cin >> n >> x;vector nums(n);for (int i = 0; i > nums[i];if(x == 0 ) cout << n * (n + 1 ) / 2 << endl;else{for (int i = 0, j = 0, sum = 0; i = x){res += n - i;sum -= nums[j++];}}cout << res << endl;}return 0;}停车场车辆统计
#include #define MAX_N 10000using namespace std;int ct;bool cur;int res;int main(){while(scanf("%d",&cur) == 1){if(cur == 1){ct++;if(ct == 3){res++;ct = 0;}}else{if(ct) res++;ct = 0;}getchar();}if(ct) res++;printf("%d\n",res);return 0;}绘图机器、计算面积
#include #define y0 yy#define y1 yyytypedef long long ll;using namespace std;ll x0,x1,y0,dealtay;ll N,E;ll res;int main(){scanf("%lld %lld",&N,&E);for(int i = 0; i < N; i++){scanf("%lld %lld",&x1, &dealtay);res += abs(y0)*(x1-x0);y0 += dealtay;x0 = x1;}res += abs(y0)*(E-x0);printf("%lld\n",res);return 0;}求最多可以派出多少支团队
#include #include #define MAX(a,b) ((a) > (b) ? (a) : (b)) int cmp(const void* a, const void* b) {return (*(int*) a) - (*(int*) b);} int main() {int n;scanf("%d", &n); int capacities[n];for(int i=0; i= l && capacities[r] >= minCap) {r--;ans++;} // 双人组队while(l = minCap) {// 如果两个人的能力值之和>=minCap，则组队ans++;l++;r--;} else {// 否则将能力低的人剔除，换下一个能力更高的人l++;}} printf("%d\n", ans); return 0;}找朋友
#include #include #include using namespace std;int main() {int n;cin >> n;vector w(n);vector res(n);stack stk;for (int i = 0; i > w[i];}for (int i = n - 1; i >= 0; i--) {while (!stk.empty() && w[stk.top()] <= w[i]) {stk.pop();}if (!stk.empty()) {res[i] = stk.top();}stk.push(i);}for (int i = 0; i < n; i++) {cout << res[i];if (i + 1 < n) {cout << " ";}}return 0;}最长子字符串的长度
#include #include int main() {int m, n;scanf("%d %d", &m, &n); // 记录前车到达终点的时刻，本题后车不可能比前车更早到达，因此如果后车到达时刻 < 前车到达时刻arrived，则后车也是按照前车arrived时刻达到double arrived = 0; for(int i=0; i<m; i++) {// 当前车的速度double speed;scanf("%lf", &speed); // 当前车到达终点的时刻// * 当前车如果比前车更早到达，则被前车阻碍，按前车到达时间算// * 当前车如果比前车更晚到达，则不被前车阻碍，按后车到达时间算arrived = fmax(arrived, n / speed + i); // n*1.0/speed是行驶花费时间； i是第i辆车的出发时间} // 到达时刻 - 出发时刻 = 路上花费的时间double cost = arrived - (m - 1);// 至多保留3个小数位char res[100];sprintf(res, "%.3f", cost); // %g 格式 不会打印无效小数位printf("%g", atof(res)); return 0;}智能驾驶
#include #include #include #define MAX_SIZE 200 // 记录路径中位置的几个状态typedef struct {int x; // 位置横坐标int y; // 位置纵坐标int init; // 到达此位置所需的最少初始油量int remain; // 到达此位置时剩余可用油量int flag; // 到达此位置前有没有加过油} Node; Node *new_Node(int x, int y) {Node *node = (Node *) malloc(sizeof(Node));node->x = x;node->y = y;node->init = 0;node->remain = 0;node->flag = 0;return node;} /** 基于链表实现队列 **/typedef struct ListNode {Node *ele;struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, Node *ele) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));node->ele = ele;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} Node *removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; return removed->ele;} // m * n 的地图int m, n;// 地图矩阵int matrix[MAX_SIZE][MAX_SIZE]; // 上下左右四个方向对应的偏移量int offsets[4][2] = {{-1, 0}, {1,0}, {0,-1}, {0,1}}; int bfs() {// 如果左上角和右下角不可达，则直接返回-1if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {return -1;} // 广搜队列LinkedList *queue = new_LinkedList(); // 起始位置Node *src = new_Node(0, 0); if (matrix[0][0] == -1) {// 如果起始位置就是加油站，则到达(0,0)位置所需初始油量为0，且剩余可用油量为100，且需要标记已加油src->init = 0;src->remain = 100;src->flag = 1;} else {// 如果起始位置不是加油站，则到达(0,0)位置所需的初始油量至少为matrix[0][0], 剩余可用油量为0，未加油状态src->init = matrix[0][0];src->remain = 0;src->flag = 0;} addLast_LinkedList(queue, src); // dist_init[x][y] 用于记录起点 (0, 0) 到达 (x, y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的初始油量int dist_init[MAX_SIZE][MAX_SIZE];for (int i = 0; i < m; i++) {for (int j = 0; j init;dist_remain[0][0] = src->remain; // 广搜while (queue->size > 0) {Node *cur = removeFirst_LinkedList(queue); // 从当前位置cur开始向上下左右四个方向探路for (int i = 0; i x + offsets[i][0];int newY = cur->y + offsets[i][1]; // 新位置越界 或者 新位置是障碍，则新位置不可达，继续探索其他方向if (newX = m || newY = n || matrix[newX][newY] == 0) {continue;} // 如果新位置可达，则计算到达新位置的三个状态数据int init = cur->init; // 到达新位置所需的最少初始油量int remain = cur->remain; // 到达新位置时还剩余的最多可用油量int flag = cur->flag; // 是否加油了 if (matrix[newX][newY] == -1) {// 如果新位置是加油站，则加满油remain = 100;// 标记加过油了flag = 1;} else {// 如果新位置不是加油站，则需要消耗matrix[newX][newY]个油remain -= matrix[newX][newY];} // 如果到达新位置后，剩余油量为负数if (remain 100) {continue;} // 如果可达新位置，则继续检查当前路径策略到达新位置(newX, newY)所需的初始油量init是否比其他路径策略更少if (init > dist_init[newX][newY]) {// 如果不是，则无需探索新位置(newX, newY)continue;} // 当前路径策略到达新位置(newX,newY)所需初始油量init更少，或者，init和前面路径策略相同，但是当前路径策略剩余可用油量remain更多if (init dist_remain[newX][newY]) {// 则当前路径策略更优，记录更优路径的状态dist_init[newX][newY] = init;dist_remain[newX][newY] = remain; // 将当前新位置加入BFS队列Node *next = new_Node(newX, newY);next->init = init;next->remain = remain;next->flag = flag; addLast_LinkedList(queue, next);}}} // dist_init[m - 1][n - 1] 记录的是到达右下角终点位置所需的最少初始油量if (dist_init[m - 1][n - 1] == INT_MAX) {return -1;} else {return dist_init[m - 1][n - 1];}} int main() {scanf("%d,%d", &m, &n); for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &matrix[i][j]);getchar();}} printf("%d\n", bfs()); return 0;}运输时间
#include #include int main() {int m, n;scanf("%d %d", &m, &n); // 记录前车到达终点的时刻，本题后车不可能比前车更早到达，因此如果后车到达时刻 < 前车到达时刻arrived，则后车也是按照前车arrived时刻达到double arrived = 0; for(int i=0; i<m; i++) {// 当前车的速度double speed;scanf("%lf", &speed); // 当前车到达终点的时刻// * 当前车如果比前车更早到达，则被前车阻碍，按前车到达时间算// * 当前车如果比前车更晚到达，则不被前车阻碍，按后车到达时间算arrived = fmax(arrived, n / speed + i); // n*1.0/speed是行驶花费时间； i是第i辆车的出发时间} // 到达时刻 - 出发时刻 = 路上花费的时间double cost = arrived - (m - 1);// 至多保留3个小数位char res[100];sprintf(res, "%.3f", cost); // %g 格式 不会打印无效小数位printf("%g", atof(res)); return 0;}200
电脑病毒感染
#include#include#include#includeusing namespace std;struct Edge {int destination;//弧尾编号int weight;//弧的权值};int main() {int N, link;cin >> N >> link;vector<vector> Graph(N + 1);//邻接表法存储图for (int i = 0; i > u >> v >> w;Edge e;e.destination = v;e.weight = w;Graph[u].push_back(e);}int start;cin >> start;//使用Dijkstra算法计算vector dis(N + 1, INT_MAX);dis[start] = 0;vector visit(N + 1, false);for (int i = 0; i < N + 1; i++) {int u = -1, MIN = INT_MAX;for (int j = 0; j < N + 1; j++) {if (visit[j] == false && dis[j] < MIN) {u = j; MIN = dis[j];}}if (u == -1) {continue;}visit[u] = true;for (Edge edge : Graph[u]) {int v = edge.destination;int w = edge.weight;if (dis[u] + w < dis[v]) {dis[v] = dis[u] + w;}}}int result = 0;for (int i = 1; i < N + 1; i++) {result = max(result, dis[i]);}if (result < INT_MAX) {cout << result;return 0;}else {cout << -1;return 0;}}小朋友分组最少调整次数
#include #include #define MAX_SIZE 90000 typedef struct ListNode {int num;int count;struct ListNode* next;} ListNode; typedef struct LinkedList {int size;ListNode* head;ListNode* tail;} LinkedList; LinkedList* new_LinkedList() {LinkedList* link = (LinkedList*) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addFirst_LinkedList(LinkedList* link, int num, int count) {ListNode* node = (ListNode*) malloc(sizeof(ListNode));node->num = num;node->count = count;node->next = NULL; if(link->size == 0) {link->head = node;link->tail = node;} else {node->next = link->head;link->head = node;} link->size++;} void addLast_LinkedList(LinkedList* link, int num, int count) {ListNode* node = (ListNode*) malloc(sizeof(ListNode));node->num = num;node->count = count;node->next = NULL; if(link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} ListNode* removeFirst_LinkedList(LinkedList* link) {if(link->size == 0) exit(-1); ListNode* removed = link->head; if(link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; return removed;} LinkedList* confirm(LinkedList* queue, int confirmed_num) {// 此方法用于剔除掉队列中已被调整完位置的小朋友，并且抽离后，尝试合并抽离位置前后的小朋友（如果是同一组）// 时间复杂度有点高这里，可能会超时LinkedList* back_queue = new_LinkedList(); while (queue->size > 0) {ListNode* first = removeFirst_LinkedList(queue); if(first->num == confirmed_num) {continue;} if(back_queue->size == 0 || back_queue->tail->num != first->num) {addLast_LinkedList(back_queue, first->num, first->count);} else {back_queue->tail->count += first->count;}} return back_queue;}int main() {// 初始小朋友（序号）排队顺序int nums[MAX_SIZE];int nums_size = 0; while (scanf("%d", &nums[nums_size++])) {if (getchar() != ' ') break;} // 序号->组号 映射关系int map[nums_size + 1];for (int i = 0; i < nums_size; i++) {int num;scanf("%d", &num); map[num] = i / 3;} // 相邻相同组号合并统计LinkedList* queue = new_LinkedList();for (int i = 0; i size == 0 || queue->tail->num != num) {addLast_LinkedList(queue, num, 1);} else {queue->tail->count++;}} // 记录调整次数int moved_count = 0;while(queue->size > 0) {ListNode* first = removeFirst_LinkedList(queue); // 当first.count = 1 时，情况如下// 1 x 1 1 y z// 1 x 1 y 1 zif(first->count == 1) {ListNode* x = queue->head; // 判断x是否存在连续完整分组while (x->count == 3) {removeFirst_LinkedList(queue);x = queue->head;} if(x->num == first->num && x->count == 2) {// 情况：1 2 2 2 x[1 1]// 将开头1，移动进x中moved_count += 1;removeFirst_LinkedList(queue);} else {// 情况如下：// 1 x[2 2] 1 1// 1 x[2] 1 2 1// 将后面的两个1移动到开头moved_count += 2;queue = confirm(queue, first->num);}} else if(first->count == 2) {// 当first.count == 2 时，情况如下：// 1 1 x 1 y zmoved_count += 1;queue = confirm(queue, first->num);}} printf("%d\n", moved_count); return 0;}二叉树计算
思路:
#include #include #define MAX_SIZE 10000 typedef struct TreeNode {int num; // 当前节点的值int childSum; // 当前节点的左子树+右子树的和struct TreeNode *leftChild;struct TreeNode *rightChild;} TreeNode; TreeNode *new_TreeNode(int num) {TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode));node->num = num;node->childSum = 0;node->leftChild = NULL;node->rightChild = NULL;return node;} // 中序遍历序列int midOrder[MAX_SIZE]; // 前序遍历序列int preOrder[MAX_SIZE]; int cmp(const void *a, const void *b) {return *((int *) a) - *((int *) b);} /** * 判断两个子数组是否相同（元素相同，顺序可以不同） * @param midL 子数组1的左边界 * @param preL 子数组2的左边界 * @param size 子数组的长度 * @return 子数组1和子数组2是否相同 */int notEquals(int midL, int preL, int size) {int arr1[size];int arr2[size];for (int i = 0; i < size; i++) {arr1[i] = midOrder[midL + i];arr2[i] = preOrder[preL + i];} qsort(arr1, size, sizeof(int), cmp);qsort(arr2, size, sizeof(int), cmp); for (int i = 0; i preR) return NULL; // 先根据前序遍历序列得到根节点，前序序列的首元素就是根节点int rootNum = preOrder[preL];TreeNode *root = new_TreeNode(rootNum); // 在中序遍历序列中，找到对应根值的位置，这个位置可能有多个，但是只有一个是正确的for (int i = midL; i leftChild = buildTree(midL, i - 1, preL + 1, preL + leftLen);root->rightChild = buildTree(i + 1, midR, preR - rightLen + 1, preR); // 记录该节点：左子树+右子树的和（本题新二叉树节点的值）root->childSum = (root->leftChild == NULL ? 0 : (root->leftChild->num + root->leftChild->childSum)) + (root->rightChild == NULL ? 0 : (root->rightChild->num + root->rightChild->childSum)); break;} return root;} // 二叉树中序遍历void getMidOrder(TreeNode* root) {if (root == NULL) return; // 先遍历左子树TreeNode* leftChild = root->leftChild;if(leftChild != NULL) {getMidOrder(leftChild);} // 再遍历根printf("%d ", root->childSum); // 最后遍历右子树TreeNode* rightChild = root->rightChild;if(rightChild != NULL) {getMidOrder(rightChild);}} int main() {int size = 0; while (scanf("%d", &midOrder[size++])) {if (getchar() != ' ') break;} for (int i = 0; i < size; i++) {scanf("%d", &preOrder[i]);} // 根据中序序列和前序序列还原树结构TreeNode *root = buildTree(0, size - 1, 0, size - 1); // 打印新的二叉树的的中序遍历序列getMidOrder(root); return 0;}分月饼
思路：
#includeusing namespace std;const int N=110;int w[N],n,m,res;void dfs(int u,int sum,int down,int up){//枚举分给第u个人时,月饼总量还剩下sum 第u个人能分到的最小月饼数量为down 最大月饼数量为upif(u==m){if(sum==0)res++;return;}if(down>sum||sumup)return;//不合法情况for(int i=down;i>m>>n;dfs(0,n,1,n);cout<<res<<endl;return 0;}最长连续手牌
思路：
#include #include #include using namespace std;int n;vector w;vector color;vector st;int res = 0;void dfs(int cnt, int preNum, const string &preColor) {res = max(res, cnt);// 更新结果变量resfor (int i = 0; i > num) {w.push_back(num);}string colorStr;getline(cin, colorStr);stringstream colorStream(colorStr);string col;while (colorStream >> col) {color.push_back(col);}n = w.size();st.resize(n, 0);// 初始化标记数组dfs(0, -1, "");// 调用dfs函数进行搜索cout << res << endl;// 输出结果return 0;}5G网络建设
#include #include #include using namespace std;class UnionFind {private:vector parent;public:UnionFind(int n) {parent.resize(n + 1);for (int i = 1; i > n >> m; // 读取节点数和边数UnionFind uf(n);vector<vector> edges;for (int i = 1; i > x >> y >> z >> p; // 读取边的起始节点、结束节点、权重和标志if (p == 1) uf.unite(x, y); // 如果标志为1，直接合并两个节点else {edges.push_back({x, y, z}); // 否则将边加入边列表}}// 按边的权重排序sort(edges.begin(), edges.end(), [](const vector& a, const vector& b) {return a[2] < b[2];});int ans = 0;for (const auto& edge : edges) {if (uf.unite(edge[0], edge[1])) ans += edge[2]; // 如果成功合并两个节点，累加权重}// 判断所有节点是否联通bool ok = true;for (int i = 2; i <= n; i++) {if (uf.find(i) != uf.find(1)) ok = false;}if (ok) {cout << ans << endl; // 如果所有节点联通，输出最小花费}else {cout << -1 << endl; // 否则输出-1}return 0;}攀登者2
#include #define MAX_SIZE 100000 int canClimb[MAX_SIZE] = {0};int canClimb_count = 0; void climb(const int heights[], int heights_size, int strength, int direction) {// 找到第一个地面位置int j = 0;while (j < heights_size && heights[j] != 0) {j++;} int cost = 0; // 攀登体力总消耗（包括上山，下山）//int upCost = 0; // 上山体力消耗//int downCost = 0; // 下山体力消耗 // 开始攀登for (int i = j + 1; i 0) {// 如果过程是上坡cost += diff * 3;//upCost += diff * 2; // 则上山时，体力消耗 = 高度差 * 2//downCost += diff; // 相反的下山时，体力消耗 = 高度差 * 1 // 由于 height[i] > heights[i-1]，因此如果 height[i] > heights[i+1] 的话，位置 i 就是山顶if (i + 1 >= heights_size || heights[i] > heights[i + 1]) {// 计算攀登此山顶的上山下山消耗的体力和if (cost < strength) {//if (upCost + downCost < strength) {// 需要注意，逆序heights数组后，我们对于的山峰位置需要反转int idx = direction ? i : heights_size - i - 1; if(!canClimb[idx]) {// 如果不超过自身体力，则可以攀登canClimb[i] = 1;canClimb_count++;}}} } else if (diff < 0) {// 如果过程是下坡cost -= diff * 3;//upCost -= diff; // 则上山时，体力消耗 = 高度差 * 1//downCost -= diff * 2; // 相反的下山时，体力消耗 = 高度差 * 2// heights[i] < heights[i-1]，因此位置i不可能是山顶}}} void reverse(int nums[], int nums_size) {int i = 0;int j = nums_size - 1; while (i < j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp; i++;j--;}} // 算法实现（本题实际考试为核心代码模式，因此考试时只需要写出此函数实现即可）int getResult(int heights[], int heights_size, int strength) {climb(heights, heights_size, strength, 1); reverse(heights, heights_size);climb(heights, heights_size, strength, 0); return canClimb_count;} // 输入处理int main() {int heights[MAX_SIZE];int heights_size = 0; while (scanf("%d", &heights[heights_size++])) {if (getchar() != ',') break;} int strength;scanf("%d", &strength); printf("%d\n", getResult(heights, heights_size, strength)); return 0;}园区参观路径(dp)
#include int main() {// 长n -> 行数, 宽m -> 列数int n, m;scanf("%d %d", &n, &m); // 地图矩阵，这里把二维压缩为了一维int matrix[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 由于matrix是一维数组，所以这里(i, j)二维坐标也要转成一维坐标scanf("%d", &matrix[i][j]);}} if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {puts("0");return 0;} long dp[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {dp[i][j] = 0;}} dp[0][0] = 1; for (int i = 0; i < n; i++) {for (int j = 0; j 0) {dp[i][j] += dp[i - 1][j];} if (j > 0) {dp[i][j] += dp[i][j - 1];}}} printf("%ld\n", dp[n - 1][m - 1]); return 0;}部门人力分配
#include #include #include using namespace std;int num, m;vector nums;int check(const vector& nums, int m, int x) {int cnt = 0;int l = 0, r = nums.size() - 1;while (l <= r) {if (nums[l] + nums[r] <= x) {l++;r--;}else r--;cnt++;}return cnt > m; while ( cin >> num ) nums.push_back(num);sort(nums.begin(), nums.end());int n = nums.size();int l = nums[n - 1], r = 1e9;while (l > 1;if (check(nums, m, mid)) r = mid;else l = mid + 1;}cout << l << endl;return 0;}结队编程
#include #include #define MAX_SIZE 6000 typedef struct Node {int idx; // 当前节点的值在原数组中的索引int val; // 当前节点的值struct Node *left; // 当前节点的左子节点struct Node *right; // 当前节点的右子节点int count; // 当前节点的左子树中节点数量} Node; Node *new_Node(int idx, int val) {Node *node = (Node *) malloc(sizeof(Node));node->idx = idx;node->val = val;node->left = NULL;node->right = NULL;node->count = 0; return node;} /** * 向二叉搜索树中插入新节点 * * @param root （树/子树）根节点 * @param node 要插入的新节点 * @param res 数组，其中res[i]代表第i个节点右边比自己小的元素的个数 * @return 根节点 */Node *insertNode(Node *root, Node *node, int res[]) {if (root == NULL) {return node;} // 由于本题中每个员工有独一无二的职级，即levels中所有元素值都不互相相同，因此这里非大即小if (node->val val) {// 如果要插入的新节点的值，比根节点小，则插入根节点左子树root->count++; // 根节点左子树的节点树+1root->left = insertNode(root->left, node, res); // 递归进入左子树继续比较} else {// 如果要插入的新节点的值，比根节点大，则需要插入根节点的右子树res[node->idx] += root->count + 1; // 本处代码原理请看题目解析中的图示root->right = insertNode(root->right, node, res); // 递归进入右子树继续比较} return root;} void reverse(int nums[], int nums_size) {int l = 0;int r = nums_size - 1; while (l = 0; i--) {root = insertNode(root, new_Node(i, levels[i]), rightSmaller);} reverse(levels, levels_size);root = NULL; // leftSmaller[i] 记录的是 levels[i] 左边比自己小的元素的个数int leftSmaller[MAX_SIZE] = {0};for (int i = n - 1; i >= 0; i--) {root = insertNode(root, new_Node(i, levels[i]), leftSmaller);}reverse(leftSmaller, levels_size); // 统计各个元素： 左小 * 右大 + 左大 * 右小long sum = 0;for (int i = 0; i < n; i++) {// 由于本题中每个员工有独一无二的职级，即levels中所有元素值都不互相相同int leftSmallerCount = leftSmaller[i];// 索引i的左边有 i 个元素，而索引i的左边有leftSmallerCount个比自己小的，因此剩余 i - leftSmallerCount 都是比自己大的int leftBiggerCount = i - leftSmallerCount; int rightSmallerCount = rightSmaller[i];// 索引i右边有 n-i-1 个元素，而索引i的右边有rightSmallerCount比自己小的，因此剩余 n-i-1-rightSmallerCount 都是比自己大的int rightBiggerCount = n - i - 1 - rightSmallerCount; sum +=leftSmallerCount * rightBiggerCount + leftBiggerCount * rightSmallerCount;} return sum;} int main() {int n;scanf("%d", &n); int levels[MAX_SIZE];int levels_size = 0;while (scanf("%d", &levels[levels_size++])) {if (getchar() != ' ') break;} printf("%ld\n", getResult(n, levels, levels_size)); return 0;}数据单元的变化替换
#include #include #define TRUE 1#define FALSE 0 #define MAX_SIZE 26#define MAX_CELL_CONTENT_LENGTH 110 // cells[i]记录每个单元格的内容char cells[MAX_SIZE][MAX_CELL_CONTENT_LENGTH];int cells_size = 0; // res记录最后打印结果char res[MAX_SIZE * MAX_CELL_CONTENT_LENGTH] = {'\0'}; int changeCell(int index) {// 原始单元格内容char *cell = cells[index];unsigned long long cell_length = strlen(cell); // 替换引用后的单元格内容char cell_changed[MAX_CELL_CONTENT_LENGTH] = {'\0'};unsigned long long cell_changed_length = 0; int l = 0;while (cell[l] != '\0') {if (cell[l] != '<') {// 非中的内容直接记录到cell_changedcell_changed[cell_changed_length++] = cell[l++];continue;} // 引用单元格编号只能是A~Z的字母，即引用引用字符串长度只能是3，比如""// 因此 l ~ l+2 是引用范围，l指向''， l+1指向单元格编号if (cell[l + 2] != '>') {return FALSE;} // 引用单元格的编号char reference_cell_num = cell[l + 1];// 当前单元格的编号char self_cell_num = (char) ('A' + index); // 引用单元格编号只能是A~Z的字母，且不能自引用if (reference_cell_num 'Z' || reference_cell_num == self_cell_num) {return FALSE;} // 引用单元格的数组索引， 'A' -> 0... 'Z' -> 25int reference_index = reference_cell_num - 'A'; // 引用单元格编号不存在if (reference_index >= cells_size) {return FALSE;} if (!changeCell(reference_index)) return FALSE; // 将单元格内容中的引用部分，替换为被引用的单元格的内容strcat(cell_changed, cells[reference_index]);// 将 “引用” 替换为 “单元格内容”后，更新cell_changed的长度cell_changed_length = strlen(cell_changed); // 将 l 移动到 l+2指向的'>' 后面l += 3;} strcpy(cells[index], cell_changed); return TRUE;} int main() {char s[MAX_SIZE * MAX_CELL_CONTENT_LENGTH];scanf("%s", s); // 按照分隔符","截取输入字符串char *token = strtok(s, ",");while (token != NULL) {strcpy(cells[cells_size++], token);token = strtok(NULL, ",");} // 对每个单元格内容进行“引用”替换for (int i = 0; i < cells_size; i++) {if (!changeCell(i)) {// 如果某个单元格"引用"替换失败，则返回"-1"puts("-1");return 0;} else {// 否则记录该单元格内容到结果字符串strcat(res, cells[i]); if (i != cells_size - 1) {strcat(res, ",");}}} puts(res); return 0;}高效货运
枚举
#include using namespace std;int main() {int wa, wb, wt, pa, pb;cin >> wa >> wb >> wt >> pa >> pb;int ans = 0;for (int i = 1; i = wt) {break; // 如果超过货车容积，结束循环}if ((wt - a) % wb == 0) {int j = (wt - a) / wb; // 计算运输 B 货物的数量ans = max(ans, i * pa + j * pb); // 计算对应的价值，更新答案}}cout << ans << endl;return 0;}找数字
#include #include using namespace std;int main() {int n;cin >> n;// 输入一个整数 nvector w;// 将整数 n 转换为二进制表示，存储到向量 w 中while (n) {w.push_back(n % 2);n /= 2;}w.push_back(0);// 在向量末尾添加一个前导0int m = w.size();// 获取向量长度// 遍历向量，找到第一个01子串，进行交换操作for (int i = 0; i < m; i++) {if (i + 1 < m && w[i] == 1 && w[i + 1] == 0) {swap(w[i], w[i + 1]);// 使用 swap 函数交换向量中的元素int l = 0, r = i - 1;// 将低位中的1全部移动到最低位，0移动到最高位，以保证结果尽可能小while (l < r) {while (l < r && w[l]) {l++;}while (l < r && w[r] == 0) {r--;}if (l < r) {swap(w[l], w[r]);// 使用 swap 函数交换向量中的元素l++;r--;}}break;// 跳出循环}}int res = 0;// 将二进制向量转换为十进制数for (int i = 0; i < m; i++) {if (w[i]) {res += 1 << i;}}cout << res << endl;// 输出结果return 0;}中文分词模拟器(无oj)
#include using namespace std;string joinString (vector arr , string s){string res = "";for (auto x : arr){res += x;res += s;}return res.substr(0 , res.size() - s.size());}// 动态规划求解字符串s是否能被某单词列表组成// 在有多种拆分情况下，考虑从左到右长度尽量长的单词去切分string solve(const string& s, const vector& words) {int n = s.length();vector f(n + 1, false); // f[i]表示s[i:]这个后缀能被某单词列表组成f[n] = true; // 空串能被某单词列表组成for (int i = n; i >= 0; i--) { // 从后往前求解for (const string& x : words) { // 遍历单词列表int m = x.length(); // 单词长度if (i + m <= n && s.substr(i, m) == x && f[i + m]) { // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成f[i] = true; // 则s[i:]能被某单词列表组成break;}}}// 接下来考虑如何从f这个动态规划数组中拆出具体方案vector res; // 记录分解方式if (!f[0]) { // 如果s不能被某单词列表组成, 直接返回本身，用逗号拼接string res = "";for (auto x : s){res += x;res += ",";}return res.substr(0 , res.size() - 1);}int i = 0;// 从前往后求解while (i < n) {int mx = -1; // 记录从i开始，最长可能的长度，需要满足两个条件: 这个前缀出现在单词中，去掉这个前缀，后缀还是能被组成// 遍历单词列表for (const string& x : words) {// 单词长度int m = x.length();// 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成if (i + m <= n && s.substr(i, m) == x && f[i + m]) {mx = max(mx, m);}}// 记录分解方式res.push_back(s.substr(i, mx));i += mx;}// 返回分解方式return joinString(res , ",");}int main() {string s;getline(cin, s);string wordsInput;getline(cin, wordsInput);vector words;size_t start = 0;size_t end = wordsInput.find(",");while (end != std::string::npos) {words.push_back(wordsInput.substr(start, end - start));start = end + 1;end = wordsInput.find(",", start);}words.push_back(wordsInput.substr(start, end));// 对s split先vector asks;start = 0;end = s.find(",");while (end != std::string::npos) {asks.push_back(s.substr(start, end - start));start = end + 1;end = s.find(",", start);}asks.push_back(s.substr(start, end));// 一个个单词去dpvector res;for (const string& x : asks) {res.push_back(solve(x, words));}cout << joinString(res , ",") << endl;return 0;}符号运算
#include #include #include #define MAX_LENGTH 200 // 分数结构typedef struct Fractions {int fa; // 分母int ch; // 分子} Fractions; Fractions *new_Fractions(int fa, int ch) {Fractions *fra = (Fractions *) malloc(sizeof(Fractions));fra->fa = fa;fra->ch = ch;return fra;} // 操作数栈Fractions *oper_num[MAX_LENGTH];int oper_num_size = 0; // 操作符栈char oper_sign[MAX_LENGTH];int oper_sign_size = 0; // 辗转相除法，求两个数的最大公约数int getMaxCommonDivisor(int x, int y) {while (y != 0) {int tmp = y;y = x % y;x = tmp;}return x;} // 取出oper_num栈顶两个操作数进行运算void calc() {// 操作数顺序会对运算产生影响Fractions *b = oper_num[--oper_num_size]; // 栈顶元素是运算符右边的操作数Fractions *a = oper_num[--oper_num_size]; // 栈顶倒数第二个元素是运算符左边的操作数 // 运算符char op = oper_sign[--oper_sign_size]; // 记录运算结果Fractions *result = new_Fractions(1, 0); if (op == '+') {result->fa = a->fa * b->fa;result->ch = a->ch * b->fa + b->ch * a->fa;} else if (op == '-') {result->fa = a->fa * b->fa;result->ch = a->ch * b->fa - b->ch * a->fa;} else if (op == '*') {result->fa = a->fa * b->fa;result->ch = a->ch * b->ch;} else if (op == '/') {result->fa = a->fa * b->ch;result->ch = a->ch * b->fa;} oper_num[oper_num_size++] = result;} int main() {char s[MAX_LENGTH];gets(s); // +,-,*,/ 运算符优先级int priority[128] = {0};priority['+'] = 1;priority['-'] = 1;priority['*'] = 2;priority['/'] = 2; // 操作数的字符缓存容器char numStr[MAX_LENGTH] = {'\0'};int numStr_size = 0; int i = 0;while (s[i] != '\0') {char c = s[i]; // 遇到数字字符if (c >= '0' && c = '0' && c = 当前运算符，就需要不停出栈运算while (oper_sign_size > 0 && oper_sign[oper_sign_size - 1] != '(' &&priority[c] 1) {calc();} // oper_num栈中只剩一个数时，该数就是表达式结果Fractions *result = oper_num[--oper_num_size]; // 如果结果的分母为0（除数为0），则不合法if (result->fa == 0) {puts("ERROR");return 0;} // 求分子、分母的最大公约数，并进行约份，求得最简格式的分子，分母int k = getMaxCommonDivisor(result->fa, result->ch);result->fa /= k;result->ch /= k; // 求计算结果的符号，这里用乘法是为了避免 分母小，分子大，除法结果为0的情况，这样会丢失符号信息if (result->fa * result->ch fa);int ch = abs(result->ch); if (fa == 1) {// 如果分母为1，则直接输出分子printf("%d\n", ch);} else {// 如果分母不为1，则输出 分子 / 分母printf("%d/%d\n", ch, fa);} return 0;}根据IP查找城市
#include #include #include #include #define CITY_NAME_LENGTH 100#define CITY_LIST_LENGTH 500000#define QUERY_LIST_LENGTH 700000 typedef struct Range {char city[CITY_NAME_LENGTH];long startIpDec;long endIpDec;long ipLen;} Range; // IP地址转整型long ip2dec(char *ip) {long res = 0; int n1, n2, n3, n4;sscanf(ip, "%d.%d.%d.%d", &n1, &n2, &n3, &n4); res = n1 | (res << 8);res = n2 | (res << 8);res = n3 | (res << 8);res = n4 | (res <city, city);range->startIpDec = ip2dec(startIpStr);range->endIpDec = ip2dec(endIpStr);range->ipLen = range->endIpDec - range->startIpDec + 1;return range;} // 第一行输入char s1[CITY_LIST_LENGTH]; // 第二行输入char s2[QUERY_LIST_LENGTH];Range *ranges[CITY_LIST_LENGTH];int ranges_size = 0; int main() {gets(s1); char *token1 = strtok(s1, ";");while (token1 != NULL) {// 提取各个城市IP列表信息char city[CITY_NAME_LENGTH] = {'\0'};char startIpStr[10] = {'\0'};char endIpStr[10] = {'\0'}; sscanf(token1, "%[^=]=%[^,],%[^,]", city, startIpStr, endIpStr);ranges[ranges_size++] = new_Range(city, startIpStr, endIpStr); token1 = strtok(NULL, ";");}gets(s2); // 遍历待查询的IP地址char *token2 = strtok(s2, ",");while (token2 != NULL) {long ipDec = ip2dec(token2); // 记录该目标IP地址的最佳匹配城市char *city = "";// 记录最佳匹配城市IP段的长度long minLen = LONG_MAX; // 将带查询IP与城市IP段列表逐一匹配for (int i = 0; i = ranges[i]->startIpDec && ipDec endIpDec && minLen > ranges[i]->ipLen) {city = ranges[i]->city;minLen = ranges[i]->ipLen;}} printf("%s", city); token2 = strtok(NULL, ","); if(token2 != NULL) {printf(",");}} return 0;}文件缓存系统(py)
# 双向链表节点class Node:def __init__(self, key, val, freq):""":param key: 记录本题的键:param val: 记录本题的值:param freq: 记录该键被访问的次数"""self.key = keyself.val = valself.freq = freqself.prev = Noneself.next = None# 双向链表class Link:def __init__(self):self.size = 0self.head = Noneself.tail = None def addLast(self, node):"""尾插:param node: 要被插入的节点"""if self.size == 0:# 空链表，则node节点插入后，即为头、尾节点self.head = nodeself.tail = nodeelse:# 非空链表，则node节点插入到tail节点后面self.tail.next = nodenode.prev = self.tailself.tail = node self.size += 1 def remove(self, node):"""删除指定节点:param node: 要删除的节点"""if self.size == 0:# 空链表没有节点，所以无法删除return if self.size == 1:# 链表只有一个节点，则删除完后，变为空链表self.head = Noneself.tail = Noneelif self.head == node:# 如果要删除的节点是头节点self.head = self.head.nextself.head.prev = Noneelif self.tail == node:# 如果要删除的节点是尾节点self.tail = self.tail.prevself.tail.next = Noneelse:# 如果要删除的节点是中间节点node.prev.next = node.nextnode.next.prev = node.prev self.size -= 1# LFU缓存class LFUCache:def __init__(self, capacity):self.keyMap = {}# keyMap用于记录key对应的nodeself.freqMap = {}# freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的self.capacity = capacity# LFU缓存中能记录的最多key的数量self.minFreq = 0# LFU缓存中所有的key中最少的访问次数 def get(self, key):# 如果文件不存在，则不作任何操作。if key not in self.keyMap:return # 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间node = self.keyMap[key]self.incNodeFreq(node) def put(self, key, val):# 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中if key in self.keyMap:return # 当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小位置，再存放新文件。while self.capacity 0:self.minFreq = min(self.freqMap.keys())else:# 文件系统没有缓存文件了，则最少次数为0，表示文件系统空了self.minFreq = 0 # 新增文件，则文件系统容量减少self.capacity -= val# 新增文件的访问次数为1，因此最少访问次数变为了1self.minFreq = 1node = Node(key, val, self.minFreq)# 执行新增操作，freqMap和keyMap都要新增对应文件的记录self.freqMap.setdefault(self.minFreq, Link())self.freqMap.get(self.minFreq).addLast(node)self.keyMap[key] = node def incNodeFreq(self, node):"""增加key的访问次数:param node: key对应的node"""# 由于key的访问次数增加，因此要从原访问次数的链表中删除self.freqMap[node.freq].remove(node) # 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数if self.freqMap[node.freq].size == 0:# 最少次数的链表空了，则删除对应最少次数的记录del self.freqMap[node.freq] # 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）if node.freq == self.minFreq:self.minFreq += 1 # 当前key访问次数++node.freq += 1 # 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）self.freqMap.setdefault(node.freq, Link())self.freqMap[node.freq].addLast(node)# 输入获取m = int(input()) lfu = LFUCache(m) n = int(input()) for _ in range(n):operation = input().split() op = operation[0]fileName = operation[1] if "put" == op:fileSize = int(operation[2])lfu.put(fileName, fileSize)else:lfu.get(fileName) if lfu.capacity == m:print("NONE")else:ans = list(lfu.keyMap.keys())ans.sort()print(",".join(ans))员工派遣
#include using namespace std;typedef long long LL;LL x, y, cntx, cnty;bool check(LL k, LL x, LL y, LL cntx, LL cnty) {LL a = k / x - k / (x * y);LL b = k / y - k / (x * y);LL c = k / (x * y);LL d = k - a - b - c;return d >= max(0LL, cntx - b) + max(0LL, cnty - a);}int main(){cin >> x >> y >> cntx >> cnty;LL l = 1, r = 1e18;while (l > 1;if (check(mid, x, y, cntx, cnty)) r = mid;else l = mid + 1;}cout << l << endl;return 0;}跳格子3
#include #include #define MAX_SIZE 100000 int main() {// 输入获取int n;scanf("%d", &n); int scores[n];for (int i = 0; i < n; i++) {scanf("%d", &scores[i]);} int k;scanf("%d", &k); // 核心代码// 第i个格子，可以从第i-k个格子~第i-1个格子调过来，因此本题滑窗的长度相当于k+1k++; // dp[i]表示跳到第i个格子能得到的最大分数int dp[n];dp[0] = scores[0]; // 单调队列（单调递减，队首是滑窗最大值）int queue[MAX_SIZE];int queue_size = 0; queue[queue_size++] = scores[0];int queue_first_idx = 0; // 初始滑窗的形成过程（即只有新增尾部元素的过程）for (int i = 1; i n时, 需要取n, 此时只有滑窗形成过程，没有滑窗移动过程// dp[i] = max(dp[0]~dp[i-1]) + scores[i]// 即单调队列队首保存的是max(dp[0]~dp[i-1])dp[i] = queue[queue_first_idx] + scores[i]; // 保持单调队列的单调递减性，即如果后入队的dp[i] 大于 队尾元素，则队尾元素出队while (queue_size > 0 && dp[i] > queue[queue_first_idx + queue_size - 1]) {queue_size--;} // 当队尾没有比dp[i]更小的元素后，dp[i]才能入队queue[queue_first_idx + queue_size] = dp[i];queue_size++;} // 滑窗的右移过程（即相较于老滑窗失去一个首元素，新增一个尾元素）for (int i = k; i 0 && dp[i] > queue[queue_first_idx + queue_size - 1]) {queue_size--;} queue[queue_first_idx + queue_size] = dp[i];queue_size++;} printf("%d\n", dp[n - 1]); return 0;}贪吃的猴子
#include #include int main() {int n;std::cin >> n;std::vector nums(n);for (int i = 0; i > nums[i];}int k;std::cin >> k;int number = 0;for (int i = 0; i = 0) {number -= nums[l];number += nums[r];ans = std::max(ans, number);r--;l--;}std::cout << ans << std::endl;return 0;}项目排期
#include#include#include#include using namespace std;// 定义检查函数，判断在x天内是否能完成n个人的m个工作bool check(int x, int cnt, vector& choose, vector& w) {if (cnt == w.size()) {return true;}for (int i = 0; i 0 && choose[i] == choose[i - 1]) {continue;}// 如果第i个人能够完成当前工作，则更新状态并继续检查下一个工作if (choose[i] + w[cnt] <= x) {choose[i] += w[cnt];if (check(x, cnt + 1, choose, w)) {return true;}choose[i] -= w[cnt];}}return false;}vector w;int num;int main() {while (cin >> num) w.push_back(num);int n = w.back();w.pop_back();// 对工作时间向量进行降序排序sort(w.begin(), w.end(), greater{});// 初始化二分查找的左右边界int l = 1, r = accumulate(w.begin(), w.end(), 0);// 使用二分查找确定最少需要的天数while (l > 1;// 初始化选择数组，用于标记每个人完成的工作时间vector choose(n, 0);if (check(mid, 0, choose, w)) r = mid;else l = mid + 1; }cout << l << endl;return 0;}亲子游戏
#include #include #include using namespace std;// 定义广度优先搜索函数int bfs(queue<pair>& q, vector<vector>& g, vector<vector>& w, vector& dx, vector& dy, int n) {while (!q.empty()) {// 从队列中取出当前位置pair t = q.front();q.pop();int x = t.first, y = t.second;// 如果当前位置为终点，返回糖果数量if (g[x][y] == -2) {return w[x][y];}// 遍历四个方向for (int i = 0; i < 4; i++) {int x1 = x + dx[i], y1 = y + dy[i];// 判断是否越界或者是不可访问的位置if (x1 = n || y1 = n || g[x1][y1] == -1) {continue;}// 如果该位置未访问过，将其加入队列，并初始化糖果数量为0if (w[x1][y1] == 0) {q.push({x1, y1});w[x1][y1] = 0;}// 更新糖果数量，取当前位置糖果数和上一步位置的糖果数量之和的最大值w[x1][y1] = max(w[x1][y1], max(0, g[x1][y1]) + w[x][y]);}}// 如果无法到达终点，返回-1return -1;}int main() {int n;cin >> n;// 存储糖果数量的二维数组w，初始值为0vector<vector> w(n, vector(n, 0));// 存储起点坐标的队列queue<pair> q;// 存储地图元素的二维数组gvector<vector> g(n, vector(n, 0));// 读取地图元素并初始化起点和糖果数量数组for (int i = 0; i < n; i++) {for (int j = 0; j > g[i][j];if (g[i][j] == -3) {// 添加起点q.push({i, j});w[i][j] = 0;}}}// 四个方向的移动vector dx = {-1, 1, 0, 0};vector dy = {0, 0, 1, -1};// 调用广度优先搜索函数获取结果int result = bfs(q, g, w, dx, dy, n);cout << result << endl;return 0;}可以处理的最大任务数
#include #include #include using namespace std;vector a[100005];int solve() {int ans = 0;priority_queue<int, vector, greater> pq; // 使用小顶堆作为待处理队列for (int i = 0; i < 100005; i++) {while (!pq.empty() && pq.top() < i) {pq.pop(); // 第一步：移除已经结束的任务}if (!a[i].empty()) {for (int j = 0; j > n; // 输入任务数量for (int i = 0; i > x >> y;a[x].push_back(y); // 存储任务的开始和结束时间}cout << solve() << endl;return 0;}推荐多样性
#include #include #include #define MAX_ROWS 100#define MAX_ROW_LEN 10000 /* 链表节点 */typedef struct Node {int val;struct Node *next;} Node; /* 链表 */typedef struct Link {int size;Node *head;Node *tail;} Link; // 创建链表Link *new_Link() {Link *link = (Link *) malloc(sizeof(Link)); link->size = 0;link->head = NULL;link->tail = NULL; return link;} // 尾插void addLast_Link(Link *link, int val) {Node *node = (Node *) malloc(sizeof(Node));node->val = val;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} // 头删int removeFirst_Link(Link *link) {if (link->size == 0) exit(-1); Node *removed = link->head;if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; int val = removed->val;free(removed); return val;} int main() {int n, k;scanf("%d %d", &n, &k); getchar(); Link *lists[MAX_ROWS];int lists_size = 0; char s[MAX_ROW_LEN];while (gets(s)) {// 本地测试，以空行作为输入截止条件if (strlen(s) == 0) break; Link *link = new_Link(); char *token = strtok(s, " ");while (token != NULL) {addLast_Link(link, atoi(token));token = strtok(NULL, " ");} lists[lists_size++] = link;} // 窗口矩阵，k行n列，每一列对应一个窗口，这里将二维矩阵一维化，方便后面赋值int windows[k * n];// 窗口矩阵中正在赋值的索引位置int idx = 0;// 正在从第level个列表中取值int level = 0; // 当窗口矩阵填满后，结束循环while (idx < k * n) {// 当前轮次是否发生了"借"动作int flag = 0; // 从第level个列表中取前n个元素for (int i = 0; i size == 0 && lists_size > 1) {// 删除第level个空列表for (int j = level + 1; j < lists_size; j++) {lists[j - 1] = lists[j];}lists_size--;level %= lists_size; // 防止越界flag = 1; // 发生了"借"动作}} // 如果没有发生"借"动作，则需要切到下一行if (!flag) {level = (level + 1) % lists_size; // 防止越界}} // 遍历列号for (int j = 0; j < n; j++) {// 遍历行号for (int i = 0; i < k; i++) {// 按列打印printf("%d", windows[i * n + j]);if (j != n - 1 || i != k - 1) {printf(" ");}}} return 0;}两个字符串间的最短路径问题
#include #include #include int main() {char A[10000];scanf("%s", A); char B[10000];scanf("%s", B); int m = (int) strlen(B);int n = (int) strlen(A); // 初始时preRow记录第一行上各点到(0,0)点的最短距离，即为(0,0) -> (0,j) 的直线路径int preRow[n + 1];for (int j = 0; j <= n; j++) {preRow[j] = j;} // 初始时curRow记录第二行上各点到(0,0)点的最短距离int curRow[n + 1]; for (int i = 1; i (i, 0) 的直线路径curRow[0] = i; for (int j = 1; j <= n; j++) {if (A[j - 1] == B[i - 1]) {// 如果可以走斜线，则选走斜线的点curRow[j] = preRow[j - 1] + 1;} else {// 如果不能走斜线，则从当前点的上方点、左方点中选择一个较小值curRow[j] = (int) fmin(preRow[j], curRow[j - 1]) + 1;}} // 压缩for (int j = 0; j <= n; j++) preRow[j] = curRow[j];} printf("%d", curRow[n]); return 0;}跳马
#includeusing namespace std;const int N = 30;char g[N][N]; // 存储地图int n, m; // 地图的行数和列数int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2}; // 马的移动方向（x轴）int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1}; // 马的移动方向（y轴）unordered_map<int, vector<vector>> dist; // 标记从每一个马的当前位置出发到达(i, j)的最短距离// BFS算法，计算从马的当前位置出发到达目标位置(i, j)的最短距离void bfs(int x, int y, int u, int k) {queue<pair> q;q.push({x, y});dist[u][x][y] = 0;while (q.size()) {auto [x1, y1] = q.front();q.pop();for (int i = 0; i < 8; i++) {int x2 = x1 + dx[i], y2 = y1 + dy[i];// 判断是否越界，以及是否已经访问过，距离是否超过了kif (x2 = n || y2 = m || dist[u][x2][y2] = k) {continue;}dist[u][x2][y2] = dist[u][x1][y1] + 1;q.push({x2, y2});}}}int main() {cin >> n >> m; // 输入地图的行数和列数vector<pair> pos; // 存储马的初始位置// 遍历输入地图for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int u = i * m + j;dist[u] = vector<vector>(n, vector(m, 0x3f3f3f3f));// 初始化距离为无穷大cin >> g[i][j];// 如果当前位置是马的起点，则进行BFS计算最短距离，并将起点位置加入pos列表if (g[i][j] >= '1' && g[i][j] <= '9') {bfs(i, j, u, g[i][j] - '0');pos.push_back({i, j});}}}int ans = 0x3f3f3f3f; // 初始化最终答案为无穷大// 遍历所有可能的目标位置for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int cnt = 0;// 遍历所有马的起点位置，计算到达目标位置的总距离for (auto &p : pos) {int u = p.first * m + p.second;// 如果有某个马无法到达目标位置，则将cnt设为无穷大if (dist[u][i][j] == 0x3f3f3f3f) {cnt = 0x3f3f3f3f;break;}cnt += dist[u][i][j];}// 更新最终答案为所有目标位置中的最小值ans = min(ans, cnt);}}// 输出最终答案，如果无法到达任何目标位置，则输出-1if (ans == 0x3f3f3f3f) puts("-1");else cout << ans << endl;return 0;}路口最短时间问题
#include #include #define MAX_SIZE 10 int n, m;int lights[MAX_SIZE][MAX_SIZE];int timePerRoad;int rowStart, colStart;int rowEnd, colEnd; int offsets[4][2] = {{-1, 0}, {1,0}, {0,-1}, {0,1}}; int visited[MAX_SIZE][MAX_SIZE] = {0}; /*! * 根据三点坐标，确定拐弯方向 * @param preX 前一个点横坐标 * @param preY 前一个点纵坐标 * @param curX 当前点横坐标 * @param curY 当前点纵坐标 * @param nextX 下一个点横坐标 * @param nextY 下一个点纵坐标 * @return cur到next的拐弯方向， >0 表示向左拐， ==0 表示直行（含调头）， curint dx1 = curX - preX;int dy1 = curY - preY; // 向量 cur->nextint dx2 = nextX - curX;int dy2 = nextY - curY; // 两个向量的叉积 >0 表示向左拐， ==0 表示直行（含调头）， = minCost[0]) {return;} // 如果当前点是终点，且花费的时间cost更少，则更新minCostif (curX == rowEnd && curY == colEnd) {minCost[0] = cost;return;} // 否则，从当前位置的四个方向继续探索路径for (int i = 0; i < 4; i++) {// 新位置int nextX = curX + offsets[i][0];int nextY = curY + offsets[i][1]; // 新位置越界或者已经访问过，则不能访问，继续其他方向探索if (nextX = n || nextY = m || visited[nextX][nextY]) {continue;} // 标记新位置访问过visited[nextX][nextY] = 1; // 根据pre,cur,next三点，判断拐弯方向int direction = getDirection(preX, preY, curX, curY, nextX, nextY); // cur到达next位置必须要增加timePreRoad个时间int increment = timePerRoad;// preX=-1, preY=-1 表示pre位置不存在，此时探索下一个位置不需要花费等待周期if (preX >= 0 && preY >= 0 && direction >= 0) {// pre位置存在，且cur->next是左拐或者直行，则需要增加当前位置对应的等待周期时间increment += lights[curX][curY];} // 递归进入新位置dfs(nextX, nextY, curX, curY, cost + increment, minCost); // 回溯visited[nextX][nextY] = 0;}} int getResult() {// 记录访问过的点，防止走回路// 初始时起点位置标记为访问过visited[rowStart][colStart] = 1; // 记录起点到终点的最小花费时间，这里minCost定义为数组，是为了其在dfs函数调用结束后，不会被释放内存，因为它是引用类型变量int minCost[] = {INT_MAX};// 开始暴搜所有起点到终点的路径dfs(rowStart, colStart, -1, -1, 0, minCost);return minCost[0];} int main() {scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &lights[i][j]);}} scanf("%d", &timePerRoad); scanf("%d %d", &rowStart, &colStart); scanf("%d %d", &rowEnd, &colEnd); printf("%d\n", getResult()); return 0;}字符串拼接
#include #include #define MAX_SIZE 31 char s[MAX_SIZE];int s_len;int n; /*! * 全排列求解 * @param pre 排列最后一个字符在cArr中的位置 * @param level 排列的长度 * @param used used[i] 用于标记 s[i] 元素是否已使用 * @param count 符号要求的排列有几个 * @return count */int dfs(int pre, int level, int used[], int count) {// 当排列长度到达n，则是一个符合要求的排列if (level == n) {// 符合要求的排列个数+1return ++count;} for (int i = 0; i = 0 && s[i] == s[pre]) continue; // 树层去重(去除重复排列)if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue; used[i] = 1;count = dfs(i, level + 1, used, count);used[i] = 0;} return count;} int cmp(const void *a, const void *b) {return *((char *) a) - *((char *) b);} int getResult() {int i = 0;while (s[i] != '\0') {// 输入非法if (s[i] 'z') return 0;i++;} s_len = i; if (s_len < n) {// 无法拼接出满足条件的字符串return 0;} // 排序s，可以方便后面求解全排列时，进行树层去重qsort(s, i, sizeof(char), cmp); int used[MAX_SIZE] = {0};return dfs(-1, 0, used, 0);} int main() {scanf("%s", s);scanf("%d", &n); printf("%d\n", getResult()); return 0;}Wonderland
#include #include #include using namespace std;int main() {vector cost, days;int x;// 读取输入，将输入的数据存入days数组while (cin >> x) {days.push_back(x);}// 初始化cost数组，将days数组的前四个元素放入cost数组中for (int i = 0; i < 4; i++) {cost.push_back(days[0]);days.erase(days.begin());}int choose[] = {1, 3, 7, 30};// 不同的购买方案bool isPlay[366] = {false};// 标记游玩日期for (int x : days) {isPlay[x] = true;}int f[366];// 将f数组初始化为正无穷fill(f, f + 366, 1e9);f[0] = 0; // 初始条件for (int i = 1; i < 366; i++) {if (isPlay[i]) {// 当天是游玩日for (int j = 0; j < 4; j++) {// 考虑四种不同的购买方案f[i] = min(f[i], f[max(0, i - choose[j])] + cost[j]);}} else {f[i] = f[i - 1]; // 当天不是游玩日，花费与前一天相同}}// 输出最终结果cout << f[365] << endl;return 0;}伐木工
#include #include #include using namespace std;int main() {int n;cin >> n;vector f(n + 1, 0);for (int i = 1; i <= n; i++) {f[i] = i;for (int j = 1; j < i; j++) {f[i] = max(f[i], max(f[i - j] * j, (i - j) * j));}}vector res;int m = n;while (m >= 1) {if (f[m] == m) {res.push_back(m);break;}for (int k = m - 1; k > 1; k--) {if (k * (m - k) == f[m]) {res.push_back(k);res.push_back(m - k);m = 0;break;} else if (k * f[m - k] == f[m]) {res.push_back(k);m -= k;break;}}}sort(res.begin(), res.end());for (int i : res) {cout << i << " ";}return 0;}抢7游戏(dp)
#include int main() {int m;scanf("%d", &m); // dpA[i] 表示 A 叫 数字i 的方案数long long dpA[m + 2];// 初始化dpA[i]for (int i = 0; i < m + 2; i++) dpA[i] = 0;// 由于是A从m开始叫，因此A叫m的方案数为1dpA[m] = 1; // dpB[i] 表示 B叫 数字i 的方案数long long dpB[m + 2];// 初始化dpB[i]for (int i = 0; i = 7; i--) {// B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数dpB[i] = dpA[i + 1] + dpA[i + 2];// A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数dpA[i] = dpB[i + 1] + dpB[i + 2];} // 返回B叫7的方案数printf("%lld", dpB[7]); return 0;}寻找最优的路测线路
#include #include #include #define MAX_SIZE 400 int cmp(const void *a, const void *b) {return *((int *) b) - *((int *) a);} int main() {int r, c;scanf("%d %d", &r, &c); int matrix[r][c];for (int i = 0; i < r; i++) {for (int j = 0; j =0，因此这里可以初始化为0int dist[MAX_SIZE] = {0};// 起点0 到 终点0 路径的最小权值节点就是自身，即matrix[0][0]点的权重dist[0] = matrix[0][0]; // 优先队列记录路径（终点），并且路径中的最小权值节点的权值越大，优先级越高int pq[MAX_SIZE] = {0};int pq_size = 0; // 初始时将(0,0)入队pq[pq_size++] = 0; // 上下左右的方向偏移量int offsets[4][2] = {{-1, 0}, {1,0}, {0,-1}, {0,1}}; while (pq_size > 0) {// 取出优先队列中优先级最大的路径（终点）int u = pq[--pq_size]; // 将一维化坐标u，解析为二维坐标(x,y)int x = u / c;int y = u % c; // 已找到dist[r-1][c-1]最优解，则可以提前结束if (x == r - 1 && y == c - 1) break; // 向上下左右四个方向探索for (int i = 0; i < 4; i++) {// 新位置坐标int newX = x + offsets[i][0];int newY = y + offsets[i][1]; // 新位置越界则无法访问if (newX = r || newY = c) continue; // 新位置的一维化坐标int v = newX * c + newY;// 当前路径（终点u）的最小权值节点的权值为dist[u]// 要加入当前路径的新位置的点的权值 matrix[newX][newY]// 那么形成的新路径的最小权值节点的权值即为 w = min(dist[u], matrix[newX][newY])int w = (int) fmin(dist[u], matrix[newX][newY]); // 形成的新路径的终点为 v（即新位置一维化坐标）// 而dist[v]记录的是起点到点v的所有路径中“最大的”最小权值节点if (dist[v] < w) {// 因此如果dist[v] < w的话，则更新dist[v]dist[v] = w;// 并将新路径加入优先队列，参与下一轮比较pq[pq_size++] = v;// 优先级排序，由于43行是pq尾删，即尾部优先级最大，因此这里升序qsort(pq, pq_size, sizeof(int), cmp);}}} // 返回起点（0，0）到终点(r-1, c-1)的所有路径中"最大的"最小权值节点的权值printf("%d\n", dist[r * c - 1]); return 0;}篮球游戏
#include #include #define MAX_SIZE 200 typedef struct ListNode {int ele;struct ListNode *prev;struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, int ele) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));node->ele = ele;node->prev = NULL;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;node->prev = link->tail;link->tail = node;} link->size++;} int removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;link->head->prev = NULL;} link->size--; int res = removed->ele; free(removed); return res;} int removeLast_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->tail; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->tail = link->tail->prev;link->tail->next = NULL;} link->size--; int res = removed->ele; free(removed); return res;} int main() {int inputs[MAX_SIZE];int inputs_size = 0; while (scanf("%d", &inputs[inputs_size++])) {if (getchar() != ',') break;} int outputs[MAX_SIZE];int outputs_size = 0; while (scanf("%d", &outputs[outputs_size++])) {if (getchar() != ',') break;} // 利用队列结构模拟圆桶LinkedList *queue = new_LinkedList();// outputs[index]是要被取出的篮球的编号int index = 0; // 记录题解char res[MAX_SIZE] = {'\0'};int res_size = 0; for (int i = 0; i size > 0) {// 圆桶左边的篮球的编号int left = queue->head->ele;// 圆桶右边的篮球的编号int right = queue->tail->ele; if (left == outputs[index]) {// 优先比较圆桶左边的篮球是不是当前要取出的篮球，优先左边的原因是：当桶只有一个篮球的情况下，必须从左边取出res[res_size++] = 'L';removeFirst_LinkedList(queue);index++;} else if (right == outputs[index]) {// 比较圆桶右边的篮球是不是当前要取出的篮球res[res_size++] = 'R';removeLast_LinkedList(queue);index++;} else {// 如果圆桶左右两边都不是要取出的球，则本轮取出流程结束break;}}} // 最终如果圆桶空了，则说明所有球都取出了，否则按照给定要求无法取出所有球if (queue->size != 0) {puts("NO");} else {puts(res);} return 0;}矩阵匹配
#include #include using namespace std;int n, m, K; // 声明变量 n, m, K，分别表示行数、列数和第K大元素的数量vector<vector> myMap; // 声明二维向量 myMap，用于存储输入的数字// findMuniu 函数：实现匈牙利匹配算法，用于在矩阵中找到一个增广路径bool findMuniu(int x, vector<vector>& mp, vector& chw, vector& match) {for (int j = 1; j <= m; j++) {if (mp[x][j] && chw[j]) {chw[j] = false;if (match[j] == 0 || findMuniu(match[j], mp, chw, match)) {match[j] = x;return true;}}}return false;}// check 函数：检查给定的数字 p 是否可以添加到匹配图中bool check(int p) {vector<vector> mp(n + 1, vector(m + 1, false)); // 声明二维向量 mp，用于存储匹配图for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {mp[i][j] = (myMap[i][j] <= p); // 构建匹配图}}int ans = 0;vector match(m + 1, 0); // 声明一维向量 match，用于存储匹配的数字for (int i = 1; i <= n; i++) {vector chw(m + 1, true); // 声明一维向量 chw，表示当前可用的数字if (findMuniu(i, mp, chw, match)) {ans++;}}return ans >= n - K + 1; // 返回匹配数是否大于等于 n - K + 1}// solve 函数：使用二分查找算法找到矩阵中可以选出 M!/N! 种组合数组中第 K 大的数字的最小值int solve(int mx) {int l = 1, r = mx;int ans = 0;while (l > n >> m >> K; // 输入 n, m, K 的值myMap.resize(n + 1, vector(m + 1, 0)); // 调整 myMap 的大小int mx = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j > myMap[i][j]; // 输入矩阵中的数字mx = max(mx, myMap[i][j]); // 计算矩阵中的最大值}}int result = solve(mx); // 调用 solve 函数cout << result << endl; // 输出结果return 0;}最小矩阵宽度
#include #include #include #define MAX_SIZE 1000 // 矩阵行数, 矩阵列数int n, m;// 矩阵int matrix[MAX_SIZE][MAX_SIZE]; // 目标数组长度int k;// cnts[num] 记录的是 目标数组中num元素的个数int cnts[MAX_SIZE] = {0}; int getResult() {// 未完成匹配的元素的个数int total = k; // 记录最小子矩阵的宽度int minLen = INT_MAX; // 当前子矩阵的左边界（列号）int l = 0;// 当前子矩阵的右边界（列号）int r = 0; // 如果右边界未越界，则可以继续尝试找最小子矩阵while (r < m) {// 将第r列所有元素纳入子矩阵for (int i = 0; i 0) {total--;}} // 纳入r列后，看看总的未匹配元素数量total还有几个，如果total为0，则说明当前子矩阵匹配到了所有目标数组元素while (total == 0) {// 若此时子矩阵宽度 r - l + 1 更小，则更新最小子矩阵宽度minLen = (int) fmin(minLen, r - l + 1); // 由于当前子矩阵已经匹配到所有目标数组元素，因此下一步应该将 l 右移，尝试更小宽度的子矩阵for (int i = 0; i < n; i++) {// l 右移，相当于当前子矩阵移除了第 l 列所有元素，被移除的元素num如果是目标数组元素，则对应的未匹配数量应该被恢复int num = matrix[i][l]; // 如果当前num不是目标数组元素，或者当前num是目标数组元素，但是属于超出部分（这两种情况必然cnts[num] = 0），则对应num元素的恢复，会影响到整体未匹配数量totalif (cnts[num]++ >= 0) {total++;}} // l右移，且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素l++;} // r右移r++;} if (minLen == INT_MAX) {return -1;} else {return minLen;}} int main() {scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &matrix[i][j]);}} scanf("%d", &k); for (int i = 0; i < k; i++) {int num;scanf("%d", &num);cnts[num]++;} printf("%d\n", getResult()); return 0;}启动多任务排序
#includeusing namespace std;// 用邻接表存储图vector g[26];// 存储每个节点的入度int d[26];// 记录节点是否被访问过bool vis[26];int main() {string s;// 读取输入，构建图的邻接表while (cin >> s) {int a = s[0] - 'A', b = s[3] - 'A';d[a]++;g[b].push_back(a);vis[a] = vis[b] = true;}// 使用队列进行拓扑排序queue q;// 存储拓扑排序的结果vector res, v;// 初始化队列，将入度为0且存在的节点加入队列和结果集合中for (int i = 0; i < 26; i++) {if (!d[i] && vis[i]) {q.push(i);v.push_back(i);}}// 开始拓扑排序while (q.size()) {int sz = q.size();// 将当前层次的节点按字典序排序sort(v.begin(), v.end());// 将排序后的节点加入结果集合for (int &x : v) {res.push_back(x);}v.clear();// 处理当前层次的节点while (sz--) {int t = q.front();q.pop();// 遍历当前节点的邻接表for (int &x : g[t]) {d[x]--;// 如果某个相邻节点入度为0，加入队列和结果集合中if (!d[x]) {q.push(x);v.push_back(x);}}}}// 输出拓扑排序的结果for (int &x : res) {char ch = x + 'A';cout << ch << " ";}return 0;}贪心歌手
#include #include int cmp(const void *a, const void *b) {return *((int *) b) - *((int *) a);} int main() {int t, n;scanf("%d %d", &t, &n); // roadCost是A~B城市必需的路程时间int roadCost = 0;for (int i = 0; i < n + 1; i++) {int cost;scanf("%d", &cost);roadCost += cost;} // remain是刨去必要的路程时间后，剩余可以用于赚钱的时间int remain = t - roadCost; // 如果没有剩余时间可以用，则赚不到钱if (remain <= 0) {puts("0");return 0;} // 优先队列（降序数组）记录赚到的钱, 即数组尾巴是某天赚的最少的钱int pq[remain + 1];int pq_size = 0; for (int i = 0; i 0) {// 只有remain天可以赚钱，超出的时间不能赚钱，因此需要比较超出的时间赚的钱m，和前面时间中赚的最少的钱pq.peekif (pq_size >= remain) {// pq.peek只可能是某座城市停留的最后一天的赚的钱，因为每座城市都是停留的最后一天赚的钱最少if (m > pq[pq_size - 1]) {// 如果当前城市当天赚的钱m，比前面天里面赚的最少的pq.peek多，那么就赚pq.peek钱的那天时间节约下来，给当天用pq_size--;} else {// 如果当前城市当天赚的钱m，比前面天里面赚的最少的pq.peek还少，则当前城市继续待下去赚的钱只会更少，因此没必要呆下去了break;}} // 如果所有城市停留时间没有超出remain天，或者当天是超出的时间，但是比前面赚的最少的一天的赚的更多，则赚m更优pq[pq_size++] = m;qsort(pq, pq_size, sizeof(int), cmp); //每天收入减少dm -= d;}} int ans = 0;for (int i = 0; i < pq_size; i++) {ans += pq[i];} printf("%d\n", ans); return 0;}反射计数
#include #include using namespace std;int main() {int m, n, y, x, sy, sx, t;cin >> m >> n >> y >> x >> sy >> sx >> t;vector g(n);for (int i = 0; i > g[i];}int ans = 0;while (t >= 0) {if (g[x][y] == '1') {ans += 1;}int x1 = x + sx;int y1 = y + sy;if (x1 = n) {sx = -sx;}if (y1 = m) {sy = -sy;}x += sx;y += sy;t -= 1;}cout << ans << endl;return 0;}模拟目录管理功能
#include #include #include /** 树节点 **/typedef struct TreeNode {char curDicName[11]; // 当前目录名struct TreeNode *father; // 父目录（只能有一个）struct LinkedList *children; // 子目录（可以有多个，这里使用链表记录）} TreeNode; /** 链表节点 **/typedef struct ListNode {TreeNode *ele; // 链表用于记录多个子目录，因此链表节点的内容就是树节点struct ListNode *next;} ListNode; /** 链表 **/typedef struct LinkedList {ListNode *head;ListNode *tail;int size;} LinkedList; /** 树 **/typedef struct Tree {TreeNode *root; // 记录树根节点TreeNode *cur; // 记录当前目录对应的节点} Tree; /**链表结构方法**/// 初始化链表LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList)); link->head = NULL;link->tail = NULL;link->size = 0; return link;} // 尾插链表void addLast_LinkedList(LinkedList *link, TreeNode *ele) {ListNode *listNode = (ListNode *) malloc(sizeof(ListNode));listNode->ele = ele;listNode->next = NULL; if(link->size == 0) {link->head = listNode;link->tail = listNode;} else {link->tail->next = listNode;link->tail = listNode;} link->size++;} // 遍历链表，获取指定节点的内容TreeNode *get_LinkedList(LinkedList *link, char *dicName) {ListNode *curListNode = link->head;while (curListNode != NULL) {if (strcmp(curListNode->ele->curDicName, dicName) == 0) {return curListNode->ele;}curListNode = curListNode->next;}return NULL;} /**树形结构方法**/TreeNode *new_TreeNode(char *curDicName, TreeNode *father) {TreeNode *treeNode = (TreeNode *) calloc(1, sizeof(TreeNode)); strcpy(treeNode->curDicName, curDicName);treeNode->father = father;treeNode->children = new_LinkedList(); return treeNode;} // 初始化树Tree *new_Tree() {Tree *tree = (Tree *) malloc(sizeof(Tree)); // 由于目录名结尾都要带'/'，因此可以认为根目录是空串，后期拼接时再尾部追加'/'// 另外根目录没有父目录，因此父目录设置为NULLtree->root = new_TreeNode("", NULL);// 初始时，当前目录就是根目录tree->cur = tree->root; return tree;} // 创建指定目录void mkdir_Tree(Tree *tree, char *dicName) {TreeNode *p = get_LinkedList(tree->cur->children, dicName); // mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作if (p != NULL) {return;} TreeNode *treeNode = new_TreeNode(dicName, tree->cur);addLast_LinkedList(tree->cur->children, treeNode);} // 跳转到指定目录void cd_Tree(Tree *tree, char *dicName) {if (strcmp(dicName, "..") == 0) {// cd .. 为返回上级目录，如果目录不存在则不执行任何操作if (tree->cur->father != NULL) {// cur 变更指向上级目录tree->cur = tree->cur->father;}} else {TreeNode *p = get_LinkedList(tree->cur->children, dicName); // cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作if (p != NULL) {// cur 变更指向下级目录tree->cur = p;}}} // 输出当前路径字符串char *pwd_Tree(Tree *tree) {char *tmp = (char *) calloc(10000, sizeof(char));char *res = (char *) calloc(10000, sizeof(char)); // 倒序路径，即不停向上找父目录TreeNode *cur = tree->cur;while (cur != NULL) {strcpy(tmp, res); strcpy(res, cur->curDicName);strcat(res, "/");strcat(res, tmp);cur = cur->father;} return res;} int main() {// 初始化目录结构Tree *tree = new_Tree(); // 记录最后一条命令的输出char lastCommandOutPut[10000]; char s[50];while (gets(s)) {// 本地测试解开此行注释 if(strlen(s) == 0) break; char *cmd_key = strtok(s, " ");char *cmd_val = strtok(NULL, " "); if (strcmp(cmd_key, "pwd") == 0) {// pwd 命令不需要参数if (cmd_val != NULL) {continue;}strcpy(lastCommandOutPut, pwd_Tree(tree));} else if (strcmp(cmd_key, "mkdir") == 0 || strcmp(cmd_key, "cd") == 0) {// 约束：mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abcif (cmd_val == NULL) continue; char *p = strtok(NULL, " ");if (p != NULL) continue; if(!(strcmp(cmd_key, "cd") == 0 && strcmp(cmd_val, "..") == 0)) {unsigned long long len = strlen(cmd_val); // 目录名约束校验// 约束：目录名称仅支持小写字母// 约束：不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。// 关于嵌套路径和绝对路径，我简单理解就是cmd_val含有'/'字符，可以被小写字母判断涵盖住int i = 0;for (; i < len; i++) {char c = cmd_val[i]; if (c 'z') {break;}} if(i != len) {continue;}} if(strcmp(cmd_key, "mkdir") == 0) {mkdir_Tree(tree, cmd_val);// 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut));} else {cd_Tree(tree, cmd_val);// 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut));}}} puts(lastCommandOutPut); return 0;}特殊的加密算法
#include #define MAX_SIZE 201 // 明文数字个数int n;// 明文int datas[MAX_SIZE]; // 密码本矩阵大小int m;// 密码本int secrets[MAX_SIZE][MAX_SIZE]; // 记录密码本中元素值等于“明文第一个数字”的所有元素的位置int starts[MAX_SIZE] = {0};int starts_size = 0; // 上，左，右，下偏移量，注意这里的顺序是有影响的，即下一步偏移后产生的密文的字符序必然是：上 < 左 < 右 < 下int offsets[4][2] = {{-1, 0}, {0,-1}, {0,1}, {1,0}}; /*! * * @param x 当前位置横坐标 * @param y 当前位置纵坐标 * @param index datas[index]是将要匹配的明文数字 * @return 是否找到符合要求的路径 */int dfs(int x, int y, int index, int path[], int *path_size, int used[][MAX_SIZE]) {// 已找到明文最后一个数字，则找到符合要求的路径if (index == n) {return 1;} // 否则，进行上、左、右、下四个方向偏移，注意这里的顺序是有影响的，即下一步偏移后产生的密文的字符序必然是：上 < 左 < 右 < 下for (int i = 0; i < 4; i++) {// 新位置int newX = x + offsets[i][0];int newY = y + offsets[i][1]; // 新位置越界，或者新位置已使用，或者新位置不是目标值，则跳过if (newX = m || newY = m || used[newX][newY] ||secrets[newX][newY] != datas[index]) {continue;} // 递归进入新位置path[(*path_size)++] = newX * m + newY;used[newX][newY] = 1; // 如果当前分支可以找到符合要求的路径，则返回if (dfs(newX, newY, index + 1, path, path_size, used)) {return 1;} // 否则，回溯used[newX][newY] = 0;(*path_size)--;} return 0;} void getResult() {for (int i = 0; i < starts_size; i++) {// 出发位置int x = starts[i] / m;int y = starts[i] % m; // used[i][j]用于记录密码本(i,j)元素是否已使用int used[MAX_SIZE][MAX_SIZE] = {0};// 出发点位置元素已使用used[x][y] = 1;// 记录结果路径各节点位置int path[MAX_SIZE] = {0};int path_size = 0;// 出发点位置记录path[path_size++] = starts[i]; // 开始深搜if (dfs(x, y, 1, path, &path_size, used)) {// 找到符合要求的路径，则打印for (int j = 0; j < path_size; j++) {int pos = path[j];printf("%d %d", pos / m, pos % m); if (j < path_size - 1) {printf(" ");}} return;}} // 找不到符合要求的路径，则打印errorputs("error");} int main() {scanf("%d", &n); for (int i = 0; i < n; i++) {scanf("%d", &datas[i]);}scanf("%d", &m); for (int i = 0; i < m; i++) {for (int j = 0; j < m; j++) {scanf("%d", &secrets[i][j]); // 如果密码本(i,j)位置元素指等于明文第一个数字值，则记录(i,j)作为一个出发位置if (secrets[i][j] == datas[0]) {starts[starts_size++] = i * m + j;}}} getResult(); return 0;}田忌赛马
#include #define MAX_SIZE 10 int a[MAX_SIZE];int a_size = 0; int b[MAX_SIZE];int b_size = 0; int maxBiggerCount = 0;int ans = 0; void dfs(int level, int used[], int biggerCount) {if (level >= a_size) {if (biggerCount > maxBiggerCount) {maxBiggerCount = biggerCount;ans = 1;} else if (biggerCount == maxBiggerCount) {ans += 1;} return;} for (int i = 0; i b[level]的位置的数量, 此时a[level] == a[i]dfs(level + 1, used, biggerCount + (a[i] > b[level] ? 1 : 0));used[i] = 0;}} int main() {while (scanf("%d", &a[a_size++])) {if (getchar() != ' ') break;} while (scanf("%d", &b[b_size++])) {if (getchar() != ' ') break;} int used[MAX_SIZE] = {0}; // 求解a的全排列dfs(0, used, 0); printf("%d\n", ans); return 0;}最长子字符串的长度(二）(5OJ)
#include #include #include #include #define MAX_SIZE 500000 char s[MAX_SIZE]; typedef struct ListNode {int ele;struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, int ele) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));node->ele = ele;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} int removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; int res = removed->ele; free(removed); return res;} int getResult() {int status = 0b000; // map[i] 用于记录 状态i 出现的过的所有位置LinkedList *map[8];for (int i = 0; i < 8; i++) {map[i] = new_LinkedList();} addLast_LinkedList(map[0], -1); int maxLen = 0; int n = (int) strlen(s); for (int i = 0; i =s.length()，此时i需要对s.length()求余，避免后面越界char c = s[i % n]; if (c == 'l') {status ^= 0b100;} else if (c == 'o') {status ^= 0b010;} else if (c == 'x') {status ^= 0b001;} if (i size > 0) {// status状态最早出现的位置int earliest = map[status]->head->ele; // i 是当前位置，和 earliest 位置的状态相同if (i - earliest > n) {// 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliestremoveFirst_LinkedList(map[status]);} else {// 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度maxLen = (int) fmax(maxLen, i - earliest);break;}}} return maxLen;} int main() {gets(s); printf("%d\n", getResult()); return 0;}考古学家(py)
# 输入获取n = int(input())arr = input().split()# 全局变量path = []used = [False] * ncache = set()# 全排列求解def dfs():if len(path) == n:cache.add("".join(path))return for i in range(n):if used[i]:continue # 树层去重if i > 0 and arr[i] == arr[i-1] and not used[i-1]:continue path.append(arr[i])used[i] = Truedfs()used[i] = Falsepath.pop()# 算法入口def getResult():# 排序是为了让相同元素相邻，方便后面树层去重arr.sort()dfs() # 输出石碑文字的组合（按照升序排列）for v in sorted(list(cache)):print(v)# 算法调用getResult()最大社交距离
#include #define MAX_N 10000using namespace std;int N,res;bool rec[505];int cur;int main(){scanf("%d",&N);while(getchar() != '[');getchar();getchar();rec[0] = 1;while (scanf("%d",&cur) == 1){// printf("cur:%d\n",cur);if(cur < 0){cur = -cur;rec[cur] = 0;}else if(cur == 1){int prv = 0;int ct = 0;int curmax = -1;for(int i = 1; i < N; i++){if(rec[i]){if(curmax = 1){curmax = (ct-1)/2;res = (prv+i)/2;}prv = i;ct = 0;}else ct++;}if(curmax == -1 && ct == 0){res = -1;break;}if(ct != 0){if(ct-1 > curmax){res = N-1;}}rec[res] = 1;// //test res// printf("res:%d\n",res);}getchar();// //test rec[]// for(int i = 0; i < N; i++) printf("%d ",rec[i]);// putchar('\n');}// //test rec[]// for(int i = 0; i < N; i++) printf("%d ",rec[i]);// putchar('\n');printf("%d\n",res);return 0;}文本统计分析(py)
# 算法入口import redef fn(s):s = re.sub("\\[\"']", "", s)# 替换\"和\'为空串s = re.sub("\".*?\"", "a", s)# 将成对双引号及其中内容替换为空串s = re.sub("'.*?'", "a", s)# 将成对单引号及其中内容替换为空串s = re.sub("-.+", "", s)# 将-往后的注释替换为空串s = re.sub("\\s+", "", s)# 将空白字符替换为空串s = re.sub(";+", ";", s)# 将连续分号替换为单个分号return sdef getResult(lines):s = "".join(map(fn, lines)) # 题目描述说：文本以”;”分隔，最后一条可以没有”;”# 为了避免复杂处理，这里无论最后一条文本有没有分号，都加一个s += ";" # 下面处理主要是为了处理跨行文本"""比如aaaa;;aaaa比如;aaaa;aaaa"""s = re.sub(";+", ";", s)s = re.sub("^;", "", s) # 记录文本条数count = 0 for c in s:if c == ';':count += 1# 此时一行有几个分号，就代表几条文本 return count# 输入获取lines = [] while True:line = input() if line != "":lines.append(line)else:print(getResult(lines))break信道分配
#include #define MAX_SIZE 20 int getResult(int R, int N[], int D);int binary_sub(int minuend[], int subtrahend[], int size);int calc_bin(const int bin[], int bin_size); int main() {int R;scanf("%d", &R); int N[MAX_SIZE] = {0};for(int i=0; i 0) {subtrahend[subtrahend_size++] = D % 2;D /= 2;} // count记录N能承载几个Dint count = 0; // N中高阶信道的单个信道就能满足D，因此这些高阶信道有几个，即能承载几个Dfor(int i = R; i >= subtrahend_size; i--) {// R ~ subtrahend.length 阶的单个信道就能承载一个D，因此这些信道有几个，就能承载几个Dcount += N[i];} // 0 ~ subtrahend.length - 1 阶的单个信道无法承载一个D，因此这些阶需要组合起来才能承载一个Dint minuend[subtrahend_size];for(int i=0; i= 0; i--) {if(minuend[i] >= subtrahend[i]) {// 如果对应位的信道数足够，则直接相减minuend[i] -= subtrahend[i];} else {// 如果对应位的信道数不足，此时有两种策略，一是向低位借，一是向高位借// 具体向哪里借，需要看 minuend 的 [0,i] 低位部分是否能够承载 subtrahend[0, i] 低位部分if(calc_bin(minuend, i+1) < calc_bin(subtrahend, i+1)) {// 如果minuend 的 [0,i]不能承载，则向高位借，即从j=i+1位开始借int j = i + 1;while (j 0) {// 如果高位 j 有信道可借，则借minuend[j] -= 1;return 1;} else {// 否则继续向更高位探索j += 1;}}// 如果所有高位都没有富余信道数，则说明减法结果为负数return 0;} else {// 如果minuend 的 [0,i]可以承载，则向低位借(向低位借，可以避免浪费)// 此时minuend[i]为负数，表示欠债minuend[i] -= subtrahend[i];// 将当前阶位的欠债，转移到前面的低阶位上，注意转移时，欠债x2minuend[i-1] += minuend[i] << 1;// 转移后，当前阶位的欠债变为0minuend[i] = 0;}}} return 1;} int calc_bin(const int bin[], int bin_size) {int ans = 0;for(int i=0; i<bin_size; i++) {ans += bin[i] * (1 << i);}return ans;}欢乐的周末
#include #include /** 并查集定义 **/typedef struct {int *fa;int count;} UFS; UFS *new_UFS(int n) {UFS *ufs = (UFS *) malloc(sizeof(UFS)); ufs->fa = (int *) malloc(sizeof(int) * n);for (int i = 0; i fa[i] = i;} ufs->count = n; return ufs;} int find_UFS(UFS *ufs, int x) {if (x != ufs->fa[x]) {ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);return ufs->fa[x];}return x;} void union_UFS(UFS *ufs, int x, int y) {int x_fa = find_UFS(ufs, x);int y_fa = find_UFS(ufs, y); if (x_fa != y_fa) {ufs->fa[y_fa] = x_fa;ufs->count--;}} int main() {// 长度m表示行数, 宽度n表示列数int m, n;scanf("%d %d", &m, &n); int matrix[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &matrix[i][j]);}} UFS *ufs = new_UFS(n * m); // 记录小华，小为的位置int huawei[2];int huawei_size = 0; // 记录餐厅的位置int restaurants[m * n];int restaurants_size = 0; // 上下左右四个方向偏移量int offsets[4][2] = {{-1, 0}, {1,0}, {0,-1}, {0,1}}; for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(matrix[i][j] == 1) continue; // 二维坐标(i, j) 转为 一维坐标posint pos = i * n + j; switch (matrix[i][j]) {case 2:// 收集小华，小为的位置huawei[huawei_size++] = pos;break;case 3:// 收集餐厅的位置restaurants[restaurants_size++] = pos;break;} for (int k = 0; k = 0 && newI = 0 && newJ < n && matrix[newI][newJ] != 1) {// 如果(i,j)和（newI,newJ）位置都是非1，则合并union_UFS(ufs, pos, newI * n + newJ);}}}} // 小华所在连通分量的根int hua_fa = find_UFS(ufs, huawei[0]);// 小为所在连通分量的根int wei_fa = find_UFS(ufs, huawei[1]); if (hua_fa != wei_fa) {// 如果小华和小为的不属于同一个连通分量，则二人无法去往相同餐厅puts("0");} else {// 找出和小华、小为在同一个连通分量里面的餐厅int ans = 0;for (int i = 0; i < restaurants_size; i++) {if (find_UFS(ufs, restaurants[i]) == hua_fa) {ans++;}}printf("%d\n", ans);} return 0;}二叉树的广度优先遍历
#include #include #include /** 链表定义 **/typedef struct ListNode {char post[27];char mid[27];struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, char *post, char *mid) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));strcpy(node->post, post);strcpy(node->mid, mid);node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} ListNode *removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; return removed;} // res记录题解char res[27];int res_size = 0; /*! * 字符串截取（左闭右开） * @param s 字符串 * @param start 起始位置（包含） * @param end 结束位置（不包含） * @return 指定区间的子串 */char *subString(char *s, int start, int end) {int len = end - start; char *tmp = (char *) calloc(len + 1, sizeof(char));strncat(tmp, s + start, len); return tmp;} /*! * 本方法用于从后序遍历、中序遍历序列中分离出：根，以及其左、右子树的后序、中序遍历序列 * @param post 后序遍历结果 * @param mid 中序遍历结果 * @param queue BFS的执行队列 */void devideLR(char *post, char *mid, LinkedList *queue) {// 后序遍历的最后一个元素就是根char rootEle = post[strlen(post) - 1];// 将根加入题解res[res_size++] = rootEle; // 在中序遍历中找到根的位置rootIdx，那么该位置左边就是左子树，右边就是右子树int rootIdx = strchr(mid, rootEle) - mid; // 左子树长度，左子树是中序遍历的0~rootIdx-1范围，长度为rootIdx// 如果存在左子树，即左子树长度大于0if (rootIdx > 0) {// 则从后序遍历中，截取出左子树的后序遍历char* leftPost = subString(post, 0, rootIdx);// 从中序遍历中，截取出左子树的中序遍历char* leftMid = subString(mid, 0, rootIdx);// 将左子树的后、中遍历序列加入执行队列addLast_LinkedList(queue, leftPost, leftMid);} // 如果存在右子树，即右子树长度大于0if (strlen(post) - 1 - rootIdx > 0) {// 则从后序遍历中，截取出右子树的后序遍历char* rightPost = subString(post, rootIdx, strlen(post) - 1);// 从中序遍历中，截取出右子树的中序遍历char* rightMid = subString(mid, rootIdx + 1, strlen(mid));// 将右子树的后、中遍历序列加入执行队列addLast_LinkedList(queue, rightPost, rightMid);}} int main() {char post[27];char mid[27]; scanf("%s %s", post, mid); // 广度优先搜索的执行队列，先加入左子树，再加入右子树LinkedList *queue = new_LinkedList(); // 层序遍历出来的元素存放在res中devideLR(post, mid, queue); while (queue->size > 0) {ListNode* node = removeFirst_LinkedList(queue);devideLR(node->post, node->mid, queue);} puts(res); return 0;} 图像物体的边界
#includeusing namespace std;const int N = 5010;int a[N][N];// 存储地图信息，表示地图中每个位置是否可以到达int n, m;// 地图的行数和列数int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};// 用于遍历相邻位置的行偏移int dy[8] = {-1, 1, 0, 0, -1, 1, 1, -1};// 用于遍历相邻位置的列偏移int visited[N][N];// 记录每个位置是否已经被访问过// 深度优先搜索，用于遍历地图中的连通块void dfs(int x, int y) {// 边界条件判断if (x n || y m) return;if (a[x][y] == 0) return;// 如果当前位置不可到达，返回if (visited[x][y]) return;// 如果当前位置已经被访问过，返回visited[x][y] = 1;// 标记当前位置为已访问// 遍历当前位置的所有相邻位置for (int i = 0; i > n >> m;// 读取地图信息for (int i = 1; i <= n; i++) {for (int j = 1; j > mp[i][j];}}// 根据地图信息更新a数组，表示可到达的位置for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (mp[i][j] == 5) {// 如果当前位置为5，则更新其周围相邻位置可到达for (int k = 0; k < 8; k++) {int ni = i + dx[k];int nj = j + dy[k];if (mp[ni][nj] == 1) {a[ni][nj] = 1;}}}}}int cnt = 0;// 记录连通块的数量// 遍历地图中的每个位置for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 如果当前位置可到达且未被访问过，进行DFS遍历if (a[i][j] == 1 && visited[i][j] == 0) {cnt++;// 连通块数量加1dfs(i, j);// 对连通块进行DFS遍历}}}// 输出连通块的数量cout << cnt << endl;return 0;}找单词(5oj)
#includeusing namespace std;const int N=1010;char g[N][N];int n;string s;bool vis[N][N];int dx[4]={-1,1,0,0}, dy[4]={0,0,1,-1};bool dfs(int cnt, int x, int y, vector<pair>& path) {// 判断是否越界、已访问或者当前位置字符不匹配if (x = n || y = n || vis[x][y] || g[x][y] != s[cnt]) {return false;}// 如果已经找到字符串的最后一个字符，输出路径并返回 trueif (cnt == s.size() - 1) {int m = path.size();for (int i = 0; i < m; i++) {printf("%d,%d", path[i].first, path[i].second);if (i < m - 1) {printf(",");}}return true;}// 标记当前位置已访问vis[x][y] = true;// 遍历四个方向for (int i = 0; i < 4; i++) {int a = dx[i] + x;int b = dy[i] + y;// 记录路径path.push_back({a, b});// 递归调用 dfsif (dfs(cnt + 1, a, b, path)) {return true;}// 回溯，移除路径path.pop_back();}// 恢复当前位置未访问状态vis[x][y] = false;return false;}int main() {scanf("%d\n", &n);// 读取迷宫字符数组 gfor (int i = 0; i > t;for (int j = 0; j > s;// 在迷宫中寻找字符串 s 的路径for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (g[i][j] == s[0]) {memset(vis, 0, sizeof vis);vector<pair> path = {{i, j}};if (dfs(0, i, j, path)) {break;}}}}return 0;}找城市\
#includeusing namespace std;const int N = 1010;vector g[N];int n, num;vector res;bool vis[N];// 深度优先搜索，计算以 u 为根的子树节点数量int dfs(int u, int fa) {int cnt = 1;vis[u] = true;for (int& x : g[u]) {if (x == fa || vis[x]) continue;cnt += dfs(x, u);}return cnt;}// 枚举切除每个节点后的最大子树，更新最小的最大子树数量及对应节点void solve(int u) {memset(vis, 0, sizeof vis);vis[u] = true;// 当前节点被切割int cnt = 0;for (int i = 1; i <= n; i++) {if (vis[i]) continue;cnt = max(cnt, dfs(i, 0));}if (cnt < num) {res.clear();}if (cnt > n;for (int i = 1; i > a >> b;g[a].push_back(b);g[b].push_back(a);}num = 1e9;for (int i = 1; i <= n; i++) {// 枚举切除第 i 个节点的最大子树solve(i);}for (int& x : res) cout << x << " ";return 0;}可以组成网络的服务器
#include #include using namespace std;int n, m;vector<vector> g;vector<vector> st;vector dx = {-1, 1, 0, 0};vector dy = {0, 0, 1, -1};int cnt, res;void dfs(int i, int j) {// 计数器加1cnt++;// 将当前位置的标记为truest[i][j] = true;// 遍历四个方向for (int d = 0; d = 0 && x = 0 && y > n >> m;// 创建网格和标记矩阵g.resize(n, vector(m));st.resize(n, vector(m));// 读取网格的内容for (int i = 0; i < n; i++) {for (int j = 0; j > g[i][j];}}// 遍历网格，找到所有的单元格（除了边界以外的单元格），并对其进行深度优先遍历（DFS）for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (g[i][j] == 1 && !st[i][j]) {// 计算当前单元格的访问次数cnt = 0;// 对当前单元格进行深度优先遍历（DFS）dfs(i, j);// 更新最大访问次数res = max(res, cnt);}}}// 输出结果cout << res << endl;return 0;}快递员的烦恼
#include #include #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX_SIZE 11#define MAX_ID 1000 int n;int dist[MAX_SIZE][MAX_SIZE];int path[MAX_SIZE][MAX_SIZE]; int ans;/** * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 // * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j] * * @param pre 上一个点, 初始为0，表示从披萨店出发 * @param sum 当前全排列路径累计的路径权重 * @param used 全排列used数组，用于标记哪些点已使用过 * @param level 用于记录排列的长度 */void dfs(int pre, int sum, int used[], int level) {if (level == n) {// 此时pre是最后一个客户所在点，送完最后一个客户后，司机需要回到披萨店，因此最终累计路径权重为 sum + dist[pre][0]// 我们保留最小权重路径ans = MIN(ans, sum + dist[pre][0]);return;} for (int i = 1; i <= n; i++) {if (used[i]) continue; used[i] = 1;dfs(i, sum + dist[pre][i], used, level + 1);used[i] = 0;}} // floyd算法求解图中任意两点之间的最短路径void floyd() {for (int k = 0; k < n + 1; k++) {for (int i = 0; i < n + 1; i++) {for (int j = 0; j j的距离int newDist = dist[i][k] + dist[k][j];// 如果newDist是i->j的更短路径if (newDist j的最短距离dist[i][j] = newDist;// 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 kpath[i][j] = k;}}}}} int main() {int m;scanf("%d %d", &n, &m); for (int i = 0; i < n + 1; i++) {for (int j = 0; j < n + 1; j++) {// 初始时默认i,j不相连，即i,j之间距离无穷大if (i != j) {dist[i][j] = INT_MAX;}path[i][j] = -1;}} // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理int map[MAX_ID]; for (int i = 1; i <= n; i++) {int id, dis;scanf("%d %d", &id, &dis); // 离散化处理map[id] = i; // 投递站到客户之间的距离distancedist[0][i] = dis;dist[i][0] = dis;} for (int i = 1; i <= m; i++) {int id1, id2, dis;scanf("%d %d %d", &id1, &id2, &dis); int i1 = map[id1];int i2 = map[id2]; // 客户与客户之间的距离信息dist[i1][i2] = dis;dist[i2][i1] = dis;} // floyd算法调用floyd(); // ans记录经过所有点后回到出发点的最短距离ans = INT_MAX; // 全排列模拟经过所有点的路径int used[MAX_SIZE] = {0};dfs(0, 0, used, 0); printf("%d\n", ans);}查找一个有向网络的头节点和尾节点
#include #include #define MAX_SIZE 10000 /** 基于链表实现队列 **/typedef struct ListNode {int ele;struct ListNode *next;} ListNode; typedef struct LinkedList {int size;ListNode *head;ListNode *tail;} LinkedList; LinkedList *new_LinkedList() {LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));link->size = 0;link->head = NULL;link->tail = NULL;return link;} void addLast_LinkedList(LinkedList *link, int ele) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));node->ele = ele;node->next = NULL; if (link->size == 0) {link->head = node;link->tail = node;} else {link->tail->next = node;link->tail = node;} link->size++;} int removeFirst_LinkedList(LinkedList *link) {if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) {link->head = NULL;link->tail = NULL;} else {link->head = link->head->next;} link->size--; return removed->ele;} int cmp(const void *a, const void *b) {return *((int *) a) - *((int *) b);} int main() {int n;scanf("%d", &n); // 记录每个点的入度int inDegree[MAX_SIZE] = {0};// 记录每个点的后继点集合LinkedList *next[MAX_SIZE] = {NULL}; // 记录图中点LinkedList *points = new_LinkedList();int occurs[MAX_SIZE] = {0}; for (int i = 0; i size;// head记录图的头节点int head = 0; // 队列记录入度为0的点LinkedList *queue = new_LinkedList(); ListNode *cur = points->head;while (cur != NULL) {int p = cur->ele; // 题目描述中说图中只有一个首节点，首节点是入度为0的节点，因此如果某节点p没有入度，则为头节点if (inDegree[p] == 0) {head = p;addLast_LinkedList(queue, p);break;} cur = cur->next;} // tails记录所有尾节点int tails[MAX_SIZE];int tails_size = 0; // count记录已被剥去的点个数，如果图中存在环，则必然最终count size > 0) {// 剥离入度为0的点int fa = removeFirst_LinkedList(queue);count++; // 如果fa没有后继点，即fa没有出度，则fa是尾节点if (next[fa] == NULL) {tails[tails_size++] = fa;continue;} // 如果fa有后继点，则其所有后继点入度-1ListNode *cur = next[fa]->head;while (cur != NULL) {int ch = cur->ele; inDegree[ch] -= 1; // 如果ch点入度变为0，则加入队列if (inDegree[ch] == 0) {addLast_LinkedList(queue, ch);} cur = cur->next;}}if (count != total) {// 如果存在环，则必然count < totalprintf("-1");} else {// 如果不存在环，则打印头节点和尾节点printf("%d ", head); // 注意本题描述存在冲突（用例2输出的尾节点是从小到大排序的，而题目输出描述是要求尾节点从大到小排序），这里以用例为准qsort(tails, tails_size, sizeof(int), cmp); for (int i = 0; i < tails_size; i++) {printf("%d", tails[i]); if (i < tails_size - 1) {printf(" ");}}}return 0;}