發表新討論
#34483: 解題報告


dfd8282@gmail.com (fishhh)

d537. 4. 染色遊戲 -- 98學年度 北基區 資訊學科能力競賽 | From: [36.239.44.132] | 發表日期: 2023-03-23 21:18

在輸入每個顏色的時候紀錄每個顏色跑到第 [i][j] 時的最小時間即為 max(abs(x-i),abs(y-j))

接下來對於每個位置每個顏色的出現時間做排序 排序完後依序把顏色出現時間、結束時間打上差分序列就好了

for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
            pii vp[5];
            for(int i=1;i<=3;i++){
                vp[i-1] = {tt[j][k][i],i};
            }
            for(int i=0;i<3;i++){
                for(int j=i+1;j<3;j++){
                    if(vp[j]<vp[i])swap(vp[i],vp[j]);
                }
            }
            // sort(all(vp));
            cal[vp[0].first][(1<<(vp[0].second-1))]++;
            cal[vp[1].first][(1<<(vp[0].second-1))]--;
            cal[vp[1].first][(1<<(vp[0].second-1)|(1<<(vp[1].second-1)))]++;
            cal[vp[2].first][(1<<(vp[0].second-1)|(1<<(vp[1].second-1)))]--;
            cal[vp[2].first][7]++;
        }
    }

最後就遍歷一次差分序列就可以知道最多出現的次數了~

 

#34484: Re: 解題報告


dfd8282@gmail.com (fishhh)

d537. 4. 染色遊戲 -- 98學年度 北基區 資訊學科能力競賽 | From: [36.239.44.132] | 發表日期: 2023-03-23 21:21

複雜度 O(n^2) 可以過 n<=1000 的狀況

那個 sort 會被我註解掉是因為會被卡常><

ZeroJudge Forum