首页 > 其他分享 >“科大国创杯”2023 年安徽省青少年信息学科普日活动 简要题解

“科大国创杯”2023 年安徽省青少年信息学科普日活动 简要题解

时间:2023-04-09 16:56:01浏览次数:50  
标签:题解 复杂度 T2 T3 枚举 2023 初中 创杯 短路

老年退役选手感受单调队列力量。

初中组没有实现,如果有问题欢迎爆 d 我。

小学组

T1 grade

直接累加即可。不需要按百分比算(也就是别 /100),那样可能会出现一些浮点数误差。

T2 order

暴力枚举 $t$ 就可以了

T3 string

答案即为 $cnt4+cnt5-cnt20$。注意到对于一个数,我们只关心其个位和十位就可以判定了,然后就是 $O(n)$。

T4 hex

并查集维护连通性即可。注意如果不建虚点的话需要特判 $n=1$。

初中组

T1 score

和小学组一样,不做除法就可以了。

T2 count

排好序,枚举一个 $i$,然后枚举 $j$ 的时候 $k$ 尺取一下,时间复杂度 $O(n^2)$。

记得开 long long。

T3 walk

先找全局最短路。

如果询问边不在最短路上,直接输出全局最短路。

这样本质不同的询问个数就是 $O(n)$ 了。

然后可以预处理 $(1,1) \to (x,y)$ 和 $(x,y) \to (n,n)$ 的最短路 单次询问简单讨论一下 $O(n)$ 是容易的。

总时间复杂度 $O(n^2+\min(n,q)n)$,即 $O(n^2)$。

T4 stone

首先你考虑不依赖随机性质怎么做。

我对于每一轮从 $x$ 出发:

先假装每个点 $i$ 的负贡献是 $|x-i| \times a_i$。

然后每次向左/右选的贡献就是一个前缀/后缀和的形式。于是可以直接贪心,复杂度 $O(n(r-l))$。

因为数据随机,所以相邻的轮的贡献可能很快就会到达相同的状态 $(l,r)$,感觉上直接加个记忆化就能过。

鲜花

初中组 T2 放过 $O(n^2\log n)$,T3 边权随机并放过小常数 $O(n^2+qn)$,水老师实乃良心出题人!!!

标签:题解,复杂度,T2,T3,枚举,2023,初中,创杯,短路
From: https://www.cnblogs.com/DitaMirika/p/17300561.html

相关文章

  • element-ui按需使用-2023年
    element-ui按需引入报错Error:Cannotfindmodule‘babel-preset-es2015‘版本需要更新了下载babelnpmi@babel/preset-env-D 因为是使用es6编译,所以在babel.config.js中写成module.exports={presets:['@vue/cli-plugin-babel/preset',["@babel/preset-e......
  • JavaWeb-JSP-JSTL c foreach -2023-04-09
    <%@taglibprefix="c"uri="http://java.sun.com/jsp/jstl/core"%><%@pageimport="java.util.ArrayList"%><%@pagecontentType="text/html;charset=UTF-8"language="java"%><html>&l......
  • [省选联考 2023] 染色数组 题解
    题目描述给定一个长度为\(n\)的正整数数组\(A\),其中每个数都在\(1\)到\(m\)之间,从左到右排成一排。现在要将每个数字染成红色或者绿色,我们定义一个染色方案为优秀的染色方案,当且仅当它满足:每个数\(A_{i}\)要么被染成红色,要么被染成绿色。红色的数从左到右依次严格递......
  • JavaWeb-JSP JSTL标签 -2023-04-09
    <%--CreatedbyIntelliJIDEA.User:AdministratorDate:2023/4/9Time:15:10TochangethistemplateuseFile|Settings|FileTemplates.--%><%@pagecontentType="text/html;charset=UTF-8"language="java"%>&l......
  • 联合省选2023邮寄
    Day-INFNOIP诡异的地方写挂,导致在队线附近,省选压力其实很大。Day-7模拟赛一道网络流模型建错拿到了\(-1\)的\(5\)分,一道线段树写成分块T+Wa成\(0\)分,喜提倒一。但是可以和ducati一样的排名。Day-1找了个理由请假回家。早上去跑步,将四公里跑进了16min,比较开心。......
  • [省选联考 2023] 染色数组 题解
    题目描述给定一个长度为\(n\)的正整数数组\(A\),其中每个数都在\(1\)到\(m\)之间,从左到右排成一排。现在要将每个数字染成红色或者绿色,我们定义一个染色方案为优秀的染色方案,当且仅当它满足:每个数\(A_{i}\)要么被染成红色,要么被染成绿色。红色的数从左到右依次严格递......
  • 2023年了,为什么我们找工作更难了
    2020年的新冠疫情对整个世界都造成了极大的影响,软件测试行业也不例外。疫情期间,大多数公司都采取了远程办公的方式,这对于软件测试行业来说带来了一些挑战。然而,随着2023年的到来,疫情已经结束,为什么软件测试从业者找工作仍然这么难呢?以下是一些可能的原因。1.市场竞争激烈随着技术......
  • P2824 [HEOI2016/TJOI2016]排序 题解
    题目传送门前言线段树好题!!!!咕咕了挺久的一道题目,很早之前就想写了,今天终于找了个时间A掉了。题意给定一个\(1\)到\(n\)的排列,有\(m\)次操作,分两种类型。1.0lr表示将下标在\([l,r]\)区间中的数升序排序。2.1lr表示将下标在\([l,r]\)区间中的数降序排序。给......
  • ruoyi-cloud微服务版启动过程报错_20230320版_ Verion 9 of Highlight.js has reached
      Verion9ofHighlight.jshasreachedEOL. Itwillnolonger报错: 这里修改成10.7.3版本D:\2023\qdBigData\RuoYi-Cloud-master\ruoyi-ui>npminstall--registry=https://registry.npm.taobao.org然后到对应目录,再去执行编译去看看.不报错了 >npmrundev然后执行看......
  • 日常随笔2023.4.9
    #日常随笔2023.4.9​最近有些在脑海中有些许胡思乱想,我总是爱这样毫无边际的去幻想。这种行为是无法停止,所以倒不如尝试着回头去追忆自己想过的东西,一方面总结有用的经验,能加深自己的印象,另一方面,想和写是两码事情,想象可以没有逻辑,自由自在,但写作确实要讲究逻辑,不能任由散乱去......