减舟's Blog

D1T1 铺地毯

#include <cstdio>
const int MAXN = 100001;
int n, x, y, a[MAXN], b[MAXN], g[MAXN], k[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &a[i], &b[i], &g[i], &k[i]);
	scanf("%d%d", &x, &y);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] <= x && x <= a[i] + g[i] && b[i] <= y && y <= b[i] + k[i])
			ans = i;
	printf("%d\n", ans);
	return 0;
}

D1T2 选择客栈

#include<cstdio>
using namespace std;
int f[200001], sav[200001], ans[200001], num[200001];
int n, p, k, cnt = 0;

int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++) {
		int color, cost;
		scanf("%d%d", &color, &cost);
		if (cost <= p) f[i] = f[i - 1] + 1; 
    		else f[i] = f[i - 1];
    	if (sav[color] == 0) {
        	sav[color] = i; num[color]++; continue;
    	}
      	if (f[i] - f[sav[color] - 1] > 0) ans[i] = num[color];
      		else ans[i] = ans[sav[color]];
      	sav[color] = i;
      	num[color]++;
    }   
    for (int i = 1; i <= n; i++) cnt += ans[i];
    printf("%d\n", cnt);
    return 0;
}

D1T3 Mayan游戏

    Mayan游戏写起来比较棘手，做法的话，就是上DFS。有两个剪枝操作：某种颜色存在但是个数小于3没法消除；如果一个方块左边也是方块就不必左移，因为右移效果一样字典序更小。

#include <cstdio>
#include <cstdlib>
#include <cstring>
void swap(int &a, int &b) {
	int c = a; a = b; b = c;
}

int n;

struct map {
	int a[5][7];
	bool d[5][7];
	
	void Read() {
		memset(a, 0, sizeof(a));
		memset(d, 0, sizeof(d));
		for (int i = 0; i < 5; i++) {
			int t1, t2 = 0;
			scanf("%d", &t1);
			while (t1) {
				a[i][t2++] = t1; scanf("%d", &t1);
			}
		}
	}
	
	void Falldown(int i) {
		int pop = 0;
		for (int j = 0; j < 7; j++)
			if (a[i][j]) {
				a[i][pop++] = a[i][j];
				if (j >= pop) a[i][j] = 0;
			}
	}
	
	void Fall() {
		for (int i = 0; i < 5; i++) Falldown(i);
	}
	
	bool Combo() {
		memset(d, 0, sizeof(d)); bool ret = 0;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++) {
				if (a[i][j] == 0) continue;
				
				if (0 < i && i < 4)
					if (a[i - 1][j] == a[i][j] && a[i][j] == a[i + 1][j]) {
						d[i - 1][j] = d[i][j] = d[i + 1][j] = 1;
						ret = 1;
					}
				if (0 < j && j < 6)
					if (a[i][j - 1] == a[i][j] && a[i][j] == a[i][j + 1]) {
						d[i][j - 1] = d[i][j] = d[i][j + 1] = 1;
						ret = 1;
					}
			}
		return ret;
	}
	
	void Collapse() {
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (d[i][j]) a[i][j] = 0;
		memset(d, 0, sizeof(d));
	}
	
	void Move(int i, int j, int k) {
		swap(a[i][j], a[i + k][j]);
		Falldown(i), Falldown(i + k);
		while (Combo()) {
			Collapse(); Fall();
		}
	}
	
	bool Empty() {
		for (int i = 0; i < 5; i++)
			if (a[i][0]) return 0;
		return 1;
	}
	
	int GetMin() {
		int cnt[11] = {0};
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (a[i][j]) cnt[a[i][j]]++;
		int min = 35;
		for (int i = 1; i <= 10; i++)
			if (cnt[i] && cnt[i] < min) min = cnt[i];
		return min;
	}
} sta;

struct Node {
	int a, b, c;
	
	void Load(int A, int B, int C) {
		a = A, b = B, c = C;
	}
} ans[100];
	
void dfs(int t) {
	if (sta.Empty()) {
		for (int i = 1; i <= t; i++)
			printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
		exit(0);
	}
	if (t == n) return;
	if (sta.GetMin() <= 2) return;
	map bak = sta;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 7; j++) {
			if (sta.a[i][j] == 0) continue;
			if (i < 4 && sta.a[i][j] != sta.a[i + 1][j]) {
				ans[t + 1].Load(i, j, 1); sta.Move(i, j, 1);
				dfs(t + 1);
				sta = bak;
			}
			if (i > 0 && sta.a[i - 1][j] == 0) {
				ans[t + 1].Load(i, j, -1); sta.Move(i, j, -1);
				dfs(t + 1);
				sta = bak;
			}
		}
}
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	sta.Read();
	dfs(0);
	printf("-1\n");
	return 0;
}

D2T1 计算系数

    杨辉三角就可以了～

#include <cstdio>
#include <algorithm>
const int M = 10007;
using namespace std;

int f[1001][1001];
int a, b, k, n, m;

int main() {
	long long ans = 1;
	scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
	f[1][1] = f[1][2] = 1;
	for (int i = 2; i <= k; i++) 
		for (int j = 1; j <= i + 1; j++)
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % M;
	ans = f[k][m + 1];
	for (int i = 1; i <= n; i++) ans = (ans * a) % M;
	for (int j = 1; j <= m; j++) ans = (ans * b) % M;
	printf("%d", ans);
	return 0;
}

D2T2 聪明的质检员

    二分法计算就可以了。P.S.VIJOS是windows评测，我一开始%lld没过，然并卵

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

long long n, m, S, w[200001], v[200001], l[200001], r[200001], arr[200001];
long long sum1[200001], sum2[200001];

long long fun(int k) {
	long long ret = 0;
	for (int i = 1; i <= n; i++) {
		if (w[i] >= k) {
			sum1[i] = sum1[i - 1] + 1;
			sum2[i] = sum2[i - 1] + v[i];
		} else {
			sum1[i] = sum1[i - 1];
			sum2[i] = sum2[i - 1];
		}
	}
	for (int i = 1; i <= m; i++)
		ret += (sum1[r[i]] - sum1[l[i] - 1]) * (sum2[r[i]] - sum2[l[i] - 1]);
	return S - ret;
}

long long find(int L, int R) {
	if (L == R) return abs(fun(L));
	long long M = (L + R) / 2; 
	long long tmp = fun(arr[M]);
	long long ret = abs(tmp);
	if (tmp > 0) ret = min(find(L, M), ret);
		else if (tmp < 0) ret = min(find(M + 1, R), ret);
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%I64d%I64d%I64d", &n, &m, &S);
	for (int i = 1; i <= n; i++){
		scanf("%I64d%I64d", &w[i], &v[i]);
		arr[i] = w[i];
	}
	sort(arr + 1, arr + n + 1);
	for (int i = 1; i <= m; i++)
		scanf("%I64d%I64d", &l[i], &r[i]);    
	long long ans = find(1, n);
	printf("%I64d", ans);
	return 0;
}

D2T3 观光公交

    易见每个旅客上车时间都已固定，答案取决于下车时间，所以得出贪心操作正确性。然后就是每次氮气都用在在车上人最多的时候。

#include <cstdio>
int n, m, k, t, a, b;
int d[1001], lim[1001], sce[1001], up[1001], down[1001];
	
	int max(int a, int b) { return a > b ? a : b; }
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int p = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i < n; i++) scanf("%d", &d[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &t, &a, &b);
		up[a]++, down[b]++;
		sce[a] = max(sce[a], t);
		p += t;
	}
	for (int i = 1; i <= n; i++)
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	while (k--) {
		int cnt = 0, _max = 0, t = 0;
		for (int i = n; i > 1; i--) {
			if (lim[i] <= sce[i]) cnt = 0;
			cnt += down[i];
			if (d[i - 1] && cnt > _max) _max = cnt, t = i - 1;
		}
		if (!t) break;
		d[t]--;
		for (int i = t + 1; i <= n; i++)
			lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
		ans += down[i] * lim[i];
	}
	printf("%d\n", ans - p);
	return 0;
}