2019.11.08【NOIP提高組】模拟 A 組

今天的比賽終于沒有那麼難看了，但還是有一些值得改進的地方。

T1：這時一道水題，但是我想複雜了。

首先我們把所有點按y從大到小排序，然後對于每一個點我們隻需要考慮哪些y值比它的的就行了。

我們枚舉每一個點，然後把它當做原點，接着把y值比它大的點按極角排序，最後用叉積來算三角形的面積即可。

這裡可以用字首和優化成O(n^2)的。

總結：

1、這一類計算幾何一般要想到極角排序和叉積。

2、在極角排序時，一二象限的極角值時正數，三四象限的極角值時負數。這是因為一條射線的極角值取決于(1,0)這條射線轉到它的度數及方向。在極角排序時要注意這個的影響。

T2：首先發現這個圖是一個簡單環套樹。

對于最大值，我們發現一個入度為0的點一定是要保留的。同時，對于一個所有點的入度都為1的簡單環，也至少有一個點要保留。這樣我們就求出了最大值。

對于最小值，我們用拓撲排序。對于一個入度為0的點，它是必保留的，是以它指向的點是必須要幹掉的。這樣一來，我們隻需在拓撲的時候确定哪些點一定會被幹掉，把剩下保留的點加入隊列繼續拓撲即可。

T3：這道題的題目大意可以轉換為求一個字首AB和字尾BA，使得它們的長度最大。

設f[i]表示A為1~i時B的最大長度，通過畫圖我們發現：f[i+1]>=f[i]-2

變形後得：f[i]<=f[i+1]+2

接着我們倒着求f，每次從f[i+1]+2開始枚舉，枚舉倒第一個成立的答案就是f[i]。

用哈希判斷兩個字元串是否相等就可以了。