D2T1：贪心、二分、并查集

一些技巧

常见的贪心技巧

货币使用问题：
尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。

区间调度问题：
工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。

切题小技巧

1. 递归，从后向前
2. 预处理
3. 划分子结构
4. 单调队列、滑动窗口
5. 能剪的枝一定要减！能剪的枝一定要减！能剪的枝一定要减！
6. 但是剪枝别剪挂了……

手动扩栈

编译时指定参数

-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 [NOIP2016提高组]组合数问题

#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 [NOIP2017提高组]奶酪

自底至上找出通路，可以联想到森林合并。

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