首页 > 其他分享 >7/20 训练笔记

7/20 训练笔记

时间:2024-07-20 16:29:16浏览次数:12  
标签:星星 q1 20 cout 训练 int rep 笔记 两颗

闲话

调试约一个下午后发现极大值设小了。

Cardboard Box

考虑开两个堆 \(q_1\) 和 \(a_2\),一个存入所有一颗星星的取法,另一个存入所有两颗星星的取法。
每次两颗两颗比较,然后如果某一次取了一颗星星,那么(设这颗星星对应关卡编号为 \(i\))把 \(b_i - a_i\) 压入堆中。
还有一些别的细节,见代码。
代码:

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
int a[300010], b[300010], del[300010][3], ch[300010], w, n, ans, cnt, res;
map<int, int> mp;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q1, q2;
void debug(priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q) {
    cout << "[ ";
    while (!q.empty()) {
        cout << "{ " << q.top().first << " " << q.top().second << " }" << " ";
        q.pop();
    }
    cout << "]";
}
signed main() {
    cin.tie(0) -> ios :: sync_with_stdio(false);
    cin >> n >> w;
    rep (i, 1, n) {
        ch[i] = 0;
        cin >> a[i] >> b[i];
        q1.push({a[i], i});
        q2.push({b[i], i});
    }
    if (w == 2 * n) {
        rep (i, 1, n) {
            ans += b[i];
        }
        cout << ans << "\n";
        rep (i, 1, n) {
            cout << 2;
        }
        cout << "\n";
        return 0;
    }
    if (w % 2 == 1) {
        q1.push({0, 0});
        ch[0] = 1;
        w++;
    }
    while (cnt < w) {
        while (!q1.empty() && del[q1.top().second][1]) {
            q1.pop();
        }
        while (!q2.empty() && del[q2.top().second][2]) {
            q2.pop();
        }
        int a1 = 0x3f3f3f3f3f3f3f3f, id1 = 0, a2 = 0x3f3f3f3f3f3f3f3f, id2 = 0;
        if (!q1.empty()) {
            a1 = q1.top().first; id1 = q1.top().second; q1.pop();
            while (!q1.empty() && del[q1.top().second][1]) {
                q1.pop();
            }
            a2 = q1.top().first; id2 = q1.top().second; q1.pop();
        }
        int b1 = 0x3f3f3f3f3f3f3f3f, idb = 0;
        if (!q2.empty()) {
            b1 = q2.top().first; idb = q2.top().second; q2.pop();
        }
        if ((mp[id1] || mp[id2] || mp[idb]) && (id1 && id2 && idb)) {
            assert(0);
        }
        if (a1 + a2 <= b1) {
            // cout << a1 << " " << a2 << "\n";
            cnt -= ch[id1] + ch[id2];
            ch[id1]++; ch[id2]++;
            // mp[id1] = mp[id2] = 1;
            if (ch[id1] == 1) {
                q1.push({b[id1] - a[id1], id1});
            }
            if (ch[id2] == 1) {
                q1.push({b[id2] - a[id2], id2});
            }
            if (ch[id1] == 2) {
                del[id1][1] = 1;
                mp[id1] = 1;
            }
            if (ch[id2] == 2) {
                del[id2][1] = 1;
                mp[id2] = 1;
            }
            del[id1][2] = del[id2][2] = 1;
            q2.push({b1, idb});
            // cout << "q1: "; debug(q1); cout << "\n";
            // cout << "q2: "; debug(q2); cout << "\n";
            // ans += a1 + a2;
            cnt += ch[id1] + ch[id2];
        } else {
            // cout << b1 << "\n";
            cnt -= ch[idb];
            ch[idb] += 2;
            del[idb][1] = 1;
            del[idb][2] = 1;
            mp[idb] = 1;
            q1.push({a1, id1});
            q1.push({a2, id2});
            // cout << "q1: "; debug(q1); cout << "\n";
            // cout << "q2: "; debug(q2); cout << "\n";
            // ans += b1;
            cnt += ch[idb];
        }
    }
    assert(cnt == w);
    rep (i, 1, n) {
        ans += (ch[i] == 1 ? a[i] : (ch[i] == 2 ? b[i] : 0));
        assert(ch[i] <= 2);
        res += ch[i];
    }
    // assert(res == w || res == w - 1);
    cout << ans << "\n";
    rep (i, 1, n) {
        cout << ch[i];
    }
    cout << "\n";
}

标签:星星,q1,20,cout,训练,int,rep,笔记,两颗
From: https://www.cnblogs.com/IANYEYZ/p/18313315

相关文章

  • 基于mnist数据集的手写数字识别模型的训练可视化预测
    使用 tensorflow库创建训练模型数据集使用公开的mnist 一、构建模型fromtensorflow.keras.layersimportDense,DropoutimporttensorflowastfdefmnistModel():model=tf.keras.Sequential([tf.keras.layers.Flatten(input_shape=(28,28)),#对......
  • DatawhaleAI夏令营 机器学习方向 学习笔记
    电力需求预测挑战赛理解赛题【训练时序预测模型助力电力需求预测赛题任务给定多个房屋对应电力消耗历史N天的相关序列数据等信息,预测房屋对应电力的消耗。赛题数据赛题数据由训练集和测试集组成,为了保证比赛的公平性,将每日日期进行脱敏,用1-N进行标识。即1为数据集最近一天,......
  • 代码随想录算法训练营第31天 | 贪心3:134.加油站、135.分发糖果、860.柠檬水找零、406.
    代码随想录算法训练营第31天|贪心3:134.加油站、135.分发糖果、860.柠檬水找零、406.根据身高重建队列134.加油站https://leetcode.cn/problems/gas-station/description/代码随想录https://programmercarl.com/0134.加油站.html135.分发糖果https://leetcode.cn/problems......
  • 2023年度好题(1)
    文章有点长,都是由本人一点一点写出来的,公式加载需要一段时间。CF1152ENekoandFlashback思路来自@apple365。思路任意一组\(b_i,c_i\)都是相邻的两条边,所以我们将\(b_i\)和\(c_i\)连起来,如果可以跑通一条欧拉路径,那么这条欧拉路径上的所有数字就可以组成数组\(a\)......
  • 240720-模态应变法计算阻尼-论文阅读
    技术报告:NASA-ComputationalSimulationofDampinginCompositeStructures摘要提出了一种复合材料结构被动阻尼预测的计算方法。该方法综合了微观力学、层压理论和结构阻尼理论,建立了多级阻尼模型。采用有限元离散化方法对结构层面的阻尼进行了模拟。论文中将这个方法应......
  • 2024牛客暑期多校训练营2
    H.InstructionsSubstring题目大意:给出一段长为\(n\)的字符串,其中WASD分别代表向上下左右走,给出目的地\((x,y)\),选择一段连续子序列使得从\((0,0)\)出发可以经过目的地,求这样的子序列的总数。思路:用前缀和记录到\(i\)为止到达的位置,从前往后遍历右端点\(r\),找到恰好到......
  • 2064:【例2.1】交换值 题解
    题目链接题目描述输入两个正整数\(a\)和\(b\),试交换\(a\)、\(b\)的值(使\(a\)的值等于\(b\),\(b\)的值等于\(a\))。解题思路该题有很多种方法,例如:直接输出\(b\)和\(a\)(偷鸡方法)使用algorithm库的swap函数使用额外变量辅助位运算\(......\)但这道题目放在"运算符和表达式"......
  • SQL Server 2008中的代码安全(七):证书加密
    原文链接:https://blog.csdn.net/downmoon/article/details/6252336证书可以在数据库中加密和解密数据。证书包含密钥对、关于证书拥有者的信息、证书可用的开始和结束过期日期。证书同时包含公钥和密钥,前者用来加密,后者解密。SQLServer可以生成它自己的证书,也可以从外部文件或程......
  • 谷粒商城实战笔记-36~44-Vue
    文章目录一,36-前端基础-Vue-介绍&HelloWorld1,MVVM思想直接操作DOM的示例使用Vue和MVVM的示例MVVM与DOM操作的主要区别2,Vue简介3,Vue的使用步骤3.1新建项目3.2安装依赖3.3使用Vue二,37-前端基础-Vue-基本语法&插件安装1,v-model1.1,双向绑定1.2,vue的双向绑定1.2.1html......
  • 谷粒商城实战笔记-35-前端基础-ES6-模块化
    文章目录一,什么是模块化二,export1.`export`语法2.批量导出3.默认导出三,import1,import语法2,批量导入一,什么是模块化模块化编程是一种软件设计技术,它将程序分解为独立的、可复用的部分,每个部分负责执行特定的功能。这种设计方法在多种编程语言中都有应用,包括Jav......