A
直接判断或者观察出只有 1 和 11 输出 NO 即可。
B
构造序列 使得 即可。
多余的部分应当加在数列的最后一位(k)上。
C
有一个基本思想:所有标记的轮廓中必定存在一个已经标记的格子和未标记过的格子相邻,而标记这个未标记格子的代价是 1。
所以答案就是矩阵中不同数的数量。
D
由于限制了不允许选取负数,且每个数选过一次后就会变成 0(在后续的操作中,也许会变成负数),所以每个数虽然可以选择多次但是其最多只有第一次选取时可以导致数组和变小。
假设有一个选择方案 是最优的(其中 代表第 次选择中选择了下标 ),我们可以发现其必定有 。
所以只需要求出每个正数的贡献(第 i 个正数的贡献是 ),然后取前 m 大即可(选择完后若不足 m 个正数,那么此时数组中的非负整数必定是 0)。
E
本题数据范围较大,单独考虑每一棵树 天后的高度。
对于一颗高度为 的树,单日增长为 的树,其第一次被修剪需要的天数为: ,记为 。
接下来它每次被修剪所需要的天数即为: ,记为 。
所以能够留给这颗树生长的有效天数应该为: 。(以 为起点)
坑点:求第 天中午的状态实际上是进行了 次变化(生长和剪切),需要特判 的情况。
时间复杂度:。
F
经典的【最小化最大值】问题。
考虑二分答案,设二分的答案为 那么 check 的过程就是检查所有边权小于等于 的边组成的图能否使得选定的 个集合都在一个连通块内部,这个连通块判断问题可以使用并查集解决。
时间复杂度:
G
分析一:图中有效桥的数量不超过 条。证明:对于每一对桥,我们从较低石头的角度看,每块石头最多这能连接其左右第一个大于其本身的两块石头。
分析二:这些桥之间只存在【并列】(两座桥只有端点相连)和【包含】(其中一座桥全部在另一座桥中)两种关系。证明:不存在【相交】的两对桥 使得:。(根据题意中桥存在的条件可以得出 和 的矛盾)
分析三:被【包含】的桥必定不优,不会被选取。证明:假设存在一对桥 ,其内部存在其它桥,即便选取了其内部的桥,进入区间 还是需要通过石头 和石头 又因为区间 中的石头都同时低于 和 ,所以光是通过石头 和 的代价就已经超过 了。
总结:我们先筛选出所有的可行桥(单调栈找前后最近大于自己的数,也可以用倍增或者线段树来找),然后删去其中被【包含】的桥(排序后每个点选取最远的可行点建桥即可),由于此时的桥只存在【并列】关系(选取时相互间不会影响),所以选取其中贡献最大的 m 个桥即可(桥 的贡献为 )。
时间复杂度:
参考代码:
A
#include <iostream>
using namespace std;
int main() {
int x;
cin >> x;
if(x == 1 || x == 11) puts("NO");
else puts("YES");
return 0;
}
B
#include <iostream>
using namespace std;
void solved() {
int n;
cin >> n;
int i = 1, sum = 0;
for(; i <= n; i ++) {
if(sum + i > n) break;
sum += i;
}
for(int j = 1; j < i - 1; j ++) cout << j << ' ';
cout << i - 1 + n - sum << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
void solved() {
int n, m;
cin >> n >> m;
vector<bool> vis(n*m);
int x;
for(int i = 1; i <= n * m; i ++) {
cin >> x;
vis[x - 1] = true;
}
x = 0;
for(bool p: vis) if(p) x ++;
cout << x << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100009;
int a[N];
void solved() {
int n, m;
cin >> n >> m;
ll ans = 0;
multiset<ll> se;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
ans += a[i];
if(a[i] > 0) {
se.insert(1ll * a[i] * (n - i + 1));
}
}
while(m -- && se.size()) {
ans -= *se.rbegin();
se.erase(se.find(*se.rbegin()));
}
cout << ans << endl;
}
int main() {
// FIO
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int n, m, h[N], a[N], k, b;
void solved() {
cin >> n >> m >> k >> b;
for(int i = 1; i <= n; i ++) cin >> h[i];
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) {
int t = m - 1, ans;
int t1 = (k - h[i]) / a[i] + 1;
if(t >= t1) {
t -= t1, h[i] = b;
t1 = (k - h[i]) / a[i] + 1;
t %= t1;
}
h[i] += t * a[i];
}
for(int i = 1; i <= n; i ++) cout << h[i] << ' '; cout << endl;
}
int main() {
// FIO
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
F
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int n, m, k;
int u[N], v[N], w[N];
vector<int> ve[N];
int bin[N];
int finding(int x) {
return bin[x] == x ? x : bin[x] = finding(bin[x]);
}
bool check(int mid) {
for(int i = 1; i <= n; i ++) bin[i] = i;
for(int i = 1; i <= m; i ++) {
if(w[i] <= mid) bin[finding(v[i])] = finding(u[i]);
}
for(int i = 1; i <= k; i ++) {
for(int j = 1; j <= (int)ve[i].size() - 1; j ++)
if(finding(ve[i][j]) != finding(ve[i][0])) return false;
}
return true;
}
void solved() {
cin >> n >> m;
for(int i = 1; i <= m; i ++) cin >> u[i] >> v[i] >> w[i];
cin >> k;
int x;
for(int i = 1; i <= k; i ++) {
cin >> x; ve[i].resize(x);
for(int &y: ve[i]) cin >> y;
}
int l = 1, r = 2e9;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
}
int main() {
// FIO
// int ttx; read(ttx); while(ttx --)
solved();
return 0;
}
G
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200009;
int a[N];
ll c[N];
int l[N << 1], r[N << 1];
int b[N << 1], tot;
void solved() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = n; i >= 2; i --) c[i] = abs(a[i] - a[i - 1]);
for(int i = 2; i <= n; i ++) c[i] += c[i - 1];
stack<int> st;
for(int i = 1; i <= n; i ++) {
bool tp = false;
while(!st.empty() && a[st.top()] <= a[i]) {
if(a[st.top()] != a[i]) l[tot] = st.top(), r[tot] = i, b[tot] = tot;
else l[tot] = st.top(), r[tot] = i, b[tot] = tot, tp = true;
tot ++;
st.pop();
}
if(!st.empty() && !tp) l[tot] = st.top(), r[tot] = i, b[tot] = tot, tot ++;
st.push(i);
}
priority_queue<ll> pq;
sort(b, b + tot, [](int x, int y)->bool{
if(l[x] != l[y]) return l[x] < l[y];
return r[x] > r[y];
});
int mx = 0;
for(int i = 0; i <= tot - 1; i ++) {
int x = b[i];
if(l[x] < mx) continue;
pq.push(c[r[x]] - c[l[x]] - abs(a[r[x]] - a[l[x]]));
mx = max(mx, r[x]);
}
ll ans = c[n];
while(m -- && pq.size()) {
ans -= pq.top();
pq.pop();
}
cout << ans;
}
int main() {
// FIO
// int ttx; read(ttx); while(ttx --)
solved();
return 0;
}
全部评论
(5) 回帖