2019/10/9 CSP-S 模拟测
2024-09-06 10:28:02
T1:最大约数和
给定一个正整数 S,现在要求你选出若干个互不相同的正整数,使得它们的和不大于 S,而且每个数的因数(不包括本身)之和最大。S <= 1000
分析:
其实考完才听他们说是背包,不过也没差了,不管了
首先约数和\(sum\)是可以预处理的,用类似埃氏筛的方式枚举一下然后累加一下
然后发现有很明显的阶段,考虑\(dp\)
\(f[i] = f[j] + sum[i - j], 0 <= j <= i\)
代码:
#include<bits/stdc++.h>
#define N (1000 + 10)
#define int long long
using namespace std;
int n;
int f[N], sum[N];
signed main() {
freopen("sum.in", "r", stdin);
freopen("sum.out", "w", stdout);
scanf("%lld", &n);
for (register int i = 1; i <= n; ++i)
for (register int j = 2; i * j <= n; ++j) sum[i * j] += i;
for (register int i = 1; i <= n; ++i)
for (register int j = 0; j <= i; ++j) f[i] = max(f[i], f[j] + sum[i - j]);
printf("%lld", f[n]);
return 0;
}
T2:最佳序列
给一个长度为 n 的数组 A,给定 L, R,求所有满足长度大等于 L,小等于 R 的 A 数组的子区间的平均值的最大值。 n <= 1e5
分析:
考场没思路,前缀和+枚举区间长度\(60pts\)走人
观察数据范围可以套一个\(log\),试试二分平均值
怎么\(check\)呢
每次重构前缀和数组\(sum\),在前缀和数组上减去二分的\(mid\),那么问题转化为判断区间上有没有一段长度在\([L, R]\)之间的区间最小值大于\(0\)
枚举右端点\(i\),则左端点的可能区间为\([i - R, i - L]\),区间和为\(sum[i] - sum[左端点-1]\)
对于每一个枚举的\(i\),\(sum[i - L]\)相当于一个定值,那么维护\(sum[左端点-1]\)的最小值,若其能使区间和\(>=0\)则答案合法,否则答案不合法
维护最小值用单调队列
代码:
#include<bits/stdc++.h>
#define N (500000 + 10)
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
return cnt * f;
}
int n, L, R, head, tail;
double a[N], sum[N], q[N], pos[N], gmax;
bool check(double r) {
memset(q, 0, sizeof q);
memset(sum, 0, sizeof sum);
head = 1, tail = 0;
for (register int i = 1; i <= n; ++i) sum[i] = 1.0 * a[i] - r + sum[i - 1];
for (register int i = L; i <= n; ++i) {
while (head <= tail && q[tail] >= sum[i - L]) --tail;
while (head <= tail && pos[head] + R < i) ++head;
q[++tail] = sum[i - L];
pos[tail] = i - L;
if (sum[i] - q[head] >= 0) return true;
}
return false;
}
int main() {
n = read(), L = read(), R = read();
for (register int i = 1; i <= n; ++i) a[i] = read(), gmax = max(gmax, a[i]);
double mid;
double l = 0, r = 1.0 * gmax;
for(register int i = 1; i <= 100; ++i) {
mid = (l + r) / 2;
// cout<<mid<<endl;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.4lf", mid);
return 0;
}
T3:贸易/华莱士
给定一个图,求边权最小的基环树森林,允许重边不允许自环,点、边<=5e5
分析:
考场上打了个错误的\(kruscal\)不知道为什么能拿\(50pts\),权当撞大运吧
大方向至少是对的,考虑类似\(kruscal\)的方式用并查集维护连通性并以一些奇怪的方式来判断边选还是不选
- 如果当前边两头点在一个集合,没有环就选上
- 如果当前边两头点不在一个集合,再次分类讨论:如果是两棵基环树则不用连上,否则加上这条边,并判断新的并查集是不是一棵基环树即可
对于每个联通块是不是基环树打标记,最后只需要看加入的总边数是否等于\(n\)判断\(No\)
代码:
#include<bits/stdc++.h>
#define int long long
#define N (500000 + 10)
using namespace std;
inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
return cnt * f;
}
int n, m, fa[N], ans, cnt;
bool check[N];
int get_fa(int x) {return x == fa[x] ? x : fa[x] = get_fa(fa[x]);}
struct node {
int u, v, w;
}edge[N << 1];
bool cmp(node a, node b) {
return a.w < b.w;
}
signed main() {
n = read(), m = read();
for (register int i = 1; i <= n; ++i) fa[i] = i, check[i] = 0;
for (register int i = 1; i <= m; ++i) edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
sort (edge + 1, edge + m + 1, cmp);
for (register int i = 1; i <= m; ++i) {
int fx = get_fa(edge[i].u), fy = get_fa(edge[i].v);
if (fx == fy) {
if (check[fx]) continue;
else check[fx] = 1, ans += edge[i].w, fa[fy] = fx, ++cnt;
} else {
if (check[fx] && check[fy]) continue;
if (check[fx] || check[fy]) check[fx] = 1;
fa[fy] = fx;
ans += edge[i].w, ++cnt;
}
}
// for (register int i = 1; i <= n; ++i) if (!check[i]) return printf("No"), 0;
if (!cnt) return printf("No"), 0;
printf("%lld", ans);
return 0;
}
最新文章
- Python error: ascii’/&#39;utf-8′ codec can’t decode byte 0xb8 in position 50: ord
- spring mvc超强的json支持,你自己根本不需要额外的配置。spring mvc都给你配置好了!!!
- Android中实现app版本更新
- c语言 函数返回二位数组 函数参数为二维数组
- Configuring the JA-SIG CAS Client --官方
- 简述tcp协议对http性能的影响及优化
- BZOJ 4034: [HAOI2015]T2( 树链剖分 )
- CentOS-Desktop版service network restart报错
- vue--指令中值得随笔的地方
- SHELL脚本--expr命令全解
- ASP.NET Core 2.2 十八.各种Filter的内部处理机制及执行顺序
- 从.Net到Java学习第五篇——Spring Boot &;&;Profile &;&;Swagger2
- 通过语法设置DNS解析
- Taro 常用 API
- python 2解决编码问题
- Spring boot+ logback环境下,日志存放路径未定义的问题
- 廖雪峰Java3异常处理-1错误处理-4自定义异常
- having 的用法
- wpf 的依赖属性只能在loaded 事件之后才能取到
- bzoj 1012 BST 支持插入,区间最大