首页 > 其他分享 >『模拟赛』多校A层冲刺NOIP2024模拟赛16

『模拟赛』多校A层冲刺NOIP2024模拟赛16

时间:2024-10-31 18:22:27浏览次数:1  
标签:ch const 16 int ll 模拟 mathcal NOIP2024 define

Rank

依托,给我烂完了(

image

A. 四舍五入

唐题,赛时被硬控 3h。

发现枚举 \(i\) 是一个很没前途的选择,分成三段后仍然需要 \(\mathcal{O(n)}\) 去跑 \(\left[1,\lfloor{\frac{i}{2}}\rfloor\right]\) 这一段,复杂度仍是 \(\mathcal{O(n^2)}\) 的,只有 30pts。

正难则反,我们换个角度考虑枚举 \(j\),对于一个 \(j\) 而言,其有贡献的 \(i\) 的区间是固定的,我们可以记录这些区间,用差分的思路做,得出每个 \(i\) 的答案,但这样算会有调和级数 \(n\ln n\) 左右段区间,空间就炸了,因此直接记录在每个 \(i\) 上对后续产生的新贡献即可,这样空间就是线性的,时间复杂度是 \(\mathcal{O(n\ln n)}\)。注意区间的右端点不特殊处理的话最大会达到 \(2n\),空间要开大一倍。

ps:发现用逗号会比用分号慢 100ms 左右,望周知。

点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 2e6 + 5;
const int mod = 1e9 + 7;
int n, tot;
int a[N << 1];
namespace Wisadel
{
    short main()
    {
        freopen("count.in", "r", stdin), freopen("count.out", "w", stdout);
        n = qr;
        fo(i, 1, n) for(int l = 0; l <= n; l += i)
        {
            a[l]++;
            a[l + i / 2 + (i & 1)]--;
        }
        int now = 1, res = a[0];
        fo(i, 1, n)
        {
            res += a[i];
            printf("%d ", res);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 填算符

人类智慧思维题。

发现这 \(k\) 个 & 放到前 \(k\) 个空中一定能保证权值最大,因此 \(\mathcal{O(n^2)}\) 的思路很好出,我们双指针每次考虑 \(i\) 是否能替换 \(j\) 上的 &,判断标准直接 \(\mathcal{O(n)}\) 跑一遍算出结果比较即可。

发现我们做了巨大多次无用计算,考虑用 st 表优化。依旧是倒序考虑,考虑当前位 \(i\) 能否放置 &,只需要用 st 表求出 \(\left[1,i\right]\) 中前 \(j-1\) 个为 & 后面为 | 的值再 & 上当前值 \(a_{i+1}\),判断其能否满足当前的需求,需求初始为最大权值。若满足则直接将其入栈记录答案,否则该位上符号为 |,那么 \(a_{i+1}\) 一定对答案有贡献,我们的需求可以进一步降低为最大权值中 \(a_{i+1}\) 无法满足的,即二进制下一些最大权值为 1 而 \(a_{i+1}\) 不为 1 的数位的按位或和

感性理解下,就是我们现在需要满足一些条件,其中一些条件已经确定可以满足,那么前面只需满足其他的条件即可。

理解了这道题就做完了,复杂度主要是 st 表预处理的 \(\mathcal{O(n\log n)}\),双指针下判断可以 \(\mathcal{O(n)}\) 做。

点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, k;
int lg[N];
ll a[N], sta[30][N], sto[30][N];
bool yz[N];
stack<int> ans;
namespace Wisadel
{
    inline ll Wgta(int l, int r)
    {
        if(l > r) return 0;
        int d = lg[r - l + 1];
        return sta[d][l] & sta[d][r - (1 << d) + 1];
    }
    inline ll Wgto(int l, int r)
    {
        if(l > r) return 0;
        int d = lg[r - l + 1];
        return sto[d][l] | sto[d][r - (1 << d) + 1];
    }
    inline ll W(int l, int mi, int r)
    {
        if(mi + 2 > r) return 0;
        return Wgta(1, mi + 1) | Wgto(mi + 2, r);
    }
    short main()
    {
        freopen("bitop.in", "r", stdin), freopen("bitop.out", "w", stdout);
        n = qr, k = qr;
        fo(i, 1, n) sta[0][i] = sto[0][i] = a[i] = qr;
        fo(i, 2, n) lg[i] = lg[i >> 1] + 1;
        fo(i, 1, lg[n]) fo(j, 1, n - (1 << i) + 1)
            sta[i][j] = sta[i - 1][j] & sta[i - 1][j + (1 << (i - 1))],
            sto[i][j] = sto[i - 1][j] | sto[i - 1][j + (1 << (i - 1))];
        ll tot = W(1, k, n);
        int j = k;
        fu(i, n - 1, 1)
        {
            if(i <= j || !j) break;
            if(((W(1, j - 1, i) & a[i + 1]) & tot) == tot)
                ans.push(i), j--;
            else tot ^= (a[i + 1] & tot);
        }
        while(j) ans.push(j--);
        while(ans.size()) printf("%d ", ans.top()), ans.pop();
        puts("");
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 道路修建

比较困难的数据结构题。硬暴力有 10pts。

D. 逆序图

神秘题,暴力都不会打。

好烂的一场,开场切不出 T1 会无形带来巨大的压力,然后整场思维感觉都被冻住了,T1 T2 感觉都不算很难,但都只打了最低一档暴力分。

下午体育课,挥洒汗水后思维确实活跃了不少,鉴定为早上没跑操 + 没早读导致的(?)

出题人说上 100 没有 CSP-S 难(


完结撒花~

想什么呢

image

标签:ch,const,16,int,ll,模拟,mathcal,NOIP2024,define
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18518199

相关文章

  • 20241031模拟赛题解
    T1题目描述给定一个圆形蛋糕,被\(n\)条切割线分成\(n\)个扇形蛋糕块,按照顺时针编号,第\(i\)块上有\(a_i\)个草莓,第\(i\)条切割线到第\(i+1\)条切割线之间的部分是第\(i\)块蛋糕。Alice和Bob流选择切割线,假设Alice选择了第\(i\)条切割线,Bob选择了第\(j\)条......
  • 模拟用户登录网站
    模拟用户登录网站requests模块Requests继承了urllib2的所有特性。Requests支持HTTP连接保持和连接池,支持使用cookie保持会话,支持文件上传,支持自动确定响应内容的编码,支持国际化的URL和POST数据自动编码。requests的底层实现其实就是urllib3Requests的文档非常完备,中文......
  • NOIP 模拟赛:2024-10-28
    T1:给定两个数组\(a,b\),要求将\(b\)重排,使得\(b>a\)的位置个数最多,在此基础上最大化\(b\)的字典序。\(n\le5000\)。最多的位置个数是容易求的,排个序即可。如何最大化字典序?依次枚举\(i=1\simn\),然后从大到小枚举\(j\)看看\(b_i=j\)是否可以让后面依然保持大于位......
  • AP5216 是一款 PWM工作模式, 高效率、外围简单、内置功率管,适用于5V~100V输入的高精度
    产品描述AP5216是一款PWM工作模式,高效率、外围简单、内置功率管,适用于5V~100V输入的高精度降压LED恒流驱动芯片。输出最大功率可达9W,最大电流1.0A。AP5216可实现全亮/半亮功能切换,通过MODE切换:全亮/半亮模式。AP5216工作频率固定在130KHZ,同时内置抖频电路,可以降低......
  • AP5165B芯片
    产品描述AP5165B是一款外围电路简单的连续电流模式的降压型LED恒流驱动芯片。在输入电压高于LED电压时,可以有效地用于驱动一颗或者多颗串联LED。输出电流可调,最大可达1A。适用于3-36V电压范围的非隔离式恒流LED驱动领域。AP5165B内置功率开关和一个高端电流检测电路,可......
  • Leetcode每日一题 3216. 交换后字典序最小的字符串
    Leetcode每日一题##3216.交换后字典序最小的字符串###C++给你一个仅由数字组成的字符串s,在最多交换一次相邻且具有相同奇偶性的数字后,返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数,则它们具有相同的奇偶性。例如,5和9、2和4奇偶性相同,而......
  • 016_HBase
    1HBase分布式介绍分布式用户​ 使用负载均衡,把请求分发给不同的服务器。​ redis16384​负载均衡器​​ session共享​ 向session放入数据​ SESSION共享内存。checkServer-redis​ RPC协议=》RMI》EJB=》Spring框架分布式系统​ 将服务器拆分。​ 多台电脑,多......
  • 【10-31模拟赛T1】四舍五入
    给出\(n\),对于任意正整数\(i\)满足\(1\leqi\leqn\),求有多少个正整数\(j\)满足\(1\leqj\leqn\)且\(i\bmodj\leq\frac{j}{2}\)。枚举\(i\)不好处理,可以反过来,外层枚举\(j\),内层枚举左右端点\(l=kj,r=kj+\lfloor\frac{j}{2}\rfloor\)(\(k\)为自然......
  • Leetcode刷题Python之3165.不包含相邻元素的子序列的最大和
    提示:利用线段树解决不包含相邻元素的子序列最大和问题。文章目录一、题目描述示例二、解题思路1.思路分析2.线段树的状态设计3.线段树的操作三、代码实现代码详细解释四、总结时间复杂度分析一、题目描述给定一个整数数组nums和一个二维数组queries,其中q......
  • 模拟信号和数字信号之间的区别
    ​​模拟信号和数字信号之间的区别:1.信号的表示方式;2.信号的处理和传输;3.抗干扰能力;4.存储和复制;5.应用场景。模拟信号和数字信号作为信息载体,在通信领域内扮演着核心角色。模拟信号以连续变化的方式表征信息,而数字信号则以离散数值形式存在。1.信号的表示方式模拟信号的连续......