Summary3-25模拟赛 Summary

3-25模拟赛 Summary

Process

三道题都只会暴力。一开始两个小时一直在想T3网络流如何建模,没想出来就都只有暴力分了

Score

30 + 35 + 20 = 85

Problems

arg

Description

给出一个长度为m的序列A, 请你求出有多少种1 …n的排列, 满足A是它的一个LIS

Solution

只会暴力

bsh

Description

给定一个正n边形及其三角剖分, 共2n−3条边 (n条多边形的边和n−3条对角线), 每条边的长度为1.
共q次询问, 每次询问给定两个点, 求它们的最短距离.

Solution

分治乱搞,还没改这道题

cti

Description

一个有n×m个格子的矩形,每个格子上可以是空地、朝向上下左右的炮塔或者是敌人。每个炮塔能打死一个格子上所有的敌人,其射出的弹道不能相交,问你最多能打死多少个敌人

Solution

最小割模型。
每个点拆成横点和竖点,分别以横着的和竖着的炮打出去的链建图,横着的正向建,竖着的反向建,然后每个点横点向竖点连inf的边就能保证不相交。
然后直接跑Dinic板子即可

Categories: Summary Tags: , ,

Comments

No Comments Yet. Be the first?

Post a comment