正睿暑期培訓day4考試

鏈接

A

求出來到每座山的距離後，就可以計算出每隻貓等待的時間與出發時間的關係。

如果出發時間為\(x\),求出來只貓的等待時間。這裡用\(b_i\)表示第i只貓的等待時間。然後我們將這些時間排序。問題就轉化為了，從m個有序的數中，選出p個，每個數字覆蓋以其為開頭的一段區間。這段區間的貢獻為\(x\times num-sum\),其中x為當前選定的數字。\(num\)為覆蓋區間的長度。\(sum\)為覆蓋區間的數字和。

這樣就可以得到一個\(m^2p\)的朴素dp。
\(f[i][j]\)表示選出i個點，覆蓋前j個元素，最小貢獻。
\(f[i][j]=\min\limits_{k=1}^i\{f[i-1][k - 1]+b[k]\times j+(j-k)\times b[k]-(sum[j]-sum[k]))\}\)

然後就很斜率優化了。。。

/*
* @Author: wxyww
* @Date: 2019-08-07 19:31:15
* @Last Modified time: 2019-08-07 19:49:05
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 50010,M = 1010;
#define int ll
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll sum[N];
int n,m,p,f[N],g[N],a[N];
ll b[N];
ll B(int x) {
    return sum[x] - x * b[x] + g[x - 1];
}
bool cmp(int x,int y) {
    return x > y;
}
int q[N];
int calc(int x,int y) {
    return b[x] * y  + B(x);
}
bool check(int p1,int p2,int p3) {
    return 1ll * (B(p2) - B(p3)) * (b[p3] - b[p1]) > 1ll * (B(p1) - B(p3)) * (b[p3] - b[p2]);
}
 main() {
    n = read(),m = read(),p = read();
    for(int i = 2;i <= n;++i) a[i] = a[i - 1] + read();
    for(int i = 1;i <= m;++i) {
        int x = read(),y = read();
        b[i] =  y - a[x];
    }

    sort(b + 1,b + m + 1,cmp);

    for(int i = 1;i <= m;++i) sum[i] = sum[i - 1] + b[i];

    memset(f,0x3f,sizeof(f));
    f[0] = 0;
    for(int j = 1;j <= p;++j) {
        for(int i = 0;i <= m;++i) g[i] = f[i];
        memset(f,0x3f,sizeof(f));
        f[0] = 0;
        int head = 1,tail = 0;
        for(int i = 1;i <= m;++i) {
            while(head < tail && check(q[tail],q[tail - 1],i)) --tail;
            q[++tail] = i;
            while(head < tail && calc(q[head + 1],i) <= calc(q[head],i)) ++head;
            f[i] = calc(q[head],i) - sum[i];
        }
    }

    cout<<f[m]<<endl;
    return 0;
}

B

非常interesting的一道題。

考慮倒著做。用某大佬的話說就是"拔地鼠"，只有當某個位置所在的行和列不含有除這個位置外的地鼠，這個位置才可以被"拔出來"。我們將其拔出來之後，將他所在的行和列都標記為灰色。表示可能為白色(有地鼠)，也可能為黑色(無地鼠)。

然後開始bfs,將儘量多的點刷為灰色。

最後比較一下非灰色的點是不是與初始狀態相同。

需要特判初始狀態本就與終止狀態相同的情況。還有，如果某一行和某一列都為灰色，那麼他們的交點處初始必須是白色。否則就無法開始。

/*
* @Author: wxyww
* @Date: 2019-08-07 20:10:07
* @Last Modified time: 2019-08-07 20:26:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s1[N][N],s2[N][N];
int sum1[N],sum2[N],vis1[N],vis2[N],vis[N][N],col[N][N];
queue<pair<int,int> >q;
int main() {
    int n = read(),m = read();
    int bz = 0;
    for(int i = 1;i <= n;++i) scanf("%s",s1[i] + 1);
    for(int i = 1;i <= n;++i) scanf("%s",s2[i] + 1);
    for(int i = 1;i <= n;++i) 
        for(int j = 1;j <= m;++j) 
            if(s1[i][j] != s2[i][j]) bz = 1;
    if(!bz) {
        puts("1");return 0;
    }

    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            if(s2[i][j] == 'X') {
                sum1[i]++;sum2[j]++;
                col[i][j] = 1;
            }
        }
    }

    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            if(s2[i][j] == 'X' && sum1[i] == 1 && sum2[j] == 1) {
                q.push(make_pair(i,j));
                vis[i][j] = 1;
            }
        }
    }

    while(!q.empty()) {
        int x = q.front().first,y = q.front().second;q.pop();
        if(vis1[x] <= 2) {
            vis1[x]++;
            for(int i = 1;i <= m;++i) {
                if(col[x][i] == 1) {
                    sum1[x]--;sum2[i]--;
                }
                col[x][i] = 2;
            }
            for(int i = 1;i <= m;++i) 
                if(!vis[x][i] && !sum1[x] && !sum2[i])  q.push(make_pair(x,i)),vis[x][i] = 1;
        }
        if(vis2[y] <= 1) {
            vis2[y]++;
            for(int i = 1;i <= n;++i) {
                if(col[i][y] == 1) sum1[i]--,sum2[y]--;
                col[i][y] = 2;
            }
            for(int i = 1;i <= n;++i) 
                if(!vis[i][y] && !sum1[i] && !sum2[y]) q.push(make_pair(i,y)),vis[i][y] = 1;
        }
    }
     bz = 0;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            if(s1[i][j] == 'O' && vis1[i] && vis2[j]) bz = 1;
        }
    }
    if(!bz) {
        puts("0");return 0;
    }
    bz = 0;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            if(!vis1[i] && !vis2[j] && s1[i][j] != s2[i][j]) bz = 1; 
        }
    }
    if(bz) puts("0");
    else puts("1");

    return 0;
}

C

毒瘤防AK題。。。並不想寫。

總結

T1一開始寫了一個假的dp，浪費了大量時間。T2騙分成分較大，數據有點水。T3到最後有點著急，沒寫出來。。。

T1這種簡單題應該做對並及時對拍。T2沒思路只能亂搞了。T3.。。。