P2757 國家集訓隊 等差子序列

2022-09-22 20:18:15 字數 1270 閱讀 8482

p2757 國家集訓隊 等差子序列

考慮有用值域

對於 \(1 \le val_i \le \lceil \frac \rceil\) 那麼有用值域是 \([1, 2*val_i]\)

對於 \(\lceil \frac \rceil \lt val_i \le n\) 那麼有用值域是 \([2*val_i-n, n]\)

然後我們可以發現,對於一對可行解 \(a + c = 2 * val_i (a \lt val_i \lt c)\)

記錄 \(l_i\) 為 \(val_i\) 在有用值域內的字首和, \(r_i\) 為 \(val_i\) 在有用值域內的字尾和。

那麼當所有可行 \(a, c\) 在 \(val_i\) 的同一側的時候 \(l_i\) 和 \(r_i\) 為 \(2*val_i\) 的倍數。

那麼有解只要任意一個 \(val_i\), \(l_i, r_i\) 不為0,\(l_i \not\equiv 0 (\mod (2*val_i))\)並且\(r_i \not\equiv 0 (\mod (2*val_i))\)

/*

name:p2757

author: gensokyo_alice

date: 26/9/20/ 09:24

description:

*/#include #include #include #include #include #include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll n, t, val[maxn], c[maxn], l[maxn], r[maxn];

void add(ll, ll);

ll ask(ll);

int main()

for (ll i = 1; i <= n; i++) c[i] = 0;

for (ll i = n; i >= 1; i--)

ll flag = 0;

for (ll i = 1; i <= n; i++)

} if (flag) puts("y");

else puts("n");

} return 0;

}void add(ll x, ll val)

}ll ask(ll x)

return ret;

}

P2757 國家集訓隊 等差子序列

題目傳送門 推薦一篇好題解 此題要求我們在一個序列中找出一個等差子序列。 顯然,我們只需要考慮子序列長度len 3的情況,因為在長度為4的子序列中必定有一個長度為3的子序列。 問題就變成了 在序列找到三個數,滿足a j a i a k a j 且i 移項,a i a k 2 a j o n 2 的做...

P2757 國家集訓隊 等差子序列

給你一個 1 n 的排列,問是否存在等差子序列 權值線段樹 hash 首先要滿足等差序列的條件為 a i a k 2 a j ,其中 i j k 那麼根據這個條件我們就可以列舉等差序列中心,判斷兩端是否有滿足條件的 a i a k 我們可以知道若一個排列長度為 3 並且我們要以 2 為等差序列中心 ...