CLYZ-NOIP十连测 Day3

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;
}
上一篇:题解[P5666树的重心]


下一篇:马拉车算法