首页 > 其他分享 >USACO24Bronze 游记兼 TJ All in Once

USACO24Bronze 游记兼 TJ All in Once

时间:2024-02-19 15:57:01浏览次数:36  
标签:10 普及 log 中位 T2 USACO24Bronze 流光 TJ Once

我没有其他组别的号了。所以只能写 Bronze 的游记了。

如果行的话,下一次我会写 Silver 的。

一开始看了看三道题,T1T2 感觉都很不可做,直奔 T3。

一看 T3(Bessie 很 nb,会各种各样的东西,会科学,会魔法,今天我们发现她会分身术),不就是个二分吗?秒杀。

好的,现在搞 T1T2,直接《男 左 女 右 我 选 左》,开了 T1。

T1 一看数据范围就知道这题不一般,得推,结果发现答案只与最后一位有关系,秒杀。

所以只有 T2 了。剩下的三个小时四十五分钟(是的,T1T3只用了 15 分钟)可以全部用来死磕 T2。

一开始毫无头绪,干脆写模拟,但是用模拟我发现过程是有一定规律的!

找到规律,\(O(M)\) 瞬间变成 \(O(N \log N)\),T2 搞定。

于是...就这样 AK 了...

附录:三道题 TJ

按照难易度从小到大排序。

T3

2~4

直接暴力。

\(O(NQ)\)。

5~9

想不出来。

AC

直接预处理出 Bessie 为了到达每一个农场她最晚要什么时候起来,然后排序 lower_bound 即可。

\(O(Q \log N)\)。

思维:普及-中位

代码:普及-下位

算法:普及-中位

无数据结构

综合:普及-中位

T1

直接想出了正解。

AC

本题有一个绝妙的性质,叫做:

对于一个数 \(x\),如果 \(10 \mid x\),则输出 E,否则输出 B

这玩意可以拆成两部分。

第一部分,如果 \(10 \mid x\),则输出 E

考虑数学归纳法。

首先 10 肯定成立。

\[\because x \ \text{is not palid} \]

\[\therefore \forall x \ \text{that is palid}, \ 10 \nmid x \]

\[\therefore 10a \to y \to 10b \quad (b \lt a) \]

所以成立。

第二部分也就很简单了:直接选取个位,坑死对方。

\(O(N)\)。

思维:普及-上位

代码:普及-下位

无算法

无数据结构

综合:普及-中位

T2

这个题我要精讲!

4~8

直接大模拟。

\(O(NM)\)。

AC

经典多解题。

首先建有向图。

解法一

Spetial Thank to appear_hope for this solution.

可以观察到除了环以外,每一个弱连通块每分钟会损失 1 单位牛奶。

直接计算。

\(O(\min(M, N))\)。

解法二

用模拟程序推出来的。

我们维护一个最终会流光的桶的集合,然后按照流光的时间从小到大选取。

对于一个流光的桶,被这个桶影响到的桶如果也会流光,那么也要将这个新桶加入集合。

\(O(\min(M, N \log N))\)。

标签:10,普及,log,中位,T2,USACO24Bronze,流光,TJ,Once
From: https://www.cnblogs.com/hhc0001deljbk/p/18021094

相关文章

  • FastJSON学习
    第一节:JSON数据格式回顾 JSON的数组格式:运行:结果:  JSON的对象格式:运行: 结果: ......
  • TJ -「HNOI2015」开店
    TJ-「HNOI2015」开店(洛谷)一,题意给你一棵\(n\)个节点的树,点有点权,边有边权,\(Q\)次询问每次让你求解点权在\(L\)到\(R\)之间的点到点\(u\)的距离和。(强制在线)数据范围:\(n\le1.5\times10^5,Q\le2\times10^5\)二,思路首先,我们先看弱化版,假设没有年龄的限制,看单个询问,设\(dis_i......
  • 第17天:信息打点-语言框架&开发组件&FastJson&Shiro&Log4j&SpringBoot等
    框架:简单代码的一个整合库,如果使用框架就只需要学习使用框架调用即可如:文件上传功能是需要很多代码来实现的,框架把这个代码进行封封装,调用即可影响:如果采用框架开发,代码的安全性是取决于框架的过滤机制 #Python-开发框架-Django&FlaskDjango1、识别插件2、Set-Cookie:expi......
  • ztjdtj.py
    代码片#-*-coding:utf-8-*-"""计算涨停价和跌停价,给定品种和昨天收盘价.Parameters----------lc:前收盘价,浮点数stype:整型,optional证券品种(0=可转债,1=股票).Thedefaultis0.Returns-------None.使用举例:%runztjdtj.py100#......
  • 洛谷 P3976 [TJOI2015] 旅游
    这出题人语言表达能力真的感人……希望你们看完这篇题解后不要觉得我的语言表达能力和出题人不相上下。题目大意给定一棵有点权的树,每次询问从\(u\)到\(v\)的路径上后经过的点权减去先经过的点权的最大值,再把这条路径上所有点的点权加上一个给定的数。分析俗话说得好:如果......
  • ExtJS 页面单文件
    更新记录2024年1月31日初始化。ExtJS教程汇总:https://www.cnblogs.com/cqpanda/p/16328016.html页面单文件写法ExtJS用官方脚手架(SenchaCMD)生成页面,在默认情况下会生成三个文件(View、ViewController、ViewModel)。有些时候为了方便可以直接像VueJS一样只定义一个文件,可......
  • fastjson 1268-jdbc
    1268-jdbc复现靶场项目是https://github.com/lemono0/FastJsonParty版本{"@type":"java.lang.AutoCloseable"回包:{"timestamp":"2024-01-31T09:45:27.342+0000","status":500,"error":"InternalS......
  • Vue模板语法——v-once 数据响应式
    一、数据响应式如何理解响应式html5中的响应式:屏幕尺寸的变化导致样式的变化数据的响应式:数据的变化导致页面内容的变化什么是数据绑定数据绑定:将数据填充到标签中v-once只编译一次显示内容之后不再具有响应式功能二、v-once指令v-once应用场景如果显示的......
  • TJ-CF1423K
    CF1423K首先,我们假设\(a>b\),设\(\gcd(a,b)=c,a=k_1\timesc,b=k_2\timesc\)则\(c\leb<a\)则是\(c,k_1,k_2\)构成一个三角形,且\(k_1>k_2(k_1>1)\)分类讨论:\(c\)为最大值\(c<k_1+k_2,c>k_1>k_2\)由于\(c,k_1,k_2\)都为正整数,也就是说只要\(c>2......
  • P3879 [TJOI2010] 阅读理解(水题)
    [TJOI2010]阅读理解题目描述英语老师留了N篇阅读理解作业,但是每篇英文短文都有很多生词需要查字典,为了节约时间,现在要做个统计,算一算某些生词都在哪几篇短文中出现过。输入格式第一行为整数N,表示短文篇数,其中每篇短文只含空格和小写字母。按下来的N行,每行描述一篇短文......