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