CF 977F Consecutive Subsequence

传送门

思路

  CF 的第一场 div3，在我提交了一份有错的代码后突然不能提交了，在跑什么 System Testing，我就跟它杠上了，直到它评测完。唉，我太弱了，这么傻逼的题都不能一次 AC，害得我正好碰到 System Testing，唉，我太弱啦！

  离散化，设 fi f i $f_i$ 表示以 i i $i$ 结尾的最长长度。如果存在 ai−1$a_i-1$$a_i - 1$ 就转移，否则就不转移。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = int(2e5) + 5;
int n;
int a[maxn];

int bound;
int disc[maxn];
void discretize()
{
    for (int i = 1; i <= n; i++)
        disc[++bound] = a[i];
    std::sort(disc + 1, disc + 1 + bound);
    bound = std::unique(disc + 1, disc + 1 + bound) - (disc + 1);
    for (int i = 1; i <= n; i++)
        a[i] = std::lower_bound(disc + 1, disc + 1 + bound, a[i]) - disc;
}

int f[maxn];

void run()
{
    n = readIn();
    for (int i = 1; i <= n; i++)
        a[i] = readIn();
    discretize();

    int ans = 0;
    int pos = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = std::lower_bound(disc + 1, disc + 1 + bound, disc[a[i]] - 1) - disc;
        int val;
        if (disc[t] != disc[a[i]] - 1)
            val = 1;
        else
            val = f[t] + 1;
        f[a[i]] = std::max(f[a[i]], val);
        if (val > ans)
        {
            ans = val;
            pos = i;
        }
    }

    printOut(ans);
    putchar('\n');
    std::vector<int> rec;
    int cnt = disc[a[pos]];
    for (; pos; pos--)
    {
        if (disc[a[pos]] == cnt)
        {
            rec.push_back(pos);
            cnt--;
        }
    }
    for (int i = rec.size() - 1; ~i; i--)
    {
        printOut(rec[i]);
        putchar(' ');
    }
}

int main()
{
    run();
    return 0;
}