Codeforces Round #636 (Div. 3) A~D

http://codeforces.com/contest/1343/

A. Candies

題意

給定一個 \(n\) ，詢問任意一個 \(x\) 滿足 \(x+2x+4x+?+2^{k?1}x=n,k\gt1\)，題目保證存在至少一個 \(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 = \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_i\le k\)；
• 任意的 \(a_i+a_{n-i+1} = x\) ，\(x\) 是某常數，

給定一個正整數序列和 \(k\) ，詢問將該序列變成上述特殊序列，最少需要替換多少個元素，

解題

起初以為確定 \(x\) 的值是關鍵，只需要找到使得替換次數最少的 \(x\) 的即可，但是這題資料 \(On^2\) 指定過不了，二分也沒有明確的單調關系（頭大

可以先假設一下，如果我們已經確定了 \(x\) 的值，對于每一對元素，需要替換的個數 \(d_i\) 值為

\[p_{i} = min(a_i,a_{i+1}),\ \ q_{i} = max(a_i,a_{i+1}),\\ d_i = \left\{ \begin{array}{**lr**} 0 & p_i+q_{n-i+1} = x\\ 1 & p_i+1\le x\le q_i+k,\ \ x\ne p_i+q_{n-i+1}\\ 2 & p_i+1\gt x \ \ \lor \ \ q_i+k\lt x \end{array} \right. \]

，設 \(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})\)
  • 區間 \(x\in [p_i+1,q_i+k]\cap \complement_u\{p_i+q_i\}\) 內的 \(D_x = D_x+1\)
  • 區間 \(x\in [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),x\in [2,2k]\) ，可以使用差分替代線段樹，設 \(m_x = D_{x} - D_{x-1},x\gt 1\) ，且 \(m_1 = n\) ，則 \(D_x = \sum_{i=1}^x m_i\) ，每一對 \(a_i,a_{n-i+1}\) 僅僅影響著幾個 \(m_x\) 值，

• 初始化 \(m_x = 0,x\in [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)

標籤：其他

上一篇：CF1327E Count The Blocks（組合數學，計數）

下一篇：HashMap淺析