[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;
}

总结

期望得分:100 + 100 + 0 = 200
实际得分:100 + 100 + 0 = 200
t3的70分没拿实在可惜。前两题还可以。t1第一次写的时候bug较多。

一言

好几次张口却发现,想说的那么多,能说的却那么少,况且这世界也已经够吵。 ——这世界已经够吵了

原文地址:https://www.cnblogs.com/wxyww/p/9851451.html