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

20241002 模拟赛

时间:2024-11-08 15:20:55浏览次数:1  
标签:cnt 20241002 max sum 贡献 枚举 三元组 模拟

20241002 模拟赛

A inv

容易想到按 \(s\) 中 \(0\) 和 \(1\) 的连续段将原序列分段考虑。显然大的数放前面最好。于是按值从大到小,段从前往后分配值,\(0\) 的段降序,\(1\) 的段升序即可完成构造。求逆序对可以直接树状数组。但这题每个不同 \(01\) 段之间都有大小关系,于是每段中的每个数都与后面所有段组成逆序对,再加上倒序段中的贡献就能 \(O(n)\) 完成。

B beauty

做法:考虑枚举一个分界值 \(v\),将小于等于 \(v\) 的 \(a_i\) 设为 \(0\),其余设为 \(1\)。再枚举 \(a\) 中 \(0\) 的个数 \(cnt\)。这时一个序列的贡献就是 \(2\min(cnt, n-cnt)\)。易得这样序列的个数为 \(v^{cnt}(V-v)^{n-cnt}C_n^{cnt}\)。

考虑这样做的正确性。对于 \(a\) 中的两个对应位置的值 \(x,y(x\ge y)\),它们对答案的贡献为 \(2(x-y)\)。对于枚举到的每个 \(v\in[y,x)\),这时 \(x\) 被设置为 \(1\),\(y\) 被设置为 \(0\),这两个位置的贡献就为 \(2\)。总共造成了 \((x-1)-y+1=x-y\) 次贡献。所以每对位置的贡献都正确,从而总贡献正确。换句话说,这里就是将累加每个位置的贡献转化为累加每个分界点的贡献。

C max

注意到一个性质:每一个特征值都能用不超过 \(3\) 个数生成,原因是三维都小于 \(max\) 的三元组没有用,剩下的每个三元组至少贡献了一个 \(max\)。依次考虑选了几个三元组。

选了一个:这时方案数显然为 \(n\) 种。

选了两个:总方案数为 \(C_n^2\)。但是如果这两个三元组之间存在三维偏序关系,得到的特征值就与只选大三元组相同,减去这样的方案数。记 \(x_i=\sum_{j=1}^n [a_j<a_i\land b_j<b_i\land c_j<c_i]\)。

选了三个:总方案数为 \(C_n^3\)。仅能由三个三元组得到的特征值显然是三个 \(max\) 分别来自三个三元组。那么不合法的(与选两个重复的)就存在一个三元组贡献了至少两个 \(max\)。那么考虑贡献两个和三个的情况。

两个:不妨设两个 \(max\) 分别是 \(a,b\)(其他两种同理)。那么枚举贡献了两个 \(max\) 的这个三元组 \(i\)。那么就要求出有多少种 \(j,k\) 满足 \(a_j<a_i,b_j<b_i,a_k<a_i,b_k<b_i\)。记 \(y_i=\sum_{j=1}^n [a_j<a_i\land b_j<b_i]\)。显然对于一个 \(i\),这样的方案数就是 \(C_{y_i}^2\)(记另两种为 \(C_{z_i}^2+C_{w_i}^2\))。

三个:此时的 \(i,j,k\) 满足 \(a_j<a_i,b_j<b_i,c_j<c_i,a_k<a_i,b_k<b_i,c_k<c_i\),也就是两个三维偏序。但注意到这种情况已经被上一种包含,且被减去了三次,需要在加回去两次。

那么最后的答案就为 \(n+C_n^2+C_n^3-\sum_{i=1}^n x_i-\sum_{i=1}^n (C_{y_i}^2+C_{z_i}^2+C_{w_i}^2)+2\sum_{i=1}^n C_{x_i}^2\)。

标签:cnt,20241002,max,sum,贡献,枚举,三元组,模拟
From: https://www.cnblogs.com/luyuyang/p/18535166

相关文章

  • 20240928 模拟赛
    20240928模拟赛Agenius将模运算转化,\(\sum_{i=1}^{n}a_i\bmodk=\sum_{i=1}^{n}(a_i-\lfloor\frac{a_i}{k}\rfloor\timesk)=sum-k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor=s\)。移项得到\(sum-s=k\sum_{i=1}^n\lfloor\frac{a_i}{k}\rfloor\)。于是\(sum-s\)是......
  • 20240925 模拟赛
    20240925模拟赛Apow显然如果出现了\(1\),那么\(1\)和后面的数都没用了。于是剩下的数不小于\(2\)。考虑\(3\)个数的情况,只有\(a^{(b^c)}\)和\((a^b)^c\)两种情况。第二中等价于\(a^{bc}\),注意到当\(b,c\geq2\)时\(b^c\geqbc\),于是第一种情况一定不优,所以直接......
  • 20240918 模拟赛
    20240918模拟赛AStringBPack看这个数据范围很容易想到dp,设\(f_{i,,j,k}\)(pair<int,int>)表示前\(i\)个物品,拿走\(j\)个\(1\),\(k\)个\(2\)所用的最少车数,以及最后一辆车所用的最少空间。转移分当前这个拿不拿掉讨论,非常显然。最后枚举总共拿了几个\(1\)和几个......
  • 20240914 模拟赛
    20240914模拟赛A开挂(openhook)可以发现结果序列是能确定的,而且我们并不关心具体对哪个数进行操作,有用的信息只有操作次数,从而可以得到一个数组\(c\)表示对某个数操作了某个次数。设对\(tot\)个数进行了操作,将\(c\)从小到大排序,将\(b\)中的前\(tot\)小从大到小排序,于......
  • Chromium 进程降权和提权模拟示例c++
     一、背景知识概念参考微软链接:强制完整性控制-Win32应用程序|Microsoft学习授权)(模拟级别-Win32apps|MicrosoftLearnDuplicateTokenEx函数(securitybaseapi.h)-Win32apps|MicrosoftLearn本文主要演示 low,medium,high,andsystem四种权限创建......
  • C++:模拟实现STL的list
    目录一.list类1.list的创建节点2.list迭代器的运算符操作3.list的构造函数及析构4.list的迭代器5.list的插入及删除二.整体代码1.list.h2.list.cpp在上一节已经了解list在库中的用法,在这里实现list的底层逻辑一.list类1.list的创建节点template<classT>struc......
  • [赛记] NOIP2024加赛1 && 多校A层冲刺NOIP2024模拟赛18
    暴力错解大赛玩游戏82pts乱糊的错解,正确性和时间复杂度都不对,但是拿了82pts;对于正解,考虑从$k$将原序列分成两个部分,左边和右边,然后分别求一次前缀和(注意这里,可以省去很多分讨和常数),设前一个前缀和数组为$a$,后一个为$b$,那么问题就转化成有两个指针$i,j$,可以任......
  • NOIP 模拟 7
    T1图书管理(book)考虑每个数做中位数的贡献,经典trick就是小于的为\(-1\),大于的为\(1\),前缀和相减为\(0\)的就合法,不会链表。T2两棵树(tree)又是经典trick,森林的连通块数为点数减边数,证明就是算树的数量,好像之前见过这个trick。然后把贡献拆开,\(e\)代表点,\(v\)代......
  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19其实不太想写博客,但还是从今天开始坚持写吧。T1图书管理对于这种一边大一边小的问题,一般套路是大的设为$1$,小的设为$-1$,这道题也是,这样之后去扫一遍,两端的前缀和值一样即可。T2两棵树新学到的一个重要$trick$是:$$连通块的个数......
  • C# 队列的一些并发模拟
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Threading;usingSystem.Collections.Concurrent;namespace......