首页 > 其他分享 >NOIP2023模拟13联测34 总结

NOIP2023模拟13联测34 总结

时间:2023-11-07 22:24:50浏览次数:35  
标签:13 题目 sum 34 大意 联测 区间 NOIP2023

NOIP2023模拟13联测34 总结

目录

比赛过程

看了一下题,感觉就 \(T2\) 有一点思路。

\(T1\) 先打一个 \(30\) 分暴力,感觉要分位考虑,想了大概 \(1h\) 就跳了。

\(T2\) 想到了先求出整个区间的长度乘上包含这个区间的总数再减去重复算的,想了很久,只会相邻的,只好打个暴力,发现线段树超时,加上离散化又挂了,于是调了好久都没调出来。只好跳了

\(T3\) 赶紧打个暴力

\(T4\) 检查了前 \(3\) 题代码后没什么时间了,题也没看懂

题目

A. origen

题目大意

给定 \(n\) 个整数 \(a_1,a_2,a_3\cdots a_n\) ,求

\[\sum_{i = 1}^n\sum_{j = i}^n(\oplus_{k = i}^ja_k)^2 \mod 998244353 \]

\(n\le 2 * 10^5 , 0\le a_i \le 2 * 10 ^5\)

思路

设 \(s_i = \oplus_{j = 1}^i a_j\) ,则原式变为:

\[\sum_{i = 0}^{n - 1} \sum_{j = 1}^n (s_i \oplus s_j)^2 \]

按位考虑,一个数可以用二次幂的和来表示。考虑怎么处理平方。

因为:

\[(\sum_{i = 1}^n a_i)^2 = \sum_{i = 1}^i a_i^2+ 2\sum_{i = 1}^{n - 1}\sum_{j = i +1}^n a_i*a_j \]

把两部分分开处理。

先处理前面的那项

把 \(i\) 的每一位分开求贡献,当前处理到第 \(j\) 位

设前 \(i - 1\) 个数这一位为 \(0\) 的数有 \(s0\) 个,为 \(1\) 的数有 \(s1\) 个

那么求这一位的贡献

  • 若当前这一位为 \(1\) :\(2^j*2*s0\)
  • 若当前这一位为 \(0\) :\(2^j*2*s1\)

然后处理后面的那项

先枚举两位 \(j1 , j2\)

当前处理到第 \(i\) 位

设 \(sum_{k , l}\) 为前面 \(i - 1\) 个数的第 \(j1\) 位为 \(k\) ,第 \(j2\) 位为 \(l\) 的个数

设第 \(i\) 个数这两位分别是 \(x , y\)

那么这里的贡献为:\(2 *2^{j1} * 2^{j2} *sum_{!x , !y}\)

B.competition

题目大意

现在有 \(n\) 个区间 \([l_i , r_i]\) ,现在问你选取若干的连续的区间的区间并的大小的和。

思路

设 \(pre_{i , j}\) 表示前 \(i - 1\) 个区间内,包含点 \(j\) 的最靠右的数是多少。

可以发现答案就是

\[\sum_{i = 1}^n (r_i - l_i +1) * i * (n - i + 1) - pre_{i , j} * (n - i +1) \]

也就是这个区间被记入答案的次数乘上区间的大小再减去重复的次数

可以用一棵线段树维护加离散化来维护。

先统计答案,然后用线段树更新 \(pre\)

要卡常

C. tour

题目大意

有 \(n\) 个城市,每个城市有一个文化值 \(val_i\)

接下来有两种操作

  • 0 x y

    表示城市 \(x\) 和城市 \(y\) 之间建立一条无向边 (保证修建前 \(x\) 和 \(y\) 不连通)

  • 1 x y

​ 代表有一个人,初始时他的文化值为 \(0\) ,他会从 \(x\) 走到 \(y\) (保证此时 \(x\) 与 \(y\) 连通),每走到一个城 市 \(i\),他会与这个城市进行文化交流,如果此时他的文化值大于等于 \(val_i\) ,那么这次文化交流是 成功的。无论文化交流结果如何,在此之后,他的文化值会加上 \(val_i\) 。求出成功的文化交流的次数。

D.abstract

题目大意

定义函数 \(f(i , j) , g(i , j)\) ,分别表示 \(i\to j\) 的权值和权值或,想要求出 \(\sum_{i = 1}^n\sum_{j = 1}^n f(i , j) ^{g(i , j)}\)

把 $f(i , j) , g(i , j) $ 放到 \(i\to j\) 的简单路径上的点权和点权或

输出答案 \(\mod 111121\)

定义:\(0^0 = 0\)

标签:13,题目,sum,34,大意,联测,区间,NOIP2023
From: https://www.cnblogs.com/2020fengziyang/p/17816179.html

相关文章

  • 实验三_OOP_张文瑞_202213260018
    任务1源代码:11#pragmaonce2233#include<iostream>44usingstd::cout;55usingstd::endl;6677classPoint{88public:99Point(intx0=0,inty0=0);1010~Point()=default;11111212intget_x()......
  • NOIP2023模拟13联测34 B.competition
    NOIP2023模拟13联测34B.competition目录NOIP2023模拟13联测34B.competition题目大意思路code题目大意现在有\(n\)个区间\([l_i,r_i]\),现在问你选取若干的连续的区间的区间并的大小的和。思路设\(pre_{i,j}\)表示前\(i-1\)个区间内,包含点\(j\)的最靠右的......
  • NOIP2023模拟13联测34 A. origen
    NOIP2023模拟13联测34A.origen目录NOIP2023模拟13联测34A.origen题目大意思路code题目大意给定\(n\)个整数\(a_1,a_2,a_3\cdotsa_n\),求\[\sum_{i=1}^n\sum_{j=i}^n(\oplus_{k=i}^ja_k)^2\mod998244353\]\(n\le2*10^5,0\lea_i\le2*10^5\)思路设......
  • NOIP2023模拟8联测29 总结
    NOIP2023模拟8联测29总结题目T1集合大意给出一个序列\(S\),找出有多少个区间\([L,R]\),使得\([L,R]\)值域的连续长度不超过\(k\)。\(n\leq2*10^5,k\leqn\)赛时思路对于区间\([L,R]\),如果有\([L',R']\)符合答案(\(R'\leqR\)且\(L\leqL'\)),那么区间\([L,R']\)......
  • NOIP2023模拟9联测30 总结
    NOIP2023模拟9联测30总结题目T1上海大意判断是否存在\(n\)正整数,使得\(n^2\)是\(k\)的倍数,且\(n\)不是\(k\)的倍数。如果存在,输出最小的\(n\);不存在输出\(-1\)。\(k\leq10^{12}\)赛时思路对于\(n\)来说,\(n\)一定要包含\(k\)有的质因数,而且\(n\)不......
  • NOIP2023模拟9联测32 总结
    NOIP2023模拟9联测32总结题目T1花菖蒲大意构造一个一度点数等于\(a\),二度点数等于\(b\),总点数小于\(2000\)的树。\(a,b\leq200\)赛时思路构造一条链,去除首位后有\(b\)个节点,这\(b\)个节点接一个一度点,加上首位两个一度点,如果一度点不够,那么将首部改造一个一度......
  • NOIP 模拟13(NOIP A层联测26)
    100+100+20+17,T3按理说应该想到考虑两部分分别的贡献的,明明这个套路很常见。5k:就喜欢这种数据结构专场,多来点。A.origen先前缀和,以下\(p_i\)表示前缀异或和。考虑将一个数\(k\)二进制差分,假设拆成\(2^a+2^b+2^c\),则\(k^2=(2^a+2^b+2^c)\times(2^a+2^b+2^c)\),也就是指数......
  • CF1359D Yet Another Yet Another Task
    貌似没有线段树做法。记\(s\)为\(a\)的前缀和数组。对于一个确定的右端点\(r\)和左端点\(l\),它对于答案的贡献是\(s_r-s_{l-1}-max\{a_i\},l\lei\ler\),如果枚举右端点,令\(c_l=s_{l-1}+max\{a_i\},l\lei\)。那么其实就是要求\(1\lek\ler-1\)的\(min\{c_k\}\)。线......
  • mac os13上安装apache\php\mysql
    macos13上安装1,下载并安装brew,brew是macos上的软件安装工具;2,安装apache2brewinstallhttpd 安装成功后提示:工程文件根目录DocumentRootis/usr/local/var/www配置文件Thedefaultportshavebeensetin/usr/local/etc/httpd/httpd.confto8080andin/usr/local/e......
  • [洛谷 P3481] [BZOJ1118] [POI2009] PRZ-Algorithm Speedup
    题目描述你需要计算一个函数\(F(x,y)\),其中\(x,y\)是两个正整数序列。boolF(std::vector<int>x,std::vector<int>y){if(W(x).size()!=W(y).size())returnfalse;if(W(x).size()==1)returntrue;returnF(p(x),p(y))&&F(s(x),s(y));}\(W......