Codeforces Round #636 (Div. 3) A~D
http://codeforces.com/contest/1343/
A. Candies
题意
给定一个 (n) ，询问任意一个 (x) 满足 (x+2x+4x+⋯+2^{k−1}x=n,kgt1)，题目保证存在至少一个 (x) 满足条件。
解题
等比数列求和 (1+2+2^2+...+2^{k-1} = 2^k-1)，遍历寻找 (2^k-1) 为 (n) 的因子的情况。
for i in range(int(input())):
pow2 = 4;n=int(input())
while pow2-1<=n:
if(n%(pow2-1)==0):
print(n//(pow2-1))
break
pow2 *= 2
B. Balanced Array
题意
给定一个偶数 (n) ，求任意一个长度为 (n) 且满足下述条件的序列：
- 前 (n/2) 个元素是偶数
- 后 (n/2) 和元素是奇数
- 所有的元素都是唯一的
- 前半段和与后半段和相等
如果序列不存在输出 “NO” ，存在输出 “YES” 并在第二行输出这个序列。
解题
分情况讨论，当 (n/2) 是奇数时，奇数个偶数相加为偶数，奇数个奇数相加为奇数，前后半段和不可能相等，所以此时不存在目标序列。
当 (n/2) 是偶数时，前半段以 (2,4,6,...,2i-2,2i) 的形式填充，其和为 (sum_1 = i(i+1) = frac{n^2}{4}+frac{n}{2}) 。后半段以 (1,3,5,..,2i-5,2i-3,x) 的形式填充，其和为 (sum_2 = (frac{n}{2}-1)^2+x) ，可以求出 (x) 值为 (sum_1-sum_2 = frac{3}{2}n-1) 。这时序列满足条件。
for t in range(int(input())):
n = int(input())
if((n/2)%2!=0):
print("NO")
continue
else:
print("YES")
for i in range(1,n//2+1):
print(2*i,end=' ')
for i in range(1,n//2):
print(2*i-1,end=' ')
print(3*n//2-1)
C. Alternating Subsequence
题意
给定一个序列（序列不含0），询问其最长正负交替子序列的最大和。
解题
贪心，从每个连续同符号子段中取出值最大的，组成的序列即为所求。
for t in range(int(input())):
n = int(input())
l = 0;s = 0
maxV = 0
for a in list(map(int,input().split())):
if(l==0 or maxV*a<0):
s+=maxV
l+=1
maxV = a
elif(maxV*a>0):
maxV = max(maxV,a)
print(s)
D. Constant Palindrome Sum
题意
假设有一种正整数特殊序列，满足下列条件：
- 所有的元素小于等于 (k) ，即 (a_ile k)；
- 任意的 (a_i+a_{n-i+1} = x) ，(x) 是某常数。
给定一个正整数序列和 (k) ，询问将该序列变成上述特殊序列，最少需要替换多少个元素。
解题
起初以为确定 (x) 的值是关键，只需要找到使得替换次数最少的 (x) 的即可。但是这题数据 (On^2) 指定过不了，二分也没有明确的单调关系（头大
可以先假设一下，如果我们已经确定了 (x) 的值。对于每一对元素，需要替换的个数 (d_i) 值为
，设 (D_x) 为总替换次数，即 (D_x = sum_{i=1}^nd_i) 。从 ([2,2k]) 区间内的任何一个数都可以成为 (x) ，而且都有其对应的 (D_x) 。
可以发现，每一对 (a_i,a_{n-i+1}) 的值都影响着一片区域内 (D_x) 的值，我们可以用线段树快速求出区间内的所有 (D_x) 。（见到区间就想线段树，已经没救了）
- 初始化 (D_x = 0,x in [2,2k])
- 遍历所有的元素对：
- (p_{i} = min(a_i,a_{i+1}), q_{i} = max(a_i,a_{i+1}))
- 区间 (xin [p_i+1,q_i+k]cap complement_u{p_i+q_i}) 内的 (D_x = D_x+1)
- 区间 (xin [2,p_i+1)cup(q_i+k,2k]) 内的 (D_x = D_x+2)
- 最后 (ans = min(D_x))
复杂度 (O(nlogk)) 理论上是可以过题的，但是 Div.3 写线段树，简直是冤大头。
再仔细思考下，我们对 (D) 序列只有一次查询，即最后的 (ans = min(D_x),xin [2,2k]) ，可以使用差分替代线段树。设 (m_x = D_{x} - D_{x-1},xgt 1) ，且 (m_1 = n) ，则 (D_x = sum_{i=1}^x m_i) 。每一对 (a_i,a_{n-i+1}) 仅仅影响着几个 (m_x) 值。
- 初始化 (m_x = 0,xin [1,2k])
- 遍历所有的元素对：
- (p_{i} = min(a_i,a_{i+1}), q_{i} = max(a_i,a_{i+1}))
- (m_{p_i+1} = m_{p_i+1}-1;)
- (m_{p_i+q_i} = m_{p_i+q_i}-1;)
- (m_{p_i+q_i+1} = m_{p_i+q_i+1}+1;)
- (m_{q_i+k+1} = m_{q_i+k+1}+1;)
- 最后 (ans = min(D_x) = min( sum_{i=1}^x m_i))
复杂度 (O(n))，比线段树代码短几十行。
def scanf():
return list(map(int,input().split()))
for t in range(int(input())):
n,k = scanf()
a = [0]+scanf()
m = [0 for i in range(2*k+2)]
m[1] = n
for i in range(1,n//2+1):
p = min(a[i],a[n-i+1])
q = max(a[i],a[n-i+1])
m[p+1]-=1
m[p+q]-=1
m[p+q+1]+=1
m[q+k+1]+=1
ans = 9e18; D=m[1]
for mit in m[2:]:
D += mit
ans = min(ans,D)
print(ans)
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
