首页 算法

# 一些技巧

# 常见的贪心技巧

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

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

# 切题小技巧

  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;
}
  
 更新于