2021牛客OI賽前集訓營-普及組（第二場）C 題題解

目錄

• ​​Description​​
• ​​Solution​​
• ​​Code​​

Description

給你 \(n\) 個點，将其按 \(y_i\) 從大到小排序，從中任意選出一些點，組成序列 \(a\)，要使其滿足 $a_{i-2} < a_i < a_{i-1} $ 或 \(a_{i-1} < a_i < a_{i-2}\)，求合法方案數。

Solution

隻談正解。

考慮按照 \(x\) 從小到大排序。

并轉化一下思路，從後向前選數，需要保證 \(y\) 是單調遞增的。

設 \(f_{i,1/0}\) 表示考慮第 \(i\) 位作為目前序列中 \(y\) 最大的點，\(y\) 第二大的點是從哪轉移而來的，\(1\) 表示由右邊的點轉移而來，\(0\) 表示由左邊的點轉移而來。

假設目前處理到第 \(i\) 位，前面的已經處理完了，那麼對于一位 \(j\)，

配一張圖友善了解：

倒序枚舉 \(j\)：

• 如果 \(a_{j,y} > a_{i,y}\)，那麼 \(f_{j,1} += f_{i,0}\)

此時就是把 \(a_{i,y}\) 當做了 \(y\) 第二大的點，想 \(j\) 這個 \(y\) 值第一大的點轉移。

然後你手玩一下題目要求，發現一個合法序列的 \(x\) 一定是一左一右的反複橫跳，是以隻有 \(f_{i,0}\) 這一個方向可以轉移。

• 如果 \(a_{j,y} < a_{i,y}\)，那麼 \(f_{i,0} += f_{j,1}\)

這個和上面同理。但還有一個問題，這樣 \(f_{i,0}\) 的值不就改變了嗎？接下來如果有個位置 \(k\)，滿足 \(a_{k,y} > a_{i,y}\) 怎麼辦？無需多慮，這樣做剛好考慮上 \(i\) 作為一個中間點時的情況。

那麼為什麼不連 \(k\) 以前的也考慮上？這樣轉移不滿足題目要求。

然後這題就做完了，答案是 \(\sum_{i=1}^{n} (f_{i,0} + f_{i,1})\)

挺神奇的考慮方向。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑題
Knowledge: 垃圾算法
Time: O(能過)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 6000+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct node {
int x, y;
bool operator < (const node &b) const { return x < b.x; }
}a[MAXN];

int n, ans = 0;
int f[MAXN][2];

int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}

signed main()
{
n = read();
for(int i = 1; i <= n; ++i) a[i].x = read(), a[i].y = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) {
f[i][0] = f[i][1] = 1;
for(int j = i - 1; j >= 1; --j) {
if(a[j].y > a[i].y) f[j][1] = (f[j][1] + f[i][0]) % mod;
else f[i][0] = (f[i][0] + f[j][1]) % mod;
        }
    }
for(int i = 1; i <= n; ++i) {
ans = (ans + f[i][0] + f[i][1]) % mod;
    }
printf("%lld\n", (ans - n + mod) % mod);
return 0;
}