CLYZ-NOIP2021 国庆集训 B 组 Day3
题面：https://files.cnblogs.com/files/blogs/575626/day3B.zip
头文字 A
我们考虑记下来到 \(n\) 的答案为 \(a_n\)，那么我们可以得到一个显然的递推式
\[a_n=a_{n-1}+a_{n-2}+n-2 \]然后这玩意直接用矩阵快速幂转移即可。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
inline int Mod(int x) {
if (x >= mod) {
return x - mod;
}
else {
return x;
}
}
using std::cin;
using std::cout;
int n;
struct Matrix {
int a[4][4];
Matrix() {
memset(a, 0, sizeof a);
}
Matrix operator * (Matrix b) {
Matrix ret;
for (int i = 0; i < 4; ++i) {
for (int k = 0; k < 4; ++k) {
for (int j = 0; j < 4; ++j) {
ret.a[i][j] = (ret.a[i][j] + (long long) a[i][k] * b.a[k][j]) % mod;
}
}
}
return ret;
}
Matrix operator ^ (int x) {
Matrix ret;
for (int i = 0; i < 4; ++i) {
ret.a[i][i] = 1;
}
Matrix u = *this;
for (; x; x >>= 1, u = u * u) {
if (x & 1) {
ret = ret * u;
}
}
return ret;
}
};
int main() {
freopen("subset.in", "r", stdin);
freopen("subset.out", "w", stdout);
cin >> n;
Matrix I;
I.a[0][0] = 1;
I.a[0][1] = 1;
I.a[0][2] = 1;
I.a[1][0] = 1;
I.a[2][2] = 1;
I.a[2][3] = 1;
I.a[3][3] = 1;
if (n < 3) {
cout << 0 << '\n';
return 0;
}
I = I ^ (n - 2);
cout << Mod(I.a[0][2] + I.a[0][3]) << '\n';
return 0;
}
头文字 B
这玩意，很明显首先求一个强连通分量，缩点，然后求的就是剩下的 \(DAG\) 上的最长链。
#include <bits/stdc++.h>
using std::cin;
using std::vector;
using std::pair;
using std::cout;
const int N = 1e6 + 10;
int n, m, dfc, dfn[N], low[N], num, col[N], top, stk[N], in[N], val[N], f[N];
vector<int> v[N], e[N];
template<typename T>
inline T min(const T &x, const T &y) {
return x > y ? y : x;
}
template<typename T>
inline T max(const T &x, const T &y) {
return x > y ? x : y;
}
void dfs(int u) {
dfn[u] = low[u] = ++dfc;
stk[++top] = u;
for (auto &j: v[u]) {
if (dfn[j]) {
if (!col[j]) {
low[u] = min(low[u], dfn[j]);
}
}
else {
dfs(j);
low[u] = min(low[u], low[j]);
}
}
if (low[u] == dfn[u]) {
++num;
while (!col[u]) {
col[stk[top--]] = num;
val[num]++;
}
}
return;
}
int main() {
freopen("bomb.in", "r", stdin);
freopen("bomb.out", "w", stdout);
std::ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1, x, y; i <= m; ++i) {
cin >> x >> y;
v[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
dfs(i);
}
}
for (int i = 1; i <= n; ++i) {
for (auto &j: v[i]) {
if (col[j] != col[i]) {
e[col[j]].push_back(col[i]);
in[col[i]]++;
}
}
}
std::queue<int> q;
for (int i = 1; i <= num; ++i) {
if (!in[i]) {
q.push(i);
f[i] = val[i];
}
}
int ans = 0;
while (q.size()) {
int nw = q.front();
q.pop();
ans = max(ans, f[nw]);
for (auto &j: e[nw]) {
f[j] = max(val[j] + f[nw], f[j]);
if (!--in[j]) {
q.push(j);
}
}
}
cout << ans << '\n';
return 0;
}
头文字 C
我们考虑这玩意肯定是底边最短的时候，层数最多。
那么考虑设计一个 \(dp\) 表示， \(f_i\) 表示 \([i...n]\) 中最下层的最短长度。
然后 \(f_i=\min_{j=i+1 \and sum_{j-1}-sum_{i-1}\ge f_j}^n sum_{j-1}-sum_{i-1}\)
这玩意的话，考虑直接用单调队列维护即可。
#include<bits/stdc++.h>
const int N = 100005;
int n, s[N], f[N], g[N], q[N], h, t;
int main() {
freopen("block.in", "r", stdin);
freopen("block.out", "w", stdout);
scanf("%d", &n);
h = t = 1;
q[1] = n + 1;
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
s[i] = s[i - 1] + x;
}
for (int i = n; i >= 1; i--) {
while (h < t && s[q[h + 1] - 1] - f[q[h + 1]] >= s[i - 1]) {
h++;
}
f[i] = s[q[h] - 1] - s[i - 1];
g[i] = g[q[h]] + 1;
while (h <= t && s[i - 1] - f[i] >= s[q[t] - 1] - f[q[t]]) {
t--;
}
q[++t] = i;
}
printf("%d\n", g[1]);
return 0;
}
头文字 D
暴力想法，过了。
我们考虑，暴力维护这些东西，考虑维护一个数组 \(val_i\) 这个东西肯定是单调不增的，然后连续的段很多。维护这些连续段，考虑每次添加一个数会对于这玩意产生什么影响即可，就是枚举这个数的因数，看他之前在哪里出现，然后出现的位置到 \(i\) 这个区间里取 \(\max\) 即可。
这个取 \(max\) 操作最后可以用一个类似于归并操作的trick转化为 \(O(段数+d(a_i))\) 做一次。
最后枚举所有段数求答案即可。
时间复杂度看起来像是 \(n\log^2 n\) 的
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::tuple;
using std::make_tuple;
using std::__gcd;
using std::get;
using std::pair;
using std::make_pair;
using std::cerr;
template<typename T>
inline T max(const T &x, const T &y) {
return x > y ? x : y;
}
template<typename T>
inline T min(const T &x, const T &y) {
return x < y ? x : y;
}
const int N = 1e5 + 10;
int n, a[N], pos[N];
long long cnt[N];
vector<int> d[N];
vector<tuple<int, int, int>> v;
int main() {
freopen("gcd.in", "r", stdin);
freopen("gcd.out", "w", stdout);
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i) {
d[j].emplace_back(i);
}
}
for (auto &j: d[a[1]]) {
pos[j] = 1;
}
for (int i = 2; i <= n; ++i) {
vector<tuple<int, int, int>> tmp, tmp1;
vector<pair<int, int>> v1;
for (int j = 0; j < d[a[i]].size(); ++j) {
if (pos[d[a[i]][j]]) {
v1.emplace_back(pos[d[a[i]][j]], d[a[i]][j]);
}
}
std::sort(v1.begin(), v1.end(), std::greater<pair<int, int>> ());
int last = i, mx = 0;
for (auto &j: v1) {
if (j.first < last && j.second > mx) {
if (last != i) {
tmp.emplace_back(mx, j.first + 1, last);
}
last = j.first;
mx = j.second;
}
}
v.insert(v.begin(), make_tuple(__gcd(a[i], a[i - 1]), i - 1, i - 1));
tmp.emplace_back(mx, 1, last);
int I = 0, J = 0;
while (I < v.size() && J < tmp.size()) {
if (get<0>(v[I]) >= get<0>(tmp[J])) {
int mx = std::max(get<1>(v[I]), get<1>(tmp[J]));
tmp1.emplace_back(get<0>(v[I]), mx, get<2>(v[I]));
if (mx == get<1>(v[I])) {
++I;
}
else {
get<2>(v[I]) = mx - 1;
}
if (mx == get<1>(tmp[J])) {
++J;
}
else {
get<2>(tmp[J]) = mx - 1;
}
}
else {
int mx = std::max(get<1>(v[I]), get<1>(tmp[J]));
tmp1.emplace_back(get<0>(tmp[J]), mx, get<2>(tmp[J]));
if (mx == get<1>(v[I])) {
++I;
}
else {
get<2>(v[I]) = mx - 1;
}
if (mx == get<1>(tmp[J])) {
++J;
}
else {
get<2>(tmp[J]) = mx - 1;
}
}
}
v.clear();
for (int i = 0; i < tmp1.size(); ++i) {
if (!v.size()) {
v.push_back(tmp1[i]);
}
else if (get<0>(v.back()) == get<0>(tmp1[i])) {
get<1>(v.back()) = get<1>(tmp1[i]);
}
else {
v.push_back(tmp1[i]);
}
}
for (auto &j: v) {
cnt[get<0>(j)] += get<2>(j) - get<1>(j) + 1;
}
for (auto &j: d[a[i]]) {
pos[j] = i;
}
}
for (int i = 1; i <= n; ++i) {
cout << cnt[i] << '\n';
}
return 0;
}