首页 > 其他分享 >CSP2024-33

CSP2024-33

时间:2024-10-08 21:47:53浏览次数:7  
标签:lfloor le vert 33 sum CSP2024 ge bigg

2A

题意:给定一个01串,每次可以循环移动一个子串,求多少次操作使整串有序(升序)。

每次操作至多使极大全1段个数减一:111100001111 \(\to\) 000011111111

数一下一开始有多少全1段,判断一下最后一个元素是否是1即可。submission

A

题意:给定 \(n, m, a, b, k\),求满足 \(ax + by = k,\ x, y \ge 0\) 的 \(n + m - (x + y) \times \min(\lfloor\frac{n}{x}\rfloor,\ \lfloor\frac{m}{y}\rfloor)\) 最小值。

数据范围:\(1 \le n, m, a, b, k \le 10^9\)。

exgcd 求出一组 \((X, Y)\),其他可用 \((X + k\Delta x,\ Y - k\Delta y)\) 表示。

枚举 \(O(\sqrt n)\) 种不同的 \(\min(\lfloor\frac{n}{x}\rfloor,\ \lfloor\frac{m}{y}\rfloor)\),容易求出 \(\max(x + y) = X + Y + k(\Delta x - \Delta y)\)。submission

B

题意:

C

题意:定义一个序列的权值为每个数依次拼接后数的大小。

构造一个 \(a_i \in [0, 9]\) 的序列,使得他所有最长严格上升子序列的权值和等于 \(c\),\(0 \le c \le 10^{13}, \ \vert a\vert \le 500\)。


如果 \(c\) 足够大,可以用 \(56789a + 01234b\) 表示(两数互质),令 \(b < 56789\)。

构造形如 [5...9][0...4] 的数列,使得 LIS 为 \(5\),且只存在 \(56789\) 和 \(01234\) 两种形式。

两部分显然是独立的,只讨论前一部分,用 \(0 \sim 4\) 对应 \(5 \sim 9\)。

在 \(k\) 进制下进行构造,满足 \(k^5\) 足够大。

设最大的 \(i\) 满足 \(\sum_{j = 0}^{i - 1}k^{j} \le a\),则剩下的 \(a - \sum_{j = 0}^{i - 1}k^{j}\) 可被 \(k\) 进制表示为 \(\sum_{j = 1}^i x_jk^{i - j}\),保证 \(i \le 5\)。

构造:\(\bigg\vert 012\cdots i\bigg\vert + \bigg\vert i^{x_i} + (i -1)^{x_{i - 1}} + \cdots + 1^{x1}\bigg\vert + \bigg\vert 2^k + \cdots + i^{k}\bigg\vert + \bigg\vert(i + 1) + (i + 2) + \cdots + 4\bigg\vert\)。

上标表示这个串重复出现次数,加法表示拼接。

\([i + 1, 4]\) 的部分唯一确定,对前三段进行计数。

假设选了 \(\text{I}\) 的一个前缀 \([0, j]\),若 \(j + 1\) 出现在 \(\text{II}\),则方案数为 \(x_{j + 1} \times k^{i - j - 1}\);否则方案数为 \(k^{i - j}\)。

那么总方案为:

\[\sum_{j = 0}^{i - 1} x_{j + 1}\times k^{i - j - 1} + \sum_{j = 1}^i k^{i - j} = a \]

上述构造最坏情况下(\(i = 5,\ x_j = k - 1\))有长度 \(9k\)。

满足 \(56789a \le 10^{13}\land \sum_{i = 0}^5 k^i > a\) 的最小 \(k\) 为 \(45\);满足 \(b < 56789\land \sum_{i = 0}^5 k^i > b\) 的最小 \(k\) 为 \(9\)。

\(9 \times (45 + 9) < 500\),满足限制。

哪些数一定存在一组非负整数解 \((a, b)\) 呢?

考虑 \(56789k \equiv i \pmod {1234}\),对于每个 \(i\) 求出最小 \(k\),所有与 \(i\) 同余的数都能在这基础上累加 \(1234\) 得到。

即 \(c \ge 56788 k_i\) 一定有解。

\(k\) 有最大值 \(1233\),因此 \(c \ge 700208374\) 一定能用上述方式构造。


否则令 \(c = 789a + 256b\),满足两数互质。

沿用类似的方式,可以每部分构造出上界为 \(4k\) 的序列。

满足 \(789a \le 700208374\land \sum_{i = 0}^3 k^i > a\) 的最小 \(k\) 为 \(96\);满足 \(b < 789\land \sum_{i = 0}^3 k^i > b\) 的最小 \(k\) 为 \(9\)。

最坏长度 \(4 \times(96 + 9) < 500\),满足限制。

同理对于 \(c\ge 201195\) 都能找到 \((a, b)\)。


令 \(c = 347a + 012b\),对应 \(k\) 为 \(8\) 和 \(7\),管辖 \(c \ge 3817\) 的范围。


构造序列 \(9^{\lfloor \frac{c}{9}\rfloor} + (c \bmod 9)\),长度不大于 \(425\)。

D

标签:lfloor,le,vert,33,sum,CSP2024,ge,bigg
From: https://www.cnblogs.com/Luxinze/p/18453076

相关文章

  • CSP2024 前集训:csp-s模拟10
    前言T2赛时不会,T3没有想到移项遂打了个背包得\(50pts\),T4又放回滚莫队板子,结过开太晚了没打完,以后板子麻烦放靠前点谢谢。T1需要线性基思想,听5k讲完貌似懂了,但是学了再回来补吧。T2首先选择一个度数不是\(1\)的点当根。对于一个非叶子节点\(p\)被扫到有两种情况......
  • 【孤岛划分】分布式能源接入弹性配电网模型研究【IEEE33节点】(Matlab代码实现)
      目录......
  • CSP2024 前集训:csp-s模拟9
    前言T1状压挂了\(10pts\),貌似做法是假的,但是一下午也没调出来哪儿假了,但是错误率很低,几百组能有一组错的。T2赛时数据锅了赛后重测了,赛时想到线段树但是没能具体实现,最后无奈写暴力。T3、T4没看。T1邻面合并\(m\le8\)所以考虑状压表示每一行哪些地方被覆盖,对与相邻两......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......
  • 虚拟机启动后ens33处于DOWN状态,无法远程连接
    平时用于学习和测试,在本地通过VMware部署了Ubuntu服务器,并配置了静态IP,方便远程连接。在某次启动虚拟机后,发现无法通过SSH连接。用ipaddr查看,发现ens33处于DOWN状态root@shawn-virtual-machine:~#ipaddr1:lo:<LOOPBACK,UP,LOWER_UP>mtu65536qdiscnoqueuestateUNKNOW......
  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19,\(30+20+40+15=105\)。T1构造字符串10pts:输出\(-1\)。30pts:对于所有\(z_i=0\)的情况,也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的,然后从\(1\)到\(n\)扫一遍,输出除去不同的字符之外的字典序最小的字符。70pts:暴搜。枚举每个......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • 永旺梦乐城盛大开业,3300个停车位的智慧运营管理系统上线!
    长沙首家!永旺梦乐城9月12日正式开业!这座融合特色餐饮、娱乐体验的商场,将为长沙消费者带来,超越传统商业综合体的全新体验。开业当日,占地1.3万平方米的永旺超市人声鼎沸,顾客络绎不绝,场面异常火爆。永旺梦乐城是亚洲最大的零售企业集团之一——日本永旺集团旗下核心企业,而......
  • CSP2024-S1游记
    额额,由于对自己水平极度自信,所以没怎么练初赛,只做了两张真题,教练一直叫我做NFLS的模拟题,我一个都没做好吧膜拜巨佬ydy,真的勇诶,直接不做(他把卡涂错了,最后61pts)初赛随便考考都能过吧听说这次CCF不仅把J组分线推上90的高位还泄题了,怎么出的卷啊话说回来,这次又是主场作战,所以在前一......
  • [题解][洛谷P1633] 二进制
    题目描述有三个整数A,B,C,构造三个整数X,Y,Z满足:1.A,B,C在二进制下1的数量分别与X,Y,Z相等;2.X,Y,Z在二进制下的长度不超过A,B,C的最大长度;3.X+Y=Z。输出Z的最小值,若不存在Z,输出-1。题意分析首先考虑X,Y在什么情况下会使1的数量发生改变。设x,y,z分别表示X,Y,Z中1的数量,则......