AT_arc233_d.Zigzag Code for Cubic Functions
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given positive integers A,B,C,L,R. Here, L≤R. Define
f(n)=n3+An2+Bn+C.
For a non-empty string S consisting of + and −, define
g(S)=∑i=1∣S∣{f(i)−f(i)(Si=+)(Si=−).
Here, Si denotes the i-th character of S.
An integer k is said to be generable from S if there exists a non-empty substring S′ of S such that g(S′)=k.
Construct a string S that satisfies the following conditions.
- 1≤∣S∣≤2×106
- S is a string consisting of + and −.
- Among the strings satisfying the two conditions above, S maximizes the number of integers between L and R, inclusive, that are generable from S.
Furthermore, for the constructed string S and each k=L,L+1,…,R, determine whether there exist two integers l,r satisfying the following conditions, and if they exist, find one such pair.
- 1≤l≤r≤∣S∣
- Letting S′ be the string formed by the l-th through r-th characters of S, we have g(S′)=k.
What is a substring?
A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, AB is a substring of ABC, but AC is not a substring of ABC.
给你正整数 A,B,C,L,R,其中 L≤R。定义
f(n)=n3+An2+Bn+C。
对于一个由字符 + 和 − 构成的非空字符串 S,定义
g(S)=∑i=1∣S∣{f(i)−f(i)(Si=+)(Si=−)。
这里,Si 表示字符串 S 的第 i 个字符。
若存在 S 的一个非空子串 S′,使得 g(S′)=k,则称整数 k 可由 S 生成。
请构造一个字符串 S,使其满足以下条件:
- 1≤∣S∣≤2×106;
- S 是仅由 + 和 − 构成的字符串;
- 在所有满足上述两个条件的字符串中,S 能够生成的、落在区间 [L,R] 内(含端点)的整数个数最多。
此外,对所构造出的字符串 S 以及每个 k=L,L+1,…,R,判断是否存在整数 l,r 满足以下条件;若存在,则输出其中任意一对:
- 1≤l≤r≤∣S∣;
- 记 S′ 为 S 中从第 l 个字符到第 r 个字符(含)构成的子串,则有 g(S′)=k。
什么是子串?
字符串 S 的一个子串,是指从 S 的开头删除零个或多个字符、并从 S 的末尾也删除零个或多个字符后所得到的字符串。
例如,AB 是 ABC 的子串,但 AC 不是 ABC 的子串。
输入格式
The input is given from Standard Input in the following format:
A B C L R
输入从标准输入中以如下格式给出:
A B C L R
输出格式
Print a solution in the following format:
S
outputL
outputL+1
⋮
outputR
Here, outputi denotes the output for k=i.
If there exist two integers l,r satisfying the conditions, print them in the following format:
l r
If they do not exist, print -1.
If there are multiple solutions, you may print any of them.
按以下格式输出一个解:
S
outputL
outputL+1
⋮
outputR
其中,outputi 表示当 k=i 时的输出。
若存在满足条件的两个整数 l,r,则按以下格式输出它们:
l r
若不存在这样的整数,则输出 -1。
若存在多个解,可输出其中任意一个。
输入输出样例
输入#1
2 2 3 22 23
输出#1
+---+--+ 2 5 6 8
输入#2
1 2 2 5 7
输出#2
++ -1 2 2 -1
说明/提示
Sample 1 Explanation:
We have
f(n)=n3+2n2+2n+3 and
f(1)=8,f(2)=23,f(3)=54,f(4)=107.
Since
g(−−−+)=−f(1)−f(2)−f(3)+f(4)=−8−23−54+107=22 and
g(−−+)=−f(1)−f(2)+f(3)=−8−23+54=23,
both 22 and 23 are generable from −−−+.
Constraints
- 1≤A,B,C≤105
- 1≤L≤R≤min(L+105,1014)
- All input values are integers.
样例 1 解释:
我们有
f(n)=n3+2n2+2n+3,且
f(1)=8,f(2)=23,f(3)=54,f(4)=107。
由于
g(−−−+)=−f(1)−f(2)−f(3)+f(4)=−8−23−54+107=22,以及
g(−−+)=−f(1)−f(2)+f(3)=−8−23+54=23,
因此 22 和 23 均可由 −−−+ 生成。
限制条件
- 1≤A,B,C≤105
- 1≤L≤R≤min(L+105,1014)
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?