当前位置：网站首页>题解：Edu Codeforces 109(div2)
题解：Edu Codeforces 109(div2)
2022-08-09 20:51:00 【Here_SDUT】
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;
}边栏推荐
- 基于网络数据流的未知密码协议逆向分析
- [Essay] To the friends of the 19th issue
- 继承关系下构造方法的访问特点
- 线性表的定义和基本操作
- visual studio 2022调试技巧介绍
- UE4_定序器控制蓝图对象
- Don't tell me to play, I'm taking the PMP exam: what you need to know about choosing an institution for the PMP exam
- XXE-XML外部实体注入-知识点
- Cholesterol-PEG-Thiol, CLS-PEG-SH, Cholesterol-PEG-Sulfhydryl for improved solubility
- 顺序表的定义和基本操作
猜你喜欢
RHEL7系统修复rm -rf /boot /etc/fstab
URL Protocol 网页打开应用程序
[Deep learning] pix2pix GAN theory and code implementation
Acrel5000web能耗系统在某学院的应用-Susie 周
FS4066耐高压1到4节内置MOS的锂电池充电管理芯片
数据集成API如何成为企业数字化转型的关键？
Simulation of Water Temperature Control System Based on Fuzzy PID Controller
DSPE-PEG-Silane,DSPE-PEG-SIL,磷脂-聚乙二醇-硅烷修饰二氧化硅颗粒用
Don't tell me to play, I'm taking the PMP exam: what you need to know about choosing an institution for the PMP exam
How to fix Windows 11 not finding files
![[Deep learning] pix2pix GAN theory and code implementation](/img/4a/b95b68bee66bd572cf213994e26429)
随机推荐
阿里二面：没有 accept，能建立 TCP 连接吗？
DSPE-PEG-Silane, DSPE-PEG-SIL, phospholipid-polyethylene glycol-silane modified silica particles
【高效工具】远程控制软件 ToDesk（收藏夹）
RHEL7系统修复rm -rf /boot /etc/fstab
[corctf 2022] section
Reverse Analysis of Unknown Cryptographic Protocol Based on Network Data Flow
QGIS编译SIP的问题
企业数据打通有什么好处？不同行业怎么解决数据打通难题？
威纶通触摸屏制作自定义弹出窗口的具体方法（3种）
Excel如何打出正负号？Excel打出正负号的方法
[Generic Programming] Full Detailed Explanation of Templates
【stack】【queue】【priority_queue】【deque】详解
Word箭头上面怎么打字
Skywalking系列学习之Trace Profiling源码分析
继承关系下构造方法的访问特点
matlab neural network ANN classification
消防安全培训｜“蓝朋友”，开课了！
linux定时执行sql文件[通俗易懂]
Overview of Security Analysis Technology for Smart Home Devices
Unity_物体自转