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

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

时间:2023-08-07 19:13:31浏览次数:38  
标签:题解 复杂度 T2 T3 2023 创杯

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

小学组

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)→(x, y)
和 (x, y)→(n, n)
的最短路 单次询问简单讨论一下 O(n)
是容易的。
总时间复杂度 O(n^2 + min(n, q)n)
,即 O(n^2)

T4 stone

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

对于每一轮从 x
出发:
先假装每个点 i
的负贡献是 | x ? i | ×a i
然后每次向左 / 右选的贡献就是一个前缀 / 后缀和的形式。于是可以直接贪心,复杂度 O(n(r ? l))。(假的假的,我若治了 / ll)
因为数据随机,所以相邻的轮的贡献可能很快就会到达相同的状态 (l, r)
,感觉上直接加个记忆化就能过。

鲜花

初中组 T2 放过 O(n 2 logn)!!!

T3 边权随机并放过小常数 O(n 2 + qn)

水老师实乃良心出题人!!!

点个赞再走吧!!!

标签:题解,复杂度,T2,T3,2023,创杯
From: https://www.cnblogs.com/niuzeyu1/p/17612473.html

相关文章

  • 打开电脑中应用程序及问题解决方案
    1、使用os.system()函数:示例代码importosos.system("notepad.exe")这将在Windows系统上打开记事本应用程序。2、使用subprocess示例代码:importsubprocesssubprocess.Popen(['notepad.exe'])3、使用webbrowser示例代码:importwebbrowserwebbrowser.open('http://www.goog......
  • 【题解】 Pattern Matching in A Minor "Low Space" CCPC Mianyang 2022
    https://vjudge.net/contest/573644#problem/K字符串匹配,但卡空间。考虑哈希做法,不妨把\(s\)每\(20000\)个字符哈希成一个字符,于是\(s\)长度只有\(500\),可以跑个KMP。于是对于\(t\),我们只需要同时维护\(20000\)个KMP的指针。但如果字符串长度不是\(20000\)的倍......
  • Photoshop 2023 for mac(ps 2023 ai beta)v25.0beta中文版
    Photoshop 2023mac更新了,智能AI在ps 2023beta版上线了。ps2023更新内容有内置AI绘图、有实时渐变、生成填充等功能,还支持神经滤镜,帮你打造更加强大的创作。ps2023mac中文版系统要求•需要macOS11或更高版本•Intel或AppleSilicon•8GBRAM(推荐16GB)•4GB可用硬......
  • OWASP-Top-10-for-LLMs-2023
    一、LLM01:PromptInjection0x1:攻击原理这通过特殊构造的输入来污染/覆盖prompt提示,以此攻击一个大型语言模型(LLM),使其产生非预期的意外行为。提示注入漏洞(PromptInjectionVulnerability)是指攻击者通过精心构造的输入,操控一个大型语言模型(LLM),使得LLM在不知情的情况下执行攻......
  • 2023年8月最新全国省市区县和乡镇街道行政区划矢量边界坐标经纬度地图数据 shp geojso
    发现个可以免费下载全国 geojson 数据的网站,推荐一下。支持全国、省级、市级、区/县级、街道/乡镇级以及各级的联动数据,支持导入矢量地图渲染框架中使用,例如:D3、Echarts等geojson数据下载地址:https://geojson.hxkj.vip该项目github地址:https://github.com/TangSY/echarts-m......
  • 2023/08/07
    每次游戏玩家会拿到一张彩票,上面会有9个数字,分别为数字1到数字9,数字各不重复,并以3×3的“九宫格”形式排布在彩票上。在游戏开始时能看见一个位置上的数字,其他位置上的数字均不可见。你可以选择三个位置的数字刮开,这样玩家就能看见四个位置上的数字了。最后玩家再从3......
  • 2023.8 模拟赛日志
    2023暑假集训ab班day1127round。预期:\(0+25+0=25\)实际:\(80+20+0=100\)题目:23ab-day1划(待写)不会做,搞了很久最后逐一假掉。竟然有分。题解是一些恶心的区间分类,比较简单,可惜了。好像有很多做法23ab-day1Heinrich树论科技,跳过。写了暴力换根。23ab-day1朝花夕拾......
  • P9498 「RiOI-2」equals题解
    题目传送门:P9498「RiOI-2」equals-洛谷|计算机科学教育新生态(luogu.com.cn)这是洛谷月赛Div.2T3,由于我比较菜,只能赛场上切到T3(T4是黑。),开题我们很容易就看出这道题首先需要初始化每个点到根节点的最短路,而且边权都为1,所以我们先无脑打一个堆优化的dijkstra,剩下的就是处......
  • P1005 [NOIP2007 提高组] 矩阵取数游戏题解
    题面传送门:P1005[NOIP2007提高组]矩阵取数游戏-洛谷|计算机科学教育新生态(luogu.com.cn)分析题目可知,这道题是一道求最值的问题,第一次看题没有认真读题,以为是每次只在某一行中选一个数,于是想了半天无果。重新读题才发现每次需要每行都取,那么这就很简单了,相当于在每一行......
  • 洛谷 P1336 最佳课题选择 题解
    P1336最佳课题选择题解状态:考虑\(f_{i,j}\)表示前\(i\)种论文里面,一共写了\(j\)篇,的最少花费时间。转移策略:我们一次考虑每一种论文写多少篇。假设写\(k\)篇,\(k\in[0,j]\cap\mathbb{Z}\),有转移方程:\[f_{i,j}=min(f_{i-1,j-k}+cost(i,k)),k\in[0,j]\cap\mathbb{......