IOI2020 国家集训队作业 Part 1

发布时间 2023-10-23 19:39:32作者: 樱雪喵

日期不对,但要保证顺序正确方便查找少了啥题。
计算几何和实在不会的题没写。

9.20

CF504E Misha and LCP on Tree
*3000 二分,hash,树剖

CF505E Mr. Kitayuta vs. Bamboos
*2900 二分,堆,时间倒流

9.21

CF506E Mr. Kitayuta's Gift
*3000 矩阵乘法,DP,自动机,字符串
你管这叫 *3000?

CF512D Fox And Travelling
*2900 DP,树上背包,组合计数,拓扑排序

CF516D Drazil and Morning Exercise
*2800 树的直径,双指针,并查集

CF516E Drazil and His Happy Friends
*3100 同余最短路,exgcd,优化建图

CF521D Shop
*2800 贪心

CF521E Cycling City
*3100 构造,dfs 生成树,树上差分

CF526F Pudding Monsters
*3000 线段树,单调栈,连续段计数

9.25

CF526G Spiders Evil Plan
*3300 树的直径,长链剖分,倍增

CF527E Data Center Drama
*2600 欧拉回路,构造

CF536D Tavas in Kansas
*2900 博弈论,dp,最短路

CF538H Summer Dichotomy
*3200 贪心,二分图

CF547D Mike and Fish
*2600 欧拉回路,二分图

CF547E Mike and Friends
*2800 ACAM,BIT

CF555E Case of Computer Network
*2800 边双连通分量,树上差分,lca

10.2

CF559E Gerald and Path
*3000 dp

CF566C Logistical Questions
*3000 数学(导数),点分治

CF566E Restoring Map
*3200 构造,树,bitset

CF568E Longest Increasing Subsequence
*3000 构造,dp,LIS

CF571D Campus
*3100 并查集,二分

CF573E Bear and Bowling
*3200 分块/平衡树 优化 dp

10.6

CF575A Fibonotci
*2700 矩乘,线段树

CF575I Robots protection
*2800 二维树状数组

CF576D Flights for Regular Customers
*2700 矩乘,dp,最短路

CF576E Painting Edges
*3300 线段树分治,扩展域并查集

10.7

CF578E Walking!
*2700 构造,贪心

CF578F Mirror Box
*3200 Matrix-Tree 定理

CF582D Number of Binominal Coefficients
*3300 数位 dp,库默尔定理

CF582E Boolean Function
*3000 表达式树,状压 dp,FWT

10.8

CF585E Present for Vitalik the Philatelist
*2900 莫反,容斥

CF585F Digits of Number Pi
*3200 SAM,数位 dp

10.12

CF587D Duff in Mafia
*3100 2-SAT 的前缀优化建图,二分

10.13

CF587F Duff is Mad
*3000 ACAM,BIT,根号分治

CF590E Birthday
*3200 ACAM,最长反链,二分图匹配

10.14

CF603E Pastoral Oddities
*3000 线段树分治,kruskal

CF605E Intergalaxy Trips
*2700 期望 dp,最短路

10.16

CF611H New Year and Forgotten Tree
*3200 Hall 定理,构造

10.17

CF613E Puzzle Lover
*3200 DP,hash

CF626G Raffles
*3100 期望,贪心,set

CF627F Island Puzzle
*3400 构造