首页 > 其他分享 >NOIP 模拟赛

NOIP 模拟赛

时间:2024-09-15 13:02:48浏览次数:8  
标签:NOIP 组长 ge tag 111 组员 排序 模拟

警示:看到一道做过的题不要着急上头去写,写炸了心态就崩了。

T1

题意:
有 \(n\) 个人,每个人有经验 \(w_i\)、薪水 \(s_i\)、意愿 \(p_i\) 三个属性。要选出 \(2k\) 个人组成 \(k\) 组,每组两个人。每个组内一人做组长,一人做组员。要求组长经验 \(\ge\) 组员。
每个人可能有三种意愿:组员、组长或者都行。选择人必须根据他的意愿来选。
问能否选出 \(k\) 个组;如果能,最小薪水总和是多少。
\(n\cdot k\le 10^5\)。

首先 \(k>[n/2]\) 肯定没法选出来,直接特判 \(-1\)。
于是 \(10^5\ge n\cdot k\ge 2k^2\),可以得到 \(k\le \dfrac{\sqrt {10^5}}{2}\),也就是 \(O(nk^2)\) 是可行的。

观察到如果人员是按工作经验从小到大排序选择,那么后选择的组长的待选组员集合肯定包含前选择的组长;也就是前面选的组长选了组员,不会影响后面组长选组员。这是无后效性,启发我们动态规划。

一个想法就是 \(dp[i][j][k]\) 表示前 \(i\) 个人有 \(j\) 组,多余 \(k\) 个组员的最小薪水和。转移比较显然。

但是如果只按照工作经验排序无法通过,因为在相同的工作经验人员内部,DP 时必须先遍历到组员,再遍历到组长才行,不然有可能最优解是在这个相同工作经验人员内部选了几组,无法覆盖到这个可能性。
所以排序时按照组员、全能、组长的意愿排序即可。

坑点:sort 的 cmp 函数必须是 \(<\) 而不是 \(\le\)。

T2

原题,做法在动态规划合集的 BoardFolding 处。

T3

维护一个数据结构,支持加数、删数、全体 \(+1\)、全体异或 \(x\)。

显然是 \(01\) Trie。维护前三个操作是很简单的,考虑异或操作对 \(+1\) 操作的影响。

维护一个数 \(tag\),表示此时 Trie 里的所有数,要异或 \(tag\) 后才是真实值。

原本 \(+1\) 操作是沿着 \((111\dots 1)_2\) 的边走,然后把路径上的点交换左右儿子;但是现在多了一个 \(tag\),也就是在 Trie 里 \(\bigoplus tag=(111\dots 1)_2\) 才是真正要进位的数。

所以沿着 \((111\dots 1)_2\bigoplus tag\) 的路径走一遍,交换儿子即可。

标签:NOIP,组长,ge,tag,111,组员,排序,模拟
From: https://www.cnblogs.com/FLY-lai/p/18415151

相关文章

  • CSP 模拟 30
    妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈妈#include<bits/stdc++.h>#defineintlonglong#definelsp<<1#definersp<<1|1#defineintlonglongtypedeflonglongll;typedefunsignedlonglongull;inlineintread(){charch=getchar();intx=0,f=1;for(;ch<'......
  • 【重温童年】基于tkinter模块设计的Q宠大乐斗武器升星模拟器:重温经典,畅享休闲时光
    在快节奏的现代生活中,我们总是在寻找那些能够让我们暂时忘却烦恼,沉浸在简单快乐中的休闲方式。对于许多80后、90后而言,Q宠大乐斗无疑是一款充满回忆的经典网页游戏。它以其独特的宠物养成、战斗系统以及丰富多样的武器系统,吸引了无数玩家的心。今天,就让我们一起重温那段美好的......
  • 【2025】“急救课堂”微信小程序的设计与实现, 在线急救培训与模拟演练、在线急救教育
    博主介绍:  ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W+粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台的优质作者。通过长期分享和实战指导,我致力于帮助更多学生......
  • linux 模拟题
    一,填空题linux主要是基于各种       来完成各种操作。打印当前所在的位置的命令是       linux的选项是哪两种        当前登录的用户tom,切换至用户家目录        想要使用命令本身的作用       ......
  • 南沙C++noip老师解一本通题: 1360:奇怪的电梯(lift)
    ​【题目描述】大楼的每一层楼都可以停电梯,而且第i层楼(1≤i≤N)上有一个数字Ki(0≤=Ki≤=N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:33125代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上”可以到4......
  • 2024 Noip 做题记录(一)
    \(\text{ByDaiRuiChen007}\)Round#1-20240909A.[P10997]ColorProblemLink题目大意你有\(n\)行\(m\)列的一个矩阵,第\(i\)行第\(j\)列的格子(记作\((i,j)\))上写有一个整数\(a_{i,j}\),你可以把所有格子染上红、橙、黄、绿四种颜色之一。红色格子的上方只......
  • macOS 中 Rosetta 模拟器打开,造成 MLX 框架的错误
    概述背景AppleSilicon(M1,M2芯片)是基于ARM架构的,而老的IntelMac是基于x86_64架构的。Rosetta2是macOS提供的工具,用于在AppleSilicon上模拟运行x86应用程序。某些应用程序(如终端)可能默认通过Rosetta运行为x86架构,而不是ARM原生运行。在安装及编......
  • 9.14 模拟赛
    A.矩形小C有一个\(n\timesn\)的矩阵,每个格子有一个颜色\(a_{i,j}\len\)。给定\(k\),你需要计算出对于所有格子,以这个格子为左上角的最大正方形,满足内部颜色数量不超过\(k\)。\(n\le500\)。枚举左上角\(i,j\),二分正方形的边长,然后用\(|a|\)的复杂度求这个正......
  • NOIP 复习题之动态规划
    AT_joi2022ho_c選挙で勝とう首先要先把协作者买出来,再对于之后的州把买的协作者全部用上。则我们可以先枚举需要的协作者数量\(x\),可以知道的是:我们枚举选择哪些\(x\)个协作者,再在剩下的州中选择\(A_i\)最小的\(K-x\)个州即可。则考虑dp。我们对\(B_i\)进行排序后,协作......
  • 2024.09.14模拟赛总结
    $T1$似乎是签到题,但是没开$unsigned$$long$$long$挂成$88$分了。直接模拟即可,从后往前考虑,将每个数放到离其最近的位置,不过不会证...#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongLL;constintN=1000010;structwasd......