A. Potion-making
题意
告诉你需要配置药剂的浓度k%，药剂由水和药混合而成，让你找到药剂最小的剂量，满足浓度为k%，浓度计算方法：药的体积/药剂总体积。
分析
设药的体积为a，水的体积为b，则$\frac{1-k}{k} = \frac{b}{a}$，那么要求a+b最小，即求一下1-k和k的最大公约数g，答案就是$\frac{1-k}{g} + \frac{k}{g}$
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
int k;
cin >> k;
int a = k, b = 100-k;
int tt = __gcd(a,b);
a/= tt, b/=tt;
cout << a + b <<endl;
}
return 0;
}
B. Permutation Sort
题意
给你一个1-n的排列，有一个操作：将排列的某个连续区间内的数字调整次序，但是不能选择整个排列作为区间，问最少需要几次调整可以将一个排列变成升序的。
分析
有四种情况：
- 初始状态已经是升序：需要0次。
- 初始时1在最左端或者n在最右端，则需要1次调整即可变成升序。
-
初始时1在最右端并且n在最左端，发现无论如何都需要3多次才行。
- 剩下的情况都只要两次调整即可，因为最大值和最小值在内部。
分别判断即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int a[111];
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int f = 1;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] != i) f = 0;
}
if(f == 1) puts("0");
else if(a[1] == 1 || a[n] == n) puts("1");
else if(a[1] == n && a[n] == 1) puts("3");
else puts("2");
}
return 0;
}
C. Robot Collisions(思维+贪心+模拟)
题意
一个数轴上的某些点上有机器人，保证一个点上不会有多个机器人，每个机器人的速度都是1，给出机器人的初始方向L或R，坐标为0和m的地方是一堵墙，机器人碰到墙后立马掉头。两个机器人如果在整数坐标点相遇则两个机器人消失，问所有机器人消失的时间，如果不会消失则用-1代替。
分析
对于每对机器人（假设左边的机器人坐标为$x_1$，右边的为$x_2$）一共有四种情况：
（1）RL：左边的向右，右边的向左走，下同，则相遇时间为$\frac{x_2-x_1}{2}$
（2）RR：相遇时间为 $m-\frac{x_2+x_1}{2}$
（3）LL：相遇时间为 $\frac{x_2+x_1}{2}$
（4）LR：这种情况要分两类讨论，如果 $x_1$ 距离 0 的距离小于 $x_2$ 距离 m 的位置，则相遇时间为 $m-x_2+\frac{x_1+x_2}{2}$，否则为$m+\frac{x_1-x_2}{2}$
由于机器人的速度等于1，那么要求两个机器人在整数点相遇其实等价于要求相遇时间为整数，由上面四种情况可以发现：只有两个机器人所在坐标的奇偶性相同才可能相遇，自然而然地就可以想到将机器人分奇偶进行处理。
奇偶分组后，只要解决其中一组的相遇先后顺序，另外一组也是同理，故下面都是对奇偶性相同的一组机器人进行讨论。我们可以发现，对于一组机器人的方向序列，相邻的”RL”肯定都是最先相遇的，同时在最左边的”LL”肯定也先相遇，那么先处理完整个方向序列最左边的所有”LL”，并且将相邻的”RL”也碰撞掉后，剩下的只可能是”LRRRR…”或者”RRR….”。类似于”LL”，最右边的”RR”肯定也会最先相遇，所有可以从右往左将所有的”RRRR”处理掉，剩下的只可能是”LR”、”L”、 “R”，LR也可以相遇碰撞，剩下的单个就是永远不会碰撞的机器人。
上述的处理可以用一个栈来实现：每次放入一个机器人，与栈顶比较，如果栈顶和放入的机器人刚好可以构成”LL”或者”RL”，则将栈顶弹出，算出两个机器人的相遇时间，否则将机器人放入栈中，最后的情况就是”LRRRR…”或者”RRR….”，每次弹出两个机器人判断方向进行计算即可，相遇时间的公式在最上方已经给出。
另外需要注意的是题目所给的坐标不是有序的，需要先进行排序。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int ans[maxn];
struct node {
int id, x;
char dir;
const bool operator<(const node &t) const { return x < t.x; }
} in[maxn];
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
stack<node> sta1, sta2;//定义一个奇数栈和偶数栈
for (int i = 1; i <= n; i++) {
in[i].id = i;
scanf("%d", &in[i].x);
}
for (int i = 1; i <= n; i++) {
getchar();
scanf("%c", &in[i].dir);
}
sort(in + 1, in + 1 + n);//坐标排序
for (int i = 1; i <= n; i++) {
if (in[i].x & 1) {//当前机器人的坐标为奇数，压入奇数栈
if (sta1.empty())//如果栈为空则直接压入即可
sta1.push(in[i]);
else if (sta1.top().dir == 'L') {
if (in[i].dir == 'L') {//LL
ans[in[i].id] = ans[sta1.top().id] =
(sta1.top().x + in[i].x) / 2;
sta1.pop();
} else {//LR
sta1.push(in[i]);
}
} else {
if (in[i].dir == 'L') {//RL
ans[in[i].id] = ans[sta1.top().id] =
(in[i].x - sta1.top().x) / 2;
sta1.pop();
} else {//RR
sta1.push(in[i]);
}
}
} else {//偶数栈
if (sta2.empty())
sta2.push(in[i]);
else if (sta2.top().dir == 'L') {
if (in[i].dir == 'L') {
ans[in[i].id] = ans[sta2.top().id] =
(sta2.top().x + in[i].x) / 2;
sta2.pop();
} else {
sta2.push(in[i]);
}
} else {
if (in[i].dir == 'L') {
ans[in[i].id] = ans[sta2.top().id] =
(in[i].x - sta2.top().x) / 2;
sta2.pop();
} else {
sta2.push(in[i]);
}
}
}
}
//最后从右往左处理RR和LR的情况
while (sta1.size()) {
node xx = sta1.top();
sta1.pop();
if (sta1.empty()) {
ans[xx.id] = -1;
break;
}
node yy = sta1.top();
sta1.pop();
if (xx.dir == yy.dir)//RR
ans[xx.id] = ans[yy.id] = m - (xx.x + yy.x) / 2;
else {//LR
if (yy.x > m - xx.x) {
ans[xx.id] = ans[yy.id] = m + (yy.x - xx.x)/2;
} else {
ans[xx.id] = ans[yy.id] = m-xx.x + (xx.x + yy.x) / 2;
}
}
}
while (sta2.size()) {
node xx = sta2.top();
sta2.pop();
if (sta2.empty()) {
ans[xx.id] = -1;
break;
}
node yy = sta2.top();
sta2.pop();
if (xx.dir == yy.dir)
ans[xx.id] = ans[yy.id] = m - (xx.x + yy.x) / 2;
else {
if (yy.x > m - xx.x) {
ans[xx.id] = ans[yy.id] = m + (yy.x - xx.x) / 2;
} else {
ans[xx.id] = ans[yy.id] = m - xx.x + (xx.x + yy.x) / 2;
}
}
}
//puts("---------------");
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
puts("");
}
return 0;
}
D. Armchairs（DP）
题意
有n个座位，用1-n编号，用一个01序列表示，1表示初始有人坐着，0表示空座位。你有一个操作，可以让任意一个人去任意一个空座位，所需要消耗的时间为abs(i-j)，其中i表示这个人的座位编号，j表示他要去的座位编号。问你用最少的时间，使得初始时做了人的座椅全空，题目保证人的数量少于等于座椅数量的一半
分析
首先将0和1分别放在两个容器里，用 $dp[i][j]$ 表示已经处理了前 i 个1，且第 i 个1被分配到了第 j 个0的位置的最少花费。我们可以从第i-1个1的情况推出第i个1的情况：由于第i个1被分配到了第j个0的位置，那么第i-1个1肯定分配在第1到j-1个0的某个位置（稍微思考一下就能得出），于是$dp[i][j] = min(dp[i-1][k]) + abs(pos1[i]-pos0[j]),1 \leq k \leq j-1$ ，其中pos1表示所有1的座位编号，pos0表示所有0的座位编号。时间复杂度为 $O(n^3)$，可以用前缀和优化，我们发现每次枚举k的时候就是为了找到dp[i-1] [1 to j-1]的最小值，而 j 的值每次+1，故可以用一个变量表示这个最小值，在每次循环的时候更新一下就行，可以省去一个循环，优化到 $O(n^2)$
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
vector<int> p0,p1;
int dp[5555][5555];
int main(int argc, char const *argv[]) {
int n;
cin >> n;
p0.push_back(0);
p1.push_back(0);
for(int i = 1; i <= n; i++){
int x;
cin >> x;
if(x == 0) p0.push_back(i);
else p1.push_back(i);
}
memset(dp,0x3f,sizeof dp);
for(int i = 0; i <= p0.size(); i++) dp[0][i] = 0;
for(int i = 1; i <= p1.size(); i++) {
int mmin = 0x3f3f3f3f;
for(int j = 1; j <= p0.size(); j++) {
mmin = min(mmin, dp[i-1][j-1]);
dp[i][j] = min(dp[i][j], mmin + abs(p1[i]-p0[j]));
}
}
int ans = 0x3f3f3f3f;
for(int i = 1; i <= p0.size(); i++) ans = min(ans, dp[p1.size()-1][i]);
cout << ans;
return 0;
}
