简单题。
因为偶乘偶为偶，奇乘奇为奇，所以直接找有多少个奇偶性相同的块即可。
最后修改次数就是 \(n-cnt\)。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5;
int T, n, a[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (i > 1 && a[i] % 2 != a[i - 1] % 2) ++cnt;
}
cout << n - cnt - 1 << endl;
}
return 0;
}
肯定不能直接暴力做。
仔细观察，我们可以发现，对于两个数在不同区间的逆序对个数为 \(\frac{n\cdot (n-1)}{2}\)，而两个数在同一个区间的个数也为 \(\frac{n\cdot (n-1)}{2}\) 个。
所以最终答案为 \(n!\cdot n \cdot (n-1)\)。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int T;
ll n;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
ll fac = 1;
for (ll i = 2; i <= n; ++i) fac = fac * i % mod;
cout << fac * n % mod * (n - 1) % mod << endl;
}
return 0;
}
挺有意思的双指针题。
首先可以想到排序。
我们可以预处理出 \([1,10^5]\) 中每个数的所有约数。
然后双指针，每移动一下，就加/减这个数的所有约数，如果当前 \(cnt\) 等于 \(m\)，则说明 \([l,r]\) 满足条件，更新 \(a_r-a_l\) 的最小值即可。
复杂度 \(O(n\sqrt n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, inf = INT_MAX >> 1;
int T, n, m, a[N], vis[N];
vector<int> v[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
for (int i = 1; i <= 1e5; ++i) {
for (int j = i; j <= 1e5; j += i) {
v[j].push_back(i);
}
}
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i) vis[i] = 0;
sort(a + 1, a + n + 1);
int p = unique(a + 1, a + n + 1) - (a + 1);
n = p;
int l = 1, r = 0, cnt = 0, ans = inf;
while (1) {
while (r < n && cnt < m) {
++r;
for (int i = 0; i < v[a[r]].size(); ++i) {
int x = v[a[r]][i];
if (x > m) break;
if (!vis[x]) ++cnt;
++vis[x];
}
}
if (cnt < m) break;
ans = min(ans, a[r] - a[l]);
for (int i = 0; i < v[a[l]].size(); ++i) {
int x = v[a[l]][i];
if (x > m) continue;
--vis[x];
if (!vis[x]) --cnt;
}
++l;
}
if (ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}
思维题。
我们考虑一个点 \(u\) 在所有时刻内的点权为多少。
可以发现，假如 \(u\) 的深度为 \(0\)，那么 \(t\) 时刻时它的权值为其子树内所有深度为 \(t\) 的点的初始权值异或和。
现在只考虑每个子树内相同深度的点集在 \(2^n\) 种情况中的贡献。
根据异或的性质可知，当且仅当点集内有奇数个 \(1\) 时才会造成贡献，而满足这种情况的方案数为 \(\sum\limits_{i=1}^{cnt}[i\equiv 2\pmod 1]\dbinom{cnt}{i}\)，也就是 \(2^{cnt-1}\) 种。
其中 \(cnt\) 为点集的大小。
为什么呢？根据二项式定理可知：
\[\sum\limits_{i=0}^{cnt}(-1)^i\cdot \dbinom{cnt}{i}=(-1+1)^{cnt}=0 \]\[\sum\limits_{i=0}^{cnt}\dbinom{cnt}{i}=(1+1)^{cnt}=2^{cnt} \]所以 \(\sum\limits_{i=1}^{cnt}[i\equiv 2\pmod 1]\dbinom{cnt}{i}=\frac{2^{cnt}-0}{2}=2^{cnt-1}\)。
因此每个点集的贡献数为 \(2^{cnt-1}\times 2^{n-cnt}=2^{n-1}\)。
点集的个数好求，只需要把以每个子树的深度累加起来即可，即 \(\sum\limits_{u}\operatorname{dep}(u)\)。
最终答案为 \(\left [\sum\limits_{u}\operatorname{dep}(u)\right ]\cdot 2^{n-1}\)。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, mod = 1e9 + 7;
int T, n, dis[N];
vector<int> adj[N];
void dfs(int u, int lst) {
dis[u] = 1;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i]; if (v == lst) continue;
dfs(v, u); dis[u] = max(dis[u], 1 + dis[v]);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) adj[i].clear();
ll mi = 1;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
mi = mi * 2 % mod;
}
dfs(1, 0);
ll x = 0;
for (int i = 1; i <= n; ++i) x = (x + dis[i]) % mod;
cout << mi * x % mod << endl;
}
return 0;
}
我们先二分答案，然后把边权小于 \(mid\) 的边都设为双向边。
原因很显然，不过多解释。
接着跑一边 tarjan 缩点。从拓扑序最高的点跑一边 dfs 看其他点能不能都到达即可。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int T, n, m, in[N], low[N], dfn[N], vis[N], id[N], d[N], cnt, tot, num;
struct edge{int u, v, w;}e[N];
vector<int> adj[N];
stack<int> st;
void add(int u, int v) {adj[u].push_back(v);}
void dfs(int u) {
dfn[u] = low[u] = ++tot; in[u] = 1;
st.push(u);
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++cnt;
while (st.top() != u) {
in[st.top()] = 0;
id[st.top()] = cnt;
st.pop();
}
id[u] = cnt; in[u] = 0; st.pop();
}
}
void dfs2(int u) {
vis[u] = 1;
++num;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i]; if (vis[v]) continue;
dfs2(v);
}
}
bool check(int mid) {
cnt = tot = num = 0;
for (int i = 1; i <= n; ++i) adj[i].clear(), vis[i] = d[i] = dfn[i] = 0;
for (int i = 1; i <= m; ++i) {
if (e[i].w <= mid) {
add(e[i].u, e[i].v);
add(e[i].v, e[i].u);
} else add(e[i].u, e[i].v);
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int v = adj[i][j]; if (id[i] == id[v]) continue;
++d[id[v]];
}
}
for (int i = 1; i <= n; ++i) {
if (!d[id[i]]) {
dfs2(i);
return num == n;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w;
int l = 0, r = 1e9, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
cout << ans << endl;
}
return 0;
}