常见的贪心技巧
货币使用问题： 尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。
区间调度问题： 工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。
切题小技巧
- 递归，从后向前
- 预处理
- 划分子结构
- 单调队列、滑动窗口
- 能剪的枝一定要减！能剪的枝一定要减！能剪的枝一定要减！
- 但是剪枝别剪挂了……
手动扩栈
编译时指定参数
-Wl,--stack=size
size是栈的大小，单位为字节。
P5686 [CSP-SJX2019]和积和
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 500005, P = 1e9+7;
int n;
ll a[N], b[N], sa[N], sb[N], s[N], ssa[N], ssb[N];
int main() {
scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%lld", a+i);
for(int i=1; i<=n; ++i) scanf("%lld", b+i);
ll ans = 0, s = 0, sa = 0, sb = 0;
for(int i=n; i>=1; --i) {
sa += a[i]*(n+1-i)%P; sa%=P; sb += b[i]*(n+1-i)%P; sb%=P;
ll del = ((a[i]*sb%P + b[i]*sa%P)%P + P - a[i]*b[i]%P*(n-i+1)%P)%P;
s += del; s %= P;
ans += s; ans %= P;
}
printf("%lld\n", ans);
return 0;
}
U129453 「EZEC-4.5」占座位
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, ll> f;
ll n, k;
ll dfs(ll n) {
if(f[n]) return f[n];
if(n < 2*k+2) return f[n] = 1;
return f[n] = dfs(n/2) + dfs(n-n/2);
}
int main() {
scanf("%lld%lld", &n, &k);
if(k == 0) printf("%lld\n", n); else printf("%lld\n", dfs(n));
return 0;
}
P1182 数列分段 Section II
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m; ll a[N];
bool check(ll v) {
ll sum = 0, pt = 0;
int i=1;
while(i<=n) {
while(i<=n && sum + a[i] <= v) {
sum += a[i];
++i;
}
++pt; if(pt > m) return false; sum = 0;
}
return true;
}
int main() {
//freopen("p1182_1.in","r",stdin);
scanf("%d%d", &n, &m);
ll l=1, r=1e9;
for(int i=1; i<=n; ++i) {
scanf("%lld", a+i);
l = max(l, a[i]);
}
while(l < r-1) {
ll mid = l+(r-l)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l)) printf("%lld\n", l); else printf("%lld\n", r);
return 0;
}
P2822 组合数问题
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 2200, INF = 0x3f3f3f3f;
int c[N][N], sum[N][N];
int T, k;
int main() {
scanf("%d%d", &T, &k);
c[0][0] = 1;
for(int i=1; i<=2000; ++i) {
c[i][0] = 1;
for(int j=1; j<=i; ++j) {
c[i][j] = c[i-1][j-1] + c[i-1][j];
c[i][j] %= k;
}
}
for(int i=0; i<=2000; ++i) {
for(int j=0; j<=i; ++j) {
sum[i][j] = (c[i][j] == 0);
}
}
for(int i=0; i<=2000; ++i) {
for(int j=1; j<=2000; ++j) {
sum[i][j] += sum[i][j-1];
}
}
for(int j=0; j<=2000; ++j) {
for(int i=1; i<=2000; ++i) {
sum[i][j] += sum[i-1][j];
}
}
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", sum[n][min(n,m)]);
}
return 0;
}
P1007 独木桥
求最大时间时，把碰面想象成交换身份即可
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int l, n, p[5005];
int main() {
scanf("%d%d", &l, &n);
for(int i=1; i<=n; ++i) scanf("%d", p+i);
int ans1 = 0;
for(int i=1; i<=n; ++i) {
ans1 = max(ans1, min(p[i], l+1-p[i]));
}
int ans2 = 0;
for(int i=1; i<=n; ++i) {
ans2 = max(ans2, max(p[i], l+1-p[i]));
}
printf("%d %d\n", ans1, ans2);
return 0;
}
P3958 奶酪
特点是自底至上找出通路，可以联想至森林合并。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1100;
struct node {
LL x, y, z;
} a[N];
bool cmp(node a, node b) {
return (a.z < b.z);
}
bool tp[N], bt[N];
int fa[N], T, n;
LL h, r;
int root(int x) {
return fa[x]==x?x:root(fa[x]);
}
bool check(int i, int j) {
LL dist = (a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y) + (a[i].z-a[j].z)*(a[i].z-a[j].z);
return dist <= 4*r*r;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%lld%lld", &n, &h, &r);
memset(bt, false, sizeof bt);
memset(tp, false, sizeof tp);
for(int i=1; i<=n; ++i)
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
sort(a+1, a+n+1, cmp);
for(int i=1; i<=n; ++i) {
if(a[i].z - r <= 0) bt[i] = true;
if(a[i].z + r >= h) tp[i] = true;
}
for(int i=1; i<=n; ++i) fa[i] = i;
for(int i=1; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
if(check(i, j)) {
fa[root(i)] = root(j);
}
}
}
bool fla = false;
for(int i=1; i<=n; ++i) {
if(bt[i] && tp[root(i)]) {
fla = true;
break;
}
}
printf("%s", (fla ? "Yes\n" : "No\n"));
}
return 0;
}