CodeForces 731F

CodeForces731FCodeForces 731FCodeForces731F

  • 题目
    CodeForces731F
  • 题意
    给定一组序列,找到其中一个数(leadingnumberleading numberleadingnumber),选择其他数组成一个集合,集合中的其他数可以减掉一些值,使得选出的那个数整除集合中其他数,答案就是操作完的数的和,最终求和的最大。
  • 分析
    首先从小到大排序,依次选择aia_iai​(1in1{\leq}i{\leq}n1≤i≤n)作为leadingnumberleadingnumberleadingnumber,假设当前选择的数是aka_kak​,那么aia_iai​(k+1ink+1{\leq}i{\leq}nk+1≤i≤n),都是能在集合中的并且能使得最后的和最大。但是这些数都不一定是aka_kak​的倍数,所以要变成aiakak{\lfloor}{\frac{a_i}{a_k}}{\rfloor}*a_k⌊ak​ai​​⌋∗ak​。
    本题的nnn是2e52e52e5,显然不能通过。继续观察发现,aia_iai​的范围是2e5{\leq}2e5≤2e5,这个条件提示可以枚举区间,计算区间的贡献。例如对于数ak=2a_k = 2ak​=2,来说后面的数有可能是8,98,98,9,那么标记8,98,98,9出现一次,出现的次数乘上区间的权值888,就是答案。见代码
  • 代码
/*
  独立思考
  一个题不会做,收获5%,写了代码10%,提交对了30%,总结吃透了这个题才是100%.
*/
#include<bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &x)
{
	x = 0;
	char c = getchar();
	int sgn = 1;
	while (c < '0' || c > '9') {if (c == '-')sgn = -1; c = getchar();}
	while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
	x *= sgn;
}
template <typename T>
void out(T x)
{
	if (x < 0) {putchar('-'); x = -x;}
	if (x >= 10)out(x / 10);
	putchar(x % 10 + '0');
}
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
const int N = 2e5 + 5;
const int M = 2e5;
int a[N];
ll sum[N];
int vis[N];
struct s_tree
{
	int l;
	int r;
	int cnt;
} tree[N << 2];

void pushup(int rt)
{
	tree[rt].cnt = tree[rt << 1].cnt + tree[rt << 1 | 1].cnt;
}

void build(int rt, int l, int r)
{
	tree[rt].l = l;
	tree[rt].r = r;
	if (l == r) {
		tree[rt].cnt = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt);
}

void update(int rt, int x)
{
	int l = tree[rt].l;
	int r = tree[rt].r;
	if (l == r) {
		tree[rt].cnt++;
		return ;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) update(rt << 1, x);
	else update(rt << 1 | 1, x);
	pushup(rt);
}

int query(int rt, int L, int R)
{
	int l = tree[rt].l;
	int r = tree[rt].r;
	if (L <= l && r <= R) return tree[rt].cnt;
	int ans = 0;
	int mid = (l + r) >> 1;
	if (L <= mid) ans += query(rt << 1, L, R);
	if (R > mid) ans += query(rt << 1 | 1, L, R);
	return ans;
}

int main ()
{
	int n;
	read(n);
	build(1, 1, M);
	int mx = 0;
	for (int i = 1; i <= n; i++) {read(a[i]); update(1, a[i]); vis[a[i]] = 1; mx = max(mx, a[i]);}
	ll ans = 0;
	for (int i = 1; i <= mx; i++) if (vis[i]) {
			ll _ = 0;
			int j ;
			for (j = i - 1; j <= mx; j += i)
			{

				_ += (ll)query(1, j - i + 1, j) * (j - i + 1);//区间贡献
			}
			if (j > mx) _ += (ll)query(1, j - i + 1, mx) * (j - i + 1);
			ans = max(ans, _);
		}
	cout << ans << endl;
	return 0 ;
}
  • 方法
    贪心,权值线段树,前缀和
  • 总结
    可以直接前缀和
上一篇:利用iframe 监听页面宽度变化


下一篇:Leetcode 98 验证二叉搜索树