某島

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

Codeforces Round #741

傳送門

https://codeforces.com/contest/1562

靠字元串題漲了點分 > <、

Problem B. Scenes From a Memory

給定一個不包含數字 0 的數,要求保留最少的數字,使得最後不是素數,有多解任意輸出一組即可,保證一定有解。
先寫個保留數字儘可能少的爆搜,然後果斷猜一下最後保留的數字不會太多。。。

具體的話,就是如果存在 1 4 6 8 9 那麼顯然就是 1 位,剩下的只有。。
2 3 5 7 。。那麼不能出現重複的數,否則可以整除 11,那麼鴿巢一下方案已經非常少了。
最後結論貌似是保留 2 位即可。。。

當然用上面的爆搜的話,其實不用仔細去推,隨便給個差不多的上界直接爆過去即可。。。

Problem C. Rings

腦經急轉彎。

Problem E. Rescue Niwen!

挺傻的一眼題。。。套個 sa 模板就可以寫 dp 了,中間類似求重複子串,要去掉 lcp。

        LL z = 0;
        REP_1(i, n) {
            dp[i] = (n - sa[i]);
            FOR(j, 1, i) if (sa[j] < sa[i]) {
                checkMax(dp[i], dp[j] + (n  - sa[i]) - lcpp(sa[i], sa[j]) ) ;
            }

            checkMax(z, dp[i]);
        }
        cout << z << endl;

O(n2) 爆過去即可,lcp 甚至可以暴力寫。所以這個 dp 的複雜度可以進一步優化嗎?