某島

… : "…アッカリ~ン . .. . " .. .
August 11, 2021

Codeforces Round #737 (Div. 2)

傳送門

https://codeforces.com/contest/1557

說著要回 Div1,結果分越來越低了。。。
上紫名好難啊。。。。(暴風哭泣)

Problem B. Moamen and k-subarrays

給定一個數組,拆成 k 個 子段,再重新排序,問這樣是否能將這個數組排序,保證數字不相同。

然後開始默認需要拆 n 份,然後看相鄰位置如果再排序後也相鄰就讓需要拆的份數 -1.

Problem C. Moamen and XOR

給定 n,k 問有多少組長度為 n 的數組 a,滿足 && 和大於等於 xor 和。(ai <= 2^k)

對 n 分奇偶討論即可,比賽的時候對冪次取模結果 debug 了好久不能更蠢。。。

Problem D. Ezzat and Grid

給定一個 01 矩陣,問至少刪掉多少行,使得相鄰行 至少再某一列都有 1。

對於每一行,我們向下連邊,這個東西顯然是一個 dag,dp 求最長鏈即可。
因為是求最長鏈,可以對圖可以有所簡化,將邊的規模縮小為 O(n)。

所以難點在於如何用數據結構幫助建圖。
最簡單的方式當然是用 set 去維護區間集合,這個東西在很多計算幾何題目里應該經常會用到。

Problem E. Assiut Chess

交互題。棋盤上有一個看不見的 King,給你一個 Queen,在限定步數內將死這個 King。
King 不能走到被你一步可以將死的位置。

基本想法是固定我的位置,然後一步步把對手卡到四角。
但是貌似有一些情況需要特殊處理,我想不太清楚。。。然後看步數比較寬鬆試圖用隨機化亂搞過去但是失敗了。。。
嘛。。。感覺這種題數據著實也不太好出。。。果不其然,現場也確實被各種亂搞爆過去了。。

Comments are closed.