cf补题

原题链接

https://codeforces.com/contest/1492

官方题解

https://codeforces.com/blog/entry/87792

B: 第一次写的写法在极限情况下会有指针回溯，复杂度退回(n ^ 2)， 第二种写法预先记录好位置则为O(n)

审题：题目说明了所有的n加起来不会超过1e5，说明数据规模最大就是1e5

第一种写法 – tle

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define db double
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per (i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, 1sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define debug system("pause")
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define pline cout << endl << endl 
inline int lowbit(int x) {return x & -x;} 
inline bool cmp(int a, int b) {return a > b;}
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 1e5 + 10;
int t, n;   
int a[N];
int main() {
    cin >> t; 
    while(t -- ) {
        cin >> n;   
        rep(i, 1, n) cin >> a[i];
        int end = n;
        while(end) {
            int maxn = 0;   
            int idx;
            for(int i = 1; i <= end; i ++ ) {
                if(a[i] > maxn) {
                    maxn = a[i];
                    idx = i;
                }
            }

            for(int i = idx; i <= end; i ++ ) {
                cout << a[i] << " ";
            }
            end = idx - 1;
        }

        cout << endl;
    }

    return 0;
}

第二种写法 – ac

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define db double
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per (i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, 1sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define debug system("pause")
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define pline cout << endl << endl 
inline int lowbit(int x) {return x & -x;} 
inline bool cmp(int a, int b) {return a > b;}
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 1e5 + 10;
int t, n;   
int a[N];
map<int, int> idx;
int main() {
    scanf("%d", &t); 
    while(t -- ) {
        cin >> n;   
        rep(i, 1, n) {
            scanf("%d", &a[i]);
            idx[a[i]] = i;
        }

        int end = n;
        while(n) {
            if(idx[n] <= end) {
                for(int i = idx[n]; i <= end; i ++ ) printf("%d ", a[i]);
                end = idx[n] - 1;
            }
            n -- ;
        }
        cout << endl;

        printf("\n");
    }

    return 0;
}

c题含义 ： 从串s中选择m个下标 组成的子序列等于t串 让相邻下标的差值的最大值 最大

C : 直接写个双指针记录短串中的每一个字符在长串中出现的起始位置和终点位置
然后枚举短串中每两个相邻的字符，用前一个字符在长串中的起始位置减去后一个字符在长串中出现的
终点位置，求得差的最大值即可

ac代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define db double
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per (i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, 1sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define debug system("pause")
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define pline cout << endl << endl 
inline int lowbit(int x) {return x & -x;} 
inline bool cmp(int a, int b) {return a > b;}
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 2e5 + 10;
int q[N], h[N]; 
int n, m;
string str1, str2;

int main() {
    cin >> n >> m;
    cin >> str1 >> str2;

    for(int i = 0, j = 0; j < m; i ++ ) {
        if(str1[i] == str2[j]) q[j ++ ] = i;
    }

    for(int i = n - 1, j = m - 1; j; i -- ) {
        if(str1[i] == str2[j]) h[j -- ] = i;
    }

    int maxn = -1;
    for(int i = 0; i + 1 < m; i ++ ) maxn = max(maxn, h[i + 1] - q[i]);

    cout << maxn << endl;

    return 0;
}