当前位置：网站首页>Solution: Edu Codeforces 109 (div2)
Solution: Edu Codeforces 109 (div2)
2022-08-09 23:14:00 【Here_SDUT】
A. Potion-making
题意
Tells you the concentration of the medicine you need to configurek%,Potion is made by mixing water and medicine,Allows you to find the smallest dose of the potion,Satisfy the concentration of k%,Concentration calculation method：volume of medicine/The total volume of the drug.
分析
Let the volume of the medicine be a,The volume of water is b,则\frac{1-k}{k} = \frac{b}{a},那么要求a+b最小,Just ask1-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的排列,有一个操作：Reorder the numbers in a continuous range of the arrangement,But the entire permutation cannot be selected as an interval,Q It takes at least a few tweaks to turn an array into ascending order.
分析
有四种情况：
- The initial state is already ascending：需要0次.
- 初始时1on the far left orn在最右端,则需要1Adjustment to become ascending order.
- 初始时1on the far right andn在最左端,Discover what is needed no matter what3多次才行.
- In the remaining cases, only two adjustments are required,Because the max and min are inside.
分别判断即可.
代码
#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(思维+贪心+模拟)
题意
There are robots at certain points on a number line,It is guaranteed that there will not be more than one robot at a point,The speed of each robot is1,Gives the initial orientation of the robotL或R,坐标为0和mThe place is a wall,The robot turned around immediately after hitting the wall.If two robots meet at an integer coordinate point, the two robots disappear,Ask the time when all bots disappear,Use if it doesn't disappear-1代替.
分析
for each pair of robots（Suppose the coordinates of the robot on the left are x_1,右边的为x_2）一共有四种情况：
（1）RL：左边的向右,右边的向左走,下同,The meeting time is \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：This situation can be divided into two categories,如果 x_1 距离 0 的距离小于 x_2 距离 m 的位置,The meeting time is m-x_2+\frac{x_1+x_2}{2},否则为m+\frac{x_1-x_2}{2}
Since the speed of the robot is equal to 1,So asking two robots to meet at an integer point is actually equivalent to requiring the meeting time to be an integer,It can be found from the above four situations：An encounter is only possible if the coordinates of the two robots have the same parity,Naturally, it is conceivable to divide the robot into parity and even for processing.
After parity grouping,Just solve the sequence of encounters of one of the groups,The same is true for the other group,Therefore, the following discussion is about a group of robots with the same parity.我们可以发现,Orientation sequence for a set of robots,相邻的”RL”They must have met first,Also on the far left”LL”Definitely meet first,Then process the leftmost of the entire direction sequence first”LL”,and will be adjacent”RL”Also after the collision,The rest can only be”LRRRR…”或者”RRR….”.类似于”LL”,最右边的”RR”It will definitely be the first to meet,All can be moved from right to left”RRRR”处理掉,The rest can only be”LR”、”L”、 “R”,LRCollision is also possible,The remaining single is a robot that will never collide.
The above processing can be implemented using a stack：Put in one robot at a time,与栈顶比较,If the top of the stack and the robot placed in it just fit”LL”或者”RL”,则将栈顶弹出,Calculate the time when the two robots meet,Otherwise put the robot in the stack,最后的情况就是”LRRRR…”或者”RRR….”,Two robots pop up each time to judge the direction for calculation,The formula for the encounter time is given at the top.
Another thing to note is that the coordinates given by the title are not ordered,需要先进行排序.
代码
#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;//Define an odd stack and an even stack
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) {//The coordinates of the current robot are odd,Push onto the odd stack
if (sta1.empty())//If the stack is empty, just push it directly
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 {//even stack
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]);
}
}
}
}
//Finally process from right to leftRR和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序列表示,1Indicates that someone is sitting initially,0表示空座位.You have an operation,Anyone can go to any vacant seat,The time required is abs(i-j),其中iIndicates the person's seat number,jIndicates the seat number he is going to.Ask you to use the least amount of time,Makes the seat that was originally a human being completely empty,The number of title sponsors is less than or equal to half the number of seats
分析
首先将0和1Separate into two containers,用 dp[i][j] 表示已经处理了前 i 个1,且第 i 个1被分配到了第 j 个0location for the least cost.我们可以从第i-1个1The situation is introduced Noi个1的情况：由于第i个1被分配到了第j个0的位置,那么第i-1个1Definitely assigned in the first1到j-1个0的某个位置（After a little thought, you can figure it out）,于是dp[i][j] = min(dp[i-1][k]) + abs(pos1[i]-pos0[j]),1 \leq k \leq j-1 ,其中pos1表示所有1seat number,pos0表示所有0seat number.时间复杂度为 O(n^3),可以用前缀和优化,We find each enumerationktime is to finddp[i-1] [1 to j-1]的最小值,而 j 的值每次+1,Therefore, this minimum value can be represented by a variable,Just update it every time you loop,A loop can be omitted,优化到 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;
}边栏推荐
- ACM MM 2022 | Cloud2Sketch: 长空云作画，AI笔生花
- 在VMware上安装win虚拟机
- 单元测试
- Bean life cycle
- Technology Sharing | How to use the JSON Schema mode of interface automation testing?
- cadence中复制一部分PCB到另一个PCB中去
- Puyuan Jingdian turned losses into profits in the first half of the year, and high-end products continued to develop!Are you optimistic about "Huawei" in the instrument industry?
- Install win virtual machine on VMware
- Simple questions peek into mathematics
- STC8H开发(十五): GPIO驱动Ci24R1无线模块
猜你喜欢
Lyapp exponents and bifurcation diagrams for fractional chaotic systems
Several ways to draw timeline diagrams
4D Summary: 38 Knowledge Points of Distributed Systems
6个规则去净化你的代码
hdu 1503 Advanced Fruits（最长公共子序列的应用）
Word怎么制作一张标准的答题卡？
TF生成均匀分布的tensor
必看设计干货｜易知微设计师是怎么做标准可视化设计服务的？
LoRa Basics无线通信技术和应用案例详解
别叫我玩，我要考PMP：考PMP选择机构需要了解的那些事儿
随机推荐
C语言预处理命令是什么？
AI+医疗：使用神经网络进行医学影像识别分析
编程时请选择正确的输入法，严格区分中英文
在VMware上安装win虚拟机
Daily practice of PMP | Do not get lost in the exam -8.8 (including agility + multiple choice)
PMP daily practice | didn't lost a 8.9 (including agile + multi-select)
The overall construction process of the Tensorflow model
SQL语句及索引的优化
MySQL跨表、多表更新SQL语句总结
技术分享 | 接口自动化测试如何处理 Header cookie
APP automation test framework - UiAutomator2 introductory
FS4066耐高压1到4节内置MOS的锂电池充电管理芯片
什么是IDE（集成开发环境）？
Word第一页不要页眉怎么设置？设置Word首页不要页眉方法教程
NIO Cup 2022 Nioke Summer Multi-School Training Camp 7 CFGJ
抽象类 or 接口
Technology Sharing | How to use the JSON Schema mode of interface automation testing?
6个规则去净化你的代码
Leetcode 93 复原IP地址
AI识万物：从0搭建和部署手语识别系统