[20181025上午][模拟赛]

T1

思路

直接模拟每一秒发生的变化并且用优先队列优化一下，可以拿到80分。然后发现中间一些时间什么事情都没有干。所以可以直接跳过那些无贡献的时间。时间复杂度为\(O(mlogn)\)

代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define pi pair<int,int>
using namespace std;
const int N = 100000 + 100;
typedef long long 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;
}
int n ,m ,x;
int ans2;
int a[N];
priority_queue<pi,vector<pi>,greater<pi> > q;
int main() {
    freopen("fish.in","r",stdin);
    freopen("fish.out","w",stdout);
    int m = read(),n = read(),x = read();//m是鱼的数量，x是时间，n是猫 
    for(int i = 1;i <= n;++i) {
        int x = read();
        q.push(make_pair(x,x));
        m--;
    }
    int now = 1;
    for(;now < x&&m;++now) {
        while(!q.empty()) {
            pi k = q.top();
            if(k.first > now) {
                now = k.first - 1;
                break;
            }
            q.pop();
            q.push(make_pair(k.second+now,k.second));
            m--;
            if(!m) break;
        }
    }
    while(!q.empty()) ans2 += q.top().first > x,q.pop();
    cout<<m<<" "<<ans2;
    return 0;
}

T2

思路

先去写了一个背包，然后过了小样例，没过大样例。然后觉着肯定要排序，试了五六种排序方法，过了大样例。

代码

/*f[i][j]表示前i个物品剩余j的钱所能得到的最大价值
if(j + p[i] >= q[i])
f[i][j] = max(f[i - 1][j + p[i]] + v[i],f[i - 1][j]) 
else f[i][j] = f[i - 1][j]
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1000 + 100,M = 5000 + 100;
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 f[N][M];
int n ,m;
struct node{
    int p,q;
    ll v;
}a[N];

bool cmp(node x,node y) {
    return x.q - x.p > y.q - y.p;
}
void solve() {
    for(int i = 1;i <= n;++i) {
        for(int j = 0;j <= m;++j) {
            if(j + a[i].p > m || j + a[i].p < a[i].q) {
                f[i][j] = f[i - 1][j];
                continue;
            }
            f[i][j] = max(f[i-1][j],f[i-1][j + a[i].p] + a[i].v);
        }
    }
    ll ans = 0;
    for(int i = 0;i <= m;++i)
        ans = max(ans,f[n][i]);
    cout<<ans;
}
void solve1() {
    for(int i = 1;i <= n;++i) {
        for(int j = 0 ;j <= m;++j) {
            if(j > a[i].p)
            f[i][j] = max(f[i-1][j - a[i].p] + a[i].v , f[i-1][j]);
            else f[i][j] = f[i-1][j];
        }
    }
    ll ans = 0;
    for(int i = 0;i <= m;++i) ans = max(ans,f[n][i]);
    cout<<ans;
}
int main() {
    freopen("bag.in","r",stdin);
    freopen("bag.out","w",stdout);
    n = read(),m = read();
    int bz1 = 0;
    for(int i = 1;i <= n;++i) {
        a[i].p = read();a[i].q = read();a[i].v = read();
        if(a[i].p != a[i].q) bz1 = 1;
    }
    if(!bz1) {
        solve1();
        return 0;
    }
    sort(a + 1,a + n + 1,cmp);
    solve();
    return 0;
}

T3

思路

对于前70分，直接模拟就行了。将走过的位置标记一下，然后从外部bfs一遍。标记过的点不入队。bfs不到的点就是答案了。剩下的三十分离散化一下。似乎很麻烦，留个坑吧

70分代码

#include<cstdio>
#include<iostream>
#include<queue>
#define pi pair<int,int>
using namespace std;
const int N = 2018;
typedef long long ll;
int dx[5] = {0,1,-1,0,0};
int dy[5] = {0,0,0,1,-1}; 
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;
}
int a[N + 10][N + 10];
int X,Y;
queue<pi>q;
int bfs() {
    int ans = 0;
    q.push(make_pair(1,1));
    ans++;
    a[1][1] = 1;
    while(!q.empty()) {
        int x = q.front().first,y = q.front().second;
        q.pop();
        for(int i = 1;i <= 4;++i) {
            int x_ = x + dx[i],y_ = y + dy[i];
            if(!a[x_][y_] && x_ <= 2018 && x_ >= 1 && y_ <= 2018 && y_ >= 1) {
                ans++;
                a[x_][y_] = 1;
                q.push(make_pair(x_,y_));
            }
        }
    }
    return ans;
}
int main() {
    freopen("beng.in","r",stdin);
    freopen("beng.out","w",stdout);
    int k = read();
    X = 1005,Y = 1005;
    char c;
    int b;
    a[X][Y] = 1;
    while(k--) {
        cin>>c;b = read();
        if(c == 'U') {
            int To = X - b;
            while(X >To) {
                X--;
                a[X][Y] = 1;
            }
        }
        if(c == 'D') {
            int To = X + b;
            while(X < To) {
                X++;
                a[X][Y] = 1;
            }
        }
        if(c == 'L') {
            int To = Y - b;
            while(Y > To) {
                Y--;
                a[X][Y] = 1;
            }
        }
        if(c == 'R') {
            int To = Y + b;
            while(Y < To) {
                Y++;
                a[X][Y] = 1;
            }
        }
    }
    cout<<N * N - bfs();
    return 0;
}