当前位置：网站首页>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;
}边栏推荐
- TF中random.normal()与random.truncated_normal()
- cadence中复制一部分PCB到另一个PCB中去
- 别叫我玩，我要考PMP：考PMP选择机构需要了解的那些事儿
- SecureCRT 设置超时自动断开连接时长
- ACM MM 2022 | Cloud2Sketch: 长空云作画，AI笔生花
- 同步锁synchronized追本溯源
- 5个 Istio 访问外部服务流量控制最常用的例子，你知道几个？
- Lyapp exponents and bifurcation diagrams for fractional chaotic systems
- 10个 Istio 流量管理 最常用的例子，你知道几个？
- CVPR22 Oral｜通过多尺度token聚合分流自注意力，代码已开源
猜你喜欢
10个 Istio 流量管理 最常用的例子，你知道几个？
万字总结：分布式系统的38个知识点
ACM MM 2022 | Cloud2Sketch: Painting with clouds in the sky, AI brush strokes
kvm虚拟机出现启动不了,NOT available,PV大于分区
SQLi-LABS Page-2 (Adv Injections)
APP automation test framework - UiAutomator2 introductory
Converting angles to radians
几种绘制时间线图的方法
必看设计干货｜易知微设计师是怎么做标准可视化设计服务的？
Bean生命周期
随机推荐
编程语言中，取余和取模的区别
论文解读（DropEdge）《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》
NetCore路由的Endpoint模式
Pagoda measurement - building LightPicture open source map bed system
Shanghai Konan SmartRocket series product introduction (3): SmartRocket iVerifier computer interlocking system verification tool
mysql多表左链接查询
Tensorflow中使用convert_to_tensor去指定数据的类型
[Implementation of the interface for adding, deleting, checking, and modifying a double-linked list]
In programming languages, the difference between remainder and modulo
【stack】【queue】【priority_queue】【deque】Detailed explanation
supervisor 命令操作大全「建议收藏」
Use zeros(), ones(), fill() methods to generate data in TF
STC8H development (15): GPIO drive Ci24R1 wireless module
Interpretation of the paper (DropEdge) "DropEdge: Towards Deep Graph Convolutional Networks on Node Classification"
LeetCode26：删除有序数组中的重复项
威纶通触摸屏制作自定义弹出窗口的具体方法（3种）
CVPR22 Oral｜通过多尺度token聚合分流自注意力，代码已开源
Tensorflow模型整体构建流程
Technology Sharing | How to use the JSON Schema mode of interface automation testing?
Referenced file contains errors 完美解决方法