2019暑期acm训练日记

专题计划:lyd的专题练习题+kuangbin专题

然而队友让我做数学,我太难了


7.7

  • 基本算法

    0802 占卜DIY (模拟)

    POJ2083 Fractal (dfs)

    POJ3714 Raid (水题)

    0805 防线(秦腾与教学评估) (二分答案)

    0807 糖果传递 (贪心+中位数性质)

    POJ1723 Soldiers (构造+中位数性质)

    POJ1220 Number Base Conversion (任意进制高精度转换)

    POJ1050 To the Max (dp最大子矩阵和)

7.8

  • 基本数据结构

    1801 括号画家 (栈+模拟)

    1802 表达式计算4 (表达式计算+中缀转后缀)

    1803 City Game (降维+单调栈)

    POJ1193 内存分配 (链表+堆)

    1806 Matrix (二维hash)

    POJ1635 Subway Tree Systems (树的hash/树的最小表示法)

    1807 Necklace (最小表示法)

7.9

  • 基本数据结构

    1808 Milking Grid (KMP next数组的性质+hash)

    1809 匹配统计 (KMP灵活运用)

    POJ3630 Phone List (字典树)

    POJ1442 Black Box (对顶堆)

    1812 生日礼物 (贪心+链表+优先队列)

    1813 双栈排序 (二分图染色+模拟)

7.11

  • 搜索

    2901 靶形数独 (dfs+回溯+剪枝)

    2902 虫食算 (dfs+回溯+剪枝)

    2903 Mayan游戏 (dfs+剪枝)

    POJ1167 The Buses (dfs+回溯+剪枝)

7.12

  • 数论

    Gcd HYSBZ - 2818 (线性筛+欧拉函数+前缀和)

    Longge’s problem POJ - 2480 (素数筛+因子分解+积性函数+欧拉函数)

7.13

  • 数论

    青蛙的约会 POJ - 1061 (拓展欧几里得)

    TYVJ1339 (找不到题)

    计算器 HYSBZ - 2242 (快速幂+线性同余方程+高次同余方程)

    Matrix Power Series POJ - 3233 (矩阵快速幂+二分)

    233 Matrix HDU - 5015 (构造+矩阵快速幂)

    Widget Factory POJ - 2947 (线性同余方程组+高斯消元)

7.14

  • 数论

    Xor HYSBZ - 2115 (线性基+异或性质+dfs生成树)

    新Nim游戏 HYSBZ - 3105 (贪心+线性基)

    Strange Way to Express Integers POJ - 2891 (中国剩余定理)

  • 牛客吉首大学2019年程序设计竞赛(重现赛)

    E、G、H 3道水题

7.15

  • 数论

    排列计数 HYSBZ - 4517 (逆元+错排公式)(未提交)

    Sky Code POJ - 3904 (容斥+二进制)(容斥+莫比乌斯反演)

    TYVJ1864 (找不到题)

  • 搜索

    Missile Defence System POJ - 3700 (dfs+迭代加深)

    CODEVS1411 (找不到题)

    TYVJ1030 (找不到题)

    CODEVS1099 (找不到题)

    Weather Forecast POJ - 2044 (bfs/dfs)

7.16

  • 数论

    换教室 HYSBZ - 4720 (概率dp+最短路)

7.17

  • 数论

    Dropping tests POJ - 2976 (01分数规划)

    TYVJ2049 (找不到题)

    Georgia and Bob POJ - 1704 (阶梯博弈)

  • 数据结构进阶

    CODEVS1069 (找不到题)

    Rochambeau POJ - 2912 (带权并查集)

    True Liars POJ - 1417 (带权并查集+背包)

7.18

  • 牛客多校1 (3/10,263/975)

    A. Equivalent Prefixes

    F. Random Point in Triangle

    J. Fraction Comparision

    补题:

    B. Integration

    知识库拓展:

    1.信号与系统里的的拆项法

    2.三角形重心3等分/6等分面积,2:1划分中线

    3.三角形由三点坐标计算面积公式:

    S=abs(x[1]*(y[2]-y[3])+x[2]*(y[3]-y[1])+x[3]*(y[1]-y[2]))/2;

  • 数据结构进阶

    Buy Tickets POJ - 2828 (逆向思维+树状数组+二分)

7.20

  • 牛客多校2 (1/10,365/765)

    H.Second Large Rectangle

    补题:

    F.Partition problem

7.22

  • 杭电多校1

    D. Vacation

    补题:

    B. Operation

    I. String

  • codeforces div2 (rating:2152,+3,1503)

7.23

  • 2019个人专题赛-第一场 (10/12,11/77)

    A. Beautiful Paintings

    B. Holiday Of Equality

    C. Fafa and his Company

    D. 宇航员

    E. Phone Numbers

    F. DDoS

    G. New Year and Counting Cards

    H. Lucky Year

    I. Diagonal Walking

    J. Adjacent Replacements

  • codeforces The 2019 University of Jordan Collegiate Programming Contest (组队练习,7/12)

7.24

  • 杭电多校2

    E. Everything Is Generated In Equal Probability

    J. Just Skip The Problem

    补题:

    K. Keen On Everything But Triangle

  • codeforces div3 (rating:306,+89,1592)

7.25

  • 牛客多校3 (2/10,186/865)

    B. Crazy Binary String

    H. Magic Line

    补题:

    D. Big Integer

    知识库拓展:

    1.同余乘法运算规律

    2.BSGS、拓展BSGS

7.26

  • 2019个人综合赛1 (7/10,2/75)

    A. Pretty Poem

    D. The Two Routes

    F. Sliding Window

    G. Thematic Contests

    H. Boredom

    I. You can Solve a Geometry Problem too

    J. Divide by three, multiply by two

    补题:

    B. Seating of Students

    C. hannnnah_j’s Biological Test

  • 权值线段树、主席树原理学习

7.27

  • 牛客多校4 (5/11,161/828)

    A. meeting

    C. sequence

    D. triples I

    J. free

    K. number

  • 主席树代码实现

7.28

  • FFT、NTT原理、代码实现

    A * B Problem Plus HDU - 1402 (FFT)

    Rikka with Subset HDU - 5829 (NTT)

7.29

  • 杭电多校3

    F. Fansblog

    G. Find the answer

  • FFT、NTT例题

    洛谷3803 (FFT)

    3-idiots HDU - 4609 (FFT)

7.30

  • 2019个人综合赛2 (6/10,4/74)

    A. Nauuo and Chess

    B. Sky Code

    D. Cinema

    E. Writing Code

    G. Constructing Roads

    I. The Labyrinth

7.31

  • 杭电多校4

    A. AND Minimum Spanning Tree

    G. Just an Old Puzzle

    补题:

    J. Minimal Power of Prime

    C. Divide the Stones

8.1

  • 牛客多校5 (2/10,395/840)

    A. digits 2

    G. subsequence 1

    补题:

    B. generator 1

    G. subsequence 1

8.2

  • 2019个人综合赛3 (5/10,8/71)

    D. Pair Of Lines (叉积)

    F. Mike and Shortcuts (bfs)

    G. Switches and Lamps (前缀和)

    H. Space Elevator (dp)

    J. Hello Kiki (拓展中国剩余定理)

    补题:

    A. Destroy Walls (最大生成树)

    B. Maximum Xor Secondary (单调栈)

    I. Ghd (随机化算法)

8.3

  • 牛客多校6 (3/10,262/829)

    A. Garbage Classification

    B. Shorten IPv6 Address (模拟)

    J. Upgrading Technology

    补题:

    D. Move (二分|暴力)

    知识库拓展:

    1.%x %X %04x %04X

    2.atoi() x=atoi(str);

    3.itoa() itoa(x,str,base);

    4.蔡勒公式

    c:世纪 (已过世纪,当前世纪-1,y/100)

    y:年 (公元后取后两位数,y%100,y-100*c)

    m:月 (1、2月份看作13、14,进位的话年份减1,m<=2?m+12,y–:m)

    d:日

    1582年10月4日之后

    1
    week = (( y + y/4 + c/4 - 2*c + 13*(m+1)/5 + d - 1 ) % 7 + 7 ) % 7;

    1582年10月4日或之前

    1
    week = (( y + y/4 + c/4 - 2*c + 13*(m+1)/5 + d + 2 ) % 7 + 7 ) % 7;

8.5

  • 杭电多校5

    E. permutation 1 (分类枚举)

    F. string matching (扩展KMP)

    G. permutation 2 (打表找规律)

    补题:

    D. equation (分类+前缀和)(还在蜜汁wa中)

8.6

  • 2019个人综合赛4 (3/10,7/67)

    D. Elections (贪心+暴力枚举)

    I. Reachability from the Capital (技巧dfs)

    J. John (Nim博弈)

    补题:

    B. Time to Raid Cowavans (分块)

    C. XOR and Favorite Number (莫队)

    G. Rotating Scoreboard (半平面交求多边形核)

    F. “Ray, Pass me the dishes!” (线段树)

8.7

  • 杭电多校6

    E. Snowy Smile (最大子矩阵和+线段树)

    H. TDL (构造+枚举)

    L. Stay Real (贪心)

    补题:

    B. Nonsense Time (逆向+最长上升子序列)

    注意点:

    1.最长上升子序列求得的dp[]并不是最终的LIS序列,需用一个pre记录每个值的前一个值,最后用最末尾的值回溯

8.8

  • 牛客多校7 (5/11,215/855)

    A. String (最小表示法)

    B. Irreducible Polynomial (多项式实数域约分)

    C. Governing sand (权值线段树)

    D. Number (水题,构造)

    J. A+B problem (水题)

8.9

  • 2019个人综合赛5 (5/10,5/65)

    B. Jamie and Binary Sequence (changed after round) (贪心+模拟)

    C. Desert King (01分数规划+最小生成树)

    E. Zuma (区间DP)

    G. How Many Pieces of Land ? (平面图欧拉定理+高精度)

    I. Selecting Courses (二分图匹配+匈牙利算法)

8.10

  • 牛客多校8 (4/10,178/796)

    A. All-one Matrices (悬线法)(单调栈+前缀和)

    B. Beauty Values (线性贡献+取补集)

    C. CDMA (构造+递归)

    G. Gemstones (栈)

8.12

  • 杭电多校7

    K. Kejin Player (期望)

8.13

  • 南京多校1

8.14

  • 杭电多校8

    I. Calabash and Landlord

    J. Quailty and CCPC

8.15

  • 牛客多校9 (3/10,217/711)

    B. Quadratic equation (解二次同余方程+二次剩余)

    D. Knapsack Cryptosystem (折半搜索)

    E. All men are brothers (容斥+并查集+树状数组)

    补题:

8.16

  • 南京多校2

    C. Sdl and Network Flows (单调栈)

    E. SDL’s Number (数学)

    F. Game (博弈)

    I. Sdl and Math Problem (二分)

    J. Sdl and McDonald’s (dp+线段树)

8.17

  • 牛客多校10 (4/10,180/744)

    B. Coffee Chicken (分治+递归)

    D. Han Xin and His Troops (中国剩余定理+大数)

    E. Hilbert Sort (递归+坐标变换)

    H. Stammering Chemists (水题)

    补题:

    F. Popping Balloons

8.19

  • 杭电多校9

    B. Rikka with Cake (树状数组+闭平面分割)

    E. Rikka with Game (博弈)

    F. Rikka with Coin (枚举)

    补题:

8.20

  • 摸鱼

    数论学习

    python入门

    QT开发

8.21

  • 杭电多校10

    C. Valentine’s Day (贪心)

    E. Welcome Party

    I. Block Breaker (dfs)

  • FWT学习

8.22

  • 摸鱼

8.23

  • CCPC网络赛 (5,11,2/21)

    A. ^&^ (构造)

    C. K-th occurrence (后缀数组+主席树)

    F. Shuffle Card (逆向)

    G. Windows Of CCPC (递归)

    H. Fishing Master (贪心)

8.24

  • 开学了,结束