当前位置：网站首页>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;
}边栏推荐
- Bean生命周期
- 数独 | 回溯-7
- TF中使用zeros(),ones(), fill()方法生成数据
- Wps下划线怎么弄？Wps添加下划线的最全方法
- LED闪烁 闪灯芯片IC 手电筒IC 闪灯控制IC 闪烁IC流水灯
- CVPR22 Oral｜通过多尺度token聚合分流自注意力，代码已开源
- 别叫我玩，我要考PMP：考PMP选择机构需要了解的那些事儿
- 论文解读（DropEdge）《DropEdge: Towards Deep Graph Convolutional Networks on Node Classification》
- Technology Sharing | How to use the JSON Schema mode of interface automation testing?
- AI识万物：从0搭建和部署手语识别系统
猜你喜欢
随机推荐
Install win virtual machine on VMware
ACM MM 2022 | Cloud2Sketch: Painting with clouds in the sky, AI brush strokes
Cookie, session, token
几种绘制时间线图的方法
Word文档怎么输入无穷大符号∞
别叫我玩，我要考PMP：考PMP选择机构需要了解的那些事儿
CVPR22 Oral | shunt through multi-scale token polymerization from attention, code is open source
Bean life cycle
FS4066耐高压1到4节内置MOS的锂电池充电管理芯片
json事例
APP自动化测试框架-UiAutomator2基础入门
STC8H Development (15): GPIO Drives Ci24R1 Wireless Module
hdu 1333 Smith Numbers（暴力思路）
STC8H开发(十五): GPIO驱动Ci24R1无线模块
leetcode:数组中的第K个最大元素
SQL语句及索引的优化
必看设计干货｜易知微设计师是怎么做标准可视化设计服务的？
np中的round函数,ceil函数与floor函数
万字总结：分布式系统的38个知识点
Pagoda measurement - building LightPicture open source map bed system