Solution Idea

50097. Conveyor Belt

參考解答

  • 移動array 中的element 時,若一次只移動一個element,將因為運算量太多造成TLE。

  • 正確的作法為一次將移動$(T/64)mod N$ 個element,並且需要一塊額外記憶體儲存這些element:

    • 此額外記憶體因為容量過大,若直接宣告在function 內將造成RE,合適的作法為宣告在global 或者在function 內宣告為static。
    • 可以使用<string.h> 中的memcpymemmove function 一次移動整塊記憶體記憶體內容。
  • 此題的bit operation 有很多種做法,提供兩種想法:

    • 可如同程式cast 成 unsigned long long 在作運算。
    • 若left shift k bit,為了記錄左方k bit,也可以用$(1LL \lt \lt ( 64 - k ) )-1LL$ 為mask 搭配and operation 避免對負數作right shift operation 所產生的錯誤結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<string.h> // for memcpy and memmove
#include"transmission.h"
#define MAXSIZE 1048576
void shiftWord(long long belt[],int N,int nWord){
    static long long buffer[MAXSIZE];
    memcpy(buffer,belt,sizeof(long long)*nWord);
    memmove(belt,belt+nWord,sizeof(long long)*(N-nWord));
    memcpy(belt+N-nWord,buffer,sizeof(long long)*nWord);
}
void shiftOffset(long long belt[],int N,int nOffset){
    if(nOffset==0)
        return;
    long long shiftLeft=(long long)nOffset;
    long long shiftRight=64LL-shiftLeft; // 64LL makes compiler consider constant 64 as a long long value
    long long leftmost=(unsigned long long)belt[0]>>shiftRight;
    for(int i=0;i<N-1;i++){
        belt[i]<<=shiftLeft;
        belt[i]|=(unsigned long long)belt[i+1]>>shiftRight;
    }
    belt[N-1]<<=shiftLeft;
    belt[N-1]|=leftmost;
}
void transmission(long long belt[],int N,int T){
    shiftWord(belt,N,(T>>6)%N);
    shiftOffset(belt,N,T&63);
}

Discussion