首页 > > 程序设计 > C/C++ >

正睿暑期培训day4考试

2019-08-16 08:01:06来源：博客园阅读 ()

正睿暑期培训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;
}