首页 > 其他分享 >AtCoder Regular Contest 131 D AtArcher

AtCoder Regular Contest 131 D AtArcher

时间:2023-05-05 18:44:18浏览次数:45  
标签:AtCoder typedef ll mid long 131 Regular maxn

洛谷传送门

AtCoder 传送门

观察可以发现:

  • 使每支箭的距离都为 \(D\) 一定不劣;
  • 每支箭坐标一定为整数;
  • 设最左边的箭坐标为 \(x\),那么 \(x\) 太小时可以把最左边的箭移到最右边,\(x\) 太大时可以把最右边的箭移到最左边。计算可得 \(x\) 的最优取值范围为 \(x \in [-\left\lfloor\frac{ND}{2}\right\rfloor, -\left\lfloor\frac{ND}{2}\right\rfloor + D)\)。

这样枚举 \(x\) 就得到了一个 \(O(mD)\) 做法。

考虑与其单独算每个 \(x\) 的得分,不如把所有 \(x\) 放在一起考虑,单独算每个线段的贡献。预处理出 \((l_i, r_i, v_i)\) 表示坐标落在 \([l_i, r_i)\) 的箭能得 \(v_i\) 分,对于一个固定的 \(x\),差分可得坐标落在这个区间内的箭的数量为:

\[\max(\min(\left\lceil\frac{r_i - x}{D}\right\rceil, n), 0) - \max(\min(\left\lceil\frac{l_i - x}{D}\right\rceil, n), 0) \]

发现因为 \(x\) 取值区间长度为 \(D\),所以上面式子中左、右项的值最多变一次。二分出极长相同区间后,对这个范围的 \(x\) 的答案区间加上面式子乘上 \(v_i\),可以使用差分。

时间复杂度 \(O(m \log D + D)\)。

code
// Problem: D - AtArcher
// Contest: AtCoder - AtCoder Regular Contest 131
// URL: https://atcoder.jp/contests/arc131/tasks/arc131_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;

ll n, m, K, A, a[maxn], b[maxn], D, d[maxn];
struct node {
	ll l, r, x;
	node(ll a = 0, ll b = 0, ll c = 0) : l(a), r(b), x(c) {}
} c[maxn];
// [l, r)

inline ll calc(ll t, ll x) {
	return x < t ? min((t - x + D - 1) / D, n) : 0;
}

void solve() {
	scanf("%lld%lld%lld", &n, &m, &D);
	A = -(n * D / 2);
	for (int i = 0; i <= m; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld", &b[i]);
	}
	for (int i = m; i >= 2; --i) {
		c[++K] = node(-a[i], -a[i - 1], b[i]);
	}
	c[++K] = node(-a[1], a[1] + 1, b[1]);
	for (int i = 2; i <= m; ++i) {
		c[++K] = node(a[i - 1] + 1, a[i] + 1, b[i]);
	}
	for (int i = 1; i <= K; ++i) {
		ll L = c[i].l, R = c[i].r, x = c[i].x, p = A;
		while (p <= A + D - 1) {
			ll l = p, r = A + D - 1, pos = -1, u = calc(L, p), v = calc(R, p);
			while (l <= r) {
				ll mid = (l + r) >> 1;
				if (calc(L, mid) == u && calc(R, mid) == v) {
					pos = mid;
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
			d[p - A + 1] += (v - u) * x;
			d[pos + 1 - A + 1] -= (v - u) * x;
			p = pos + 1;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= D; ++i) {
		d[i] += d[i - 1];
		ans = max(ans, d[i]);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,ll,mid,long,131,Regular,maxn
From: https://www.cnblogs.com/zltzlt-blog/p/17375084.html

相关文章

  • 【统计数据分析专论】02-Regularization 正则化
    Regularization正则化课件翻译ModelingNonlinearRelation非线性关系建模上节课学了线性模型但是非线性模型也很重要考虑一个由基函数的线性组合定义的模型在数学中,基函数是函数空间中特定基底的元素。函数空间中的每个连续函数可以表示为基函数的线性组合,就像向量......
  • 网络对抗实验六 MSF应用基础--20201313
    《网络对抗技术》——Exp6MSF应用基础目录《网络对抗技术》——Exp6MSF应用基础一、实践内容二、问题回答三、实践过程实验准备:1、一个主动攻击实践ms08_067_netapi2、一个针对浏览器的攻击ms10_018_ie_behaviors3、一个针对客户端的攻击Wireshark4、成功应用一个辅助模块sniff......
  • github报错Failed to connect to github.com port 443 after 21313 ms: Couldn't conn
    github报错Failedtoconnecttogithub.comport443after21313ms:Couldn'tconnecttoserver网络连接问题,我开vpn了。github报错Recvfailure:Connectionwasreset该错误通常表示网络连接问题,可能是您的Internet连接出现问题或GitHub服务器上的连接问题。刷新重新登......
  • AtCoder Regular Contest 128 E K Different Values
    洛谷传送门AtCoder传送门考虑判断有无解。把序列分成\(c=\left\lceil\frac{len}{k}\right\rceil\)段,则\(\foralla_i\lec\)且\(\sum\limits_{i=1}^n[a_i=c]\le((len-1)\bmodk)+1\)。必要性显然。充分性可以考虑直接构造,不难证明。考虑如何构造字典序最小......
  • AtCoder Regular Contest 134 D Concatenate Subsequences
    洛谷传送门AtCoder传送门我一年前甚至不会做/qd发现\(a_{x_1}\)为\(k=\min\limits_{i=1}^na_i\)时最优。然后开始分类讨论:如果\(\min\limits_{a_i=k}a_{i+n}\lek\),答案为\((k,\min\limits_{a_i=k}a_{i+n})\)。这是因为如果再选一个\(k\)肯定不优。否则......
  • AtCoder Beginner Contest 300
    A-N-choicequestion#include<bits/stdc++.h>usingnamespacestd;intread(){intx=0,f=1,ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-......
  • AtCoder Regular Contest 128 D Neq Neq
    洛谷传送门AtCoder传送门考虑把所有\(a_i=a_{i+1}\)的位置断开,分别计算然后把方案数乘起来。接下来的讨论假设\(a_i\nea_{i+1}\)。考虑一个dp,设\(f_i\)为\([1,i]\)最后剩下的集合的方案数。转移显然是\(f_i\getsf_i+f_j\),但是需要满足\((a_j,a_{j+1},...,......
  • AtCoder Beginner Contest 242(D,E)
    AtCoderBeginnerContest242(D,E)D(二叉树搜索)D题目大意就是首先给你一个字符串,代表\(S^0\),然后我们可以操作得到\(S^1,S^2\)等等我们可以知道\(S^i\)是拿\(S^(i-1)\)经过一系列替换而来的,因为这个字符串只有三种字符串,\(A,B,C\),这个替换方式就是把\(A\)替换成\(BC\),把\(B\)......
  • AtCoder Regular Contest 125 F Tree Degree Subset Sum
    洛谷传送门AtCoder传送门首先将度数\(-1\)。设\(f_i\)为体积为\(i\)至多能用几个物品凑出来,\(g_i\)为至少。我们现在要证明一个东西:\(x\in[g_i,f_i]\),\((i,x)\)合法。首先若\((s,x)\)合法,那么必须满足\(s-x\in[-z,z-2]\),其中\(z=\sum\limits_{i=1}......
  • AT_abc106_d [ABC106D] AtCoder Express 2 题解
    题目传送门解题思路区间\(dp\)。划分阶段:以左右城市之间的列车数量为阶段。状态表达:设\(f_{i,j}\)为城市\(i\)与城市\(j\)之间的列车数量。状态转移:由图可知,城市\(l\)与城市\(r\)之间的列车数量,就是城市\(l\)与城市\(r-1\)之间的列车数量与城市\(l+1\)与......