飞行员兄弟
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 的矩阵，您可以改变任何一个位置
上把手的状态。
但是，这也会使得第 行和第
列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 ，表示所需的最小切换把手次数。
接下来 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
输入样例：
-+-----------+--
输出样例：
61 11 31 44 14 34 4
由于仅有 16 个位置，所以通过二进制枚举每个位置的翻转情况，来确定最佳翻转方案。
注意提前预处理 chang[x][y] 数组，表示修改 (x,y) 位置后引起的位置修改。
下面代码将 (x, y) 转换为 x * 4 + y 来处理。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 16;int change[N];int get(int x, int y) {return 4 * x + y;}int main(){int s = 0;for(int i = 0; i < 4; i++){char buf[5];scanf("%s", buf);for(int j = 0; j < 4; j++){if(buf[j] == '+') s += 1 << get(i, j);}}//cout << s << endl;for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++){int x = get(i, j);for(int k = 0; k < 4; k++){change[x] += (1 << get(i, k)) + (1 << get(k, j));}change[x] -= 1 << x;}}vector<pair<int,int>> ans, tmp;for(int st = 0; st < (1 << 16); st ++){int t = s;tmp.clear();for(int i = 0; i < 16; i++){if(st >> i & 1) {int x = i / 4, y = i % 4;tmp.push_back({x, y});t ^= change[i];}}if(t == 0 && (ans.empty() || ans.size() > tmp.size())) ans = tmp;}cout << ans.size() << "\n";for(auto &[x, y] : ans) {cout << x + 1 << " " << y + 1 << "\n";}}
占卜DIY
达达学会了使用扑克 DIY 占卜。
方法如下：
一副去掉大小王的扑克共 张，打乱后均分为
堆，编号
，每堆
张，其中第
堆称作“生命牌”，也就是说你有
条命。
这里边， 张
被称作死神。
初始状态下，所有的牌背面朝上扣下。
流程如下：
1.抽取生命牌中的最上面一张(第一张)。
2.把这张牌翻开，正面朝上，放到牌上的数字所对应编号的堆的最上边。(例如抽到 ，正面朝上放到第
堆牌最上面，又比如抽到
，放到第
堆牌最上边，注意是正面朝上放)
3.从刚放了牌的那一堆最底下(最后一张)抽取一张牌，重复第 步。（例如你上次抽了
，放到了第二堆顶部，现在抽第二堆最后一张发现是
，又放到第
堆顶部………）
4.在抽牌过程中如果抽到 ，则称死了一条命，就扔掉
再从第
步开始。
5.当发现四条命都死了以后，统计现在每堆牌上边正面朝上的牌的数目，只要同一数字的牌出现 张正面朝上的牌(比如
个
)，则称“开了一对”，当然
个
是不算的。
6.统计一共开了多少对，开了 对称作”极凶”，
对为“大凶”，
对为“凶”，
对为“小凶”，
对为“中庸”，
对“小吉”，
对为“吉”，
为“大吉”，
为“满堂开花，极吉”。
输入格式
一共输入 行数据，每行四个数字或字母，表示每堆牌的具体牌型(不区分花色只区分数字)，每堆输入的顺序为从上到下。
为了便于读入，用 代表
。
同行数字用空格隔开。
输出格式
输出一个整数，代表统计得到的开出的总对数。
输入样例：
8 5 A AK 5 3 29 6 0 63 4 3 43 4 4 55 6 7 68 7 7 79 9 8 89 0 0 0K J J JQ A Q KJ Q 2 2A K Q 2
输出样例：
9
按照题意模拟即可。
注意正面牌不可以再翻，也就是翻过的牌扔掉即可，不用放在最顶端。
数据量较小，可以使用 vector ,deque 。最佳的复杂度应该是list 。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 14;deque<int> a[N];unordered_map<char,int> mp;int cnt[N];int main(){for(int i = 2; i <= 9; i++) mp[char('0' + i)] = i;mp['0'] = 10;mp['A'] = 1; mp['J'] = 11; mp['Q'] = 12; mp['K'] = 13;rep(i,1,13) {char buf[3];rep(j,1,4) {scanf("%s", buf);int x = mp[buf[0]];a[i].push_back(x);}}while (a[13].size() > 0){int x = a[13].front(); a[13].pop_front();while(x != 13) {cnt[x] ++;if(a[x].size() == 0) break;int nx = a[x].back();a[x].pop_back();x = nx;}}int rs = 0;for(int i = 1; i <= 12; i++){if(cnt[i] == 4) rs ++;}cout << rs << endl;return 0;}
分形
分形，具有以非整数维形式充填空间的形态特征。
通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。
现在，定义“盒子分形”如下：
一级盒子分形：
X
二级盒子分形：
X XXX X
如果用 #card=math&code=B%28n%20-%201%29&id=YMtIj) 代表第
级盒子分形，那么第
级盒子分形即为：
B(n - 1) B(n - 1)B(n - 1)B(n - 1) B(n - 1)
你的任务是绘制一个 级的盒子分形。
输入格式
输入包含几个测试用例。
输入的每一行包含一个不大于 的正整数
，代表要输出的盒子分形的等级。
输入的最后一行为 ，代表输入结束。
输出格式
对于每个测试用例，使用 X 符号输出对应等级的盒子分形。
请注意 X 是一个大写字母。
每个测试用例后输出一个独立一行的短划线。
输入样例：
1234-1
输出样例
X-X XXX X-X X X XX XX X X XX XXX XX X X XX XX X X X-X X X X X X X XX X X XX X X X X X X XX X X XX XX X X XX X X X X X X XX X X XX X X X X X X XX X X XX XX X X XX XXX XX X X XX XX X X XX X X X X X X XX X X XX X X X X X X XX X X XX XX X X XX X X X X X X XX X X XX X X X X X X X-
n = 1 时边长为 1
n = 2 时边长为 3
可以推断出 n 阶边长为
然后以左上角的坐标代入 DFS 绘制即可。
注意字符数组截止字符 '\0' ，以及每组测试数据单独清空。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 900;char s[N][N];int n;void dfs(int x, int y, int len) {if(len == 1) {s[x][y] = 'X';return;}int sub = len / 3;dfs(x, y, sub);dfs(x, y + 2 * sub, sub);dfs(x + sub, y + sub, sub);dfs(x + 2 * sub, y, sub);dfs(x + 2 * sub, y + 2 * sub, sub);}int main(){while(cin >> n) {if(n == -1) break;int len = pow(3, n - 1);rep(i,1,len) {rep(j,1,len) s[i][j] = ' ';s[i][len+1] = '\0';}dfs(1, 1, len);rep(i,1,len) {printf("%s\n", s[i] + 1);}puts("-");}}
袭击
在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。
依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。
经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。
该系统由 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。
将军派出了 个特工进入据点之中，打算对能源站展开一次突袭。
不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。
作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。
他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。
你能帮他算出来这最短的距离是多少吗？
输入格式
输入中包含多组测试用例。
第一行输入整数 ，代表测试用例的数量。
对于每个测试用例，第一行输入整数 。
接下来 行，每行输入两个整数
和
，代表每个核电站的位置的
坐标。
在接下来 行，每行输入两个整数
和
，代表每名特工的位置的
坐标。
输出格式
每个测试用例，输出一个最短距离值，结果保留三位小数。
每个输出结果占一行。
数据范围,
输入样例：
240 00 11 01 12 22 33 23 340 00 00 00 00 00 00 00 0
输出样例：
1.4140.000
分治
详细题解请参考：AcWing 119. 袭击 - AcWing
这个题目数据很弱，还是有极端的例子可以卡掉这个做法。
比如一半同类点均匀分布在左侧，另外一半均匀分布在右侧。可以想到往深层次递归时，左右两侧的复杂度均是 #card=math&code=O%28n%5E2%29&id=b9WpY)。
所以该题讲解分治算法，仅做知识点学习参考。这种方法在随机数据下表现良好。（非恶意构造数据），就像快排的期望复杂度是 #card=math&code=O%28n%5Clog%20n%29&id=ljPBp)，但是最坏复杂度为
#card=math&code=O%28n%5E2%29&id=YAem7)。
另外，解决 K 维空间信息，可以使用 K-D Tree 来维护。
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const double INF = 1e15;const double eps = 1e-6;struct node{double x,y;bool type;bool operator <(const node b){return x < b.x;}}points[N],tmp[N];double inf;double dist(node a,node b){if(a.type == b.type) return inf;double dx = a.x - b.x,dy = a.y - b.y;return sqrt(dx * dx + dy * dy);}double dfs(int l,int r){if(l >= r) return INF;int mid = l + r >> 1;double mid_x = points[mid].x;double res = min(dfs(l,mid),dfs(mid+1,r));{int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r){if(points[i].y < points[j].y){tmp[++k] = points[i++];}else{tmp[++k] = points[j++];}}while(i <= mid)tmp[++k] = points[i++];while(j <= r)tmp[++k] = points[j++];for(int i=1,j=l;i<=k;i++,j++)points[j] = tmp[i];}int k = 0;for(int i=l;i<=r;i++){if(points[i].x >= mid_x - res && points[i].x <= mid_x + res){tmp[++k] = points[i];}}for(int i=1;i<=k;i++){for(int j=i-1;j>=1 && tmp[i].y - tmp[j].y < res;j--){res = min(res,dist(tmp[i],tmp[j]));}}inf = min(inf, res);return res;}int main(){int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf",&points[i].x,&points[i].y);points[i].type = 0;}for(int i=n+1;i<=2*n;i++){scanf("%lf%lf",&points[i].x,&points[i].y);points[i].type = 1;}n *= 2;inf = dist(points[1], points[n]);sort(points + 1,points + 1 + n);printf("%.3f\n",dfs(1,n));}return 0;}
防线
达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天……受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。
就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。
数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。
由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。
但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。
防线由很多防具组成，这些防具分成了 组。
我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。
也就是说，我们可以用三个整数 ，
和
来描述一组防具，即这一组防具布置在防线的
(
D%3EE#card=math&code=K%E2%88%88%20Z%EF%BC%8CS%20%2B%20KD%E2%89%A4E%EF%BC%8CS%20%2B%20%28K%20%2B%201%29D%3EE&id=Tc6vM))位置上。
黑化的怪兽达达设计的防线极其精良。
如果防线的某个位置有偶数个防具，那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况，因为 也是偶数)。
只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。
作为行动队的队长，lqr 要找到防线的破绽以策划下一步的行动。
但是，由于防具的数量太多，她实在是不能看出哪里有破绽。
作为 lqr 可以信任的学弟学妹们，你们要帮助她解决这个问题。
输入格式
输入文件的第一行是一个整数 ，表示有
组互相独立的测试数据。
每组数据的第一行是一个整数 。
之后 行，每行三个整数
，代表第
组防具的三个参数，数据用空格隔开。
输出格式
对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 “There’s no weakness.”(不包含引号) 。
否则在一行内输出两个空格分隔的整数 和
，表示在位置
有
个防具。当然
应该是一个奇数。
数据范围
防具总数不多于,
,
,
,
输入样例：
321 10 12 10 121 10 11 10 141 10 14 4 11 5 16 10 1
输出样例：
1 1There's no weakness.4 3
给定一个具体位置，很容易算出对于第 i 组防线，在这个位置之前放置了多少个防线。
由于题目给出了最多只有一个奇数点位置的条件，所以可以通过二分这个位置，在 #card=math&code=O%28n%29&id=HaORp) 的时间内判断这个位置之前是否存在奇数点即可。
此题难点在于单调性不容易发现。是一个非常有趣的题目。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 200010;int T, n;int s[N], e[N], d[N];bool check(int m) {ll rs = 0;rep(i,1,n) {int r = min(e[i], m);if(r < s[i]) continue;rs += (r - s[i]) / d[i] + 1;}return rs & 1;}int main(){scanf("%d", &T);while(T--){scanf("%d", &n);rep(i,1,n) {scanf("%d%d%d", &s[i], &e[i], &d[i]);}ll l = 0, r = INT_MAX;while(l < r) {int m = (l + r) / 2;if(check(m)) r = m;else l = m + 1;}int cnt = 0;rep(i,1,n) {if(l >= s[i] && l <= e[i] && (l - s[i]) % d[i] == 0) cnt ++;}if(cnt & 1)printf("%lld %d\n", l, cnt);elseputs("There's no weakness.");}}
赶牛入圈
农夫约翰希望为他的奶牛们建立一个畜栏。
这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含 单位的三叶草，来当做它们的下午茶。
畜栏的边缘必须与 轴平行。
约翰的土地里一共包含 单位的三叶草，每单位三叶草位于一个
的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的
坐标都为整数，范围在
到
以内。
多个单位的三叶草可能会位于同一个 的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。
只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。
请你帮约翰计算一下，能包含至少 单位面积三叶草的情况下，畜栏的最小边长是多少。
输入格式
第一行输入两个整数 和
。
接下来 行，每行输入两个整数
和
，代表三叶草所在的区域的
坐标。
同一行数据用空格隔开。
输出格式
输出一个整数，代表畜栏的最小边长。
数据范围,
输入样例：
3 41 22 14 15 2
输出样例：
4
蓄栏必须是正方形的。坐标范围 1~10000，但点数最多只有 500。
求最小边长的蓄栏，使得至少包含 C 单位面积三叶草。
可以想到，最终蓄栏的边上一定会有三叶草。而求解最小边长可以使用二分，当边长固定下来后，可以枚举蓄栏的右下角坐标，并且使用双指针来维护蓄栏的左上角即可。
蓄栏的坐标可以提前离散化，共 500 个点，所以最多会有 1000 个不同的数字。
复杂度是 #card=math&code=O%28n%5E2%5Clog%20%5Ctext%7BMAX%7D%29&id=koLAL)，n 为离散化之后的数量，MAX为坐标最大值。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 1010;int n, c;int s[N][N], x[N], y[N];vector<int> v;bool check(int m) {int u = 1, l = 1;for(int d = 1; d <= n; d ++){// 双指针调整，注意离散化数组 v 的下标访问要 -1while(v[d - 1] - v[u - 1] + 1 > m) u ++;l = 1;for(int r = 1; r <= n; r ++){while(v[r - 1] - v[l - 1] + 1 > m) l ++;if(s[d][r] - s[d][l - 1] - s[u - 1][r] + s[u - 1][l - 1] >= c){return true;}}}return false;}int main(){ios::sync_with_stdio(false); cin.tie(nullptr);cin >> c >> n;rep(i,1,n) {cin >> x[i] >> y[i];v.push_back(x[i]);v.push_back(y[i]);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());rep(i,1,n) {int a = lower_bound(v.begin(), v.end(), x[i]) - v.begin() + 1;int b = lower_bound(v.begin(), v.end(), y[i]) - v.begin() + 1;s[a][b] ++;}n = v.size();rep(i,1,n) rep(j,1,n) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];int l = 1, r = v.size();while(l < r) {int m = (l + r) / 2;if(check(m)) r = m;else l = m + 1;}cout << l << endl;return 0;}
糖果传递
有 个小朋友坐成一圈，每人有
个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 ，表示小朋友的个数。
接下来 行，每行一个整数
，表示第
个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数，表示最小代价。
数据范围,
,
数据保证一定有解。
输入样例：
41254
输出样例：
4
请参考「七夕祭」一题。
每个数字与平均值作差后，求前缀和。记前缀和数组的中位数是 mid，统计mid与前缀和数组中的每个数字的差的绝对值和，即为答案。
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 1000010;int n, a[N];ll s[N];int main(){ios::sync_with_stdio(false); cin.tie(nullptr);cin >> n;ll sum = 0;rep(i,1,n) {cin >> a[i];sum += a[i];}ll ave = sum / n;rep(i,1,n) {s[i] = s[i - 1] + a[i] - ave;}int mid = (n + 1) / 2;nth_element(s + 1, s + mid, s + n + 1);ll m = s[mid], rs = 0;rep(i,1,n) {rs += abs(s[i] - m);}cout << rs << endl;return 0;}
士兵
格格兰郡的 名士兵随机散落在全郡各地。
格格兰郡中的位置由一对 #card=math&code=%28x%2Cy%29&id=wUUvN) 整数坐标表示。
士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 或
坐标也将加
或减
）。
现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 坐标相同并且
坐标相邻。
请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。
需注意，两个或多个士兵不能占据同一个位置。
输入格式
第一行输入整数 ，代表士兵的数量。
接下来的 行，每行输入两个整数
和
，分别代表一个士兵所在位置的
坐标和
坐标，第
行即为第
个士兵的坐标
#card=math&code=%28x%5Bi%5D%2Cy%5Bi%5D%29&id=UpTsK)。
输出格式
输出一个整数，代表所有士兵的总移动次数的最小值。
数据范围,
输入样例：
51 22 21 33 -23 3
输出样例：
8
y 轴上的问题可以看做是「货仓选址」中位数问题。
x 轴上略有些不同。
首先对 x 轴排序，可以想到，第 i 个士兵最终会在第 i 个位置。
假设第 1 个士兵它的 x 的坐标为 a，那么第 i 个士兵将是 a + i - 1。
那么第 i 个士兵要走 %7C%20%3D%20%7C(x_i%20-%20i)%20-%20(a%20-%201)%7C#card=math&code=%7Cx_i-%28a%2Bi-1%29%7C%20%3D%20%7C%28x_i%20-%20i%29%20-%20%28a%20-%201%29%7C&id=xGr3g) 单位距离。
将 看做一个整体，问题又可转换为「货仓选址」。
时间复杂度 #card=math&code=O%28n%5Clog%20n%29&id=hL7zZ)
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;const int N = 10010;int n, x[N], y[N];int main(){ios::sync_with_stdio(false); cin.tie(nullptr);cin >> n;rep(i,1,n) {cin >> x[i] >> y[i];}sort(x + 1, x + 1 + n);sort(y + 1, y + 1 + n);rep(i,1,n) x[i] -= i;sort(x + 1, x + 1 + n);int rs = 0, m = (n + 1) / 2;rep(i,1,n) {rs += abs(y[i] - y[m]) + abs(x[i] - x[m]));}cout << rs << endl;}
数的进制转换
编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。
这里有 个不同数位
。
输入格式
第一行输入一个整数，代表接下来的行数。
接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。
输入进制和输出进制都在 到
的范围之内。
（在十进制下） (
仍然表示
)。
输出格式
对于每一组进制转换，程序的输出都由三行构成。
第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。
第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。
第三行为空白行。
同一行内数字用空格隔开。
输入样例：
862 2 abcdefghiz10 16 123456789012345678901234567890123456789016 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD235 23 333YMHOUE8JPLT7OX6K9FYCQ8A23 49 946B9AA02MI37E3D3MMJ4G7BL2F0549 61 1VbDkSIMJL3JjRgAdlUfcaWj61 5 dl9MDSWqwHjDnToKcsWE1S5 10 42104444441001414401221302402201233340311104212022133030
输出样例：
62 abcdefghiz2 1101110000010001011111001001011001111100100110001101001000110 123456789012345678901234567890123456789016 3A0C92075C0DBF3B8ACBC5F96CE3F0AD216 3A0C92075C0DBF3B8ACBC5F96CE3F0AD235 333YMHOUE8JPLT7OX6K9FYCQ8A35 333YMHOUE8JPLT7OX6K9FYCQ8A23 946B9AA02MI37E3D3MMJ4G7BL2F0523 946B9AA02MI37E3D3MMJ4G7BL2F0549 1VbDkSIMJL3JjRgAdlUfcaWj49 1VbDkSIMJL3JjRgAdlUfcaWj61 dl9MDSWqwHjDnToKcsWE1S61 dl9MDSWqwHjDnToKcsWE1S5 421044444410014144012213024022012333403111042120221330305 4210444444100141440122130240220123334031110421202213303010 1234567890123456789012345678901234567890
10以内的进制互转是容易，不论是 10 进制转换为 x 进制还是 x 进制转换为 10 进制。
该题需要从 a 进制转换为 b 进制数字，。
如果你首先把 a 转换为 10 进制，再转换为 b 进制，那么该题需要实现高精度，因为数字很大。
当然我们不想随随便便就写高精度。
设 a 进制数字为 ，b 进制数字为
。
问题集中到求解 ，
%5Cover%20b%5E%7Bi%7D%7D%20%5C%25%20b#card=math&code=bi%20%3D%20%7B%28a%7Bn-1%7Da_%7Bn-2%7D%5Ccdots%20a_0%29%5Cover%20b%5E%7Bi%7D%7D%20%5C%25%20b&id=XUjis)。
所以，可以按照高精度除以低精度的模版来求解 b 进制下的数字。
例如，将一个 long long 存储的数字 a = 123456789012345679 转成数组存储，你或许可以这么写：
ll a = 123456789012345679;vector<int> b;while(a) {b.push_back(a % 10);a /= 10;}
#include<bits/stdc++.h>using namespace std;#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)#define per(i,j,k) for(int i=int(j);i>=int(k);i--)typedef long long ll;int main(){ios::sync_with_stdio(false); cin.tie(nullptr);int T;cin >> T;while(T--){int A, B;string line;cin >> A >> B >> line;vector<int> a, b;for(auto c : line) {if(isdigit(c)) a.push_back(c - '0');else if(isupper(c)) a.push_back(c - 'A' + 10);else a.push_back(c - 'a' + 36);}reverse(a.begin(), a.end());// 核心while(a.size()) {int t = 0;// 做除法, 顺便求余数for(int i = a.size() - 1; i >= 0; i--) {a[i] += t * A;t = a[i] % B;a[i] /= B;}b.push_back(t);while(a.size() && a.back() == 0) a.pop_back();}reverse(b.begin(), b.end());cout << A << ' ' << line << "\n";line = "";for(auto c : b) {if(c <= 9) line += char('0' + c);else if(c <= 35) line += char('A' + c - 10);else line += char('a' + c - 36);}cout << B << ' ' << line << "\n\n";}}
耍杂技的牛
农民约翰的 头奶牛（编号为
）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 头奶牛中的每一头都有着自己的重量
以及自己的强壮程度
。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 ，表示奶牛数量。
接下来 行，每行输入两个整数，表示牛的重量和强壮程度，第
行表示第
头牛的重量
以及它的强壮程度
。
输出格式
输出一个整数，表示最大风险值的最小可能值。
数据范围,
,
输入样例：
310 32 53 3
输出样例：
2
对于两头牛 a 和 牛 b，对比 a 在 b 上面与 b 在 a 上面这两种情况的最大风险值：
%2C(sum%2Bw_a)-s_b)~%3F~%20%5Cmax((sum%20-%20s_b)%2C(sum%20%2B%20w_b)%20-%20s_a))%20%5C%5C%0A%5CDownarrow%5C%5C%0Amax(-s_a%2Cw_a-s_b)~%3F~max(-s_b%2Cw_b-s_a)%5C%5C%0A#card=math&code=%5Cmax%28%28sum%20-%20s_a%29%2C%28sum%2Bw_a%29-s_b%29~%3F~%20%5Cmax%28%28sum%20-%20s_b%29%2C%28sum%20%2B%20w_b%29%20-%20s_a%29%29%20%5C%5C%0A%5CDownarrow%5C%5C%0Amax%28-s_a%2Cw_a-s_b%29~%3F~max%28-s_b%2Cw_b-s_a%29%5C%5C%0A&id=GRCwM)
如果 a 应该在 b 上面，那么前式应当小于右式，最终化简为 。
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> PII;const int N = 5e4 + 5;PII a[N];int main(){int n;cin >> n;for(int i = 0; i < n; i ++ ){int x, y;scanf("%d %d", &x, &y);a[i].first = x + y;a[i].second = y;}sort(a, a + n);ll res = -1e18, sum = 0;for(int i = 0; i < n; i ++ ){sum -= a[i].second;res = max(res, sum);sum += a[i].first;}cout << res << endl;return 0;}
最大的和
给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 或更大的连续子阵列。
矩形的总和是该矩形中所有元素的总和。
在这个问题中，具有最大和的子矩形被称为最大子矩形。
例如，下列数组：
0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2
其最大子矩形为：
9 2-4 1-1 8
它拥有最大和 。
输入格式
输入中将包含一个 的整数数组。
第一行只输入一个整数 ，表示方形二维数组的大小。
从第二行开始，输入由空格和换行符隔开的 个整数，它们即为二维数组中的
个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。
数组中的数字会保持在 的范围内。
输出格式
输出一个整数，代表最大子矩形的总和。
数据范围
输入样例：
40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2
输出样例：
15
如果枚举子矩阵的左上角和右下角，复杂度将是#card=math&code=O%28n%5E4%29&id=bIsSg)。
假设固定了子矩阵的上边界和下边界，此时子矩阵可以压缩成一维，转换为对于一个一维数组求解连续子序列最大值。这个问题是个经典的DP入门题，可以在 #card=math&code=O%28n%29&id=YUv7c) 时间内解决。方法是对于每个右边界，去找最满意的左边界。
再算上一开始枚举的上下边界，总体复杂度是 #card=math&code=O%28n%5E3%29&id=ky2DS)
#include <bits/stdc++.h>using namespace std;const int N = 101;int a[N][N],b[N][N],n,d[N];int main(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j] = b[i-1][j] + a[i][j];int res = 0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){// i 作为上边界，j 为下边界, 一维数组值为 b[j][k] - b[i-1][k]memset(d,0,sizeof d);for(int k=1;k<=n;k++){d[k] = max(d[k-1] + b[j][k] - b[i-1][k],b[j][k] - b[i-1][k]);res = max(d[k],res);}}}cout<<res<<endl;return 0;}
任务
今天某公司有 个任务需要完成。
每个任务都有相应的难度级别和完成任务所需时间。
第 个任务的难度级别为
，完成任务所需时间为
分钟。
如果公司完成此任务，他们将获得（）美元收入。
该公司有 台机器，每台机器都有最长工作时间和级别。
如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。
如果任务难度级别超过机器的级别，则机器无法完成次任务。
每台机器一天内只能完成一项任务。
每个任务只能由一台机器完成。
请为他们设计一个任务分配方案，使得该公司能够最大化他们今天可以完成的任务数量。
如果有多种解决方案，他们希望选取赚取利润最高的那种。
输入格式
输入包含几个测试用例。
对于每个测试用例，第一行包含两个整数 和
，分别代表机器数量和任务数量。
接下来 行，每行包含两个整数
，分别代表机器最长工作时间和机器级别。
再接下来 行，每行包含两个整数
，分别代表完成任务所需时间和任务难度级别。
输出格式
对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。
数据范围,
,
输入样例：
1 2100 3100 2100 1
输出样例：
1 50004
每个任务所需时间 ，所需级别
，所获收益为
，而
最大值仅为 100，所以
的差距即便最大，收益差距也不如
相差 1 所带来的结果更大。
对于每个任务，按照 从大到小考虑，对于
相同的，按照
从大到小考虑。
维护一个多重集合，集合内存放着所有还没有使用的机器，这些机器的最长工作时长都大于等于当前枚举的任务。
然后对每个任务，在多重集中查找级别大于等于该任务的最小机器。如果找不到，则该任务无法完成。
#include <bits/std++.h>using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int N = 100000 + 5;int n,m;pair<int, int> a[N], b[N];int main() {while(cin >> n >> m){for (int i = 1; i <= n;i++)scanf("%d%d", &a[i].first, &a[i].second);for (int i = 1; i <= m;i++)scanf("%d%d", &b[i].first, &b[i].second);sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + m);multiset<int> st;ll res = 0, cnt = 0;for (int i = m, j = n; i >= 1;i--){while(j >= 1 && a[j].first >= b[i].first)st.insert(a[j--].second);auto it = st.lower_bound(b[i].second);if(it != st.end()){cnt++;res += 500 * b[i].first + 2 * b[i].second;st.erase(it);}}cout << cnt << ' ' << res << endl;}return 0;}
该解法以任务角度去匹配机器，如果反过来使用机器去匹配任务是不行的，无论从小到大还是从大到小去考虑机器，都无法保证每一步贪心选择的最优任务会使得全局最优。
若有收获，就点个赞吧
0 人点赞
