451 B

先来道水题……

大意

给定长为的一个序列,保证序列中的每个元素都不同。问存不存在这样一对,使得翻转区间后整个序列单调递增。所谓翻转,即为如下操作:

题解

这个题目是一道Div 2 B 题,很多人能够看一眼就得出正确的算法。这道题很明显只需要维护一下从1开始的最长上升序列和以n为结尾的最长上升序列,判断一下中间那一段可不可以经过翻转后连在原序列中使得它单调递增。时空复杂度均为
但是……只要去看一看status,我们可以发现大多数人的空间都在上百上千K左右,其实我们完全可以把空间压缩到 。你要相信,尝试这样的讨论对以后参加重要比赛绝对有好处的!

代码

int main() {
    scanf("%d\n", &n);
    int st = 0, et = 0, l = 0, ls = 0, rst = 0, rrst = 0, ret = 0, rret = 0;
    for (int i = 1; i <= n + 1; ++i) {
        if (i <= n) scanf("%d", &m); else m = (int)2e9;
        if (m < l && !st) st = i - 1, rst = l, rrst = ls;
        else if (m > l && st && !et) et = i - 1, ret = l, rret = m;
        else if (m < l && st && et) No();
        ls = l, l = m;
    }
    if (rrst > ret || rst > rret) No();
    printf("yes\n");
    printf("%d %d\n", st ? st : 1, et ? et : 1);
    return 0;
}

466 B

大意

给定三个正整数,令,现在要求一组,使得,而且使得最小。

题解

这个题目的标准解法也不难发现。
首先考虑这么一个性质:

简单证明一下。若,那么一共只有个;若,那么,取值也只有个。故此性质得证。
考虑令,则对于一个确定的,有,而根据上面的性质的取值只有种。故问题可以在的时间内解决。
题目是不难,但是……能1A的都是好汉!这个过程稍微处理不好就会WA,特别是在处理不同的种取值之间的转换,更何况这个题目需要输出方案,我亲眼看见一个提交由于输反而WA,真是太@#$%了……
没有做过的不妨挑战一下。

代码

WA.cpp
n = 6 * n - 1;

if (a * b > n) { printf("%I64\n", a * b), printf("%I64 %I64\n", a, b); return 0; }
bool ps = 0;
if (a < b) swap(a, b), ps = 1;
    
long long c = n / b, ans = INF;
for ( ; c; ) {
        long long ca = max(c + 1, a);
        if (b * ca < ans) ans = b * ca, pa = ca, pb = b;
        --c;
        if (!c) break;
        b = (n - 1) / c + 1;
}

printf("%I64d\n", ans);
if (!ps) printf("%I64d %I64d\n", pa, pb);
else printf("%I64d %I64d\n", pb, pa);
AC.cpp
n = 6 * n - 1;

if (a * b > n) { printf("%I64\n", a * b), printf("%I64 %I64\n", a, b); return 0; }
bool ps = 0;
if (a < b) swap(a, b), ps = 1;
    
long long c = n / b, ans = INF;
for ( ; c; ) {
        long long ca = max(c + 1, a);
        if (b * ca < ans) ans = b * ca, pa = ca, pb = b;
        b = n / c + 1;
        c = n / b;
}

printf("%I64d\n", ans);
if (!ps) printf("%I64d %I64d\n", pa, pb);
else printf("%I64d %I64d\n", pb, pa);

TO BE CONTINUED……