某島

… : "…アッカリ~ン . .. . " .. .
April 11, 2020

Andrew Stankevich Contest 15

https://codeforces.com/gym/100218

Problem A. Perfect Bombing

暴力 + bitset 優化即可。

Problem B. Fixed Point

Wikipedia, Morphism
非常厲害的題,感覺是背包 DP?不太會。

Problem C. Paragraph Formatting

經典 DP。

Problem D. Young Hackers

給定一個文本串 T,一個模式串 P,對文本串的每個後綴,求出其與模式串每個後綴的 LCP 的最大值。

這裡面最大的那個值,顯然就是最長公共子串(LCS)。所以我們用 LCS2 的代碼改改就好了。
文本串和模式串都反過來跑後綴自動機。

Problem E. Mazes Exit Guide

給定兩個有向圖,每條邊都有一個顏色,保證每個點出發的邊,顏色兩兩不同。
問是否存在一個顏色序列,使得兩個圖分別從各自的起點出發,沿著該序列的邊遍歷,均可以到達各自的終點。

記憶化搜索,dp[100][100]。類似 double maze

Problem F. Nonequal Parts

分硬幣遊戲,Alice 和 Bob 輪流從當前狀態中選出任意一堆,並拆分成任意多堆,要求本次拆分出的堆中,沒有兩個硬幣數是相同的。不能拆分時判負。求初始為一堆 n 個硬幣的勝負態,並構造一組初始的操作方案。
SG 函數基本功。

Problem G. Primitive Product

題面有點故弄玄虛。。。其實就是因式分解,然後枚舉因子的正負號,排序輸出即可。

Problem H. Rent A Car

費用流裸題。

Problem I. Roundtrip

給定一個無向圖,和三個節點 a,b,c。要求找一條從 a 點出發,經過 b、c 的哈密頓迴路。
網路流判定,然後從殘量網路里還原出方案,細節很多。

Problem J. Yet Another Minimal Triangle

給定一組點集,從中選取三個點,使得形成的三角形面積最小(不可退化)。

O(n3) 居然能暴過去。。。不知道是不是 intended behavior。
正解可以看 peter50216 的。