题解:Edu Codeforces 109(div2)

题目链接

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇