代码编织梦想

比赛链接https://atcoder.jp/contests/abc332
比赛时间:2023年 12 月 10 日 20:00-21:40

A题:Online Shopping

标签:枚举、模拟
题意:给定 n n n个物品,第 i i i个物品的价格是 p i p_i pi,需要购买件数是 q i q_i qi,如果购买物品的总花费大于等于 s s s,不需要支付运费,否则需要支付运费 k k k,求最终支付的金额。
题解:求一下购买物品的总花费,判断下是否大于等于 s s s,对应输出即可。
代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ll n, s, k, sum = 0;
    cin >> n >> s >> k;
    for (int i = 1; i <= n; i++) {
        ll p, q;
        cin >> p >> q;
        sum += p * q;
    }
    if (sum >= s) cout << sum;
    else cout << sum + k;
    return 0;
}

B题:Glass and Mug

标签:模拟
题意:给定 G G G容量的玻璃杯和 M M M容量的马克杯,一开始两个杯子里面都没水,给定以下操作先后顺序,求 K K K次操作之后,两个杯子中各自的水量。( G < M G<M G<M

  1. 如果玻璃杯装满水(即装满 G G G),倒掉玻璃杯中所有水。
  2. 否则,如果马克杯是空的,装满水。
  3. 否则,将马克杯中的水倒到玻璃杯中。

题解:按照题目要求模拟就好了,维护两个变量,两个杯子中各自水量情况。按照题目中的先后顺序,模拟这 K K K次操作。注意第三个情况,我们把水从马克杯往玻璃杯倒的时候,需要考虑到目前玻璃杯还能装多少 以及马克杯能倒过去多少,应该要拿这两种情况中的小的那个倒过去。
代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k, g, m;
    cin >> k >> g >> m;

    // 当前玻璃杯里的水量 马克杯里的水量
    int a = 0, b = 0;
    for (int i = 1; i <= k; i++) {
        if (a == g) {
            a = 0;
        }
        else if (b == 0) {
            b = m;
        }
        else {
            // 当前玻璃杯里还能装多少水量
            // 当前马克杯里的水量
            int x = min(g - a, b);
            a += x;
            b -= x;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}

C题:T-shirts

标签:枚举、模拟
题意:给定一个长度为 N N N的字符串 S S S(只含 0 、 1 、 2 0、1、2 012),表示具体日程安排。
0 0 0:没有计划; 1 1 1:出去吃饭; 2 2 2:参加竞赛
0 0 0:没有计划的日子,会把所有穿过的T恤洗掉
1 1 1:出去吃饭,可以穿素色T恤或者带 l o g o logo logo的T恤
2 2 2:参加竞赛,只能穿带 l o g o logo logo的T恤
一开始给定你 M M M件素色T恤,求最少要购买几件带 l o g o logo logo的T恤才能满足日程安排?
穿过了的 T恤就不能再穿了,除非给它重新洗过了。
1 < = M < = N < = 1000 1<=M<=N<=1000 1<=M<=N<=1000
题解:发现其实 N N N很小,所以我们可以直接从小到大枚举一下需要购买的带 l o g o logo logo的 T恤数量,然后跑下字符串 S S S的日程,看看是否满足日程安排。因为是从小到大,找到的第一个就可以直接输出了。
题目中有要求,穿过了的 T恤就不能再穿了,除非给它重新洗过了。所以我们在枚举带 l o g o logo logo的 T恤数量的过程中,需要维护一下目前还没穿和已经穿过的素色 T恤数量、目前还没穿和已经穿过的带 l o g o logo logo的 T恤数量。

以下是针对于具体日程安排的处理逻辑:
0 0 0:没有计划的日子,会把所有穿过的T恤洗掉;这时候把对应已经穿过的加到未穿过的数量上,然后把对应已经穿过的数量置 0 0 0
1 1 1:出去吃饭,很显然要优先穿素色的T恤,先判这个逻辑;如果没有未穿过的素色T恤,再考虑穿带 l o g o logo logo的 T恤,如果带 l o g o logo logo的 T恤也没有,那说明现在枚举的购买 T恤数量 k k k不够,跳出往后找更大数量。
2 2 2:参加竞赛。和出去吃饭的逻辑差不多,只不过因为只能穿带 l o g o logo logo的T恤,所以直接判带 l o g o logo logo的情况就好了。
代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;

    // k: 买带logo的T恤 件数
    for (int k = 0; k <= n; k++) {
        bool f = 1;
        int a1 = m, a2 = 0; // plain  没穿过/已经穿过
        int b1 = k, b2 = 0; // logo  没穿过/已经穿过
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') {
                a1 += a2; a2 = 0;
                b1 += b2; b2 = 0;
            }
            else if (s[i] == '1') {
                if (a1 > 0) a1--, a2++;
                else {
                    if (b1 > 0) b1--, b2++;
                    else {
                        f = 0;
                        break;
                    }
                }
            }
            else if (s[i] == '2') {
                if (b1 > 0) b1--, b2++;
                else {
                    f = 0;
                    break;
                }
            }
        }
        if (f == 1) {
            cout << k << endl;
            return 0;
        }
    }
    return 0;
}

D题:Swapping Puzzle

标签:全排列、深度优先搜索
题意:给定两个行数和列数分别是 H H H W W W的二维矩阵 A A A B B B。可以对 A A A矩阵的相邻两行或者相邻两列进行交换,求最少的交换次数能够使得 A A A矩阵变成 B B B矩阵。( 2 < = H , W < = 5 2<=H,W<=5 2<=H,W<=5
题解:看到这个数据这么小,很容易想到暴搜。对矩阵 A A A的行和列分别做一个全排列深搜。
举个例子,比如行数 H = 3 H=3 H=3,列数 W = 3 W=3 W=3
那么一开始行的情况: 1 、 2 、 3 1、2、3 123
来看个行的其中一个全排列的情况: 2 、 3 、 1 2、3、1 231,这个情况也就是说现在的第 1 1 1行是原来的第 2 2 2行,现在的第 2 2 2行是原来的第 3 3 3行,现在的第 3 3 3行是原来的第 1 1 1行。

那我们是不是弄出了一种行的交换情况,那这种情况行到底交换了多少次呢?熟悉逆序数的同学,应该能发现交换的次数 其实就是这个情况的序列逆序数的值。
比如这里 2 、 3 、 1 2、3、1 231 2 2 2要在 1 1 1的前面 肯定是和 1 1 1进行了交换。

同理,列也是类似的;我们对行和列都做一个全排列操作之后,分别统计一下对应序列的逆序数值,相加一下就是改变成目前这种情况,总的交换次数。

然后还有个问题就是如何去判断这种情况下 A A A矩阵和 B B B矩阵是否相同的,我们可以把全排列的情况记录一下,到时候比较的时候看看这种情况下 A A A矩阵的当前行和当前列是对应初始 A A A矩阵的哪一行和哪一列,然后对应进行比较即可。
代码

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 1e9;
int a[15][15], b[15][15];
int c[15], d[15], vis1[15], vis2[15];

void dfs1(int p) { // 做列的全排列
    if (p == m + 1) {
        bool f = true;
        for (int i = 1; i <= n; i++) {
            if (!f) break;
            for (int j = 1; j <= m; j++) {
                if (a[c[i]][d[j]] != b[i][j]) {
                    f = false;
                    break;
                }
            }
        }
        if (f) {
            int cnt = 0; // 操作次数
            for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            if (c[i] > c[j]) cnt++;

            for (int i = 1; i <= m; i++)
            for (int j = i + 1; j <= m; j++)
            if (d[i] > d[j]) cnt++;
            ans = min(ans, cnt);
        }
        return ;
    }
    for (int i = 1; i <= m; i++) {
        if (!vis2[i]) {
            vis2[i] = 1;
            d[p] = i;
            dfs1(p + 1);
            vis2[i] = 0;
        }
    }
}

void dfs2(int p) { // 针对行做一个全排列
    if (p == n + 1) {
        dfs1(1);
        return ;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis1[i]) {
            vis1[i] = 1;
            c[p] = i; // 现在的第p行是原来的第i行
            dfs2(p + 1);
            vis1[i] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    cin >> a[i][j];

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    cin >> b[i][j];

    dfs2(1);
    if (ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}

E题:Lucky bag

标签:贪心、随机化
题意:给你 n n n件物品,第 i i i件物品的权重为 w i w_i wi,想要把这些物品分成 d d d组,希望最小化总重量的方差。
方差定义: V = 1 D ∑ i = 1 D ( x i − x ˉ ) 2 V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2 V=D1i=1D(xixˉ)2 x ˉ \bar{x} xˉ定义为各组数据和的平局值: x ˉ = 1 D ( x 1 + x 2 + ⋯ + x D ) \bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D) xˉ=D1(x1+x2++xD)
题解: 通过观察能发现这是一个贪心,当 x i x_i xi的值越接近答案越小, 我们可以把每个数加到当前和最小的组里,然后通过随机化 进行多次贪心,随机化的次数可以稍微多点。每次贪心把序列打乱, 然后多次进行操作获得对应的值,从中取最小值就可以了。
代码

#include <bits/stdc++.h>
using namespace std;

int n, d, w[20], b[20], t = 2000000;
double ans = 1e18, sum = 0;

int main() {
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    double avg = sum / d;
    while (t--) {
        memset(b, 0, sizeof(b));
        random_shuffle(w + 1, w + n + 1);
        int k = 1;
        sum = 0;
        for (int j = 1; j <= n; j++) {
            for (int i = 2; i <= d; i++) {
                if (b[i] < b[k]) k = i;
            }
            b[k] += w[j];
            k = 1;
        }
        for (int i = 1; i <= d; i++) sum += (avg - b[i]) * (avg - b[i]);
        sum = sum / d;
        ans = min(ans, 1.0 * sum);
    }
    printf("%.15lf", ans);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/oitutor/article/details/134917436

atcoder beginner contest 322 (a~f题)_阿史大杯茶的博客-爱代码爱编程

A - First ABC 2 Description Problem Statement You are given a string

【oj比赛日历】快周末了,不来一场比赛吗? #12.09-爱代码爱编程

CompHub[1] 实时聚合多平台的数据类(Kaggle、天池…)和OJ类(Leetcode、牛客…)比赛。本账号会推送最新的比赛消息,欢迎关注! 以下信息仅供参考,以比赛官网为准 目录 2023-12-09(周六) #7场比赛2023-12-10(周日) #4场比赛2023-12-11(周一) #1场比赛2023-12-12(周二) #无比赛

c语言-爱代码爱编程

        阶乘的概念:一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,且0的阶乘为1,自然数n的阶乘写作n! 。 任何大于等于1 的自然数n 阶乘表示方法: n!=1×2×3×…×(n-1)×n 或 n!=n×(n-1)! 0!=1 1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 … n

c语言之字符逆序(牛客网)-爱代码爱编程

个人主页(找往期文章包括但不限于本期文章中不懂的知识点):我要学编程(ಥ_ಥ)-CSDN博客 字符逆序__牛客网  题目:  思路:既然有空格就不能用scanf函数来接收字符了。因为scanf函数遇到空格会停止读取。我们可以用gets函数来进行读取。定义一个字符数组,用来存储字符串。我们再将这个字符串逆序输出就可以了。 gets函数的知识点:

c++max函数的使用-爱代码爱编程

在C++中,std::max函数是一个模板函数,位于<algorithm>头文件中,这个函数用于比较两个或多个值,并返回其中的最大值。 下面是代码示例: #include <iostream> using namespace std; int max(int num1, int num2) { if (num1 >

【effective objective -爱代码爱编程

文章目录 前言六、理解“属性”这一概念七、在对象内部尽量直接访问实例变量八、理解“对象等同性”这一概念九、以“类族模式”隐藏实现细节十、在既有类中使用关联对象存放自定义数据十一、理解objc_msgSend的作

【算法训练营】等式,道路升级(c++,python实现)-爱代码爱编程

等式 问题描述 有n个变量和m个“相等”或“不相等”的约束条件,请你判定是否存在一种赋值方案满足所有m个约束条件。 输入格式 第一行一个整数T,表示数据组数。 接下来会有T组数据,对于每组数据: 第一行是两个整数n,m,表示变量个数和约束条件的个数。 接下来m行,每行三个整数a,

c++:lambda-爱代码爱编程

初识Lambda //[]()->{}; //捕获列表,参数列表,返回类型,函数体 #include <iostream> using namespace std; /* bool compare

掘根宝典之c++友元(友元函数,友元类,友元成员函数)-爱代码爱编程

什么是友元 生活中你的家有客厅(public),有你的卧室(private) 客厅所有来的客人都可以进去,但是你的卧室是私有的,也就是说只有你能进去 但是呢,你也可以让A进去,不过实现这个的关键是让A称为你的好朋友。 让A成为你的好朋友的这个过程就是友元 我们都知道,在类外我们是无法直接访问类对象的私有数据的,只能通过类的公有方法来访问,有的时候

atcoder beginner contest 333 (a -爱代码爱编程

目录 [A - Three Threes](https://atcoder.jp/contests/abc333/tasks/abc333_a)Problem StatementConstraintsInput

atcoder abc beginer 332 d -爱代码爱编程

        暴力枚举,分别对行和列进行全排列,然后检查这种方案是否能使a与b相同,并计算这种方案最少需要的操作数(也就是全排列方案中的逆序对的数量,这里我用了归并来计算,其实冒泡也就够了,因为数据范围很小,只有2-5),这里检查a与b是否相同用了一些技巧(从别人学来的)。         a[sta1[i]][sta2[j]]!=b[i][j](st

abc332:e -爱代码爱编程

状态压缩,dp 题目:E - Lucky bag (atcoder.jp) 代码如下:注释写的很详细了。 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF= 0x3f3f3f3f; const int N=3e5+5e4;