牛客算法課 (算法入門班) 貪心與模擬(2)

一開始以為是個圖論題, 想著跑n 次 dijistra, 把每個點的最短距離求出來, 然後一個一個找, 但是會超時 而且很笨.

其實這一題也可以利用滑動窗口來做.

首先, 你知道小朋友永遠選擇最短距離走. 如果這個距離過半了, 他會選擇走另一條路. 

你就把窗口定義為, 每個小朋友找他的最遠小朋友的距離. 維護的方法就是不過總距離的一半, 盡可能的往下個小朋友靠. 

如果發現某一個小朋友, 他再繼續下去 就過半了, 我們就換一個縮短窗口, 也就是換一個小朋友. 同時間更新答案.

#include
#include
using namespace std;
int main(){
    int n, l = 1, r = 1, sum = 0, ans = -1;
    int a[100000];
    cin >> n;
    memset(a, 0, sizeof(a));
    int totDis = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        totDis += a[i];
    }
    int halfDis = totDis/2;
    while(r <= n){
        if(sum <= halfDis){
            sum += a[r];
            r++;
        }else if(sum > halfDis){
            sum -= a[l];
            l++;
        }
        if(sum <= halfDis)ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

其實不難發現 x 的數字範圍是0 到 3. 它表明附件必須有一定數量的雷. 

我們從第一格開始走起, 就跟著他旁邊給的資訊慢慢更新我佈雷的b數組.

然後代碼就非常簡單了.

#include
#include
using namespace std;
int n, ans = 0;
vector a(10002, 0);
vector b(10002, 0);
bool work(){
    for(int i = 2; i <= n; i++){
        //我們現在處於第3個格子, 按照謎語的提示 只填寫剩餘的雷數
        b[i] = a[i - 1] - b[i - 1] - b[i - 2];
        if(b[i] != 0 && b[i] != 1)return 0;
    }    
    return a[n] == (b[n - 1] + b[n]);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    b[1] = 0;
    if(work())ans++;
    b[1] = 1;
    if(work())ans++;
    cout << ans; 
}

一道不錯的題.

首先糖糖是不可以進行排序 *** 作的因為會打亂順序.

但是基於觀察你不難發現, 其實你只需要記錄每一組的最大值, 然後我們就可以分開討論不同組的情況.

我們還是優先解決 發功的問題.

觀察發現, 發功只對前面的東西有效, 也就是對後面的東西沒效, 在這裡如果你用暴力幫所有糖糖加

分, 會超時. 所以我們學過的東西只有差分, 前綴和, 還有滑動窗口這幾個知識點. 

滑動窗口沒啥用.

那麼考慮差分. 誒! 你會發現其實c 就是一個變量, 表示前面的數字都受到這個變量的影響, 後面不會. 我們在課上學是差分對後面的有影響. 所以這裡你會覺得有點吊櫃啦.

所以這種後差分, 當然不會配前綴和, 而是配後綴和. 我們就可以O(n)算到每一個糖糖家了多少分.

既然發功解決了, 那麼就剩下糖糖自己怎麼解決了.

我們發現, 題目說 後面可以刪除前面的. 是不是說明後面的數字如果夠大,前面的人都要死光. 

如果順序枚舉並不能更新全局的最大值. 所以我們直接倒著枚舉, 我們每一次都更新不同組的最大值. 

然後比較. 我們假設 ans 一開始就是n, 只要能被刪除就減1/

#include
using namespace std;
int T, n, m;
struct node{
    int group = 0, score = 0;
};
void work(){
    vector b(50011);
    vector c(50011, 0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)cin >> b[i].group >> b[i].score;
    for(int i = 1; i <= m; i++){
        int x;
        cin >> x;
        c[x]++;
    }
    //prefixSum for c
    for(int i = n; i >= 1; i--){
        c[i] += c[i + 1];
        //add all scores
        b[i].score +=c[i];
    }
    int max0 = -1;
    int max1 = -1;
    int ans = n;
    for(int i = n; i >= 1; i--){
        if(b[i].group == 1){
            max1 = max(max1, b[i].score);
            if(b[i].score < max0)ans--;
        }else{
            max0 = max(max0, b[i].score);
            if(b[i].score < max1) ans--;
        }
    }
    cout << ans << endl;
}
int main(){
    cin >> T;
    while(T--){
        work();
    }
    return 0;
}

枚舉中線.

由於要求區間和, 所以前綴和這個 *** 作必不可少.

假設自己有一條中線在k這個位置, 然後你可以先把 中線左邊的 k區間算出總和, 用一個max 把他記下來, 然後我們再嘗試把右半區間加上去,看看能不能得到更大的值, 如果可以就更換我們的答案.

如果不能就跳過.

我們每一次遇到更好的值的時候都會更新左半區間, 如果不能更新, 我們就會帶著這個區間, 一直走下去 和不同的右半區間進行匹配並且更新我們的答案, 所以, 這樣子做不但能避免重合還能不斷更新最大值.

#include
#include
using namespace std;
void work(){
    int n, k;
    cin >> n >> k;
    vector a(n + 1, 0);
    for(int i = 1; i<= n; i++){
        cin >> a[i];
        //prefixSum
        a[i] += a[i - 1];
    }
    //maintain two sliding window
    long long ans1 = -1e18, ans2 = -1e18;
    for(int mid = k; mid + k <= n; mid++){
        long long newSum1 = a[mid + k] - a[mid];
        long long newSum2 = a[mid] - a[mid - k];
        ans2 = max(ans2, newSum2);
        ans1 = max(ans1, ans2 + newSum1);
    }
    cout << ans1<< endl;
}
int main(){
    int T;
    cin >> T;
    while(T--){
        work();
    }
}

首先, 由於n只有1000, 我們可以考慮 n^2 時間的解.

異或的意思是只有兩邊一樣的之後, 異或才會有0, 不然就是其他解.

所以我們跟之前一樣, 枚舉中間點, 計算左邊不同和異或結果有什麼, 然後, 遍歷右邊, 如果發現結果有一樣的, 就直接返回左邊之前記錄的出現次數.

那有沒有方法可以直接用一個O(1)的 *** 作, 得到某個區間全部異或的結果呢?

其實異或前綴和和普通前綴和一樣.

那為什麼可行呢?

因為 任何數字xor 0, 都會不會發生改變. 也就是說, 你把 [a1, a2, a3.... ai] 這段區間的異或結果 跟[a1, a2, a3]的異或結果, 異或一下, 那麼a1,a2,a3 由於是一樣的所以, 變成了0, 那麼就剩下a4....ai的異或結果了.

//异或前缀和数组
//两个相同的数异或为0
//异或是一种非进制加法，0对异或的值没有影响
#include 
using namespace std;

int a[1005];
mapmp;

int main() {
    long long ans=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        a[i]^=a[i-1];
    }
    for(int i=1;i<=n;i++) {
        for(int j=0;j 
 NC19913[CQOI2009] 中位數圖 
做法幾乎跟上面一樣, 由於中位數必須滿足, 左右出現的比b大和小的數字相同的次數, 所以, 我們在這裡考慮把所有比b大的數字 都改成1, 比b小的數字改成-1, 然後求前綴和.
 
然後我們就可以枚舉中點, 然後看看他的左邊分別的前綴和是多少, 如果他和後綴和相加等於0, 表明這個區間中比b大和比b小的數字的出現次數是一樣的.
 
幾乎和上面的統計方法是一摸一樣的
 
#include
#include
#include
 
「土」秘法地震 (垃圾題目, 知道原理就行不要做, 他媽的什麼狗屎輸入, 用cin 就沒辦法做) 
首先, 我們要計算矩陣的前綴和, 和一開始的機關炸彈一樣做法. 然後就是求k*k矩陣中大於0 的矩陣和數量就行了.
 
公式就是 dp[i][j] - dp[i - k][j] - dp[i][j - k] - dp[i-k][j-k]
 
你用圖表畫一次就知道為什麼公式是這樣了.
 
//前缀和不为0，就加上1
#include 
using namespace std;
#define M 1005
 
int a[M][M];
 
int main() {
    int n,m,k,ans=0;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for(int i=k;i<=n;i++)
        for(int j=k;j<=m;j++)
            if(a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]!=0)ans++;
    cout<
 
仓库选址 
 
可以觀察到, 從一個點走去令一個點帶來的變化量, 就是格子內貨品的需求量 * 距離.
 
我們想辦法把距離前綴和求出來, 然後我們就可以跟著y的水平移動來判別, 全部點走到哪一個點貨費最少.
 
一開始是所有點到(1, 1)這個格子的總距離, 然後就是平移到(1, 2) 的距離, 那麼該怎麼求呢?
 
由於水平移動 (1, 2)到(n,m)這個矩形所有的距離都會減1, 所以我們直接減掉這個矩陣的距離和一次就行了.  所以就是 (1, 1)總開銷 + (1, n)的開銷增加 - (1,2) 到(n,m)的開銷減少. 如此類推.
 
  
 
#include
#include
#include
using namespace std;
int grid[1005][1005];
inline int matrixSum(int A,int B,int C,int D){
    return grid[C][D]-grid[A-1][D]-grid[C][B-1]+grid[A-1][B-1];
}
int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> m >> n;
        int now = 0, nxt = 0, ans = 0x3f3f3f3f;
        memset(grid, 0, sizeof(grid));
        int x;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> x;
                //now 是每個點到(1, 1)總距離 乘以 人數 
                now+=(i-1+j-1)*x;
                grid[i][j]=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1]+x;
            }
        }
        //我們把每一行的最優值找出來, 和ans比較
        //然後進入每次進入下一行, 就更新每個點到(i, 1)的總距離和.
        //這樣做的好處是不用管什麼時候應該處理垂直變化和橫向變化
        for(int i=1; i<=n; i++){
            nxt = now;
            for(int j=1; j<=m; j++){
                ans=min(ans,nxt);
                //把每個人子矩陣中的人數走多了的減去走少了的, 就是下個點的距離
                nxt+=matrixSum(1,1,n,j)-matrixSum(1,j+1,n,m);
            }
            //把每個人子矩陣中的人數走多了的減去走少了的, 就是下個點的距離, 垂直的走
            now+=matrixSum(1,1,i,m)-matrixSum(i+1,1,n,m);
        }
        cout << ans << endl;
    }
}
 
牛牛的木板 
這裡總共有兩種做法,第一種是滑動窗口, 另一種和滑動窗口做法差不多,但是比較簡單.
 
先說滑動窗口, 只要我們當前窗口內的黑色數量不多於m, 我們就繼續擴大窗口, 不然就縮窗口直到裡面的黑色少一個, 我們就又有能力往右擴展.
 
class Solution {
public:
    int solve(int n, int m, vector& a) {
        // write code here
        int l = 0, r = 0, temp= 0, ans = 0;
        while(r < n){
            if(!a[r]){
                temp++;
            }
            while(temp > m){
                if(!a[l])temp--;
                l++;
            }
            ans = max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
};
 
第二種方法, 就是每次我沒把不同累積出現的黑色數目最後一個的坐標記下來, 我們每次都把當前坐標之前的所有m個黑色變成白色, 看看最大長度是多少. 
 
其實就像是前綴和, 不過是記錄黑色的前綴和. 把前綴和當成index, 然後把坐標放在裡面.
 
假如說我們的a 數組 遍歷到了第9位, 目前總共出現了6次黑色. 而m 是3. 我們可以去找第3次黑色出現的位置, 然後統計長度, 因為這中間只有3個黑色, 全都是我們可以轉化.
 
class Solution {
public:
    int b[1000006];
    int tot=0,ans=0;
    int solve(int n,int m,vector&a) {
        b[0]=-1;
        for(int i=0;i
 
[SCOI2009]生日礼物 
也是滑動窗口, 保證窗口裡有k種不同就可以, 如果有k種了, 就縮小窗口, 跟之前做法一樣.
 
唯一要留意的地方`是離散化, 由於同一個地方可以出現多過一種彩帶, 所以用一個結構體把他存下來.
 
#include 
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct vv{
    ll col,pos;
}a[N];
int cnt[N];

bool cmp(vv x,vv y)
{
    if(x.pos==y.pos) return x.col1) {cnt[a[l].col]--; l++; }
            ans=min(ans,a[r].pos-a[l].pos);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/langs/1353523.html